改进的多种群遗传算法及其应用资料下载.pdf

1、Min（）Xf，ba，X，其中，（）nxxxX,21=，（）naaa,a21=，（）nbbb,b21=，iiibax,，ni,2,1?=。2010 International Conference on Circuit and Signal Processing 978-1-4244-6782-2/10/$26.00 2010 IEEE 3262.1 个体间距离的改进及其优越性证明 传统的海明距离定义如下：（）=nkjkikjiijxxxxd12 （1）其中，Nji,2,1,=且ji。但是当各决策变量的取值范围不一样时，海明距离应用起来有一定的局限性，会产生虚假距离现象。也就是说当各变量的可行

2、域不同时，取值范围大的变量在海明距离的计算中起主导作用，尤其差异很大时，此现象更为明显。为了解决这一问题，我们定义两个单独个体ix与jx之间的归一化海明距离为个体间距离。nxxDnkkjkikij=12 （2）其中，Nji,2,1,=且ji，kkkab=。与海明距离的定义相比，改进的个体间距离考虑了由于变量取值范围差异导致的假距离现象，使个体间距离与各变量的取值范围无关，较之海明距离更为合理；并且距离的取值在 0 到 1 之间变化，易于操作。为了说明此改进方案的优越性，下面举例给出统计验证。证明：假设种群中每个个体包含 3 个基因，第i个个体为,321iiixxx，并且 101ix，即11=；

3、1002ix，即102=；10003ix，即1003=。在规定区域内随机产生 200 个个体，并随机配成 100对，则第i对个体对应基因的绝对距离为：1,021111=iiixx；10,022122=iiixx；100,023133=iiixx；其中，11 ix和21 ix分别是第i对个体的一对对应基因。由公式（1）计算 100 对个体的海明距离为：,10021ddd；由公式（2）计算 100 对个体的的改进距离为：,10021DDD。由数理统计知识可知第 k 个基因与海明距离的相关度计算公式如下：=10011001221001）（*）（）（*）（iiikikiikikkddddroo 其中，

4、3,2,1=k，ik是第 i 对个体第 k 个基因的绝对距离，ko是 100 个ik的平均值，d是 100 个海明距离的平均值。经过 Matlab 多次随机试验得到的结果相都差无几，其中一次为：1r=0.0059；2r=0.0877；3r=0.9991。同理，第 k 个基因与改进个体距离的相关度计算公式为：=10011001221001）（*）（）（*）（iiikikiikikkDDDDRoo 其中，D是 100 个改进个体距离的平均值。经过 Matlab 多次随机试验得到的计算结果也趋于稳定，其中一次为：1R=0.6317；2R=0.5826；3R=0.6193。从相关度分析可以看出，随着基

5、因所属范围不断变大，基因与海明距离的相关度也不断增加，而基因与改进个体距离的相关度却基本保持平衡，有效避免了虚假距离现象，保证了公平与准确性。证毕 2.2 种群间距离的改进 种群距离：两个子种群中心之间的归一化海明距离。nxxDnkkejkeikeij=12 （3）其中，Mji,2,1,=且ji，NxxNpipkeik=1为第 i 个子种群的第 k 个变量的中心。同理，改进的种群距离也与各变量取值范围的差异无关，并且取值在 0 到 1 之间变化。种群分散度：所有个体的分散程度的归一化表示。2MMijeijdispCDD=（4）其中，Mji,2,1,=且ji。3自适应调整搜索范围 为保持各子种群

6、的相对独立，各子种群间不直接发生交叉关系，而是通过精英种群间接地引进其它子种群的优秀基因。在交叉时偶尔从精英种群中引进一个优质个体，以改善种群质量。精英种群集中了群落中最优秀的个体，还享有在整个可行域内活动的特权，这样就可以通过协同进化把全局最优基因输送到各个可行域不断缩小的子种327群，提高找到全局最优解的概率。合理地减小搜索区域的范围可以降低搜索的盲目性、提高精度，但是基于进化代数直接强制收缩搜索区域的方案会导致可能错过最优解。我们根据种群进化的进程、种群的主要活动范围，来确定并逐步地缩小搜索区域，以提高算法的收敛效率。并以个体间距离、种群间距离和种群分散度作为搜索区域变化的判断依据和决策

7、量。在执行某一子种群的缩减搜索区域这一操作时，首先用（2）式计算精英种群个体之间的距离ijD，Mji,2,1,=且ji，然后求其最大值，令maxD=MaxijD。然后用（3）式计算该子种群与精英种群之间的距离eliteD，若eliteD（01），则保留该子种群的最优个体，并取消该子种群的存在。若dispD且maxD（和是预先设定的 0 到1 之间的值），则执行收缩搜索区域的操作。为了最终决定搜索区域变化的程度，我们引入收缩因子，由（5）式求得。=4.024.026.026.0maxmaxmaxdispelitedispelitedispeliteDDDothersDDDDDD （5）然后按照（

8、6）式计算该子种群的下一代搜索区域范围。+=）（）（111111ttttttttabcbabcaoo （6）其中，o1tc是该子种群最优个体的位置。为了避免新的搜索区域超出前代，采用（7）式和（8）式进行调整。其它11,=tttttbbbbb （8）依照以上所述方法对所有子种群的搜索区域逐个进行自适应变化。4算法步骤 Step1：初始化子种群个数 M、子种群规模 N、搜索范围a，b、以及终止迭代次数 T 等参数。Step2：在可行域内随机生成 M 个子种群和一个精英种群，每个子种群包含 N 个个体，采用浮点数对个体进行编码。Step3：计算个体的目标函数值，对各子种群中个体的适应度进行比较并排

9、序，从每个子种群中选取较优的 N/M个个体输送到精英种群中。Step4：判断终止条件是否满足。如满足，则结束进化；否则，继续。Step5：按顺序选定一个子种群，判断该子种群是否还有存在价值，若无，则剔除，M=M-1，返回 Step5。判断该子种群的搜索区域变化条件是否满足。如满足，则依据（5）-（8）式自适应变化；Step6：采取带有最优保留策略的比例选择操作完成该子种群父代个体的选择，对父代子种群用协同进化的方法执行交叉和变异操作，得到新一代子种群。Step7：判断是否所有子种群都操作结束。否则，转至Step5。Step8：从 M 个新一代子种群中各选取 N/M-4 个最优个体作为精英种群成

10、员，替换精英组织中的劣解，完成对精英种群的更新操作，然后返回 Step4。5算法应用 为了验证本文提出的算法的效果，选择两个典型的遗传算法性能测试函数，分别采用标准多种群遗传算法（SMGA）和本文提出的改进的多种群遗传算法（IMGA）进行测试，并比较它们的性能。考察的性能指标为搜索到满意解的概率、找到满意解的平均进化代数、平均收敛时间和满意解的平均值。5.1 测试函数 函数 1：Schaffer1 函数 1）（50sin*）（）,（21.02225.0222+=yxyxyxf 其中，55x，2020y。Schaffer1 函数的极值分布如图 1 所示，它是模式欺骗很大的一类线性不可分函数，在（

11、0，0）点达到极小值 0，周围存在无穷多个局部最小值，属于高难度函数寻优问题，采用简单遗传算法搜索到它的全局最优解将是一个小概率事件，设定其收敛条件为求得的满意解小于 0.0001。图 1 Schaffer1 函数的极值分布图 函数 2：Schaffer6 函数 3282222223）（001.01（5.0sin5.0）,（yxyxyxf+=其中，55x，2020y。Schaffer6 函数的极值分布如图 2 所示，它在（0，0）点达到极大值 1，周围存在无穷多个非常接近 1 的局部最大值，设定收敛条件为求得的满意解大于 0.9999。图 2 Schaffer6 函数的极值分布图 5.2 测试

12、结果 实验中，设有 5 个子种群，规模均为 30；=0.01、=0.17、=0.22；最大进化代数为 80，每种情况下的测试都重复 100 次，测试结果见表 1 和表 2。表 1 优化函数 1 时两种遗传算法的性能对比 算法 收敛 次数 平均进化代数平均收敛时间 平均收敛值SMGA 23 28.6 0.436s 0.00007 IMGA 100 10.5 0.118s 0.00000 表 2 优化函数 2 时两种遗传算法的性能对比 算法 收敛 次数 平均进化代数平均收敛时间 平均收敛值SMGA 72 30.4 0.464s 0.99995 IMGA 98 12.2 0.106s 1 由表 1

13、和表 2 可以看出：在测试条件相同的情况下，IMGA 的收敛率和满意解质量相对于 SMGA 有较大的提高，表明改进算法的全局搜索能力比较强，性能更加稳定。同时，IMGA 在收敛情况下的平均进化代数和平均收敛时间均明显的少于 SMGA，表明改进算法有很强的快速定位能力，能根据进化情况准确分析出优质目标所在范围。图 3 测试函数 1 时各子种群与精英种群的距离 图 3 给出了 IMGA 优化函数 1 时各子种群与精英种群的距离变化曲线（由于带有子种群剔除和条件结束操作的IMGA 进化代数太少，无法绘制相关曲线，所以在绘制该图时禁用了以上两种操作）。由图可知，由于协同进化的作用，改进的多种群遗传算法

14、在进化过程中会驱使各子种群向着同一个方向进化，降低了搜索的随机性，提高了收敛的速率。6 结论 考虑到在遗传算法应用中由于各决策变量取值范围的不同造成计算个体间距离时产生虚假距离现象，本文在传统的海明距离基础上给出了改进的个体间距离和种群距离的定义。基于多种群协同进化的思想，加强了种群间个体的交流过程以引进其它种群的优秀基因，在种群个数尽量少的情况下加速种群向着全局最优方向收敛。采用种群搜索区域自适应变化的策略逐步缩小搜索范围，提高了搜索效率和最优解精度，增强了种群的局部搜索能力。仿真实例优化结果表明，改进的遗传算法有很强的的寻优能力和较快的收敛速度。参考文献 1 W.Pan,H.Z.Diao

15、and Y.W.Jing,“An improved real numbers adaptive genetic algorithm,”Control and Decision,vol.21,no.7,pp.792795,2006.2 Y.M.Yuan,W.H.Fan and Y.T.Yang,“Genetic algorithm based on the diversification of growth strategy,”Control and Decision,vol.24,no.12,pp.1801-1804,2009.3 X.Liang,G.Zhao and M.Huang,“The

16、 application of a new parallel genetic algorithm,”Control and Instruments in Chemical Industry,vol.36,no.1,pp.31-34,2009.4 Tahera K.,R.N.Ibrahim,and P.B.Lochert,“Development of a self-adaptive genetic algorithm,”in Seventh International Conference on Intelligent Systems Design and Application,pp.883

17、-888,2007.5 D.W.Gong,X.Y.Sun,“Multi-population genetic algorithm with variational search areas,”Control Theory and Applications,vol.23,no.2,pp.256-260,2006.6 K.G.Srinivasa,K.R.Venugopal and L.M.Patnaik,“A self-adaptive migration model genetic algorithm for data mining applications,”Information Sciences,vol.177,no.20,pp.42954313,2007.7 B.Li,T.S.Lin,“An evaluation of coevolution in genetic algorithm,”computer science,vol.36,no.4,pp.3437,2009.329