|
引言 ✦ 传统的遗传算法是一种借鉴于生物界自然选择和进化机制发展起来的高度并行、随机、自适应的全局优化概率搜索算法。因为优化时不依赖于梯度，具有很强的鲁棒性和全局搜索能力。因此，被广泛应用于机器学习、模式识别、数学规划等领域。然而，随着遗传算法的广泛应用以及研究的深人，其诸多缺陷与不足也暴露出来，例如，早熟收敛问题（下简称“早熟”）。 1 “早熟收敛”介绍 1.1 何为“早熟” 早熟性收敛，也叫“早熟”(Prematurity)，是指在遗传算法早期，在种群中出现了超级个体，该个体的适应值大大超过当前种群的平均个体适应值。从而使得该个体很快在种群中占有绝对的比例，种群的多样性迅速降低，群体进化能力基本丧失，从而使得算法较早收敛于局部最优解的现象。 1.2 “早熟”现象举例 具体来讲，当我们在某个算法上寻优求解时，不可避免地有时得到的解为局部最优解，如图1所示：  图1 遗传算法陷入局部最优 此时，算法就进入局部最优解，且由于算法的某方面限制，使得算法跳不出局部最优解的范围，这种现象就称作算法早熟。 在使用算法对多维函数进行优化时，算法同样可能会陷入局部最优解，如图2所示：  图2 多维优化问题陷入局部最优 1.3 “早熟”现象成因 早熟收敛的发生主要和下列几个方面有关: ⚫ 群体中存在超级个体 选择操作中当群体中存在个别超级个体时(该个体的适应度比其他个体高得多)，该个体在选择算子作用下将会多次被选中，下一代群体很快被该个体所控制，从而导致群体停滞不前。 ⚫交叉概率与变异概率的设置 交叉和变异操作发生的频度是受交叉概率Pc和变异概率Pm控制的，Pc和Pm的恰当设定涉及全局搜索和局部搜索能力的均衡，进化搜索的最终结果对Pc、Pm的取值相当敏感，不同Pc、Pm的取值很可能会导致不同的计算结果。 ⚫ 群体规模的设置 当群体规模较小时，群体中多样性程度低，个体之间竞争性较弱，随着进化的进行，群体很快趋于单一化，交叉操作产生新个体的作用渐趋消失，群体的更新只靠变异操作来维持，群体很快终止进化；当群体规模取值较大时，势必造成计算量的增加，计算效率受到影响。 ⚫最大迭代次数作为终止条件 遗传算法常用的终止判断条件为，当迭代次数达到人为规定的最大遗传代数时，则终止进化。如迭代次数过少，进化不充分，也会造成未成熟收敛。 为克服未成熟收敛，许多学者对算法改进进行了一些有益的探索，特别对遗传控制参数的设定，提出了自适应的交叉和变异，并获得了一些有益的结论。但是遗传算法的未成熟收敛与上述诸多因素有关，在应用遗传算法解决实际问题时，控制参数如何设定、遗传算子如何设计往往是根据实际问题试探性地给出的，不恰当的设定会在很大程度上影响算法的性能。 2 多种群遗传算法 针对遗传算法存在的上述问题，出现了一种多种群遗传算法(Multiple Population GA，MPGA）来取代常规的标准遗传算法(Standard GA,SGA) 2.1 多种群遗传算法的改进 MPGA在SGA的基础上主要有以下改进： 1.各种群取不同的控制参数 SGA仅靠单个群体进行进化，而遗传算法的结果往往又依赖于一些重要控制参数，如种群数、交叉概率、变异概率、编码方式等。MPGA引入多个种群同时进行优化搜索，对不同的种群赋予不同的控制参数，从而兼顾算法的全局搜索和局部搜索。 2.移民算子沟通多种群进行协同进化 各种群相对独立，种群交互通过移民算子联系。移民算子将各种群的最优个体定期引入其它种群中，实现种群之间的协同进化，最终获取最优解。 3.人工选择算子辅助算法终止 通过人工选择算子保存各种群每个进化代中的最优个体，并作为判断算法收敛的依据。 多种群遗传算法的流程图如图3所示：  图3 多种群遗传算法流程图 下面对上述改进展开详细说明与分析。 2.2 各种群取不同的控制参数 交叉概率Pc和变异概率Pm的取值决定了算法全局搜索和局部搜索能力的均衡。在SGA中，交叉算子是产生个体的主要算子，它决定了遗传算法全局搜索的能力；而变异算子只是产生新个体的辅助算子，它决定了遗传算法的局部搜索能力。许多学者建议选择较大的Pm(0.7~0.9)和较小的Pm(0.001~0.05)。但是Pc和Pm的取值方式还是有无数种，对于不同的选择，优化结果差异也是很大的。 MPGA弥补了SGA的这一不足，通过多个设有不同控制参数的种群协同进化，同时兼顾了算法的全局搜索和局部搜索。使得对遗传控制参数的敏感性降低，能够有效地克服未成熟收敛的现象。 2.3 移民算子 各种群是相对独立的，相互之间通过移民算子联系。移民算子将各种群在进化过程中出现的最优个体定期地(每隔一定的进化代数)引人其他的种群中，实现种群之间的信息交换。 具体的操作规则是将目标种群中的最差个体用源种群的最优个体代替。移民算子在MPGA中至关重要，如果没有移民算子，各种群之间失去了联系，MPGA将等同于用不同的控制参数进行多次SGA计算，从而失去了MPGA的特色。 2.4 人工选择算子 精华种群和其它种群不同，每一代进化后，通过人工选择算子选出种群的最优个体放入精华种群，并且精华种群不进行选择、交叉、变异等操作，保证进化过程中最优个体不被破坏和丢失。 精华种群的最优个体最少保持代数将作为算法终止判据，该判据充分利用了遗传算法在进化中的知识积累，较之最大遗传代数更为合理。 3 总结 🔹多种群遗传算法就相当于多个标准遗传算法的结合体，只不过需要通过移民算子将这些个标准的遗传算法联系起来。 🔹如果没有移民算子，各种群之间将失去联系变成独立进化。MPGA将等同于用不同控制参数进行多次SGA计算，从而失去了MPGA的特色。 🔹然后通过人工选择算子保存各种群每个进化代中的最优个体，最后以最优个体最少保持代数作为终止判据。 参考资料 [1].爱听雨的犬猫.多种群遗传算法优化算法[EB/OL].(2022-8-26)[2023-3-27]. https://blog.csdn.net/m0_56306305/article/details/126437357 [2].M.scoe.遗传算法系列 | 多种群遗传算法(matlab)[EB/OL].(2022-7-21)[2023-3-27]. https://blog.csdn.net/sfejojno/article/details/125918337 [3].早熟收敛_百度百科(baidu.com)[EB/OL].(2022-8-5)[2023-3-27]. |
|
|
