📚 课程目录第4章遗传算法

4. 遗传算法：生物进化启发

遗传算法，说白了就是跟大自然学优化。你想想看，生物进化了几亿年，把各种奇形怪状的物种都折腾出来了，那套「优胜劣汰、适者生存」的机制，用在求解优化问题上，效果出奇的好。

我第一次接触遗传算法是在一个排产项目里。传统方法算到天荒地老，结果还不一定好。后来我试着用遗传算法去跑，嘿，十几代下来就找到了不错的解。嗯，从那以后我就把这套方法当成了工具箱里的常备武器。

  核心思想：模拟自然选择与遗传机制，通过种群迭代搜索最优解。

4.1 编码方式：怎么把解变成「染色体」

遗传算法不能直接处理问题的解，得先把解「编码」成一条染色体。编码方式选得好不好，直接影响算法的效率和精度。

4.1.1 二进制编码

最经典的方式。把每个变量用一串二进制位表示，然后拼起来就是一条染色体。

# 假设变量 x 范围 [0, 10]，精度 0.01
# 需要 10 位二进制（2^10 = 1024 个离散值）
x = 3.14 → 二进制：0100111001

优点：交叉、变异操作简单直观，理论分析成熟
缺点：连续变量离散化会损失精度，长染色体导致搜索空间爆炸

我的经验：二进制编码适合组合优化问题，比如背包问题、路径规划。连续优化我一般不用它，精度控制太麻烦。

4.1.2 实数编码

直接用浮点数表示变量，一条染色体就是一个向量。

# 三维优化问题
染色体 = [3.14, 2.71, 1.41]  # 直接就是实数向量

优点：精度高，适合连续优化，搜索效率高
缺点：交叉变异算子需要专门设计

注意：实数编码的变异算子不能随便乱改，否则可能产生无效解。我曾经吃过这个亏，变异后变量跑出边界，结果迭代了十几代才发现。

4.2 选择算子：谁有资格「传宗接代」

选择算子的作用，就是从当前种群里挑出「优秀个体」作为父代。挑得好，算法收敛快；挑得不好，容易早熟或者原地踏步。

4.2.1 轮盘赌选择

每个个体被选中的概率跟它的适应度成正比。适应度越高，轮盘上的扇形就越大。

# 伪代码
total_fitness = sum(fitness)
for each individual:
    prob = fitness[i] / total_fitness
    # 随机转轮盘，落在哪个扇区就选谁

优点：实现简单，符合自然选择直觉
缺点：适应度差异大时，容易过早收敛；差异小时，搜索效率低

4.2.2 锦标赛选择

随机挑 k 个个体，从中选最好的那个。重复直到选够父代数量。

# 锦标赛选择（k=3）
def tournament_selection(population, k=3):
    candidates = random.sample(population, k)
    return max(candidates, key=lambda ind: ind.fitness)

优点：控制选择压力，避免早熟，实现简单
缺点：k 值需要调参，太大容易丢失多样性

我建议：一般用锦标赛选择，k 取 2 或 3。轮盘赌在适应度差异大的时候容易出问题，我踩过坑。

4.3 交叉算子：基因重组

交叉是遗传算法产生新个体的主要手段。两个父代染色体交换部分基因，生成子代。

4.3.1 单点交叉

随机选一个交叉点，交换点之后的部分。

父代1: 1010|0110
父代2: 1101|1001
交叉后:
子代1: 1010|1001
子代2: 1101|0110

4.3.2 多点交叉

随机选多个交叉点，分段交换。

父代1: 10|10|01|10
父代2: 11|01|10|01
交叉后:
子代1: 10|01|01|01
子代2: 11|10|10|10

4.3.3 均匀交叉

每个基因位独立决定来自哪个父代，通常用掩码控制。

掩码:   1 0 1 0 1 0 1 0
父代1:  1 0 1 0 0 1 1 0
父代2:  1 1 0 1 1 0 0 1
子代:   1 1 1 1 0 0 1 1  # 掩码为1取父代1，为0取父代2

交叉方式	特点	适用场景
单点交叉	破坏性小，保留基因块	二进制编码，组合优化
多点交叉	破坏性中等，搜索能力强	长染色体，需要探索
均匀交叉	破坏性最大，随机性强	实数编码，连续优化

避坑指南：我曾经在实数编码上用单点交叉，结果子代全是父代的简单拼接，效果很差。后来换成均匀交叉，配合算术重组，收敛速度明显提升。

4.4 变异算子：引入新基因

变异是为了保持种群多样性，防止算法陷入局部最优。变异概率一般设得很低，通常在 0.01~0.1 之间。

4.4.1 二进制变异

随机翻转某些基因位：0 变 1，1 变 0。

变异前: 10100110
变异后: 10110110  # 第4位翻转

4.4.2 实数变异

给某个基因加上一个随机扰动，通常服从高斯分布或均匀分布。

# 高斯变异
x_new = x_old + N(0, sigma)
# sigma 控制变异幅度，一般取变量范围的 1/10

我的习惯：变异概率我一般设 0.05 左右。太高了算法变成随机搜索，太低了容易早熟。sigma 我取变量范围的 5%~10%，效果比较稳定。

4.5 遗传算法完整流程

把上面这些算子串起来，就是一个完整的遗传算法流程。我画了张图，方便你理解整体结构。

  流程总结：初始化 → 评估 → 判断终止 → 选择 → 交叉 → 变异 → 回到评估，直到满足终止条件。

4.6 参数调优建议

遗传算法的参数调起来挺玄学的。我整理了一份常用参数范围，你可以作为起点。

参数	推荐范围	我的经验
种群大小	50~200	问题复杂就取大一点，简单问题50就够了
交叉概率	0.6~0.9	我一般设0.8，效果比较均衡
变异概率	0.01~0.1	0.05是个不错的起点
锦标赛k值	2~5	k=3最常用，压力适中
最大迭代次数	100~1000	看问题复杂度，先设200试试

注意：参数不是固定的。我建议你先用默认参数跑一遍，观察收敛曲线，再根据情况调整。别一上来就调参，容易调出幻觉。

遗传算法的魅力在于它的灵活性和鲁棒性。编码方式、选择算子、交叉变异算子，每个环节都可以根据具体问题定制。你想想看，这种「搭积木」式的设计思路，是不是比那些黑箱优化器有意思多了？