浅谈遗传算法及其部分改进算法

唐文琦 曾干敏 刘泽宇

摘 要：遗传算法广泛应用于函数寻优、组合寻优等方面，同时算法设计灵活易实现，但具有易早熟收敛的缺点。本文简单阐述遗传算法工作原理，分析其易早熟收敛的原因，最后介绍了两种改进算法——多种群遗传算法、模拟退火遗传算法，并分析两种算法在避免早熟收敛上的原理及效果。

关键词：遗传算法；模拟退火遗传算法；多种群遗传算法

遗传算法（Genetic Algorithm）是一种全局优化概率算法，其借鉴进化论的自然选择机制和染色体的交叉变异机制，最终保留对于当前环境适应能力最强的个体或者群体。

对于具体的问题，通过编码表示解空間中的解；使用适应度函数衡量解的优劣程度；交叉和变异引入随机因素，避免寻优过程陷入局部最优；在每次进化的过程中，淘汰部分适应度较弱的个体，最终寻得全局最优。

1 遗传算法的具体步骤以及优缺点

在遗传算法中，个体（染色体）为一段编码，代表解空间中的一个可行解；基因表示个体上的编码片段；群体为个体集合；适应度为个体对应解的优劣程度。

1.1 具体步骤

算法的主要步骤如下：

1）编码。使用适当的编码表示解空间中的所有可行解，目前有二进制码等被广泛使用的编码方案。但是对于具体的问题，需要设计特定的编码方案，例如解决TSP问题时，以所有点的访问顺序作为编码。

2）初始化染色体种群。随机生成个体上的编码信息，其所对应的解应该是可行的，遗传算法从这些初始解出发迭代进化。

3）计算个体适应度。对于具体的问题，通常都有一个目标函数，通过个体的编码计算出其目标值大小，再根据待优化问题的性质，得到对应的适应度。

4）选择。随机挑选个体进行交叉、变异，适应度越大，选中概率越大。

5）交叉、变异。模拟生物细胞核内染色体间交换基因片段和染色体上基因突变的过程。交叉和变异均是随机发生的，其中变异发生的概率很低。交叉让个体间交换基因片段，生成新的个体；变异使得个体上某个编码片段发生突变，生成新的个体。

6）更新种群。模拟自然选择机制，一般是基于适应度大小，保留较优的部分个体，从而使得种群进化。

1.2 遗传算法优缺点

1.2.1 遗传算法的优点

遗传算法寻优过程不依赖于梯度，可以通过交叉、变异跳出局部最优，具有较强的全局搜索能力；具有很强的灵活性，各个步骤的具体实现可以高度自定义；可以作为其他算法的外部框架来提升改进其他算法。

1.2.2 遗传算法的缺点

早熟收敛[1]是遗传算法的最大缺点，其表现为群体中所有个体之间相似度很高，进而导致进化缓慢甚至停止。

发生早熟收敛的原因主要有：

1）群体中出现部分个体的适应度比其余个体高很多，在每次迭代过程中，这些个体极易被选中，经过多次交叉、变异后，群体中所有个体彼此相似，相互之间失去了竞争性，导致群体的进化过程停滞不前，无法寻得全局最优解。

2）参数设置不当和每个步骤具体的实现设计得不合适，对于参数和步骤的具体实现没有科学的标准，只能试探性地给出。

2 遗传算法的部分改进算法

对于遗传算法的易早熟收敛，这里提出两个改进算法——多种群遗传算法、模拟退火遗传算法。

2.2 多种群遗传算法

鉴于参数和遗传算法每个步骤具体实现的设置不当导致算法早熟收敛，多种群遗传算法[4]（Multiple Population Genetic Algorithm）在遗传算法的基础上做了如下改进：

1）引入多个种群并行寻优，每个种群具有不同的算法参数（影响着全局、局部寻优能力）。

2）使用移民算子在算法迭代过程中，使种群定期使用最优个体替换掉相邻种群的最劣个体，实现多种群之间协同进化。

3）在每次迭代过程中，使用人工选择算子选出各种群最优个体，组成精英种群，作为判断算法迭代结束的依据，一般迭代结束条件为精英种群中的最优个体保持指定代数以上。精英种群不发生交叉、变异，只起保存作用。

3 总结

遗传算法寻优不依赖于梯度，全局寻优能力较强，但是易早熟收敛。模拟退火遗传算法引入Metropolis接受准则，对于较差的解不完全抛弃，以一定的概率保留，有效的抑制了早熟收敛。多种群遗传算法引入具有不同参数的种群协同搜索，有效地避免了参数设置不当造成的搜索效果不佳。

参考文献：

[1]蒋腾旭，谢枫.遗传算法中防止早熟收敛的几种措施[J].计算机与现代化，2006（12）：54-56.

[2]王雪梅，王义和.模拟退火算法与遗传算法的结合[J].计算机学报，1997（4）：381-384.

[3]常忠东.对模拟退火算法的衰减函数T和MetrOPolis准则的改进[J].内蒙古民族大学学报（自然汉文版），2011，26（4）：408-409.

[4]叶在福，单渊达.基于多种群遗传算法的输电系统扩展规划[J].电力系统自动化，2000，24（5）.

作者简介：唐文琦，男，汉族，本科。