PPS-DMIA：基于定向交配与不可行解归档的约束多目标优化推拉搜索新方法

《IEEE Access》：PPS-DMIA: Directed Mating With Infeasible Solution Archive in Push and Pull Search for Constrained Multi-Objective Optimization

本文针对现实世界中普遍存在的约束多目标优化问题(CMOPs)，提出了一种名为PPS-DMIA（带定向交配和不可行解归档的推拉搜索）的新型进化算法。该研究旨在解决现有PPS-DM算法在定向交配效率方面的四个关键局限。通过引入全面归档更新、不可行解归档维护、直接差分向量生成以及基于标量化值的引导解选择四项核心机制，PPS-DMIA在LIR-CMOP基准测试问题上显著提升了搜索性能，超越了PPS-DM及其他先进算法，为复杂约束优化问题提供了更有效的解决方案。

　　

在工程设计、资源分配等众多现实场景中，决策者常常需要同时优化多个相互冲突的目标，并且必须满足一系列严格的约束条件，这类问题被统称为约束多目标优化问题(CMOPs)。传统的优化方法在处理此类复杂问题时往往力不从心，而进化算法(EAs)因其能够一次运行即可获得一组代表目标间最佳权衡的可行解而展现出巨大潜力。然而，如何高效地平衡目标优化与约束满足之间的关系，始终是该领域面临的核心挑战。

推拉搜索(PPS)框架为解决这一挑战提供了新思路。它将优化过程清晰地划分为两个阶段：推阶段忽略约束，专注于寻找具有优异目标值的解；拉阶段则转向寻找满足约束条件的可行解。尽管PPS框架表现出了良好的性能，但其改进版PPS-DM在利用可行解归档进行定向交配以加速拉阶段搜索时，仍存在几个关键问题：归档更新不充分导致交配机会减少；可行解稀缺时定向交配难以执行；差分向量未能直接指向引导解，削弱了搜索的方向性；引导解的选择未考虑焦点解的搜索方向。

为了突破这些局限，研究人员在《IEEE Access》上发表了他们的最新成果——PPS-DMIA算法。该研究通过四项创新机制显著提升了定向交配的效能：首先，算法会在每一代使用所有生成的解来全面更新归档，确保有价值的解不被遗漏；其次，引入了一个专门的不可行解归档，即使在可行解稀少时也能支持定向交配；第三，新的解生成直接使用引导解与焦点解之间的差分向量，增强了搜索的方向引导；最后，根据焦点解的搜索方向（由其权重向量λ^j定义），基于标量化函数值来选择引导解，使交配过程更具方向性。

在技术方法上，本研究主要基于推拉搜索(PPS)框架和差分进化(DE)算法。研究在LIR-CMOP1-12测试问题上进行了系统评估，种群规模N设为300，最大代数T_max为2000。性能评价采用倒代距离(IGD)和超体积(HV)指标，并通过Nemenyi检验进行统计显著性分析。同时，还设计了消融实验以验证各个新机制的具体贡献。

IV. CONVENTIONAL PPS 与 V. CONVENTIONAL PPS-DM

本章节回顾了传统的PPS和PPS-DM方法。PPS采用基于分解的MOEA/D框架，使用切比雪夫标量化函数g^te，并在推拉阶段采用不同的解更新策略。PPS-DM在此基础上引入了定向交配，在拉阶段从可行归档A中选取被焦点解x^j支配的解构成集合M，用于生成新解，以期加速向帕累托前沿(PF)的收敛。

VI. ISSUE FOCUS

本章节系统阐述了PPS-DM存在的四个问题(i)-(iv)，为提出新方法明确了改进方向。这些问题直接影响了定向交配的频率和效果，限制了算法在复杂CMOPs上的性能。

VII. PROPOSED PPS-DMIA

本章节详细介绍了提出的PPS-DMIA方法。其核心创新体现在四个方面：(i)全面归档机制，利用所有生成解集合Q更新可行归档A，增加了高质量解进入归档的机会；(ii)不可行归档机制，维护一个基于约束违反支配关系?_f+φ的非支配不可行解归档A‘，解决了可行解不足时定向交配难以触发的问题；(iii)直接差分机制，使用p¹- x^j的直接差分向量生成新解，使搜索直接指向引导解；(iv)标量化选择机制，从具有最小约束违反φ的解集M‘中，选择标量化函数g^te值最小的解作为p¹，确保了交配方向与焦点解的搜索方向λ^j一致。

VIII. EXPERIMENTAL SETTINGS

本章节说明了实验设置。选用LIR-CMOP1-12作为测试问题，这些问题的帕累托前沿(PF)与无约束帕累托前沿(UPF)关系各异，有助于全面评估算法性能。对比算法包括BiCo、CTAEA、CMOEA-MS等多种先进约束多目标优化算法。

IX. EXPERIMENTAL RESULTS AND DISCUSSION

A. OPTIMIZATION PERFORMANCE ON EACH PROBLEM

实验结果表明，在LIR-CMOP1-4和7-8等PF与UPF分离的问题上，PPS-DMIA凭借其不可行归档优势，能更早、更有效地找到可行区域，IGD值降低更快。即使在PF与UPF重合的LIR-CMOP5-6上，PPS-DMIA也因全面归档机制而表现优异。对于具有不连续PF和小可行区域的LIR-CMOP9-12，PPS-DMIA也展现出竞争力。

B. OPTIMIZATION PERFORMANCE ACROSS ALL PROBLEMS

在所有12个测试问题的综合排名中，PPS-DMIA在IGD和HV指标上均取得了最佳的平均排名，且Nemenyi检验表明其性能显著优于基准算法PPS-DM及其他对比算法。

C. ANALYSIS OF ALGORITHM BEHAVIOR

以LIR-CMOP2为例的算法行为分析直观展示了PPS-DMIA的优势。当可行归档A中解很少时，PPS-DM无法有效进行定向交合，而PPS-DMIA可利用不可行归档A‘顺利执行定向交配，使种群更接近PF。

D. ABLATION STUDY

消融研究清晰地证实了PPS-DMIA四项机制的有效性。性能按PPS-DM, PPS-DMIA-A, PPS-DMIA-B, PPS-DMIA-C, PPS-DMIA的顺序依次提升，表明每一项机制都对最终性能的提升做出了贡献。

综上所述，PPS-DMIA通过系统性地解决PPS-DM在定向交配方面的关键问题，有效提升了约束多目标优化的性能。其创新点在于充分利用搜索过程中产生的所有解（包括可行和不可行解）的信息来指导搜索，特别是在可行区域难以寻找的场景下展现出明显优势。这项研究不仅推动了推拉搜索框架的发展，也为处理复杂的现实世界优化问题提供了更强大的工具。未来的研究方向包括将PPS-DMIA的机制扩展到其他进化算法框架、处理高维多目标问题、离散优化问题以及在实际应用中验证其有效性。