NSGA-II算法实战：用Python手把手教你解决多目标优化问题（附完整代码）

NSGA-II算法实战用Python手把手教你解决多目标优化问题附完整代码在工程优化、金融投资和人工智能等领域我们常常需要同时优化多个相互冲突的目标。比如设计汽车时既要降低油耗又要提高安全性投资组合需要平衡收益与风险机器学习模型需要兼顾准确率与计算效率。这类多目标优化问题MOOP的解决方案不是单一的最优解而是一组被称为Pareto前沿的折衷解集。NSGA-II非支配排序遗传算法II正是解决这类问题的利器。作为进化计算领域的经典算法它通过独特的非支配排序机制和拥挤距离计算能够高效地找到分布均匀的Pareto最优解集。本文将带你从零开始实现NSGA-II算法并通过一个实际优化案例演示其完整应用流程。1. 环境准备与问题定义在开始编码前我们需要准备Python环境和明确待解决的优化问题。建议使用Python 3.8版本并安装以下依赖库pip install numpy matplotlib考虑一个经典的双目标优化问题我们需要同时优化以下两个函数函数1f1(x) -x² 最大化函数2f2(x) -(x-2)² 最大化这两个函数在x∈[-55,55]区间内存在明显的冲突关系。当x趋近于0时f1取得最大值而当x趋近于2时f2取得最大值。我们的目标是找到一组x值能够在两个目标之间取得最佳平衡。import math import random import matplotlib.pyplot as plt def function1(x): return -x**2 def function2(x): return -(x-2)**22. NSGA-II核心组件实现2.1 非支配排序实现非支配排序是NSGA-II的核心机制用于将解集划分为不同等级的前沿层。第一前沿层包含不被任何其他解支配的解第二前沿层包含仅被第一层解支配的解以此类推。def fast_non_dominated_sort(values1, values2): S [[] for _ in range(len(values1))] # 被支配解集合 front [[]] # 前沿层级 n [0]*len(values1) # 支配计数 rank [0]*len(values1) # 前沿等级 # 计算支配关系 for p in range(len(values1)): for q in range(len(values1)): if (values1[p] values1[q] and values2[p] values2[q]) or \ (values1[p] values1[q] and values2[p] values2[q]) or \ (values1[p] values1[q] and values2[p] values2[q]): if q not in S[p]: S[p].append(q) elif (values1[q] values1[p] and values2[q] values2[p]) or \ (values1[q] values1[p] and values2[q] values2[p]) or \ (values1[q] values1[p] and values2[q] values2[p]): n[p] 1 if n[p] 0: rank[p] 0 if p not in front[0]: front[0].append(p) # 构建前沿层级 i 0 while front[i]: Q [] for p in front[i]: for q in S[p]: n[q] - 1 if n[q] 0: rank[q] i 1 if q not in Q: Q.append(q) i 1 front.append(Q) return front[:-1]2.2 拥挤距离计算拥挤距离用于衡量解在目标空间中的分布密度确保Pareto前沿的多样性。距离值越大表示该解周围越空旷对维持解集多样性越有价值。def crowding_distance(values1, values2, front): distance [0]*len(front) # 按目标函数1排序 sorted1 sorted(range(len(front)), keylambda x: values1[front[x]]) # 按目标函数2排序 sorted2 sorted(range(len(front)), keylambda x: values2[front[x]]) # 边界点距离设为无穷大 distance[0] distance[-1] float(inf) # 计算中间点的拥挤距离 for k in range(1, len(front)-1): distance[k] (values1[front[sorted1[k1]]] - values1[front[sorted1[k-1]]]) / \ (max(values1) - min(values1) 1e-10) distance[k] (values2[front[sorted2[k1]]] - values2[front[sorted2[k-1]]]) / \ (max(values2) - min(values2) 1e-10) return distance3. 遗传算子实现3.1 选择与交叉NSGA-II采用二元锦标赛选择机制结合非支配等级和拥挤距离来选择优质个体def binary_tournament(population, fitness1, fitness2): # 随机选择两个个体 a, b random.sample(range(len(population)), 2) # 比较非支配等级 rank_a fitness1[a] rank_b fitness1[b] if rank_a rank_b: # 等级越小越好 return population[a] elif rank_a rank_b: return population[b] else: # 等级相同比较拥挤距离 if fitness2[a] fitness2[b]: return population[a] else: return population[b]3.2 变异操作变异操作引入随机性帮助算法跳出局部最优def mutate(x, min_x, max_x, mutation_rate0.1): if random.random() mutation_rate: return min_x (max_x - min_x) * random.random() return x4. 完整算法流程实现将上述组件整合成完整的NSGA-II算法def nsga2(pop_size50, max_gen100, min_x-55, max_x55): # 初始化种群 population [min_x (max_x - min_x) * random.random() for _ in range(pop_size)] for gen in range(max_gen): # 评估目标函数 f1_values [function1(x) for x in population] f2_values [function2(x) for x in population] # 非支配排序 fronts fast_non_dominated_sort(f1_values, f2_values) # 计算拥挤距离 crowding_distances [] for front in fronts: crowding_distances.append(crowding_distance(f1_values, f2_values, front)) # 选择父代 parents [] while len(parents) pop_size: parents.append(binary_tournament(population, [next((i for i, front in enumerate(fronts) if p in front), 0) for p in range(len(population))], [next((d for i, front in enumerate(fronts) for j, p in enumerate(front) if p idx), 0) for idx in range(len(population))])) # 生成子代 offspring [] for i in range(0, pop_size, 2): parent1 parents[i] parent2 parents[i1] if i1 pop_size else parents[0] # 模拟二进制交叉 child1 0.5 * parent1 0.5 * parent2 child2 1.5 * parent1 - 0.5 * parent2 # 扩大搜索空间 # 变异 child1 mutate(child1, min_x, max_x) child2 mutate(child2, min_x, max_x) offspring.extend([child1, child2]) # 合并父代和子代 combined population offspring[:pop_size] # 环境选择 new_population [] f1_combined [function1(x) for x in combined] f2_combined [function2(x) for x in combined] fronts fast_non_dominated_sort(f1_combined, f2_combined) for front in fronts: if len(new_population) len(front) pop_size: new_population.extend([combined[i] for i in front]) else: # 按拥挤距离排序选择 crowding crowding_distance(f1_combined, f2_combined, front) sorted_front sorted(zip(front, crowding), keylambda x: -x[1]) remaining pop_size - len(new_population) new_population.extend([combined[i] for i, _ in sorted_front[:remaining]]) break population new_population return population5. 结果可视化与分析运行算法并可视化Pareto前沿# 运行算法 final_population nsga2(pop_size50, max_gen100) # 计算最终目标值 f1_final [function1(x) for x in final_population] f2_final [function2(x) for x in final_population] # 绘制Pareto前沿 plt.figure(figsize(10, 6)) plt.scatter([-f for f in f1_final], [-f for f in f2_final], cblue, labelPareto Front) plt.xlabel(Function 1 (x²), fontsize12) plt.ylabel(Function 2 ((x-2)²), fontsize12) plt.title(NSGA-II Pareto Front, fontsize14) plt.grid(True) plt.legend() plt.show()通过分析可视化结果我们可以观察到解集在目标空间中形成了典型的Pareto前沿曲线。靠近曲线左上方的解在函数1上表现更好而靠近右下方的解在函数2上更优。这种分布验证了NSGA-II在维持解集多样性方面的有效性。