-
摘要: 高维多目标优化问题由于具有巨大的目标空间使得一些经典的多目标优化算法面临挑战.提出一种基于自适应模糊支配的高维多目标粒子群算法MAPSOAF，该算法定义了一种自适应的模糊支配关系，通过对模糊支配的阈值自适应变化若干步长，在加强个体间支配能力的同时实现对种群选择压力的精细化控制，以改善算法的收敛性；其次，通过从外部档案集中选取扰动粒子，并在粒子速度更新公式中新增一扰动项以克服粒子群早熟收敛并改善个体分布的均匀性；另外，算法利用简化的Harmonic归一化距离评估个体的密度，在改善种群分布性的同时降低算法的计算代价.该算法与另外五种高性能的多目标进化算法在标准测试函数集DTLZ{1，2，4，5}上进行对比实验，结果表明该算法在收敛性和多样性方面总体上具有较显著的性能优势.
-
关键词:
- 自适应模糊支配 /
- 精英个体扰动 /
- 粒子群算法 /
- 高维多目标优化问题 /
- 高维多目标粒子群优化算法
Abstract: The huge objective space makes some representative multiobjective optimization algorithms face challenges. A many-objective particle swarm optimization based on adaptive fuzzy dominance (MAPSOAF) is proposed. An adaptive fuzzy dominance relation is defined to adjust the threshold of fuzzy dominance adaptively to improve the convergence of MAPSOAF. Second, a perturbation term is added to the particle's velocity formula by selecting an elite member from the external archive to conquer premature convergence and to enhance the diversity of population. In addition, a method of simplified Harmonic normalized distance is utilized to evaluate the density of individuals and reduce the computational cost when while improving the population diversity. MAPSOAF is compared with other five high-performance multiobjective evolutionary algorithms on the benchmark test set DTLZ {1, 2, 4, 5}, and the results show that the proposed MAPSOAF has more significant performance advantages in convergence and diversity over the peering algorithms. -
科学研究与工程实践中不断涌现出要求同时优化4个或4个以上目标的问题, 研究者一般将这类优化问题称为高维多目标优化问题(Many-objective optimization problem, MAOP), 与优化目标数为2至3个的多目标优化问题(Multi-objective optimization problem, MOP)相比, MAOP问题的目标空间更大, 搜索的难度也更大.其原因在于:随着目标空间维度的增加, 种群中非被占优个体的数量将呈指数级增长, 运用Pareto支配关系择优个体的方法面临失效的窘地, 算法的搜索能力被极大地削弱; 另外, 由于Pareto支配关系在高维空间中效果变差, 使得分布性保持机制成为算法选择个体的主导因素, 但是由个体密度信息主导的选择机制不一定能有效地驱动近似Pareto前沿向真实Pareto前沿逼近, 甚至可能对优化过程有负面影响[1-3].为解决高维多目标优化问题带来的挑战, 各国学者从不同的视角提出了解决方法.陈振兴等[4]融合张角拥挤控制策略解决MAOP问题.巩敦卫等[5]基于目标分解的策略提出高维多目标并行优化方法. Drechsler等[6]提出了目标优胜关系的宽松Pareto支配关系: Favor关系, 但该关系易受到目标函数量纲差别的影响. Di Pierro等[7]提出K-占优机制, 但其只考虑了一个目标向量相对于另一个目标向量的改善目标数. Sato等[8]提出对解个体的支配区域进行缩放以改变解个体在目标空间中的位置, 从而达到改变解个体支配关系的目的.需要指出, 这种方法需要用户为每一个目标函数指定修正参数. Hernandez-diaz等[9]通过引入评判目标间优劣关系的阈值提出了$\varepsilon$-占优机制, 但该策略依赖阈值的选取方法. Kang等[10]在总结新型占优机制优劣的基础上提出了E-占优, 但E-占优方法在求解MAOP问题中的性能如何, 文献中并未讨论. Zou等[11]提出了一种L-最优性, 该占优方法不仅考虑了目标值得到改善的目标个数而且在所有目标具有同等重要性的情况下, 改善的目标函数也考虑其中, 但该方法随着目标个数的持续增加, 仍面临着选择压力退化的问题. Farina等[12]将模糊理论引入到多目标优化算法中, 但该策略亦存在产生循环支配之缺陷.毕晓君等[13]将模糊理论引入高维多目标进化算法模型, 并结合模糊理论$\alpha$-截集提出了新的环境选择策略.
粒子群优化(Particle swarm optimization, PSO)是Kennedy等[14]受到飞鸟集群活动的启发而提出的一种群体智能优化算法, 其具有易于实现和收敛速度快等优势.近年来, PSO算法在多目标优化领域的研究取得了很大的进展, 涌现出了不少的多目标粒子群算法(Multi-objective particle swarm optimization algorithm, MOPSO), 但将其用于高维多目标优化问题求解的理论和方法还很少.
本文在已有多目标粒子群算法和宽松支配关系等研究的基础上, 提出一种基于自适应模糊支配的高维多目标粒子群优化(Many-objective particle swarm optimization based on adaptive fuzzy dominance, MAPSOAF)算法, 以求解复杂的MAOP问题.算法的创新点主要包括: 1)以步长幅度自适应地调整模糊隶属度支配的阈值来改进模糊支配关系, 在加强个体间支配能力的同时实现对种群选择压力的精细化调控, 以改善算法的收敛性; 2)增加扰动粒子改造基本PSO算法的速度更新公式, 在克服种群早熟收敛的同时改善个体分布的均匀性; 3)利用简化的Harmonic归一化距离评估个体的密度, 在改善种群分布性的同时降低算法的计算代价.上述三种策略有机结合, 形成了MAPSOAF算法的主要特点, 这些策略在算法的不同阶段实施, 以协同地提高MAPSOAF算法的总体性能.
论文的第1节简要介绍高维多目标优化问题相关概念.第2节描述构成MAPSOAF算法的若干重要组件和算法的流程, 它是本文的重点章节.第3节是论文的仿真实验与结果分析.最后是本文的结论部分.
1. 高维多目标优化问题相关概念
不失一般性, 一个具有$n$个决策变量、$m$个目标函数的多目标优化问题, 以最小化为例, 可表述为式(1)的形式.
$ \begin{cases} {\rm {min}}\quad y= F({x})=(f_1({x}), f_2({x}), \cdots, f_m({x}))\\ x=({x}_1, {x}_2, \cdots, {x}_n)\in {X} \subset {\rm {\bf R}}^n \\ y=(y_1, y_2, \cdots, y_m)\in Y \subset {\rm {\bf R}}^m \end{cases} $
(1) 式中, $x$称为决策向量, $X$是$n$维的决策空间; $y$称为目标函数, $Y$是$m$维的目标空间; 目标函数$F$定义了映射函数和需要同时优化的$m$个目标.当时, 称式(1)为高维多目标优化问题.对于决策空间任意的两点, 当${x}_1$的目标函数都不大于并且至少存在一个小于${x}_2$的目标函数时, 称${x}_1$ Pareto支配${x}_2$, 记为${x}_1 \prec {x}_2$.若${x}^* \in {\pmb {X}} $不受种群中其他个体支配, 则称${x}^*$为Pareto非支配解, 种群中所有非支配解组成的集合成为Pareto解集, 其对应的目标函数构成的集合为Pareto前沿.
2. 基于自适应模糊支配的高维多目标粒子群优化算法
2.1 自适应模糊支配关系
目前基于宽松支配关系的多目标/高维多目标进化算法大多采用变换目标函数值的方法, 鉴于目标函数值是不可预测的, 这就使得算法参数难以设定, 而且目标函数值的改变, 尤其在高维多目标优化中, 会使寻优偏离真实的Pareto前沿. Farina等[12]将模糊理论引入高维多目标优化中, 通过计算个体间目标优劣的数量来衡量个体的支配关系, 提出$(1-k_F)$支配策略.这种模糊支配关系的优点在于个体间的支配关系不再受到目标函数量纲和数值差异大小的影响, 并使支配关系的复杂程度不受到目标数量的影响.但是该支配策略存在一个重要缺陷, 即种群中的个体可能会陷入循环支配, 从而使得种群中不存在非支配的解, 导致算法各种择优策略无法实施, 迫使算法停止.基于此, 这里提出一种自适应的模糊支配关系, 这种支配关系以步长幅度自适应地调整模糊隶属度支配阈值, 在提高个体之间支配概率的同时, 实现对高维多目标进化算法种群选择压力的精细化调控, 以更好地促进算法收敛.
假设${F}({x}_{i})$和${F}({x}_{j})$分别表示种群中任两个个体${x}_i$和${x}_j$的目标向量, $B_t({x}_i, {x}_j)$、$W_s({x}_i, {x}_j)$和$E_q({x}_i, {x}_j)$分别表示$F(x_i)$中优于、劣于和等于$F(x_j)$的目标个数, 据此, ${x}_i$和${x}_j$的模糊支配隶属度$C({x}_i, {x}_j)$则可用式(2)表示, 而模糊集${CS}$可用式(3)表示.此外, 为避免种群个体发生循环支配, 借鉴文献[13]的做法, 这里为种群中的个体${x}_i$赋予目标质量属性$Q({x}_i)$, 以刻画${x}_i$目标值的总体表现, 其计算方法如式(4)所示.
$ \begin{equation} C({x}_i, {x}_j)=\frac{B_t({x}_i, {x}_j)}{B_t({x}_i, {x}_j)+W_s({x}_i, {x}_j)} \end{equation} $
(2) $ \begin{equation} CS= \left\{ C({x}_i, {x}_j)|{x}_i, {x}_j \in \left[ {1:N} \right]\land i\neq j \right\} \end{equation} $
(3) $ \begin{equation} Q({x}_i)=\sqrt{{\sum\limits_{j=1}^m ({f}_{j}({x}_{i})-{z}_{j})^2}} \end{equation} $
(4) 其中, ${N}$表示种群的规模, ${z}_{j}$为第个目标函数的最小值.当目标函数最小值已知时, ${z}_{j}$取第${j}$个目标函数真正的最小值; 而当目标函数真正的最小值难以获得时, ${z}_{j}$的值取当前种群对应的第${j}$个目标函数的最小值.
由于目标质量属性${Q}$是一个标量, 满足传递性, 即当$Q({x}_i) <Q({x}_j)$且$Q({x}_j) < Q({x}_k)$时, 有$Q({x}_i) <Q({x}_k)$成立.不仅如此, 为保持个体模糊支配关系和目标质量属性的一致, 这里将个体的目标质量属性Q结合到模糊隶属度中, 式(5)给出了带约束的模糊支配隶属度的表达式.
$ \begin{equation} C({x}_{i}, {x}_{j})= \begin{cases} \displaystyle \frac{B_t({x}_{i}, {x}_{j})}{B_t({x}_{i}, {x}_j)+ W_s({x}_{i}, {x}_{j})}, \ \\ \qquad\qquad\mbox {若} ~Q({x}_{i})\leq Q({x}_{j}) \\ \displaystyle \frac{-B_t({x}_{i}, {x}_{j})}{B_t({x}_{i}, {x}_{j})+W_s({x}_i, {x}_j)}, \ \\ \qquad\qquad \mbox {若}~ Q({x}_i)> Q({x}_j) \end{cases} \end{equation} $
(5) 在高维多目标优化问题中, 随着迭代次数的增加, 种群中非支配解的数目急剧增多, 导致种群的选择压力不断降低, 严重地影响了算法的收敛性能, 因而需要在进化过程中逐渐放宽个体的支配条件, 减少群体中非支配解的数目, 以增大种群的选择压力.基于此, 这里尝试自适应地调整模糊隶属度的支配阈值来控制支配条件.
本文的自适应模糊支配关系可表述如下:假设${x}_i$和${x}_j$是种群中任两个个体, 当$E_q({x}_i, {x}_j)\neq m$ (${m}$为MAOP问题的目标数), 若利用式(5)计算得到的模糊隶属度$C({x}_i, {x}_j)$满足大于等于阈值${\lambda}$ (${\lambda} \in(0.5, 1]$)且${\lambda}$随迭代次数的增加而递减时, 则称${x}_i$自适应模糊支配${x}_j$.因此, 当${\lambda}=1$时, 模糊支配关系成立需满足$W_s({x}_i, {x}_j)=0$, 且$B_t({x}_i, {x}_j)>0$, 即个体${x}_i$的所有目标都不劣于${x}_j$, 并且至少存在一个目标函数要优于${x}_j$, 此时模糊支配关系等价于Pareto支配关系; 而当${\lambda}=0.5$时, 模糊支配关系成立需要满足$B_t({x}_i, {x}_j)>W_s({x}_i, {x}_j)$, 即${x}_i$优于${x}_j$的目标个数要大于其劣于${x}_j$的目标个数, 此时模糊支配关系等价于$\epsilon$-支配; 而当${\lambda} \in(0.5, 1)$时, 此时的模糊支配关系实际上是一种宽松的Pareto支配关系.阈值${\lambda}$越小则支配关系越宽松, 这有利于减少种群中非支配解的数目, 以增强群体的选择压力, 促进算法较快收敛.因此, 随着迭代次数${t}$的增加, 阈值${\lambda}$应从1逐渐降至0.5附近, 这里规定${\lambda}$值依式(6)进行非线性递减.
$ \begin{equation} {\lambda}(t)=\left(0.5+\frac {t}{2{T}}\right){\rm exp}\left(\frac {-5t}{{T}}\right) \end{equation} $
(6) 其中, ${t}$为当前的进化代数, ${T}$为算法允许的最大迭代次数.
需要注意的是, 现有宽松支配关系一般需要设置合理的参数以达到放宽支配条件, 增大支配概率之目的, 但这些支配关系的参数值与种群中非支配解的数量之间仅仅是一种定性关系, 而非定量关系, 因而在进化过程中难以精细化调整参数值.鉴于式(5)中分子$(B_t({x}_i, {x}_j))$的最小值为$1/{m}, $分母$(B_t({x}_i, {x}_j)+W_s({x}_i, {x}_j))$的最大值为${m}, $因此, 模糊隶属度$C({x}_i, {x}_j)$的最小值为$1/{m}, $阈值${\lambda}$最小的有效调整步长可置为$1/{m}.$不妨令$B_t({x}_i, {x}_j)+W_s({x}_i, {x}_j)=Ds$, 且设阈值${\lambda}$的调整步长为1/${Ds}$, 则当${\lambda}$值减少一个步长1/${Ds}$时, 意味着模糊支配关系降低了对较优目标个数所占比重的要求, 使得群体中的个体更易形成支配关系, 从而可提高支配的概率和种群的选择压力, 促进算法收敛.一般地, 在高维多目标进化算法的后期, $E_q({x}_i, {x}_j)$的值会逐渐增大, 种群中更容易产生非支配解, 通过对相邻世代种群的模糊支配, 隶属度阈值变化一个步长的大小, 使得紧邻的下一代种群非支配解的数目可量化地减少.因此, 这种以步长为幅度自适应地调整支配阈值的方法适于处理一些高维多目标优化问题.此外, 由于黄金分割比例近年来被广泛应用于复杂系统优化中并取得了良好的效果, 受此启发, 这里将黄金分割点引入算法以执行种群规模的划分.
具体地, 设种群规模为${N}, $利用黄金分割点${G}$将种群分割为规模不等的两个子群, 则较小子群的规模为${N}-\lfloor G\cdot N \rfloor$ ($\lfloor \cdot \rfloor$表示向下取整).当规模为N的种群中非支配解的数目不超过${N}-\lfloor G\cdot N \rfloor$时, 以1/${Ds}$为步长降低支配阈值, 以放宽支配条件; 当种群中非支配解数目超过${N}-\lfloor G\cdot N \rfloor$时, 则增大支配阈值, 以缩紧支配条件.算法1给出了按步长自适应调整支配阈值的流程.
算法1.按步长自适应调整支配阈值
输入. 种群规模${N}, $最大进化代数, 黄金分割点G, 初始支配阈值${\lambda}_0$.
输出. 调整后的支配阈值.
1.基于模糊支配关系计算当前种群中非支配解的数目: Nondominated_Num.
2.计算步长1/${Ds}$.
3. IF ($Nondominated\_Num\leq N-\lfloor G\cdot N \rfloor$)
4. ${\lambda}(t)=({\lambda}(t)-1/Ds)$ //放宽支配条件
5. IF (${\lambda}(t)\leq 0.5$) //对阈值越下界的处理
6. 对${\lambda}$累加若干个步长, 直至${\lambda}>0.5$
7. END IF
8. ELSE
9. ${\lambda}(t)=({\lambda}(t)+1/Ds)$//缩紧支配条件
10. IF (${\lambda}(t)>1.0$)
11. ${\lambda}(t)=1.0$//对阈值越上界的处理
12. END IF
13. END IF
14.输出${\lambda}(t)$.
以上自适应模糊支配关系将MAOP问题中个体之间m个目标的比较转化成模糊隶属度和目标质量属性两个值的比较, 使得在目标个数很多时, 也能容易地评价个体的优劣, 并促进算法收敛.此过程没有加入任何的偏好信息, 没有引入额外的参数, 没有改变目标函数的数值, 更没有对目标进行删减, 而是利用了个体目标函数的完整信息.以步长为幅度调整支配阈值的大小, 实现精细化调控支配的松紧程度, 可满足不同情况下的需求, 因而自适应模糊支配关系较适合MAOP问题的求解.
2.2 增加扰动项的粒子速度更新方式
在粒子群优化算法中, 一个无质量的粒子i可视为MAOP问题的一个潜在解, 粒子i在搜索空间内以一定的速度飞行, 并根据其自身和集体的飞行经验来动态调整飞行速度.在基本PSO算法中粒子$i$的速度和位置的更新方程分别如式(7)和式(8)所示:
$ \begin{equation} v_{i, j}^{t+1}=wv_{i, j}^{t}+c_1r_1(Pbest_{i, j}^t-{x}_{i, j}^{t})+c_2r_2(Gbest_{j}^t-{x}_{i, j}^{t}) \end{equation} $
(7) $ \begin{equation} {x}_{i, j}^{t+1}={x}_{i, j}^{t}+v_{i, j}^{t+1} \end{equation} $
(8) 从式(7)可知, 粒子i在第t代的移动速度的变化受其自身历史最优位置${Pbest}_{i}^{t}$和全局最优位置${Gbest}^{t}$的共同影响, 图 1以2-目标优化问题为例, 示意在多目标粒子群算法中当前粒子i速度的变化趋势.
在多目标粒子群算法的前期, 粒子以较快的速度飞行, 且具有较强的全局搜索能力, 但在算法后期, 若粒子自身的历史最优位置${Pbest}_{i}^{t}$和全局最优位置${Gbest}^{t}$比较接近, 则容易导致大量粒子的聚集, 使得种群中粒子的多样性变差, 可能会引起算法早熟收敛.基于此, 这里考虑对多目标粒子群算法中粒子的速度公式进行改造, 通过增加一扰动项来增强种群的多样性, 从而有效避免算法陷入局部最优.其中的扰动粒子从外部档案(精英解集)中选择离当前粒子$i$的欧氏距离最近的个体.改造后的粒子速度更新如式(9)所示.
$ v_{i, j}^{t+1}= wv_{i, j}^{t}+c_1r_1(Pbest_{i, j}^t-{x}_{i, j}^{t})+\nonumber\\ c_2r_2(Gbest_{j}^t-{x}_{i, j}^{t})+ c_3r_3 (Pd_{i}^t-{x}_{i, j}^{t}) $
(9) 其中, 在式(7)$ \sim $(9)中, ${w}$为惯性权重, ${c}_1$、${c}_2$和${c}_3$为学习系数, ${r}_1$、${r}_2$和${r}_3$为区间[0, 1]上服从均匀分布的随机数, ${x}_{i}^t=({x}_{i, 1}^t, {x}_{i, 2}^t, \cdots, {x}_{i, n}^t)$和${v}_{i}^t=(v_{i, 1}^t, v_{i, 2}^t, \cdots, v_{i, n}^t)$为第t次迭代时粒子i在n维搜索空间中的位置和速度, 而${x}_{i, j}^t$和${v}_{i, j}^t$分别表示第t代的粒子i在搜索空间第j维上的位置和速度. ${Pbest}_{i}^t=(Pbest_{i, 1}^t, Pbest_{i, 2}^t, \cdots, Pbest_{i, n}^t)$为第t次迭代时粒子$i$的自身最佳位置, ${Gbest}_{i}^t=(Gbest_{i, 1}^t, Gbest_{i, 2}^t, \cdots, Gbest_{i, n}^t)$为第t次迭代时整个种群的全局最佳位置, ${Pbest}_{i, j}^t$和${Gbest}_{i, j}^t$分别表示第t次迭代时粒子i在第j维上的自身最佳位置和全局最佳位置. ${Pd}_{i}^t$表示第t次迭代时距离当前粒子i的欧氏距离最近的精英个体.在方程(9)的右边, 第1部分为粒子当前速度乘以惯性权重进行加速, 表示粒子对当前自身运动的信任, 依据自身的速度进行惯性运动; 第2部分为自我认知部分, 表示粒子对自身历史的思考; 第3部分为社会认知部分, 表示粒子在群体中的信息共享和相互合作; 第4部分为扰动部分, 表示粒子受到档案精英粒子的影响.图 2为增加一扰动项之后粒子$i$的速度更新示意图.从式(9)可知, 增加扰动项后多目标粒子群算法中粒子$i$的速度变化将受其历史最优解${Pbest}_{i}^{t}$、全局最优解${Gbest}^{t}$和离粒子$i$的欧氏距离最近的精英粒子${Pd}_{i}^t$的共同影响.而且从图 2也可看出, 加入扰动项之后的粒子可较好地逼近Pareto前沿.
图 2 增加扰动项之后算法中粒子的速度更新示意图Fig. 2 Velocity updation of particles after adding turbulence item in MOSPO从外部档案中选择距离当前粒子的欧氏距离最近的精英个体作为扰动粒子, 原因有二: 1)外部档案中的个体是算法迄今发现的较优秀的粒子, 它们一般更加靠近Pareto前沿, 新增精英个体引导粒子的移动将有利于粒子朝Pareto前沿靠近; 2)选择离当前粒子的欧氏距离最近的精英个体作为扰动粒子相当于对搜索空间进行均匀划分, 而且还能较好地引导粒子在多个子空间内进行深度搜索, 种群中粒子的多样性和搜索能力都能得以改善, 可有效防止算法早熟收敛.
2.3 全局最优位置的选取
在多目标粒子群算法中, 全局最优位置在引导粒子群朝Pareto前沿逼近的过程中发挥着重要的作用.由于MAOP问题的结果是一个非劣解集, 因此粒子$i$的全局最优位置有若干候选方案, 而不像单目标优化问题那样可以直接确定.多目标粒子群算法中每个粒子的全局最优位置从外部档案(精英集)中产生, 为防止档案中部分粒子被重复选取, 致使粒子朝相同的方向进化而造成聚集, 这里给档案集中的粒子赋予一定的选择概率, 依概率选择粒子$i$的全局最优位置.如果外部档案中某个精英个体被选为粒子$i$的全局最优位置, 则该精英个体再次被选中的概率将减少, 其减少的概率将均匀分配给档案集中其他的个体.式(10)给出了档案个体被选为全局最优位置后其概率的变化方式.
$ \begin{equation}\small P_k= \begin{cases} P_k-\dfrac{1}{size(pop)}, \ 若档案中精英个体k被选中\\ P_k+\dfrac{1}{size(pop)\times (size(archive)-1)}, \ \mbox {其他} \end{cases} \end{equation} $
(10) 其中, ${P}_k$表示外部档案集中的个体k被选中的概率, $size$($pop$)和$size$($archive$)分别表示粒子群和外部档案的规模, 初始时外部档案中所有的非劣解的选择概率取值为1/$size$($archive$).
2.4 改进的邻域拥挤密度估计方法
高维多目标优化问题的求解目标之一是要求获得的近似Pareto解集中的解个体不仅能均匀分布在Pareto前沿面上, 而且要求它们的分布尽量广泛.实现该目标需要体现出种群个体在目标空间的分布情况, 而个体之间的结构和联系主要表现为个体在目标空间中的疏密远近.这里采用一种简化的Harmonic归一化距离方法计算个体的拥挤密度, 一方面可克服Harmonic平均距离存在的缺陷[15], 另一方面可高效地维持群体的分布性.具体描述如下:
对于种群中的第i个个体, 假设在目标空间中与个体i的距离由近及远的个体距离依次为${d}_{i, 1}$, ${d}_{i, 2}$, $\cdots$, ${d}_{i, N-1}$, 则个体i的Harmonic平均距离如式(11)所示.
$ \begin{equation} \displaystyle d_i= \displaystyle \frac{N-1}{\displaystyle \frac{1}{d_{i, 1}}+ \displaystyle \frac{1}{d_{i, 2}}+\displaystyle\cdots+\displaystyle \frac{1}{\displaystyle d_{i, N-1}}} \end{equation} $
(11) 式(11)中的N为种群规模, 即个体Harmonic平均距离的计算考虑了种群其他所有个体的距离, 计算量很大.种群中相对距离较远的个体对所要计算邻域密度的个体的影响不应考虑在内, 会引入不必要的偏差, 造成资源浪费, 这种情况在高维多目标优化问题中尤为明显.在不影响精度的情况下, 这里提出减少参与计算平均距离的个体数量, 即计算的数目由$N-1$降为k, 并取, 可得到式(12):
$ \begin{equation} \displaystyle d_i= \displaystyle \frac{k}{\displaystyle \frac{1}{\displaystyle d_{i, 1}}+ \displaystyle \frac{1}{d_{i, 2}}+\displaystyle\cdots+\displaystyle \frac{1}{\displaystyle d_{i, N-1}}} \end{equation} $
(12) 鉴于种群个体之间的距离d可能为任意的正数, 为方便计算, 对${d}_{i, j}~(j=1, 2, \cdots, k)$用归一化方法进行规范, 可得相对距离为, 和${d}_{\rm max}$分别为种群中个体之间的最小距离和最大距离, 分布越好的个体其拥挤度应该越大.为了保持${d}_{i}$和${d}_{i, k}$的一致性, 可得, 而且一般距离越近的个体对该个体的拥挤度的影响越大, 反之距离越远影响会越小.为了扩大这种差异, 现对相对距离进行平方, 即, 由此可得个体拥挤距离的计算公式:
$ \begin{equation} \displaystyle d_i= \displaystyle \frac{k}{\displaystyle \sum\limits_{j=1}^k \displaystyle \left[1-\left(\frac{d_{i, j}-d_{\rm min}}{ d_{\rm max}-d_{\rm min}}\right)^2\right]} \end{equation} $
(13) 分析式(13)可以发现, 该拥挤密度的计算方法只考虑了个体在局部邻域内相邻的个个体之间的距离, 这种简化的Harmonic归一化距离方法相比于Harmonic平均距离减少了计算量.具体分析如下:设种群规模为N, 搜索空间的维度为n, 目标数为m.由于简化后的拥挤密度计算方法仅考虑了个相邻的个体, 其数量要少于Harmonic平均距离方法, 所以时间复杂度要小于Harmonic平均距离的复杂度${\rm O}(mn\log_2 n)$, 减少量为, 其总复杂度为.相比于循环拥挤排序方法, 这里使用简化的Harmonic归一化距离无需反复计算个体的拥挤密度, 仅需计算一次, 大大降低了算法的计算复杂度.
种群中的个体由于具有共同的相邻个体而联系在一起, 因此能在一定程度上反映出该个体在种群中的整体分布; 同时, 采取在该局部邻域内距离不同的个体对其拥挤度的影响不同的放大策略和归一化方法, 保证了个体具有较好的邻域分布.由此可见, 简化的拥挤密度估计方法能够从局部和全局两方面来维持种群的分布性.
2.5 高维多目标优化的环境选择策略
在高维多目标优化问题中, 决策空间和目标空间的搜索范围极大扩张, 自适应模糊支配关系虽然能在一定程度上增强选择压力, 提高收敛性能, 但如果环境选择策略设计不当, 则可能导致种群陷入局部最优甚至收敛停滞.针对这一问题, 本文利用文献[13]中改进的环境选择策略更新种群和外部档案, 而且引入两个参数${w}_1$和${w}_2$分别表示支配度权重和拥挤距离权重, 以协调收敛性和分布性.因此, 粒子$i$的适应度计算方法变化如下:
$ \begin{equation} fitness(i)=w_1\cdot r_{i}-w_2\cdot d_{i} \end{equation} $
(14) 其中, ${r}_{i}$和${d}_{i}$分别表示粒子$i$的支配度和拥挤距离, 详情参见文献[13].
2.6 MAPSOAF算法流程
在前面第2.1 $\sim$第2.5节的基础上, 算法2给出了自适应模糊支配的高维多目标粒子群算法的流程.
算法2. MAPSOAF算法流程
输入.种群规模N, 外部档案最大容量${N}_0$, 黄金分割点G, 初始支配阈值${\lambda}_0$, 最大迭代次数, 支配度权重${w}_1$, 拥挤距离权重${w}_2$.
输出. 外部档案集.
1.初始化规模为N的粒子群, 对每个粒子, 确定其初始位置和初始速度, 粒子的自身历史最好位置Pbest设置为粒子本身, 置外部档案集为空, 令迭代器${t}=1$.
2. WHILE (${t}\leq T_{\rm max}$)
3. 计算粒子群中各粒子的目标向量, 根据第2.1节的自适应模糊支配关系, 将较好的${N}_0$个个体拷贝至外部档案中.
4. 根据第2.2节和第2.3节为种群粒子选择扰动粒子和全局最优位置, 并依式(9)更新粒子速度.
5. 利用第2.4节中改进的拥挤密度方法为种群中的粒子计算拥挤距离.
6. 利用第2.5节的方法更新粒子群和外部档案集.
7. ${t} = t +1$
8. END WHILE
9.输出外部档案集.
3. 实验与结果分析
3.1 实验设置
3.1.1 对等比较算法
为检验MAPSOAF算法的性能, 这里选取5个代表性的多目标进化算法作为对比算法, 它们分别是: 1) Deb等[16]提出的改进型非劣分类遗传算法NSGA-II; 2) Nebro等[17]提出的基于档案的混合分散搜索算法AbYSS; 3) Zitzler等[18]提出的改进型强度Pareto进化算法SPEA2; 4) Nebro等[19]提出的限制速度的多目标粒子群算法SMPSO; 以及5) Wang等[20]提出的自适应调整约束子问题MOEA/D算法, 即MOEA/D-ACD算法.
3.1.2 高维多目标测试函数集
为检验本文算法的有效性, 这里将MAPSOAF算法与上述5种对比算法一同在4, 10, 30目标的DTLZ测试函数集[21]上进行实验比较.选用可扩展为任意目标维数和自变量维数的通用测试函数DTLZ{1, 2, 4, 5}.所有实验在硬件配置AMDA10-8 700P CPU 1.8 GHz主频8.0 GB内存, Windows 7 64位操作系统的ThinkPad E565计算机上运行. 1)当目标个数为4时, DTLZ函数集参数设置为:目标个数为4, 决策空间的维度为10, 算法的迭代次数为2 000; 2)当目标个数为10时, DTLZ函数集参数设置为:目标个数为10, 决策空间的维度为20, 算法迭代次数为5 000; 3)当目标个数为30时, DTLZ函数集参数设置为:目标个数为30, 决策空间维度为50, 算法的迭代次数为10 000.
3.1.3 性能指标
反转世代距离(Inverted generational distance, IGD) [22]度量了真实的Pareto前沿到算法获得的近似Pareto前沿之间的距离.由于DTLZ函数集的真实Pareto解集是已知的, 通过对真实Pareto解集进行多样性采样, 计算这些采样点到近似Pareto解点之间的距离既反映了算法的收敛性又能反映出算法所获解集的多样性.一般而言, IGD指标值越小则说明近似Pareto前沿的收敛性和多样性越好.设P是多目标优化问题的真实Pareto解集, 则IGD性能指标值可通过式(15)进行计算.
$ \begin{equation} \displaystyle IGD=\displaystyle \frac{1}{|P|}\displaystyle\sum\limits_{\displaystyle i=1}^{\displaystyle |P|}\displaystyle Dist_{i} \end{equation} $
(15) 其中, 为归一化后的最小的欧氏距离; $f_{m}^{\rm max}$和分别表示集合P在第m个目标上获得的最大值和最小值; ${p}_{i}\in P$, $i= 1, 2, \cdots$, $|{P}|$; ${a}_{j}\in A$, $j = 1, 2, \cdots$, $|{A}|$.实验对各测试函数采样10 000个均匀分布的Pareto最优解点作为真实Pareto前沿的近似解集来计算IGD值.
3.1.4 实验参数
5种对比算法的主要参数均采用对应参考文献中的建议值, 如表 1所示.
表 1 5种对比算法的参数设置Table 1 Parameter settings of all the algorithms comparedAlgorithm Parameter settings NSGA-II ${N}=100, P_{c}=0.9, P_{m}=1/n, \eta_{c}=20, \eta_{m}=20$ SPEA2 ${N}=100, P_{c}=0.9, P_{m}=1/n, \eta_{c}=20, \eta_{m}=20$ SMPSO ${C}_1\in[1.5, 2.5], C_2\in[1.5, 2.5], P_{m}=1/n, \eta_{m}=20$ AbYSS ${N}=100, N_{RefSet1}=10, N_{RefSet2}=10, P_{c}=0.9, P_{m}=1/n, \eta_{c}=20, \eta_{m}=20$ MOEA/D-ACD ${N}=100, CR=1.0, F=0.5, P_{m}=1/n, \eta_{m}=20, \delta=0.9, n_{r}=2$ 在表 1中, N表示种群规模; ${P}_{c}$表示杂交概率; ${P}_{m}$表示变异概率; $\eta_{c}=20$和$\eta_{m}=20$分别是SBX和多项式变异的分布指数.对于AbYSS算法而言, ${N}_{RefSet1}$和${N}_{RefSet2}$分别是RefSet1和RefSet2的规模.在MOEA/D-ACD算法中, T定义了在加权系数中邻域的规模, ${\eta}$为控制从T个邻域解中选择父本的概率, 而${n}_{r}$表示父代个体被子代个体取代的最大数目. ${C}_1$和${C}_2$是SMPSO算法中两个从区间[1.5, 2.5]的范围内随机选取的控制参数.需要指出, 对比算法的参数是经过适当调参后为解决本文实验中绝大多数的MAOP问题而设定的.为公平比较起见, 本文MAPSOAF算法的主要参数参照其他对比算法进行设置, 例如MAPSOAF种群规模为100, 外部档案的最大容量为100, 而计算个体适应度的支配度和拥挤距离的权重系数则参考文献[15]的研究, 分别取${w}_1=$1.5, ${w}_1$=0.5.
为减少随机误差对统计结果的影响, 这里所有的实验各执行30次, 每次使用不同的随机数种子, 以统计IGD的均值和方差.此外, 为了使获得的结论在统计上合理、可靠, 这里采用Wilcoxon$'$s rank sum test来检验MAPSOAF算法和其他对比算法所获得的结果具有水平为$\alpha=0.5$的显著性差异.
3.2 实验结果与分析
表 2 $\sim$表 5分别统计了函数DTLZ{1, 2, 4, 5}具有4、10和30个目标时获得的IGD均值(mean)和标准差(std), 其中采用粗体显示不同算法在同一测试函数上获得的最好的IGD均值, 表中的"+", "$-$"和" $\approx$"分别表示算法获得的结果要显著地优于、劣于和相似于MAPSOAF算法获得的水平为$\alpha=0.05$的Wilcoxon秩和检验的结果.
表 2 各算法在DTLZ1函数上获得IGD值的比较Table 2 Results of IGD for algorithms compared based on DTLZ1各项指标 算法 NSGA-II AbYSS SPEA2 SMPSO MOEA$/$D-ACD MAPSOAF 目标个数 4目标 mean 2.0458E-01 9.5918E-02 1.7712E-01 7.8417E-02 3.4736E-01 8.2288E-02 std 5.6012E-04 5.5421E-04 1.1871E-04 4.0001E-04 5.8170E-05 8.4901E-04 rank 5 $-$ 3 $-$ 4 $-$ 1 + 6 $-$ 2 10目标 mean 6.7936E-01 5.9651E-01 6.1816E-01 5.0051E-01 6.9881E-01 4.9810E-01 std 4.9647E-04 7.5481E-04 3.6454E-04 4.7007E-04 4.4327E-05 7.5541E-04 rank 5 $-$ 3 $-$ 4 $-$ 2 $\approx$ 6 $-$ 1 30目标 mean 7.9579E-01 7.8171E-01 7.7545E-01 7.4014E-01 8.0986E-01 6.5187E-01 std 2.1294E-04 4.5699E-03 6.5441E-04 0.00E+00 2.9857E-04 5.3458E-03 rank 5 $-$ 3 $-$ 4 $-$ 2 $\approx$ 6 $-$ 1 rank sum 15 10 11 5 18 4 final rank 5 3 4 2 6 1 better$/$worst$/$similar 0$/3/$0 0$/3/$0 0$/3/$0 1$/1/$1 0$/3/$0 $/$ 从表 2可以看出, MAPSOAF算法在10-目标和30-目标的DTLZ1问题上分别获得了最优的IGD均值, SMPSO算法在4-目标的DTLZ1问题上获得了最好的IGD均值, 但本文的算法在该问题上获得的IGD值与SMPSO算法获得的IGD值具有相同的数量级($10^{-2}$), 表明MAPSOAF算法在4-目标的DTLZ1问题上的表现仅稍逊于SMPSO算法, 而要优于AbYSS、SPEA2、NSGA-II和MOEA/D-ACD算法.其次, 通过统计各算法在DTLZ1(4, 10, 30)三个测试例上获得的IGD值的最终排序, 表现最好的是MAPSOAF, 然后依次是SMPSO、AbYSS、SPEA2、NSGA-II和MOEA/D-ACD.从表 2的"better/worst/similar"结果来看, 各算法在DTLZ1(4, 10, 30)三个测试函数上只有SMPSO的结果是"1/1/1", 而其他4种对比算法的结果均是"0/3/0", 这表明MAPSOAF算法在这3个高维多目标的DTLZ1问题上较之其他对比算法具有显著的IGD性能优势.由于DTLZ1问题的Pareto前沿具有线性、多模态的特征, 说明MAPSOAF算法在求解此类问题特征的MAOP问题时较其他算法更具优势.
表 3给出了各算法在4、10和30目标的DTLZ2问题上获得的IGD值. MAPSOAF算法分别在10-目标和30-目标的DTLZ2问题上获得了最好的IGD均值结果, 而NSGA-II算法则在4-目标的DTLZ2问题上获得了最佳的IGD均值.需要指出的是, MAPSOAF算法在4-目标的DTLZ2问题上获得的IGD值仅略差于NSGA-II算法(二者处于相同的数量级$10^{-2}$), 而要优于SMPSO、AbYSS、SPEA2和MOEA/D-ACD算法.此外, 通过统计各算法在DTLZ2(4, 10, 30)三个测试例上获得的IGD值的最终排序, 表现最好的是MAPSOAF, 然后依次是NSGA-II、SMPSO、AbYSS、SPEA2和MOEA/D-ACD.从表 3的"better/worst/similar"来看, 各算法在DTLZ2(4, 10, 30)三个测试函数上只有NSGA-II的结果是"1/1/1", 而其他4种对比算法的结果均是"0/3/0", 这表明本文算法在这3个高维多目标的DTLZ2问题上较其他对比算法而言具有显著的IGD性能优势.由于DTLZ2问题具有凹状Pareto前沿, 表明MAPSOAF算法能够较好地求解具有这类问题特征的MAOP问题.
表 3 各算法在DTLZ2函数上获得IGD值的比较Table 3 Results of IGD for algorithms compared based on DTLZ2各项指标 算法 NSGA-II AbYSS SPEA2 SMPSO MOEA$/$D-ACD MAPSOAF 目标个数 4目标 mean 7.0109E-02 2.8412E-01 3.5341E-01 1.5415E-01 4.1627E-01 8.9241E-02 std 5.1015E-04 7.1918E-04 6.8418E-04 4.5159E-04 1.8748E-04 4.6174E-04 rank 1+ 4 $-$ 5 $-$ 3 $-$ 6 $-$ 2 10目标 mean 5.2851E-01 5.6171E-01 6.0151E-01 5.5241E-01 6.9741E-01 4.8169E-01 std 5.6740E-04 6.9151E-04 5.9871E-04 5.1762E-04 3.5061E-04 5.5651E-04 rank 2 $\approx$ 4 $-$ 5 $-$ 3 $-$ 6 $-$ 1 30目标 mean 7.5548E-01 7.8851E-01 7.8158E-01 7.7941E-01 7.9967E-01 6.9181E-01 std 6.5141E-03 5.9210E-04 4.2225E-04 6.2131E-03 5.1101E-04 3.6518E-03 rank 2 $-$ 5 $-$ 4 $-$ 3 $-$ 6 $-$ 1 rank sum 5 13 14 9 18 4 final rank 2 4 5 3 6 1 better$/$worst$/$similar 1$/1/$1 0$/3/$0 0$/3/$0 0$/0/$0 0$/3/$0 $/$ 从表 4可知: MOEA/D-ACD算法在DTLZ4(4, 10, 30)三个高维目标测试问题上均获得了最优的IGD均值, 而MAPSOAF算法在4-目标的DTLZ4问题上排名第2, 在10-目标和30-目标的DTLZ4问题上均排名第3.通过统计各算法在DTLZ4(4, 10, 30)三个测试例上获得的IGD值的最终排名, 表现最好的是MOEA/D-ACD, 然后依次是NSGA-II、MAPSOAF、SMPSO、AbYSS和SPEA2.从表 4的"better/worst/similar"来看, MOEA/D-ACD获得的结果是"3/0/0", 而NSGA-II获得的结果是"0/2/1", 而其他两种对比算法的结果均是"0/3/0".由此可见, 在DTLZ4(4, 10, 30)三个测试函数上, MOEA/D-ACD算法的IGD性能是最佳的, 而MAPSOAF算法的表现只能处于中游位置. DTLZ4问题的Pareto前沿为凹形、有偏的特点, 说明本文算法在求解具有这类问题特征的MAOP问题时性能尚待提高.
表 4 各算法在DTLZ4函数上获得IGD值的比较Table 4 Results of IGD for algorithms compared based on DTLZ4各项指标 算法 NSGA-II AbYSS SPEA2 SMPSO MOEA$/$D-ACD MAPSOAF 目标个数 4目标 mean 8.3841E-02 2.1541E-01 2.6114E-01 1.5116E-01 7.1981E-02 7.9141E-02 std 3.2987E-04 4.1123E-04 5.6101E-04 6.8917E-04 3.3176E-04 4.5005E-04 rank 3 $\approx$ 5 $-$ 6 $-$ 4 $-$ 1+ 2 10目标 mean 5.8584E-01 6.5141E-01 6.9184E-01 6.6810E-01 5.4214E-01 5.9515E-01 std 5.8771E-04 4.4414E-04 6.6516E-04 7.0151E-04 3.6011E-04 4.6001E-04 rank 2 $\approx$ 4 $-$ 6 $-$ 5 $-$ 1+ 3 30目标 mean 7.5541E-01 8.2994E-01 8.0441E-01 8.1945E-01 7.0713E-01 7.9541E-01 std 8.8151E-03 8.5104E-04 2.9414E-03 4.6054E-03 5.6807E-03 5.1112E-03 rank 2 $-$ 6 $-$ 4 $-$ 5 $-$ 1+ 3 rank sum 7 15 16 14 3 8 final rank 2 5 6 4 1 3 better$/$worst$/$similar 0$/2/$1 0$/3/$0 0$/3/$0 0$/3/$0 3$/0/$0 $/$ 从表 5可以看出, MAPSOAF算法在DTLZ5(4, 10, 30)三个测试函数上均获得了最优的IGD均值.通过统计各算法在DTLZ5(4, 10, 30)三个测试例上获得的IGD值的最终排序, 表现最好的是MAPSOAF, 然后依次是SMPSO、NSGA-II、SPEA2、AbYSS和MOEA/D-ACD.从表 5最末一行的"better/worst/similar"来看, 各算法在DTLZ1(4, 10, 30)三个测试函数上只有NSGA-II的结果是"0/2/1"以及SMPSO的结果是"0/3/1", 而其他两种对比算法的结果均是"0/3/0".表 5的结果表明MAPSOAF算法在DTLZ5(4, 10, 30)三个测试问题上较之其他几种对比算法具有显著的性能优势. DTLZ5问题具有凹形且退化的Pareto前沿, 而MAPSOAF算法能在该MAOP问题上获得较好的结果.
表 5 各算法在DTLZ5函数上获得IGD值的比较Table 5 Results of IGD for algorithms compared based on DTLZ5各项指标 算法 NSGA-II AbYSS SPEA2 SMPSO MOEA$/$D-ACD MAPSOAF 目标个数 4目标 mean 1.38121E-01 1.6051E-01 1.7717E-01 9.5651E-02 1.8678E-01 9.1410E-02 std 5.6012E-04 5.5421E-04 1.1871E-04 4.0001E-04 5.8170E-05 8.4901E-04 rank 3 $-$ 4 $-$ 5 $-$ 2 $\approx$ 6 $-$ 1 10目标 mean 6.5172E-01 7.1141E-01 7.0914E-01 6.9241E-01 7.2661E-01 5.0941E-01 std 7.5615E-04 5.5551E-04 4.1191E-04 6.4101E-04 5.5827E-04 5.9151E-04 rank 2 $\approx$ 5 $-$ 4 $-$ 3 $-$ 6 $-$ 1 30目标 mean 7.7141E-01 7.8810E-01 7.6585E-01 7.6151E-01 7.9841E-01 6.9510E-01 std 3.4287E-03 8.8140E-04 3.9410E-03 4.6415E-03 8.2662E-04 4.6519E-03 rank 4 $-$ 5 $-$ 3 $-$ 2 $-$ 6 $-$ 1 rank sum 9 14 13 7 18 3 final rank 3 5 4 2 6 1 better$/$worst$/$similar 0$/2/$1 0$/3/$0 0$/3/$0 0$/3/$1 0$/3/$0 $/$ 综观表 2 $\sim$表 5的实验结果, MAPSOAF算法相对其他5种代表性MOEA算法总体上具有显著的收敛性和多样性上的优势.究其原因, MAPSOAF算法通过定义步长幅度自适应地调整模糊隶属度支配的阈值, 实现了对种群选择压力的精细化控制, 能较好地改善算法的收敛性能; 其次, MAPSOAF算法在粒子飞行速度的更新公式中新增了一扰动项, 而且扰动粒子来源于外部档案中不重复的精英解, 这种策略一方面能克服种群早熟收敛的缺点, 另一方面也能改善群体分布的均匀性; 此外, MAPSOAF算法采用简化的Harmonic归一化距离方法评估个体的拥挤密度, 既改善了种群的分布性, 同时减小了计算代价, 提高了算法的效率.这三种策略相同协同, 有效地提高了算法在求解高维多目标优化问题时的总体性能.
4. 结论
高维多目标优化问题巨大的目标空间使得一些经典的多目标优化算法面临困境, 迫切需要发展新型高维多目标优化算法应对挑战.论文提出一种基于自适应模糊支配的高维多目标粒子群算法MAPSOAF, 该算法以步长为幅度, 自适应地调整模糊隶属度支配阈值, 实现对种群选择压力的精细化控制; 其次算法在粒子速度更新公式中新增一扰动项, 实现在克服种群早熟收敛的同时改善群体的分布性; 最后, 算法采用简化的Harmonic归一化距离评估个体的密度, 实现改善群体分布性的同时降低算法的计算代价. MAPSOAF算法与其他5种代表性的MOEA算法在12个基准高维多目标测试函数上进行IGD性能实验, 结果表明本文的算法具有较显著的收敛性和多样性的性能优势.
未来将利用MAPSOAF算法求解实践中如雷达优化问题、水资源优化问题、翼行设计问题和护士排班等典型高维多目标优化问题, 以进一步测试和改善算法的性能; 另外, 考虑将一些新近提出的进化范例引入到高维多目标优化算法的框架中, 以不断提高解决复杂MAOP问题的能力.
-
图 2 增加扰动项之后算法中粒子的速度更新示意图
Fig. 2 Velocity updation of particles after adding turbulence item in MOSPO
表 1 5种对比算法的参数设置
Table 1 Parameter settings of all the algorithms compared
Algorithm Parameter settings NSGA-II ${N}=100, P_{c}=0.9, P_{m}=1/n, \eta_{c}=20, \eta_{m}=20$ SPEA2 ${N}=100, P_{c}=0.9, P_{m}=1/n, \eta_{c}=20, \eta_{m}=20$ SMPSO ${C}_1\in[1.5, 2.5], C_2\in[1.5, 2.5], P_{m}=1/n, \eta_{m}=20$ AbYSS ${N}=100, N_{RefSet1}=10, N_{RefSet2}=10, P_{c}=0.9, P_{m}=1/n, \eta_{c}=20, \eta_{m}=20$ MOEA/D-ACD ${N}=100, CR=1.0, F=0.5, P_{m}=1/n, \eta_{m}=20, \delta=0.9, n_{r}=2$ 
下载: 导出CSV
表 2 各算法在DTLZ1函数上获得IGD值的比较
Table 2 Results of IGD for algorithms compared based on DTLZ1
各项指标 算法 NSGA-II AbYSS SPEA2 SMPSO MOEA$/$D-ACD MAPSOAF 目标个数 4目标 mean 2.0458E-01 9.5918E-02 1.7712E-01 7.8417E-02 3.4736E-01 8.2288E-02 std 5.6012E-04 5.5421E-04 1.1871E-04 4.0001E-04 5.8170E-05 8.4901E-04 rank 5 $-$ 3 $-$ 4 $-$ 1 + 6 $-$ 2 10目标 mean 6.7936E-01 5.9651E-01 6.1816E-01 5.0051E-01 6.9881E-01 4.9810E-01 std 4.9647E-04 7.5481E-04 3.6454E-04 4.7007E-04 4.4327E-05 7.5541E-04 rank 5 $-$ 3 $-$ 4 $-$ 2 $\approx$ 6 $-$ 1 30目标 mean 7.9579E-01 7.8171E-01 7.7545E-01 7.4014E-01 8.0986E-01 6.5187E-01 std 2.1294E-04 4.5699E-03 6.5441E-04 0.00E+00 2.9857E-04 5.3458E-03 rank 5 $-$ 3 $-$ 4 $-$ 2 $\approx$ 6 $-$ 1 rank sum 15 10 11 5 18 4 final rank 5 3 4 2 6 1 better$/$worst$/$similar 0$/3/$0 0$/3/$0 0$/3/$0 1$/1/$1 0$/3/$0 $/$
下载: 导出CSV
表 3 各算法在DTLZ2函数上获得IGD值的比较
Table 3 Results of IGD for algorithms compared based on DTLZ2
各项指标 算法 NSGA-II AbYSS SPEA2 SMPSO MOEA$/$D-ACD MAPSOAF 目标个数 4目标 mean 7.0109E-02 2.8412E-01 3.5341E-01 1.5415E-01 4.1627E-01 8.9241E-02 std 5.1015E-04 7.1918E-04 6.8418E-04 4.5159E-04 1.8748E-04 4.6174E-04 rank 1+ 4 $-$ 5 $-$ 3 $-$ 6 $-$ 2 10目标 mean 5.2851E-01 5.6171E-01 6.0151E-01 5.5241E-01 6.9741E-01 4.8169E-01 std 5.6740E-04 6.9151E-04 5.9871E-04 5.1762E-04 3.5061E-04 5.5651E-04 rank 2 $\approx$ 4 $-$ 5 $-$ 3 $-$ 6 $-$ 1 30目标 mean 7.5548E-01 7.8851E-01 7.8158E-01 7.7941E-01 7.9967E-01 6.9181E-01 std 6.5141E-03 5.9210E-04 4.2225E-04 6.2131E-03 5.1101E-04 3.6518E-03 rank 2 $-$ 5 $-$ 4 $-$ 3 $-$ 6 $-$ 1 rank sum 5 13 14 9 18 4 final rank 2 4 5 3 6 1 better$/$worst$/$similar 1$/1/$1 0$/3/$0 0$/3/$0 0$/0/$0 0$/3/$0 $/$
下载: 导出CSV
表 4 各算法在DTLZ4函数上获得IGD值的比较
Table 4 Results of IGD for algorithms compared based on DTLZ4
各项指标 算法 NSGA-II AbYSS SPEA2 SMPSO MOEA$/$D-ACD MAPSOAF 目标个数 4目标 mean 8.3841E-02 2.1541E-01 2.6114E-01 1.5116E-01 7.1981E-02 7.9141E-02 std 3.2987E-04 4.1123E-04 5.6101E-04 6.8917E-04 3.3176E-04 4.5005E-04 rank 3 $\approx$ 5 $-$ 6 $-$ 4 $-$ 1+ 2 10目标 mean 5.8584E-01 6.5141E-01 6.9184E-01 6.6810E-01 5.4214E-01 5.9515E-01 std 5.8771E-04 4.4414E-04 6.6516E-04 7.0151E-04 3.6011E-04 4.6001E-04 rank 2 $\approx$ 4 $-$ 6 $-$ 5 $-$ 1+ 3 30目标 mean 7.5541E-01 8.2994E-01 8.0441E-01 8.1945E-01 7.0713E-01 7.9541E-01 std 8.8151E-03 8.5104E-04 2.9414E-03 4.6054E-03 5.6807E-03 5.1112E-03 rank 2 $-$ 6 $-$ 4 $-$ 5 $-$ 1+ 3 rank sum 7 15 16 14 3 8 final rank 2 5 6 4 1 3 better$/$worst$/$similar 0$/2/$1 0$/3/$0 0$/3/$0 0$/3/$0 3$/0/$0 $/$
下载: 导出CSV
表 5 各算法在DTLZ5函数上获得IGD值的比较
Table 5 Results of IGD for algorithms compared based on DTLZ5
各项指标 算法 NSGA-II AbYSS SPEA2 SMPSO MOEA$/$D-ACD MAPSOAF 目标个数 4目标 mean 1.38121E-01 1.6051E-01 1.7717E-01 9.5651E-02 1.8678E-01 9.1410E-02 std 5.6012E-04 5.5421E-04 1.1871E-04 4.0001E-04 5.8170E-05 8.4901E-04 rank 3 $-$ 4 $-$ 5 $-$ 2 $\approx$ 6 $-$ 1 10目标 mean 6.5172E-01 7.1141E-01 7.0914E-01 6.9241E-01 7.2661E-01 5.0941E-01 std 7.5615E-04 5.5551E-04 4.1191E-04 6.4101E-04 5.5827E-04 5.9151E-04 rank 2 $\approx$ 5 $-$ 4 $-$ 3 $-$ 6 $-$ 1 30目标 mean 7.7141E-01 7.8810E-01 7.6585E-01 7.6151E-01 7.9841E-01 6.9510E-01 std 3.4287E-03 8.8140E-04 3.9410E-03 4.6415E-03 8.2662E-04 4.6519E-03 rank 4 $-$ 5 $-$ 3 $-$ 2 $-$ 6 $-$ 1 rank sum 9 14 13 7 18 3 final rank 3 5 4 2 6 1 better$/$worst$/$similar 0$/2/$1 0$/3/$0 0$/3/$0 0$/3/$1 0$/3/$0 $/$
下载: 导出CSV
-
[1] Adra S F, Fleming P J. A diversity management operator for evolutionary many-objective optimisation. In: International Conference on Evolutionary Multi-Criterion Optimization. Berlin, Heidelberg, Germany: Springer-Verlag, 2009. 81-94 [2] Wagner T, Beume N, Naujoks B. Pareto-, aggregation-, and indicator-based methods in many-objective optimization. In: International Conference on Evolutionary Multi-Criterion Optimization. Berlin, Heidelberg, Germany: Springer-Verlag, 2007. 742-756 [3] Li M Q, Yang S X, Liu X H. Shift-based density estimation for Pareto-based algorithms in many-objective optimization. IEEE Transactions on Evolutionary Computation, 2014, 18(3):348-365 doi: 10.1109/TEVC.2013.2262178 [4] 陈振兴, 严宣辉, 吴坤安, 白猛.融合张角拥挤控制策略的高维多目标优化.自动化学报, 2015, 41(6):1145-1158 http://www.aas.net.cn/CN/abstract/abstract18689.shtmlChen Zhen-Xing, Yan Xuan-Hui, Wu Kun-An, Bai Meng. Many-objective optimization integrating open angle based congestion control strategy. Acta Automatica Sinica, 2015, 41(6):1145-1158 http://www.aas.net.cn/CN/abstract/abstract18689.shtml [5] 巩敦卫, 刘益萍, 孙晓燕, 韩玉艳.基于目标分解的高维多目标并行进化优化方法.自动化学报, 2015, 41(8):1438-1451 http://www.aas.net.cn/CN/Y2015/V41/I8/1438Gong Dun-Wei, Liu Yi-Ping, Sun Xiao-Yan, Han Yu-Yan. Parallel many-objective evolutionary optimization using objectives decomposition. Acta Automatica Sinica, 2015, 41(8):1438-1451 http://www.aas.net.cn/CN/Y2015/V41/I8/1438 [6] Drechsler D, Drechsler R, Becker B. Multi-objective optimisation based on relation favour. In: Proceedings of the 1st International Conference on Evolutionary Multi-Criterion Optimization. London, UK: Springer-Verlag, 2001. 154-166 [7] Di Pierro F, Djordjević S, Kapelan Z, Khu S T, Savić D, Walters G A. Automatic calibration of urban drainage model using a novel multi-objective genetic algorithm. Water Science and Technology, 2005, 52(5):43-52 doi: 10.2166/wst.2005.0105 [8] Sato H, Aguirre H E, Tanaka K. Controlling dominance area of solutions and its impact on the performance of MOEAs. In: International Conference on Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science, Vol.4403. Berlin, Germany: Springer, 2007. 5-20 [9] Hernández-Díaz A, Santana-Quintero L, Coello-Coello C, Molina J. Pareto-adaptive ε-dominance. Evolutionary Computation, 2007, 15(4):493-517 doi: 10.1162/evco.2007.15.4.493 [10] Kang Z, Kang L S, Zou X F, Liu M Z, Li C H, Yang M, et al. A new evolutionary decision theory for many-objective optimization problems. In: Advances in Computation and Intelligence. Berlin, Heidelberg, Germany: Springer, 2007. 1-11 [11] Zou X F, Chen Y, Liu M Z, Kang L S. A new evolutionary algorithm for solving many-objective optimization problems. IEEE Transactions on Systems, Man, and Cybernetics-Part B:Cybernetics, 2008, 38(5):1402-1412 doi: 10.1109/TSMCB.2008.926329 [12] Farina M, Amato P. A fuzzy definition of "optimality" for many-criterion optimization problems. IEEE Transactions on Systems, Man, and Cybernetics-Part A:Systems and Humans, 2004, 34(3):315-326 doi: 10.1109/TSMCA.2004.824873 [13] 毕晓君, 张永建, 陈春雨.基于模糊支配的高维多目标进化算法MFEA.电子学报, 2014, 42(8):1653-1659 doi: 10.3969/j.issn.0372-2112.2014.08.031Bi Xiao-Jun, Zhang Yong-Jian, Chen Chun-Yu. A many-objective evolutionary algorithm based on fuzzy dominance:MFEA. Acta Electronica Sinica, 2014, 42(8):1653-1659 doi: 10.3969/j.issn.0372-2112.2014.08.031 [14] Kennedy J, Eberhart R C. Particle swarm optimization. In: Proceedings of the 1995 IEEE International Conference on Neural Networks. Perth, WA, Australia: IEEE, 1995. 1942-1948 [15] 肖婧, 毕晓君, 王科俊.基于全局排序的高维多目标优化研究.软件学报, 2015, 26(7):1574-1583 http://d.old.wanfangdata.com.cn/Periodical/rjxb201507002Xiao Jing, Bi Xiao-Jun, Wang Ke-Jun. Research of global ranking based many-objective optimization. Journal of Software, 2015, 26(7):1574-1583 http://d.old.wanfangdata.com.cn/Periodical/rjxb201507002 [16] Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197 doi: 10.1109/4235.996017 [17] Nebro A J, Luna F, Alba E, Dorronsoro B, Durillo J J, Beham A. AbYSS:adapting scatter search to multiobjective optimization. IEEE Transactions on Evolutionary Computation, 2008, 12(4):439-457 doi: 10.1109/TEVC.2007.913109 [18] Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the Strength Pareto Evolutionary Algorithm, TIK-Report 103, 2001. [19] Nebro A J, Durillo J J, Garcia-Nieto J, Coello Coello C A, Luna F, Alba E. SMPSO: a new PSO-based metaheuristic for multi-objective optimization. In: Proceedings of the 2009 IEEE Symposium on Computational Intelligence in Multi-Criteria Decision-Making (MCDM). Nashville, TN, USA, 2009, 66-73 [20] Wang L P, Zhang Q F, Zhou A M, Gong M G, Jiao L C. Constrained subproblems in a decomposition-based multiobjective evolutionary algorithm. IEEE Transactions on Evolutionary Computation, 2016, 20(3):475-480 doi: 10.1109/TEVC.2015.2457616 [21] Deb K, Thiele L, Laumanns M, Zitzler E. Scalable multi-objective optimization test problems. In: Proceedings of the 2002 IEEE Congress on Evolutionary Computation. Honolulu, HI, USA: IEEE, 2002. 825-830 [22] Zhang Q F, Zhou A M, Zhao S Z, Suganthan P N, Liu W D, Tiwari S. Multiobjective Optimization Test Instances for the CEC 2009 Special Session and Competition, Technical Report CES-487, 2009. 期刊类型引用(25)
1. 谢承旺，潘嘉敏，郭华，王冬梅，付世炜. 一种采用混合策略的大规模多目标进化算法. 计算机学报. 2024(01): 69-89 . 
百度学术2. 叶倩琳，王万良，王铮. 多目标粒子群优化算法及其应用研究综述. 浙江大学学报(工学版). 2024(06): 1107-1120+1232 . 百度学术3. 刘亚丽，熊伟，韩驰，熊明晖，刘正. 基于TOPSIS-MOPSO的侦察星座优化设计. 电讯技术. 2024(06): 893-901 . 百度学术4. 刘亚丽，熊伟. 基于多目标进化算法的侦察星座优化方法研究. 指挥控制与仿真. 2024(04): 97-104 . 百度学术5. 闵芬，董文波，丁炜超. 基于决策变量时域变化特征分类的动态多目标进化算法. 自动化学报. 2024(11): 2154-2176 . 本站查看6. 寇发荣，郭心如，高建，刘朋涛. 电液馈能互联悬架侧倾与俯仰协调优化. 噪声与振动控制. 2024(06): 1-8 . 百度学术7. 曾依浦，戴毅茹，陈雨田. 基于反向学习和精英提升的无速度项动态粒子群算法. 计算机与现代化. 2023(03): 113-120 . 百度学术8. 侯莹，吴毅琳，白星，韩红桂. 数据驱动选择策略的多目标差分进化算法. 控制与决策. 2023(07): 1816-1824 . 百度学术9. 马晓东，魏利胜. 基于PSO磁悬浮球系统自适应灰预测控制. 重庆工商大学学报(自然科学版). 2023(05): 16-24 . 百度学术10. Sifeng Zhu，Chengrui Yang，Jiaming Hu. MaOEA/I:Many-objective Evolutionary Algorithm Based on Indicator I_(ε+). Journal of Harbin Institute of Technology(New Series). 2023(05): 52-64 . 必应学术11. 郭成，张万达，王波，王加富. 多种群并行协作的粒子群算法. 计算机与现代化. 2022(01): 33-40 . 百度学术12. 谢承旺，余伟伟，郭华，张伟，张琼冰. DAV-MOEA:一种采用动态角度向量支配关系的高维多目标进化算法. 计算机学报. 2022(02): 317-333 . 百度学术13. 张凯庆，嵇启春. 速度时变的多中心半开放式车辆路径问题研究. 系统仿真学报. 2022(04): 836-846 . 百度学术14. 梁正平，骆婷婷，王志强，朱泽轩，胡凯峰. 一种基于目标空间转换权重求和的超多目标进化算法. 自动化学报. 2022(04): 1060-1078 . 本站查看15. 何江红，李军华，周日贵. 参考点自适应调整下评价指标驱动的高维多目标进化算法. 自动化学报. 2022(06): 1569-1589 . 本站查看16. 许振兴，祝水然. 多策略融合改进的多目标粒子群算法（英文）. Journal of Measurement Science and Instrumentation. 2022(03): 284-299 . 百度学术17. 张伟，黄卫民. 基于种群分区的多策略自适应多目标粒子群算法. 自动化学报. 2022(10): 2585-2599 . 本站查看18. 郑峰婴，王峰，甄子洋，许梦园，范涛. 先进布局无人机多目标自适应概率引导控制分配. 控制理论与应用. 2022(12): 2366-2376 . 百度学术19. 张勇，杨康，郝国生，巩敦卫. 基于相似历史信息迁移学习的进化优化框架. 自动化学报. 2021(03): 652-665 . 本站查看20. 杨五四，陈莉，王毅，张茂省. 一种适应度排序的高维多目标粒子群优化算法. 西安电子科技大学学报. 2021(03): 78-84 . 百度学术21. 张勇，胡江涛. 高计算代价动态优化问题的代理模型辅助粒子群优化算法. 陕西师范大学学报(自然科学版). 2021(05): 71-84 . 百度学术22. 王霞，王耀民，施心陵，高莲，李鹏. 噪声环境下基于蒲丰距离的依概率多峰优化算法. 自动化学报. 2021(11): 2691-2714 . 本站查看23. 万琴，颜金娥，李智，肖岳平，陈国泉. 基于改进RANSAC算法的全景图像拼接技术. 光电子·激光. 2021(12): 1253-1261 . 百度学术24. 谢承旺，余伟伟，闭应洲，汪慎文，胡玉荣. 一种基于分解和协同的高维多目标进化算法. 软件学报. 2020(02): 356-373 . 百度学术25. 张利峰. 无线网络环境下传输感知图像的模糊处理算法. 金陵科技学院学报. 2020(01): 6-9 . 百度学术其他类型引用(18)
-
下载:
计量
- 文章访问数: 3223
- HTML全文浏览量: 415
- PDF下载量: 645
- 被引次数: 43
