遗传算法是什么？用选择、交叉和变异来进化出好答案

遗传算法（Genetic Algorithm，GA）是一种模拟生物遗传和自然选择过程来寻找问题最优解的搜索算法，是演化计算中最有代表性的一种方法。它由美国密歇根大学的约翰·霍兰德及其学生在 20 世纪 60 至 70 年代发展起来，霍兰德在 1975 年出版的《自然与人工系统中的适应》奠定了它的理论基础；他的学生 David Goldberg 在 1989 年出版的教材让遗传算法得到了广泛的普及。

从生物学借来的概念

遗传算法使用了一套来自遗传学的术语。染色体：一个候选解的编码形式，比如一串由 0 和 1 组成的二进制数字，或者一串实数、一个城市访问顺序。基因：染色体上的每一个位置。种群：一群染色体，也就是同时维护的一批候选解。适应度：衡量一个候选解有多好的数值，由要解决的问题决定。

算法的步骤

第一步，随机生成一个初始种群。第二步，计算每个个体的适应度。第三步，选择：从当前种群中挑选出用来繁殖的个体，适应度高的被选中的概率更大。常用的方式有轮盘赌选择，每个个体被选中的概率与它的适应度成正比；以及锦标赛选择，每次随机抽出几个个体，选其中最好的那个。第四步，交叉：把两个被选中的父代染色体在某个位置切开，交换它们的后半段，产生两个新的子代。这模仿了生物有性繁殖中基因的重组，能够把不同个体中好的“片段”组合到一起。第五步，变异：以一个很小的概率，随机地改变子代染色体中的某些基因，比如把 0 变成 1。变异为种群引入新的可能性，防止种群过早地变得单一。第六步，用新一代替换旧的种群，有时会直接保留上一代中最好的几个个体，叫作精英保留，保证最好的解不会丢失。重复第二到第六步，直到满足停止的条件。

一个例子：旅行商问题

一个推销员要访问若干个城市，每个城市只去一次，最后回到出发地，怎样走总路程最短？可以把一条访问路线编码为城市的一个排列，适应度是路线总长度的倒数，越短越好。通过选择较短的路线、交叉组合两条路线的部分顺序、随机交换路线中两个城市的位置作为变异，一代代演化，就能找到相当短的路线。需要注意的是，对于排列这样的编码，普通的交叉会产生重复访问某些城市的非法路线，需要使用专门设计的交叉方式，比如部分匹配交叉、顺序交叉。

为什么它能工作

霍兰德提出的模式定理给出了一种解释：适应度高于平均水平的、短小的基因片段组合（叫作模式），在一代代的选择和交叉中，会以指数的速度增加。好的“积木块”被不断地保留和组合，最终构建出好的解，这被称为积木块假说。

使用中的问题

编码的设计对效果影响很大，需要让交叉和变异能产生有意义的新解。早熟收敛是常见的问题：种群很快变得非常相似，失去了多样性，停在一个局部最优解上。可以通过增加种群规模、提高变异率、保持多样性的策略来缓解。此外，遗传算法需要大量地计算适应度，参数也需要调节，在可以使用梯度信息的问题上往往不如梯度方法高效。遗传算法被广泛用于调度和排班、车间作业安排、网络和电路设计、特征选择、神经网络结构和超参数的优化等领域。