遗传算法的早熟问题

遗传算法的早熟问题 遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应的全局优化概率搜索算法。由于优化时不依赖于梯度，具有很强的鲁棒性和全局搜索能力，因此，被广泛应用于机器学习、模式识别、数学规划等领域。然而，随着遗传算法的广泛应用以及研究的深入，其诸多缺陷与不足也暴露出来，早熟收敛正是其中的一大问题。 未成熟收敛是遗传算法中不可忽视的现象，主要表现在群体中的所有个体趋于同一状态而停止进化（也就是过早收敛），算法最终不能给出令人满意的解。未成熟收敛的发生主要和下列几个方面有关：

• 选择操作是根据当前群体中个体的适应度值所决定的概率进行的，当群体中存在个体超常个体时（该个体的适应度比其他个体高得多），该个体在选择算子作用下将会多次被选中，下一代群体很快被该个体所控制，群体中失去竞争性，从而导致群体停滞不前。
• 交叉和变异操作发生的频度是受交叉概率Pc和变异概率Pm控制的。Pc和Pm的恰当设定涉及遗传算法全局搜索和局部搜索的能力的均衡，进化搜索的最终结果对Pc和Pm的取值相当敏感，不同的Pc、Pm取值很可能会导致不同的计算结果。
• 群体规模对遗传算法的优化性能也有较大的影响。当全体规模较小时，群体中多样性程度低，个体之间竞争性较弱，随着进化的进行，群体很快趋于单一化，交叉操作产生新个体的作用渐趋消失，群体的更新只靠变异操作来维持，群体很快终止进化，当群体规模取值较大时，势必造成计算量的增加，计算效率收到影响
• 遗传算法常用的终止判据是，当迭代次数到达认为规定的最大遗传代数时，则终止进化。如迭代次数过少，进化不充分，也会造成不成熟收敛。为克服未成熟收敛，对遗传控制参数的设定尤为重要，因此自适应的交叉和变异得以出现。

由于早熟现象的产生，因此又出现了其他算法来避免这一问题，如：粒子种群算法（PSO），多种群遗传算法等