资源描述：
《论文演化算法的收敛性分析及算法改进》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、演化算法的收敛性分析及算法改进覃俊%，!康立山%陈毓屏%%（武汉大学软件工程国家重点实验室，武汉I#""J!）!（中南民族大学计科院，武汉I#""JI）5>1*0)：K8LMNLOD(31*0)$B(1摘要文章利用马尔可夫随机过程刻画了演化算法，证明了标准演化算法是不收敛的，说明了演化算法收敛于最优解的必要条件：非完全遍历性。并论证了采取精华保留策略的标准遗传算法以概率%收敛于最优解，并据此分析了一个典型实例——CPC<算法的收敛性及其算法改进方案。关键词遗传算法收敛性精华策略文章编号%""!>Q##
2、%>（!""#）%&>""&%>"!文献标识码<中图分类号PR#"%$S!"#$%&’#()#&*#+&,-./0/,&1+-)%(02"3435(%’#3#&2%6$%3572,20%&+-)%(02"380&97&:，;<,&)=0/",&:$"#&>750&):%（PD4/3*34T49U*V(8*3(89(W/(W3K*845+=0+4480+=，X2D*+Y+0648A039，X2D*+I#""J!）!（/(23D:4+348Y+0648A039W(8Z*30(+*)0304A，X2D*+I
3、#""JI）+?/2(,*2：PD4B(1;23*30(+*)=(803D10A604K4,K03D*1*8?(6BD*0+$[30A34A30W04,3D*33D4B)*AA0BB(1;23*30(+*)=(7803D10A+(3B(+648=4,3((;301*)84A()230(+2+30)*+4)030A3A38*34=90A2A4,$@(84(648，*W*1(2AB(1;23*30(+*)=(803D10AA32,04,$<#.@%(1/：:(1;23*30(+*)=(803D1，:(+6
4、48=4+B4，5)030A3A38*34=9%引言随机生成一个初始群体演化算法的理论分析主要集中在三个方面：一方面是由确定每一个体适应值按比例选择机制进行选择挑出父体’())*+,提出的模式定理，并在其基础上导出的隐含并行定理，84;4*3这些理论是从基因空间（编码空间）这一较低层的角度去抽象以概率!"杂交算法。第二个方面是基于偏序关系的理论在偏序空间分析了演以概率!#变异化算法的收敛性，文献-%.利用偏序集的一些结论导出了隐含并计算个体适应值行性的定量分析。这两种方法虽然定量地估算出了具有较优结按
5、比例选择机制进行选择挑出父体构特点的模式在进化过程中的增长规律以及并行性度量，但未2+30)终止条件能导出遗法算法能够收敛于问题最优解的概率。还有许多学者其中算法的比例选择是指按适应值高低比例选取父体。越从其它方面去刻画演化算法，如模拟演化算法（/012)*34,56(7好的个体（这里指适应值越小）被选中的概率越大。)230(+*89:(1;23*30(+）模型，类模拟退火（/012)*34,<++4*)0+=>从算法易见，:C<的选择、杂交和变异算子都是独立随机)0?4）方法等。还有学者结合具体的应
6、用来分析演化算法，如适进行的，新群体仅与其父代群体及遗传算子有关，而与其父代应值地图，最优控制理论，小生境技术等，从不同角度刻画了演群体之前的各代群体无关，即满足后无效性，并且各代群体之化算法，对算法的设计、分析和应用都有一定意义。但对算法收间的转换概率与时间起点无关，即:C<构成的@*8?(6链是时敛性分析未能给出较一般的框架-#.。齐的。该文试图基于马尔可夫随机过程这个较高层的角度去刻!$%（#，#&%）E!F’（#G%）E%(’（#）)$H)!$%画演化算法。如果把演化算法进化过程中的每一代群体
7、看作为其中$，%!*为状态，#为起始时刻。并且初始分布对一种状态的话，则可以把整个进化过程作为一个随机过程来考@*8?(6链极限行为无影响，所以初始群体分布可任意。查，并可利用@*8?(6链来对进化过程进行收敛性分析。-结论%.：基本遗传算法收敛于最优解的概率小于%。证明将群体的各种可能状态*分为包括最优个体的状态!标准演化算法描述及其收敛性分析*"和不包括最优个体的状态*+；*)*""*+（*"#*+E!）。要证明!%进标准演化算法（:)*AA0BC4+430B<)=(803D1，简称:C<）求解入
8、*"状态的稳定概率小于%。此类优化问题的算法框架描述如下：用反证法。假设基本遗传算法能收敛于最优解的概率等于基金项目：国家自然科学基金（编号：S&S#"#"，S""J#"I#，J""J%"I!）作者简介：覃俊（%&SQ>），女，副教授，在职博士生，主要研究领域：遗传算法，电子商务，数据库与T]]。计算机工程与应用!""#$%&&%%，则进入!"状态的稳定概率应等于"，即：部最优，要么所找的多目标优化解不完全（H15IJ7解集中在某’()$+$#"!",
