基于进化算法的N皇后问题：如何实现平滑适应度曲线？

核心问题诊断 #

你的曲线波动剧烈主要源于三个关键问题：

• 突变率过高：0.6-1.0的突变概率几乎会每代打乱个体，完全抵消进化积累的优质特征，导致种群fitness剧烈震荡。
• 缺乏统计平均：每个突变率仅运行1次，进化算法的随机性会让单次结果波动极大，无法反映平均收敛趋势。
• 选择策略限制多样性：先排序种群再做锦标赛选择，缩小了选择范围，加剧局部波动。

具体改进步骤 #

1. 大幅降低突变率

把突变概率调整到0.05-0.2区间，既能维持种群多样性，又不会破坏已进化出的优质解：

# 修改常量定义
MUTATION_PROBABILITIES = [0.05, 0.1, 0.15]  # 替换原有的高突变率

2. 增加重复实验次数

对每个突变率重复多次实验（建议5-10次），再取所有实验的总平均，抵消随机性带来的波动：

# 添加重复实验常量
REPEATS = 5  # 每个突变率重复5次
overall_average_fitness = np.zeros(GENERATIONS)

# 修改循环逻辑
for mutation_rate in MUTATION_PROBABILITIES:
    for _ in range(REPEATS):
        best_fitness, average_fitness = evolutionary_algorithm(mutation_rate)
        overall_average_fitness += np.array(average_fitness)

# 计算总平均：突变率数量 × 重复次数
overall_average_fitness /= (len(MUTATION_PROBABILITIES) * REPEATS)

3. 优化选择与精英保留

• 取消种群预排序，直接从原始种群抽取锦标赛样本，保留多样性；
• 添加精英保留策略，将每代前10%的优质个体直接传入下一代，保障进化方向性：

def next_generation(population, mutation_rate):
    new_population = []
    
    # 直接从原始种群选择父母，取消预排序
    while len(new_population) < POP_SIZE:
        parent1 = select_parents(population)
        parent2 = select_parents(population)
        child1, child2 = crossover(parent1, parent2)
        new_population.append(mutate(child1, mutation_rate))
        new_population.append(mutate(child2, mutation_rate))
    
    # 精英保留：保留当前种群前10%的最优个体
    elite_count = int(POP_SIZE * 0.1)
    sorted_pop = sorted(population, key=fitness, reverse=True)
    new_population = sorted_pop[:elite_count] + new_population[elite_count:]
    
    return new_population

4. 绘图时添加滑动窗口平滑

对最终的平均fitness做滑动窗口平均，进一步消除小幅度波动：

# 滑动窗口平滑处理，窗口大小设为10
window_size = 10
smoothed_fitness = np.convolve(overall_average_fitness, np.ones(window_size)/window_size, mode='valid')

# 替换原绘图代码，使用平滑后的数据
plt.figure(figsize=(12, 6))
plt.plot(range(window_size-1, GENERATIONS), smoothed_fitness, label='Smoothed Overall Average Fitness', color='blue')
plt.title('Overall Average Non-Attacking Pairs Fitness Over Generations')
plt.xlabel('Generation')
plt.ylabel('Fitness (Number of Non-Attacking Pairs)')
plt.xticks(ticks=np.arange(0, GENERATIONS + 1, 100))
plt.grid()
plt.axhline(y=N * (N - 1) / 2 + 0.001, color='black', linewidth=0.8, linestyle='--', label='Max Non-Attacking Pairs')
plt.legend()
plt.show()

额外优化建议 #

• 调整锦标赛规模：把select_parents中的锦标赛样本数从5改为3，平衡选择压力和种群多样性；
• 改用攻击对数作为适应度（最小化目标）：最小化问题的收敛曲线通常更稳定，你可以将fitness函数改为返回攻击对数，再取负数或直接最小化。

内容的提问来源于stack exchange，提问作者FullMetal Alchemist