「工业人工智能」基于集成填充准则的多阶段代理模型辅助进化优化算法

引言

在复杂工业过程优化中，可行域复杂的昂贵约束多目标优化问题（ECMOPs）普遍存在，主要包括：1）可行域是不连续的，即约束帕累托最优前沿（CPF）被分割成多个片段。如图1所示，左侧展示了不可行障碍将局部可行区域隔离。在函数评估有限的情况下，搜索往往只能到达远离CPF的局部可行区域，因此穿越这些不可行障碍并接近CPF的可能性大大降低。右侧显示CPF被不可行区域划分为多个片段，这使得算法在跨越不可行障碍进行搜索和探索更多可行区域时面临更大的挑战。2）ECMOPs的可行域可能非常窄。因此，初始解可能远离CPF，这使得在函数评估数量有限的情况下，同样难以在接近CPF的地方找到解。

图1 不可行障碍在ECMOPs中的例子

为解决ECMOPs问题中的可行域复杂问题，最近东北大学流程工业综合自动化国家重点实验室联合西湖大学可信及通用人工智能实验室在计算智能顶级期刊IEEE TEVC上发表了一篇《A Multi-Stage Expensive Constrained Multi-Objective Optimization Algorithm Based on Ensemble Infill Criterion》的文章。该方法提出一种基于集成填充准则和多阶段搜索的策略，可实现高效求解具有复杂可行域的昂贵约束多目标优化问题。让我们一起来了解一下吧！

 

原文链接：https://ieeexplore.ieee.org/document/10530447

1.研究背景

在ECMOPs中实现可行性、收敛性、多样性、探索和利用之间的平衡是复杂的，依赖单一的填充准则更具挑战性，这主要是因为：

首先，在收敛性和多样性之间取得平衡是一个挑战。算法的性能要求在不同的搜索阶段有所不同，如图1右侧所示。CPF不连续的情况下，一旦在CPF附近实现收敛，则需要将重点转向促进多样性以提高整体性能。

其次，在多个目标冲突的情况下平衡探索和利用具有挑战性。例如，代理模型在逼近每个目标函数景观时的精度可能会有所不同。单纯考虑收敛性和多样性之间的平衡，对不同目标函数需要不同程度的探索和利用，降低了寻找最优解的效率。

最后，平衡约束和目标之间的优先级具有挑战。在具有多个不可行障碍的ECMOPs，如图1左侧所示，有必要将目标的搜索优先级高于约束。这种优先级排序确保了搜索过程能够有效地穿过不可行区域，同时引导搜索走向无约束帕累托最优前沿（UPF）。然后，将搜索拉回到CPF。

为解决这些挑战，本文首先结合多个独立的填充准则，提出了一种新的填充准则，以改善候选解的选择。通过整合多个填充准则，旨在更好地平衡收敛性与多样性、目标与约束之间的探索与利用性能。填充准则从候选集中选择潜在解的有效性在很大程度上依赖于代理辅助搜索提供高质量候选解集的能力。然而，在ECMOPs的背景下，分离的可行区域对代理辅助搜索过程构成了重大挑战。这些挑战是由于约束函数的复杂性和多个约束的组合而产生的，这导致了复杂的约束景观。

虽然在进化计算领域，一些多阶段约束多目标进化算法（CMOEAs）[3][4]被提出，通过逐渐增加对约束的考虑和利用不可行的解提高搜索性能来解决这些困难。但是，这些方法需要数以万计的函数评估才能获得满意的解。受此启发，本文又在集成填充准则的基础上本文还扩展了多阶CMOEAs的概念，提出了基于集成填充准则的多阶段代理模型辅助进化优化算法（EIC-MSSAEA），旨在消耗尽量少的函数评估就可以获得满意的解。

2. EIC-MSSAEA介绍

本节概述EIC-MSSAEA，并深入研究其两个关键部分：高斯过程（GP）辅助的多阶段优化和集成填充准则。图2提供了EIC-MSSAEA的算法框架图，以帮助理解，该图是针对具有两个目标和两个约束函数的ECMOPs。

图2. EIC-MSSAEA框架

2.1 算法框架

EIC-MSSAEA是一种迭代算法，每轮包含四个步骤。在迭代阶段，使用评估过的数据为每个目标和约束函数构建一个GP。根据可用的数据信息确定后续的优化阶段。每个阶段执行独立的优化，并且通过增加约束数量逐步增加问题的难度。下一步通过对目标和约束函数的GP近似模型来定义一个便宜的多目标优化问题。在Stage1阶段，重点仅放在目标函数上。在Stage2中，目标和一个约束函数被优化。在Stage3，所有约束函数都被考虑。然后，采用NSGA-III求解Stage1和Stage2中的便宜优化问题MOP_Stage1和MOP_Stage2，Stage3采用基于约束支配准则的NSGA-III-CDP求解便宜优化问题MOP_Stage3。通过优化便宜的问题，在每个阶段产生一个最优种群。值得注意的是，任何MOEA都可以求解MOP_Stage1和MOP_Stage2，而任何CMOEA可以求解MOP_Stage3。在第三步中，利用基于集成的填充准则从最优种群中选择最佳候选输入集，用于昂贵的函数评估。第四步，对选定的输入进行昂贵的评估，以获得相应的目标和约束函数值。然后，用新数据更新GP模型，EIC-MSSAEA进入下一个循环。

2.2 GP辅助的多阶段优化

对每个目标和约束函数建立GP模型之后，引入Stage Transition重新分配计算资源，确定当前的搜索阶段。Stage Transition的提出基于两个主要原因。首先，在某些ECMOPs中，CPF和UPF不相交，且它们之间存在显著距离，Stage1阶段忽略约束可能导致搜索偏离CPF，导致浪费评估，如图3所示。其次，在该ECMOPs中，减少约束条件后，子CPF仍然与CPF不相交，使得在Stage2中的搜索无效。为了避免在Stage1和Stage2中CPF和UPF距离较远的问题求解造成的函数评估浪费，EIC-MSSAEA首先利用前Tr轮得到的数据，在Stage1中函数评估数量达到3T_r时，根据约束违反值的差值和可行性率来检测当前问题的CPF是否与UPF距离较远。约束违反差值和可行率的计算公式为

图3 搜索偏离约束帕累托最优前沿

如果约束违反值差值大于等于0并且可行率等于0，则表明Stage1中的搜索偏离CPF，终止当前搜索阶段Stage1，并将剩余的函数评估分配给Stage3；如果没有，则继续从Stage1搜索。

在确定搜索阶段后，构造一个基于GP的廉价优化问题，每个阶段的优化问题都是不同的。例如，在复杂的ECMOPs中，CPF通常位于UPF附近。因此，在第一阶段，只考虑目标，可以克服不可行的障碍快速收敛到UPF附近。MOP_Stage1如下所示

在Stage1中，搜索被推到UPF附近。为了探索更多的局部可行区域并提高多样性，本文只考虑Stage2中可行率最低的约束。通过利用不可行解来增加子CPF区域的搜索，从而快速收敛到CPF。因此，在Stage2中构建的MOP_Stage1如下

在Stage2中，发现足够的可行区域之后，在Stage3中，需要提高解的可行性、收敛性和多样性。因此，在Stage3中构造的MOP_Stage3如下

以上三个搜索阶段的搜索行为如图4（a）-（d）所示，其中（a）和（b）是第一阶段中，Stage Transition讨论的搜索偏离最优前沿面和不偏离前沿面的情况。（c）和（d）分别对应第二和第三阶段。

图4 不同阶段的搜索行为示意图

2.3集成填充准则

在每个阶段搜索完获得最优种群，通过集成填充准则有效地选择高质量的解。在Stage1中，第一个准则ND-A使用非支配排序方法对候选解集P^*和档案Ar中的解进行排序，分别得到非支配解集P^*_nd和Ar_nd，接下来计算种群中非支配解与档案中非支配解集之间的角度

然后从非支配种群的个体中选出夹角最大的解。第一个被选出的解与它的预测目标值一起存储在Ar_nd中，并从P^*_nd中删除，以增强解的多样性。选择后续解的过程遵循串行的方式。

所提出的第二填充准则成员ND-ΔPBI来选择第二个候选解。首先对P^*_nd和Ar_nd进行归一化，根据解到参考向量V的垂直距离安排Ar_nd，识别出非空的参考向量V_n，并在Ar_nd中计算每个解的PBI值。

使用同样的方法，将P^*_nd中的解排列到V_n中，并计算P^*_nd中每个解的PBI值。最后，计算每个参考向量下PBI提升最大的解，PBI提升计算如下

EIC的第三个成员是EPDI，它考虑模型的不确定性，以平衡探索和利用。首先，靠近和多样性函数（Proximity and Diversity，PD）可以有效地衡量收敛性和多样性，并且与其它标量函数相比，PD具有更好的通用性[5]。PD函数定义如下

其次，PD提升函数（PDI）定义如下

 EPDI可推导为

在Stage2和Stage3中，解的可行性在每个成员中优先级更高。因此，在ND-A和ND-ΔPBI中，可行支配准则应用于P^*_nd和Ar_nd，以选择最佳可行解。然后，采用最大角度和ΔPBI准则选择最优解进行评价。在EIC的第三成员中，也考虑了约束函数的不确定性信息。如果在Ar中没有可行解，首先利用PoF找到一个可行解，然后以EPDI和PoF的乘积作为填充准则。为了更清晰地了解EIC, EIC成员的作用如图5所示。Stage1忽略约束，而在Stage2和Stage3中，约束具有更高的优先级。Stage1和Stage2/Stage3旨在平衡目标和约束。此外，六个成员共同实现了可行性、收敛性、多样性、探索性和利用性的平衡。

图5 每个成员在集成填充准则中的作用

3 仿真实验

3.1 消融实验

3.1.1GP辅助的多阶段搜索的消融实验

EIC-MSSAEA结合了三个独立的优化过程，为每个阶段分配一定数量的函数评估。为了评估每个阶段的有效性，本文将Stage2和Stage3（称为EIC-S2S3）的组合与Stage3单独（称为EIC-S3）进行比较，使用第三阶段作为基准算法。这种比较能够评估Stage2的影响。EIC-S3和EIC-S2S3的IGD结果总结在表1中。EIC-S2S3在14个测试实例中有8个优于EIC-S3，验证了Stgae2的有效性。

                       表1 EIC-S3和EIC-S2S3的IGD结果

与EIC-S3相比，EIC-S2S3专注于第二阶段的优化过程，只考虑一个约束。这种简化降低了问题的复杂性。通常，ECMOPs涉及多个约束，假设每个约束具有相同的难度，求解ECMOPs的复杂度取决于约束数量。约束条件越多，解决ECMOPs的难度就越大。相比之下，只有一个约束的问题相对容易解决。

EIC-S2S3利用不可行解加速收敛，通过只考虑一个约束而不是同时考虑所有约束来发现更多的可行区域。将EIC-S2S3与包含所有三个阶段的完整EIC-MSSAEA进行比较，以验证Stage1的有效性，如表2所示。EIC-MSSAEA在14个测试用例中的7个优于EIC-S2S3。这些实验结果证明了Stage1的有效性。

表2 EIC-S2S3和EIC-MSSAEA的IGD结果

与EIC-S2S3相比，EIC-MSSAEA增加了一个不考虑约束条件的优化阶段（Stage1）。这一阶段有助于搜索过程克服不可行的障碍，并向UPF附近收敛。随后，在Stage2和Stage3的引导下，促进了向UPF附近的CPF快速收敛。

3.1.2集成填充准则消融实验

为了充分了解每个成员在算法中的作用。首先，将每个成员替换为ND-A、ND-ΔPBI和EPDI，得到三个不同的变体:EICp11、EICp21和EICp31。通过比较这些变体的性能可以确定Stage1中每个成员的具体贡献。然后，本文将每个约束成员替换为ND-A-CDP、ND-ΔPBI-CDP和EPDI-PoF，创建EICp12、EICp22和EICp32的变体。通过对这些变体的比较评估，阐明了Stage2和Stage3中每个成员所扮演的不同角色。为了对算法性能进行综合评估，本文使用GD 、PD 、可行率（Feasible ratio，FR）、IGD和CPU时间等性能指标，排序结果如图6所示。

图6 每个成员分别在Stage1和Stage2/Stage3性能排序

图6左侧显示了EICp11、EICp21和EICp31各性能指标的平均排名。EICp11以精英解作为参考点，并根据角度选择它们周围的解，因此在FR中排名最高。强调了EICp11有效维持可行解的贡献。在GD方面，EICp21稳居榜首。EICp21在提高收敛性方面起关键作用。虽然EICp11、EICp21和EICp31都考虑了收敛性和多样性，但EICp31还加入了来自目标模型的不确定信息，以提高探索和开发性能。EICp31在PD和IGD中排名最高，说明了其贡献。然而，EICp31的计算效率最低。

图6右侧总结了每个指标在LIRCMOP上的EICp12、EICp22和EICp32的平均排名结果。EICp12在FR中排名第一，说明它对维持可行域内可行解的贡献最大。EICp22在GD中排名第一，表明其对提高收敛性贡献最大。虽然EICp12、EICp22 和EICp32都考虑了可行性、收敛性和多样性，但EICp32额外加入了来自目标和约束模型的不确定信息，以提高探索和开发性能。EICp32在PD和IGD中排名最高，说明了其贡献。然而，EICp32在CPU时间上排名最后。

3.2 与其它算法比较

将EIC-MSSAEA与ASA-MOEA/D[6]，MGSAEA[7]，KTS[8]，USeMOC[9]，HSMEA[10]，EIM-PoF[11]，MultiObjectiveEGO[12]在LIRCMOP ，MW等标准测试问题上进行比较。如表3所示，所提算法在整体上实现了最好的结果。

表3 与其它算法比较的IGD结果

此外，图7给出了所有算法在LIRCMOP13上获得的最小IGD对应的解分布。与其它算法相比，EIC-MSSAEA获得的解更接近CPF，这一结果加强了本文方法的有效性。

图7 ASA-MOEA/D、MGSAEA、KTS、USeMOC、 HSMEA、EIM-PoF、MultiObjectiveEGO和EIC-                  MSSAEA在LIRCMOP13上得到的最小IGD值对应的  解的分布

3.3 与无约束昂贵多目标进化算法的比较

EIC-MSSAEA具有很强的灵活性，其第一阶段称为EIC-S1，可以用来解决EMOPs。为了测试EIC-S1的性能，在两个无约束多目标标准测试问题上与利用填充准则发展的最先进算法进行了比较，实验结果如表4所示。EIC-S1在三目标的测试问题中， 16例中分别有11例、12例和10例优于ABSAEA、EIMEGO和NSGA-III-EHVI。上述统计结果验证了EIC-S1在昂贵无约束多目标测试问题上的显著性能。

表4 ABSAEA、EIMEGO、NSGA-III-EHVI和EIC-S1在 DTLZ和WFG上获得的IGD值

4. 总结

本章提出一种基于填充准则的多阶段的SAEA（EIC-MSSAEA）用于求解ECMOPs。该算法包括GP辅助的多阶段优化和集成填充准则。对于CPF不连续且可行域较小的约束多目标优化问题，多阶段优化过程旨在通过克服不可行障碍来快速逼近CPF。在每个阶段，集成填充准则根据可行性、收敛性、多样性、探索性和利用性选择最优解进行评估。在有约束的标准测试问题上评估了该算法的性能，实验结果说明EIC-MSSAEA在处理具有复杂可行域的ECMOPs表现出了良好的性能。

需要注意的是，集成填充准则的一个成员计算积分需要从多维的目标空间采样，高维的目标空间会给填充准则的计算效率带来挑战。因此，EIC-MSSAEA不适合求解目标空间高维的ECMOPs。

参考文献

[1] D. Guo, Y. Jin, J. Ding, and T. Chai, “Heterogeneous ensemblebased infill criterion for evolutionary multiobjective optimization of expensive problems,” IEEE Trans. Cybern., vol. 49, no. 3, pp. 1012–1025, May. 2018.

[2]X. Wu, Q. Lin, J. Li, K. C. Tan, and V. C. Leung, “An ensemble surrogate-based coevolutionary algorithm for solving large-scale expensive optimization problems,” IEEE Trans. Cybern., vol. 53, no. 9, Sep. 2022.

[3]R. Sun, J. Zou, Y. Liu, S. Yang, and J. Zheng, “A multistage algorithm for solving multiobjective optimization problems with multiconstraints,” IEEE Trans. Evol. Comput., vol. 27, no. 5, pp. 1207–1219, Nov. 2022.

[4]H. Ma, H. Wei, Y. Tian, R. Cheng, and X. Zhang, “A multistage evolutionary algorithm for multi-objective optimization with complex constraints,” Inf. Sci., vol. 560, pp. 68–91, Jun. 2021.

[5]H. Ge, M. Zhao, L. Sun, Z. Wang, G. Tan, Q. Zhang, and C. P. Chen, “A many-objective evolutionary algorithm with two interacting processes: Cascade clustering and reference point incremental learning,” IEEE Trans. Evol. Comput., vol. 23, no. 4, pp. 572–586, Oct. 2018.

[6]Z. Yang, H. Qiu, L. Gao, L. Chen, and J. Liu, “Surrogate-assistedmoea/d for expensive constrained multi-objective optimization,” Inf. Sci., p. 119016, Aug. 2023.

[7] Y. Zhang, H. Jiang, Y. Tian, H. Ma, and X. Zhang, “Multigranularity surrogate modeling for evolutionary multiobjective optimization with expensive constraints,” IEEE Trans. Neural Netw. Learn. Syst., vol. 35, no. 3, pp. 2956–2968, Aug. 2023.

[8]Z. Song, H. Wang, B. Xue, M. Zhang, and Y. Jin, “Balancing objective optimization and constraint satisfaction in expensive constrained evolutionary multi-objective optimization,” IEEE Trans. Evol. Comput., Jul. 2023.

[9]S. Belakaria, A. Deshwal, and J. R. Doppa, “Uncertainty aware search framework for multi-objective bayesian optimization with constraints,” arXiv preprint arXiv:2008.07029, 2020.

[10]A. Habib, H. K. Singh, T. Chugh, T. Ray, and K. Miettinen, “A multiple surrogate assisted decomposition-based evolutionary algorithm for expensive multi/many-objective optimization,” IEEE Trans. Evol. Comput., vol. 23, no. 6, pp. 1000–1014, Feb. 2019.

[11]D. Zhan, Y. Cheng, and J. Liu, “Expected improvement matrixbased infill criteria for expensive multiobjective optimization,” IEEE Trans. Evol. Comput., vol. 21, no. 6, pp. 956–975, Apr. 2017.

[12]R. Hussein and K. Deb, “A generative kriging surrogate model for constrained and unconstrained multi-objective optimization,” in Proceedings of the Genetic and Evolutionary Computation Conference 2016, 2016, pp. 573–580.

初稿：吴昊峰

初审：颜学明

终审：金耀初