Abstract:

Constrained Multi-Objective Evolutionary Algorithms （CMOEAs） are metaheuristics tailored for solving constrained multi-objective optimization problems. These algorithms use population-based stochastic search paradigms， striking balance between objectives and constrains on various optimization problems. However， they do not take advantage of gradient information of the functions， exhibiting slow convergence speed on complex problems. Nevertheless， the introduction of gradients is not trivial， as the calculation of the gradients of all the objectives and constraints are computationally expensive， and the conflicts between objectives and constraints make it difficult to determine the gradient directions. Therefore， an optimization algorithm combining evolutionary computation and Gradient Descent （GD） was proposed， namely CMOEA with Multiple Stages assisted by Gradients （CMOEA-MSG）. It consists of two stages： at the first stage， helper problems were constructed and either the gradients of objectives or the gradients of constraints were calculated， which were used to update solutions and drive the population to quickly converge towards feasible regions； at the second stage， the constraint-first principle was utilized to solve the original problem， so as to ensure the feasibility and diversity of the population. Compared with peer algorithms on LIR-CMOP， MW and DAS-CMOP test sets， CMOEA-MSG is verified to be more effective for solving constrained multi-objective optimization problems.

Key words: constrained multi-objective optimization, Evolutionary Algorithm (EA), Gradient Descent (GD), multi-stage search

摘要：

约束多目标进化算法（CMOEA）是一类专门为解决约束多目标优化问题而设计的元启发式算法。这类算法利用基于种群的黑盒随机搜索模式，可以在不同优化问题上达到目标与约束之间的有效平衡；然而它们未有效利用函数的梯度信息，在复杂问题上收敛过慢。但引入梯度信息不是一个简单的过程，同时计算所有目标和约束的梯度会消耗大量的计算资源，且目标和约束之间的矛盾会使梯度方向难以确定。为此，提出一种进化计算和梯度下降（GD）的联合优化算法——基于梯度辅助的多阶段约束多目标进化算法（CMOEA-MSG）。该算法包括两个阶段：在第一阶段，算法通过构建辅助问题并有选择性地计算目标或约束的梯度更新解，使种群快速收敛至可行区域；在第二阶段，算法采用约束优先原则求解原问题，保证种群的可行性和多样性。与现有同类算法在LIR-CMOP、MW和DAS-CMOP三个测试集上的对比结果表明，CMOEA-MSG可以更有效地解决约束多目标优化问题。

关键词: 约束多目标优化, 进化算法, 梯度下降, 多阶段搜索