2.[论文解析] TSMC 2023 求解昂贵不等式约束优化问题的两阶段代理辅助差分进化算法_代理辅助算法

摘要

Constraint handling is a core part when using surrogate-assisted evolutionary algorithms (SAEAs) to solve expensive constrained optimization problems (ECOPs). However, most existing SAEAs for ECOPs train a surrogate for each constraint. With the number of constraints increasing, the training burden of surrogates becomes heavy and the efficiency of the algorithm is greatly reduced. To solve this issue, this article proposes an efficient two-stage surrogate-assisted differential evolution (eToSA-DE) algorithm to handle expensive inequality constraints. eToSA-DE trains one surrogate for the degree of constraint violation and the type of the surrogate varies during the evolution process. In the first stage when there are only a few feasible individuals, a Gaussian process regression model is trained to fit the degree of constraint violation. In the second stage when more feasible individuals are accumulated, a support vector machine classification model is trained to classify whether candidates are feasible. Both types of surrogates are constructed by individuals which are chosen by the boundary training data selection strategy. These selected individuals are located around the feasible boundaries and helpful for the surrogate to approximate the feasibility structure. Besides, a feasible exploration strategy is devised to search for promising areas. To alleviate the error caused by the regression model, a nearest neighbor rectification is adopted to modify the prediction results. Extensive experiments on benchmark test functions and two formulated engineering optimization problems demonstrate that the proposed method can get satisfactory optimization results and significantly improve the efficiency of the algorithm.

贡献

• 本文提出了用于 ECOP 的两阶段 eToSA-DE。第一阶段主要处理昂贵的约束。它的目的是探索可行的区域并帮助算法避免在不可行的候选区域上浪费大量评估。第二阶段主要处理目标。它的目的是在可行的领域探索接近最优的解决方案，直到评估完毕。因此，两阶段演化过程有助于对有限的昂贵评估进行适当的分配。

• 其次，我们将回归器和分类器结合起来，用于对应两个阶段的约束违规。在可行信息较少的第一阶段，GP回归器主要由不可行个体训练来探索可行区域。随着更多可行信息的积累，第二阶段开始，由可行个体和不可行个体构建SVM分类器，以局部区分候选者是否可行。本质上，约束的预测是一个二元分类问题，并且分类器比具有小训练数据集的回归器更鲁棒。因此，当更多的可行信息积累得足够多时，构建SVM来提高候选预测的鲁棒性。

• 设计了一种边界训练数据选择策略来为约束违反模型选择训练样本。该策略选择分散在可行边界周围的个体。这些数据有助于代理模型局部拟合可行性结构，从而提高预测的准确性。

相关工作

约束处理技术

约束处理技术（CHT）是约束优化的重要组成部分。它通常可以分为以下四类：

• 基于可行性的技术

• 基于惩罚的技术

• 基于优势的技术

• 混合技术

本文所提出的 eToSA-DE 使用混合技术来处理约束，该技术结合了可行性规则和基于惩罚的技术。

差分进化

进化优化器的搜索能力对SAEA的性能有很大影响。差分进化（DE）是一种高效的启发式算法，具有强大的搜索能力。它的进化过程简单，主要由变异、交叉、选择三个算子组成。DE有多种突变策略。本文利用DE/currentto-feasible/1和DE/best/1，配合二项式交叉作为进化优化器。

代理模型

代理是预测候选人的工具。在代理人的协助下，SAEA 可以减少昂贵的评估数量。eToSA-DE 在两种情况下采用两种进化策略的代理：第一个是GP回归模型，另一个是SVM分类模型。

• 高斯过程：

• 支持向量机

eToSA-DE框架

eToSA-DE的框架如上图所示。首先通过真实的目标函数和约束函数对档案进行初始化和评估。如果不满足终止条件，则由边界训练数据选择所选择的个体更新代理。之后，档案中最好的 NP 个体组成种群。它们产生后代来寻找有前途的候选人。然后，由训练有素的代理人预测后代。预测结果通过其最近邻进行修正，以减少预测误差的影响。最后，选择预测最好的候选人。如果所选候选人不在档案中，则将对其进行真实评估并添加到档案中。重复上述过程，直到用完昂贵评估次数。

模型管理

与大多数现有的 ECOP 的 SAEA 不同，eToSADE 仅训练两个代理。针对目标建立GP回归模型，针对约束违反程度建立另一个模型，有两种情况。具体来说，当可行区域信息较少时，建立GP回归模型。随着种群的进化，更多可行的信息被探索出来。在这种情况下，构建 SVM 分类模型来对候选是否可行进行分类。

另外，对于第一阶段的目标和约束的回归模型，由于预测误差而导致的错误排序可能会误导种群的进化。为了减少其负面影响，设计了最近邻校正来微调回归模型的预测结果。流程如下所示：

illustration_nearest_neighbor_rectification

总结

本文提出了一种高效的两阶段代理辅助DE来处理昂贵的不等式约束，将其命名为eToSA-DE。与大多数现有的 ECOP 的 SAEA 不同，eToSA-DE 仅针对约束违反程度训练一个代理来解决问题，从而仅提供约束违反情况。根据已知可行个体的数量，进化过程分为两个阶段。第一阶段，建立GP回归模型来搜索更多可行区域的信息。在第二阶段，构建SVM分类模型以进行鲁棒预测。为了适应更令人信服的可行性结构，设计了边界训练数据选择策略。它在可行的边界周围选择个体来训练代理人的约束。至于目标，GP 回归模型在每一代中都会由有前途的个体更新。为了减少回归模型的误差影响，对预测值进行最近邻校正。对于进化优化器，DE-current-to-feasible/1旨在探索更多可行信息，DE/best/1用于收敛。

对于未来的工作，如何提高 SAEA 的多目标 ECOP 效率是值得研究的。训练一个代理人了解违反约束的程度是一种潜在的方法。但应减少某一替代约束所造成的不利影响。