Chapter1_IntroductiontoEvolutionComputationandSimu

[e-mail]1/11/2020,Page1郑伟诗智能科学系[e-mail]进化计算与模拟退火法遗传算法遗传算法简介遗传算法是什么？遗传算法（GeneticAlgorithm，GA）是进化计算的一个分支，是一种模拟自然界生物进化过程的随机搜索算法。遗传算法的思想来源是怎样的？它由谁提出的？GA思想源于自然界“自然选择”和“优胜劣汰”的进化规律，通过模拟生物进化中的自然选择和交配变异寻找问题的全局最优解。它最早由美国密歇根大学教授JohnH.Holland提出，现在已经广泛应用于各种工程领域的优化问题之中。基本原理遗传算法达尔文进化论现代遗传学生物模拟技术基本原理生物遗传进化•群体•种群•染色体•基因•适应能力•交配•变异•进化结束遗传算法•搜索空间的一组有效解•选择得到的新群体•可行解的编码串•染色体的一个编码单元•染色体的适应值•染色体交换部分基因得到新染色体•染色体某些基因的数值改变•算法结束生物遗传进化过程遗传算法类比关系基本原理种群淘汰的个体新种群淘汰选择交配变异群体父代染色体1父代染色体2子代染色体1子代染色体2生物进化过程遗传基因重组过程基本原理模式定理模式指群体中编码的某些位置具有相似结构的染色体集合模式的定义长度指模式中第一个具有确定取值的基因到最后一个具有确定取值的基因的距离模式的阶指模式中具有确定取值的基因个数Holland的模式定理提出，遗传算法的实质是通过选择、交配和变异算子对模式进行搜索，低阶、定义长度较小且平均适应值高于群体平均适应值的模式在群体中的比例将呈指数级增长。即随着进化的不断进行，较优染色体的个数将快速增加。基本原理积木块假设积木块指低阶、定义长度较小且平均适应值高于群体平均适应值的模式积木块假设认为在遗传算法运行过程中，积木块在遗传算子的影响下能够相互结合，产生新的更加优秀的积木块，最终接近全局最优解。遗传算法的流程流程结构染色体编码群体初始化适应值评价选择算子交配算子变异算子算法流程图和伪代码应用举例函数优化问题算法的执行步骤示意图染色体编码二进制编码方法（BinaryRepresentation）浮点数编码方法（FloatPointRepresentation）minUmaxU12211minmaxminLjLjjXUUU0000…00001111…1111121XX...XXLL群体初始化一般情况下，遗传算法在群体初始化阶段采用的是随机数初始化方法。采用生成随机数的方法，对染色体的每一维变量进行初始化赋值。初始化染色体时必须注意染色体是否满足优化问题对有效解的定义。如果在进化开始时保证初始群体已经是一定程度上的优良群体的话，将能够有效提高算法找到全局最优解的能力。适应值评价评估函数用于评估各个染色体的适应值，进而区分优劣。评估函数常常根据问题的优化目标来确定，比如在求解函数优化问题时，问题定义的目标函数可以作为评估函数的原型。在遗传算法中，规定适应值越大的染色体越优。因此对于一些求解最大值的数值优化问题，我们可以直接套用问题定义的函数表达式。但是对于其他优化问题，问题定义的目标函数表达式必须经过一定的变换。选择算子轮盘赌选择算法30%43%21%6%指针转动方向/*onceofroulettewheelselection*输出参数：*选中的染色体*/procedureRWS1m←0;2r←Random(0,1);//0至1的随机数3fori=1toN4m←m+Pi;5ifr＜=m6returni;7endif8endforendprocedure交配算子在染色体交配阶段，每个染色体能否进行交配由交配概率Pc（一般取值为0.4到0.99之间）决定，其具体过程为：对于每个染色体，如果Random(0,1)小于Pc则表示该染色体可进行交配操作（其中Random(0,1)为[0,1]间均匀分布的随机数），否则染色体不参与交配直接复制到新种群中。每两个按照Pc交配概率选择出来的染色体进行交配，经过交换各自的部分基因，产生两个新的子代染色体。具体操作是随机产生一个有效的交配位置，染色体交换位于该交配位置后的所有基因。交配算子X1X2…XkXk+1Xk+2…XD交配交配位置父代染色体1父代染色体2子代染色体1子代染色体2Y1Y2…YkYk+1Yk+2…YDX1X2…XkYk+1Yk+2…YDY1Y2…YkXk+1Xk+2…XD变异算子染色体的变异作用于基因之上，对于交配后新种群中染色体的每一位基因，根据变异概率Pm判断该基因是否进行变异。如果Random(0,1)小于Pm，则改变该基因的取值（其中Random(0,1)为[0,1]间均匀分布的随机数）。否则该基因不发生变异，保持不变。染色体０１１０１０１００１新染色体００１０１０１００１变异遗传算法流程图和伪代码初始化群体选择交配变异适应值评价，保存最优染色体重新评价适应值，更新最优染色体满足终止条件/*P(t)表示某一代的群体，t为当前进化代数Best表示目前已找到的最优解*/ProcedureGAbegint←0;initialize(P(t));//初始化群体evaluate(P(t));//适应值评价keep_best(P(t));//保存最优染色体while(不满足终止条件)dobeginP(t)←selection(P(t));//选择算子P(t)←crossover(P(t));//交配算子P(t)←mutation(P(t));//变异算子t←t+1;P(t)←P(t-1);evaluate(P(t));if(P(t)的最优适应值大于Best的适应值)//以P(t)的最优染色体替代Bestreplace(Best);endifendend是否开始结束应用举例例4.1已知函数，其中，用遗传算法求解y的11242322214321xxxxx,x,x,xfy554321x,x,x,x最大值。运行步骤步骤1：初始化。假设群体规模为5；使用浮点数编码方式构造染色体，即每个染色体以形式(x1,x2,x3,x4)表示。初始化群体的染色体，得到C1=(-2.1351,2.0917,-0.1327,-4.1006)C2=(1.0152,-3.9811,-2.6638,3.7535)C3=(4.0589,2.1904,-0.1503,0.0023)C4=(-3.4098,-3.0714,-0.9008,-4.3712)C5=(0.2073,2.9932,-4.0802,1.8794)步骤2：适应值评价选择评估函数Eval(C)=计算每个染色体的适应值如下：Eval(C1)=f(-2.1351,2.0917,-0.1327,-4.1006)=0.0373603Eval(C2)=f(1.0152,-3.9811,-2.6638,3.7535)=0.0255988Eval(C3)=f(4.0589,2.1904,-0.1503,0.0023)=0.0448529Eval(C4)=f(-3.4098,-3.0714,-0.9008,-4.3712)=0.0238214Eval(C5)=f(0.2073,2.9932,-4.0802,1.8794)=0.0331319因此Best=C3，Eval(Best)=0.044852911242322214321xxxxx,x,x,xfy步骤3：选择采用轮盘赌选择算法，计算群体适应值总和为0.0373603+0.0255988+0.0448529+0.0238214+0.0331319=0.164765分别计算每个染色体适应值同群体适应值总和的比：C1：0.226749C2：0.155365C3：0.272223C4：0.144578C5：0.201085下面是5次选择产生的[0,1]的随机数和选中的染色体：1：0.278756C22：0.604389C33：0.230964C24：0.376263C25：0.858791C5因此得到种群为C1/=(1.0152,-3.9811,-2.6638,3.7535)C2/=(4.0589,2.1904,-0.1503,0.0023)C3/=(1.0152,-3.9811,-2.6638,3.7535)C4/=(1.0152,-3.9811,-2.6638,3.7535)C5/=(0.2073,2.9932,-4.0802,1.8794)步骤4：交配假设交配概率为0.88。下面是对每个染色体生成的[0,1]的随机数，决定染色体是否参加交配。C1/0.3410440.88参加交配C2/0.61379710.88参加交配C3/0.9630420.88不参加交配C4/0.3475450.88参加交配C5/0.5936770.88参加交配即C1/和C2/、C4/和C5/进行交配，每对染色体交配时随机生成0至3之间的自然数作为交配位。以下是各对染色体的交配位和得到的子代染色体。1.C1/=(1.0152,-3.9811,-2.6638,3.7535)和C2/=(4.0589,2.1904,-0.1503,0.0023)交配位为1；子代染色体为：C1//=(1.0152,-3.9811,-0.1503,0.0023)C2//=(4.0589,2.1904,-2.6638,3.7535)2．C4/=(1.0152,-3.9811,-2.6638,3.7535)和C5/=(0.2073,2.9932,-4.0802,1.8794)交配位为2；子代染色体为：C4//=(1.0152,-3.9811,-2.6638,1.8794)C5//=(0.2073,2.9932,-4.0802,3.7535)故交配后的新种群为：C1//=(1.0152,-3.9811,-0.1503,0.0023)C2//=(4.0589,2.1904,-2.6638,3.7535)C3//=(1.0152,-3.9811,-2.6638,3.7535)C4//=(1.0152,-3.9811,-2.6638,1.8794)C5//=(0.2073,2.9932,-4.0802,3.7535)步骤5：变异假设变异概率为0.1。对于每个染色体的每个基因随机生成[0,1]的随机数，若该随机数小于0.1，则改变基因的值，否则不改变基因的值。以下是发生变异的染色体和基因改变的过程。C3//=(1.0152,-3.9811,-2.6638,3.7535)→C3///=(3.0953,-3.9811,-2.6638,3.7535)C4//=(1.0152,-3.9811,-2.6638,1.8794)→C4///=(1.0152,0.0153,-2.6638,1.8794)故得到的新群体为C1///=(1.0152,-3.9811,-0.1503,0.0023)C2///=(4.0589,2.1904,-2.6638,3.7535)C3///=(3.0953,-3.9811,-2.6638,3.7535)C4///=(1.0152,0.0153,-2.6638,1.8794)C5///=(0.2073,2.9932,-4.0802,3.7535)步骤6：重新评价染色体适应值，更新Best计算每个染色体的适应值如下：Eval(C1///)=f(1.0152,-3.9811,-0.1503,0.0023)=0.0558585Eval(C2///)=f(4.0589,2.1904,-2.6638,3.7535)=0.0230112Eval(C3///)=f(3.0953,-3.9811,-2.6638,3.7535)=0.0210019Eval(C4///)=f(1.0152,0.0153,-2.6638,1.8794)=0.0789962Eval(C5///)=f(0.2073,2.9932,-4.0802,3.7535)=0.0245465因为Max(0.0