遗传算法及对于过早收敛的改进

1、遗传算法及对于过早收敛的改进摘 要 遗传算法是模拟达尔文生物进化论中的自然 选择与遗传学机理的生物过程的一种计算模型。该模型通过 模拟自然进化过程来搜索最优解，其应用非常广泛。但是在 运用遗传算法的过程之中经常遇到过早收敛的问题，为了改 进该问题，在文中对遗传算法进行了介绍，并在此基础上就 如何改进过早收敛进行探讨。关键词 遗传算法；过早收敛；改进中图分类号 TP18 文献标识码 A 文章编号 2095-6363 （2017）15-0023-01遗传算法（ Genetic Algorithm ，GA ）是自然科学与工程 科学互相结合的产物，是一类借鉴达尔文自然选择机理（适 者生存，优胜劣汰遗传

2、机制）演化而来的随机化搜索方法。遗传算法求解优化问题的性能与交叉概率（Pc）、变异概率 （ Pm）等参数的选择有着很大的联系。 本文基于传统思 路，对 GA 的交叉概率和变异概率参数进行自适应控制，对 过早收敛问题进行了适当优化。1 遗传算法综述1.1 遗传算法思想 通常来说，遗传算法包括三个算子，即选择、交叉和变 异。选择算子的作用是为了提升整个群体的平均适度值，在 整个群体中选择那些评价值高的个体组成交配池的主要群 体： 交叉算子的主要作用是选择交配池中的优良基因遗传 给下一代，先将交配池中个体进行两两配对，再有目的的交 换部分基因，生成基因性状更加复杂的个体；变异算子是对 个体某一个或是

3、几个按照某一较小的概率进行反转二进制 字符。从而实现对自然界中基因突变现象的模拟。1.2 遗传算法的思想流程1）初始化群体； 2）计算群体上每个个体的适应度值；3）针对于个体适应度值，依据某个规则选择将进入下一代 的个体； 4）通过概率 Pc进行交叉操作； 5）通过概率 Pm 进 行突变操作； 6）未达到终止条件，则返回 2）步，否则进入 下一步； 7）输出群体中适应度值最大的个体作为问题的满 意解或最优解。2 过早收敛及其特点 过早收敛在早期的选择过程，种群中就出现了“完美” 个体，该类个体的适应度值特别大，然而选择压力很大，后 期变异概率比较小。继而在后期的繁殖中占主体地位，种群 的多样性

4、会很快的降低进而导致种群多样化的丧失。过早收敛对于整个种群来说弊大于利，因为结果并非是 全局最优，仅仅是局部最优。特别是到了算法进行的后期， 进过算法的多代进化，完美的个体已经在种群中占据绝大多数，这时传统的交叉操作已经不能达到预期的作用。变异操 作虽然能产生不同于父代的个体，使整 ?过程能跳出局部最 优而达到全局最优，但是变异概率是小概率事件，同样无法 达到理想结果。3 过早收敛的原因3.1 种群规模太小 种群数量太小，种群基因库不能被多重选择，只靠后期 变异带来新的基因，效率是远远不够的。3.2 选择压力 选择过程会根据适应度值的大小进行遗传或者淘汰。过 大的选择压力会导致种群多样性的流失

5、，以至于遗传过程趋 于收敛。3.3 变异概率 遗传算法中，对收敛速度起到决定性作用的是变异概 率。当 Pm 太小时，变异过程不会产生不同于父本的个体， 整个过程会去趋近于收敛。4 预防过早收敛的措施4.1 传统方式 选择合适的种群规模。在计算量允许的情况下，尽可能 选择较大的群体规模；适中的选择压力，避免选择过程将大 多数个体淘汰，保持种群的多样性。4.2 改进方式遗传算法中的算子主要是选择、交叉、变异。作为遗传 算法中最主要的部分，交叉和变异对于避免过早收敛起到决 定性的最用。如今比较流行的交叉变异过程选择对应的概率 都是一个固定的常数，根据问题的实际情况来确定。1994 年， Sriniv

6、as 依据遗传算法传统思想建立了一套随 当代种群适应度值而动态变化的自适应遗传算法。其中交叉 概率和变异概率的值由以下公式确定。式中：为种群中最大的适应度值；为每代种群中平均适 应度值；为要较差的两个个体中较大的适应度值；为要变异 个体的适应度值； K1 ，k2，k3，k4取（ 0，1）区间的值。 Pc 和 Pm 随适应度值变化的曲线如图 1、图 2 所示。由以上公式得出在遗传过程中，当种群趋于收敛达到局 部最优时， 遗传过程的 Pc 和 Pm 概率会增加， 而处于刚开始 阶段个体适应度值大小不一时，交叉变异概率会很小。这样 保证了当出现“完美”个体时，不会被该类个体迅速占领主 要地位而过早收敛。5 结论 通过自适应遗传算法，交叉概率和变异概率随着个体的 适应度值在种群平均适应度和最大适应度值之间进行线性 调整，打破了传统交叉变异概率一成不变的传统方式，使得 遗传算法得到最终的全局最优解。参考文献1 何大阔，王福利 .一种提高遗传算法全局收敛型的方法J. 东北大学学报（自然科学版） ，2003，24（6）：51