从算法到人工智能 · 第 21 课：遗传算法——让一群解"进化"出最优解

上一课模拟退火是单解型：一个解自己爬山，靠"温度"允许偶尔退一步。这一课换一条完全不同的思路——种群型：不放一个解，放一群解，让它们像生物一样选择、交叉、变异，一代一代演化，逼近最优。这就是遗传算法（Genetic Algorithm, GA）。

它的灵感来自达尔文的自然选择：一个种群里的个体有好有坏，环境压力会淘汰差的、留下好的；好个体之间"交配"产生后代，后代还可能发生微小"变异"。反复很多代之后，种群整体会越来越适应环境。

一、进化靠三步

生物的进化，拆开看就三个机制：

这三步循环往复：选择 → 交叉 → 变异 → 得到新一代 → 再来。每一代都朝着"适应度更高"的方向偏一点，几十上百代之后，种群里就冒出了接近最优的个体。

二、遗传算法的五个零件

要把一个"求最优解"的问题翻译成"进化"，得先准备五样东西：

1. 编码（Encoding）——把一个解表示成一串"基因"（染色体）。最经典的是二进制编码：一个解 = 一串 0/1。
2. 适应度函数（Fitness）——给每个个体打个分，衡量它"多好"。我们要最大化的那个目标，往往就是适应度。
3. 选择算子（Selection）——按适应度高低挑父母。常用轮盘赌：适应度占比越大，被选中概率越大。
4. 交叉算子（Crossover）——两个父母各取一段，拼出孩子。
5. 变异算子（Mutation）——对孩子的基因位做小概率翻转，防止种群"僵化"。

准备好这五样，遗传算法就能跑起来了。

三、完整实现：求 f(x) = x² 的最大值

先用一个最简单的问题热身：在 0 到 31 之间，哪个整数让 x² 最大？ 答案显然是人人都知道的 31。但遗传算法不知道答案，它要自己"进化"出来——这正好能让我们看清它的运作过程。

第一步：编码。 0~31 一共 32 个数，用 5 位二进制刚好装下（11111 = 31）。所以一个个体就是 5 位 0/1 串，例如 10110 表示 22。

import random

def decode(chrom):
    """把 0/1 串解码成整数：二进制 → 十进制"""
    return int(''.join(map(str, chrom)), 2)

def fitness(chrom):
    """适应度 = x²，我们想最大化它"""
    x = decode(chrom)
    return x * x

第二步：选择（轮盘赌）。 每个个体被选中的概率，正比于它的适应度——适应度越高，占的"扇形"越大：

轮盘赌的前提：适应度必须非负（本例 x² 天然满足）。如果目标函数可能取负值，先整体平移成正数（比如都加上一个足够大的常数），否则"占比"会出问题、选择会失效。

def roulette_select(pop, fits):
    """轮盘赌选择：适应度越高的个体，越容易被选中"""
    total = sum(fits)
    r = random.random() * total          # 转盘转到哪
    acc = 0
    for ind, f in zip(pop, fits):
        acc += f
        if acc >= r:                     # 累积到 r，就选它
            return ind[:]
    return pop[-1][:]                    # 理论上不会到这，兜底

第三步：交叉（单点交叉）。 两个父母各切一刀，交换后半段：

def crossover(a, b, rate=0.8):
    """单点交叉：随机切一刀，交换两个父母的后半段"""
    if random.random() < rate:
        point = random.randint(1, len(a) - 1)
        return a[:point] + b[point:], b[:point] + a[point:]
    return a[:], b[:]                    # 没触发交叉，原样复制

第四步：变异。 每个基因位以一个小概率翻转 0↔1：

def mutate(chrom, rate=0.01):
    """逐位变异：每个基因位以 rate 的概率翻转"""
    return [1 - g if random.random() < rate else g for g in chrom]

第五步：主循环。 把四步串起来，迭代很多代：

def genetic_algorithm(pop_size=8, chrom_len=5, gens=30,
                      cross_rate=0.8, mut_rate=0.01):
    # 1. 初始化：随机生成一群个体
    pop = [[random.randint(0, 1) for _ in range(chrom_len)]
           for _ in range(pop_size)]
    best = max(pop, key=fitness)         # 精英保留：当前最优先记住

    for _ in range(gens):
        fits = [fitness(ind) for ind in pop]
        new_pop = [best[:]]              # 最优个体直接进下一代
        while len(new_pop) < pop_size:
            a = roulette_select(pop, fits)   # 选父母
            b = roulette_select(pop, fits)
            c1, c2 = crossover(a, b, cross_rate)   # 交叉
            new_pop += [mutate(c1, mut_rate),      # 变异
                        mutate(c2, mut_rate)]
        pop = new_pop[:pop_size]         # 新一代接管
        best = max(pop, key=fitness)     # 更新最优

    return decode(best), fitness(best)

random.seed(1)
x, v = genetic_algorithm()
print(f"进化出的最优解 x={x}, f(x)={v}")

运行结果基本是 x=31, f(x)=961——遗传算法自己找到了最大值，尽管它从没见过"31 这个数最大"这条规则。

关于最小化：这个例子求的是"最大化"。如果你要的是最小化 f(x)，把它当成"最大化 -f(x)"即可——两者完全等价。所以遗传算法虽然嘴上总说"适应度越高越好"，实际对最小化问题同样适用。

四、逐行拆解：为什么它能"变好"

遗传算法能收敛，靠的是这三个算子的合力：

• 选择给了方向：适应度高的个体（x 更大）更常被选作父母，差的个体慢慢被淘汰。种群的平均水平一代比一代高。
• 交叉负责"重组优势"：两个还不错的个体各取一段，有机会拼出更好的孩子。比如 11100 和 00111 交叉，可能生出 11111（=31）这个满分个体。
• 变异负责"探索新花样"：如果种群过早陷入同一个模式，变异能翻出新的组合，给进化注入新鲜血液。

三者缺一不可：只选不交叉，种群会很快趋同、失去多样性；只交叉不变异，初始种群没有的基因（比如某一位永远是 1）就永远出现不了；没有选择，则纯靠运气乱撞，退化成了纯随机搜索。

五、关键参数：几个旋钮怎么调

遗传算法有几个参数，直接决定它"进化得快不快、稳不稳"：

终止条件：上面的实现是"固定跑 gens 代"就停，简单直观。工程上更常用收敛检测——记录每一代的最优适应度，若连续 N 代（比如 20 代）都没有再提升，就提前停止，省时间。稳妥的做法是两者结合：设一个最大代数兜底，再用收敛检测提前退出。

一个常见误区：变异率设太大。变异率一大，每代都乱翻一堆基因，好不容易进化出的好个体被破坏掉，算法就退化成"随机撒点"。变异是"小调味料"，不是"主菜"。

六、模拟退火 vs 遗传算法

上一课的模拟退火和这一课的遗传算法，是元启发算法的两大流派，正好对照：

两者没有绝对优劣，看问题形态。遗传算法的优势在于并行探索——一群解同时从解空间的不同角落出发，天生不容易全挤进同一个坑里。

七、小结

1. 遗传算法把"求最优"翻译成"进化"：编码→适应度→选择→交叉→变异，一代代迭代。
2. 选择定方向、交叉重组优势、变异注入多样性，三者合力才能既快又稳地逼近最优。
3. 它是"种群型"元启发，和模拟退火（单解型）互补，特别适合离散的组合优化问题。

八、动手实验

1. 看进化过程：在 genetic_algorithm 循环里，每一代打印 best 的适应度，观察它是不是"单调上升、偶有平台"。把 mut_rate 改成 0，再看会发生什么（种群是不是很快僵化、找不到 31？）。
2. 改目标函数：把 fitness 改成求 f(x) = 5x - x² 的最大值（真值在 x≈2.5，但 x 是整数，最优是 2 或 3）。只改 fitness 一行，看遗传算法能不能自动找到新答案——体会一下"换个问题，只需换适应度函数"。
3. 试试更难的问题：把编码扩到 8 位（0~255），求 f(x) = x · sin(x) 的最大值（真值约在 x≈221）。观察：解空间变大了，同样的 30 代还够不够？要不要加大种群或代数？