遗传算法的3种改进方法和分析

1、遗传算法的3种改进方法和分析郭凯【摘要】摘要：遗传算法是一种借鉴生物界自然选择和进化机制的随机优化算 法。它在求解一般全局优化问题时具有较好的鲁棒性，而且搜索不依赖梯度信 息、。但是，在用传统遗传算法解决较复杂的优化问题时，存在早熟及稳定性差 的缺点。因而，针对这些缺点，出现了很多对传统遗传算法的改进。本文对遗 传算法的3种改进方法进行了描述，并将它们应用到一个函数优化实例中。最 后，通过比较3种改进方法与传统遗传算法优化所得结果，得出3种改进方法 交攵果更好。【期刊名称】电子测试 【年(卷)，期】2011(000)003 【总页数】3 【关键词】遗传算法；拟随机序列；变异概率；双种群遗传算法

2、0引言遗传算法(Genetic algorithm,GA)是一种借鉴生物界自然选择和进化机制发展 起来的高度并行、随机、自适应的全局优化概率搜索算法1。它模拟了自然选 择和遗传中发生的复制、交叉和变异等现象2。先产生初始种群，通过选择、 交叉和变异操作，产生一群更适合环境的个体，经过一代一代的进化，使种群 最后收敛到一群最适合环境的个体，求得问题的最优解。由于GA具有简单、 通用、鲁棒性强和适应于并行分布处理等特点，已经成功应用到很多领域3。虽 然遗传算法有许多的优点，但是在处理复杂的非线性问题时，容易出现个体的 早熟现象，使算法不能跳出局部极值，难以找到最优解。针对遗传算法的早熟现象，很多学

3、者提出了改进方案。改进方法主要在3个方 面，即改进遗传操作、调整参数和采用多种群遗传算法。本文具体的分析了 3种 改进遗传算法，并通过一个实例来探索它们在实际问题中的应用。13种改进遗传算法1.1利用拟随机Halton序列产生初始种群遗传算法中选择初始种群的目的就是为了尽可能地获取更多有关目标函数的信 息4，这在算法操作中非常重要，经常对算法的最终优化结果有一定的影响。 一般在种群初始化时，我们用产生伪随机数的方法随机地生成分布不均匀的初 始种群，但是，初始种群中的个体均匀分布比随机生成个体可以获得更多的目 标函数信息，在算法搜索中更有优势。使用拟随机序列可以产生具有低差异度的个体，它以牺牲随

4、机性为代价，换取 均匀性的提高。目前已提出的拟随机序列主要有Van der Vorput序列、Faure 序列、Sobol 序列、Halton 序列及 Niederreiter 的(t,s)序列5。Halton 序歹U6是一个标准的低差异度序列。与其它低差异序列相比，Halton序列执行起 来要简单得多，因为它对每一维上利用基本的逆函数，而用逆函数产生小数比 较容易实现7。本文利用拟随机序列Halton序列产生初始种群。1.2自适应变异概率遗传算法的参数中变异概率Pm的选择对遗传算法行为和性能有较大影响。传 统的遗传算法对个体随机地进行变异操作，当变异概率过大时，容易使种群中适应 度好的优秀个

5、体遭到破坏，从而使算法陷入一种单纯的随机搜索当中，而变异率过 低又难以引入新的基因8。而且对于不同的优化问题，如果经过反复实验来确 定Pm的值，比较繁琐。为了有效地保留种群中的优良个体模式，又保证有效地 产生一些较好的新个体模式，对传统遗传算法中的变异概率进行改进是有必要 的。本文采用自适应变异概率。对于高于群体平均适应度的个体，采用较低的Pm， 而对于低于群体平均适应度的个体，采用较高的Pm。使用公式（1）。其中：Pm1=0.1, Pm2=0.001,fmax为群体中最大的适应度值；favg为每代群 体的平均适应度值；f为要变异个体的适应度值。1.3双种群遗传算法本文采用的双种群遗传算法，其

6、思路为：先产生一个种群，然后将其分为相同 大小的两个子种群，两个子种群采用一样的选择策略、交叉算子和变异算子， 分别进化一定代以后，将两个子种群的最优个体进行交叉，再与各种群剩余的 个体合并，在合并时，使两个子种群的原有最优个体代替适应度最低的个体而 保留下来。最后，新种群再进行遗传算法操作。通过这种操作，在逐渐单一的种群中注入了新的个体，而且这些新注入的个体 是已经经过一定进化选择得到的优秀个体交叉产生的，从而使新的种群更有效 地向最优解收敛。2计算机仿真和结果分析为了考察本文所述的3种改进遗传算法的性能，选取了一个实例进行数值模拟。所选实例为：该函数是一个一元多峰函数，在-1,2上存在多个

7、极大值点，它在该范围内的图 形如图1所示。我们把3种改进遗传算法和传统遗传算法，各自运行10次，每次运行得到的 函数值及其对应的变量值被记录下来，如表1所示。由表1可以看出：3种改进遗传算法都比传统的遗传算法能较好的接近最优解 x=1.8505,f（x）=3.8503。采用实值的方法结果较一般，主要是在一元函数中， 实值的单点交叉不起作用，种群进化时主要依赖生成的初始种群和变异操作。3结论总的来说，改进方法对比传统方法，在精确性上都有所提高。另外，3种改进 也可以做进一步改善，通过对halton序列进行合理加扰可以得到分布更加均匀 的初始种群；对于有的非线性方程组求解问题，可以尝试寻找能取得更

8、高精度 的变异概率；也可以扩展种群到更多，以提高种群的多样性。多数时候，还可 以将几种改进的方法有效地结合起来处理更复杂的优化问题。参考文献HOLLAND J H.Adaption in natural and artificial systemsM.Mass:MIT Press,1992:1.雷英杰，张善文.MATLAB遗传算法工具箱及应用M.西安：西安电子科技 大学出版社，2005.张顶学，关治洪，刘新芝.基于捕食搜索策略的遗传算法研究J.计算机应用 研究，2008,25（4）: 1006.H.MAARANEN,K. M I E T T I N E N,M. M.MAKELA.Quasi-Random Initial Population for Genetic Algorithms J.Computers & Mathematics with Application，2004（ 47）:1887.黄美发，景晖，钟艳茹等，基于拟随机序列的三维模型表面采样方法J.计 算机工程，2008，34（14）:264.J.Halton.On the efficiency of certain quasirandom sequences of points in evaluating multidimensional integralsJ.NumersicheMathematik