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

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

《改进的多种群遗传算法及其应用资料下载.pdf》由会员分享，可在线阅读，更多相关《改进的多种群遗传算法及其应用资料下载.pdf（4页珍藏版）》请在冰点文库上搜索。

Min（）Xf，ba，X，其中，（）nxxxX,21=，（）naaa,a21=，（）nbbb,b21=，iiibax,，ni,2,1?

=。

2010InternationalConferenceonCircuitandSignalProcessing978-1-4244-6782-2/10/$26.002010IEEE3262.1个体间距离的改进及其优越性证明传统的海明距离定义如下：

（）=nkjkikjiijxxxxd12

（1）其中，Nji,2,1,=且ji。

但是当各决策变量的取值范围不一样时，海明距离应用起来有一定的局限性，会产生虚假距离现象。

也就是说当各变量的可行域不同时，取值范围大的变量在海明距离的计算中起主导作用，尤其差异很大时，此现象更为明显。

为了解决这一问题，我们定义两个单独个体ix与jx之间的归一化海明距离为个体间距离。

nxxDnkkjkikij=12

（2）其中，Nji,2,1,=且ji，kkkab=。

与海明距离的定义相比，改进的个体间距离考虑了由于变量取值范围差异导致的假距离现象，使个体间距离与各变量的取值范围无关，较之海明距离更为合理；

并且距离的取值在0到1之间变化，易于操作。

为了说明此改进方案的优越性，下面举例给出统计验证。

证明：

假设种群中每个个体包含3个基因，第i个个体为,321iiixxx，并且101ix，即11=；

1002ix，即102=；

10003ix，即1003=。

在规定区域内随机产生200个个体，并随机配成100对，则第i对个体对应基因的绝对距离为：

1,021111=iiixx；

10,022122=iiixx；

100,023133=iiixx；

其中，11ix和21ix分别是第i对个体的一对对应基因。

由公式

（1）计算100对个体的海明距离为：

10021ddd；

由公式

（2）计算100对个体的的改进距离为：

10021DDD。

由数理统计知识可知第k个基因与海明距离的相关度计算公式如下：

=10011001221001）（*）（）（*）（iiikikiikikkddddroo其中，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。

从相关度分析可以看出，随着基因所属范围不断变大，基因与海明距离的相关度也不断增加，而基因与改进个体距离的相关度却基本保持平衡，有效避免了虚假距离现象，保证了公平与准确性。

证毕2.2种群间距离的改进种群距离：

两个子种群中心之间的归一化海明距离。

nxxDnkkejkeikeij=12（3）其中，Mji,2,1,=且ji，NxxNpipkeik=1为第i个子种群的第k个变量的中心。

同理，改进的种群距离也与各变量取值范围的差异无关，并且取值在0到1之间变化。

种群分散度：

所有个体的分散程度的归一化表示。

2MMijeijdispCDD=（4）其中，Mji,2,1,=且ji。

3自适应调整搜索范围为保持各子种群的相对独立，各子种群间不直接发生交叉关系，而是通过精英种群间接地引进其它子种群的优秀基因。

在交叉时偶尔从精英种群中引进一个优质个体，以改善种群质量。

精英种群集中了群落中最优秀的个体，还享有在整个可行域内活动的特权，这样就可以通过协同进化把全局最优基因输送到各个可行域不断缩小的子种327群，提高找到全局最优解的概率。

合理地减小搜索区域的范围可以降低搜索的盲目性、提高精度，但是基于进化代数直接强制收缩搜索区域的方案会导致可能错过最优解。

我们根据种群进化的进程、种群的主要活动范围，来确定并逐步地缩小搜索区域，以提高算法的收敛效率。

并以个体间距离、种群间距离和种群分散度作为搜索区域变化的判断依据和决策量。

在执行某一子种群的缩减搜索区域这一操作时，首先用

（2）式计算精英种群个体之间的距离ijD，Mji,2,1,=且ji，然后求其最大值，令maxD=MaxijD。

然后用（3）式计算该子种群与精英种群之间的距离eliteD，若eliteD（01），则保留该子种群的最优个体，并取消该子种群的存在。

若dispD且maxD（和是预先设定的0到1之间的值），则执行收缩搜索区域的操作。

为了最终决定搜索区域变化的程度，我们引入收缩因子，由（5）式求得。

=4.024.026.026.0maxmaxmaxdispelitedispelitedispeliteDDDothersDDDDDD（5）然后按照（6）式计算该子种群的下一代搜索区域范围。

+=）（）（111111ttttttttabcbabcaoo（6）其中，o1tc是该子种群最优个体的位置。

为了避免新的搜索区域超出前代，采用（7）式和（8）式进行调整。

其它11,=tttttbbbbb（8）依照以上所述方法对所有子种群的搜索区域逐个进行自适应变化。

4算法步骤Step1：

初始化子种群个数M、子种群规模N、搜索范围a，b、以及终止迭代次数T等参数。

Step2：

在可行域内随机生成M个子种群和一个精英种群，每个子种群包含N个个体，采用浮点数对个体进行编码。

Step3：

计算个体的目标函数值，对各子种群中个体的适应度进行比较并排序，从每个子种群中选取较优的N/M个个体输送到精英种群中。

Step4：

判断终止条件是否满足。

如满足，则结束进化；

否则，继续。

Step5：

按顺序选定一个子种群，判断该子种群是否还有存在价值，若无，则剔除，M=M-1，返回Step5。

判断该子种群的搜索区域变化条件是否满足。

如满足，则依据（5）-（8）式自适应变化；

Step6：

采取带有最优保留策略的比例选择操作完成该子种群父代个体的选择，对父代子种群用协同进化的方法执行交叉和变异操作，得到新一代子种群。

Step7：

判断是否所有子种群都操作结束。

否则，转至Step5。

Step8：

从M个新一代子种群中各选取N/M-4个最优个体作为精英种群成员，替换精英组织中的劣解，完成对精英种群的更新操作，然后返回Step4。

5算法应用为了验证本文提出的算法的效果，选择两个典型的遗传算法性能测试函数，分别采用标准多种群遗传算法（SMGA）和本文提出的改进的多种群遗传算法（IMGA）进行测试，并比较它们的性能。

考察的性能指标为搜索到满意解的概率、找到满意解的平均进化代数、平均收敛时间和满意解的平均值。

5.1测试函数函数1：

Schaffer1函数1）（50sin*）（）,（21.02225.0222+=yxyxyxf其中，55x，2020y。

Schaffer1函数的极值分布如图1所示，它是模式欺骗很大的一类线性不可分函数，在（0，0）点达到极小值0，周围存在无穷多个局部最小值，属于高难度函数寻优问题，采用简单遗传算法搜索到它的全局最优解将是一个小概率事件，设定其收敛条件为求得的满意解小于0.0001。

图1Schaffer1函数的极值分布图函数2：

Schaffer6函数3282222223）（001.01（5.0sin5.0）,（yxyxyxf+=其中，55x，2020y。

Schaffer6函数的极值分布如图2所示，它在（0，0）点达到极大值1，周围存在无穷多个非常接近1的局部最大值，设定收敛条件为求得的满意解大于0.9999。

图2Schaffer6函数的极值分布图5.2测试结果实验中，设有5个子种群，规模均为30；

=0.01、=0.17、=0.22；

最大进化代数为80，每种情况下的测试都重复100次，测试结果见表1和表2。

表1优化函数1时两种遗传算法的性能对比算法收敛次数平均进化代数平均收敛时间平均收敛值SMGA2328.60.436s0.00007IMGA10010.50.118s0.00000表2优化函数2时两种遗传算法的性能对比算法收敛次数平均进化代数平均收敛时间平均收敛值SMGA7230.40.464s0.99995IMGA9812.20.106s1由表1和表2可以看出：

在测试条件相同的情况下，IMGA的收敛率和满意解质量相对于SMGA有较大的提高，表明改进算法的全局搜索能力比较强，性能更加稳定。

同时，IMGA在收敛情况下的平均进化代数和平均收敛时间均明显的少于SMGA，表明改进算法有很强的快速定位能力，能根据进化情况准确分析出优质目标所在范围。

图3测试函数1时各子种群与精英种群的距离图3给出了IMGA优化函数1时各子种群与精英种群的距离变化曲线（由于带有子种群剔除和条件结束操作的IMGA进化代数太少，无法绘制相关曲线，所以在绘制该图时禁用了以上两种操作）。

由图可知，由于协同进化的作用，改进的多种群遗传算法在进化过程中会驱使各子种群向着同一个方向进化，降低了搜索的随机性，提高了收敛的速率。

6结论考虑到在遗传算法应用中由于各决策变量取值范围的不同造成计算个体间距离时产生虚假距离现象，本文在传统的海明距离基础上给出了改进的个体间距离和种群距离的定义。

基于多种群协同进化的思想，加强了种群间个体的交流过程以引进其它种群的优秀基因，在种群个数尽量少的情况下加速种群向着全局最优方向收敛。

采用种群搜索区域自适应变化的策略逐步缩小搜索范围，提高了搜索效率和最优解精度，增强了种群的局部搜索能力。

仿真实例优化结果表明，改进的遗传算法有很强的的寻优能力和较快的收敛速度。

参考文献1W.Pan,H.Z.DiaoandY.W.Jing,“Animprovedrealnumbersadaptivegeneticalgorithm,”ControlandDecision,vol.21,no.7,pp.792795,2006.2Y.M.Yuan,W.H.FanandY.T.Yang,“Geneticalgorithmbasedonthediversificationofgrowthstrategy,”ControlandDecision,vol.24,no.12,pp.1801-1804,2009.3X.Liang,G.ZhaoandM.Huang,“Theapplicationofanewparallelgeneticalgorithm,”ControlandInstrumentsinChemicalIndustry,vol.36,no.1,pp.31-34,2009.4TaheraK.,R.N.Ibrahim,andP.B.Lochert,“Developmentofaself-adaptivegeneticalgorithm,”inSeventhInternationalConferenceonIntelligentSystemsDesignandApplication,pp.883-888,2007.5D.W.Gong,X.Y.Sun,“Multi-populationgeneticalgorithmwithvariationalsearchareas,”ControlTheoryandApplications,vol.23,no.2,pp.256-260,2006.6K.G.Srinivasa,K.R.VenugopalandL.M.Patnaik,“Aself-adaptivemigrationmodelgeneticalgorithmfordataminingapplications,”InformationSciences,vol.177,no.20,pp.42954313,2007.7B.Li,T.S.Lin,“Anevaluationofcoevolutioningeneticalgorithm,”computerscience,vol.36,no.4,pp.3437,2009.329