遗传算法最终章教材

遗传算法及其MATLAB实现第4组唐煦尧朱萌萌廉馨6/17/2024目录概念及背景知识流程图算法应用程序6/17/2024

遗传算法的概念最早是由BagleyJ.D于1967年提出的。后来Michigan大学的J.H.Holland教授于1975年开始对遗传算法（GeneticAlgorithm,GA）的机理进行系统化的研究。遗传算法是对达尔文生物进化理论的简单模拟，其遵循“适者生存”、“优胜略汰”的原理。遗传算法是一种通过模拟自然进化过程搜索最优解的方法。它被提出以来，在函数优化、生产调度、模式识别、神经网络、自适应控制等领域得到了广泛的应用，大大提高了问题求解的效率。现实生活中很多问题都可以转换为函数优化问题，遗传算法则大大提高了求解全局最优解的效率，具有很高的价值。概念及背景知识6/17/2024流程图初始化数据统计计算选择交叉突变遗传迭代结束？否结束是6/17/2024例题：求maxf(x(1),x(2))=21.5+x(1)*sin(4πx(1))+x(2)*sin(20πx(2))

-3.0≤x(1)≤12.1

s.t.4.1≤x(2)≤5.8函数f（x1，x2）的三维图形如图所示。6/17/2024（1）编码首先要进行编码工作，即将变量转化成二进制数串。数串的长度取决于所要求的精度。例如，变量x的区间是（L,U），要求的精度是小数点后4位，也就意味着每个变量应该被分成至少（L,U）*10^4个部分。对一个变量的二进制数串位数用以下公式计算：本例精度要求保留小数点后4位，则目标函数的两个自变量x1及x2所构成的染色体数串可以表示如下：本例中任一染色体数串都是33位，即000001010100101001101111011111110.以上编码前18位表示x1，后15位表示x2，如下表所示。6/17/2024则二进制转化成十进制为假设初始种群中有10个个体，其染色体可随机生成如下：6/17/2024相对应的十进制的实际值[x1，x2]为6/17/20246/17/2024(2)评价个体适应度对一个染色体数串的适应度的评价由以下三个步骤组成：①将染色体串进行解码，转换成真实值，即：

②评价目标函数f=-f（x）③将目标函数值转为适应度，上述染色体的适应度值如下：6/17/20246/17/2024依照染色体的适应度值进行新种群的复制，步骤如下：①计算染色体的适应度值

②计算种群的适应度值总和：③计算每个染色体被复制的概率：④计算每个染色体被复制的累积概率：6/17/2024（3）新种群复制依照轮盘选择法，转动轮盘10次（种群中有10条染色体），每次选择一个作为新种群的染色体。假设10次中产生的0~1随机数序列如下：

0.3014310.3220620.7665030.8818930.3508710.5383920.1776180.3432420.0326850.197577根据以上的计算方法，可以先计算出种群中每个染色体的适应度和概率，如下表所列。利用计算机模拟轮盘选择法，假设计算机产生10个[0,1]区间的随机数列如下：6/17/2024第1个随机数为0.301431，大于Q3小于Q4，所以U4被选中；第2个随机数为0.322062，大于Q3小于Q4，所以U4再次被选中；……第10个随机数为0.197577，大于Q1小于Q2，所以被U2选中；依照轮盘选择法，新种群的染色体组成如下：这种轮盘选择法的机理是：染色体的适应度大意味着[Qk,Qk+1]区间跨度就大，随机数发生器产生的均匀随机数就会有更大的概率落在较大长度的[Qk，Qk+1]区间里，这样具有较大Pk值的染色体自然更有机会复制到下一代。6/17/20246/17/2024（4）新种群交配①交配染色体数量的确定

交配染色体数量=染色体总量×交配概率

[10×0.25]=2即交配染色体数目为2②交配染色体对象的确立

用计算机产生[0,1]区间的10个随机数，确定其分别对应10个个体，其中低于交配概率的参加交配。③在交配池发生交配6/17/2024（5）基因突变假设突变几率P为0.01，亦即种群内所有基因都有0.01的概率进行突变。本例中共有33×10＝330个基因，即希望每一代中有3.3个突变基因，每个基因的突变概率是均等的。因此，将产生330个介于0~1之间的随机数，然后将该随机数小于0.01者选出，并将其对应的基因值加以翻转，如下表：表中第一列显示的是具体在哪些染色体以及在什么染色体的什么位置进行了突变。如，其中第一行表示在第4条染色体的第6个基因上发生了突变，因为第4条染色体的第6个基因对应的基因编号是33×（4-1)+6＝105。6/17/2024在突变后，最终新种群染色体组成如下：新一代的相对应实际值[x(1),x(2)]和适应度值如下：6/17/2024至此，已完成遗传算法的第一代流程。至此迭代，在第451代得到对应最大目标函数值的染色体：

U=[111110000000111000111101001010110]相应实际值[x(1),x(2)]=[11.631407,5,724824],适应度值eval(U)=f(11.631407,5,724824)=38.818208

从以上实例可以得出两点结论：

①遗传算法本质上是一种启发式的随机搜索算法，所以由遗传算法得出的结果每次都不尽相同。

②自变量在给定的约束条件下进行了无缝编码（即这种编码方式能够表达解空间中的所有可行解），所以从理论上讲，遗传算法总有很多机会得到全局最优结果而不是局部最优结果。6/17/2024应用程序例题：求maxf(x(1),x(2))=21.5+x(1)*sin(4πx(1))+x(2)*sin(20πx(2))

-3.0≤x(1)≤12.1

s.t.4.1≤x(2)≤5.8具体求解过程如下：①编写M文件：

functionf=lbw(x)if(x(1)>12.1||x(1)<-3.0||x(2)>5.8||x(2)<4.1)f=300;elsef=-21.5-x(1)*sin(4*pi*x(1))-x(2)*sin(20*pi*x(2));end6/17/2024

②在命令窗口输入：>>clearall;>>options=gaoptimset('Generations',600,'StallGenLimit',451,'PlotFcns',@gaplotbestf);>>[x,f]=ga(@lbw,2,options)设置遗传算法的参数和句柄函数超过连续代数不进化则算法停止超过进化代数时算法停止绘图函数，可供选择的有@gaplotbes