NSGA-II 多目标遗传算法 Python 实战：SVM 超参数优化与 Pareto 前沿可视化
当我们需要同时优化机器学习模型的多个性能指标时，单目标优化方法往往显得力不从心。比如在支持向量机(SVM)调参中，我们既希望模型准确率尽可能高，又希望训练时间尽可能短，这两个目标通常是相互矛盾的。这时候，多目标优化算法就能派上大用场。
NSGA-II(非支配排序遗传算法 II)是目前最流行的多目标优化算法之一，它通过维护一个解的种群，采用非支配排序和拥挤度比较机制，能够在一次运行中找到多个 Pareto 最优解。这些解构成了所谓的 Pareto 前沿，展示了不同目标之间的最佳权衡关系。
1. 多目标优化基础与 NSGA-II 原理
在单目标优化中，我们很容易定义"最优解"——就是使目标函数值最小(或最大)的那个解。但在多目标优化中，由于存在多个相互冲突的目标，通常不存在一个在所有目标上都最优的解，而是存在一组"非支配解"(Pareto 最优解)。
非支配解的定义是：在解集中，如果一个解在所有目标上都不比另一个解差，且至少在一个目标上严格更好，则称前者支配后者。不被任何其他解支配的解就是非支配解。
NSGA-II 通过以下机制高效寻找 Pareto 最优解：
- 快速非支配排序：将种群中的个体按支配关系分层，确保优秀个体优先保留
- 拥挤度比较：在同层个体中，优先保留目标空间中分布稀疏的个体，维持解的多样性
- 精英保留策略：将父代和子代合并选择，防止优秀个体丢失
# NSGA-II 伪代码框架 def NSGA2(): 初始化种群 P 计算每个个体的目标函数值 对 P 进行非支配排序 计算拥挤度 while 未达到终止条件: 通过选择、交叉、变异生成子代 Q 合并父代 P 和子代 Q 得到 R 对 R 进行非支配排序 计算拥挤度 选择前 N 个个体组成新一代 P return 最后一代的非支配解集2. SVM 超参数优化问题建模
支持向量机的性能很大程度上取决于其超参数的选择。我们主要关注以下两个超参数：
- 正则化参数 C：控制模型对误分类样本的惩罚力度
- 核函数参数 gamma：影响 RBF 核的局部性程度
我们的优化目标是：
- 最大化模型在测试集上的准确率
- 最小化模型的训练时间
这两个目标通常是相互冲突的——更复杂的模型(更大的 C 和 gamma)可能获得更高准确率，但需要更长的训练时间。
首先，我们需要定义评估函数，计算给定超参数下的目标值：
from sklearn.svm import SVC from sklearn.model_selection import cross_val_score import time def evaluate_svm(params, X, y): """ 评估 SVM 模型的性能 参数: params: 超参数字典 {'C': value, 'gamma': value} X: 特征数据 y: 标签数据 返回: (准确率, 训练时间) 元组 """ model = SVC(C=params['C'], gamma=params['gamma'], random_state=42) # 计算训练时间 start_time = time.time() scores = cross_val_score(model, X, y, cv=5, scoring='accuracy') elapsed_time = time.time() - start_time accuracy = np.mean(scores) return accuracy, elapsed_time3. Python 实现 NSGA-II 算法
下面我们使用 DEAP 库实现 NSGA-II 算法。DEAP 是一个强大的进化计算框架，可以方便地实现各种遗传算法。
首先设置遗传算法的基本要素：
from deap import base, creator, tools, algorithms import numpy as np import random # 定义多目标最小化问题（准确率最大化，时间最小化） creator.create("FitnessMulti", base.Fitness, weights=(1.0, -1.0)) creator.create("Individual", list, fitness=creator.FitnessMulti) # 初始化工具箱 toolbox = base.Toolbox() # 定义超参数范围 C_min, C_max = 0.1, 100 gamma_min, gamma_max = 0.0001, 10 # 注册基因生成函数 toolbox.register("attr_C", random.uniform, C_min, C_max) toolbox.register("attr_gamma", random.uniform, gamma_min, gamma_max) # 定义个体生成方式 toolbox.register("individual", tools.initCycle, creator.Individual, (toolbox.attr_C, toolbox.attr_gamma), n=1) toolbox.register("population", tools.initRepeat, list, toolbox.individual)接下来定义遗传操作和评估函数：
# 评估函数 def evaluate(individual, X, y): params = {'C': individual[0], 'gamma': individual[1]} accuracy, time_consumed = evaluate_svm(params, X, y) return accuracy, time_consumed # 注册遗传操作 toolbox.register("mate", tools.cxSimulatedBinaryBounded, low=[C_min, gamma_min], up=[C_max, gamma_max], eta=20.0) toolbox.register("mutate", tools.mutPolynomialBounded, low=[C_min, gamma_min], up=[C_max, gamma_max], eta=20.0, indpb=0.2) toolbox.register("select", tools.selNSGA2) toolbox.register("evaluate", evaluate)4. 运行 NSGA-II 优化
现在我们可以运行 NSGA-II 算法来优化 SVM 超参数了：
def run_nsga2(X, y, pop_size=50, n_gen=20, cxpb=0.9, mutpb=0.1): # 创建初始种群 pop = toolbox.population(n=pop_size) # 评估初始种群 fitnesses = [toolbox.evaluate(ind, X, y) for ind in pop] for ind, fit in zip(pop, fitnesses): ind.fitness.values = fit # 运行 NSGA-II for gen in range(n_gen): # 选择下一代 offspring = toolbox.select(pop, len(pop)) offspring = list(map(toolbox.clone, offspring)) # 应用交叉和变异 for child1, child2 in zip(offspring[::2], offspring[1::2]): if random.random() < cxpb: toolbox.mate(child1, child2) del child1.fitness.values del child2.fitness.values for mutant in offspring: if random.random() < mutpb: toolbox.mutate(mutant) del mutant.fitness.values # 评估新个体 invalid_ind = [ind for ind in offspring if not ind.fitness.valid] fitnesses = [toolbox.evaluate(ind, X, y) for ind in invalid_ind] for ind, fit in zip(invalid_ind, fitnesses): ind.fitness.values = fit # 合并父代和子代 pop = toolbox.select(pop + offspring, pop_size) return pop5. Pareto 前沿可视化与分析
获得优化结果后，我们可以将 Pareto 前沿可视化，直观展示不同超参数配置下的权衡关系：
import matplotlib.pyplot as plt def plot_pareto_front(pop, X, y): # 提取所有解的目标值 accuracies = [] times = [] for ind in pop: acc, t = ind.fitness.values accuracies.append(acc) times.append(t) # 找出非支配解 front = tools.sortNondominated(pop, len(pop), first_front_only=True)[0] front_acc = [] front_time = [] for ind in front: acc, t = ind.fitness.values front_acc.append(acc) front_time.append(t) # 绘制结果 plt.figure(figsize=(10, 6)) plt.scatter(times, accuracies, c='blue', alpha=0.5, label='All solutions') plt.scatter(front_time, front_acc, c='red', s=100, label='Pareto front') plt.xlabel('Training Time (s)') plt.ylabel('Accuracy') plt.title('Pareto Front for SVM Hyperparameter Optimization') plt.legend() plt.grid(True) plt.show() return front6. 完整案例演示
让我们用一个实际数据集演示整个流程。我们使用 sklearn 中的乳腺癌数据集：
from sklearn.datasets import load_breast_cancer from sklearn.preprocessing import StandardScaler # 加载并预处理数据 data = load_breast_cancer() X, y = data.data, data.target X = StandardScaler().fit_transform(X) # 运行 NSGA-II 优化 optimized_pop = run_nsga2(X, y, pop_size=50, n_gen=20) # 可视化 Pareto 前沿 pareto_front = plot_pareto_front(optimized_pop, X, y)运行结果将显示一个散点图，其中红色点表示 Pareto 前沿上的解。从图中我们可以清楚地看到准确率和训练时间之间的权衡关系——要获得更高的准确率，通常需要付出更长的训练时间。
7. 结果分析与决策建议
获得 Pareto 前沿后，我们需要根据实际需求选择最合适的解。以下是几种常见的决策策略：
固定约束法：如果一个目标有硬性要求，比如训练时间不能超过 5 秒，我们就在满足该约束的解中选择另一个目标最优的解。
权重法：给两个目标分配权重，计算每个解的加权和，选择总分最高的解。例如：
def weighted_score(individual, accuracy_weight=0.7): acc, time = individual.fitness.values # 归一化处理 normalized_acc = (acc - min_acc) / (max_acc - min_acc) normalized_time = (time - min_time) / (max_time - min_time) return accuracy_weight * normalized_acc + (1 - accuracy_weight) * normalized_time拐点法：选择 Pareto 前沿上斜率变化最大的点，这个点通常代表了性价比最高的折中方案。
对于我们的 SVM 调参问题，还可以进一步分析 Pareto 前沿上的解对应的超参数值，找出其中的规律：
def analyze_pareto_front(pareto_front): C_values = [] gamma_values = [] accuracies = [] times = [] for ind in pareto_front: C, gamma = ind acc, t = ind.fitness.values C_values.append(C) gamma_values.append(gamma) accuracies.append(acc) times.append(t) # 绘制超参数与目标的关系 plt.figure(figsize=(15, 5)) plt.subplot(1, 2, 1) plt.scatter(C_values, accuracies, c=times, cmap='viridis') plt.colorbar(label='Training Time (s)') plt.xscale('log') plt.xlabel('C (log scale)') plt.ylabel('Accuracy') plt.title('C vs Accuracy (Color: Time)') plt.subplot(1, 2, 2) plt.scatter(gamma_values, accuracies, c=times, cmap='viridis') plt.colorbar(label='Training Time (s)') plt.xscale('log') plt.xlabel('gamma (log scale)') plt.ylabel('Accuracy') plt.title('gamma vs Accuracy (Color: Time)') plt.tight_layout() plt.show()通过这种分析，我们可能会发现某些超参数组合能带来更好的性能-时间平衡，这些经验可以指导我们在其他数据集上的调参工作。
 到 O(1) 的查询实践)
