A.5 遗传算法

1.物竞天择，能不能算出来

说起来，前面那些章我们聊得多是梯度下降，是顺着导数指的方向一步一步往下走。可世界上有大量的问题，压根就求不出导数，或者解空间大到没法一座山一座山地爬。比方说让小张给全班排一份课表，让冲突最少，这种组合优化问题，可行解的数量常常是天文数字，再灵光的解析方法也往往无从下手。

这时候不妨换个思路。达尔文讲物竞天择，适者生存，说穿了就是一大群个体里，更能适应环境的更容易活下来，活下来才有机会把好的特征传给下一代，一代一代累积下来，种群整体就越来越能干。这套道理学生物的人熟，可仔细琢磨，它本质上像是一种搜索，在一大堆候选解里，让好的那些更容易被保留下来，再彼此组合，慢慢筛出越来越好的解。这就是遗传算法（Genetic Algorithm）的核心想法。我们后面把一个候选解叫做一个个体（individual），把当前考虑的一批候选解叫做种群（population）。

我记得最早把这套想法写成算法的，是Holland教授上世纪七十年代做的事。那会儿算力有限，他更关心这套机制本身能不能成立，今天再看，它早已经是元启发式算法里最经典的一支。

2.把一个解写成一串：染色体编码

生物里有染色体，染色体上一节一节是基因。遗传算法也照搬这一套说法。我们把一个候选解编码成一串，这一串就叫一条染色体（chromosome），串上的每一个位置叫一个基因（gene），基因的取值叫等位基因（allele）。这些名词听起来玄乎，说到底就是一串数据，根据问题不同，编码方式可以差很远。

最直观的是二进制编码。比方说背包问题，有 $n$ 个物品，每个物品要么拿要么不拿，那就用一个长度为 $n$ 的0/1串来表示一个解，这里 $n$ 是物品总数。串里第 $i$ 位是 $1$ 就表示第 $i$ 个物品拿，$i$ 是位的编号，从 $1$ 数到 $n$，是 $0$ 就表示不拿。一条具体的串，就对应一个具体的拿法。

再有一类是实数编码，适合那种解本身就是连续数值的问题。比如你要调一组神经网络的超参，每条染色体就是一串实数，每一位存一个超参的取值，可以是学习率、隐藏层大小这些。这种编码下，染色体的每一位是一个具体的实数。

还有一类特别重要，叫排列编码，专门用在那种解的本质是一串顺序的问题上。最典型的就是旅行商问题（TSP），里面要找一条走过所有城市又回到起点的最短路线。设一共有 $n$ 座城市，$n$ 是城市总数，那么一条染色体就可以写成这 $n$ 座城市的一个排列，比如 $[3,1,4,2,5]$，表示5座城市时的一种走法。这种排列编码后面会专门讲它的交叉和变异要怎么做，因为不能随便交换，否则就变成不合法的排列了。

3.适应度函数：好坏怎么量

光把解编码成串还不够，还得能判断哪个解好哪个解差。这件事就交给适应度函数（fitness function）。它把一条染色体映射成一个数，这个数越大说明这个解越好，我们约定越大越好，越小说明越差。适应度高的个体，在接下来的选择环节里就更容易被留下来。

定义适应度要紧扣问题本身。背包问题里，适应度可以就是当前拿法下物品的总价值。TSP里正好相反，路线越短越好，可我们又要适应度越大越好，那不妨把适应度定义成总距离的倒数。设一条路线的总距离是 $D$，$D$ 是把这条排列对应的所有相邻城市间距离加起来的结果，那么适应度可以取 $f = 1/D$。这样 $D$ 越小，$f$ 越大，越容易被选中。

这里有个细节要说一下。要是某条染色体根本不合法，比如背包超重了，怎么办呢。一般有两种做法，一种是在适应度里直接加一个惩罚项，超重越多适应度扣得越多，让这种解自然被淘汰。另一种是干脆把它判成一个极低的固定适应度。我建议新手用前一种，更平滑，也保留了部分有用信息。

4.三个动作：选择、交叉、变异

有了编码和适应度，就可以开始迭代了。每一代里主要做三件事，选择、交叉、变异，有时候还加一个精英保留。

选择：好的更容易留下来

选择做的事，是从当前种群里挑出一些个体，让它们去繁殖下一代。挑选的依据就是适应度，适应度高的概率大，低的概率小，但低的不一定完全没有机会，这样保住了多样性。

最经典的是轮盘赌选择（roulette wheel selection）。想象一个轮盘，每个个体占的扇形面积和它的适应度成正比。设种群规模是 $N$，$N$ 是种群里染色体的总数，第 $i$ 个个体的适应度是 $f_i$，那么它被选中的概率就是 $P_i = f_i / \sum_{j=1}^{N} f_j$。这里 $\sum$ 是求和符号，$\sum_{j=1}^{N} f_j$ 表示从第 $1$ 个到第 $N$ 个个体的适应度全部相加，也就是当前种群的总适应度。转一下轮盘，落在哪个扇形就选哪个。适应度高的扇形大，自然更容易被点到。

轮盘赌有个毛病，要是某几个个体适应度特别高，会几乎独占整个轮盘，几代之后种群里到处都是它的后代，多样性很快就会丢失。补这个毛病常用锦标赛选择（tournament selection）。做法是每次随机抽 $k$ 个个体，$k$ 是锦标赛规模，通常取 $2$ 到 $5$，从这 $k$ 个里挑适应度最高的那个作为本次胜者。这种方法实现简单，也不那么容易被极端个体带跑。

另外还有一种补丁叫精英保留（elitism）。说白了就是每一代里，把适应度最高的那几个个体，不经过任何选择、交叉、变异，原封不动直接搬进下一代。这样做能保证到目前为止最好的解不会因为随机的运气丢掉。设精英保留数量是 $E$，$E$ 是直接搬过去的个体数，通常很小，比如 $1$ 到 $3$，剩下 $N-E$ 个名额再走常规流程。

交叉：两条染色体交换片段

交叉模拟的是生物的基因重组。从种群里挑出两条染色体当父代，按某种规则交换它们的一段，得到新的子代。

二进制编码下，最简单的叫单点交叉。设染色体长度是 $L$，$L$ 是基因的总个数，随机选一个交叉点 $c$，$c$ 是位置编号，取值在 $1$ 到 $L-1$ 之间，把第一条染色体的前 $c$ 段和第二条的后 $L-c$ 段拼起来，得到一个子代。举个例子，父代A是 $[1,0,1,1,0,0]$，父代B是 $[0,1,1,0,1,1]$，选 $c=3$，那么子代就是A的前三位拼上B的后三位，得到 $[1,0,1,0,1,1]$。

排列编码可不能这么干。TSP里要是直接交换两段，子代里可能出现同一座城市出现两次，另一座城市却没了的情形，这就不是合法的排列了。这种情况下常用顺序交叉（OX，order crossover）。做法大致是，从父代A里截一段原样保留，再从父代B里按顺序把缺的城市补进去。具体细节我就不展开了，记得有这么个东西就行，关键是要保证子代还是合法的排列。

变异：保持多样性的小动作

光交叉还不够，种群里的基因翻来覆去就那么几种，几代之后大家的染色体都长得差不多，这叫早熟收敛。这情形有点像一座孤岛上的人互相婚配太久，后代的特征都趋同了，再难出新变化。变异就是来救场的。它以一个比较小的概率 $p_m$，$p_m$ 叫变异概率，通常取 $0.001$ 到 $0.01$ 这个量级，随机改动染色体的某个基因。

二进制编码下，变异就是某一位按概率 $p_m$ 把 $0$ 翻成 $1$，或把 $1$ 翻成 $0$。排列编码下，常用的是交换变异，随机选两个位置把它们的基因对调，比如 $[3,1,4,2,5]$ 把第 $2$ 位和第 $4$ 位交换，得到 $[3,2,4,1,5]$。

变异不能太频繁，太频繁就退化成随机搜索了，可又不能完全没有，没它种群很快就会同质化，陷在一个局部最优里出不来。

5.手走几步：一个最小的例子

我们用最简单的最大化问题来手走一遍。问题是在 $0$ 到 $7$ 这八个整数里找一个 $x$，让 $f(x) = x^2$ 最大，这里 $f(x)$ 表示目标函数，$x$ 是待求的整数。显然答案是 $7$，我们看看算法能不能爬到它。

设种群规模 $N=4$，用三位二进制编码，三位能表示 $0$ 到 $7$。初始种群随机生成四条染色体，分别是 $A=101$ 也就是 $x=5$，$B=011$ 也就是 $x=3$，$C=110$ 也就是 $x=6$，$D=001$ 也就是 $x=1$。

先算适应度。$f(A)=25$，$f(B)=9$，$f(C)=36$，$f(D)=1$，总适应度是 $25+9+36+1=71$。

按轮盘赌，每个个体被选中的概率是 $P_A=25/71\approx0.35$，$P_B\approx0.13$，$P_C\approx0.51$，$P_D\approx0.01$。$C$ 的扇形最大，最容易被选中，$D$ 几乎没什么机会。

假设转四次轮盘，结果是 $C, A, B, D$。注意 $D$ 虽然概率极低，轮盘赌的随机性还是可能让它中选，这就是为什么适应度低的个体也保留了一线机会。接着随机配对做交叉，第一对是 $C$ 和 $A$，交叉点 $c=2$。$C=110$，$A=101$，子代1是 $C$ 的前两位 $11$ 拼上 $A$ 的最后一位 $1$，得到 $111$，也就是 $x=7$，适应度 $49$。你看，这一代就蹦出了全局最优。第二对是 $B$ 和 $D$，交叉点 $c=1$，子代2是 $B$ 的第一位 $0$ 拼上 $D$ 的后两位 $01$，得到 $001$，也就是 $x=1$，适应度只有 $1$。变异这一代没触发，$p_m$ 实在太小。新种群里出现了全局最优的 $111$，下一轮选择时它的高适应度会帮助它扩散开来。这只是个最小到不能再小的例子，真实问题里要迭代几百几千代，可道理是一样的。

6.整体流程串起来

把上面几节合起来，整个流程大致是这样。

第一步，初始化种群，随机生成 $N$ 条染色体。第二步，逐条评估适应度。第三步，按轮盘赌或锦标赛做选择。第四步，对选出来的个体做交叉。第五步，对新生的个体按概率 $p_m$ 做变异。第六步，如果有精英保留，把当代最好的 $E$ 条直接搬过去。第七步，看停止条件到了没有，没到就回到第二步继续。停止条件一般有三种，达到最大代数、连续若干代最优适应度没有改进、或者最优适应度达到了某个预期值。

这里要提醒一句，遗传算法是个随机算法，每次跑结果都可能不一样。判断它好不好，通常要看多次独立运行下平均收敛到多优的解，不能只看一次跑得漂亮就下结论。

7.什么场景适合用，什么场景要慎重

说到底，遗传算法适合那种解空间巨大、目标函数又没法求导的问题。TSP、车间调度、排课表、车辆路径（VRP）这类组合优化是它的拿手好戏。神经网络的超参搜索也可以用它，把每一组超参当成一条染色体，适应度取验证集上的精度，跑几代下来常常能找到一组不错的搭配。小张之前调一个模型的超参，网格搜索跑了一晚上没出结果，换成遗传算法跑了一下午，给出一组他压根没试过的搭配，验证集精度反而比他手调的还高一些。

有个挺有意思的轶事。我之前看过一本书，提到NASA有一种叫ST5的航天器，上面要装一种特殊的天线。他们没让人去画图纸，而是直接用遗传算法去演化天线的形状，结果算法给出了一份形状非常古怪、看着根本不像正常天线的设计，可它的性能偏偏出奇地好，最后真的就被送上了天。这件事我一直记得，特别能说明这类算法的价值，在人想不到的角落里，它反而能找到惊喜。

也得说清楚它的边界。遗传算法每跑一代，整个种群都要评估一次适应度，如果单次评估本身就很贵，比如要训练一次神经网络，整体代价会很可观。它对参数也比较敏感，$N$ 太小多样性不够，太大算不动，$p_m$ 太高变成随机搜索，太低又早熟。调这些参数本身就是一门经验活。

和梯度下降比，梯度下降需要目标函数可导，收敛也快，可它容易陷在局部最优里，适合连续可导的问题。和模拟退火比，模拟退火是单个解在跳来跳去找，遗传算法是一群解在并行找，种群带来的多样性让它更不容易陷死在某个坑里，代价是每一代的开销也更大。这两类元启发式算法常常是互补的，工程里也有把它们的思路混起来用的做法。

今天就先到这儿，下一章见。

练习

Q1. 遗传算法的三个核心操作"选择、交叉、变异"分别模拟生物进化的什么？为什么变异概率 $p_m$ 要取得很小？

选择模拟"适者生存"，按适应度高的概率大、低的概率小（如轮盘赌 $P_i=f_i/\sum f_j$）从当前种群挑个体繁殖；交叉模拟"基因重组"，两条父代染色体交换片段产生子代；变异模拟"基因突变"，以小概率随机改动某个基因保持多样性。$p_m$ 要取得很小（通常0.001到0.01）是因为太频繁就退化成随机搜索了，可又不能完全没有（没它种群很快同质化、早熟收敛陷在局部最优里出不来），所以是"保持多样性的小动作"，不能喧宾夺主。

Q2. 旅行商问题（TSP）用遗传算法时，适应度常定义为 $f=1/D$（$D$ 是路线总距离），交叉为什么不能直接用单点交叉？

TSP的解是一串城市排列，要求每座城市恰好出现一次。如果直接用单点交换两段，子代里可能出现同一座城市出现两次、另一座城市却没有的情形，这就不是合法排列了。所以排列编码要用专门的方法，比如顺序交叉（OX）：从父代A截一段原样保留，再从父代B按顺序把缺的城市补进去，保证子代还是合法的排列。变异也要用交换变异（随机选两个位置对调），而不是翻转某一位的0/1。

Q3. 易错点：遗传算法是不是只要跑足够多代就一定能找到全局最优解？

不能保证。遗传算法是随机算法，每次跑结果都可能不一样，它只是给了更大的机会跳出局部最优、并不能承诺一定走到全局最优——种群带来的多样性让它比单点搜索（如模拟退火）更不容易陷死，但运气不好还是会落在次优解上。判断它好不好通常要看多次独立运行下平均收敛到多优的解，不能只看一次跑得漂亮就下结论。此外它对参数（种群规模 $N$、交叉概率、变异概率 $p_m$）敏感，调这些本身就是经验活。