遗传算法实验设计与仿真

遗传算法与研究课程设计学号：200704134069姓名：吴宇鑫学院：信息科学与工程学院专业：自动化班级：073班设计时间：2011-3-16至2011-4-6指导教师：吴怀宇一．设计内容(一)设计题目求下面函数的最大值2020)202040(sin)(101xxxiiiixf(二)设计的目的掌握遗传算法的基本原理,了解在MATLAB环境中实现遗传算法各算子的编程方法。并以此例说明所编程序在函数全局寻优中的应用。二．设计方案（一）理论基础1.遗传算法简介遗传算法是进化算法中产生最早、影响最大、应用也比较广泛的一个研究方向和领域，其基本思想是由美国密执安大学的JohnH.Holland教授于1962年率先提出的。1975年，他出版了专著《自然与人工系统中的适应性行为》(AdaptationinNaturalandArtificialSystems)[19]，该书系统地阐述了遗传算法的基本理论和方法，确立了遗传算法的基本数学框架。此后，从事遗传算法研究的学者越来越多，使之成为一种通用于多领域中的优化算法。遗传算法是一种基于生物的自然选择和群体遗传机理的搜索算法。它模拟了自然选择和自然遗传过程中发生的繁殖、交配和突变现象。它将每个可能的解看做是群体（所有可能解）中的一个个体，并将每个个体编码成字符串的形式，根据预定的目标函数对每个个体进行评价，给出一个适应度值。开始时总是随机地产生一些个体（即候选解），根据这些个体的适应度利用遗传算子对这些个体进行操作，得到一群新个体，这群新个体由于继承了上一代的一些优良性状，因而明显优于上一代，这样逐步朝着更优解的方向进化。遗传算法在每一代同时搜索参数空间的不同区域，然后把注意力集中到解空间中期望值最高的部分，从而使找到全局最优解的可能性大大增加。作为进化算法的一个重要组成部分，遗传算法不仅包含了进化算法的基本形式和全部优点，同时还具备若干独特的性能：1)在求解问题时，遗传算法首先要选择编码方式，它直接处理的对象是参数的编码集而不是问题参数本身，搜索过程既不受优化函数连续性的约束，也没有函数导数必须存在的要求。通过优良染色体基因的重组，遗传算法可以有效地处理传统上非常复杂的优化函数求解问题。2)若遗传算法在每一代对群体规模为n的个体进行操作，实际上处理了大约O（n3）个模式，具有很高的并行性，因而具有明显的搜索效率。3)在所求解问题为非连续、多峰以及有噪声的情况下，能够以很大的概率收敛到最优解或满意解，因而具有较好的全局最优解求解能力。4)对函数的性态无要求，针对某一问题的遗传算法经简单修改即可适应于其他问题，或者加入特定问题的领域知识，或者与已有算法相结合，能够较好地解决一类复杂问题，因而具有较好的普适性和易扩充性。5)遗传算法的基本思想简单，运行方式和实现步骤规范，便于具体使用。2.遗传算法对问题的描述对于一个求函数最大值的优化问题（求函数最小值也雷同），一般可描述为下述数学规划模型：URRX.t.s)X(fmax(1)式中，X=[x1,x2,…,xn]T为决策变量，f(X)为目标函数，RX和UR为约束条件，U是基本空间，R是U的一个子集。集合R表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。它们的关系如图1所示。图1最优化问题的可行解及可行解集合在遗传算法中，将n维决策向量X=[x1,x2,…,xn]T用n个记号Xi（i=1，2，…，n）所组成的符号串X来表示：X=X1X2…XnX=[x1,x2,…,xn]T把每个Xi看作一个遗传基因，它的所有可能取值称为等位基因，这样，X就可看做是由n个遗传基因所组成的一个染色体。一般情况下，染色体的长度n是固定的，但对一些问题n也可以是变化的。根据不同的情况，这里的等位基因可以是一组整数，也可以是某一范围内的实数值，或者是纯粹的一个符号。最简单的等位基因是由0和1这两个整数组成的，相应的染色体就可表示为一个二进制符号串。这种编码所形成的排列形式X是个体的基因型，与它对应的X值是个体的表现型。通常个体的表现型和基因型是一一对应的，但有时也允许基因型和表现型是多对一的关系。染色体X也称为个体X，对于每个个体X，要按照一定的规则确定出其适应度。个体的适应度与其对应的个体表现型X的目标函数值相关联，X越接近于目标函数的最优点，其适应度越大；反之，其适应度越小。在遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的，从而由所有的染色体X就组成了问题的搜索空间。生物的进化是以集体为主体的。与此相对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体（或种群）。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代的过程，第ｔ代群体记做P(t)，经过一代遗传和进化后，得到第t+1代群体，它们也是由多个个体组成的集合，记做P(t+1)。这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现型X将达到或接近于问题的最优解X*。生物的进化过程主要是通过染色体之间的交叉和染色体的变异来完成的。与此相对应，基本空间可行解集合URX可行解遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用所谓的遗传算子作用于群体P(t)中，进行下述遗传操作，从而得到新一代群体P(t+1)。·选择（selectin）：根据各个个体的适应度，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。·交叉（crossover）：将群体P(t)内的各个个体随机搭配成对，对每一对个体，以某个概率（称为交叉概率，crossoverrate）交换它们之间的部分染色体。·变异（mutation）：对群体P(t)中的每一个个体，以某一概率（称为变异概率，mutationrate）改变某一个或某一些基因座上的基因值为其他的等位基因。3.遗传算法的运算流程遗传算法的主要运算流程如下：步骤一：初始化。设置进化代数计数器t=0；设置最大进化代数T；随机生成M个个体作为初始群体P(0)。步骤二：个体评价。计算群体P(t)中各个个体的适应度。步骤三：选择运算。将选择算子作用于群体。步骤四：交叉运算。将交叉算子作用于群体。步骤五：变异运算。将变异算子作用于群体。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。步骤六：终止条件判断。若t≤T，则：t=t+1，转到步骤二；若tT，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。具体的流程示意图见图2所示。图2遗传算法的运算过程示意4.基本遗传算法基于对自然界中生物遗传与进化机理的模仿，针对不同的问题，很多学者设计了许多不同的编码方法来表示问题的可行解，开发了许多种不同的遗传算子来模仿不同环境下的生物群体P(t)选择运算交叉运算变异运算群体P(t+1)解码解集合个体评价遗传空间解空间遗传特性。这样，由不同的编码方法和不同的遗传算子就构成了各种不同的遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。基于这个共同特点，Goldberg总结出了一种统一的最基本的遗传算法——基本遗传算法（simplegeneticalgorithms，简称SGA）[20]。基本遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。（1）编码方法用遗传算法求解问题时，不是对所求解问题的实际决策变量直接进行操作，而是对表示可行解的个体编码的操作，不断搜索出适应度较高的个体，并在群体中增加其数量，最终寻找到问题的最优解或近似最优解。因此，必须建立问题的可行解的实际表示和遗传算法的染色体位串结构之间的联系。在遗传算法中，把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称之为编码。反之，个体从搜索空间的基因型变换到解空间的表现型的方法称之为解码方法。编码是应用遗传算法是需要解决的首要问题，也是一个关键步骤。迄今为止人们已经设计出了许多种不同的编码方法。基本遗传算法使用的是二进制符号0和1所组成的二进制符号集｛0，1｝，也就是说，把问题空间的参数表示为基于字符集｛0，1｝构成的染色体位串。每个个体的染色体中所包含的数字的个数L称为染色体的长度或称为符号串的长度。一般染色体的长度L为一固定的数，如X=10011100100011010100表示一个个体，该个体的染色体长度L=20。二进制编码符号串的长度与问题所要求的求解精度有关。假设某一参数的取值范围是[a，b]，我们用长度为L的二进制编码符号串来表示该参数，总共能产生L2种不同的编码，若参数与编码的对应关系为00000000000……00000000=0→a00000000000……00000001=1→a+δ•••111111111111……11111111=L2-1→b则二进制编码的编码精度12Lab假设某一个个体的编码是klkkkaaax21，则对应的解码公式为)2(121LjjLkjLkaabax例如，对于x[0,1023],若用长度为10的二进制编码来表示该参数的话，则下述符号串：x=0010101111就表示一个个体，它对应的参数值是x=175.此时的编码精度为1.二进制编码方法相对于其它编码方法的优点，首先是编码、解码操作简单易行；其次是交叉遗传操作便于实现；另外便于对算法进行理论分析。（2）个体适应度函数在遗传算法中，根据个体适应度的大小来确定该个体在选择操作中被选定的概率。个体的适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。基本遗传算法使用比例选择操作方法来确定群体中各个个体是否有可能遗传到下一代群体中。为了正确计算不同情况下各个个体的选择概率，要求所有个体的适应度必须为正数或为零，不能是负数。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好目标函数值为负数时的处理方法。设所求解的问题为：max()fx，xD.对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的问题，即min()max(()).fxfx当优化问题是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适应度函数值()Fx就等于相应的目标函数值()fx，即()()Fxfx.但实际目标优化问题中的目标函数有正也有负，优化目标有求函数最大值，也有求函数最小值，显然上面两式保证不了所有情况下个体的适应度都是非负数这个要求，必须寻求出一种通用且有效的由目标函数值到适应度之间的转换关系，有它来保证个体适应度总取非负值。为满足适应度取负值的要求,基本遗传算法一般采用下面方法将目标函数值()fx变换为个体的适应度().Fx对于求目标函数最大值的优化方法问题，变换方法为min(),fxCmin()0fxC时，()Fx0min()0fxC时，式中，minC为一个适当的相对比较小的数，它可以是预先指定的一个较小的数，或进化到当前代为止的最小目标函数值，又或当前代或最近几代群体中的最小目标函数值。（3）基本遗传操作方法①比例选择：选择或称复制，建立在对个体适应度进行评价的基础之上。其作用是从当前群体中选择出一些比较优良的个体，并将其复制到下一代群体中。基本遗传算法采用比例选择的方法，所谓比例选择，是指个体在选择操作中被选中的概率与该个体的适应度大小成正比。②单点交叉：单点交叉又称简单交叉，是遗传算法所使用的交叉操作方法。③基本位变异：基本位变异石最简单和最基本的变异操作，也是基本遗传算法中所使用的变异操作方法。对于基本遗传算法中用二进制编码符号串所表示的个体，对