Abstract:

Constraint handling strategies of the existing constrained multi-objective algorithms fail to solve the problems with large infeasible regions effectively， resulting in population stagnation at the edge of infeasible regions. Besides， the higher requirements are proposed for the global search ability and the maintenance of diversity of the algorithms by the discontinuous problems with constraints. To solve the above problems， a Constrained Multi-Objective Evolutionary Algorithm based on Multi-Stage Search （CMOEA-MSS） was proposed， with different search strategies used in three stages. To make the population across large infeasible regions and approximate Pareto front quickly， in the first stage， a convergence indicator was used to guide the population search without considering the constraints. In the second stage， a set of uniformly distributed weight vectors were utilized to maintain the population diversity， and an improved epsilon constraint handling strategy was presented to retain high-quality solutions in infeasible regions. In the third stage， the constraint dominance principle was adopted， and the search preference would focus on the feasible regions to ensure the feasibility of the final solution set. CMOEA-MSS was compared with NSGA-Ⅱ+ARSBX （Nondominated Sorting Genetic Algorithm Ⅱ using Adaptive Rotation-based Simulated Binary crossover） and other algorithms on MW and DASCMOP test sets. Experimental results show that CMOEA-MSS obtains the best IGD （Inverted Generational Distance） values on seven test problems and the best HV （HyperVolume） values on five test problems on MW test set， and obtains the best IGD values on three test problems， the second best IGD values on two test problems and the best HV values on five test problems on DASCMOP test set. It can be seen that CMOEA-MSS has obvious advantages in solving discontinuous and multi-modal constrained multi-objective problems.

Key words: constrained multi-objective optimization, multi-stage search, constraint handling strategy, evolutionary algorithm, convergence, diversity

摘要：

现有约束多目标进化算法的约束处理策略无法有效解决具有大型不可行区域的问题，导致种群停滞在不可行区域的边缘；此外，约束条件下的不连续问题对算法的全局搜索能力以及多样性的维持提出了更高的要求。针对上述问题，提出了一种基于多阶段搜索的约束多目标进化算法（CMOEA-MSS），在该算法的3个阶段采用不同的搜索策略。为使种群快速穿越大型不可行区域并逼近Pareto前沿，所提算法在第一阶段不考虑约束条件，利用一种收敛性指标引导种群搜索；在第二阶段采用一组均匀分布的权重向量来维持种群的多样性，并提出一种改进的epsilon约束处理策略，以保留不可行区域中的高质量解；在第三阶段采用约束优先原则，将搜索偏好集中在可行区域以保证最终解集的可行性。CMOEA-MSS与NSGA-Ⅱ+ARSBX（Nondominated Sorting Genetic Algorithm Ⅱ using Adaptive Rotation-based Simulated Binary crossover）等算法在MW和DASCMOP测试集上对比的结果表明：在MW测试集上，CMOEA-MSS在7个测试问题上获得了最好的IGD（Inverted Generational Distance）值，在5个测试问题上获得了最好的HV（HyperVolume）值；在DASCMOP测试集上，CMOEA-MSS在3个测试问题上获得了最好的IGD值，在2个测试问题上取得了次好的IGD值，在5个测试问题上获得了最好的HV值。可见，CMOEA-MSS在处理不连续以及具有多模态性质的约束多目标问题时具有明显优势。

关键词: 约束多目标优化, 多阶段搜索, 约束处理策略, 进化算法, 收敛性, 多样性