遗传算法(Genetic Algorithm)

遗传算法(GA, Genetic Algorithm)是进化算法(EA, Evolutionary Algorithm)的一种。进化算法还包括进化编程(Evolutionary programming)、 进化策略(Evolution Strategy)、以及遗传编程(Genetic programming)等。一般认为遗传算法是由John H. Holland于1975正式提出的，之后Holland及其研究团队还不断完善遗传算法理论。目前，遗传算法作为一种重要的最优化方法得到广泛应用

一. 遗传算法概论

1.1 遗传算法的基本思想

• 遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法
• 遗传算法起源于对生物系统所进行的计算机模拟研究。模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最佳解
• 遗传算法遵循自然界适者生存、优胜劣汰的原则，是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法

达尔文进化论的主要观点是：物竞天择，适者生存。遗传算法的基本思想就是模仿自然进化过程，通过对群体中具有某种结构形式的个体进行遗传操作，从而生成新的群体，逐渐逼近最优解。在求解过程中设定一个固定规模的种群，种群中的每个个体都表示问题的一个可能解，个体适应环境的程度用适应度函数判断，适应度差的个体被淘汰，适应度好的个体得以继续繁衍，繁衍的过程中可能要经过选择、交叉、变异，形成新的族群，如此往复得到更多更好的解

1.2 遗传算法的主要步骤

1.2.1 随机初始化

随机产生条染色体(chromosome)，也称个体(individual)。虽然在生物学上染色体和个体是完全不同的两个概念，但是在遗传算法中表示的是同一件事，即待优化问题的个解(solution)。这n条染色体/个体合在一起，称为群体(population)。群体的规模(即值)设置得过小很可能会导致过早收敛(premature convergence)，最终不能获取到全局最优解；而如果群体规模设置过大又会影响计算时间

另外，一条染色体是一定个数基因组成的。在遗传算法中最小的分类单元是基因，基因集合为染色体，染色体集合为群体

1.2.2 评估

在大多数遗传算法解决的问题中，有两个主要的点需要关注：其一是编码与解码，另一个是适应度函数(或称进化函数evaluation function)。通常人们会将问题抽象为一个函数，整个遗传算法工作的过程都是为了获取最优化的解。同时，函数的解通常以固定长度序列(数列或字符串)的形式出现，这条序列即上文的染色体。序列中的每个元素(数字或字符)即基因。将解的原始形式转化为序列的过程称为编码，反之则称为解码。问题千差万别，其解亦然。因此编码过程需要遵循两个基本原则：

• 字符和字符之间是独立的，即各特性之间独立
• 序列的长度尽量少，只考虑与问题相关的特性

最常见的编码是二进制编码，除此之外还有八进制、十六进制、树图编码，以及直接采用值进行编码等。另外，适应度函数可以同时对条染色体进行计算，因此遗传算法很适合用于并行计算

1.2.3 计算个体适应度

这一步称为选择算子(selection operator)，它是遗传算法中三大算子之一，另外两个是下面将要讲到的交叉算子(crossover operator)和变异算子(mutation operator)。选择算子用于从群体中挑选出两个或多个亲本用于杂交，它不仅关注如何构建子代，而且还关注子代的规模(需繁衍出多少子代)。选择的目的是突出适应的个体，就像希望的那样，他们的子代也会有更高的适应度

1.2.4 循环

通过不断循环(或称为进化)，以构建新的群体，并从新的群体中筛选适应度高的个体进行繁殖

1. 先计算群体中每条染色体的适应度
2. 再挑选出两条染色体，作为亲本

选取亲本是遗传算法比较关键的一步，它应用的是达尔文的适者生存理论(survival of the fittest)具体来说是适应度越高的染色体，被选择作为亲本的概率越高

在实践中，选择压(selection pressure)表示适应度高的染色体被选为亲本的程度。选择压确定了遗传算法的方向，它同时也极大地影响着遗传算法的收敛情况，大的选择压导致大的收敛率(convergence rate)。选择压可以理解为向着最优解每走一步的步伐大小，如果步伐太小，消耗的时间会非常久；如果全程大步流星，可能会过早的收敛，只获取到局部最优解，而不是全局最优解。此外，步伐太大还会降低群体的多样性。可以通过下图理解，图中每个红点表示一种解，蓝色波浪表示解的集合，一条绿色的横线表示一次筛选过程，因为最后要到最高点，所以划线方向不断往上。如果按照绿色的线从下往上移动，一方面可能会错过如图中的Solution1这个解，如果它被选中，其子代可能会到达全局最高点Peak C,但是因步伐太大这个点错过了，最后获取到的最高点是Peak A；另一方面因为很多步伐太快类似Solution2这些点过早地被淘汰掉，最后只剩下冲向Peak A和Peak B的点，因此群体的多样性也会降低。

为了保留上图中Solution1，同时又保证进化的方向。最开始人们想出来一种叫做轮盘赌(Roulette Wheel Selection)的方案，如下图。一方面让适应度高的具有更高被选择作为亲本的概率，另一方面又保留一些适应度较低但是有潜力的解

1.2.5 交换(crossover)

自然界的遗传变异过程比较复杂，遗传算法一再减化，最后仅模拟了两处：交换(Crossover)和变异(Mutation)，如下图：

在遗传算法中，父母本部分区域进行交换，产生子代(offspring/children)。如果要回归到生物学现象中，是同源染色体联会时的交叉互换(crossover)和非同源染色体重组(recombination)的结合体，或者更进一步说是两者的简化版。因此有些遗传算法的文献称这一步为crossover，有的则称为recombination，表达的是同一个步骤

Crossover可以发生在一个断点，如下图，这时一条染色体上的首尾基因在子代中肯定会分离：

因此，后来也出现了两个断点交叉互换，其至多个断点交叉互换：

1.2.6 突变(mutation)

在遗传算法中会对上步产生的子代进行基因突变，以获取到更多序列不同的子代，即增加群体的多样性。最开始人们想到的是随机位点突变，当然突变前的染色体也会复制，最终将所有染色体放到一起进行对比。然而，突变的位点毕竟很少，对比的群体产生了大量无效计算，因此，每次突变的子代就和亲本比，比亲本更适应的子代才保留下来，这样保证了突变的方向，又加快了计算速度

1. 通过选择算子获取到适应度最高的个体
2. 终止运行

在处理一些NP完全问题(NP complete problem)时，像很多其它算法一样，遗传算法可以无限接近最优，但是无法到达最优。接近最优的过程可能很久，这时就需要终止运行。一般而言，终止运行的条件主要有：

• 传代次数限制：例如只循环1万次，传到1万代就结束
• 运行时间：例如程序只运行1周，最终无论得到什么样的结果都终止
• 适应度无显著变化：例如到5000代时最优解的适应度与5001代时的无显著变化，这时可终止

二. 遗传算法的优缺点

2.1 遗传算法的优点

1. 如果处理得当，可以在优化问题中得到全局最优解
2. 比较容易实现并行化计算
3. 遗传算法以结果为导向，最关注的两个点，一是编码与解码，一是适应度函数。它需要的背景知识少，也不需要太关注过程。所以应用范围非常广，可以解决非线性、不连续的问题，甚至有些无法清晰知道过程的问题，也可以解决

2.2 遗传算法的缺点

1. 遗传算法非常依赖适应度函数，可以说适应度函数直接确定了结果的走向，而这个函数需要使用者自行提供，而且还没有标准，需根据实现问题总结出来
2. 群体大小选择不当，或者选择压设置不对，都可能会过早收敛，错过全局最优解，只能达到局部最优解
3. 因为遗传算法并不太关注过程，所以计算过程中的参数稍有不同可能会得到不同结果。这些参数包括群体大小、交换频率、突变频率等
4. 当染色体过长(即基因数过多)时，需要重组的片段更多，导致群体规模非常大，使计算时间急剧增加