帕累托法则在多目标优化中的应用

基于Pareto支配的优化算法是多目标优化领域中最主流、最成熟的一类方法，核心思想很直观： 直接利用"帕累托支配"这个标准来比较解的优劣，通过保留"不被支配"的优良个体，并维持解的多样性，最终得到一组分布均匀的帕累托最优解。

1

基于Pareto支配的优化算法全景图

2

核心算法详细介绍

1. NSGA-II：最经典的"多面手"

NSGA-II（Non-dominated Sorting Genetic Algorithm II） 是由Deb于2002年提出的算法，可以说是多目标优化领域最具影响力的算法。

原理本质

通过 快速非支配排序 将种群分层（rank1为最优帕累托前沿），同层内用 拥挤度距离 衡量解的稀疏程度。选择时优先保留rank小且拥挤度大的个体，从而实现收敛性和多样性的平衡。

核心步骤

1. 初始化 ：随机生成父代种群P0
2. 非支配排序 ：对P0进行快速非支配排序，得到每个个体的层数(rank)和拥挤度距离
3. 生成子代 ：通过锦标赛选择（基于rank和拥挤度）、交叉、变异生成子代Q0
4. 合并筛选 ：合并P0和Q0为R（规模2N），对R进行非支配排序并计算拥挤度
5. 精英保留 ：从R中依次选择非支配层（从rank1开始）填充新父代P1，最后一层按拥挤度从大到小选取至满N
6. 迭代 ：重复3-5直至终止

关键创新

• 快速非支配排序 ：计算复杂度从O(mN³)降至O(mN²)（m为目标数，N为种群规模）
• 拥挤度比较 ：无需人为指定共享参数，自动维持多样性
• 精英策略 ：父代子代共同竞争，优秀个体不易丢失

应用场景

生产调度、机械设计、电力系统优化等通用多目标问题。

2. SPEA2：精细化的"存档大师"

SPEA2（Strength Pareto Evolutionary Algorithm 2） 是对SPEA的改进版本，由Zitzler等人在2001年提出。

原理本质

同时维护一个 常规种群 和一个 外部存档 （存储非支配解）。采用 强度值 和 原始适应度 评估个体，并引入 近邻密度估计 来区分相同适应度的个体。

核心步骤

1. 初始化 ：生成初始种群P0和空存档P0（存档大小固定）
2. 适应度分配 ：计算每个个体的强度值S(i)（被i支配的解数），进而得到原始适应度R(i)（支配i的解数之和），再结合近邻密度D(i)得到最终适应度F(i)=R(i)+D(i)
3. 环境选择 ：将P和P中所有非支配解（F<1）复制到下一代存档，若存档超载则通过 截断操作 删除密集个体；若不足则用支配解填充
4. 交配选择 ：对存档个体进行锦标赛选择放入交配池
5. 变异 ：重组和变异生成新种群，迭代

改进点（对比SPEA）

• 精细适应度 ：同时考虑支配和被支配关系，避免选择压力丧失
• 近邻密度估计 ：用第k近邻距离的倒数作为密度，更精确
• 固定存档大小 + 边界保留截断 ：删除密集个体时优先保留边界解

应用场景

背包问题、连续变量优化（如ZDT系列测试函数）。

3. PAES：简单高效的"局部搜索专家"

PAES（Pareto Archived Evolution Strategy） 由Knowles和Corne在1999年提出，是一种基于(1+1)进化策略的算法。

原理本质

维护一个 父个体 和一个 外部存档 （存储历史非支配解）。父代通过变异产生子代，与父代和存档比较后决定是否替换。用 自适应网格 将目标空间分割，通过网格拥挤度维持多样性。

核心步骤

1. 初始化 ：随机生成父个体，评估后加入存档
2. 变异 ：对父个体进行多项式变异生成子代
3. 比较与归档：

• 若存档未满 → 子加入存档
• 若存档已满且子位于更稀疏网格 → 替换最密集网格中的解
• 若子代被存档中任一解支配 → 丢弃子代
• 若子代支配存档中某些解 → 删除被支配解，子加入存档并成为新父代
• 若互不支配 → 根据网格拥挤度决定

1. 迭代 ：重复2-3直至终止

优势

结构简单，参数少，计算开销小，适合嵌入式系统等资源受限环境。

应用案例

Ms. Pac-Man游戏AI控制器的神经网络优化（同时最大化得分、最小化神经元数）。

4. PESA-II：基于网格的"区域选择者"

PESA-II（Pareto Envelope-based Selection Algorithm II） 是Corne等人在2001年提出的改进版本。

原理本质

与PESA-I的核心区别在于 选择单元从个体变为超网格单元 。将目标空间划分为网格，每个网格单元内所有个体视为一个整体，选择时基于网格的密度进行。

核心步骤

1. 初始化 ：随机生成种群，更新外部存档（非支配解）
2. 网格划分 ：将目标空间分割成超网格，记录每个网格内的个体数
3. 选择 ： 基于网格的锦标赛选择 ——随机选两个网格，从密度较小的网格中随机选一个个体作为父代
4. 进化 ：交叉、变异生成子代，更新存档和网格信息
5. 迭代 ：重复3-4直至终止

优势

相比PESA-I（基于个体选择），区域选择能更好地维持多样性，选择压力更均匀。

应用场景

需要快速收敛且对分布性要求较高的问题。

5. MOGTO：融合多种策略的"新秀"

MOGTO（Multi-objective Gorilla Troops Optimizer） 是基于人工大猩猩部队算法的多目标改进版本。

原理本质

在原始GTO基础上引入 Pareto支配 概念，同时集成 蒙特卡洛树搜索 （增强全局探索）和 天牛须搜索 （增强局部开发），用 外部档案集 存储非支配解。

核心创新

• 探索阶段优化 ：用蒙特卡洛树搜索对三种探索机制进行优化，提高全局搜索能力
• 开发阶段优化 ：结合天牛须左右须寻优和黄金正弦策略，引导个体扩大搜索范围，避免局部最优
• 外部档案维护 ：存储互不支配解集，防止优秀解丢失

验证结果

在12个基准测试函数上优于其他6种常见算法，并在曲柄摇杆机构优化设计中验证了工程实用性。

6. AP-εPSO：引入偏好的"决策者助手"

AP-εPSO（Angle Preference based ε-Pareto Particle Swarm Optimization） 是结合角度偏好和ε-Pareto支配的粒子群算法。

原理本质

在标准粒子群框架下，引入 ε-Pareto支配 （放松支配条件以增加选择压力）和 角度偏好 （将决策者偏好方向融入搜索），配合 拥挤度判定 和 突变操作 ，用 外部归档集 存储非支配解。

核心机制

• ε-Pareto支配 ：允许在一定容差范围内放松支配关系，增加高维问题中的选择压力
• 角度偏好 ：根据决策者指定的偏好方向（权重向量），计算解与偏好方向的夹角，优先选择夹角小的解
• 三归档集变体（AP-TPSO） ：进一步将归档集分为三类，并引入高斯混沌突变

应用验证

成功应用于 出租车合乘定价模型 ，同时优化司机收益和乘客费用。

3

算法对比与选择指南

选择建议

• 通用首选 ：NSGA-II（成熟稳定，应用广泛）
• 追求解质量 ：SPEA2（精细适应度分配）
• 资源受限 ：PAES（简单高效）
• 快速收敛 ：PESA-II（基于网格的区域选择）
• 复杂非线性 ：MOGTO（多策略融合防陷入局部最优）
• 含决策偏好/高维 ：AP-εPSO（角度偏好+ε支配）