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

1. 遗传算法流程

遗传算法的基本流程如下图^[3]：

1.1 随机初始化群体

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

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

 1.2 评估初始化群体的适应度

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

1) 字符和字符之间是独立的，即各特性之间独立

2) 序列的长度尽量少，只考虑与问题相关的特性

例如，我想知道什么样的房子性价比高。通过一些分析发现影响房子价格的因素有朝向，楼层，交通，是否是学区房，房屋面积等。而与房子旁边是否有山，是不有河无关(当然对于迷信风水的人来说是有关的)，那么这两个特性我们在建模时就考虑它。建模时每个有效且独立的因素都对应到一个字符即基因，字符组合在一起成为一个解即染色体。例如1(表示坐北朝南)-2(楼层可分为低中高，2表示中)-1(交通也可划分为3档，1表示交通便利有地铁)-1(同理，1表示是学区房)-3(同理，3表示300平米)，最后合到一起就是1-2-1-1-3，这是一个解。但我们想要知道的是性价比而不是房子的价格，因此需要将这个解输入到性价比评估函数y=F(x)，得到一个值，这个值即适应度。房子条件好并不代表性价比高，1-2-1-1-3这个解对应的适应度可能并不高，整个过程我们要找到最优解 (哈哈，其实看看房产公司统计的结果，排队看房的人和关注的人数最多的应该是性格比最高的，这里房子性价比计算只是举个例子，可能还不太恰当)。

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

1.3 获取群体中适应度高的个体

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

1.4 循环

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

1.4.1 先计算群体中每条染色体的适应度

1.4.2 再挑选出两条染色体，作为亲本

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

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

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

1.4.3 父母本部分区域进行交换(crossover)

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

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

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

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

1.4.4 突变(mutation)

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

 1.4.5 通过选择算子获取到适应度最高的个体

 1.5 终止运行

在处理一些NP完全问题(NP complete problem)时，像很多其它算法一样，遗传算法可以无限接近最优，但是无法到达最优。接近最优的过程可能久到让人无法忍受，或者根本没有必要打100分，打80分已经可以解决问题了，这时就需要终止运行。一般而言，终止运行的条件主要有：

1) 传代次数限制。例如只循环1万次，传到1万代就结束

2) 运行时间。例如程序只运行1周，最终无论得到什么样的结果都终止

3) 适应度无显著变化。例如到5000代时最优解的适应度与5001代时的无显著变化，这时可终止

2. 遗传算法的优缺点

2.1 遗传算法的优点

1) 如果处理得当，可以在优化问题中得到全局最优解

2) 比较容易实现并行化计算

3) 遗传算法以结果为导向，最关注的两个点，一是编码与解码，一是适应度函数。它需要的背景知识少，也不需要太关注过程。所以应用范围非常广，可以解决非线性、不连续的问题，甚至有些无法清晰知道过程的问题，也可以解决。

总之就是原理简单，功效强大。

 2.2 遗传算法的缺点

1) 遗传算法非常依赖适应度函数，可以说适应度函数直接确定了结果的走向，而这个函数需要使用者自行提供，而且还没有标准，需根据实现问题总结出来

2) 群体大小选择不当，或者选择压设置不对，都可能会过早收敛，错过全局最优解，只能达到局部最优解

3) 因为遗传算法并不太关注过程，所以计算过程中的参数稍有不同可能会得到不同结果。这些参数包括群体大小、交换频率、突变频率等。

4) 当染色体过长(即基因数过多)时，需要重组的片段更多，导致群体规模非常大，使计算时间急剧增加

附：达尔文的自然选择理论^[6]

Owing to this struggle for life, variations, however slight and from whatever cause proceeding, if they be in any degree profitable to the individuals of a species, in their infinitely complex relations to other organic beings and to their physical conditions of life, will tend to the preservation of such individuals, and will generally be inherited by the offspring. The offspring, also, will thus have a better chance of surviving, for, of the many individuals of any species which are periodically born, but a small number can survive. I have called this principle, by which each slight variation, if useful, is preserved, by the term Natural Selection.

参考文献：

[1] Ajith Abraham1, Nadia Nedjah2and Luiza de Macedo Mourelle. Evolutionary Computation: from GeneticAlgorithms to Genetic Programming. 2006. Studies in Computational Intelligence

[2] John H. Holland. Adaptation in Natural and Articial Systems. 1975

[3] Absalom E. Ezugwu, Olawale J. Adeleke, Andronicus A. Akinyelu, Serestina Viriri. A conceptual comparison of several metaheuristic algorithms on continuous optimisation problems. 2019. Neural Computing and Applications.

[4] https://www.genome.gov/genetics-glossary/Crossing-Over

[5] Sujatha Balaraman. Applications of evolutionary algorithms and neural network for congestion management in power systems

 [6] Darwin, C. The Origin of Species. 1859