遗传算法实战：用Python从零构建进化引擎

当我在大学第一次接触遗传算法时，那些生物学术语和数学公式让我望而生畏。直到有一天，我决定用代码实现它——神奇的事情发生了，那些抽象的概念突然变得清晰可见。本文将带你用Python构建一个完整的遗传算法框架，通过编写代码来真正理解选择、交叉和变异的本质。

1. 遗传算法核心思想拆解

遗传算法的精妙之处在于它模拟了自然界的进化过程。想象你是一位育种专家，想要培育出更高产的作物品种。你不会只种植单一品种，而是会：

• 保留每代中表现最好的个体
• 让优秀个体之间进行杂交
• 偶尔允许一些随机变异
• 重复这个过程多代

在代码世界中，这个过程变成了：

population = 初始化种群()
for _ in range(代数):
    评估种群适应度(population)
    new_population = []
    while len(new_population) < 种群大小:
        parent1, parent2 = 选择父母(population)
        child1, child2 = 交叉(parent1, parent2)
        child1 = 变异(child1)
        child2 = 变异(child2)
        new_population.extend([child1, child2])
    population = new_population

关键区别 在于我们不需要等待季节更替，一次循环就能模拟一代的进化。下面我们用一个具体问题来演示：寻找函数f(x,y)=x²+y²在[0,31]区间内的最大值。

2. 染色体编码与种群初始化

在自然界，DNA用碱基对编码生物特征。在我们的算法中，我们用二进制字符串表示解：

import random

def 生成染色体(长度=10):
    return [random.randint(0,1) for _ in range(长度)]

def 初始化种群(大小=50, 染色体长度=10):
    return [生成染色体(染色体长度) for _ in range(大小)]

这里每个染色体是10位二进制数，可以表示0-1023的数字。我们将前5位对应x，后5位对应y：

def 解码(染色体):
    x = int(''.join(map(str, 染色体[:5])), 2)
    y = int(''.join(map(str, 染色体[5:])), 2)
    return x, y

注意：染色体长度和编码方式直接影响算法效果。太短会限制搜索空间，太长会增加计算成本。

3. 适应度函数设计

适应度函数是进化的指南针。对于我们的最大化问题：

def 适应度(染色体):
    x, y = 解码(染色体)
    return x**2 + y**2

但直接使用这个值会导致选择压力过大。实践中我们常做缩放：

def 缩放适应度(种群):
    原始适应度 = [适应度(c) for c in 种群]
    最小 = min(原始适应度)
    缩放后 = [f - 最小 + 1 for f in 原始适应度]  # 确保所有适应度为正
    return 缩放后

4. 选择操作实现

轮盘赌选择是最直观的实现方式：

def 轮盘赌选择(种群, 适应度列表):
    总和 = sum(适应度列表)
    选择点 = random.uniform(0, 总和)
    累计 = 0
    for i, 适应度值 in enumerate(适应度列表):
        累计 += 适应度值
        if 累计 >= 选择点:
            return 种群[i]
    return 种群[-1]  # 防止浮点误差

更高效的方法是锦标赛选择：

def 锦标赛选择(种群, 适应度列表, 规模=3):
    参赛者 = random.sample(list(zip(种群, 适应度列表)), 规模)
    return max(参赛者, key=lambda x:x[1])[0]

5. 交叉与变异操作

单点交叉的实现：

def 单点交叉(父代1, 父代2):
    点 = random.randint(1, len(父代1)-1)
    子代1 = 父代1[:点] + 父代2[点:]
    子代2 = 父代2[:点] + 父代1[点:]
    return 子代1, 子代2

基本位变异的实现：

def 变异(染色体, 变异概率=0.01):
    return [1-g if random.random() < 变异概率 else g for g in 染色体]

6. 完整算法组装

现在我们可以将这些组件组合起来：

def 遗传算法(种群大小=50, 代数=100, 交叉率=0.8, 变异率=0.01):
    种群 = 初始化种群(种群大小)
    历史最佳 = None
    
    for 代 in range(代数):
        适应度列表 = 缩放适应度(种群)
        新种群 = []
        
        # 保留当代最优个体(精英保留策略)
        当代最佳 = max(zip(种群, 适应度列表), key=lambda x:x[1])
        if 历史最佳 is None or 当代最佳[1] > 适应度(历史最佳):
            历史最佳 = 当代最佳[0]
        新种群.append(历史最佳.copy())
        
        # 生成下一代
        while len(新种群) < 种群大小:
            父代1 = 锦标赛选择(种群, 适应度列表)
            父代2 = 锦标赛选择(种群, 适应度列表)
            
            if random.random() < 交叉率:
                子代1, 子代2 = 单点交叉(父代1, 父代2)
            else:
                子代1, 子代2 = 父代1.copy(), 父代2.copy()
            
            子代1 = 变异(子代1, 变异率)
            子代2 = 变异(子代2, 变异率)
            新种群.extend([子代1, 子代2])
        
        种群 = 新种群[:种群大小]  # 保持种群大小不变
    
    return 历史最佳

7. 参数调优实战经验

经过多次实验，我发现这些参数组合效果较好：

参数	推荐范围	影响效果
种群大小	50-200	越大搜索越全面，但计算成本高
交叉率	0.7-0.9	控制新个体的生成比例
变异率	0.005-0.02	维持种群多样性关键
锦标赛规模	3-5	选择压力调节器

实际项目中，我通常这样做参数优化：

1. 先用默认参数运行几次，观察收敛速度
2. 如果早熟收敛（快速达到局部最优），尝试：
   • 增加变异率
   • 减小锦标赛规模
   • 增加种群多样性
3. 如果收敛过慢，反向调整上述参数

8. 进阶优化技巧

当解决更复杂问题时，这些技巧很实用：

适应度缩放 ：防止超级个体过早主导种群

def 窗口缩放(适应度列表, 窗口大小=5):
    排序后 = sorted(适应度列表)
    最小值 = 排序后[-window_size] if len(排序后) > window_size else 排序后[0]
    return [max(f - 最小值, 0) for f in 适应度列表]

自适应变异率 ：随着代数增加逐渐降低变异

def 自适应变异率(当前代, 总代数, 基础率=0.02, 最终率=0.001):
    return 基础率 - (基础率-最终率)*(当前代/总代数)

多种群并行 ：防止局部最优

def 岛屿模型(种群数=3, 每代迁移=2):
    群岛 = [初始化种群() for _ in range(种群数)]
    for 代 in range(代数):
        # 各岛屿独立进化
        群岛 = [遗传算法(种群) for 种群 in 群岛]
        
        # 定期迁移
        if 代 % 10 == 0:
            迁移者 = [random.choice(群岛[i]) for i in range(种群数)]
            random.shuffle(迁移者)
            for i in range(种群数):
                群岛[i].extend(迁移者[:每代迁移])

第一次实现遗传算法时，我犯了个典型错误——没有保留每代最佳个体。结果发现算法就像狗熊掰棒子，经常丢掉已经找到的好解。加上精英保留策略后，性能立即提升了30%。另一个教训是变异率设置过高会导致算法变成随机搜索，设置过低又会早熟收敛。经过多次调试，我发现0.01左右的变异率对大多数问题都是不错的起点。