4. 遗传算法：生物进化启发、编码方式、选择/交叉/变异算子

遗传算法（GA），说白了就是跟大自然偷师。你想想看，生物进化几亿年，搞出了人类这么复杂的系统，那套「优胜劣汰、适者生存」的逻辑，搬到计算机里能不能解决优化问题？

答案是肯定的。我最早接触 GA 是在做物流路径规划的时候，传统梯度方法根本搞不定那种离散、多约束的组合爆炸。后来试着用 GA 去跑，虽然收敛慢了点，但每次都能给出一个「够用」的解。嗯，这就是它的魅力——不求最优，但求可行。

4.1 生物进化与算法映射

我们先看一张图，把生物进化的概念和算法里的组件对应起来：

这张图我每次讲课都会放。核心就一句话：把问题的解编码成「染色体」，然后让它们像生物一样繁殖、变异、竞争。你不需要知道目标函数的梯度，甚至不需要函数是连续的——只要你能算出「谁更好」，GA 就能帮你找下去。

4.2 编码方式：怎么把解变成染色体？

编码是 GA 的第一步，也是最容易被忽视的一步。我见过不少新手，上来就用二进制编码，结果解空间大得离谱，跑了一晚上都没收敛。

常见的编码方式有三种：

4.3 选择算子：谁有资格繁衍？

选择算子的目的很直接：让好的解有更大机会留下后代。但「好」的标准怎么定？

最经典的是轮盘赌选择——适应度越高，被选中的概率越大。但这里有个坑：如果种群中某个个体的适应度远高于其他，它会迅速占据整个种群，导致早熟收敛。

我个人更常用的是锦标赛选择：每次随机挑 k 个个体，选最好的那个进入下一代。k 一般取 2 或 3。这样做的好处是，选择压力可控，而且实现简单。

def tournament_selection(population, fitness, k=3):
    selected = []
    for _ in range(len(population)):
        # 随机挑 k 个
        candidates = random.sample(range(len(population)), k)
        # 选适应度最高的
        best = max(candidates, key=lambda i: fitness[i])
        selected.append(population[best])
    return selected

4.4 交叉算子：基因重组

交叉是 GA 的核心搜索操作。说白了，就是把两个父代的染色体「切一刀」然后交换。

对于二进制编码，单点交叉是最直观的：

父代1: 101|10101
父代2: 010|01010
子代1: 101|01010
子代2: 010|10101

但实数编码就不能这么干了。我常用的方法是模拟二进制交叉（SBX），它能在实数空间里模拟二进制交叉的分布特性：

def sbx(parent1, parent2, eta=15):
    # eta 控制分布指数，越大子代越接近父代
    u = random.random()
    if u <= 0.5:
        beta = (2 * u) ** (1 / (eta + 1))
    else:
        beta = (1 / (2 * (1 - u))) ** (1 / (eta + 1))
    child1 = 0.5 * ((1 + beta) * parent1 + (1 - beta) * parent2)
    child2 = 0.5 * ((1 - beta) * parent1 + (1 + beta) * parent2)
    return child1, child2

嗯，这里要注意：交叉概率一般设 0.7~0.9。太高了会破坏优秀解，太低了搜索效率又不够。

4.5 变异算子：保持多样性

变异是 GA 的「保险丝」。没有变异，种群会迅速失去多样性，最后困在局部最优里出不来。

二进制编码的变异很简单——按位翻转：

def bit_flip_mutation(chromosome, pm=0.01):
    # pm 是每位变异的概率
    mutated = []
    for gene in chromosome:
        if random.random() < pm:
            mutated.append(1 - gene)
        else:
            mutated.append(gene)
    return mutated

实数编码的变异，我推荐多项式变异，它和 SBX 是配套的：

def polynomial_mutation(individual, pm=0.1, eta_m=20):
    mutated = individual.copy()
    for i in range(len(mutated)):
        if random.random() < pm:
            u = random.random()
            if u < 0.5:
                delta = (2 * u) ** (1 / (eta_m + 1)) - 1
            else:
                delta = 1 - (2 * (1 - u)) ** (1 / (eta_m + 1))
            mutated[i] += delta
    return mutated

4.6 完整流程：从编码到收敛

把上面这些串起来，一个标准的 GA 流程是这样的：

1. 初始化：随机生成 N 个个体（候选解）
2. 评估：计算每个个体的适应度
3. 选择：用锦标赛或轮盘赌选出父代
4. 交叉：按概率 Pc 对父代进行交叉，生成子代
5. 变异：按概率 Pm 对子代进行变异
6. 替换：用子代替换部分或全部父代，形成新种群
7. 终止判断：达到最大代数或适应度不再提升则停止，否则回到步骤 2

这个流程看起来简单，但实际调参的时候坑不少。我总结了一个参数速查表：