第２７卷第１１期 计算机仿真 ２０１０年１１月
文章编号：１００６—９３４８（２０１０）１１—０２０４—０５
遗传参数协同进化的自适应遗传算法
李坤，李军华，杨小芹
（南昌航空大学无损检测教育部重点实验室，江西南昌３３００６３）
摘要：在智能计算技术中，为了提高收敛速度和缩短运行时间，提出了一种遗传参数协同进化的自适应遗传算法，解决遗传 算法优化复杂的多峰值函数时出现早熟的问题。在其中的选择运算中引入一种抗早熟机制，在交叉运算中动态调整交叉算 子，并在交叉率的调整中考虑海明距离的因素。在仿真实验中，用新算法对几个典型的多峰值函数进行优化，实验结果表明 算法可以有效的避免早熟问题，收敛性能明显优于基本遗传算法和自适应遗传算法，适用于信息处理和模式识别领域。 关键词：遗传算法；自适应；海明距离 中图分类号：ＴＰ１８ 文献标识码：Ａ
Ａｎ Ａｄａｐｔｉｖｅ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ
Ｐａｒａｍｅｔｅｒｓ Ｃｏｏｐｅｒａｔｅｄ ｗｉｔｈ Ｅｖｏｌｕｔｉｏｎ
ＬＩ Ｋｕｎ，ＬＩ Ｊｕｎ—ｈｕａ，ＹＡＮＧ Ｘｉａｏ—ｑｉｎ
（Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｎｏｎｄｅｓｔｒｕｃｔｉｖｅ ｔｅｓｔ ｏｆ Ｃｈｉｎｅｓｅ Ｅｄｕｃａｔｉｏｎ Ｍｉｎｉｓｔｒｙ，
Ｎａｎｃｈａｎｇ Ｈａｎｇｋｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｃｈａｎｇ Ｊｉａｎｇｘｉ ３３００６３，Ｃｈｉｎａ）
ＡＢＳＴＲＡＣＴ：Ａｎ Ｉｍｐｒｏｖｅｄ Ａｄａｐｔｉｖｅ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ Ｐａｒａｍｅｔｅｒｓ Ｃｏｏｐｅｒａｔｅｄ ｗｉｔｈ Ｅｖｏｌｕｔｉｏｎ（ＰＣＥＡＧＡ） ｉｓ ｉｎｔｒｏｄｕｃｅｄ ｆｏｒ ｓｏｌｖｉｎｇ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｐｒｅｍａｔｕｒｅ ｏｆ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ．Ｉｎ ｔｈｅ ａｌｇｏｒｉｔｈｍ，ａ ｒｅｓｉｓｔｉｎｇ ｐｒｅｍａｔｕｒｅ ｍｅｃｈａ．
ｎｉｓｍ ｉｓ ｉｎｔｒｏｄｕｃｅｄ ｉｎｔｏ ｓｅｌｅｃｔｉｏｎ ｏｐｅｒａｔｉｏｎ，ｃｒｏｓｓｏｖｅｒ ｏｐｅｒａｔｏｒ ｉｓ ｄｙｎａｍｉｃａｌｌｙ ａｄｊｕｓｔｅｄ ｉｎ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｃｒｏｓｓｏｖｅｒ ０ｐ—
ｅｒａｔｉｏｎ，ａｎｄ ｔｈｅ ｈａｍｍｉｎｇ ｄｉｓｔａｎｃｅ ｉｓ ｃｏｎｓｉｄｅｒｅｄ ａｓ ａｎ ｉｍｐｏｒｔａｎｔ ｆａｃｔｏｒ ｏｆ ｓｅｌｆ—ａｄａｐｔａｔｉｏｎ ｏｆ ｃｒｏｓｓｏｖｅｒ ｒａｔｉｏ．Ｉｎ ｔｈｅ
ｓｉｍｕｌａｔｉｏｎ ｅｘｐｅｒｉｍｅｎｔ，ｓｅｖｅｒａｌ ｍｕｈｉｐｌｅ ｐｅａｋｓ ｆｕｎｃｔｉｏｎｓ ａｒｅ ｏｐｔｉｍｉｚｅｄ ｂｙ ｔｈｅ ｎｅｗ ａｌｇｏｒｉｔｈｍ．Ｔｈｅ ｒｅｓｕｌｔｓ ｐｒｏｖｅ ｔｈａｔ ｔｈｅ
ａｌｇｏｒｉｔｈｍ ａｖｏｉｄｓ ｔｈｅ ｃｏｎｖｅｒｇｅｎｃｅ ｏｆ ｌｏｃａｌ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ ａｎｄ ｓｈｏｗｓ ｇｒｅａｔ ａｄｖａｎｔａｇｅｓ ｏｆ ｓｉｍｐｌｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ａｎｄ
ａｄａｐｔｉｖｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｉｎ ｃｏｎｖｅｒｇｅｎｃｅ．
ＫＥＹＷＯＲＤＳ：ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ；ａｄａｐｔｉｖｅ；Ｈａｍｍｉｎｇ ｄｉｓｔａｎｃｅ
１ 引言
遗传算法“ （Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍｓ，ＧＡ）是Ｊ．Ｈｏｌｌａｎｄ教授
于１９７５年受生物进化论的启发而提出的，它是基于进化过
程中的信息遗传机制和优胜劣汰的自然选择原则的全局优
化概率搜索算法。由于遗传算法的整体搜索策略和优化计 算时不依赖于梯度信息，所以，其应用范围非常广泛 Ｊ。它
在模式识别、信息处理、组合优化、机器学习、规划策略和人 工生命等领域的应用中展示出优越性和魅力，从而也确定了
它在智能计算技术中的关键地位。
基本遗传算法作为一种全局优化的概率搜索算法，存在
收敛速度慢、运行时间长，早熟等问题。自适应遗传算法
是由Ｍ．Ｓｒｉｎｉｖａ提出的，它在遗传算法的重要参数交叉率和
变异率的调整上引入了自适应机制。自适应遗传算法能够 比较有效的解决基本遗传算法收敛速度慢，运行时间长等问
题。但是，自适应遗传算法对解决早熟问题的收效不大，尤
其是对于类似ＳｅｈａｆｆｅｒＦ 的多峰值函数，结果并不理想 』。
此外，自适应遗传算法交叉概率的调整基础过于单一，并且
仅将适应度作为参数调整的准则，忽略了海明距离等其它有
用信息。在进化过程中只使用一种交叉算子，不对交叉算子
做任何自适应调整。这些情况都说明经典自适应遗传算法
仍有进一步改进的空间和必要。
本文针对自适应遗传算法存在的问题，提出了一种改进
思路。在交叉率自适应调整的过程中综合考虑个体的海明
距离和适应度的作用，并且建立交叉算子库，为每一次交叉
运算匹配不同的交叉算子，进一步增加交叉运算结果的多样
性，并对选择和变异运算做了相应改进。
基金项目：基金项目：国家自然科学基金资助项目（６０９６３００２）；航空 科学基金项目（２ｏｏ８ｚＤ５６０Ｏ３） ２ 遗传参数协同进化的自适应遗传算法
收稿日期：２００９—０８—０４修回日期：２００９—１０—１２ ２．１算法改进的思路
－－－——２０４－．—
—— 本文提出了一种遗传参数协同进化的改进遗传算法。
为了解决自适应遗传算法中存在的问题，本文提出的算法从
以下三个方面做出了改进。
１）多样化交叉概率的调整基础，在个体编码串中添加
附加码，其中记录为个体匹配的交叉率，并作为交叉率自适
应调整的基础。 ２）改进交叉率自适应调整的规则，增加海明距离作为
调整规则的一部分，与适应度函数值一起作用于交叉率调
整。 ３）在选择运算中引入抗早熟机制，适当的降低选择压
力，避免进化初期出现超级个体，进一一步降低算法早熟的概
率。 ２．２选择运算
选择运算采用轮盘赌的策略，结合最优个体保留策略。
其中保留的最优个体的个数为２个，其他个体则通过模拟轮
盘赌的方式选出进入下一步的选择运算。本文在选择运算
的过程中引入了一种抗早熟机制，即个体被选中的概率不等
于其适应度大小，而是与适应度大小之间有一定的函数关
系。个体被选中的概率与个体适应度的关系如式（１）
Ｐ ＝（Ｆｉｔｎｅｓｓ ） （１）
Ｐ Ｐ ＝ 一 （２） ∑Ｐ
其中，０＜ｄ≤１为常数，式（１）所提供的概率要经过归
一化之后才能用于轮盘赌选择。归一化的方法如式（２）所
示，其中，１１３为群体规模。当个体的适应度函数值大于１时，根
据式（１）得到的概率会大于个体本身的适应度，并且参数ｄ
越小，这种效果越明显。在这里简单的证明一下，这种方法有
效的增加了适应度函数值较小的个体被选中的概率，可以防
止算法过早的收敛于局部最优解。
假设当前群体中适应度最大值为，某个体的适应度函数
值为＿厂ｍ ，并且有 。那么 《 …，在选择运算当中，它们被选
中的概率分别是：
Ｐ ：｝ ：
∑ ∑
于是，￣１．２ｍ ｐ￣一： 表示适应度较小的个体在模拟
轮盘赌中被选中的概率。
同理，对于式（１）和式（２）中描述的方法，也可以计算出
适应度较小的个体和适应度最大的个体在轮盘赌中被选中
的概率分别是：
Ｐ ： ，Ｐ ：单
∑（ ）。 ∑（ ）
得到适应度较小个体在轮盘赌中被选中的概率应该为
≥ （ ） ０满足条 ，。 ≤ ，所以，根据中学 数学的相关知识可知． ＜ｆ皇 ，得出结论旦＜ 。 ￣，
ｍ ＼‘，…，Ｐ…Ｐ… 因此，使用式（１）和式（２）所表示的方法，计算得出的结
果，可以有效的提高适应度较小的个体在模拟轮盘赌中被选
中的概率，同时降低了适应度高的个体被选中的概率。在本 文的实验中根据实际情况为不同的测试函数选择了不同的
值。
２．３交叉运算
交叉运算在被选择出来的个体当中，随机选取两个体，
将个体附加码中的交叉率读出后，作为交叉率自适应调整的
基础。然后在对个体问的海明距离取常用对数，并将结果直
接加到调整基础上得到这次交叉运算的交叉率。
，』、 Ｐ ＝Ｐ ＋ｌｇ《÷ｌ （３） 、Ｕ， 式（３）是交叉运算中对于交叉率的自适位调整。在式
（３）中，Ｐ ——调整交叉率的基础，本身与个体的适应度有
关，具体关系见表１；ｄ——参与交叉运算的两个体之问的海
明距离； ——人为设定的海明距离闽值，这个阈值根据多
次试验得到的经验，取值在个体编码串长度的三分之－－－效果
比较好；改进算法通过对个体参考交叉率的初始化和表１中
方式，基本达到了经典自适应遗传算法对交叉率凋整的目
的，同时改进算法在交叉算子的选用 ，选择不Ｉｉｊ】的交叉算
子增加了运算结果的多样性。
在选用交叉算子的问题上，将不同的ｊ种交叉算子——
多点交叉算子，均匀交叉算子和算数交义算子制成算 库，
并且根据参与运算的两个体的适应度 平均适应度的关系
选择不同的交叉算子的具体规则见表１。
表１交叉算子选用规则表
表１中为 ——适应度较大的个体 ．．．．——适应度较
小的个体；ｐ…——较大的参考交叉率； ——较小的参考
交叉率； ——两个体的平均参考交叉率； ２．４变异运算 变异运算中变异率取Ｐ ：０．１，使用高斯变异算子 由
于使用了最优个体保留策略，所以在变异运算中，可以尽可
能的加大在当前最优个体附近进行搜索的概率以求得更优
的解，而不用担心会破坏已经存在的优良模式 因此，本文
将当前最优个体的变异概率置为１，加大在最优个体周围进
行搜索的概率。因为已经最优个体被存储起来，昕以即使变
异结果不理想也不用担心会破坏其中的优良模式。
２．５算法的基本步骤
１）令进化代数计数器ｇｅｎ＝０，随机产生初始群体；
——２０５．．．
——