控制与决策  2020, Vol. 35 Issue (10): 2466-2474  
0

引用本文 [复制中英文]

顾清华, 莫明慧, 卢才武, 陈露. 求解约束高维多目标问题的分解约束支配NSGA-Ⅱ优化算法[J]. 控制与决策, 2020, 35(10): 2466-2474.
[复制中文]
GU Qing-hua, MO Ming-hui, LU Cai-wu, CHEN Lu. Decomposition-based constrained dominance principle NSGA-Ⅱ for constrained many-objective optimization problems[J]. Control and Decision, 2020, 35(10): 2466-2474. DOI: 10.13195/j.kzyjc.2019.0116.
[复制英文]

基金项目

国家自然科学基金项目(51774228, 51404182);陕西省自然科学基金项目(2017JM5043);陕西省教育厅专项科研计划项目(17JK0425)

作者简介

顾清华(1981-), 男, 教授, 博士生导师, 从事计算智能、群智能优化算法、复杂工业系统建模及仿真等研究, E-mail: qinghuagu@126.com;
莫明慧(1994-), 女, 硕士生, 从事计算智能算法理论的研究, E-mail: 1281800549@qq.com;
卢才武(1965-), 男, 教授, 博士生导师, 从事计算智能、群智能优化算法、复杂工业系统建模及仿真等研究, E-mail: 1114238783@qq.com;
陈露(1993-), 男, 博士生, 从事智能算法理论的研究, E-mail: 1015435316@qq.com

通讯作者

顾清华, E-mail: qinghuagu@126.com

文章历史

收稿日期:2019-01-24
修回日期:2019-04-27
求解约束高维多目标问题的分解约束支配NSGA-Ⅱ优化算法
顾清华 1,2, 莫明慧 2, 卢才武 1, 陈露 2     
1. 西安建筑科技大学~资源工程学院,西安 710055;
2. 西安建筑科技大学 管理学院,西安 710055
摘要:针对多目标进化算法处理约束高维多目标优化问题时出现解的分布性和收敛性差、易陷入局部最优解问题, 采用Pareto支配、分解与约束支配融合的方法, 提出一种基于分解约束支配NSGA-Ⅱ优化算法(DBCDP-NSGA-Ⅱ).该算法在保留NSGA-Ⅱ中快速非支配排序的基础上, 首先采用Pareto支配对种群进行支配排序; 然后根据解的性质采用分解约束支配(DBCDP)惩罚等价解, 保留稀疏区域的可行解和非可行解, 提高种群的分布性、多样性和收敛性; 最后采用个体到权重向量的垂直距离和拥挤度距离对临界值进行再排序, 直到选出N个最优个体进入下一次迭代.以约束DTLZ问题中C-DTLZ1、C-DTLZ2、DTLZ8、DTLZ9测试函数为例, 将所提出的算法与C-NSGA-Ⅱ、C-NSGA-Ⅲ、C-MOEA/D和C-MOEA/DD进行对比分析.仿真结果表明, DBCDP-NSGA-Ⅱ所得最优解分布更加均匀, 具有更好的全局收敛性.
关键词约束高维多目标    Deb约束支配    MOEA/D    NSGA-Ⅱ    分布性    收敛性    
Decomposition-based constrained dominance principle NSGA-Ⅱ for constrained many-objective optimization problems
GU Qing-hua 1,2, MO Ming-hui 2, LU Cai-wu 1, CHEN Lu 2     
1. School of Resources Engineering, Xi'an University of Architecture and Technology, Xi'an 710055, China;
2. School of Management, Xi'an University of Architecture and Technology, Xi'an 710055, China
Abstract: The distribution and convergence of solutions are poor when constrained many-objective optimization problems are solved with multi-objective evolutionary algorithm, which tend to fall into local optimal solutions. We propose a decomposition-based constrained dominance principle NSGA-Ⅱ(DBCDP-NSGA-Ⅱ) based on the fusion of Pareto dominance, decomposition and constraint dominance. In the study, based on retaining the fast non-dominant ranking in NSGA-Ⅱ, Pareto dominance is employed firstly to dominate population. Then according to the nature of the solution, the DBCDP is adopted to punish the equivalent solutions. The feasible and infeasible solutions in sparse regions are preserved to improve the distribution, diversity and convergence of the population. Finally, the critical values are reordered by the vertical distance and the crowding distance from the individual to the weight vector until N optimal individuals are selected for the next iteration. Using constrained DTLZ as an example, the algorithm is compared with C-NSGA-Ⅱ, C-MOEA/D, C-MOEA/DD and C-NSGA-Ⅲ. The results show that it has more uniform distribution and better global convergence performance than the other four algorithms.
Keywords: constrained many-objective optimization    Deb's constraint handling strategy    MOEA/D    NSGA-Ⅱ    distribution    convergence    
0 引言

高维多目标优化问题(many-objective optimization problems, MaOPs)[1]中的无约束问题研究已较为广泛.而约束优化问题研究较少, 主要原因是增加了约束条件后, 导致可行域不连通或者可行域变得较为复杂[2].但在实际工程应用中, 如复杂物流车辆调度[3]、城市水资源管理[4]等都是典型的约束高维多目标问题, 因此, 研究约束高维多目标优化对实际工业问题的解决具有重要的理论意义和实际价值.

为了求解约束MaOPs, 其关键性问题之一是保持目标与约束的平衡, 大多数进化算法都是以此为目的进行约束MaOPs求解[5].例如, 惩罚函数法采用惩罚因子来保持目标与约束之间的平衡, 将约束MaOPs转换为无约束MaOPs.文献[6]引入惩罚函数来惩罚非可行解, 对多目标差分进化算法(MOEA/D-DE)[7]进行了改进以处理约束多目标问题.采用惩罚函数简单且易实现, 但是针对不同的约束条件, 惩罚函数中的参数往往难以确定.为了避免调整惩罚参数, 学者们提出了一种分别比较目标和约束的约束处理方法, 如Deb约束支配原则[8]、Epsilon约束处理(EC)[9]、随机排序方法(SR)[10]等.由于Deb约束支配原则简单且没有额外的参数, 它是目前使用最多的约束处理方法.由于解决约束问题时MOEAD-DE需要两个惩罚参数, 为此, 文献[11]对MOEAD-DE进行了改进, 引入Deb约束准则, 提出了C-MOEA/D; 同时, 通过在NSGA-Ⅲ的精英选择算子中引入Deb约束准则, 扩展了NSGA-ⅢD在约束问题中的应用.文献[12]对MOEA/DD更新过程中融入了Deb约束准则, 而其他部分则保持不变, 成功地将MOEA/DD引入约束多目标领域, 提出了C-MOEA/DD.这3种算法在支配关系选择中, 当两个解都是非可行解时, 选择保留稀疏区域的非可行解; 当一个解为可行解, 另一个为非可行解时, 仍选择可行解.这导致算法过于保护可行解, 摒弃在稀疏区域且靠近可行域的非可行解.但是, 在求解约束高维多目标问题时, 保护在稀疏区域且靠近可行域的非可行解对于提高种群的分布性至关重要.文献[13]将Deb约束准则与NSGA-Ⅲ中参考点相融合, 通过小生境技术和关联参考点判断支配关系, 提出了一种基于参考点的约束支配关系(RPCDP), 该算法通过提高稀疏区域非可行解的保护, 从而提高最优解的分布性和收敛性.但RPCDP支配没有融入Pareto支配, 导致该算法过于依赖参考点.在求解约束MaOPs时, 以上算法在对解进行支配排序方面仍存在局限性, 需要进一步深入研究.

为了提高NSGA-Ⅱ求解约束高维多目标问题的收敛性、分布性和多样性, 本文提出一种求解约束高维多目标优化问题的分解约束支配NSGA-Ⅱ优化算法(decomposition-based constrained dominance principle NSGA-Ⅱ), 利用分解约束(decomposition-based constrained dominance principle, DBCDP)支配概念, 在保持NSGA-Ⅱ中快速非支配排序的基础上, 通过基于分解中的权重向量, 将目标空间均匀分割和解到权重向量的距离与约束处理技术相融合, 提高种群的分布性和收敛性, 然后通过保护稀疏区域的可行解和非可行解提高种群的多样性.

1 基本概念 1.1 约束高维多目标优化问题的数学描述

约束高维多目标优化问题通用的数学模型[14]

(1)

其中: M为目标函数的个数且M大于3, P为不等式约束的数目, Q为等式约束的数目, Ω为决策变量空间, x为一个候选解, FM个相互冲突的目标函数向量, RM为目标函数空间.

满足所有约束条件的解称为可行解.当存在一个约束条件不满足时, 该解称为非可行解.高维多目标优化问题的解不是唯一的, 而是一组均衡解, 称为最优非劣解集或Pareto最优解集, 并且这组解无差别.

1.2 NSGA-Ⅱ基本思想

快速非支配排序遗传算法(NSGA-Ⅱ)是在NSGA的基础上增加了精英保留策略.首先随机产生N个个体作为父代Pt, 通过交叉变异得到N个子代Qt, 将子代与父代合并形成Rt=PtQt, 从Rt中选出优先级高的N个个体进入下一代.在选择之前, 对Rt进行非支配排序.令支配个体a的个数为Xa, 支配集合Sa, 如果ab, 则个体a支配集合Sa=Sa∪{b}, 支配个体b的个数Xb=Xb+1.将X=0的个体放入F1中, F2为进化种群中去掉F1的支配个体的非支配个体, F3为进化种群中去掉F2的支配个体的非支配个体, 以此类推.将每个解划分等级, I={F1F2∪…∪ Fl-1}, T={F1F2∪…∪ Fl}, 当集合I的个数小于N时, T的个数大于N, Fl称为临界层, 使用拥挤度对临界层进行再排序, 选出N个最优个体进入下一代[8].

NSGA-Ⅱ在进行支配排序时, 仅依靠适应度函数选择最优解.当目标维度增大时, 这种支配关系会导致选择压力在接近最优前沿时明显降低, 使种群中出现大量等价解和相同解.为此, 本文提出在子代与父代合并后, 剔除相同解, 然后进行交叉和变异, 直到产生2N个不同的解, 再进行排序.在排序中, 使用分解和约束支配对Pareto支配出现的等价解进行惩罚, 从而提高算法的选择压力.

1.3 基于分解的多目标优化算法

基于帕累托支配的算法在处理高维多目标问题时性能较低, 而基于惩罚的边界交叉方法(PBI)性能表现较优[15]. PBI主要是使用解与理想点之间的距离在权重向量的投影d1和解到权重向量的距离d2来评估解的性质. d1d2的计算公式如下:

(2)
(3)

其中

(4)
(5)

M为目标函数的个数, W为权重向量的个数, R为一组具有1/p的均匀间距的向量, Ri表示M维向量, p为沿着每个目标坐标上的划分线, 而

(6)

是解x的归一化目标向量.

2 DBCDP-NSGA-Ⅱ算法 2.1 权重向量选取

使用Das等[16]提出的系统方法来生成一组均匀分布的权重向量.在具有均匀间隔δ=1/P(P=5)的三目标优化问题中生成权重向量, 使用式(4)得到231个均匀分布的权重向量.

2.2 种群关联权重向量

在生成权重向量之后, 对Rt种群个体的目标函数值进行规范化.首先确定要归一化的总体中每个目标函数fi的最小值fimin和最大值fimax, 以构造向量

(7)

然后对于每个解x, 用下面的公式计算归一化目标值Fi(x):

(8)

Rt种群个体归一化之后, 必须使每个个体关联到d2距离最短的权重向量, 并记录匹配到权重向量的解的个数, 使用RPj(u)表示分配给解u的权重向量的解的个数, 再根据RPj(u)判断解的密度.

2.3 分解约束支配策略 2.3.1 Deb约束支配

文献[17]对约束优化问题存在的问题和求解方法进行了概括, 由Deb[18]提出的可行性法则的性能表现最好.但在处理不连通的可行域或者前沿复杂的可行域多目标问题时, 如果xy为非可行解, 则仅采用约束违反度选取最优个体, 将使算法易陷入局部最优; 如果x为可行解, y为非可行解, 则选取可行解为较优个体, 将使算法过于保护可行解. Deb约束支配准则中, 每个个体仅根据Pareto支配、约束违反度两种信息来选取较优个体, 这使在稀疏区域并靠近可行区域的非可行解被淘汰, 从而导致种群探索未知领域的能力丧失.

约束违反度计算方法[7]

(9)

其中:当g(x) < 0时, g(x)=-g(x); 否则g(x)=0.当x满足约束条件中任何条件, 即x在可行域内时, VFD=0;当x不完全满足约束条件, 即x不在可行域内时, VFD≠0. VFD越小, x越靠近可行域.

2.3.2 分解约束支配准则

针对上述分析, 本文将Pareto支配、基于分解、约束支配这3种方法相融合, 提出一种新的支配方式——分解约束支配(DBCDP支配).该支配先使用Pareto支配对解进行快速排序, 再通过分解和约束支配对等价解进行惩罚. DBCDP支配主要是根据Pareto支配、约束违反度、解的密度3种信息来选取较优个体, 提高对稀疏区域并靠近可行区域的非可行解的保护.

由于uv两个解的性质不同, 分解约束支配可分为以下3种情况:

1) 当uv两个解均为可行解并为等价解时, 如果uv匹配到相同的权重向量, 则根据d1的值判断解的收敛情况, 选出距离理想点最近的解; 如果uv匹配到不相同的权重向量, 则根据RPj的值判断解的密度, 选出距离理想点最近和密度最小的解.

2) 当uv两个解都为非可行解并互不Pareto支配时, 如果uv依附相同的权重向量, 则根据约束违反度的大小判断解与可行域的距离, 选择靠近可行域的解; 否则, 根据约束违反度和RPj的值选择稀疏区域的解.

3) 当u为可行解, v为非可行解时, 根据RPj的值判断解的密度, 选出稀疏区域的解, 从而提高种群探索未知领域的能力.

根据以上3种情况的分析, 分解约束支配关系定义如下:给定一组权重向量R, uv是种群P中的两个解.如果下列语句之一成立, 则解u DBCDP支配解v:

1) uv同为可行解:

u Pareto支配v.

uv是Pareto等价解:

ⅰ) RP(u)=RP(v)并且d1(u) < d1(v);

ⅱ) RP(u)≠RP(v), d1(u) < d1(v)并且RPj(u) < RPj(v).

图 1所示, uvy为可行解并且两两Pareto等价, 因RP(y)=RP(v)并且d1(y) < d1(v), 故y DBCDP支配v.因RP(u)≠RP(v), d1(u) < d1(v), 并且RPj(u)=1 < RPj(v)=2, 故u DBCDP支配v.

图 1 uvy为可行解分布图

2) uv同为非可行解:

u Pareto支配v.

uv是Pareto等价解:

ⅰ) RP(u)=RP(v)且VFD(u) < VFD(v);

ⅱ) RP(u) ≠ RP(v), VFD(u) < VFD(v)且RPj(u) < RPj(v).

图 2所示, uvy为非可行解但两两Pareto等价, 因RP(y)=RP(v), VFD(u) < VFD(v), 故y DBCDP支配v.因RP(u)≠RP(v), VFD(u) < VFD(v), 且RPj(u)=1 < RPj(v)=2, 故u DBCDP支配v.

图 2 uvy为非可行解分布图

3) u为可行解, v为非可行解且RPj(u) < RPj(v).

为了清楚地说明DBCDP支配的作用, 图 3给出了使用Pareto支配和DBCDP支配对DTLZ8测试问题的19个随机生成解进行非支配排序的结果.对于每一个解, 在其右侧标记DBCDP支配排序, 左边标记帕累托支配秩(所在层数).

图 3 Pareto支配和DBCDP支配对DTLZ8的19个随机生成解进行排序

图 3可知, 构成第1层非支配前沿的4个帕累托等价解(A, B, C, D), 当使用DBCDP支配排序时, 该前沿被细分为两个DBCDP支配前沿:第1个是C1={A, B, D}, 包含两个极端个体AD以及具有最小d1距离和与最不拥挤的权重向量相关联的解B; 第2个是C2={C}, 其具有较大的距离d1和其相关权重向量的较大密度.根据d1和RPj, DBCDP支配对某些帕累托解的秩进行了惩罚.从图 3中还可以看到DBCDP支配有8层解, 而Pareto支配有6层解, 这表明DBCDP支配选择压力比传统的帕累托支配更强.从而进一步验证了DBCDP支配可以对帕累托等价解进行惩罚.

2.4 DBCDP-NSGA-Ⅱ算法流程

step 1:初始值设定.初始种群Pt, 决策变量数P, 目标函数个数M, 种群个数N, 权重向量大小为H=N, 迭代次数为t=0, 最大迭代次数Dmax.在决策空间中随机产生N个个体, 构成初始种群Pt, 并计算其目标函数值和约束违反度.按照Das提出的基于惩罚的边界交叉(PBI)方法生成均匀分布的权重向量集Zr.

step 2:对种群Pt进行交叉变异, 形成子代Qt, 计算子代Qt的目标函数值和约束违反度.将父代与子代合并得到Rt, 剔除相同解个体, 再进行交叉变异, 直到产生2N个不同的个体.

step 3:为Rt中的每个解寻找权重向量:

1) 对Rt进行归一化处理(找出Rt中每个目标函数的最小值和最大值以形成FminFmax), 计算Rt的理想点Z*.

2) 计算垂直距离d1d2, 根据d2将每个个体分配到其最近的权重向量, 并计算每个个体到权重向量的投影距离d1.求出每个权重向量关联解的个数.

step 4:排序:

1) 根据DBCDP支配方式求每个个体的秩;

2) 根据所求的秩进行严格排序.

step 5:锦标赛选择.利用上述排序结果, 将F1, F2, …, Fl-1按顺序存储, 再对临界层进行拥挤度排序, 直到选出N个最优个体, 形成新种群Pt+1.

step 6:清除种群的秩.

step 7:如果t+1大于最大迭代次数, 则结束运算; 否则, 返回step 2.

3 实验仿真与分析 3.1 测试函数

本实验研究DBCDP-NSGA-Ⅱ在约束DTLZ[19]测试问题上的性能. DTLZ测试函数是用于评价高维MOEAs性能最广泛的测试函数之一.本实验选取的约束DTLZ测试问题主要分为两类:第1类为只有一个约束条件的C-DTLZ1、C-DTLZ2;第2类为有M个约束条件的DTLZ8、DTLZ9.

C-DTLZ1: C-DTLZ1测试函数的最优前沿值与DTLZ1相同都为超平面, 并且在逼近最优前沿时存在由一个约束条件导致的不可行区域障碍, 从而使算法在收敛时困难增大.

C-DTLZ2:在DTLZ2问题中引入一个约束条件, 使DTLZ2的最优前沿变成不连通的最优前沿.只有位于半径为r的(M+1)超球体内的目标空间为可行域.该函数可测试算法是否具有处理不连通前沿的能力.

DTLZ8: DTLZ8测试函数的帕累托最优解是由一条直线和一个超平面组成, 其中直线由前(M-1)个约束条件确定, 超平面由第M个约束条件决定.

DTLZ9: DTLZ9测试函数的帕累托最优解是前(M-1)个目标函数约束的交集.在二维空间的帕累托最优解图中, 最优解是单位圆的四分之一圆弧.大多优化算法很难找到DTLZ9全局最优解, 只能找到某个区域的最优解.

C-DTLZ1、C-DTLZ2、DTLZ8、DTLZ9测试函数的决策变量均为[0, 1], 表达式及性质见表 1.

表 1 C-DTLZ1、C-DTLZ2、DTLZ8、DTLZ9测试函数表达式及性质
3.2 参数设置与算法对比

实验环境: Inter Core(TM)i5-2450M CPU, 内存为4 GB, Window10操作系统, MatlabR2017a版本.

参数设置:决策变量个数=10×目标函数个数, 目标函数个数M=5, 8, 12, 16, 20, 种群大小为100.文献[15]使用覆盖PF*的权重向量来保护算法多样性, 所以权重向量的数量与种群大小相同.交叉方式选择模拟二进制, 交叉率=0.5, 突变率=0.02.突变步长=0.1×(决策变量上限值-决策变量下限值), 最大迭代次数为100.

对比算法如下:为了验证本文所提出的DBCDP-NSGA-Ⅱ算法, 选择引入Deb约束准则的NSGA-Ⅱ(C-NSGA-Ⅱ)、C-NSGA-Ⅲ、C-MOEA/D、C-MOEA/DD这4种约束多目标优化算法进行对比实验研究.

3.3 性能指标

为了比较不同算法的性能, 选择反向世代距离(IGD)[20]作为评价算法的性能指标. IGD可以测量MOEA产生的所有近似解到真实PF*的平均距离. IGD的值越低, 表示得到的解集合越接近PF*.此指标能够综合评估算法的收敛性和分布性.

3.4 结果分析

本文给出了DBCDP-NSGA-Ⅱ算法在C-DTLZ1、C-DTLZ2、DTLZ8、DTLZ9测试问题上所得到的结果, 并与C-NSGA-Ⅱ、C-MOEA/D、C-MOEA/DD和C-NSGA-Ⅲ进行比较.在结果比较中, 使用Wilcoxon秩和检验的方式[21]比较与检测算法之间的差异.在置信度为95 %的情况下, 用符号“+”、“-”、“=”表示统计检验的结果. “+”表示显著优于、“-”表示显著劣于、“=”表示无差异于DBCDP-NSGA-Ⅱ.例如, 表 2中当M=5时, C-NSGA-Ⅱ的IGD平均值和标准差“2.618 2e-1-”表示DBCDP-NSGA-Ⅱ在置信度为95 %的情况下, 显著优于C-NSGA-Ⅱ.

表 2 C-DTLZ1、C-DTLZ2测试函数的IGD平均值和标准差

表 2可知, 在只有一个约束条件的C-DTLZ1、C-DTLZ2测试函数中, DBCDP-NSGA-Ⅱ求出IGD的结果相对较小, 所求最优解显著优于C-NSGA-Ⅱ、C-NSGA-Ⅲ、C-MOEA/D、C-MOEA/DD.而C-NSGA-Ⅱ和C-MOEA/D在C-DTLZ1、C-DTLZ2测试问题中所求IGD值较大, 表明这两种算法没有准确地找到可行域的位置.主要原因是当目标个数增加时, 一个解支配另一个解的能力下降, 而且这两种算法过于强调可行解支配非可行解, 使算法易陷入局部最优解.在C-DTLZ1的例子中当M=5时, C-NSGA-Ⅲ显著优于DBCDP-NSGA-Ⅱ.对于凹函数C-DTLZ2, 当M=12, 16时, C-MOEA/DD取得仅次于DBCDP-NSGA-Ⅱ的最优值.主要原因是C-NSGA-Ⅲ算法过于摒弃在稀疏区域且靠近可行域的非可行解. C-MOEA/DD虽然在锦标赛选择阶段保留了稀疏区域的非可行解, 但在支配阶段过于强调可行解支配非可行解. DBCDP-NSGA-Ⅱ在锦标赛选择、支配两个阶段都强调了保留稀疏区域的非可行解.因此才能取得更好的结果.

表 3中可看出, 对于第2类有M个约束条件的DTLZ8、DTLZ9测试问题, DBCDP-NSGA-Ⅱ求出IGD的结果相对较小, 所求最优解显著优于C-NSGA-Ⅱ、C-NSGA-Ⅲ、C-MOEA/D、C-MOEA/DD.而C-NSGA-Ⅱ、C-MOEA/D仍没取得较好的最优解.在由一条直线和一个超平面组成的DTLZ8例子中, 当M=12时, C-MOEA/DD取得最优前沿值, C-NSGA-Ⅲ结果显著优于DBCDP-NSGA-Ⅱ.当M=5, 16, 20时, C-MOEA/DD结果仅次于DBCDP-NSGA-Ⅱ.对于Pareto前沿由一条曲线组成的DTLZ9测试函数, 当M=5, 12时, C-MOEA/DD仅次于DBCDP-NSGA-Ⅱ的结果.当M=16时, C-NSGA-Ⅲ显著优于DBCDP-NSGA-Ⅱ的结果. C-NSGA-Ⅲ、C-MOEA/DD都通过参考点将目标空间均匀分割, 并将解与参考点一一对应. DBCDP-NSGA-Ⅱ采用了均匀分布的权重向量, 将解分配到离自己最近的区域内, 不存在一一对应关系, 从而提高了种群的均匀分布.

表 3 DTLZ8、DTLZ9测试函数的IGD平均值和标准差

图 4从a、b、c这3个角度展示了当M=3时迭代50次C-NSGA-Ⅱ、C-NSGA-Ⅲ、C-MOEA/D、C-MOEA/DD、DBCDP-NSGA-Ⅱ的DTLZ8测试函数结果.这些结果显示: C-NSGA-Ⅱ解的分布性差; 而C-NSGA-Ⅲ、C-MOEA/D、C-MOEA/DD、DBCDP-NSGA-Ⅱ的解在直线和超平面上分布较均匀.

图 4 C-NSGA-Ⅱ、C-NSGA-Ⅲ、C-MOEA/D、C-MOEA/DD、DBCDP-NSGA-Ⅱ在DTLZ8测试函数中的结果

图 5从a、b、c这3个角度展示了当M=3时迭代50次C-NSGA-Ⅱ、C-NSGA-Ⅲ、C-MOEA/D、C-MOEA /DD、DBCDP-NSGA-Ⅱ的DTLZ9测试函数结果.这些结果显示, C-NSGA-Ⅲ、C-MOEA/DD、DBCDP-NSGA-Ⅱ分布较广, 并且DBCDP-NSGA-Ⅱ在曲线的端点处找到2个解.

图 5 C-NSGA-Ⅱ、C-NSGA-Ⅲ、C-MOEA/D、C-MOEA/DD、DBCDP-NSGA-Ⅱ在DTLZ9测试函数中的结果

从Wilcoxon秩和检验的结果中可以得出, 在20组数学实验中, DBCDP-NSGA-Ⅱ比C-NSGA-Ⅱ优20次, DBCDP-NSGA-Ⅱ比C-NSGA-Ⅲ优17次, DBCDP-NSGAII比C-MOEA/D优20次, DBCDP-NSGA-Ⅱ比C-MOEA/DD优18次.由此可以看出, 在C-DTLZ1、C-DTLZ2、DTLZ8、DTLZ9测试问题中, DBCDP-NSGA-Ⅱ相对于C-NSGA-Ⅱ、C-NSGA-Ⅲ、C-MOEA/D、C-MOEA/DD而言, 在IGD指标上取得了较好的结果.

表 2表 3图 4图 5关于收敛性和分布性的综合结果得知, DBCDP-NSGA-Ⅱ具有较好的整体性能.仿真结果表明, 本文采用Pareto支配与基于分解的方法相融合的DBCDP支配, 成功地发挥了两种方法各自的优势.

4 结论

本文综合考虑Pareto支配、分解和约束支配3种方法的优势, 提出了一种分解约束支配NSGA-Ⅱ优化算法.在支配排序中, 进行了Pareto支配排序, 并从解到权重向量的距离、解与理想点之间的距离在权重向量的投影、解的密度3个方面对等价解进行了惩罚和严格排序, 从而保留稀疏区域的可行解和非可行解, 提高了种群的收敛性和分布性.综合分析了该算法与其他4种算法在测试函数约束DTLZ上的结果比较, 结果分析表明, 所提出的算法能够提供整体性能最优的结果.下一步的研究方向将以新型支配关系来代替传统的Pareto支配求解约束高维多目标优化问题.

参考文献
[1]
Li B, Li J, Tang K, et al. Many-objective evolutionary algorithms: A survey[J]. Acm Computing Surveys, 2015, 48(1): 1-35.
[2]
Christian von Lücken, Benjamín Barán, Brizuela C. A survey on multi-objective evolutionary algorithms for many-objective problems[J]. Computational Optimization and Applications, 2014, 58(3): 707-756.
[3]
Mendes J B, Maia N A, Veloso R R. A hybrid multi-objective evolutionary algorithm for truck dispatching in open-pit-mining[J]. IEEE Latin America Transactions, 2016, 14(3): 1329-1334. DOI:10.1109/TLA.2016.7459617
[4]
Matrosov E S, Huskova I, Kasprzyk J R, et al. Many-objective optimization and visual analytics reveal key trade-offs for London's water supply[J]. Journal of Hydrology, 2015, 531: 1040-1053. DOI:10.1016/j.jhydrol.2015.11.003
[5]
Fan Z, Li W, Cai X, et al. Push and pull search for solving constrained multi-objective optimization problems[J]. Swarm and Evolutionary Computation, 2019, 44(1): 665-679.
[6]
Zhang Q, Li H. MOEA/D: A multi-objective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2008, 11(6): 712-731.
[7]
Li H, Zhang Q. Multi-objective optimization problems with complicated pareto sets, MOEA/D and NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(2): 284-302. DOI:10.1109/TEVC.2008.925798
[8]
Deb K, Pratap A, Agarwal S, et al. A fast and elitist multi-objective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182. DOI:10.1109/4235.996017
[9]
Takahama T, Sakai S. Constrained optimization by epsilon constrained particle swarm optimizer with epsilon-level control[C]. Soft Computing as Transdisciplinary Science and Technology. Berlin, Heidelberg: Springer, 2005: 1019-1029.
[10]
Runarsson T P, Yao X. Stochastic ranking for constrained evolutionary optimization[J]. IEEE Transactions on Evolutionary Computation, 2000, 4(3): 284-294. DOI:10.1109/4235.873238
[11]
Jain H, Deb K. An evolutionary many-objective optimization algorithm using reference-point based nondominated sorting approach, Part Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4): 602-622. DOI:10.1109/TEVC.2013.2281534
[12]
Li K, Deb K, Zhang Q, et al. An evolutionary many-objective optimization algorithm based on dominance and decomposition[J]. IEEE Transactions on Evolutionary Computation, 2015, 19(5): 694-716. DOI:10.1109/TEVC.2014.2373386
[13]
毕晓君, 王朝. 一种基于参考点约束支配的NSGA-Ⅲ算法[J]. 控制与决策, 2019, 34(2): 369-376.
(Bi X J, Wang C. A reference point constrained dominance-based NSGA-Ⅲ algorithm[J]. Control and Decision, 2019, 34(2): 369-376.)
[14]
刘建昌, 李飞, 王洪海, 等. 进化高维多目标优化算法研究综述[J]. 控制与决策, 2018, 33(5): 114-122.
(Liu J C, Li F, Wang H H, et al. Survey on evolutionary many-objective optimization algorithms[J]. Control and Decision, 2018, 33(5): 114-122.)
[15]
Elarbi M, Bechikh S, Gupta A, et al. A new decomposition-based NSGA-Ⅱ for many-objective optimization[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2017, 48(7): 1191-1210. DOI:10.1109/TSMC.2017.2654301
[16]
Das I, Dennis J E. Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems[J]. Siam Journal on Optimization, 1998, 8(3): 631-657. DOI:10.1137/S1052623496307510
[17]
李智勇, 黄滔, 陈少淼, 等. 约束优化进化算法综述[J]. 软件学报, 2017, 28(6): 1529-1546.
(Li Z Y, Huang T, Chen S M, et al. Overview of constrained optimization evolutionary algorithms[J]. Journal of Software, 2017, 28(6): 1529-1546.)
[18]
Deb K. An efficient constraint handling method for genetic algorithms[J]. Computer Methods in Applied Mechanics and Engineering, 2000, 186(2/4): 311-338.
[19]
Deb K, Thiele L, Laumanns M, et al. Scalable test problems for evolutionary multi-objective optimization[C]. Evolutionary Multi-objective Optimization. London: Springer, 2005: 105-145.
[20]
Zitzler E, Thiele L, Laumanns M, et al. Performance assessment of multi objective optimizers: An analysis and review[J]. IEEE Transactions on Evolutionary Computation, 2003, 7(2): 117-132. DOI:10.1109/TEVC.2003.810758
[21]
Derrac J, García S, Molina D, et al. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms[J]. Swarm & Evolutionary Computation, 2011, 1(1): 3-18.