三种遗传算法改进方法与研究.doc

三种遗传算法的改进方法与研究 　　摘 要：遗传算法是一种基于自然选择和生物进化机制的智能优化算法，由于它具有非常多的优点，所以被广泛应用于各个领域。但是基本的遗传算法（简称GA）也存在着许多的缺点和不足：适用范围没有非常广；遗传算法很容易出现“早熟”收敛，搜索性能不高；遗传算法的时间复杂度往往比较高，而搜索的效率却比较低。本文针对基本遗传算法的陷入局部最优和早熟收敛的缺点，对基本遗传算法提出了三种改进方法：既顺序选择遗传算法、大变异遗传算法和双切点交叉遗传算法，并通过仿真实验验证了这些改进。 　　关键词：遗传算法；局部最优；早熟收敛 　　中图分类号：TP18 　　遗传算法（Genetic Algorithm，GA）起源于对生物系统所进行的计算机模拟研究，是模拟生物界“物竟天择、适者生存”的进化规律而开发出来的一种随机化搜索方法。它是由美国的J.Holland教授在1975年首先提出的，其特点是几乎不需要所求问题的任何信息，仅需目标函数的信息，而且不受搜索空间是否连续或可微的限制就可找到最优解，且具有良好的隐并行性和全局搜索能力[1-2]。遗传算法通过模拟自然选择的繁殖、交叉和变异操作来寻找更具优良品质的个体，用适应度函数来评价个体的优劣性，遵循优胜劣汰的原则，找到适应度最高的个体，并且在搜索中不断增加优良个体的数目，使种群的数目不断增加，相应的种群的整体适应度也在不断提高，循环往复，直到我们找到具有最高适应值的那个个体。由于遗传算法的优良性质而被广泛应用于函数优化、组合优化、机器学习、数据挖掘、图像处理和人工智能等很多领域。但是在处理一些非线性、多模型和多目标的函数优化问题时，基本的遗传算法局部搜索能力弱且容易出现早熟的现象，最后求出的解往往是局部最优解而不是全局最优解[3-5]。 　　本文针对基本遗传算法陷入局部最优和早熟收敛的缺点，提出了三种遗传算法的改进，并具体分析了改进的遗传算法，通过仿真实验验证了这些改进。 　　1 三种改进的遗传算法 　　1.1 顺序选择遗传算法（SBOGA） 　　基本遗传算法中个体的选择概率与个体的适应值直接相关，其计算公式为 （1） 　　一旦某个个体的适应值为0，则其选择概率为0，这个个体就不能产生后代，这是基本遗传算法的一个很大的缺点。顺序选择策略将选择概率固定化，其具体步骤为： 　　（1）按适应值大小对个体进行排序； 　　（2）定义最好的个体的选择概率q，则排序后的第j个个体的选择概率为： 　　（2） 　　这样每个个体都有可能被选中从而产生后代。 　　算法步骤如图1所示： 　　图1 顺序选择遗传算法流程图 　　1.2 大变异遗传算法（GMGA） 　　理论上，遗传算法中的变异操作可以使算法避免“早熟”。但是，为了保证算法的稳定性，变异操作的变异概率通常取值很小，所以算法一旦出现“早熟”，单靠传统的变异操作需要很多代才能变异出一个不同于其他个体的新个体。大变异操作的思路是：当某代中所有个体集中在一起时，我们以一个远大于通常的变异概率执行一次变异操作，具有大变异概率的变异操作（即“大变异操作”）能够随机、独立地产生许多新个体，从而使整个种群脱离“早熟”。 　　算法步骤如图2所示： 　　图2 大变异遗传算法流程图 　　1.3 双切点交叉遗传算法（DblGEGA） 　　单点交叉遗传使得父代双方交换基因量较大，有时候很容易破坏优秀个体，而双切点交叉相对单点交叉来说，父代双方交换的基因量较小，有利于个体的保留。 　　例如对于下面的两个个体，如果双切点交叉的方法，切点1在第2位，切点2在第5位。 　　切点1 切点2 　　10 110 011 　　01 011 101 　　则通过交叉后，两个个体分别变为： 　　10 011 011 　　01 110 101 　　即只有两个切点之间的部分进行了交换。 　　算法步骤如图3所示： 　　图3 双切点交叉遗传算法流程图 　　2 计算机仿真和结果分析 　　为了考察上述三种改进遗传算法的性能，选取一个测试函数――Rastrigrim函数进行测试。 　　Rastrigrim函数： 　　其函数图形如图4所示： 　　图4 Rastrigrim函数图形 　　我们把基本遗传算法（GA）与三种改进的遗传算法（SBOGA、GMGA和DblGEGA）对Rastrigrim函数进行测试，得到的进化曲线如图5所示。 　　图5 Rastrigrim函数的进化曲线 　　由图5我们可知，虽然基本遗传算法GA也能得到比较优良的解，但是改进后的三种遗传算法得到的解无疑更近似于理论最优解。 　　利用四种遗传算法分别进行仿真实验，运行20次，结果如表1所示： 　　表1 仿真实验结果（运行20次） 　　平均值 最好值 最差值