学术研究报告：一种基于双种群协同进化求解不规则帕累托前沿多目标优化问题的新算法

一、 研究作者、机构及发表信息

本研究由Xiaoyu Zhong, Xiangjuan Yao, Dunwei Gong, Kangjia Qiao, Xingjia Gan, Zhangxiao Li 等六位研究人员合作完成。研究者来自中国矿业大学（江苏徐州）、青岛科技大学（山东青岛）、郑州大学（河南郑州）以及中南大学（湖南长沙）等多所高校。该研究成果以题为“A dual-population-based evolutionary algorithm for multi-objective optimization problems with irregular Pareto fronts”的学术论文形式，发表于Swarm and Evolutionary Computation 期刊的第87卷（2024年），文章识别码为101566。

二、 学术背景与研究目的

本研究属于计算智能与运筹学交叉领域，具体聚焦于多目标进化算法（Multi-Objective Evolutionary Algorithms, MOEAs）。在科学研究和工程实践中，普遍存在需要同时优化多个相互冲突目标的多目标优化问题（Multi-Objective Optimization Problems, MOPs）。解决此类问题的核心是找到一组在帕累托前沿（Pareto Front, PF）上分布均匀且收敛性好的最优解集。基于分解的MOEAs（如MOEA/D）通过一组预定义的权重向量（Weight Vectors）来引导搜索并维持种群多样性，在处理常规MOPs时表现出色。

然而，现实世界中许多MOPs具有不规则的帕累托前沿，例如不连续型（Disconnected）、退化型（Degenerated）、内凹型（Inverted）、尖锐/长尾型（Sharp Peak/Low Tail）等。当这类问题使用传统基于分解的MOEA求解时，面临两个关键挑战： 1. 权重向量分布失配：均匀分布的权重向量可能导致在PF不同区域获得的解分布极不均匀，甚至部分权重向量根本与真实PF没有交点，造成计算资源浪费。 2. 多样性维护困难：在退化、不连续等复杂PF上，算法难以探索整个前沿并均匀覆盖。

为解决上述问题，现有研究主要围绕两个方向展开：一是引入辅助种群（双种群）来增强多样性；二是动态调整权重向量以适应PF形状。但现有双种群算法存在协作效率低下和计算资源分配不合理的问题，而现有的权重向量调整策略（如基于个体提取、插值、聚类或机器学习的方法）在生成均匀分布的权重时，往往受限于相似性度量的选择，难以精准匹配不规则PF的几何结构。

基于此，本研究提出了一种新颖的基于双种群协同进化的进化算法，名为DPEA-IEAW（Dual-Population-based Evolutionary Algorithm with Individual Exploitation and Weight Vector Adaptation）。其研究目标在于：通过设计一个全局探索与局部挖掘分工明确、信息充分交换的协同进化框架，结合面向局部种群的个体挖掘操作和面向全局种群的基于引导位置的权重向量自适应策略，高效、鲁棒地求解具有各种不规则PF的MOPs。

三、 研究流程与方法详述

DPEA-IEAW算法的整体框架包含两个协同进化的种群：GlobPop（全局种群）和LocPop（局部种群）。GlobPop采用基于分解的方法（使用倒切比雪夫聚合函数）进行进化，主要负责在整个搜索空间进行全局探索，推动种群向PF收敛。LocPop则采用基于帕累托支配的方法维护一组非支配解，并通过提出的个体挖掘（Individual Exploitation）操作，重点开发GlobPop中未被充分探索但具有潜力的区域。两个种群通过信息交换相互促进。

详细工作流程如下：

1. 初始化阶段：

   • 使用两层法生成一组均匀分布在单位超平面上的初始权重向量集合Λ。
   • 随机生成大小为N的初始种群，将其同时赋给GlobPop和LocPop。
   • 初始化理想点（Ideal Point）和纳什点（Nadir Point）用于后续目标值归一化。

2. 主循环（进化过程）：

   • (1) 繁殖过程：

     • GlobPop繁殖：采用类似MOEA/D的方式选择邻域内或整个种群中的个体作为父代，使用模拟二进制交叉（SBX）和多项式变异（PM）生成子代个体。
     • LocPop繁殖（个体挖掘操作 - 算法核心创新点1）：此操作旨在利用LocPop中未被GlobPop青睐但可能具有潜力的个体，以补充GlobPop可能缺失的多样性。
       • 步骤A：匹配关系构建。首先，基于归一化后的目标值，计算每个权重向量对LocPop中个体的偏好（使用聚合函数值），以及每个个体对权重向量的偏好（使用到权重向量的垂直距离）。然后，应用基于不完全偏好列表的稳定匹配选择方法（STMIC），在权重向量集Λ和LocPop之间建立一对一的稳定匹配关系。
       • 步骤B：挖掘个体选择。匹配完成后，未能在LocPop中找到匹配对象的权重向量被认为是“无效的”（可能处于拥挤区域或无交点区域），而在Λ中未找到匹配对象的LocPop个体则被认为是“有潜力但未被GlobPop充分探索的”。后者被选为需要被挖掘的父代个体。
       • 步骤C：动态偏好列表长度。STMIC中偏好列表的长度r被设计为动态增加：进化初期r较小，鼓励更多挖掘以快速提升多样性；后期r增大，将更多计算资源留给收敛压力更大的GlobPop。r的取值范围被限定在[目标数m, 邻域大小T]之间。
       • 步骤D：子代生成。对选出的每个待挖掘个体，使用SBX和PM算子生成一个子代个体。

   • (2) 权重向量自适应过程（算法核心创新点2）：

     • 此过程在特定频率下（当LocPop大小等于N时）触发，旨在调整GlobPop的权重向量以更好地匹配真实PF。
     • 步骤A：识别有效权重向量。利用上一步个体挖掘中建立的稳定匹配关系M，将与LocPop中个体成功匹配的权重向量标记为“有效的”（Λ_m），剩余的标记为“待调整的”（Λ_u）。
     • 步骤B：提取引导位置（Guide-Position）。对于每个有效权重向量λ_k，算法估算其在PF上的交点位置，称为引导位置GP(k)。首先，根据角度关联规则找到GlobPop中与λ_k关联的个体子集S_k（若为空，则选择与λ_k夹角最小的个体）。然后，将S_k中所有个体投影到λ_k方向上，选择投影距离最小的个体作为“引导解”（Guide-Solution），该引导解在λ_k上的投影坐标即被计算为GP(k)。所有有效权重向量的GP(k)构成引导集GS。
     • 步骤C：生成新权重向量。为了替换掉无效的权重向量Λ_u，算法从LocPop及其新生成的子代中保留的非支配解集P_nd中，每次迭代选择与当前引导集GS欧氏距离最大的解x。然后，通过一个线性映射（将该解的目标向量投影到单位超平面）生成一个新的权重向量λ_new。之后将λ_new加入Λ，并将F’(x)加入GS。此过程循环进行，直到权重向量总数恢复为N。这种方法能确保新生成的权重向量指向当前解分布最稀疏、最未被探索的PF区域。

   • (3) 更新过程：

     • GlobPop更新：合并GlobPop及其子代，采用基于两级一对一稳定匹配的选择方法，从合并集中选出N个个体。该方法能尽可能保留不同子空间中的解，促进多样性。
     • LocPop更新：合并LocPop及其新挖掘的子代，首先移除所有被支配的解，然后若大小超过N，则使用文献中的种群维护机制进行修剪，保留高质量的帕累托非支配解。

   • (4) 参考点更新：更新理想点和纳什点，用于下一代的归一化。

3. 实验与评估流程：

   • 对比算法：为验证DPEA-IEAW的竞争力，研究选取了7个先进的对比算法，涵盖三大类：基于固定向量的算法（NSGA-III， BCE-MOEA/D）、基于权重调整的算法（ADAW， CARV-MOEA， MOEA/D-UR）和基于PF分布学习的算法（MOPSO/VPF， LMPFE）。
   • 测试问题集：实验在5个广泛使用的测试套件（DTLZ， IDTLZ， WFG， IMOP， UF）共37个测试函数，以及2个现实世界问题（多目标旅行商问题MOTSP，多目标背包问题MOKP）上进行。这些问题覆盖了线性、凹型、凸型、退化、不连续、内凹、部分前沿、复杂帕累托集等各种PF形状。
   • 性能指标：采用IGD+ 和超体积（HV） 两个综合性能指标，从收敛性和分布性两方面评估算法性能。每个算法在每个问题上独立运行30次，报告指标的平均值。
   • 统计检验：使用Wilcoxon秩和检验（显著性水平0.05）判断DPEA-IEAW与每个对比算法性能的统计显著性差异（更好/更差/相当）。

四、 主要研究结果与分析

1. 在具有规则PF问题上的表现：在DTLZ1-4、WFG4-9等线性或凹型PF问题上，经典的NSGA-III展现了明显优势。DPEA-IEAW紧随其后，表现优于多数对比算法，尤其在多数问题上显著优于其“前身”BCE-MOEA/D。这表明，即使在规则问题上，DPEA-IEAW提出的匹配式个体挖掘机制也能更有效地避免挖掘到“支配抵抗解”，从而合理分配资源，其协同框架是有效的。

2. 在尖锐峰/长尾型PF问题上的表现：在WFG1、IMOP1、IMOP2等问题上，DPEA-IEAW取得了令人满意的综合性能。IGD+和HV的统计结果显示，其表现与ADAW、LMPFE相当或更优。分析认为，DPEA-IEAW能够利用LocPop中位于极端边界区域的个体进行挖掘，产生更多样化的解，进而辅助生成分布更优的新权重向量，从而较好地覆盖这些难处理的区域。

3. 在退化型PF问题上的表现：在DTLZ5/6、WFG3、IMOP4等PF退化为狭窄区域的问题上，使用固定权重向量的算法（如NSGA-III， BCE-MOEA/D）表现不佳。DPEA-IEAW在绝大多数问题上取得了最佳或极具竞争力的结果。Wilcoxon检验表明，其在IGD+和HV指标上分别仅在2个和1个测试问题上显著差于某些对比算法。这有力证明了个体挖掘与权重向量自适应协同工作的策略对于处理这类高难度问题具有优秀的泛化能力。

4. 在不连续型PF问题上的表现：在DTLZ7、WFG2、IMOP3/5/8等问题上，DPEA-IEAW展现了强大的竞争力。统计结果显示，在IGD+指标上，其优于4/5到5/5的对比算法；在HV指标上，也优于多数对手。这表明，即使PF的间断部分严重破坏种群多样性，DPEA-IEAW的协同机制仍能有效维持解的均匀分布。

5. 在内凹型和部分PF问题上的表现：在IDTLZ1/2等内凹PF问题上，除BCE-MOEA/D和ADAW外，其他方法均明显逊于DPEA-IEAW。在IMOP6/7等部分PF问题上，DPEA-IEAW在两个问题上均取得了最佳性能。图8（研究报告原文提及，但未在提供文本中展示）的典型运行结果可视化清晰显示，只有DPEA-IEAW和LMPFE能够在整个PF上获得分布极佳的近似解集，而其他算法的解大多集中在PF的上边界。这直观证明了DPEA-IEAW算法探索整个（即使是部分）真实PF的能力。

6. 在具有复杂帕累托集问题上的表现：在UF1-UF10系列问题上，DPEA-IEAW同样表现稳健。统计检验结果表明，其与大多数对比算法的性能相当或更优，尤其在UF3、UF7等问题的HV指标上展现出优势，说明算法在处理决策空间复杂的实际问题时也具备潜力。

五、 研究结论与价值

本研究成功提出并验证了一种名为DPEA-IEAW的新型双种群协同进化算法，专门用于求解具有不规则帕累托前沿的多目标优化问题。核心结论在于：通过构建一个全局探索（GlobPop）与局部挖掘（LocPop）角色分明、紧密协作的进化框架，并集成两项关键技术——基于稳定匹配的个体挖掘操作和基于引导位置的权重向量自适应策略——能够有效克服传统方法在处理不规则PF时面临的多样性损失、资源浪费和权重失配等挑战。

该研究的科学价值主要体现在： 1. 方法论创新：提出了一种新的权重向量调整思路，即通过估算权重向量与PF的“引导位置”来更精准地刻画PF的几何分布，并以此为指导生成更均匀的新权重，这比简单的个体提取或随机插值方法更为可靠和有效。 2. 框架设计创新：明确了双种群在协同进化中的差异化角色与动态资源分配机制（通过动态变化的偏好列表长度r），提升了协作效率，避免了计算资源的无谓消耗。 3. 算法通用性提升：在涵盖37个标准测试问题和2个实际问题的广泛实验中，DPEA-IEAW相较于7种前沿算法，在绝大多数不规则PF问题上展现出优越或极具竞争力的性能，证明了其强大的鲁棒性和泛化能力。

其应用价值在于：为解决工程、金融、调度等众多领域中普遍存在的、具有复杂多目标权衡特性的实际问题，提供了一种更加强大和可靠的优化工具。例如，在涉及折衷面形状未知或异常复杂的系统设计、资源分配、参数调优等场景中，DPEA-IEAW有望帮助决策者获得一组覆盖更全面、分布更均匀的候选方案。

六、 研究亮点

1. 创新的“引导位置”概念与权重生成机制：不同于以往基于解集直接聚类或插值的方法，本研究提出通过估算每个有效权重向量在PF上的交点（引导位置）来构建一个对PF形状的“代理模型”，并基于此模型和距离最大原则生成新权重。这种方法能更直接地响应PF的真实几何结构，是算法成功的关键。
2. 高效的双种群协同与资源分配策略：利用STMIC建立两个种群间的匹配关系，不仅能精准识别需要挖掘的潜力个体，还能同步识别出需要调整的无效权重向量。结合动态调整的偏好列表长度，实现了对“探索”与“挖掘”计算资源的自适应、合理化分配。
3. 全面而严谨的验证：研究采用了大规模、多样化的测试集（37+2个问题），覆盖了几乎所有已知类型的不规则PF，并与多类代表性前沿算法进行了详尽的对比和统计分析，结论支撑坚实可靠。
4. 对实际问题的拓展验证：除了标准测试函数，研究还将算法应用于MOTSP和MOKP两个经典的多目标组合优化问题，初步证明了算法在现实场景中的适用潜力。

七、 其他有价值内容

研究报告还对DPEA-IEAW单代计算的时间复杂度进行了详细分析，指出其主要开销来自个体挖掘、权重向量自适应和更新过程，总复杂度在可接受范围内，显示了算法的实用性。此外，研究在讨论部分也坦诚指出了算法可能的局限，例如在处理内凹PF（IDTLZ2）时，若LocPop已分布很好，额外的个体挖掘可能会略微挤占GlobPop的评估次数。这为未来的改进方向提供了思路。最后，研究建议权重向量调整频率参数fr设为0.1，这是通过实验分析确定的较优值。