一、它不走路，它繁殖

先看这一节要解的题： 每一维都用同一个多峰函数 g(t) = 2·sin(6t) + cos(11t) + 0.2t，t 在 0 到 5.5 之间， 要求八个这样的东西加起来最大。 这个函数扫一遍就知道有多坑： 单维最高在 t = 3.4194，高度 3.6710，中间夹着 7 个局部峰。八维全取最高，上限就是 29.3679。 难点不在「哪一维最高」，在「八维同时都对」。每一维有 7 个峰，八维一组合， 光「都落在峰上」的角落就有 7 的 8 次方，约 576 万个。 而每一维的峰宽窄不一，一维选错，整题就废，别的维再好也白搭。 这种地形，爬山法（上一节 Dijkstra 的亲戚）一上来就完了： 它一次只动一维，动到某个局部峰就停住，再也出不来。要跳出坑， 得允许「暂时变差」——可一旦允许变差，就没有「一定收敛」的保证了。 遗传算法的回答是：不追求「一定收敛」，改追求「一群里总有一个对的」。它同时养着一批候选解， 让它们互相交换片段。这一手叫交叉，是它跟所有「单点搜索」最根本的区别。

二、把解写成一条染色体

要用遗传算法，第一步永远是编码：把「一个解」写成一串可以切、可以换的东西。这题里八个实数， 每个用 16 位二进制表示（0 到 65535 映射到 0 到 5.5），八个拼起来就是一条 128 位的染色体。 编码一确定，剩下的事都变成对字符串的操作：

三、三件套：选择、交叉、变异

三个动作各管一件事，缺一不可：

四、同样的预算，三种找法比一次

评价次数是这类算法唯一公平的尺子—— 大家都不许多算。这里给 4040 次（40 条初始 + 100 代乘 40 条），三种办法各跑 20 次：

五、两个旋钮：变异率和选择压力

变异率是每个位翻转的概率。128 个位，0.02 意味着每条子代平均翻 2.6 位。 扫一遍就看见一个中间高、两头低的坡：

六、它该用在哪，不该用在哪

该用的场景有三个共同点：目标函数是黑箱（只能算值、不能求导）、地形多峰（局部最优一大堆）、 解的编码能自然地切成片段。芯片布线、天线形状设计、调度排班、超参数搜索，都在这个范围里。 不该用的场景也很明确：能求导的时候别用它——梯度下降一步能顶它几十代； 解只有一个最优峰（比如线性回归）的时候别用它——正规方程一行算完，比它准得多； 参数上百万的时候别用它——靠变异去碰，碰不出来。 最后这一点解释了它在深度学习里的位置：它是个配角。调神经网络权重的主力是梯度下降（下一节）， 遗传算法顶多用来搜超参数（层数、学习率这类「没法求导」的东西）。 一个网络几百万个权重，靠交叉变异去凑，凑到天荒地老也凑不出来。 所以这一节真正要带走的，不是「有个算法叫遗传算法」，而是那句更普遍的话： 求解的方法取决于「你能拿到什么」。能求导就用梯度，能穷举就用搜索， 什么都拿不到就撒点、繁殖、试错。

七、动手 Demo：八个维度上找一个最高点

核心只有四步：解码、选择、交叉、变异。代码里的 ga 函数从头到尾不到 25 行， 每一代就是「挑父母、切一刀拼起来、翻几个位、和父母一起排队取前 40」。 注意最后一步（精英保留）：父母和子代放在一起排，只留最好的 40 条。 少了这一句，「这代最高」那条曲线会上下抖；加上它，曲线就只会往上走。

BITS, DIM, HI = 16, 8, 5.5                  # 每维 16 位，8 维，取值 0 到 5.5
NB = BITS * DIM                            # 一条染色体 128 位

def g(t):                                  # 每一维都是这个多峰函数
    return 2 * np.sin(6 * t) + np.cos(11 * t) + 0.2 * t

def decode(pop):                           # 128 位 -> 8 个实数
    q = pop.reshape(len(pop), DIM, BITS)
    return q.dot(W) / float(2 ** BITS - 1) * HI

def tournament(fit, k, rng):               # 选择：抓 k 条，最强的当父母
    idx = rng.integers(0, len(fit), (len(fit), k))
    return idx[np.arange(len(fit)), fit[idx].argmax(axis=1)]

def ga(pm=0.02, tk=2, seed=0, gens=100):
    rng = np.random.default_rng(seed)
    pop = rng.integers(0, 2, (POP, NB)).astype(np.int8)
    fit = g(decode(pop)).sum(1)
    for gg in range(gens):
        par = pop[tournament(fit, tk, rng)]        # 挑父母
        kid = par.copy()                            # 交叉：单点切
        cuts = rng.integers(1, NB, POP // 2)
        for i in range(POP // 2):
            c = cuts[i]
            kid[2 * i, c:] = par[2 * i + 1, c:]
            kid[2 * i + 1, c:] = par[2 * i, c:]
        kid ^= (rng.random((POP, NB)) < pm).astype(np.int8)   # 变异
        allp = np.vstack([pop, kid])                # 父母和子代一起排队
        allf = np.concatenate([fit, g(decode(kid)).sum(1)])
        keep = np.argsort(-allf)[:POP]              # 精英保留：只留最好的
        pop, fit = allp[keep], allf[keep]
    return float(fit.max())

实跑输出：

--------------------------------------------------------------------
八个维度上找一个最高点
--------------------------------------------------------------------
==============================================================

[1] 先说这道题有多难

  每一维都用同一个函数：g(t) = 2·sin(6t) + cos(11t) + 0.2t，t 在 0 到 5.5 之间。
  它长这样（横轴是 t，越高的行就是函数值越大的地方）：


                          ##         ##         ##         
               ##         ###        ##        ###        #
     ##        ###        ###       ####       ####    ####
    ######     ####      ####       ####      #####    ####
    #######   ########   #####     ######  ########   #####
    #######   ########   ################ ########## ######
    ########  ######### ###################################
    #######################################################

  四十万个点扫一遍：单维最高在 t = 3.4194，高度 3.6710，中间有 7 个局部峰。

  题目要最大的是八个这样的东西加起来：
  F = g(x1) + g(x2) + … + g(x8)，每一维都在 0 到 5.5 里自己挑。
  八维全取最高，理论上限就是 29.3679，这就是全局最优。

  可它难在：每一维有 7 个局部峰，八个维度一组合，光「都落在峰上」的角落
  就有 7 的 8 次方，约 576 万个。**从哪儿出发，决定你能爬到哪个峰。**
  而且每一维的峰宽窄不一，**一维选错，整题就废了**，别的维再好也白搭。

[2] 遗传算法的三件套：编码、适应度、繁衍

  一条染色体是 8 乘 16 等于 128 个 0 或 1。
  每 16 位切成一段，当成一个 16 位整数，按比例映射到 0 到 5.5——这叫解码。
  于是**一条染色体就是八个候选值打包在一起**，适应度就是这八个值的 F。

  繁衍分三步：

    步骤      做什么                            作用
    ----------------------------------------------------
    选择      按适应度挑父母，越好的越多子嗣    往好里收
    交叉      父母各切一刀，前后两段拼接        把好片段凑到一起
    变异      个别位按小概率翻转                往散里搅

  **一收一散，才不至于一头扎进某个坑。**这是它跟爬山法最根本的区别：
  爬山法只走「下坡的反方向」，遗传算法敢同时保留一批差得远的候选。

  **交叉这一步是关键。**在八维的题上，A 可能第一维选对了，B 可能第三维选对了，
  交叉能把这两段拼到一条染色体上——**这就是它比爬山法强的地方。**

[3] 跑一百代，看它怎么往上爬

    代数    这代最高      种群差异（位）
    ----------------------------------------
    0       16.8414       64.0 / 128
    20      26.4482       13.5 / 128
    40      27.4798       11.0 / 128
    60      27.5310       8.6 / 128
    80      27.5427       5.1 / 128
    100     27.5446       4.2 / 128

  第 0 代那 40 条是瞎掷的，最高只有 16.8414；跑了 100 代，爬到 27.5446。
  右边一列是「随便挑两条染色体，平均有多少位不一样」：
  开局 64.0 位（一半位都不同，等于随机），到第 100 代只剩 4.2 位。
  **种群在往一处收，这叫收敛；收得太早，就叫早熟。**

  顺带看清一件事：爬到 27.5446 不等于爬到了 29.3679。
  差的这 1.82 就是它没找对的那一两个维度——**八维的题，容错很小。**

[4] 跟另外两种找法比：同样的评价次数

  遗传算法一共算了 4040 次 F（40 条初始 + 100 代乘 40 条）。
  另外两种也给 4040 次，各重复 20 次，看成绩分布。全局是 29.3679。

    找法        二十次平均    最好一次      最差一次
    ----------------------------------------------------
    随机撒点    20.1043       22.2477       18.4111
    爬山法      23.9371       27.0593       20.1440
    遗传算法    27.9469       28.9040       25.2516

  **随机撒点最惨**：4040 个点在八维空间里太稀疏，撒中一个峰都难，
  它的成绩基本上就是「随便抱八个值加起来」，跟求解没关系。
  爬山法好一些，可它一次只动一维，**动到某个局部峰就停了**，
  八维全停在最高峰的概率极低。
  遗传算法靠交叉把各维的好片段拼起来，平均水平高出 4 以上。

[5] 变异率这个旋钮

  变异率是每个位翻转的概率。128 个位，0.02 意味着每条子代平均翻 2.6 位。
  太小，种群很快一个模样，跳不出坑；太大，好不容易拼好的组合又被搅碎。

    变异率    每代翻几位    二十次平均    最好一次
    --------------------------------------------------
    0.001     0.1           26.6638       28.4686
    0.005     0.6           27.2079       28.5846
    0.020     2.6           27.9469       28.9040
    0.050     6.4           28.2163       29.1405
    0.100     12.8          26.6351       28.2161
    0.300     38.4          21.0329       23.6584

  这张表是个中间高、两头低的坡：0.001 翻不到一位，几乎只剩交叉；
  0.3 每条子代平均翻 38 位，等于把父母拆了重掷，跟随机撒点没两样。
  **最好的一档在 0.05 附近**，也就是每条子代翻 6 位上下。
  这个数不能算出来，只能扫出来。遗传算法有一半工夫花在这种试参上。

[6] 另一个旋钮：选择有多狠

  选择用锦标赛：随机抓 k 条，让最强的那条当父母。k 越大，压力越狠。

    锦标赛大小    二十次平均    最好一次      末代差异
    ------------------------------------------------------
    1             28.5761       29.2512       9.1 位
    2             27.9469       28.9040       4.2 位
    4             27.9039       28.9417       5.6 位
    8             27.7918       28.8837       2.5 位

  **能确定的是右边那一列：压力越大，剩下的差异越小**（9.1 位降到 2.5 位）。
  差异没了，交叉就拼不出新花样，**只剩变异在瞎碰，这叫早熟。**

  但左边那一列并不按 k 单调：这里 k=1 反而略好，k=8 最差。
  原因是这道题的八个维度互不相干，而这里又留了精英不淘汰，
  **只要把最好的那几条留住，父母随便抓也够用。**
  换个维度之间有牵连的题，结论就会翻过来。
  **选择压力没有「越大越好」这回事，它得跟问题配。**

[7] 这一节要知道的三件事

  一、**遗传算法不发愁「地形」，只发愁「怎么编码」。**
  这题编码是 128 个 0/1，简单；换成「排一条送货路线」，
  编码就成了一个排列，交叉和变异都得重写，不然拼出来的路线根本走不通。

  二、**它给的是「够好」，不是「最好」。**
  二十次里最好的一次 28.9040，离 29.3679 仍差 0.46，而且它给不出最优性证明。
  换来的是：不用求导、不用连续、函数黑箱也能试。

  三、**在深度学习里它只是个配角。**
  调神经网络权重的主力是梯度下降，遗传算法顶多用来搜超参数
  （层数、学习率这类「没法求导」的东西）。原因很直白：
  一个网络几百万个参数，靠交叉变异去碰，碰不出来。

第一段那个 ASCII 图不是装饰。它让你看见「坑有多密」：七个峰挤在一段区间里， 峰与峰之间的谷也不算深——这正是爬山法最怕的形状。 第二段那张进化表要看两列。左边那列从 16.84 爬到 27.54，说明确实在学； 右边那列从 64.0 位掉到 4.2 位，说明种群在往一处收。 这两件事是同一件事的两面：收得越紧，进步越慢。第 40 代到第 100 代，左边只涨了 0.06， 右边却从 11.0 掉到 4.2——后半程基本是在原地磨。 第四段那张三种找法的表，关键在「同预算」三个字。如果给随机撒点更多次数， 它也能摸到 28 以上——但那不叫「会找」，叫「钱多」。 评价次数是这类算法唯一公平的尺子，比「跑了多久」公平得多，因为它跟机器快慢无关。 第五段那张变异率的表值得记形状，不是记数字。中间高、两头低，而且两头低的原因完全不同： 小的一端是「没新东西」，大的一端是「全是新东西」。 这个形状在几乎所有「探索与利用」的取舍里都会出现——模拟退火里的温度、强化学习里的探索率， 都是同一个坡。 最后一段那张锦标赛的表，最该记的是「左边不单调、右边单调」。右边（种群差异）随压力单调下降， 这是数学上必然的；左边（成绩）不单调，因为它还取决于问题本身可不可拆。 遇到「某个参数越大越好」的说法，先问一句「在什么问题上」。

30 秒实验

1. 把 POP 从 40 改成 10，重跑第四段。 总评价次数不变（要相应把代数调成 400），但种群太小，交叉能提供的组合少，成绩应该会掉。 这说明「种群大小」和「代数」之间也有个平衡，不是越多越好。
2. 把 HI 从 5.5 改成 2.0（只在一小段区间里找），重跑。 局部峰变少，随机撒点会突然变得很强，遗传算法的优势会被压扁。这一步说明： 遗传算法的优势来自「地形坑」，地形平了它就没戏。
3. 在 ga 里把交叉整段删掉（只留选择和变异），重跑第四段。 成绩会掉到接近爬山法的水平——四十条染色体变成四十个各自乱爬的个体。 这是验证「交叉才是关键」最直接的一步。

常见误区

1. 以为遗传算法是「模拟生物进化」，所以更「自然」所以更强。它借的只是「选择＋重组」这个框架， 跟生物没有半点关系：这里的基因是二进制位，适应度是一个算出来的数， 而且它没有「物种」「种群隔离」「基因连锁」这些真实机制。
2. 以为跑得越久结果越好。Demo 里第 40 代到第 100 代只涨了 0.06， 而种群差异已经掉到 5 位——再跑下去只是在同一个局部峰上磨。 早熟一旦发生，加代数救不回来，只能改参数或者重跑。
3. 以为它一定能找到全局最优。它没有任何最优性保证。能保证最优的是穷举和（可采纳的）A； 遗传算法给的是「多次跑里挑最好」，而且必须诚实地说「这是二十次里最好的一次」。*
4. 以为「变异率越高探索能力越强」。0.3 那一行只有 21.03， 跟随机撒点一个水平——探索过头等于没学。 探索和利用之间永远是个取舍，没有「越多越好」的选项。

这一节讲的是「怎么在没有坡度的地方找路」。 下一节反过来：如果能算出一个坡度，就顺着坡度走——这就是神经网络训练的全部内容。而它的本事， 全在「中间那一层怎么弯」。

• ☐ （本节完，下一节 5.4 神经网络）

相关笔记

• 图谱搜索和最优化
• 神经网络
• 线性问题和非线性问题
• 📘 图解人工智能 · 索引