在实际工程应用中,许多问题往往需要同时优化多个相互冲突的目标,这类问题被称为多目标优化问题(multi-objective optimization problems,MOPs)[1]。近年来,人们提出了许多多目标进化算法(multi-objective evolutionary algorithms,MOEAs)[2]去处理MOPs,如基于Pareto支配的算法(NSGA-II[3])、基于指标的算法(SPEA2[4])和基于分解的算法(MOEA/D[5])。这些算法获得的Pareto解集(Pareto set,PS)在目标空间映射后得到的Pareto前沿(Pareto front,PF)分布均匀且完整。
在MOPs中,存在一类具有多模态性质的问题,如多目标旅行商问题[6]、 多目标调度问题[7]、特征选择问题[8]和多目标选址问题[9]。这类问题存在多个不同的PS对应目标空间中相同的全局PF或同时拥有局部PS,被称为多模态多目标优化问题(multimodal multi-objective optimization problems,MMOPs)[10]。如何设计多模态多目标进化算法(multimodal multi-objective evolutionary algorithms,MMOEAs)使其获得多个PS具有重要的研究意义。如图1所示[10],在最短的时间和最少的交叉口的条件下,游客从起点到终点有6种选择,且已知{方案1,方案2,方案3}和{方案4,方案5,方案6}对应相同的全局PF。但这些路径是不同的,假设在{方案1,方案2,方案3}的路径中有加油站,{方案4,方案5,方案6}的路径中没有加油站,而不同的游客有不同的需求,有些游客需要加油,有些游客因为加油站不安全而避开加油站。如果算法只找到一个PS,则不能满足所有游客的需求。
近年来,研究学者提出了大量的MMOEAs求解MMOPs。根据其算法特征,大致可以分为以下几类:1)基于Pareto支配的算法,这类算法将目标空间中的拥挤度距离[3]引入决策空间中以定位多个PS,如MO_Ring_PSO_SCD[11]、DNPD[12]和MMEAPSL [13]等。这些算法充分考虑了种群在决策空间中的多样性,但忽略了目标空间中的多样性,导致找不到更多的Pareto最优解。2)基于分解的算法[14-15],其核心是将MMOPs转化为多个简单子问题,如LORD[16]、MOEA/D-MM[17]等。这类算法在处理MMOPs时运行效率高且收敛速度快,但仍然存在PS不完整、收敛精度低等问题。3)基于指标的算法,这类算法采用选定的适应度指标引导个体搜索Pareto最优解,如:MMEA-WI[18]、NIMMO[19]等。这些算法可以有效地改善种群的多样性,但适应度指标的计算会浪费大量计算资源,尤其在大规模MMOPs中。4)基于新型进化范例的MMOEAs,这类算法将MOEAs中优越的性能移植到MMOPs求解中,如TriMOEA-TA&R[20]、SMPSO_MM[21]等,从而有效提高了算法的搜索速度和精度[22]。
由于基于分解的MMOEAs在处理MMOPs时,仍然存在PS不完整、收敛性差等问题。因此,本文以MOEA/D为框架提出了一种基于分解的差分进化算法(a decomposition-based differential evolution algorithm for multimodal multi-objective optimization,MMOEA/D-DE)。在MMOEA/D-DE中,首先,为了定位多个PS,采用一组均匀分布的权重向量将一个MMOP分解成多个标量优化子问题并且给每个权重向量分配多个个体去形成同一子种群。随后,设计了一种环境选择方法定位子种群中不同的Pareto最优解。最后,使用不同的差分算子产生子代以平衡种群的多样性和收敛性。对IEEE CEC 2019基准测试集进行数值实验,结果表明所提算法在大多数测试函数上优于其他算法。
1 基本概念
1.1 多模态多目标优化问题
在现实生活中,许多问题都可以建模成MOPs。不失一般性,一个MOP可以表示为
$ \begin{array}{c}\min _{\mathbf{X} \in \Omega} F(\mathbf{X})=\left(f_{1}(\mathbf{X}), f_{2}(\mathbf{X}), \cdots, f_{m}(\mathbf{X})\right)^{\mathrm{T}}, \\x_{i} \in\left(x_{i}^{\mathrm{l}}, x_{i}^{\mathrm{u}}\right), i=1,2, \cdots, n_{0}\end{array}$ (1)
式中:Ω是搜索空间;X=(x1,x2,…,xn)T∈Ω是n维的决策变量;fj(X)代表第j个目标函数;m表示目标的个数; 和 分别是xi的下界和上界。MOPs的一些相关概念[2-5]如下。
Pareto支配(Pareto dominance) 设X1、X2是任意的两个决策变量,X1 Pareto支配X2(记作X1≺X2),当且仅当fi(X1)≤fi(X2),∀i={1,2,…,m}并且fj(X1)<fj(X2),∃j∈{1,2,…,m}。
Pareto最优解(Pareto optimal solution) 决策变量X*∈Ω称为Pareto最优解,当且仅当¬∃Xi∈Ω,使得Xi≺X*。
Pareto解集(Pareto set,PS) 对于给定的多目标优化问题F(X),Pareto解集(R)定义为:R={X*∈Ω|¬∃Xi∈Ω,Xi≺X*}。
Pareto前沿(Pareto front,PF,记作FP) 对于给定的多目标优化问题F(X)和Pareto解集(R),Pareto前沿定义为FP={F(X*)|X*∈R}。
MMOPs作为一类具有多模态性质的MOPs,与多模态优化问题中存在多个峰值的情况类似,它存在多个不同的全局PS对应相同的PF或同时具有局部PS。相关定义如下。
局部Pareto解集和局部Pareto前沿(local PS and local PF) X是解集PL中的解,如果PL中任何一个解都不被X的邻域解Y所支配,且Y满足‖Y-X‖∞≤σ,其中σ是很小的正数。那么解集PL被称为局部Pareto解集并且它在目标空间中的映射被称为局部Pareto前沿。
全局Pareto解集和全局Pareto前沿(global PS and global PF) 如果搜索空间中没有解可以支配集合PG中的任何一个解,那么解集PG被称为全局Pareto解集并且它在目标空间中的映射被称为全局Pareto前沿。
综上,满足如下条件之一的MOPs即为MMOPs:
1)至少有一个局部PS;
2)至少有两个等价的全局PS;
其中,局部PS表示邻域内Pareto最优解的集合,全局PS表示整个种群Pareto最优解的集合。
1.2 差分进化算法
差分进化算法(differential evolution,DE)由Storn和Price[23]提出,具有结构简单、易于实施、收敛速度快、鲁棒性好等优点。该算法包括初始化、变异、交叉、选择4个步骤:
初始化:在n维的搜索空间中随机生成一个初始种群P={X1,X2,…, },其中NP表示种群规模,Xi=(Xi,1,Xi,2,…,Xi,n}表示第i个个体。
变异:每个目标向量Xi利用变异操作产生一个变异向量Vi,
$ \boldsymbol{V}_{i}=\boldsymbol{X}_{r 1}+F \cdot\left(\boldsymbol{X}_{r 2}-\mathbf{X}_{r 3}\right),$
其中F是比例因子,r1,r2,r3∈{1,2,…,NP}并且r1≠r2≠r3≠i。
交叉:目标向量Xi和变异向量Vi采用交叉操作生成试验向量Ui=(ui,1,ui,2,…,ui,n):
$ u_{i, j}=\left\{\begin{array}{l}v_{i, j}, \text { 若 } \operatorname{rand}_{j}(0,1) \leqslant C_{r} \text { 或 } j=j_{\text {rand }}, \\x_{i, j}, \text { 否则。 }\end{array}\right.$
式中:Cr是交叉概率;jrand是集合{1,2,…,n}中随机产生的一个整数;randj是(0,1)中随机产生的一个实数。
选择:对于最小化问题,根据目标向量Xi和试验向量Ui的适应度值选择个体进入下一代,
$ \boldsymbol{X}_{i}(G+1)=\left\{\begin{array}{l}\boldsymbol{U}_{i}, \text { 如果 } F\left(\boldsymbol{U}_{i}\right) \leqslant F\left(\boldsymbol{X}_{i}\right), \\\boldsymbol{X}_{i}, \text { 其他。 }\end{array}\right.$
式中,F(Xi)和F(Ui)分别是Xi和Ui的适应度值。
2 MMOEA/D-DE
2.1 研究动机
基于分解的MMOEAs求解MMOPs时,其核心是使用一组均匀分布的权重向量将一个MMOP分解为多个简单子问题,随后采用环境选择方法定位子种群中不同的Pareto最优解。尽管这类算法在处理MMOPs时运行效率高且收敛速度快,但仍然存在PS不完整、收敛精度低和多样性差等问题。针对该问题,本文提出了一种基于分解的差分进化算法。在所提方法中,为寻找多个等价的PS,每个权重向量被分配多个个体去形成一个子种群,然后设计了一种基于贪婪性选择的环境选择方法搜索子种群中不同的Pareto最优解。例如,图3中每个权重向量被分配3个个体去形成一个子种群,然后采用环境选择方法引导子种群中的个体向不同的Pareto最优解搜索。此外,DE在求解MMOPs时具有优化效率高、鲁棒性强、收敛速度快等优点,因此使用DE作为搜索算法。为平衡种群的收敛性与多样性,本文以经典DE算法为基础结合2种DE变异策略更新种群搜索最优解。实验结果表明,所提的算法不仅能够定位所有的PS,而且具有优异的性能。
2.2 算法框架
| 算法1 MMOEA/D-DE |
|---|
| 输入:种群规模NP,最大函数评价次数max FES,控制参数t,比例因子F,交叉概率Cr。 输出:Pareto解集Q 01:初始化种群P={x1,x2,…, }和权重向量W={W1,W2,…, }。 02:计算种群的适应度值Fit和理想点Z*。 03:for i=1:NP do 04: =[ ]。 05:end for 06:for i=1:NP do 07: = ∪Xi,其中j=min{gtch(Xi|W1,Z*),…,gtch(Xi| ,Z*)}。 08:end for 09:while FES<max FES 10: 设置PT= ∪ ∪…∪ 。 11: for i=1:|PT| do 12: 根据算法2产生子代μ,并更新理想点Z*。 13: 根据算法3更新子种群 ,其中j=min{gtch(μ|W1,Z*),…,gtch(μ| ,Z*)}。 14: FES=FES+1。 15: end for 16:end while 17:Q←PT中的所有Pareto最优解。 |
2.3 搜索算法
为了平衡种群的多样性和收敛性,本文采用两种差分变异策略产生子代μ。在算法前期,为了增加算法的探索能力,从整个种群中选取父代并采用DE/current-to-rand/1变异策略以改善种群的多样性,避免陷入局部最优。在算法后期,为了提升算法的收敛能力,从邻域中选择父代并采用DE/rand-to-best/1/bin变异策略引导种群向最优解靠近,进而加快种群的收敛速度。搜索算法的具体步骤和两种变异策略如下。
DE/current-to-rand/1:
$ \boldsymbol{V}_{i}=\boldsymbol{X}_{i}+\operatorname{rand} \cdot\left(\boldsymbol{X}_{r 1}-\boldsymbol{X}_{i}\right)+F \cdot\left(\boldsymbol{X}_{r 2}-\boldsymbol{X}_{r 3}\right) \text { 。 }$
DE/rand-to-best/1/bin:
$ \boldsymbol{V}_{i}=\boldsymbol{X}_{i}+\operatorname{rand} \cdot\left(\boldsymbol{X}_{\text {best }}-\boldsymbol{X}_{i}\right)+F \cdot\left(\boldsymbol{X}_{r 2}-\boldsymbol{X}_{r 3}\right) \text { 。 }$
式中:rand是(0,1)中随机产生的一个实数;Xbest是邻域中距离当前个体最近的Pareto最优解。
| 算法2 搜索算法 |
|---|
| 输入:种群规模NP,存档PT,当前函数评价次数FES,最大函数评价次数max FES,个体X。 输出:子代μ。 01:T=[NP/10]。 02:if FES/max FES≤0.5 03: 根据DE/current-to-rand/1从PT中产生子代μ 。 04:else 05: W*←Wj的T个相邻权重的集合,其中j=min{gtch(Xi|W1,Z*),…,gtch(Xi| ,Z*)}。 06: B←W*中所有权重向量的子种群的集合。 07: 根据DE/rand-to-best/1/bin从B中产生子代μ。 08: end if |
2.4 环境选择
如何定位不同的Pareto最优解是设计多模态多目标进化算法的关键。为此,本文提出了一种环境选择方法。在所提方法中,如果子种群规模大于t,则将子种群中离子代μ最近的个体Xr与μ进行比较,二者中较好的个体进入下一代。如图5所示,测试函数包含4个等价的PS(即4个正方形),且设置t=4,则每个权重向量需要去定位4个等价的Pareto最优解。当子种群规模大于t时,子种群中离子代μ最近的个体A将与μ进行比较,二者中较好的个体被保留。如果子种群规模不大于t,则子代μ进入下一代。仿真实验结果表明,环境选择能有效定位子种群中多个等价的Pareto最优解,其具体算法如下。
2.5 复杂度分析
MMOEA/D-DE的时间复杂度主要由构造子种群、搜索算法和环境选择3个部分组成。构造子种群的时间复杂度为O( )。搜索算法的时间复杂度是O(m× ),其中m为目标个数。环境选择的时间复杂度是O(n×t×NP),其中t为子种群大小,n是决策变量个数。由于t<NP且m与n相差不大,因此本文总的时间复杂度为 O(m× )。
3 实验结果及分析
3.1 测试函数与参数设置
采用IEEE CEC 2019[24]中的22个MMOPs测试算法的性能。测试函数的决策变量维数(n)、目标个数(m)、决策变量的下界(xl)、决策变量的上界(xu)和等价PS个数(PSn)如表1所示。此外,为了测试算法的性能,所提的算法和5个最新的算法进行比较,分别为 MMODE_ICD[13]、 MO_Ring_PSO_SCD[11]、LORD[16]、TriMOEA-TA&R[20]和SMPSO_MM[21]。对所有的算法,种群大小设置为800,最大函数评价次数设置为80 000[11],每个测试问题独立运行25次。对于比较的算法,内部参数设置与原文献中设置相同。对于MMOEA/D-DE,设置F=0.5,Cr=0.7,t=5。
表1 问题描述Tab.1 Problem description |
| 测试函数 | n | m | xl | xu | PSn |
|---|---|---|---|---|---|
| MMF1 | 2 | 2 | [1 -1] | [3 1] | 2 |
| MMF1_e | 2 | 2 | [1 -20] | [3 20] | 2 |
| MMF1_z | 2 | 2 | [1 -1] | [3 1] | 2 |
| MMF2 | 2 | 2 | [0 0] | [1 2] | 2 |
| MMF3 | 2 | 2 | [0 0] | [1 1.5] | 2 |
| MMF4 | 2 | 2 | [1 0] | [1 2] | 4 |
| MMF5 | 2 | 2 | [1 -1] | [3 3] | 4 |
| MMF6 | 2 | 2 | [1 -1] | [3 2] | 4 |
| MMF7 | 2 | 2 | [1 -1] | [3 1] | 2 |
| MMF8 | 2 | 2 | [-π 0] | [π 9] | 4 |
| MMF9 | 2 | 2 | [0.1 0.1] | [1.1 1.1] | 2 |
| MMF10 | 2 | 2 | [0.1 0.1] | [1.1 1.1] | 2 |
| MMF11 | 2 | 2 | [0.1 0.1] | [1.1 1.1] | 2 |
| MMF12 | 2 | 2 | [0 0] | [1 1] | 8 |
| MMF13 | 3 | 2 | [0.1 0.1 0.1] | [1.1 1.1 1.1] | 2 |
| MMF14 | 3 | 3 | [0 0 0] | [1 1 1] | 2 |
| MMF14_a | 3 | 3 | [0 0 0] | [1 1 1] | 2 |
| MMF15 | 3 | 3 | [0 0 0] | [1 1 1] | 2 |
| MMF15_a | 3 | 3 | [0 0 0] | [1 1 1] | 2 |
| SYM_PART simple | 2 | 2 | [-20 -20] | [20 20] | 9 |
| SYM_PART rotated | 2 | 2 | [-20 -20] | [20 20] | 9 |
| Omni-test | 3 | 2 | [0 0 0] | [6 6 6] | 27 |
3.2 性能评价指标
$\begin{aligned}D_{\mathrm{IGF}}(O)= & \frac{1}{\left|P^{*}\right|}\left(\sum _ { Z \in P ^ { * } } \operatorname { m i n } _ { X \in O } \left\{D_{\mathrm{E}}(F(X),\right.\right. \\& F(Z))\})\end{aligned}$
式中:P*是真实的PS;O是获得的PS;DE(F(X),F(Z))是F(X)和F(Z)之间的欧式距离。针对某一问题,IGDF越小,表明该算法获得的PF越能够代表真实的PF。
$ P_{\mathrm{PS}}=\frac{R_{C}}{D_{\mathrm{IGX}}}$
$ D_{\mathrm{IG} X}(O)=\frac{1}{P^{*}}\left(\sum_{Z \in P^{*}} \min _{X \in O}\left\{D_{\mathrm{E}}(X, Z)\right\}\right)$。
$ R_{C}=\left(\prod_{l=1}^{n} \delta_{l}\right)$
$ \delta_{l}=\left\{\begin{array}{l}1, V_{l}^{\max }=V_{l}^{\min }, \\0, v_{l}^{\min } \geqslant V_{l}^{\max } \| v_{l}^{\max } \leqslant V_{l}^{\min }, \\M_{l}, \text { 其他, }\end{array}\right.$
$ M_{l}=\left(\frac{\min \left(v_{l}^{\max }, V_{l}^{\max }\right)-\max \left(v_{l}^{\min }, V_{l}^{\min }\right)}{V_{l}^{\max }-V_{l}^{\min }}\right).$。
式中:P*是获得的PS与真实的PS之间的覆盖率;n是决策变量的维数; 和 分别是获得的PS中第l维变量的最大值和最小值; 和 分别是真实的PS中第l维变量的最大值和最小值。针对某一问题,PSP越大,表明该算法获得的PS越能够覆盖真实的PS。
3.3 实验结果
首先,比较算法在决策空间中获得多个PS的能力,不同算法的PSP值如表2所示。由表2可知,MMOEA/D-DE不仅在22个测试函数中的11个上获得了最好的性能,而且在大多数测试函数上都优于TriMOEA-TA&R。此外,MO_Ring_PSO_SCD、 SMPSO_MM和MMODE_ICD分别在4个、3个和2个测试函数上表现最佳。LORD和TriMOEA-TA&R分别在1个测试函数上性能最好。其次,比较算法在目标空间中获得PF的能力,不同算法的IGDF值如表3所示。从表3可以得出,MMOEA/D-DE在8个测试函数上优于其他算法,MMODE_ICD在5个测试函数上获得了最好的IGDF值,并且MO_Ring_PSO_SCD、LORD和SMPSO_MM在3个测试函数上性能最优。因此,由实验结果可知,MMOEA/D-DE不仅在PSP指标上获得了良好的性能,而且在IGDF指标上的实验结果是可接受的。
表2 指标PSP值统计Tab.2 Statistics of indicator PSP |
| 测试函数 | MMOEA/D-DE | MO_Ring_PSO_SCD | TriMOEA-TA&R | SMPSO_MM | LORD | MMODE_ICD |
|---|---|---|---|---|---|---|
| MMF1 | 97.16 | 66.73(+) | 30.26(+) | 85.43(+) | 69.14(+) | 72.51(+) |
| MMF1_e | 1.41 | 5.22(-) | 1.01(=) | 7.94(-) | 0.39(+) | 7.92(-) |
| MMF1_z | 134.02 | 91.41(+) | 28.76(+) | 198.36(-) | 57.33(+) | 79.81(+) |
| MMF2 | 454.88 | 106.04(+) | 71.67(+) | 152.92(+) | 143.63(+) | 358.12(+) |
| MMF3 | 523.84 | 139.78(+) | 31.10(+) | 179.79(+) | 170.30(+) | 445.72(+) |
| MMF4 | 232.61 | 113.24(+) | 83.50(+) | 138.48(+) | 132.36(+) | 126.20(+) |
| MMF5 | 53.34 | 33.44(+) | 16.77(+) | 40.25(+) | 30.02(+) | 25.91(+) |
| MMF6 | 55.20 | 36.53(+) | 22.38(+) | 41.99(+) | 32.42(+) | 33.41(+) |
| MMF7 | 169.07 | 108.96(+) | 58.41(+) | 142.80(+) | 127.90(+) | 136.33(+) |
| MMF8 | 84.01 | 47.41(+) | 9.58(+) | 61.98(+) | 14.25(+) | 20.40(+) |
| MMF9 | 756.94 | 332.35(+) | 348.68(+) | 554.91(+) | 666.47(+) | 465.10(+) |
| MMF10 | 0.18 | 6.04(-) | 0.12(=) | 5.03(-) | 0.09(+) | 5.40(-) |
| MMF11 | 0.69 | 3.16(-) | 0.64(=) | 0.96(=) | 0.83(-) | 4.01(-) |
| MMF12 | 0.38 | 4.28(-) | 0.06(+) | 1.01(-) | 0.62(-) | 4.07(-) |
| MMF13 | 1.96 | 3.05(-) | 1.72(+) | 1.96(=) | 1.84(=) | 1.86(=) |
| MMF14 | 30.83 | 26.62(+) | 28.42(+) | 29.84(+) | 21.16(+) | 30.18(+) |
| MMF14_a | 24.65 | 23.02(=) | 21.02(+) | 26.58(=) | 15.71(+) | 30.70(-) |
| MMF15 | 5.10 | 6.81(-) | 3.14(+) | 7.03(-) | 0.78(+) | 3.96(+) |
| MMF15_a | 5.19 | 6.46(-) | 3.64(+) | 6.35(-) | 3.64(+) | 4.01(+) |
| SYM_PART simple | 39.15 | 21.89(+) | 77.49(-) | 31.32(+) | 46.20(-) | 52.39(-) |
| SYM_PART rotated | 32.49 | 18.30(+) | 14.75(+) | 16.78(+) | 18.07(+) | 52.48(-) |
| Omni-test | 16.84 | 7.24(+) | 12.58(+) | 8.14(+) | 26.01(-) | 2.30(+) |
| 汇总(+/=/-) | 14/1/7 | 18/3/1 | 13/3/6 | 17/1/4 | 14/1/7 |
注:加粗表明最优。 |
表3 指标IGDF值统计Tab.3 Statistics of indicator IGDF |
| 测试函数 | MMOEA/D-DE | MO_Ring_PSO_SCD | TriMOEA-TA&R | SMPSO_MM | LORD | MMODE_ICD |
|---|---|---|---|---|---|---|
| MMF1 | 5.828×10-4 | 9.938×10-4(+) | 2.368×10-3(+) | 6.857×10-4(+) | 6.226×10-4(+) | 6.886×10-4(+) |
| MMF1_e | 7.826×10-4 | 2.948×10-3(+) | 2.467×10-3(+) | 2.001×10-3(+) | 6.817×10-4(-) | 1.596×10-3(+) |
| MMF1_z | 4.733×10-4 | 9.501×10-4(+) | 2.362×10-3(+) | 6.237×10-4(+) | 5.394×10-4(+) | 6.677×10-4(+) |
| MMF2 | 1.021×10-3 | 5.188×10-3(+) | 4.366×10-3(+) | 3.425×10-3(+) | 1.758×10-3(+) | 9.035×10-4(-) |
| MMF3 | 8.952×10-4 | 3.805×10-3(+) | 4.037×10-3(+) | 2.877×10-3(+) | 1.576×10-3(+) | 8.961×10-4(+) |
| MMF4 | 3.688×10-4 | 8.801×10-4(+) | 3.107×10-2(+) | 6.634×10-4(+) | 5.319×10-4(+) | 6.268×10-4(+) |
| MMF5 | 5.165×10-4 | 9.423×10-4(+) | 4.021×10-3(+) | 6.831×10-4(+) | 6.203×10-4(+) | 6.517×10-4(+) |
| MMF6 | 5.101×10-4 | 9.071×10-4(+) | 2.252×10-3(+) | 6.509×10-4(+) | 5.811×10-4(+) | 6.683×10-4(+) |
| MMF7 | 4.889×10-4 | 9.158×10-4(+) | 3.131×10-3(+) | 6.616×10-4(+) | 5.777×10-4(+) | 7.187×10-4(+) |
| MMF8 | 4.908×10-4 | 1.311×10-3(+) | 2.467×10-3(+) | 9.271×10-4(+) | 6.308×10-4(+) | 6.468×10-4(+) |
| MMF9 | 7.872×10-3 | 3.658×10-3(-) | 6.178×10-2(+) | 3.035×10-3(-) | 2.489×10-3(-) | 2.942×10-3(-) |
| MMF10 | 1.965×10-1 | 1.538×10-1(-) | 2.263×10-1(+) | 1.507×10-1(-) | 1.914×10-1(=) | 1.976×10-1(+) |
| MMF11 | 9.817×10-2 | 7.584×10-2(-) | 1.574×10-1(+) | 8.941×10-2(-) | 8.717×10-2(-) | 9.913×10-2(+) |
| MMF12 | 8.284×10-2 | 6.189×10-2(-) | 8.460×10-2(=) | 8.168×10-2(=) | 8.352×10-2(=) | 8.299×10-2(+) |
| MMF13 | 1.556×10-1 | 8.269×10-2(-) | 2.420×10-1(+) | 1.217×10-1(-) | 1.493e×10-1(=) | 1.531×10-1(=) |
| MMF14 | 5.529×10-2 | 4.867×10-2(-) | 8.526×10-2(+) | 4.655×10-2(-) | 5.398×10-2(-) | 4.162×10-2(-) |
| MMF14_a | 5.603×10-2 | 4.885×10-2(-) | 7.541×10-2(+) | 4.556×10-2(-) | 5.711×10-2(+) | 4.179×10-2(-) |
| MMF15 | 1.770×10-1 | 1.530×10-1(-) | 2.058×10-1(+) | 1.524×10-1(-) | 1.844×10-1(+) | 1.686×10-1(-) |
| MMF15_a | 1.799×10-1 | 1.553×10-1(-) | 1.954×10-1(+) | 1.538×10-1(-) | 1.840×10-1(+) | 1.676×10-1(-) |
| SYM_PART simple | 6.433×10-3 | 9.703×10-3(+) | 4.051×10-2(+) | 6.930×10-3(+) | 5.698×10-3(-) | 2.870×10-3(-) |
| SYM_PART rotated | 7.653×10-3 | 9.703×10-3(+) | 1.407×10-2(+) | 1.259×10-2(+) | 6.150×10-3(-) | 2.724×10-3(-) |
| Omni-test | 6.222×10-3 | 1.796×10-2(+) | 1.407×10-2(+) | 9.807×10-1(+) | 4.022×10-3(-) | 5.104×10-3(-) |
| 汇总(+/=/-) | 13/0/9 | 21/1/0 | 13/1/8 | 12/3/7 | 12/1/9 |
注:加粗表明最优。 |
为了可视化地比较多次运行后算法之间的性能差异,将所有算法在具有27个等价全局PS的测试函数Omni-test上获得的PS和PF分别在图6、图7进行展示。对于PS,从图6可以得出,尽管MMOEA/D-DE,LORD和TriMOEA-TA&R定位了所有的PS区域,但是MMOEA/D-DE比TriMOEA-TA&R获得了更多的Pareto最优解。此外,剩余的算法不仅没能找到所有的PS,并且MMOEA/D-DE在决策空间中的收敛性优于MO_Ring_PSO_SCD和SMPSO_MM。对于PF,从图7可以看出,所有的算法都能够覆盖真实的PF,但是MO_Ring_PSO_SCD、SMPSO_MM的收敛性差于其他算法。综上所述,MMOEA/D-DE不仅能定位所有的PS,而且能很好地近似真实的PF。
3.4 参数敏感性分析
为了确定恰当的算法参数,对MMOEA/D-DE在不同的参数水平$ T=\left\{\left[\frac{N_{P}}{5}\right],\left[\frac{N_{P}}{10}\right],\left[\frac{N_{P}}{20}\right]\right. ， \left.\left[\frac{N_{P}}{40}\right]\right\}$和t={2,3,4,5}下进行实验,实验结果如表4所示。由表4可知,当t=5时,MMOEA/D-DE获得了最小的排名,表明此时算法性能最佳。对于邻域大小T而言,从表4可得,当T=[NP/20],算法表现最佳。因此,在本文中设置算法参数t=5、T=[NP/10]。
表4 Friedman检验不同参数设置下MMOEA/D-DE的平均排名Tab.4 Average ranking of MMOEA/D-DE with different parameter settings by the Friedman test |
| 参数 | 算法 | 排名 |
|---|---|---|
| t | t=2 | 3.204 5 |
| t=3 | 3.25 | |
| t=4 | 3 | |
| t=5 | 2.386 4 | |
| t=6 | 3.159 5 | |
| T | T=[NP/5] | 2.5 |
| T=[NP/10] | 2.340 9 | |
| T=[NP/20] | 2.590 9 | |
| T=[NP/40] | 2.568 2 |
注:加粗表明最优。 |
3.5 算法有效性分析
为了验证所提算法的有效性,对算法使用的策略进行单独分析。MMOEA/D-DE/rand表示算法仅使用DE/current-to-rand/1产生子代。MMOEA/D-DE/best代表算法仅采用DE/rand-to-best/1/bin产生子代。MMOEA/D-DE/ES表示算法从子种群中删除切比雪夫值最大的个体来替代环境选择策略。对以上的算法进行实验并对得到的PSP值进行Friedman检验,结果如表5所示。由表5可知,MMOEA/D-DE获得了最好的性能,其结果验证了所提算法的有效性。此外,为了进一步分析算法的有效性,所有算法在具有2个全局PS的测试函数MMF3上获得的Pareto最优解如图8所示。由图8可知,尽管每个算法都定位了所有的PS区域,但MMOEA/D-DE在每个PS上获得了更多的Pareto最优解。综上所述,MMOEA/D-DE的每个策略能有效提升算法的性能。
4 结论
本文提出了MMOEA/D-DE算法求解MMOPs。在所提算法中,属于同一权重向量的个体划分成一个子种群,并采用环境选择方法定位子种群中不同的Pareto最优解。最后,为了进一步改善种群的多样性和收敛性,算法采用不同的差分进化策略更新子种群。通过和5种最新的算法进行比较,结果表明MMOEA/D-DE不仅能获得更多的PS,而且在目标空间上具有良好的多样性。未来将尝试设计一个自适应的子种群框架来进一步优化算法的性能,并将其应用于作业车间调度等实际工程问题中。