NSGA-非支配排序遗传

1. 方法概述

本项目实现的是 NSGA-II（Non-dominated Sorting Genetic Algorithm II）多目标优化框架，核心代码位于 NSGA-非支配排序遗传/core/nsga2_runner.py。与很多简化版本不同，本项目不仅支持内置多目标基准问题，还支持：

• Custom 模式：用户输入多个目标函数表达式，并可附带不等式/等式约束；
• UploadSurrogate 模式：上传数据后训练随机森林代理，并把“预测目标 + distance_to_center”构造成双目标问题；
• uniform/per_dim 两类边界；
• runs>1 的多次独立运行，并按最佳 front0_size 选取代表性运行。

设多目标问题为

$$ \min_{\boldsymbol{x}\in\Omega}\ \boldsymbol{f}(\boldsymbol{x})= \big(f_1(\boldsymbol{x}),\ldots,f_m(\boldsymbol{x})\big)^\top \tag{1} $$

2. 问题定义、约束罚函数与上传代理优化

在 Custom 模式下，若给定不等式约束 \(g_k(\boldsymbol{x})\le 0\) 和等式约束 \(h_\ell(\boldsymbol{x})=0\)，则项目构造罚函数

$$ P(\boldsymbol{x})= \rho\sum_k \max\big(g_k(\boldsymbol{x}),0\big)^p +\rho_{eq}\sum_\ell \max\big(|h_\ell(\boldsymbol{x})|-\varepsilon,0\big)^p \tag{2} $$

若第 \(j\) 个目标被设置为最大化，则代码会先做符号翻转。于是内部用于 NSGA-II 的目标写为

$$ \tilde f_j(\boldsymbol{x})=s_j f_j(\boldsymbol{x})+P(\boldsymbol{x}), \qquad s_j= \begin{cases} 1, & \text{min}\\ -1, & \text{max} \end{cases} \tag{3} $$

在上传代理优化模式下，首先训练随机森林预测器

$$ \hat f(\boldsymbol{x})=\frac{1}{300}\sum_{b=1}^{300}T_b(\boldsymbol{x}) \tag{4} $$

再定义第二目标

$$ d_c(\boldsymbol{x})= \frac{1}{d}\sum_{j=1}^{d}\left(\frac{x_j-c_j}{s_j}\right)^2 \tag{5} $$

于是上传模式下实际求解的是

$$ \boldsymbol{f}_{up}(\boldsymbol{x})= \begin{bmatrix} \sigma\,\hat f(\boldsymbol{x})\\ d_c(\boldsymbol{x}) \end{bmatrix}, \qquad \sigma= \begin{cases} 1, & \text{min}\\ -1, & \text{max} \end{cases} \tag{6} $$

其中第一目标在导出阶段会再恢复成真实方向。

3. 核心数学模型

3.1 初始化与支配排序

若边界为 \([\boldsymbol{l},\boldsymbol{u}]\)，则初始种群按均匀分布生成：

$$ \boldsymbol{x}_i^{(0)}=\boldsymbol{l}+\boldsymbol{r}_i\odot(\boldsymbol{u}-\boldsymbol{l}),\qquad \boldsymbol{r}_i\sim U(0,1)^d \tag{7} $$

项目使用标准最小化支配关系：

$$ \boldsymbol{a}\prec \boldsymbol{b} \Longleftrightarrow \big(\forall j,\ \tilde f_j(\boldsymbol{a})\le \tilde f_j(\boldsymbol{b})\big)\ \land\ \big(\exists j,\ \tilde f_j(\boldsymbol{a})< \tilde f_j(\boldsymbol{b})\big) \tag{8} $$

非支配排序后，第 \(k\) 层前沿记为 \(\mathcal{F}_k\)。

3.2 拥挤距离与锦标赛选择

对同一前沿 \(\mathcal{F}\) 上的个体，项目按目标维计算拥挤距离。对非边界个体 \(i\)，第 \(j\) 个目标贡献为

$$ \mathrm{cd}_{ij}= \frac{\tilde f_j(i^+)-\tilde f_j(i^-)}{\tilde f_j^{\max}-\tilde f_j^{\min}} \tag{9} $$

总拥挤距离为

$$ \mathrm{CD}_i=\sum_{j=1}^{m}\mathrm{cd}_{ij} \tag{10} $$

二元锦标赛时，项目按“等级优先、拥挤距离次之”选择父代：

$$ i^\star= \operatorname*{arg\,min}_{i\in\{a,b\}} \big(\mathrm{rank}_i,-\mathrm{CD}_i\big) \tag{11} $$

3.3 SBX 交叉与多项式变异

项目使用有界 SBX 交叉。对某一维，子代计算为

$$ c_1=\frac{1}{2}\Big((x_1+x_2)-\beta_q(x_2-x_1)\Big),\qquad c_2=\frac{1}{2}\Big((x_1+x_2)+\beta_q(x_2-x_1)\Big) \tag{12} $$

其中 \(\beta_q\) 由 eta_c 与随机数共同决定，最终再截断到边界内。

随后使用多项式变异。若某一维被选中变异，则

$$ x_j\leftarrow \operatorname{clip}\!\big(x_j+\Delta_q(u_j-l_j),\,l_j,\,u_j\big) \tag{13} $$

其中 \(\Delta_q\) 由 eta_m 和随机数按 Deb 多项式变异公式生成。若 mut_prob<0，项目自动使用

$$ p_m=\frac{1}{d} \tag{14} $$

作为逐维变异概率。

3.4 环境选择

每轮把父代与子代合并：

$$ \mathcal{Q}^{(t)}=\mathcal{P}^{(t)}\cup \mathcal{O}^{(t)} \tag{15} $$

再按前沿逐层填充下一代，最后一层若装不下，则按拥挤距离降序截断：

$$ \mathcal{P}^{(t+1)}=\operatorname{SelectByFrontAndCrowding}\big(\mathcal{Q}^{(t)},N\big) \tag{16} $$

3.5 多次运行与最佳运行选择

项目支持 \(R\) 次独立运行，第 \(r\) 次运行使用随机种子

$$ \mathrm{seed}_r=\mathrm{seed}_0+r-1 \tag{17} $$

每代会记录第一前沿规模

$$ s_r^{(t)}=\big|\mathcal{F}_{1,r}^{(t)}\big| \tag{18} $$

最终最佳运行并不是按 HV 或 IGD 选，而是按最终 Pareto 前沿规模最大来选：

$$ r^\star=\operatorname*{arg\,max}_{1\le r\le R}s_r^{(T)} \tag{19} $$

被选中的第 \(r^\star\) 次运行的 Pareto 前沿和最终种群会被写入主要结果表。

4. 算法流程

结合 core/nsga2_runner.py、core/custom_problem.py、core/problems.py 与 utils/excel_handler.py，本项目 NSGA-II 的流程为：

1. 选择内置问题、Custom 或 UploadSurrogate。
2. 根据 uniform/per_dim 规则构造边界。
3. 按式（7）初始化种群，并计算目标向量。
4. 进行非支配排序和拥挤距离计算。
5. 按式（11）选择父代，使用式（12）和式（13）生成子代。
6. 按式（15）与式（16）完成环境选择。
7. 记录每代 front0_size 及前沿目标统计。
8. 若 runs>1，按式（19）选出代表性运行，并导出 Run_Summary、History_All、Pareto_Front、Final_Population 等工作表及图像。

5. 关键参数说明

• pop_size：种群规模。
• n_gen：进化代数。
• runs：独立运行次数。
• seed：基础随机种子。
• cx_prob、eta_c：SBX 交叉参数。
• eta_m、mut_prob：多项式变异参数。
• tournament_k：锦标赛抽样规模。
• bounds_mode：uniform 或 per_dim。

6. 评价指标与输出结果解释

项目输出内容非常完整，通常包括：

• Run_Summary：每次运行的前沿规模、目标维数、决策维数。
• History_All：所有运行、所有代的 front0_size 及目标统计。
• Pareto_Front：最佳运行的第一前沿。
• Final_Population：最佳运行最终整个种群，含 rank 和 crowding。
• Custom_Objective：仅 Custom 模式下出现，保存表达式与约束。
• UploadedData、SurrogateMetrics、Bounds：上传代理优化模式下的附加信息。

需要特别注意：最佳运行的判据是 front0_size_best_run，不是目标值最优或 HV 最优。论文结果部分建议以 Pareto_Front 作为主表或主图的数据源，以 History_All 说明 front0_size 的代际演化，并在正文中注明最佳运行是按第一前沿规模选取。若使用上传代理模式，还应交代第二目标来自样本中心偏离度，约束则通过罚函数并入目标评价。

7. 论文写作模板

可在论文方法部分表述为：

“本文采用 NSGA-II 进行多目标优化。算法首先对种群执行非支配排序并计算拥挤距离，再利用基于等级和拥挤距离的锦标赛选择生成父代，通过有界 SBX 交叉和多项式变异产生子代，并在父子合并种群上执行环境选择。对于自定义问题，本文支持把不等式与等式约束统一转化为罚函数并叠加到各目标上；对于数据驱动问题，本文进一步构造了‘随机森林预测目标 + 距样本中心偏离度’的双目标代理问题，从而输出 Pareto 解集。”

7.1 结果部分补充模板

若需把实验结果直接写入论文结果部分，可进一步表述为：

“图X展示了算法得到的 Pareto 前沿，表X列出了代表性非支配解及其决策变量和目标函数值。结合 HV、IGD、前沿规模或档案规模等指标可见，该算法在保持解集多样性的同时实现了较好的收敛性能。对于上传代理优化场景，所得前沿刻画了预测目标与样本中心偏离度之间的权衡关系，从而为方案筛选提供了多解备选。”

7.2 写作替换提示

为便于直接落稿，正文撰写时可将结果文件中的字段替换为以下论文措辞：

• ParetoFront、Pareto_Front 可写为“最终 Pareto 前沿解集”或“非支配解集”；
• ParetoSolutions 可写为“Pareto 前沿对应的决策变量组合”；
• HVHistory、hv_final 可写为“超体积指标及其演化曲线”；
• igd 可写为“反世代距离指标”；
• 上传代理模式下的第二目标可写为“预测目标与样本中心偏离度之间的权衡关系”。

7.3 可直接替换的论文结果段落

若需进一步直接落稿，可按以下模板替换其中的表号、图号和数值：

“由表X可知，在 [runs] 次独立运行后，NSGA-II 所选取代表性运行的第一前沿规模 front0_size_best_run 为 [front0_size_best_run]。需要说明的是，该代表性运行并非按目标值最优或 HV 最大选取，而是依据第一前沿规模最大这一实现判据确定。图X给出了该最佳运行对应的 Pareto_Front，说明算法能够在多个目标之间形成较为清晰的非支配折中关系；由图Y所示 History_All 的代际演化结果可见，front0_size 随迭代逐步扩展并在后期趋于稳定，表明算法的非支配解搜索能力逐渐收敛。表Y可进一步列出 Pareto_Front 或 Final_Population 中 rank=0 个体对应的代表性决策变量组合与目标函数值。若采用上传代理优化模式，还应说明第二目标来自样本中心偏离度，并结合 SurrogateMetrics 中的 RMSE、MAE 和 \(R^2\) 指标论证所得 Pareto 解集的代理可信度。”

8. 实现说明与注意事项

• 本实现是完整的 NSGA-II 桌面版，支持内置问题、自定义表达式和上传代理三种问题来源。
• Custom 模式下所有最大化目标都会先转成最小化，导出前再恢复符号。
• 多次运行时，代码按 front0_size 最大选择代表性运行，这一准则要在论文里说明。
• 上传代理优化模式下第二目标 distance_to_center 为项目自定义构造，并非标准 NSGA-II 问题库内容。

9. 单篇终审补充

9.1 图题与表题对齐建议

• Run_Summary 表可写为：表X NSGA-II 各次运行前沿规模汇总。
• History_All 表可写为：表X NSGA-II 全部运行代际演化历史。
• Pareto_Front 表可写为：表X NSGA-II 代表性运行的第一前沿解集。
• Final_Population 表可写为：表X NSGA-II 最终种群及其 rank、crowding 信息。
• 若绘制前沿图，建议写为：图X NSGA-II Pareto 前沿分布图。

9.2 终审说明

• 当前实现的代表性运行是按 front0_size_best_run 选取，不是按 HV 最优或某个目标最优选取，论文正文必须写清这一点。
• 上传代理模式下第二目标是项目自定义的样本中心偏离度，不能泛写成标准测试问题的第二目标。

9.3 全量强化补充

本次全量强化绑定的真实上传验证目录为 具体的算法3/优化与多目标/NSGA-非支配排序遗传/results/manual_upload_verify_20260328/nsga_sample_upload_real_check。主结果文件为 NSGA_results_20260328_235211.xlsx，实际工作表为 Summary、Problem、NSGA2_Params、Bounds、Run_Summary、History_All、Pareto_Front、Final_Population、UploadedData、SurrogateMetrics、Charts。

当前真实图文件包括 NSGA_pareto_20260328_235211.png 与 NSGA_history_20260328_235211.png，同目录还保留较早一次运行的 235204 版本。论文正文若引用前沿图和历史图，应固定使用与主结果文件同时间戳的 235211 版本，避免混用不同轮次的图件。

复现脚本为 repro_nsga2.py，输入口径为 INPUT_FILE = Path('repro_inputs/nsga_sample.xlsx')，并在 problem_kwargs 中明确构造 UploadSurrogate 问题、target_column = 'f_sphere'、objective_direction = 'min'。因此这篇文档应把上传代理模式下的第二目标仍解释为项目自定义的权衡目标，而不是标准测试集里的固定第二目标。

10. 软件实现核查补充（2026-07）

本篇对应的软件源码目录是 具体的算法3/优化与多目标/NSGA-非支配排序遗传。这是多目标算法，不应按单目标“最优值”表述。当前软件实现支持多目标优化和多目标上传数据代理优化；上传模式通过代理目标构造新的双目标/多目标问题，再运行 NSGA 系列算法。

当前较新的代表性目录为 results/NSGA-非支配排序遗传分析结果_20260517_144000-多目标优化 与 results/NSGA-非支配排序遗传分析结果_20260517_144012-多目标上传数据代理优化。主工作簿中应重点看 Pareto_Solutions、Pareto_Objectives、Population_Final、History、Run_Summary、Quality_Metrics、Charts，上传模式再叠加 UploadedProblem、UploadedData、SurrogateMetrics。因此论文或用户说明中应把结果解释为“近似 Pareto 前沿”和“质量指标”，不要写成单一最优解。

当前稳定图表为 pareto_front.png、hv_history.png、repository_size.png。复现代码位于 复现代码/多目标优化/ 或 复现代码/多目标上传数据代理优化/，上传模式输入副本为 repro_inputs/nsga_sample.xlsx，复现结果进入 repro_outputs/。旧文如果引用 benchmark 目录，只能作为历史补充，正式交付应优先采用当前 20260517 新目录。