论文部分内容阅读
摘 要 遗传算法是模拟达尔文生物进化论中的自然选择与遗传学机理的生物过程的一种计算模型。该模型通过模拟自然进化过程来搜索最优解，其应用非常广泛。但是在运用遗传算法的过程之中经常遇到过早收敛的问题，为了改进该问题，在文中对遗传算法进行了介绍，并在此基础上就如何改进过早收敛进行探讨。
关键词 遗传算法；过早收敛；改进
中图分类号 TP18 文献标识码 A 文章编号 2095-6363（2017）15-0023-01
遗传算法（Genetic Algorithm，GA）是自然科学与工程科学互相结合的产物，是一类借鉴达尔文自然选择机理（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。
遗传算法求解优化问题的性能与交叉概率（Pc）、变异概率（Pm）等参数的选择有着很大的联系。本文基于传统思路，对GA的交叉概率和变异概率参数进行自适应控制，对过早收敛问题进行了适当优化。
1 遗传算法综述
1.1 遗传算法思想
通常来说，遗传算法包括三个算子，即选择、交叉和变异。选择算子的作用是为了提升整个群体的平均适度值，在整个群体中选择那些评价值高的个体组成交配池的主要群体： 交叉算子的主要作用是选择交配池中的优良基因遗传给下一代，先将交配池中个体进行两两配对，再有目的的交换部分基因，生成基因性状更加复杂的个体；变异算子是对个体某一个或是几个按照某一较小的概率进行反转二进制字符。从而实现对自然界中基因突变现象的模拟。
1.2 遗传算法的思想流程
1）初始化群体；2）计算群体上每个个体的适应度值；3）针对于个体适应度值，依据某个规则选择将进入下一代的个体；4）通过概率Pc进行交叉操作；5）通过概率Pm进行突变操作；6）未达到终止条件，则返回2）步，否则进入下一步；7）输出群体中适应度值最大的个体作为问题的满意解或最优解。
2 过早收敛及其特点
过早收敛在早期的选择过程，种群中就出现了“完美”个体，该类个体的适应度值特别大，然而选择压力很大，后期变异概率比较小。继而在后期的繁殖中占主体地位，种群的多样性会很快的降低进而导致种群多样化的丧失。
过早收敛对于整个种群来说弊大于利，因为结果并非是全局最优，仅仅是局部最优。特别是到了算法进行的后期，进过算法的多代进化，完美的个体已经在种群中占据绝大多数，这时传统的交叉操作已经不能达到预期的作用。变异操作虽然能产生不同于父代的个体，使整個过程能跳出局部最优而达到全局最优，但是变异概率是小概率事件，同样无法达到理想结果。
3 过早收敛的原因
3.1 种群规模太小
种群数量太小，种群基因库不能被多重选择，只靠后期变异带来新的基因，效率是远远不够的。
3.2 选择压力
选择过程会根据适应度值的大小进行遗传或者淘汰。过大的选择压力会导致种群多样性的流失，以至于遗传过程趋于收敛。
3.3 变异概率
遗传算法中，对收敛速度起到决定性作用的是变异概率。当Pm太小时，变异过程不会产生不同于父本的个体，整个过程会去趋近于收敛。
4 预防过早收敛的措施
4.1 传统方式
选择合适的种群规模。在计算量允许的情况下，尽可能选择较大的群体规模；适中的选择压力，避免选择过程将大多数个体淘汰，保持种群的多样性。
4.2 改进方式
遗传算法中的算子主要是选择、交叉、变异。作为遗传算法中最主要的部分，交叉和变异对于避免过早收敛起到决定性的最用。如今比较流行的交叉变异过程选择对应的概率都是一个固定的常数，根据问题的实际情况来确定。
1994年，Srinivas依据遗传算法传统思想建立了一套随当代种群适应度值而动态变化的自适应遗传算法。其中交叉概率和变异概率的值由以下公式确定。
式中：为种群中最大的适应度值；为每代种群中平均适应度值；为要较差的两个个体中较大的适应度值；为要变异个体的适应度值；K1，k2，k3，k4——取（0，1）区间的值。Pc和Pm随适应度值变化的曲线如图1、图2所示。
由以上公式得出在遗传过程中，当种群趋于收敛达到局部最优时，遗传过程的Pc和Pm概率会增加，而处于刚开始阶段个体适应度值大小不一时，交叉变异概率会很小。这样保证了当出现“完美”个体时，不会被该类个体迅速占领主要地位而过早收敛。
5 结论
通过自适应遗传算法，交叉概率和变异概率随着个体的适应度值在种群平均适应度和最大适应度值之间进行线性调整，打破了传统交叉变异概率一成不变的传统方式，使得遗传算法得到最终的全局最优解。
参考文献
[1]何大阔，王福利.一种提高遗传算法全局收敛型的方法[J].东北大学学报（自然科学版），2003，24（6）：511-514.
[2]张铃，张钹.遗传算法机理的研究[J].软件学报，2000（7）：945-951.
[3]蒋腾旭，谢枫.遗传算法中防止早熟收敛的几种措施[J].计算机与现代化，2006（12）：54-57.
关键词 遗传算法；过早收敛；改进
中图分类号 TP18 文献标识码 A 文章编号 2095-6363（2017）15-0023-01
遗传算法（Genetic Algorithm，GA）是自然科学与工程科学互相结合的产物，是一类借鉴达尔文自然选择机理（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。
遗传算法求解优化问题的性能与交叉概率（Pc）、变异概率（Pm）等参数的选择有着很大的联系。本文基于传统思路，对GA的交叉概率和变异概率参数进行自适应控制，对过早收敛问题进行了适当优化。
1 遗传算法综述
1.1 遗传算法思想
通常来说，遗传算法包括三个算子，即选择、交叉和变异。选择算子的作用是为了提升整个群体的平均适度值，在整个群体中选择那些评价值高的个体组成交配池的主要群体： 交叉算子的主要作用是选择交配池中的优良基因遗传给下一代，先将交配池中个体进行两两配对，再有目的的交换部分基因，生成基因性状更加复杂的个体；变异算子是对个体某一个或是几个按照某一较小的概率进行反转二进制字符。从而实现对自然界中基因突变现象的模拟。
1.2 遗传算法的思想流程
1）初始化群体；2）计算群体上每个个体的适应度值；3）针对于个体适应度值，依据某个规则选择将进入下一代的个体；4）通过概率Pc进行交叉操作；5）通过概率Pm进行突变操作；6）未达到终止条件，则返回2）步，否则进入下一步；7）输出群体中适应度值最大的个体作为问题的满意解或最优解。
2 过早收敛及其特点
过早收敛在早期的选择过程，种群中就出现了“完美”个体，该类个体的适应度值特别大，然而选择压力很大，后期变异概率比较小。继而在后期的繁殖中占主体地位，种群的多样性会很快的降低进而导致种群多样化的丧失。
过早收敛对于整个种群来说弊大于利，因为结果并非是全局最优，仅仅是局部最优。特别是到了算法进行的后期，进过算法的多代进化，完美的个体已经在种群中占据绝大多数，这时传统的交叉操作已经不能达到预期的作用。变异操作虽然能产生不同于父代的个体，使整個过程能跳出局部最优而达到全局最优，但是变异概率是小概率事件，同样无法达到理想结果。
3 过早收敛的原因
3.1 种群规模太小
种群数量太小，种群基因库不能被多重选择，只靠后期变异带来新的基因，效率是远远不够的。
3.2 选择压力
选择过程会根据适应度值的大小进行遗传或者淘汰。过大的选择压力会导致种群多样性的流失，以至于遗传过程趋于收敛。
3.3 变异概率
遗传算法中，对收敛速度起到决定性作用的是变异概率。当Pm太小时，变异过程不会产生不同于父本的个体，整个过程会去趋近于收敛。
4 预防过早收敛的措施
4.1 传统方式
选择合适的种群规模。在计算量允许的情况下，尽可能选择较大的群体规模；适中的选择压力，避免选择过程将大多数个体淘汰，保持种群的多样性。
4.2 改进方式
遗传算法中的算子主要是选择、交叉、变异。作为遗传算法中最主要的部分，交叉和变异对于避免过早收敛起到决定性的最用。如今比较流行的交叉变异过程选择对应的概率都是一个固定的常数，根据问题的实际情况来确定。
1994年，Srinivas依据遗传算法传统思想建立了一套随当代种群适应度值而动态变化的自适应遗传算法。其中交叉概率和变异概率的值由以下公式确定。
式中：为种群中最大的适应度值；为每代种群中平均适应度值；为要较差的两个个体中较大的适应度值；为要变异个体的适应度值；K1，k2，k3，k4——取（0，1）区间的值。Pc和Pm随适应度值变化的曲线如图1、图2所示。
由以上公式得出在遗传过程中，当种群趋于收敛达到局部最优时，遗传过程的Pc和Pm概率会增加，而处于刚开始阶段个体适应度值大小不一时，交叉变异概率会很小。这样保证了当出现“完美”个体时，不会被该类个体迅速占领主要地位而过早收敛。
5 结论
通过自适应遗传算法，交叉概率和变异概率随着个体的适应度值在种群平均适应度和最大适应度值之间进行线性调整，打破了传统交叉变异概率一成不变的传统方式，使得遗传算法得到最终的全局最优解。
参考文献
[1]何大阔，王福利.一种提高遗传算法全局收敛型的方法[J].东北大学学报（自然科学版），2003，24（6）：511-514.
[2]张铃，张钹.遗传算法机理的研究[J].软件学报，2000（7）：945-951.
[3]蒋腾旭，谢枫.遗传算法中防止早熟收敛的几种措施[J].计算机与现代化，2006（12）：54-57.