快速遗传算法研究吴斌吴坚涂序彦【摘要】 提出了一种称为广义自适应遗传算法的快速遗传算法，它首先产生均匀分布的初始种群，其次根据种群模式的状况决定是否引入“高品质”移民， 最后自适应地进行交换和变异运算其搜索性和全局收敛性比现有的许多遗传算 法都有明显的改善，并通过仿真说明了该改进遗传算法的有效性关键词 广义自适应；遗传算法；初始种群；移民；适应度函数中图分类号TP301.6Research of Fast Genetic AlgorithmWu Bin Wu Jian(Dept. of Information and Control Engineering , SWIT Mianyang 621002)Tu Xuyan(Information Engineering School, UST Beijing Beijing 100083)Abstract A fast genetic algorithm GSAGA(generalized self-adaptivegenetic algorithm) is presented in this paper. First, evenly distributed initial population is generated. Then, high quality immigrants are introduced according to the condition of the population schema. Finally, crossover and mutation are operated on self-adaptively. In GSAGA, the searching performance and global convergence are greatly improved compared with many existing genetic algorithms. Through emulation, the validity of this modified genetic algorithm is proved.Key words generalized self-adaptive; genetic algorithm; initial population; immigration; fitness function在遗传算法中，算法的收敛性主要通过复制实现，而搜索性主要通过交换和 变异实现。
由于复制和交换的作用，适应度高于种群平均适应度的优良个体得到 保留，并且其数量随着进化而不断增加，最后成为种群中的超级个体，产生封闭 竞争，即出现“近亲繁殖”，减慢甚至导致进化地停滞，过早地收敛于局部极值 解;而变异操作可以增加新的搜索空间，扩大搜索范围，以利于找到全局最优解， 但增加变异会影响收敛的速度现有的各种改进遗传算法有助于解决算法搜索性 与收敛性间的矛盾，但许多算法只有在迭代步数很多时才有可能搜索到全局极值 点附近，给算法的实际应用造成了困难为此，本文提出了一种快速遗传算法—— 广义自适应遗传算法(GSAGA)1广义自适应遗传算法的原理1・1初始种群的产生在许多改进的遗传算法中，初始种群的产生依然采用完全的随机方式，而没 有解决初始种群中各个体在解空间中的分布情况这有可能让许多个体都集中在 某一局部区域内，不利于扩大搜索空间和收敛到全局最优解广义自适应遗传算 法首先在初始种群的产生上要求各个体之间保持一定的距离，使各个体尽可能均 匀地分布在整个解空间上定义相同长度的以a为基的两个字符串中对应位不相同的数量称为两者间 的广义海明距离，记为GH设个体是以为基的字符串，个体的长度为k，种群的规模大小为N，则要求 入选种群的所有个体之间的广义海明距离GH必须满足GH© j式中i、j为两个个体一” L 绍；b为一常数，视不同的编码形式而定。
一般若为二进制编码，则b=int(k/2)；若为十进制编码，则可取八心种群的大小N影响着算法的有效性，当N太小时，算法会很差或找不出问题 的解；而N太大时，则会使收敛时间增长，因此设定N=3K(K>4)对于一个以a为基，长度为k的字符串，共有ak个编码串在这ak个编码 串中，相互间广义海明距离大于或等于(k-b)的字符串编码总共有ak-(k-b)+i个所 以在广义自适应遗传算法中，种群的大小N=3k远小于ak-(k-b)+i，即要求初始种群 中所有个体间的广义海明距离大于或等于(k-b )是完全能满足要求的设两个长度为l的字符串个体间的广义海明距离是GH，则这两个字符串中 所包含的相同模式的数量为2i-gh，而长度为l的字符串个体所含的模式数为21， 故这两个字符串中所包含的不相同模式的数量就是(2'-2i-gh)广义海明距离GH 越大，字符串间所包含的不相同模式的数量就越多，种群中的模式也越多初始种群采取这种方式产生就能保证随机产生的各个体间有较明显的差别， 使它们能比较均匀地分布在解空间上，保证初始种群含有较丰富的模式，从而增 加搜索收敛于全局最优解的可 能1.2适应度函数f在遗传算法中，适应度函数用来评价各个解的优劣。
适应度计算的简单或复 杂，取决于问题本身对有些问题，只需要一个数学解析公式计算出来；有些问 题本生不存在这样的解析式，需通过一系列基于规则的步骤才能求得；还有些问 题的计算，是上述两种方法的结合在广义自适应遗传算法中，我们采用解析公式计算适应度设实际问题的目 标函数为J(x)，适应度函数为f(x)，则有1.3复制算子为了保证搜索到的最优个体不会因为选择、变异、交换算子的操作而被破坏, 我们将父代种群中适应度最大的0.1N个（10%）优良个体直接传递到子代种群中, 成为子代种群中的个体对父代种群中剩下的0.9N个（90%）个体，按各自的适应 度进行从小到大排序设各个体相应的排序序号为 皿…山川，则每个个 体按如下的数量复制到匹配池中1.4 “高品质”移民在广义自适应遗传算法中，为了避免出现超级个体，防止发生封闭竞争，将 根据匹配池中各个体间的差异来决定是否引入移民和移民的数量，并且要求被引 入的移民具有较高的“品质”，即移民个体的适应度应该大于或等于当前匹配池 中个体的平均适应度当匹配池中各个体间的广义海明距离小于一特定值上时, 就不断地引入“高品质”移民随机地替代匹配池中的某些个体，直到匹配池中个 体间的广义海明距离大于或等于止为止。
其中上为一常数，一般取为0.011.5自适应交换算子交换是对被选择到匹配池中的0.9N个个体进行的对于随机选择的交换匹 配对的两个个体来说，当两者之间的广义海明距离很小时（即两者非常相似）， 交换的作用变得不明显，因此应减少交换操作，甚至不进行交换操作，亦即交换 的概率pc应较小或为零；而当两者间的距离较大时，交换后产生新个体的机会 也较大，有助于提高搜索效率，因而应有较大的交换概率pc在广义自适应遗传算法中，交换概率Pc具有如下形式式中i，j分别为匹配对中的两个个体；GH•为它们间的广义海明距离；「站为匹配池中所有个体间的平均广义海明距离；a为一个常数，取值范围为0.2〜0.8这样确定的交换概率Pc将依据匹配对个体间的情况而变化，距离大的交换 可能性大；反之，交换的可能性就小1.6自适应变异算子变异算子保证算法能搜索到问题解空间的每一点，使算法具有全局收敛性当种群的平均广义海明距离很小时，说明种群中的各个体基本上趋于一致, 种群的基因模式单一性增强，因而可能导致进化停滞，过早地收敛于局部的极值 解，为此必须通过变异操作来改变这种情况在交换操作前，用广义海明距离来评价要交换的双亲个体的差异，根据这个 差异，以及当前匹配池中个体间的平均广义海明距离和适应度的情况来确定交换 后的后代变异概率P。
在广义自适应遗传算法中，经交换后的各个体按如下变异概率p进行变异操作 m（爲-了丽、-甌 + 0M1式中"分别为匹配池中交换前所有个体的最大适应度、平均 适应度和平均广义海明距离和配对个体间的广义海明距离；用为常数，一般取 为0.005 和"体现了群体的收敛程度，当它们较小时，说明群体已趋向收敛，P应加大匹配池中的0.9N个个体经移民、交换、变异操作后进入新一代种群1.7停止条件在广义自适应遗传算法中，算法停止条件为M代内最优适应度值无显著提高M太大则收敛时间太长，而太小则所求得的最优结果与实际最优解相差太大我M二理们根据种群规模N来确定，取 上2广义自适应遗传算法仿真文献［3］比较了几种遗传算法，我们也用其中的函数来检验广义自适应遗传 算法，并与它的结果进行了比较2.1实际问题待优化函数为7 = 100-^^式中x(i=l,2,3)的取值范围均为：工七丨求函数的最大值函数 i的最大值在(0,0,0)处取得，为1002.2算法实现每个变量用8位十进制数表示，把三个变量的十进制码串接构成一个个体, 于是编码长度K=24，种群大小N=3K=72,结束迭代次数 工适应度函数定义为式中i代表种群中第i个个体；J和J分别为种群中最小和最大的目标函数‘ min max值。
算法流程图如图1所示，程序用VB编写2.3结果分析为消除随机性带来的干扰，算法重复执行了 30次，将仿真实验数据取平均 值记录于表1中从表1可以看出，当指定的目标函数值小于99.99时，广义自 适应遗传算法能迅速地收敛到指定极值点，并且在实验中发现如果没有移民，则 对于搜索大于或等于99.99的目标函数值将要进化很多代才能搜索到，甚至有时 在指定的进化代数内搜索不到指定的极值与文献［3］的结果相比较，广义自适应遗传算法不仅收敛速度快，而且能够 搜索到更优越的解，其搜索性和收敛性比许多遗传算法都有很大的改善图1广义自适应遗传算法实现流程图表1不同遗传算法达到指定函数值的进化代数目标函灵敏值9999.599.999.9599.9999.99599.99999.999 5简单遗传算法383045185———均匀交换遗传算法385490157———引入普通移民的算法474078179———文献［3］的遗传算法372658134163——广义自适应遗传算法2.634.478.411.6338.8346.151.2752.87注：“一”表示在进化200代后该算法的最大目标函数值仍不能达到指定值3结论从上面的分析和仿真实验结果可以看出，由于广义自适应遗传算法首先通过 产生能适应问题解空间分布状况的初始种群，保证了初始种群中个体模式的合理 分布；其次是通过保护优秀个体直接进入下一代种群，避免了交换、变异操作破 坏优良个体，同时，有条件地引入“高品质”移民，有效地解决了种群中个体的 多样性；最后，对匹配池中的个体用自适应的方式确定各个体的交换概率P和C 变异概率P,从而较好地解决了算法收敛性和搜索性之间的协调问题。
在广义自 适应遗传算法的整个过程中，无论是初始种群的产生，还是外来移民的引入，以 及交换和变异概率的确定都是根据种群中各个体的具体情况而定的，并且自适应 地随着进化而不断地改变所有这一切使得广义自适应遗传算法具有良好的搜索 性和收敛性，其性能明显优于现存的许多遗传算法四川省应用基础研究基金资助项目作者简介：吴斌男，33岁，博士生，讲师作者单位：吴斌吴坚（西南工学院信息与控制工程系绵阳621002） 涂序彦 （北京科技大学信息工程学院北京100083）参考文献1 Holland John H. Adaptation in natural and artificial systems.Michigan:The University of Michigan Press,19752 Goldberg , David E. Genetic algorithms on search, optimization and machine learning. New York:Addisen—Wesley, 19893蔡弘，李衍达，一种快速收敛的遗传算法，智能控制与智能自动化.第二 届全球华人智能控制与智能自动化大会论文集.西安：西安交通大学出版社， 1997:1 689〜1 692。