4. 遗传算法：生物进化启发、编码方式、选择、交叉、变异操作、算法流程、代码实现
遗传算法，说白了就是跟大自然学优化。你想想看，生物进化了几亿年，把各种奇形怪状的物种都折腾出来了，这背后不就是个全局优化过程吗？我当年第一次接触这个算法时，觉得它特别「浪漫」——把一群候选解扔进「环境」里，让它们自己竞争、交配、变异，最后活下来的就是最优解。
嗯，咱们不扯虚的，直接上干货。
4.1 核心思想：适者生存
遗传算法（Genetic Algorithm, GA）的核心逻辑就四个字：适者生存。我们把问题的候选解编码成「染色体」，然后模拟自然选择的过程：
- 种群：一组候选解的集合
- 适应度：评价解好坏的指标
- 选择：适应度高的个体有更大机会繁衍后代
- 交叉：两个父代交换基因片段，产生新个体
- 变异：随机改变某些基因，保持种群多样性
我在项目中遇到过不少新手，一上来就调参数，结果算法要么早熟收敛，要么根本找不到好解。其实，理解清楚编码方式和算子设计，比调参数重要得多。
关键认知：遗传算法不保证找到全局最优，但它能在巨大的搜索空间里，以较大概率找到「足够好」的解。这就是它的实用价值。
4.2 编码方式：怎么把解变成染色体？
编码是遗传算法的第一步，也是最容易被忽视的一步。我个人习惯把编码方式分为三类：
| 编码方式 | 适用场景 | 优点 | 缺点 |
|---|---|---|---|
| 二进制编码 | 离散优化、函数优化 | 操作简单，理论成熟 | 精度受位数限制，连续问题效率低 |
| 实数编码 | 连续参数优化 | 精度高，无需编解码 | 交叉变异算子需特殊设计 |
| 排列编码 | TSP、调度问题 | 天然满足排列约束 | 交叉操作复杂 |
举个例子，假设我们要优化一个函数 f(x) = x²，x 的范围是 [0, 31]。用二进制编码，5位二进制数就能表示 0~31 的所有整数。染色体 10110 对应 x=22，适应度就是 484。
我的建议：对于连续优化问题，优先用实数编码。二进制编码虽然经典，但精度和搜索效率往往不如实数编码。我曾经在一个工程优化项目里，从二进制换成实数编码后，收敛速度直接翻了一倍。
4.3 选择操作：谁有资格繁衍？
选择操作决定了哪些个体能成为「父母」。常用的方法有：
- 轮盘赌选择：适应度越高，被选中的概率越大。但有个问题——如果某个个体适应度特别高，它很快会主导整个种群，导致早熟。
- 锦标赛选择：随机挑 k 个个体，选其中最好的。我比较喜欢这种方法，因为它能控制选择压力。
- 精英保留：直接把当前最优的几个个体复制到下一代，保证不丢失好解。
为什么会早熟？说白了就是种群多样性丢失得太快。我建议你至少保留 1~2 个精英个体，同时用锦标赛选择来控制选择压力。
4.4 交叉操作：基因重组
交叉是遗传算法产生新解的主要手段。不同的编码方式，交叉算子也不同：
- 单点交叉：随机选一个交叉点，交换两个父代的后半段基因
- 两点交叉：选两个交叉点，交换中间片段
- 均匀交叉：每个基因位以 0.5 的概率决定是否交换
- 算术交叉（实数编码）：子代 = α × 父代1 + (1-α) × 父代2
交叉概率一般设置在 0.6~0.9 之间。太高了会破坏好基因，太低了搜索效率又不够。
4.5 变异操作：保持多样性
变异是防止算法陷入局部最优的关键。对于二进制编码，就是按概率翻转某些位；对于实数编码，可以加上一个随机扰动。
变异概率通常很小，0.01~0.1 就够。我曾经犯过一个错误——把变异概率设到 0.3，结果算法变成了随机搜索，根本收敛不了。嗯，这里要注意：变异是「辅助」手段，不是主力。
避坑指南：我曾经在一个多峰函数优化问题中，发现算法总是收敛到同一个局部最优。排查了半天，原来是变异概率太低，种群多样性不够。把变异概率从 0.01 调到 0.05 后，问题就解决了。
4.6 算法流程
遗传算法的标准流程其实很简单，我画了一张图帮你理解：
流程其实就这几步：初始化 → 计算适应度 → 判断终止 → 选择 → 交叉 → 变异 → 回到适应度计算。终止条件可以是最大代数、适应度阈值，或者连续几代没有改进。
4.7 代码实现：手写一个简单的遗传算法
光说不练假把式。咱们用 Python 实现一个求解 f(x) = x² 最大值的遗传算法，x 范围 [0, 31]，二进制编码，5位染色体。
import random
# 参数设置
POP_SIZE = 10 # 种群大小
CHROM_LEN = 5 # 染色体长度
MAX_GEN = 50 # 最大代数
CROSS_RATE = 0.8 # 交叉概率
MUTATE_RATE = 0.05 # 变异概率
def decode(chrom):
"""二进制转十进制"""
return int(''.join(map(str, chrom)), 2)
def fitness(x):
"""适应度函数"""
return x * x
def init_population():
"""初始化种群"""
return [[random.randint(0, 1) for _ in range(CHROM_LEN)] for _ in range(POP_SIZE)]
def select(pop, fits):
"""轮盘赌选择"""
total = sum(fits)
pick = random.uniform(0, total)
current = 0
for i, f in enumerate(fits):
current += f
if current >= pick:
return pop[i]
return pop[-1]
def crossover(parent1, parent2):
"""单点交叉"""
if random.random() < CROSS_RATE:
point = random.randint(1, CHROM_LEN - 1)
child1 = parent1[:point] + parent2[point:]
child2 = parent2[:point] + parent1[point:]
return child1, child2
return parent1[:], parent2[:]
def mutate(chrom):
"""按位变异"""
for i in range(CHROM_LEN):
if random.random() < MUTATE_RATE:
chrom[i] = 1 - chrom[i]
return chrom
# 主循环
pop = init_population()
for gen in range(MAX_GEN):
# 计算适应度
decoded = [decode(chrom) for chrom in pop]
fits = [fitness(x) for x in decoded]
# 记录最优
best_idx = fits.index(max(fits))
best_x = decoded[best_idx]
best_f = fits[best_idx]
print(f"第 {gen+1} 代: x={best_x}, f(x)={best_f}")
# 生成下一代
new_pop = []
# 精英保留
new_pop.append(pop[best_idx][:])
while len(new_pop) < POP_SIZE:
p1 = select(pop, fits)
p2 = select(pop, fits)
c1, c2 = crossover(p1, p2)
c1 = mutate(c1)
c2 = mutate(c2)
new_pop.append(c1)
if len(new_pop) < POP_SIZE:
new_pop.append(c2)
pop = new_pop
print(f"\n最优解: x={best_x}, f(x)={best_f}")运行这段代码，你会发现算法很快就能找到 x=31，f(x)=961 这个最优解。当然，这是个简单问题，实际项目中遇到的问题要复杂得多。
实用技巧：我建议你在实际项目中，把适应度函数设计成「越大越好」的形式。如果原始问题是求最小值，可以取倒数或者用一个大数减去原始值。另外，适应度值的差异不要太大，否则容易早熟——可以试试适应度缩放（fitness scaling）。
4.8 参数调优建议
遗传算法的参数调优，说白了就是平衡「探索」和「利用」。我总结了一个经验表：
| 参数 | 推荐范围 | 调优方向 |
|---|---|---|
| 种群大小 | 20~100 | 太小易早熟，太大计算慢 |
| 交叉概率 | 0.6~0.9 | 高则搜索快，但可能破坏好解 |
| 变异概率 | 0.01~0.1 | 高则多样性好，但收敛慢 |
| 精英数量 | 1~5 | 保证不丢失最优解 |
嗯，这里要注意：没有万能参数组合。我建议你先用默认参数跑一遍，观察收敛曲线，再根据实际情况调整。如果收敛太快，就降低选择压力或提高变异概率；如果收敛太慢，就提高交叉概率或增大种群。