第七章 遗传算法的理论基础

第七章遗传算法的理论基础武汉大学计算机学院7.1模式定理模式定理是由Holland所提出的，其目的是从理论上解释遗传算法的有效性。Holland的模式定理是针对简单遗传算法(SGA)而言的，即假定在遗传算法中，种群的规模不变，使用二进制编码、基于适应值比例的选择策略、单点杂交算子和通常的变异算子。7.1模式定理字符集{0,1,*}上的一个字符串称为一个模式在一个模式中，*表示一个不确定的字符，即表示0或1，所以一个模式可以表示一个二进制位串的集合。例模式*0101表示集合{00101,10101}，而模式0**1*表示集合{00010，00011，00110，00111，01010，01011，01110，01111}。在一个模式中，字符0或1所出现的位置称为确定位置，字符*所出现的位置称为不确定位置。7.1模式定理模式H中确定位置的个数称为模式H的阶,记为例模式H中第一个确定位置与最后一个确定位置之间的距离称为模式H的定义长度，记为例设s是一个长度为的二进制位串，H是一个长度为的模式，若则称s与模式H匹配。)(Ho,4)0101(*o2*)1**0(o)(H,325)0101(*213**)*1*0(,Hs7.1模式定理二进制位串00与下列模式匹配：00，*0，0*，**二进制位串110与下列模式匹配：110,*10,1*0,11*,**0,*1*,1**,***.定义假设表示SGA在第t代时的种群，f为SGA所使用的适应函数，H为任一模式，则称P(t)中与模式H匹配的个体的平均适应值为模式H在第t代的适应值，记为即有)}(,),(),({)(21tvtvtvtPN),,(tHf)()()(1),(tPHvvftPHtHf7.1模式定理例假定当前种群中的个体及适应值如表1所示，则模式H及其适应值如表2所示。个体适应值1011000101105123表1个体及其适应值Hf(H,t)*****0*1**00(5+1+2+3)/4=2.75(1+2+3)/3=2(2+3)/2=2.51/1=1表2模式及其适应值7.1模式定理定理7.1(模式定理)设表示SGA在第t代时的种群，SGA的杂交概率和变异概率分别为和H为任一模式，表示第t代种群中与H匹配个体的个数，则有估计式其中为P(t)中个体的平均适应值，为个体的编码长度。)}(,),(),({)(21tvtvtvtPNcp,mp),(tHMmcpHolHptftHftHMtHM)(1)(1)(),(),()1,()(tfl6.1模式定理证首先考虑选择对模式H的影响。由于SGA采用基于适应值比例的选择策略，所以在第t代种群P(t)中，与H匹配的个体被选择作为父体的个数的期望值为)(),(),()(),()(),()()()()()()(tftHftHMNvftHMvftHMvfvfNtPvtPHvtPvtPHv6.1模式定理再考虑杂交算子对模式的影响。杂交算子随机地选取1到中的一个位置，并交换两个父体中所选取位置右边的子串。显然，若选取的杂交位置不在模式H的第一个确定位置和最后一个确定位置之间，那么原来属于H中的个体经杂交后仍然属于H。若所选取的杂交位置在模式H的第一个确定位置和最后一个确定位置之间，那么原来属于H中的个体经杂交后有可能不再属于H。1l例如那么有若111000与101011进行杂交，且随机选择的杂交位置为3，杂交后所得到的两个后代分别为111011和101000，这两个后代均不属于H。*0***1*}101100001100,111000,,100100,101011,001101{)(HtP,111000H6.1模式定理原来属于H中的个体经杂交后也有可能仍然属于H。例如若在上面的例子中111000与001100进行杂交，杂交位置仍为3，那么杂交后所得到的两个子串为111100和001000，其中后代111100仍然属于H。属于模式H的个体经杂交后不属于模式H的概率至多为1)(lHpc6.1模式定理属于模式H的个体经杂交后仍属于模式H的概率至少为由于选择和杂交是相互独立的，所以经过选择和杂交后种群中近似地有个与H匹配的个体1)(1lHpc1)(1)(),(),(lHptftHftHMc6.1模式定理最后讨论变异算子对模式H的影响。对于一个属于模式H的个体v，变异算子以概率对v的每一位相互独立地进行变异，当且仅当变异算子在H的个确定位置上不对v进行变异时，经变异算子后所得到的个体仍然属于H。由于对某一位不进行变异的概率为，于是属于模式H中个体v经变异后仍然属于模式H的概率为mp)(Homp1)()1(Homp6.1模式定理经选择、杂交、变异操作后，第t+1代中包含模式H的个体数目有以下估计式：)1,(tHMmcmmcHomcpHolHptftHftHMppHolHptftHftHMplHptftHftHMtHM)(1)(1)(),(),()1())(1(1)(1)(),(),()1(1)(1)(),(),()1,()(若6.1模式定理推论在SGA中，定义长度较短、低阶且适应值大于种群平均适应值的模式H，在种群中的数目呈指数增长证设对任意都有其中为一个常数。并设,ttCtftHf)(),(1CmcpHolHpCK)(1)(16.1模式定理当时，由定理知于是推论成立。tmcKHMKtHMpHolHoptftHftHMtHM)0,()1,()(1)(1)1()1,()1,(),(6.2基于有限马尔可夫链的收敛性分析定义设是遗传算法当代数为t时的种群，为适应函数，表示种群的最优适应值，表示全局最优适应值。若则称遗传算法依概率收敛于全局最优解。)}(,),(),({)(21txtxtxtPN)(xf},,2,1|))((max{NktxfZkt}}1,0{|)(max{*lxxff1}{lim*fZPtt6.2基于有限马尔可夫链的收敛性分析end.solution;bestthereturnwhile;end;1));(select()1();)(evaluate());(mutate()1());(crossover()(docondition)nterminatio(notwhile));(evaluate());((initialize;0begingorithmGenetic_AlproceduretttPtPtPtPtPtPtPtPtPt6.2基于有限马尔可夫链的收敛性分析定理7.2若杂交概率和变异概率满足适应函数不恒等于一个常数，则SGA不能依概率收敛于全局最优解。cpmp,10cp)(xf,10mp6.2基于有限马尔可夫链的收敛性分析定理7.2说明了简单遗传算法不能依概率收敛到全局最优解，但只要对简单遗传算法作一点改动，每次将当前找到的最好解保留下来，在算法结束后，将所保留的最好解作为问题的最优解或近似最优解输出，则可证明修改后的遗传算法依概率收敛到全局最优解。改进后的简单遗传算法描述如下：6.2基于有限马尔可夫链的收敛性分析end.solution;bestthereturnwhile;end;1chromsome;bestthekeep));(select()1();)(evaluate());(mutate()1());(crossover()(docondition)nterminatio(notwhile));(evaluate());((initialize;0beginAImproved_GproceduretttPtPtPtPtPtPtPtPtPt6.2基于有限马尔可夫链的收敛性分析定理7.3改进后的简单遗传算法依概率收敛到全局最优解。演化计算读书报告题目(下列题目选择之一)1用遗传算法或演化策略求解下列优化问题(n=2)并研究问题的维数对算法性能的影响。2使用路径表示设计并实现一个求解具有30个城市的旅行商问题的遗传算法,假定问题的距离矩阵由平面上随机生成的30个点之间的距离给定。并比较PMX杂交算子和OX杂交算子对算法性能的影响71828.2;,,2,1,303020)2cos(1exp12.0exp20),...,(min1121enixexnxnxxfiniiniin3用遗传算法求解下列约束优化问题：其中4演化计算学习过程中的一些心得体会。)()2sin()2(sin)(max2131213xxxxxxf100,1000)4(101212221221xxxxxx