基于ELECTRE-III法的高维多目标调和进化算法

易高明 耿秀荣

摘 要：针对基于Pareto支配的低维多目标进化算法在求解3个以上目标的高维多目标时出现收敛压力不足等问题，将调和模型中面向排序的ELECTRE-III引入高维多目标进化方法中，提出一种新的锦标赛选择算子。该算子包含两层操作，分别是快速非支配分层操作和同一非劣层中的赋值级别高于关系排序操作。将这种赋值级别高于关系构造的ELECRE-III排序法嵌入NSGA-II中并应用于高维多目标进化个体的优劣排序。对典型高维测试集WFG函数进行仿真实验，验证该高维多目标调和进化算法的有效性。

关键词：ELECTRE III方法;多目标进化算法;高维多目标;锦标赛选择;赋值级别高于关系

DOI：10. 11907/rjdk. 201488 开放科学（资源服务）标识码（OSID）：

中图分类号：TP312文献标识码：A 文章编号：1672-7800（2020）008-0089-06

Abstract： Aiming at the insufficient convergence pressure of low-dimensional and multi-objective evolutionary algorithms based on Pareto domination in solving three or more high-dimensional and multi-objective evolutionary algorithms， we introduce the ranking-oriented ELECTRE-III in the harmonic model into the high-dimensional and multi-objective evolutionary methods， and propose a new tournament selection operator. The operator consists of two layers of operations. The assignment level of fast non-dominated hierarchical operation and the same non-inferior layer is higher than that of relational sorting operation. The ELECRE-III ranking method with higher assignment level than relation construction is embedded in NSGA-II and applied to the ranking of evolutionary individuals in high-dimensional multi-objective problems. The simulation results of typical high-dimensional test set WFG function verify the effectiveness of the proposed harmonic evolutionary algorithm.

Key Words： ELECTRE III method;multi-objective evolution algorithm;many-objectives;competition selection;valued outranking relation

0 引言

多目標进化算法可有效求解2～3个目标优化问题，然而当目标个数超过3时，这类问题就变成高维多目标问题[1]。传统基于Pareto占优机制的多目标进化优化方法选择非支配解的压力极大降低，导致逼近真实Pareto前沿所需进化个体数量呈指数级增加。因此，基于绝对Pareto机制占优的多目标进化方法难以有效解决高维多目标问题[2]。

为了解决高维多目标优化问题，Ahmed [3]提出格支配占优的高维多目标进化算法，这是一类非常典型的细粒度Pareto占优方法。同时，研究者们开始关注第二级MOEs选择算子，即多样性保持算子，寄希望于在这个第二级算子上实施选择压力。Deb等[4]在NSGA-II基础上提出其改进版本NSGA-III，替换了NSGA-II中的拥挤距离算子;Ren等[5]提出对目标函数直线拟合并计算拟合函数的坡度差值，找出坡度差中最小目标，然后剔除对应的目标函数，达到目标降维目的;Beume等[6]提出S测度选择进化算法;Igel[7]设计多目标协方差矩阵进化方法等;Moen[8]提出TC-SEA，采取曼哈顿距离自动生成一系列分布均匀的参考点。然而上述方法依然是基于绝对Pareto选择压力以逼近真实前沿面，存在收敛性不足和分布性不均匀等问题。

本文提出一种新的高维多目标调和进化算法，可以有效克服Pareto关系下高维进化个体间存在的互不支配难题，并与具有代表性的两类高维多目标进化优化算法作对比，以验证本文算法有效性。

1 高维多目标优化问题

步骤2：考虑方案集中的全部方案对，根据方案[a]流出的有向弧数量和流入的有向弧数量之差[δ（a）]确定方案[a]的好坏，将最大[δ（a）]对应的[a]分到第一非劣集[D1]中。

步骤3：如果第一非劣集[D1]只包含一个方案，则可以删除第一层非劣集并在剩下的方案集[A]/[D1]上执行步骤2;否则，继续对第一非劣集[D1]执行与步骤2同样的操作，直到对[D1]中的各方案作出优劣排序。重复步骤2和步骤3排序全部方案。

上述排序方法为降序蒸馏法，也称正向排序法[14]。同样地，可采用反向排序法得到另一个方案集排序。之后，采用ELECTRE-II中的综合正向排序和反向排序方法给出方案的全部排序。