第16卷第2期 智能系统学报 Vol.16 No.2 2021年3月 CAAI Transactions on Intelligent Systems Mar.2021 D0:10.11992/tis.202006042 网络出版地址：https:/ns.cnki.net/kcms/detail/23.1538.TP.20201110.0926.002.html 目标空间映射策略的高维多目标粒子群优化算法 陈强，王宇嘉，梁海娜，孙欣 (上海工程技术大学电子电气工程学院，上海201620)】 摘要：为了平衡优化算法在高维多目标优化问题中收敛性和多样性之间的关系，增加算法的选择压力，本文 提出了一种基于目标空间映射策略的高维多目标粒子群优化算法(many-objective particle swarm optimization al- gorithm based on objective space mapping strategy,MOPSO-OSM。在求解高维多目标优化问题时，Pareto准则难以 从众多的非支配解中确定最优“折中”解，因此将高维多目标空间映射为以收敛性和多样性评价指标的2维空 间，再将上述2维空间根据性能指标的优劣划分为4个不同区域。同时，使用反向学习策略提高算法跳出局部 最优的能力。实验表明，MOPSO-OSM算法可以有效平衡收敛性和多样性之间的关系，达到求解复杂多日标优 化问题的目的。 关键词：目标空间映射策略；性能指标；反向学习；粒子群；高维多目标优化；Pareto准则；收敛性；分布性 中图分类号：TP18文献标志码：A 文章编号：1673-4785(2021)02-0362-09 中文引用格式：陈强，王宇嘉，梁海娜，等.目标空间映射策略的高维多目标粒子群优化算法.智能系统学报，2021,16(2)： 362-370. 英文引用格式：CHEN Qiang,VANG Yujia,.LIANG Haina,etal.M1ulti-objective particle swarm optimization algorithm based on an objective space papping strategy(J.CAAI transactions on intelligent systems,2021,16(2):362-370. Multi-objective particle swarm optimization algorithm based on an objective space papping strategy CHEN Qiang,WANG Yujia,LIANG Haina,SUN Xin (School of Electronic and Electrical Engineering,Shanghai University of Engineering Science,Shanghai 201620,China) Abstract:To balance the relationship between the convergence and diversity of the optimization algorithm in the multi- objective problem,the selection pressure of the algorithm is increased.A high-dimensional MOPSO-OSM(multi-object- ive particle swarm optimization algorithm based on objective space mapping strategy)is proposed in this paper.When solving high-dimensional multi-objective optimization problems,the Pareto based criterion cannot identify the best com- promise solutions from many nondominated solutions.Therefore,the high-dimensional multi-objective optimization space is mapped into two-dimensional space based on indexes of convergence and diversity.Then,the two-dimensional space is divided into four regions according to the performance index.Simultaneously,the ability of the jumping local optimal solution is improved using the opposition learning strategy.The experimental results show that MOPSO-OSM can balance the relationship between convergence and diversity and solve complex problems. Keywords:objective space mapping strategy;performance index,opposition learning;particle swarm optimization; high-dimensional multi-objective optimization:Pareto based criterion:convergence:diversity 在现实生活中存在大量多目标优化问题，例优化问题是由多个待优化目标函数组成，当目标 如生产制造业、金融投资、航空调度等。多目标 个数多于3个时，该问题又被称为高维多目标优 化间题(many-objective optimization problem)"。由 收稿日期：2020-06-24.网络出版日期：2020-11-10 基金项目：国家自然科学基金项目(61403249). 于各目标之间具有冲突性，传统的优化算法很难 通信作者：王宇嘉.E-mail:yjwangamber@(sues.edu.cm 得到一组最优解，因此，研究者大多采用启发式
DOI: 10.11992/tis.202006042 网络出版地址: https://kns.cnki.net/kcms/detail/23.1538.TP.20201110.0926.002.html 目标空间映射策略的高维多目标粒子群优化算法 陈强，王宇嘉，梁海娜，孙欣 （上海工程技术大学 电子电气工程学院，上海 201620） 摘 要：为了平衡优化算法在高维多目标优化问题中收敛性和多样性之间的关系，增加算法的选择压力，本文 提出了一种基于目标空间映射策略的高维多目标粒子群优化算法 (many-objective particle swarm optimization algorithm based on objective space mapping strategy，MOPSO-OSM)。在求解高维多目标优化问题时，Pareto 准则难以 从众多的非支配解中确定最优“折中”解，因此将高维多目标空间映射为以收敛性和多样性评价指标的 2 维空 间，再将上述 2 维空间根据性能指标的优劣划分为 4 个不同区域。同时，使用反向学习策略提高算法跳出局部 最优的能力。实验表明，MOPSO-OSM 算法可以有效平衡收敛性和多样性之间的关系，达到求解复杂多目标优 化问题的目的。 关键词：目标空间映射策略；性能指标；反向学习；粒子群；高维多目标优化；Pareto 准则；收敛性；分布性 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2021)02−0362−09 中文引用格式：陈强, 王宇嘉, 梁海娜, 等. 目标空间映射策略的高维多目标粒子群优化算法 [J]. 智能系统学报, 2021, 16(2): 362–370. 英文引用格式：CHEN Qiang, WANG Yujia, LIANG Haina, et al. Multi-objective particle swarm optimization algorithm based on an objective space papping strategy[J]. CAAI transactions on intelligent systems, 2021, 16(2): 362–370. Multi-objective particle swarm optimization algorithm based on an objective space papping strategy CHEN Qiang，WANG Yujia，LIANG Haina，SUN Xin (School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China) Abstract: To balance the relationship between the convergence and diversity of the optimization algorithm in the multiobjective problem, the selection pressure of the algorithm is increased. A high-dimensional MOPSO-OSM (multi-objective particle swarm optimization algorithm based on objective space mapping strategy) is proposed in this paper. When solving high-dimensional multi-objective optimization problems, the Pareto based criterion cannot identify the best compromise solutions from many nondominated solutions. Therefore, the high-dimensional multi-objective optimization space is mapped into two-dimensional space based on indexes of convergence and diversity. Then, the two-dimensional space is divided into four regions according to the performance index. Simultaneously, the ability of the jumping local optimal solution is improved using the opposition learning strategy. The experimental results show that MOPSO-OSM can balance the relationship between convergence and diversity and solve complex problems. Keywords: objective space mapping strategy; performance index; opposition learning; particle swarm optimization; high-dimensional multi-objective optimization; Pareto based criterion; convergence; diversity 在现实生活中存在大量多目标优化问题，例 如生产制造业、金融投资、航空调度等。多目标 优化问题是由多个待优化目标函数组成，当目标 个数多于 3 个时，该问题又被称为高维多目标优 化问题 (many-objective optimization problem)[1]。由 于各目标之间具有冲突性，传统的优化算法很难 得到一组最优解，因此，研究者大多采用启发式 收稿日期：2020−06−24. 网络出版日期：2020−11−10. 基金项目：国家自然科学基金项目 (61403249). 通信作者：王宇嘉. E-mail：yjwangamber@sues.edu.cn. 第 16 卷第 2 期 智 能 系 统 学 报 Vol.16 No.2 2021 年 3 月 CAAI Transactions on Intelligent Systems Mar. 2021
第2期 陈强，等：目标空间映射策略的高维多目标粒子群优化算法 ·363· 方法来求解该问题。目前，用于求解高维多目标 沿，因此，对解决高维多目标优化问题方面仍具 优化问题的启发式方法主要分为以下三类)：基 有巨大潜力。收敛性和分布性作为多目标优化 于支配关系的进化算法、基于分解的进化算法和 问题中的两个重要指标，在种群演化过程中是相 基于指标的进化算法。 互冲突的，因此设计一种能有效平衡收敛性和 基于支配关系的进化算法是通过Pareto支配 多样性的新型支配策略，对于解决高维多目标优 策略来选择非支配解。NSGA-I算法通过快速 化问题具有重要意义。本文提出了一种目标空 非支配解排序策略来获得非支配解，但是该方法 间映射策略的高维多目标粒子群优化算法，该策 无法保证种群的多样性。NSGA-Ⅲ作为NSGA- 略作为一种新的多样性保持机制，可从众多的候 Ⅱ的改进版本，为了增强算法处理高维多目标优 选解中筛选出收敛性和分布性都较优的个体，同 化问题的能力，在筛选同一等级的个体时，采用 时利用一种增强型反向学习策略帮助种群跳出 了基于参考点的方法来代替拥挤距离，然而该算 局部最优。 法仅在某些具有特定形状的Pareto前沿问题上表 现较优。CNSGA-III算法在NSGA-II的基础 1粒子群优化算法 上，通过在非支配解层中添加一个聚类操作来增 1.1基本粒子群优化算法 强算法种群的多样性，实验结果表明，该策略效 粒子群算法(particle swarm optimization. 果较差。Zou等在NSGA-Ⅱ框架基础上，提出 PSO)1是通过研究鸟群觅食规律而发展出的一 了一种在关键层中选取非支配解的旋转网格策 种群智能优化算法。粒子通过个体最优位置和群 略，在一定程度上增强了算法的选择压力。Lin 体最优位置动态更新自身的位置和速度，速度和 等提出了一种基于平衡适应度估计策略的高维 位置的更新公式分别为 粒子群算法来解决高维多目标优化问题，该策略 vid(t+1)=wVid(t)+cr(pid(t)-xid(t))+ 将目标空间划分为不同的区间并给每个区间中的 目标赋予不同的权重，然而过多的权重设置限制 c2r2(Psd(t)-xid(t)) (1) 了该方法的实际应用。 xid(t+1)=xid(f)+vid(t+1) (2) 基于分解的进化算法是通过将多目标问题转 式中：o表示权重系数；va和xa分别表示第i个 化为多个单目标问题来处理。MOEA/D8]和 粒子在第d维度上的速度和位置大小；c1和c2表 MOEA/D-M2M9是两种常用的基于分解的多目 示学习因子；r1和2表示(0,1)之间的随机数； 标进化算法。MOEA/DDI是通过目标空间分解 Pa和P如分别表示个体最优位置和群体最优位置。 与自适应权重分配相结合来解决高维多目标优化 1.2改进粒子群优化算法 问题。但上述算法过于依赖权重的选取。此外为 粒子群算法在其发展过程中，为了提高算法 了减少Pareto前沿形状对分解算法性能的影响， 的寻优性能，主要有以下几种改进策略。 Li山等山提出了一种基于模糊分解的多目标进化 1)调整算法的参数。为了平衡种群勘探与开 算法，结果表明该算法对于该问题具有较好的处 采的能力，Si等9将o引入粒子群算法中，o值 理效果。 越大，勘探未知区域的能力越强，ω值越小，小范 基于指标的进化算法是将解的评价标准作为 围内的开采能力越强，Clere等2o1建议o的取值 选择支配解的一类算法。IBEA2I采用Hyper-- 为0.729，Venter等2u则采用非线性递减的策略来 volume指标选取非支配解，该方法在处理高维多 更新0。此外还有部分研究者通过调整c1、c2的 目标问题时无法保证分布性。Bader等1提出了 取值来增强算法的搜索能力22)。 另一种基于Hypervolume指标的进化算法，在一 2)设计不同类型的拓扑结构。Kennedy通 定程度上平衡了高维多目标优化问题的收敛性和 过分析种群拓扑结构与交互概率的关系，提出了 分布性，但是Hypervolume指标的计算复杂度随 一种bare bones particle swarm(BBPS)的模型。 着目标个数的增加呈指数增加，进一步限制了 Yue等提出了一种基于环形拓扑结构的粒子群 该算法应用。此外，基于GD、IGD和R21指 算法并将其用于求解多模态的多目标问题。 标的进化算法在求解高维多目标优化问题时都取 3)与其他策略相结合，形成混合粒子群算 得了不错的效果。 法。侯翔等为了提高算法求解问题的能力，对 基于Pareto支配策略的进化算法相对于另外 所有粒子的最优位置进行降维处理，形成一个参 两类算法，可以从搜索的深度上逼近Pareto前 考全局最优解，同时使用该解来更新群体当前的
方法来求解该问题。目前，用于求解高维多目标 优化问题的启发式方法主要分为以下三类[2] ：基 于支配关系的进化算法、基于分解的进化算法和 基于指标的进化算法。 基于支配关系的进化算法是通过 Pareto 支配 策略来选择非支配解。NSGA-II[3] 算法通过快速 非支配解排序策略来获得非支配解，但是该方法 无法保证种群的多样性。NSGA-III[4] 作为 NSGAII 的改进版本，为了增强算法处理高维多目标优 化问题的能力，在筛选同一等级的个体时，采用 了基于参考点的方法来代替拥挤距离，然而该算 法仅在某些具有特定形状的 Pareto 前沿问题上表 现较优。CNSGA-III[5] 算法在 NSGA-III 的基础 上，通过在非支配解层中添加一个聚类操作来增 强算法种群的多样性，实验结果表明，该策略效 果较差。Zou 等 [6] 在 NSGA-II 框架基础上，提出 了一种在关键层中选取非支配解的旋转网格策 略，在一定程度上增强了算法的选择压力。Lin 等 [7] 提出了一种基于平衡适应度估计策略的高维 粒子群算法来解决高维多目标优化问题，该策略 将目标空间划分为不同的区间并给每个区间中的 目标赋予不同的权重，然而过多的权重设置限制 了该方法的实际应用。 基于分解的进化算法是通过将多目标问题转 化为多个单目标问题来处理。MOEA/D[ 8 ] 和 MOEA/D-M2M[9] 是两种常用的基于分解的多目 标进化算法。MOEA/DD[10] 是通过目标空间分解 与自适应权重分配相结合来解决高维多目标优化 问题。但上述算法过于依赖权重的选取。此外为 了减少 Pareto 前沿形状对分解算法性能的影响， Liu 等 [11] 提出了一种基于模糊分解的多目标进化 算法，结果表明该算法对于该问题具有较好的处 理效果。 基于指标的进化算法是将解的评价标准作为 选择支配解的一类算法。IBEA[12] 采用 Hypervolume 指标选取非支配解，该方法在处理高维多 目标问题时无法保证分布性。Bader 等 [13] 提出了 另一种基于 Hypervolume 指标的进化算法，在一 定程度上平衡了高维多目标优化问题的收敛性和 分布性，但是 Hypervolume 指标的计算复杂度随 着目标个数的增加呈指数增加[2] ，进一步限制了 该算法应用。此外，基于 GD[14] 、IGD[15] 和 R2[16] 指 标的进化算法在求解高维多目标优化问题时都取 得了不错的效果。 基于 Pareto 支配策略的进化算法相对于另外 两类算法，可以从搜索的深度上逼近 Pareto 前 沿，因此，对解决高维多目标优化问题方面仍具 有巨大潜力。收敛性和分布性作为多目标优化 问题中的两个重要指标，在种群演化过程中是相 互冲突的[17] ，因此设计一种能有效平衡收敛性和 多样性的新型支配策略，对于解决高维多目标优 化问题具有重要意义。本文提出了一种目标空 间映射策略的高维多目标粒子群优化算法，该策 略作为一种新的多样性保持机制，可从众多的候 选解中筛选出收敛性和分布性都较优的个体，同 时利用一种增强型反向学习策略帮助种群跳出 局部最优。 1 粒子群优化算法 1.1 基本粒子群优化算法 粒子群算法 (particle swarm optimization, PSO)[18] 是通过研究鸟群觅食规律而发展出的一 种群智能优化算法。粒子通过个体最优位置和群 体最优位置动态更新自身的位置和速度，速度和 位置的更新公式分别为 vid(t+1) =ωvid(t)+c1r1(pid(t)− xid(t))+ c2r2(pgd(t)− xid(t)) (1) xid(t+1) = xid(t)+vid(t+1) (2) 式中：ω 表示权重系数；vid 和 xid 分别表示第 i 个 粒子在第 d 维度上的速度和位置大小；c1 和 c2 表 示学习因子；r1 和 r2 表示 (0，1) 之间的随机数； pid 和 pgd 分别表示个体最优位置和群体最优位置。 1.2 改进粒子群优化算法 粒子群算法在其发展过程中，为了提高算法 的寻优性能，主要有以下几种改进策略。 1) 调整算法的参数。为了平衡种群勘探与开 采的能力，Shi 等 [19] 将 ω 引入粒子群算法中，ω 值 越大，勘探未知区域的能力越强，ω 值越小，小范 围内的开采能力越强，Clerc 等 [20] 建议 ω 的取值 为 0.729，Venter 等 [21] 则采用非线性递减的策略来 更新 ω。此外还有部分研究者通过调整 c1、c2 的 取值来增强算法的搜索能力[22-23]。 2) 设计不同类型的拓扑结构。Kennedy[24] 通 过分析种群拓扑结构与交互概率的关系，提出了 一种 bare bones particle swarm (BBPS) 的模型。 Yue 等 [25] 提出了一种基于环形拓扑结构的粒子群 算法并将其用于求解多模态的多目标问题。 3) 与其他策略相结合，形成混合粒子群算 法。侯翔等[26] 为了提高算法求解问题的能力，对 所有粒子的最优位置进行降维处理，形成一个参 考全局最优解，同时使用该解来更新群体当前的 第 2 期 陈强，等：目标空间映射策略的高维多目标粒子群优化算法 ·363·
·364· 智能系统学报 第16卷 最优位置。Lin等2将MOPSO同分解算法相结 合，采用两种不同的搜索策略来更新粒子的速 偏 度，结果显示，算法对复杂问题的解决性能得到 Disave= (7 n 了加强。Zain等2]为了降低算法在约束问题上 其中n表示个体的总数。 求解的难度，在标准MOPSO29算法的基础上提 根据F、Dis、Fave、Disave这4个参数将映射 出了一种基于动态搜索边界策略的MOPSO。 后的2维空间划分为4个不同的区域，如图1 2目标空间映射策略的高维多目标 所示。 粒子群算法 F 2.1高维多目标优化问题 max(F) 最小化高维多目标优化问题可以表示为 D minY(x)={fi(x),f(x),…,fm(x)》 F (3) subject tox∈D 7 B 式中：D表示决策空间，x=(x1,x2,…,xn)；Y: min(F) D→R"由m个目标函数，…fm组成，R"表示目 标空间；m≥4表示为目标函数的个数。通过式 (0,0) min(1/Dis)Dis max(1/Dis,)1/Dis (3)得到一组最优解，即Pareto解集，表示为PS, 图1映射后的2维空间划分结果 如果PF=(Y(x)∈Rmx∈PSl,称PF为Pareto前沿。 Fig.1 2-dimensinal space division result after mapping 2.2目标空间映射策略 设个体i对应的目标函数值为Y,此时其映射 由于非支配解个数增加导致算法无法收敛到 到2维空间后存在以下4种情况： 完整的Pareto前沿，本文采用目标空间映射策略 来增强算法对非支配解的选择压力。 4:(IEE Dis. ≤DiSe,Y:∈A,处于A区 首先，对每个个体在目标空间中的收敛性进 域的个体，其收敛性和分布性均是最优。 行评价，采用式(4)计算个体的收敛性： B:WIFFDis,≤Die,YeA,处于C区 考点0之间的欧式距离，这里将参考点设置为原 域的个体，其收敛性较差，分布性较好。 1 点。F,的值越小，个体的收敛性越好。 D:(YAF>F Dis >Dise,Y,∈A,处于D区 然后，对每个个体在目标空间上的分布性进 域的个体，其收敛性和分布性都较差。 行评价，采用式（⑤）计算个体的分布性： 在不同区域内的非支配解质量从好到坏的顺 f(x)-f-(x) 序为：A>B=C>D。 max(f,(x))-min(f(x)) 为进一步评价同区域内或并列区域内个体的 Disi= i=1,2,…,n 优劣，采用式(8)计算个体的序值。 (5) (1 式中：表示第+1个个体在第s个目标函数上 Valuei=a +8F Disi (8) 的目标值；Dis,越大，则第i个个体的分布越好。 式中：a和B分别为分布性权重和收敛性权重。 此时，每个非劣解都可以映射为以收敛性和 Value,越小，个体排序越好。对于处在区域A或 分布性表征的2维空间，即PS→(F,Dis,)。 D中的个体，设置a==1,保证A和D区域中的个 最后，计算收敛性评价的平均值Fae和分布 体信息不变。对于处在B和C中的个体，其收敛 性评价的平均值DiSave,Fave和Disave如式(6)和 性和分布性互不支配，假设B区域中个体数量为 (7)所示： k,当个体处在B区域时，参数设置如下：=1，α= Dis,i=1,2,…,k Dis: 1 (6) n 通过该设置，B区域中个体收敛信息保持不变，分
最优位置。Lin 等 [27] 将 MOPSO 同分解算法相结 合，采用两种不同的搜索策略来更新粒子的速 度，结果显示，算法对复杂问题的解决性能得到 了加强。Zain 等 [28] 为了降低算法在约束问题上 求解的难度，在标准 MOPSO[29] 算法的基础上提 出了一种基于动态搜索边界策略的 MOPSO。 2 目标空间映射策略的高维多目标 粒子群算法 2.1 高维多目标优化问题 最小化高维多目标优化问题可以表示为 minY(x) = {f1(x), f2(x), ··· , fm(x)} subject to x ∈ D (3) PF = {Y(x) ∈ R m |x ∈ PS} 式中： D 表示决策空间， x = ( x 1 , x 2 ,… , x n ) ； Y : D→R m 由 m 个目标函数 f1 ,f2 ,…fm 组成，R m 表示目 标空间；m≥4 表示为目标函数的个数。通过式 (3) 得到一组最优解，即 Pareto 解集，表示为 PS， 如果 ，称 PF 为 Pareto 前沿。 2.2 目标空间映射策略 由于非支配解个数增加导致算法无法收敛到 完整的 Pareto 前沿，本文采用目标空间映射策略 来增强算法对非支配解的选择压力。 首先，对每个个体在目标空间中的收敛性进 行评价，采用式 (4) 计算个体的收敛性： Fi = di,o √ m , i = 1,2,··· ,n (4) 式中：m 表示目标函数的个数；di,o 表示个体 i 到参 考点 o 之间的欧式距离，这里将参考点设置为原 点。Fi 的值越小，个体的收敛性越好。 然后，对每个个体在目标空间上的分布性进 行评价，采用式 (5) 计算个体的分布性： Disi = (∑m s=1 f i+1 s (x)− f i−1 s (x) max(fs(x))−min(fs(x))) m , i = 1,2,··· ,n (5) 式中：fs i+1 表示第 i+1 个个体在第 s 个目标函数上 的目标值；Disi 越大，则第 i 个个体的分布越好。 PS → (Fi , Disi) 此时，每个非劣解都可以映射为以收敛性和 分布性表征的 2 维空间，即 。 最后，计算收敛性评价的平均值 Fave 和分布 性评价的平均值 Disave，Fave 和 Disave 如式 (6) 和 (7) 所示： Fave = ∑n i=1 Fi n (6) Disave = ∑n i=1 ( 1 Disi ) n (7) 其中 n 表示个体的总数。 根据 Fi、Disi、Fave、Disave 这 4 个参数将映射 后的 2 维空间划分为 4 个不同的区域，如图 1 所示。 C A B D (0,0) max(Fi ) Fave min(Fi ) F max(1/Disi Dis ) min(1/Disi ave ) 1/Dis 图 1 映射后的 2 维空间划分结果 Fig. 1 2-dimensinal space division result after mapping 设个体 i 对应的目标函数值为 Yi，此时其映射 到 2 维空间后存在以下 4 种情况： {Yi |Fi ⩽ Fave ∩ 1 Disi ⩽ Disave A： , Yi ∈ A} ，处于 A 区 域的个体，其收敛性和分布性均是最优。 {Yi |Fi ⩽ Fave ∩ 1 Disi > Disave B： , Yi ∈ A} ，处于 B 区 域的个体，其收敛性较好，分布性较差。 {Yi |Fi > Fave ∩ 1 Disi ⩽ Disave C： , Yi ∈ A} ，处于 C 区 域的个体，其收敛性较差，分布性较好。 {Yi |Fi > Fave ∩ 1 Disi > Disave D： , Yi ∈ A} ，处于 D 区 域的个体，其收敛性和分布性都较差。 A > B = C > D 在不同区域内的非支配解质量从好到坏的顺 序为： 。 为进一步评价同区域内或并列区域内个体的 优劣，采用式 (8) 计算个体的序值。 Valuei = α ( 1 Disi ) +βFi (8) α = ( min( 1 Disi ) +rand( Disave −min( 1 Disi )))Disi ,i = 1,2,··· , k 式中：α 和 β 分别为分布性权重和收敛性权重。 Valuei 越小，个体排序越好。对于处在区域 A 或 D 中的个体，设置 α=β=1，保证 A 和 D 区域中的个 体信息不变。对于处在 B 和 C 中的个体，其收敛 性和分布性互不支配，假设 B 区域中个体数量为 k，当个体处在 B 区域时，参数设置如下：β=1， ， 通过该设置，B 区域中个体收敛信息保持不变，分 ·364· 智 能 系 统 学 报 第 16 卷
第2期 陈强，等：目标空间映射策略的高维多目标粒子群优化算法 ·365· 布信息被缩放到(min(1/Dis),Dise),i=1,2,…,k区 bu,k(au+ba)-a,当k=l时，xa取得最大值为bao 间内。当个体处于C区域时，假设C区域中个体 因此，当最优解的决策向量位于b的右侧时，上 数量为q,参数设置如下：B=(min(F)+rand(Fe 述方法不能跳出局部最优。 min(F》万，i=l,2,9,a=l,该设置将区域C中个 本文对上述方法进行了改进，为提高算法跳 体的收敛信息缩放到(min(F),Fwe),i=l,2,…q区 出局部最优的能力，同时不忽略当前收敛信息， 间内，而分布信息保持不变。通过上述操作，处 当x=x4m时，xa执行式(10)给出的反向学习 于区域B和C中的个体，其分布信息和收敛信息 策略。 都被缩放到相同的区间之中，因此两区域中的个 Xid=Xdmin+dmax -Xid (10) 体可以被放在一起统一评价。 从式(10)可以看出，x的取值范围扩大到了 在选取非支配解时，首先选取区域A中的个 [min,nax小，该粒子跳出局部最优区域。 体，当区域A中的个体个数大于外部文档大小 为了判断算法是否陷入局部最优，本文采用 时，选取Value,值小的个体进入档案文件；当区 文献[3]给出的判断准则作为反向学习的激发条 域A中的个体个数小于外部文档大小时，再从 件，如式(11)所示： B和C中选取剩余个体，当B和C中的个体个数 大于剩余外部文档大小时，仍然选取Value,值小 Imin(f)-min(f10) 10 的个体进人外部文档。当B和C中的个体个数 Imin(f (11) 不能满足条件时，最后选取D中的个体。 Imax(f)-max(f10 10 图2给出了目标空间映射策略的流程图。 Imax( 式中：min(f)和max(f)分别表示在第t代时，第 开始 i个目标维度上的最小和最大值。min(f-1)和 max(广0)分别表示在第1-l0代时，第i个目标维 根据min(F)、max(F)、min(Dis、max(Dis) F 和Dise,将候选解分成4个不同的区域 度上的最小和最大值。对于一个m维测试函数， 通过式(11)对其所有的目标维度的变化率进行计 计算4个不同的区域中所有个体的 算，当所有的变化率都小于0.005时，算法陷入局 Value,值 部最优。 2.4 MOPSO-OSM流程 根据Value,值大小，选取候 选解，存入外部档案 MOPSO-OSM算法具体流程如下： 1)算法初始化： 结束 2)判断是否满足停止条件，若条件满足，算 法停止迭代，否则转到3)： 图2目标映射策略的流程图 3)判断种群是否陷入局部最优，执行反向学 Fig.2 Flowchart of the objective space mapping strategy 习策略；否则，直接转到4)： 2.3反向学习策略 4)利用式(1)和(2)更新个体的速度和位置： 优化过程中如果算法陷入局部最优，则利用 5)计算个体的适应度值： 反向学习策略作为跳出机制，其中文献30]的反 6)对个体当前适应度值和前代适应度值进行 向学习策略如式(9)所示： 比较来更新个体最优， x=k(min(x)+max(xd))-xid 7)选择非支配解； xid k(aa+ba)-xid (9) 8)利用目标空间映射策略更新外部档案文件； x rand(ad,ba),if xixdmas 9)从外部档案中随机选择一个个体来更新种 式中：xa表示第i个个体在第d维决策向量上得 群最优，并转到2)； 到的新位置；xa表示所有个体在第d维上的位置； 3实验结果与分析 aa和b.分别表示种群个体在第d维目标向量上 的最小和最大边界值；k表示(0,1)间的随机数； 31测试函数 [xim,xhaJ表示在第d维上的边界约束。 为了评价算法性能的优劣，文中采取了6组 由式(9)可得，xa的取值范围为[k(au+b)- WFG测试函数。参数设置如表1所示
(min(1/Disi),Disave),i = 1,2,··· , k β = (min(Fi)+rand(Fave− min(Fi))) 1 Fi ,i = 1,2,···q (min(Fi),Fave),i = 1,2,···q 布信息被缩放到 区 间内。当个体处于 C 区域时，假设 C 区域中个体 数量为 q,参数设置如下： ，α=1，该设置将区域 C 中个 体的收敛信息缩放到 区 间内，而分布信息保持不变。通过上述操作，处 于区域 B 和 C 中的个体，其分布信息和收敛信息 都被缩放到相同的区间之中，因此两区域中的个 体可以被放在一起统一评价。 在选取非支配解时，首先选取区域 A 中的个 体，当区域 A 中的个体个数大于外部文档大小 时，选取 Valuei 值小的个体进入档案文件；当区 域 A 中的个体个数小于外部文档大小时，再从 B 和 C 中选取剩余个体，当 B 和 C 中的个体个数 大于剩余外部文档大小时，仍然选取 Valuei 值小 的个体进入外部文档。当 B 和 C 中的个体个数 不能满足条件时，最后选取 D 中的个体。 图 2 给出了目标空间映射策略的流程图。 开始 根据 min(Fi )、max(Fi )、min(Disi )、max(Disi )、Fave 和 Disave ，将候选解分成 4 个不同的区域 计算 4 个不同的区域中所有个体的 Valuei 值 根据 Valuei 值大小，选取候 选解，存入外部档案 结束 图 2 目标映射策略的流程图 Fig. 2 Flowchart of the objective space mapping strategy 2.3 反向学习策略 优化过程中如果算法陷入局部最优，则利用 反向学习策略作为跳出机制，其中文献 [30] 的反 向学习策略如式 (9) 所示： x ∗ id = k(min(xd)+max(xd))− xid x ∗ id = k(ad +bd)− xid x ∗ id = rand(ad, bd), if x ∗ id xdmax (9) 式中：xid *表示第 i 个个体在第 d 维决策向量上得 到的新位置；xd 表示所有个体在第 d 维上的位置； ad 和 bd 分别表示种群个体在第 d 维目标向量上 的最小和最大边界值；k 表示 (0，1) 间的随机数； [xdmin, xdmax] 表示在第 d 维上的边界约束。 x ∗ id 由式 (9) 可得， 的取值范围为 [k(ad +bd)− bd, k(ad +bd)−ad] x ∗ ，当 k=1 时 ， id取得最大值为 bd。 因此，当最优解的决策向量位于 bd 的右侧时，上 述方法不能跳出局部最优。 x ∗ id = xdmin 本文对上述方法进行了改进，为提高算法跳 出局部最优的能力，同时不忽略当前收敛信息， 当 时 ， xi d 执行式 (10) 给出的反向学习 策略。 x ∗ id = xdmin + xdmax − xid (10) x ∗ 从式 id (10) 可以看出， 的取值范围扩大到了 [xdmin, xdmax]，该粒子跳出局部最优区域。 为了判断算法是否陷入局部最优，本文采用 文献 [31] 给出的判断准则作为反向学习的激发条 件，如式 (11) 所示： |min(f t i )−min(f t−10 i )| |min(f t i )| 10 |max(f t i )−max(f t−10 i )| |max(f t i )| 10 (11) t m 式中：min(fi t ) 和 max(fi t ) 分别表示在第 代时，第 i 个目标维度上的最小和最大值。min(fi t−10) 和 max(fi t−10) 分别表示在第 t−10 代时，第 i 个目标维 度上的最小和最大值。对于一个 维测试函数， 通过式 (11) 对其所有的目标维度的变化率进行计 算，当所有的变化率都小于 0.005 时，算法陷入局 部最优。 2.4 MOPSO-OSM 流程 MOPSO-OSM 算法具体流程如下： 1) 算法初始化； 2) 判断是否满足停止条件，若条件满足，算 法停止迭代，否则转到 3)； 3) 判断种群是否陷入局部最优，执行反向学 习策略；否则，直接转到 4)； 4) 利用式 (1) 和 (2) 更新个体的速度和位置； 5) 计算个体的适应度值； 6) 对个体当前适应度值和前代适应度值进行 比较来更新个体最优; 7) 选择非支配解； 8) 利用目标空间映射策略更新外部档案文件； 9) 从外部档案中随机选择一个个体来更新种 群最优，并转到 2)； 3 实验结果与分析 3.1 测试函数 为了评价算法性能的优劣，文中采取了 6 组 WFG 测试函数。参数设置如表 1 所示。 第 2 期 陈强，等：目标空间映射策略的高维多目标粒子群优化算法 ·365·
·366· 智能系统学报 第16卷 表1测试函数参数设置 数设置如表2所示，所有算法均运行30次，计算 Table 1 Test functions parameter setting 收敛性和多样性指标，取其平均值。 测试函数 目标个数 决策变量个数 特征 表2对比算法参数设置 5 14 Table 2 Comparison algorithms parameter setting WFGI 混合 10 19 对比算法 参数设置 5 14 MOEA/DDT=20,Pm=1/n,7=7m=20,6=0.9,n,=2 WFG2 凸面，不连续 10 19 NSGA-III Pe=1,Pm=1/n,7e=7m=20 5 14 PESA-II Pe=1,Pm=1/n,7e=7m=20,dim=10 WFG3 线性，退化 10 19 RVEA Pe=1,Pm=1/n,1e=1m=20,a=2,f=0.1 14 凹面，多模 NMPSO Pm=1/n,7m=20,u∈[0.1,0.5]， WFG4 c1,c2,c3∈[1.5,2.5 10 19 MOPSO- w∈[0.4,0.91，c1=c2=2 5 14 OSM WFG5 凹面，欺骗性 10 19 对于MOPSO-OSM算法，其权重w是随着迭 5 14 WFG6 凹面，不可分 代次数线性减少的。 10 o 3.4结果与分析 3.2性能指标 表3和表4分别为所有算法在5目标和10目 文中利用世代距离(GD)、间距(SP)和逆世代 标测试函数时得到的GD、SP和IGD的平均值。 距离(IGD)3个指标来评估算法的性能。GD被用 3.4.1收敛性分析 来评价种群的收敛性，GD值越小，收敛性越好， 从表3中可以看出，对于5目标测试函数， 其计算公式为 NMPSO算法在WFG1和WFG2测试函数中得到 了最好的GD值。NSGA-III算法在WFG4和 WFG6问题中取得了最佳的GD值。MOPSO GD= (12) OSM算法在WFG3和WFG5取得了最优的GD n 式中：n表示非支配解的个数；d,表示非支配解与 值。对于10目标的测试函数，从表4中可以看 Pareto最优解之间的欧式距离。 出，在WFG1和WFG2测试函数上，MOEA/DD取 SP指标通常被用来评价种群的分布性，其计 得了最佳GD值。NSGA-IⅢI在WFG6问题上取得 算如式(13)所示，分布性好坏与其计算值成反比。 最优GD值，在WFG4和WFG5测试问题上，RVEA 取得的GD值排名第一。对于WFG3测试函数， 1 SP= (d-di) (13) n-1 MOPSO-OSM取得了最优的GD值。从以上可以 i=l 看出，本文所提出的算法在大部分测试函数中并 式中d为d,的平均值。 没有取得最优值。原因在于，大多数算法在求解 IGD指标被用来同时评价种群分布性和收敛 时，仅仅追求收敛性，忽视了分布性，而本文在目 性，IGD越小，算法展现出的性能越好，其计算公 标空间分配策略中，同时考虑目标向量的收敛性 式为 和分布性，所以在测试函数中，并不能完全保证 Sd(x'.P) GD的最优性，这也验证了“没有免费午餐”的 IGD= 'Ep. (14) 原理。 式中：P和P分别表示Pareto最优解集和非支配 3.4.2分布性分析 解；P表示非支配个数。 对于5目标测试函数，从表3中可以看出， 3.3对比算法及其设置 MOPSO-OSM算法在所有测试函数中都取得了最 本文所得结果与目前较为流行的进化算法进 好的SP值。对于10目标的测试函数，从表4可 行对比，比较算法包括：NSGA-II)、RVEAI2 以看出，MOPSO-OSM算法同样在所有的测试函 MOEA/DDI0、PESA-I)和NMPSO。所有使用 数中，得到了最好的SP值。以上可以看出，MOP- 的算法其种群大小都设置为100，外部文档的大 SO-OSM算法在保持种群分布性上面具有很大的 小为100，算法进化的次数为700次，算法具体参 优势
表 1 测试函数参数设置 Table 1 Test functions parameter setting 测试函数 目标个数 决策变量个数 特征 WFG1 5 14 混合 10 19 WFG2 5 14 凸面，不连续 10 19 WFG3 5 14 线性，退化 10 19 WFG4 5 14 凹面，多模 10 19 WFG5 5 14 凹面，欺骗性 10 19 WFG6 5 14 凹面，不可分 10 19 3.2 性能指标 文中利用世代距离 (GD)、间距 (SP) 和逆世代 距离 (IGD)3 个指标来评估算法的性能。GD 被用 来评价种群的收敛性，GD 值越小，收敛性越好， 其计算公式为 GD = √∑n i=1 d 2 i n (12) 式中：n 表示非支配解的个数；di 表示非支配解与 Pareto 最优解之间的欧式距离。 SP 指标通常被用来评价种群的分布性，其计 算如式 (13) 所示，分布性好坏与其计算值成反比。 S P = vt 1 n−1 ∑n i=1 (d −di) 2 (13) 式中 d 为 di 的平均值。 IGD 指标被用来同时评价种群分布性和收敛 性，IGD 越小，算法展现出的性能越好，其计算公 式为 IGD = ∑ x ∗∈P∗ d(x ∗ , P) |P∗ | (14) 式中：P 和 P *分别表示 Pareto 最优解集和非支配 解；|P * |表示非支配个数。 3.3 对比算法及其设置 本文所得结果与目前较为流行的进化算法进 行对比，比较算法包括：NSGA-III[3] 、RVEA[32] 、 MOEA/DD[10] 、PESA-II[33] 和 NMPSO[7]。所有使用 的算法其种群大小都设置为 100，外部文档的大 小为 100，算法进化的次数为 700 次，算法具体参 数设置如表 2 所示，所有算法均运行 30 次，计算 收敛性和多样性指标，取其平均值。 表 2 对比算法参数设置 Table 2 Comparison algorithms parameter setting 对比算法 参数设置 MOEA/DD T = 20, pm = 1/n,ηc = ηm = 20,δ = 0.9,nr = 2 NSGA-III pc = 1, pm = 1/n,ηc = ηm = 20 PESA-II pc = 1, pm = 1/n,ηc = ηm = 20,div = 10 RVEA pc = 1, pm = 1/n,ηc = ηm = 20,α = 2, fr = 0.1 NMPSO pm = 1/n,ηm = 20,ω ∈ [0.1,0.5], c1, c2, c3 ∈ [1.5,2.5] MOPSOOSM ω ∈ [0.4,0.9], c1 = c2 = 2 对于 MOPSO-OSM 算法，其权重 ω 是随着迭 代次数线性减少的。 3.4 结果与分析 表 3 和表 4 分别为所有算法在 5 目标和 10 目 标测试函数时得到的 GD、SP 和 IGD 的平均值。 3.4.1 收敛性分析 从表 3 中可以看出，对于 5 目标测试函数， NMPSO 算法在 WFG1 和 WFG2 测试函数中得到 了最好的 GD 值。NSGA-III 算法在 WFG4 和 WFG6 问题中取得了最佳的 GD 值。MOPSOOSM 算法在 WFG3 和 WFG5 取得了最优的 GD 值。对于 10 目标的测试函数，从表 4 中可以看 出，在 WFG1 和 WFG2 测试函数上，MOEA/DD 取 得了最佳 GD 值。NSGA-III 在 WFG6 问题上取得 最优 GD 值，在 WFG4 和 WFG5 测试问题上，RVEA 取得的 GD 值排名第一。对于 WFG3 测试函数， MOPSO-OSM 取得了最优的 GD 值。从以上可以 看出，本文所提出的算法在大部分测试函数中并 没有取得最优值。原因在于，大多数算法在求解 时，仅仅追求收敛性，忽视了分布性，而本文在目 标空间分配策略中，同时考虑目标向量的收敛性 和分布性，所以在测试函数中，并不能完全保证 GD 的最优性，这也验证了“没有免费午餐”的 原理。 3.4.2 分布性分析 对于 5 目标测试函数，从表 3 中可以看出， MOPSO-OSM 算法在所有测试函数中都取得了最 好的 SP 值。对于 10 目标的测试函数，从表 4 可 以看出，MOPSO-OSM 算法同样在所有的测试函 数中，得到了最好的 SP 值。以上可以看出，MOPSO-OSM 算法在保持种群分布性上面具有很大的 优势。 ·366· 智 能 系 统 学 报 第 16 卷
第2期 陈强，等：目标空间映射策略的高维多目标粒子群优化算法 ·367· 表35目标测试函数结果 Table 3 Results of five objectives 指标 测试函数 MOEA/DD NSGA-III PESA-II NMPSO RVEA MOPSO-OSM WFG1 0.04984 0.19206 0.18898 0.01992 0.18608 0.20270 WFG2 0.01358 0.06836 0.07510 0.01320 0.06448 0.05050 WFG3 0.32144 0.34488 0.20176 0.20410 0.37742 0.11732 GD WFG4 0.02768 0.02672 0.05006 0.02846 0.02794 0.03019 WFG5 0.02999 0.02689 0.04964 0.03432 0.02784 0.02593 WFG6 0.09136 0.02888 0.05910 0.04678 0.02894 0.03161 WFGI 1.00448 0.95402 0.19230 0.99390 1.01732 0.08098 WFG2 0.23828 0.73602 0.40762 0.33622 0.44774 0.06688 WFG3 1.23142 0.65198 0.26022 0.33496 0.71832 0.03414 SP WFG4 1.29576 0.77864 0.71048 0.59866 0.77182 0.05002 WFG5 1.30608 0.78214 0.77862 0.62052 0.78174 0.03886 WFG6 1.31684 0.77552 0.71720 0.62230 0.77496 0.03486 WFGI 0.75932 0.36725 0.62010 1.07638 0.50514 1.03702 WFG2 0.58156 0.82472 1.31474 1.12398 1.69076 0.72006 WFG3 0.93126 0.58938 2.46510 0.27382 0.73102 0.23022 IGD WFG4 1.40754 1.22568 1.84264 1.35102 1.22696 1.21534 WFG5 1.36282 1.21506 1.68982 1.27144 1.21624 1.48324 WFG6 1.38604 1.21618 1.82376 1.37084 1.22962 1.52218 表410目标测试函数结果 Table 4 Results of ten objectives 指标 测试函数 MOEA/DD NSGA-III PESA-II NMPSO RVEA MOPSO-OSM WFG1 0.06420 0.15132 0.31560 0.08642 0.07708 0.30676 WFG2 0.04110 0.43892 0.44686 0.07156 0.36180 0.28320 WFG3 1.07210 1.06524 0.39308 0.55684 1.03702 0.23066 GD WFG4 0.16558 0.11392 0.26058 0.18156 0.08268 0.20588 WFG5 0.16702 0.15618 0.28498 0.19170 0.05946 0.15036 WFG6 0.17470 0.12748 0.33294 0.14976 0.15380 0.16514 WFGI 2.95264 1.30466 1.62318 2.02932 3.61214 0.18142 WFG2 0.30970 1.40874 0.62674 0.81350 0.61172 0.06872 WFG3 3.56180 1.88106 0.53530 1.26638 1.58130 0.07624 SP WFG4 1.84452 3.67630 2.38228 2.95460 2.54844 0.14796 WFG5 2.82260 0.15618 2.76873 2.77874 2.71242 0.11114 WFG6 2.34698 2.39474 1.71234 2.42856 2.02336 0.13582 WFGI 1.53140 2.07474 3.35378 4.07131 1.69012 3.21088 WFG2 1.58062 7.08492 4.72854 2.1176 8.83920 3.64001 WFG3 3.42218 3.73876 6.42206 0.98680 4.81142 0.70094 IGD WFG4 7.86398 6.12948 6.25024 5.08556 5.89066 5.42432 WFG5 7.59892 5.89746 7.13126 5.10664 5.81356 5.64624 WFG6 7.68106 7.19022 9.46646 5.45448 6.20472 5.29934 3.4.3整体性分析 NSGA-III在WFG1、WFG5和WFG6中取得了最 从表3中可以看出，对于5目标测试函数， 优的IGD值。MOEA/DD在WFG2中取得最好的
3.4.3 整体性分析 从表 3 中可以看出，对于 5 目标测试函数， NSGA-III 在 WFG1、WFG5 和 WFG6 中取得了最 优的 IGD 值。MOEA/DD 在 WFG2 中取得最好的 表 3 5 目标测试函数结果 Table 3 Results of five objectives 指标 测试函数 MOEA/DD NSGA-III PESA-II NMPSO RVEA MOPSO-OSM GD WFG1 0.049 84 0.192 06 0.188 98 0.01992 0.186 08 0.20270 WFG2 0.013 58 0.068 36 0.075 10 0.01320 0.064 48 0.05050 WFG3 0.321 44 0.344 88 0.201 76 0.20410 0.377 42 0.11732 WFG4 0.027 68 0.026 72 0.050 06 0.02846 0.027 94 0.03019 WFG5 0.029 99 0.026 89 0.049 64 0.03432 0.027 84 0.02593 WFG6 0.091 36 0.028 88 0.059 10 0.04678 0.028 94 0.03161 SP WFG1 1.004 48 0.954 02 0.192 30 0.99390 1.017 32 0.08098 WFG2 0.238 28 0.736 02 0.407 62 0.33622 0.447 74 0.06688 WFG3 1.231 42 0.651 98 0.260 22 0.33496 0.718 32 0.03414 WFG4 1.295 76 0.778 64 0.710 48 0.59866 0.771 82 0.05002 WFG5 1.306 08 0.782 14 0.778 62 0.62052 0.781 74 0.03886 WFG6 1.316 84 0.775 52 0.717 20 0.62230 0.774 96 0.03486 IGD WFG1 0.759 32 0.367 25 0.620 10 1.07638 0.505 14 1.03702 WFG2 0.581 56 0.824 72 1.314 74 1.12398 1.690 76 0.72006 WFG3 0.931 26 0.589 38 2.465 10 0.27382 0.731 02 0.23022 WFG4 1.407 54 1.225 68 1.842 64 1.35102 1.226 96 1.21534 WFG5 1.362 82 1.215 06 1.689 82 1.27144 1.216 24 1.48324 WFG6 1.386 04 1.216 18 1.823 76 1.37084 1.229 62 1.52218 表 4 10 目标测试函数结果 Table 4 Results of ten objectives 指标 测试函数 MOEA/DD NSGA-III PESA-II NMPSO RVEA MOPSO-OSM GD WFG1 0.064 20 0.151 32 0.315 60 0.08642 0.077 08 0.30676 WFG2 0.041 10 0.438 92 0.446 86 0.07156 0.361 80 0.28320 WFG3 1.072 10 1.065 24 0.393 08 0.55684 1.037 02 0.23066 WFG4 0.165 58 0.113 92 0.260 58 0.18156 0.082 68 0.20588 WFG5 0.167 02 0.156 18 0.284 98 0.19170 0.059 46 0.15036 WFG6 0.174 70 0.127 48 0.332 94 0.14976 0.153 80 0.16514 SP WFG1 2.952 64 1.304 66 1.623 18 2.02932 3.612 14 0.18142 WFG2 0.309 70 1.408 74 0.626 74 0.81350 0.611 72 0.06872 WFG3 3.561 80 1.881 06 0.535 30 1.26638 1.581 30 0.07624 WFG4 1.844 52 3.676 30 2.382 28 2.95460 2.548 44 0.14796 WFG5 2.822 60 0.156 18 2.768 73 2.77874 2.712 42 0.11114 WFG6 2.346 98 2.394 74 1.712 34 2.42856 2.023 36 0.13582 IGD WFG1 1.531 40 2.074 74 3.353 78 4.07131 1.690 12 3.21088 WFG2 1.580 62 7.084 92 4.728 54 2.1176 8.839 20 3.64001 WFG3 3.422 18 3.738 76 6.422 06 0.98680 4.811 42 0.70094 WFG4 7.863 98 6.129 48 6.250 24 5.08556 5.890 66 5.42432 WFG5 7.598 92 5.897 46 7.131 26 5.10664 5.813 56 5.64624 WFG6 7.681 06 7.190 22 9.466 46 5.45448 6.204 72 5.29934 第 2 期 陈强，等：目标空间映射策略的高维多目标粒子群优化算法 ·367·
·368· 智能系统学报 第16卷 IGD值。MOPSO-OSM算法在WFG3和WFG4中 同一个测试函数，本文算法与其余算法相比较， 取得的IGD值排名第一。对于10目标测试函 随着目标个数的增加，对比算法的性能都在急剧 数，从表4可以看出，MOEA/DD在WFG1和WFG2 下降，而本文所提算法展现出了更好的适应性 中取得了IGD的最优值。NMPSO在WFG4和 能。通过以上可以看出，本文采用的目标空间映 WFG5中的IGD值最优。MOPSO-OSM算法在 射策略，将收敛性和多样性结合，用这两者对目 WFG3和WFG6中的IGD取得了最佳值。从以上 标向量进行分类选择，最后得到的非支配解具有 可以看出，本文所提算法在处理WFG1和WFG2 较好的性能。 问题时表现出较低的能力，主要原因在于目标映 图3分别给出了在5目标WFG3测试函数下 射策略要综合考虑个体的分布性和收敛性，导致 得到的Pareto前沿。对于WFG3测试函数，所有 算法都得不到一个完整的Pareto前沿。但是 了算法在该问题上的收敛性不足，无法得到一组 MOPSO-OSM算法的Pareto前沿相比于另外5种 完整的Pareto前沿，所以该算法在处理WFGl和 对比算法，其收敛性和分布性都是明显优于其他 WFG2问题时还有待提高。对于其余测试函数， 算法，表现出较好的性能。图4给出了MOPSO- 虽然在部分问题上算法无法得到最优值，但是所 OSM算法在5目标WFG3和WFG4测试问题中 得结果仍处于较好的排名。对于不同目标个数的 得到的GD值曲线。 5F 8 87 4 6 65 4 2 2 4 4 日标维数 目标维数 目标维数 (a)MOEA/DD on WFG3 (b)NSGA-III on WFG3 (c)PESA-II on WFG3 9 87 6 65 6 432 0 2 2 目标维数 目标维数 目标维数 (d)IBEA on WFG3 (e)NMPSO on WFG3 (f)MOPSO-OSM on WFG3 图36种算法在5目标WFG3测试函数所得Pareto前沿 Fig.3 Six algorithms obtain Pareto Front in 5 objective WFG3 test function 0.08 0.14 0.07 0.12 0.06 e0.10 0.05 0.04 0.08 0.03 M 0.06 0.02 0 20 40 60 80 100 0 20 40 60 80 100 记录次数 记录次数 (a)WFG3 (b)WFG4 图4 MOPSO-OSM在5目标WFG3和WFG4上的GD曲线 Fig.4 GD curves of MOPSO-OSM for WFG3 and WFG4 with five objectives
IGD 值。MOPSO-OSM 算法在 WFG3 和 WFG4 中 取得的 IGD 值排名第一。对于 10 目标测试函 数，从表 4 可以看出，MOEA/DD 在 WFG1 和 WFG2 中取得了 IGD 的最优值。NMPSO 在 WFG4 和 WFG5 中的 IGD 值最优。MOPSO-OSM 算法在 WFG3 和 WFG6 中的 IGD 取得了最佳值。从以上 可以看出，本文所提算法在处理 WFG1 和 WFG2 问题时表现出较低的能力，主要原因在于目标映 射策略要综合考虑个体的分布性和收敛性，导致 了算法在该问题上的收敛性不足，无法得到一组 完整的 Pareto 前沿，所以该算法在处理 WFG1 和 WFG2 问题时还有待提高。对于其余测试函数， 虽然在部分问题上算法无法得到最优值，但是所 得结果仍处于较好的排名。对于不同目标个数的 同一个测试函数，本文算法与其余算法相比较， 随着目标个数的增加，对比算法的性能都在急剧 下降，而本文所提算法展现出了更好的适应性 能。通过以上可以看出，本文采用的目标空间映 射策略，将收敛性和多样性结合，用这两者对目 标向量进行分类选择，最后得到的非支配解具有 较好的性能。 图 3 分别给出了在 5 目标 WFG3 测试函数下 得到的 Pareto 前沿。对于 WFG3 测试函数，所有 算法都得不到一个完整的 Pareto 前沿。但是 MOPSO-OSM 算法的 Pareto 前沿相比于另外 5 种 对比算法，其收敛性和分布性都是明显优于其他 算法，表现出较好的性能。图 4 给出了 MOPSOOSM 算法在 5 目标 WFG3 和 WFG4 测试问题中 得到的 GD 值曲线。 1 2 3 4 5 1 2 3 4 5 6 7 8 9 10 (a) MOEA/DD on WFG3 1 2 3 4 5 1 2 3 4 5 6 7 8 9 10 (b) NSGA-III on WFG3 1 2 3 4 5 1 0 2 3 4 5 (c) PESA-II on WFG3 1 2 3 4 5 1 2 3 4 5 6 7 8 9 10 (d) IBEA on WFG3 1 2 3 4 5 1 2 3 4 5 6 7 8 9 (e) NMPSO on WFG3 1 2 3 4 5 0 0 0 0 0 2 4 6 8 10 (f) MOPSO-OSM on WFG3 目标维数 目标维数 目标维数 目标维数 函数值 函数值 函数值 函数值 函数值 函数值 目标维数 目标维数 图 3 6 种算法在 5 目标 WFG3 测试函数所得 Pareto 前沿 Fig. 3 Six algorithms obtain Pareto Front in 5 objective WFG3 test function 0 20 40 60 80 100 记录次数 0.06 0.08 0.10 0.12 0.14 GD 值 (a) WFG3 0 20 40 60 80 100 记录次数 0.02 0.03 0.04 0.05 0.06 0.07 0.08 GD 值 (b) WFG4 图 4 MOPSO-OSM 在 5 目标 WFG3 和 WFG4 上的 GD 曲线 Fig. 4 GD curves of MOPSO-OSM for WFG3 and WFG4 with five objectives ·368· 智 能 系 统 学 报 第 16 卷
第2期 陈强，等：目标空间映射策略的高维多目标粒子群优化算法 ·369· 图4中横坐标为记录的次数，每7次迭代记 swarm optimization with a balanceable fitness estimation 录一次。从中可以看出，在迭代过程中，GD值都 for many-objective optimization problems[J].IEEE trans- 是逐渐减小，算法逐渐收敛。目标映射策略作为 actions on evolutionary computation,2018,22(1):32-46. 一种有效的筛选候选解的方法，对于算法在问题 [8]ZHANG Qingfu,LI Hui.MOEA/D:a multiobjective evol- 中的收敛性能的表现起到决定性的作用，因此， utionary algorithm based on decomposition[J].IEEE trans- 在高维多目标优化问题中，目标映射策略是可行 actions on evolutionary computation,2008,11(6): 712-731. 且有效的。 [9]LIU Hailin,GU Fangqing,ZHANG Qingfu.Decomposi- 4结束语 tion of a multiobjective optimization problem into a num- ber of simple multiobjective subproblems[J].IEEE transac- 本文提出了一种基于目标空间映射策略的高 tions on evolutionary computation,2014,18(3):450-455. 维多目标粒子群算法来求解高维多目标问题。该 [10]LI Ke,DEB K,ZHANG Qingfu,et al.An evolutionary 方法利用性能指标对目标空间进行划分，从而达 many-objective optimization algorithm based on domin- 到增强算法选择压力的目的。通过6组标准测试 ance and decomposition[J.IEEE transactions on evolu- 函数的仿真验证，实验结果表明，在处理高维多 tionary computation,2015,19(5):694-716. 目标问题时，目标空间映射策略能够有效地提高 [11]LIU Songbai.LIN Qiuzhen,TAN K C.et al.A fuzzy de- composition-based Multi/many-objective evolutionary al- 种群的收敛性和分布性。将该算法应用在工程实 例问题将是下一步的研究重点。 gorithm[J].IEEE transactions on cybernetics,2020:1-15. [12]ZITZLER E,KUNZLI S.Indicator-based selection in 参考文献： multiobjective search[C]//International Conference on Parallel Problem Solving from Nature.Berlin,Heidel- [1]ISHIBUCHI H.TSUKAMOTO N.NOJIMA Y.Evolution- berg:Springer,2004:832-842. ary many-objective optimization:a short review[C]//2008 [13]BADER J,ZITZLER E.HypE:an algorithm for fast hy- IEEE Congress on Evolutionary Computation(IEEE pervolume-based many-objective optimization[J].Evolu- World Congress on Computational Intelligence).Hong tionary computation,2011,19(1):45-76. Kong,China.2008:266-271. [14]MENCHACA-MENDEZ A,COELLO C A C.GDE- [2]刘建昌，李飞，王洪海，等.进化高维多目标优化算法研 MOEA:a new MOEA based on the generational distance 究综述).控制与决策，2018,33(5)：879-887. indicator and s-dominance[C]//2015 IEEE Congress on LIU Jianchang,LI Fei,WANG Honghai,et al.Survey on Evolutionary Computation(CEC).Sendai,Japan:IEEE, evolutionary many-objective optimization algorithms[J]. 2015:947-955. Control and decision,2018.33(5):879-887 [15]TIAN Ye,CHENG Ran,ZHANG Xingyi,et al.An indic- [3]DEB K,PRATAP A,AGARWAL S,et al.A fast and elit- ator-based multiobjective evolutionary algorithm with ref- ist multiobjective genetic algorithm:NSGA-II[J].IEEE erence point adaptation for better versatility[J].IEEE transactions on evolutionary computation,2002,6(2): transactions on evolutionary computation,2018,22(4): 182-197. 609-622. [4]DEB K,JAIN H.An evolutionary many-objective optimiz- [16]LI Fei,CHENG Ran,LIU Jianchang,et al.A two-stage ation algorithm using reference-point-based nondominated R2 indicator based evolutionary algorithm for many-ob- sorting approach,Part I:solving problems with box con- jective optimization[J].Applied soft computing,2018,67: straints[J].IEEE transactions on evolutionary computation, 245-260. 2014,18(4):577-601. [17]LI Miqing,YANG Shengxiang,LIU Xiaohui.Bi-goal [5]汤恺祥，许峰.基于大数据聚类的改进NSGA-Ⅲ算 evolution for many-objective optimization problems[J. 法[).信息记录材料，2020,21(5)：109-112 Artificial intelligence,2015,228:45-65. TANG Kaixiang,XU Feng.Improved NSGA-III al- [18]KENNEDY J,EBERHART R.Particle swarm optimiza- gorithm based on big data clustering[J].Information re- tion[C]//Proceedings of ICNN'95-International Confer- cording materials,2020,21(5):109-112 ence on Neural Network.Perth,Australia,1995: [6]ZOU Juan,FU Liuwei,ZHENG Jinhua,et al.A many-ob- 1942-1948. jective evolutionary algorithm based on rotated grid[J]. [19]SHI Y,EBERHART R C.A modified particle swarm op- Applied soft computing,2018,67:596-609. timizer[C]//1998 IEEE International Conference on Evol- [7]LIN Qiuzhen,LIU Songbai,TANG Chaoyu,et al.Particle utionary Computation Proceedings.IEEE World Con-
图 4 中横坐标为记录的次数，每 7 次迭代记 录一次。从中可以看出，在迭代过程中，GD 值都 是逐渐减小，算法逐渐收敛。目标映射策略作为 一种有效的筛选候选解的方法，对于算法在问题 中的收敛性能的表现起到决定性的作用，因此， 在高维多目标优化问题中，目标映射策略是可行 且有效的。 4 结束语 本文提出了一种基于目标空间映射策略的高 维多目标粒子群算法来求解高维多目标问题。该 方法利用性能指标对目标空间进行划分，从而达 到增强算法选择压力的目的。通过 6 组标准测试 函数的仿真验证，实验结果表明，在处理高维多 目标问题时，目标空间映射策略能够有效地提高 种群的收敛性和分布性。将该算法应用在工程实 例问题将是下一步的研究重点。 参考文献： ISHIBUCHI H, TSUKAMOTO N, NOJIMA Y. Evolutionary many-objective optimization: a short review[C]//2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence). Hong Kong, China, 2008: 266−271. [1] 刘建昌, 李飞, 王洪海, 等. 进化高维多目标优化算法研 究综述 [J]. 控制与决策, 2018, 33(5): 879–887. LIU Jianchang, LI Fei, WANG Honghai, et al. Survey on evolutionary many-objective optimization algorithms[J]. Control and decision, 2018, 33(5): 879–887. [2] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE transactions on evolutionary computation, 2002, 6(2): 182–197. [3] DEB K, JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, Part I: solving problems with box constraints[J]. IEEE transactions on evolutionary computation, 2014, 18(4): 577–601. [4] 汤恺祥, 许峰. 基于大数据聚类的改进 NSGA-Ⅲ算 法 [J]. 信息记录材料, 2020, 21(5): 109–112. TANG Kaixiang, XU Feng. Improved NSGA-III algorithm based on big data clustering[J]. Information recording materials, 2020, 21(5): 109–112. [5] ZOU Juan, FU Liuwei, ZHENG Jinhua, et al. A many-objective evolutionary algorithm based on rotated grid[J]. Applied soft computing, 2018, 67: 596–609. [6] [7] LIN Qiuzhen, LIU Songbai, TANG Chaoyu, et al. Particle swarm optimization with a balanceable fitness estimation for many-objective optimization problems[J]. IEEE transactions on evolutionary computation, 2018, 22(1): 32–46. ZHANG Qingfu, LI Hui. MOEA/D: a multiobjective evolutionary algorithm based on decomposition[J]. IEEE transactions on evolutionary computation, 2008, 11(6): 712–731. [8] LIU Hailin, GU Fangqing, ZHANG Qingfu. Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems[J]. IEEE transactions on evolutionary computation, 2014, 18(3): 450–455. [9] LI Ke, DEB K, ZHANG Qingfu, et al. An evolutionary many-objective optimization algorithm based on dominance and decomposition[J]. IEEE transactions on evolutionary computation, 2015, 19(5): 694–716. [10] LIU Songbai, LIN Qiuzhen, TAN K C, et al. A fuzzy decomposition-based Multi/many-objective evolutionary algorithm[J]. IEEE transactions on cybernetics, 2020: 1–15. [11] ZITZLER E, KÜNZLI S. Indicator-based selection in multiobjective search[C]//International Conference on Parallel Problem Solving from Nature. Berlin, Heidelberg: Springer, 2004: 832−842. [12] BADER J, ZITZLER E. HypE: an algorithm for fast hypervolume-based many-objective optimization[J]. Evolutionary computation, 2011, 19(1): 45–76. [13] MENCHACA-MENDEZ A, COELLO C A C. GDEMOEA: a new MOEA based on the generational distance indicator and ε-dominance[C]//2015 IEEE Congress on Evolutionary Computation (CEC). Sendai, Japan: IEEE, 2015: 947−955. [14] TIAN Ye, CHENG Ran, ZHANG Xingyi, et al. An indicator-based multiobjective evolutionary algorithm with reference point adaptation for better versatility[J]. IEEE transactions on evolutionary computation, 2018, 22(4): 609–622. [15] LI Fei, CHENG Ran, LIU Jianchang, et al. A two-stage R2 indicator based evolutionary algorithm for many-objective optimization[J]. Applied soft computing, 2018, 67: 245–260. [16] LI Miqing, YANG Shengxiang, LIU Xiaohui. Bi-goal evolution for many-objective optimization problems[J]. Artificial intelligence, 2015, 228: 45–65. [17] KENNEDY J, EBERHART R. Particle swarm optimization[C]//Proceedings of ICNN'95 - International Conference on Neural Network. Perth, Australia, 1995: 1942−1948. [18] SHI Y, EBERHART R C. A modified particle swarm optimizer[C]//1998 IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Con- [19] 第 2 期 陈强，等：目标空间映射策略的高维多目标粒子群优化算法 ·369·
·370· 智能系统学报 第16卷 gress on Computational Intelligence (Cat.No Proceedings of the 2002 Congress on Evolutionary Com- 98TH8360).Anchorage,.USA,1998:73-79. putation.CEC'02(Cat.No.02TH8600).Honolulu,USA, [20]CLERC M,KENNEDY J.The particle swarm-explo- 2002.1051-1056. sion,stability,and convergence in a multidimensional [30]WANG Hui,WU Zhijian,RAHNAMAYAN S,et al.En- complex space[J].IEEE transactions on evolutionary hancing particle swarm optimization using generalized computation,2002,6(1):58-73. opposition-based learning[J].Information sciences,2011, [21]VENTER G.SOBIESZCZANSKI-SOBIESKI J.Mul- 181(20):4699-4714. tidisciplinary optimization of a transport aircraft wing us- [31]马灿，刘坚，余方平.混合模拟退火的布谷鸟算法研究 ing particle swarm optimization[J].Structural and mul- [.小型微型计算机系统，2016,37(9)2029-2034. tidisciplinary optimization,2004,26:121-131. MA Can,LIU Jian,YU Fangping.Research on cuckoo al- [22]MA Borong,HUA Jun,MA Zhixin,et al.IMOPSO:an gorithm with simulated annealing[J].Journal of Chinese improved multi-objective particle swarm optimization al- computer systems,2016,37(9):2029-2034. gorithm[C]//2016 5th International Conference on Com- [32]CHENG Ran,JIN Yaochu,OLHOFER M,et al.A refer- puter Science and Network Technology (ICCSNT). ence vector guided evolutionary algorithm for many-ob- Changchun,China,2016:376-380. jective optimization[J].IEEE transactions on evolution- [23]QI Changxing,BI Yiming,HAN Huihua,et al.A hybrid ary computation,2016,20(5):773-791. particle swarm optimization algorithm[C]//2017 3rd IEEE [33]CORNE D W,JERRAM N R,KNOWLES J D,et al. International Conference on Computer and Communica- PESA-II:region-based selection in evolutionary multiob- tions (ICCC).Chengdu,China,2017:2187-2190. [24]KENNEDY J.Bare bones particle swarms[Cl//Proceed- jective optimization[C]//Proceedings of the 3rd Annual ings of the 2003 IEEE Swarm Intelligence Symposium. Conference on Genetic and Evolutionary Computation. SIS'03(Cat.No.03EX706).Indianapolis,USA,2003: Morgan Kaufmann Publishers Inc,2001:283-290. 80-87. 作者简介： [25]YUE Caitong,QU Boyang,LIANG Jing.A multiobject- 陈强，硕士研究生，主要研究方向 ive particle swarm optimizer using ring topology for Solv- 为进化计算和多目标优化。 ing multimodal multiobjective problems[J].IEEE transac- tions on evolutionary computation,2018,22(5):805-817. [26]侯翔，蒲国林协同粒子群优化算法的改进与仿真) 计算机工程与设计，2015,36(6)：1530-1534 HOU Xiang,PU Guolin.Improvement of its cooperative particle swarm optimization algorithm and simulation[J]. 王宇嘉，副教授，博土，主要研究 Computer engineering and design,2015,36(6): 方向为进化计算、群智能和目标优 化。发表学术论文16篇。 1530-1534 [27]LIN Qiuzhen,LI Jianqiang,DU Zhihua,et al.A novel multi-objective particle swarm optimization with mul- tiple search strategies[J].European Journal of operational research,2015,247(3):732-744. [28]ZAIN M Z B M,KANESAN J,CHUAH J H,et al.A 梁海娜.硕士研究生，主要研究方 向为进化计算和群智能。 multi-objective particle swarm optimization algorithm based on dynamic boundary search for constrained optim- ization[J].Applied soft computing,2018,70:680-700. [29]COELLO C A C,LECHUGA M S.MOPSO:a proposal for multiple objective particle swarm optimization[C/
gress on Computational Intelligence (Cat. No. 98TH8360). Anchorage, USA, 1998: 73−79. CLERC M, KENNEDY J. The particle swarm - explosion, stability, and convergence in a multidimensional complex space[J]. IEEE transactions on evolutionary computation, 2002, 6(1): 58–73. [20] VENTER G, SOBIESZCZANSKI-SOBIESKI J. Multidisciplinary optimization of a transport aircraft wing using particle swarm optimization[J]. Structural and multidisciplinary optimization, 2004, 26: 121–131. [21] MA Borong, HUA Jun, MA Zhixin, et al. IMOPSO: an improved multi-objective particle swarm optimization algorithm[C]//2016 5th International Conference on Computer Science and Network Technology (ICCSNT). Changchun, China, 2016: 376−380. [22] QI Changxing, BI Yiming, HAN Huihua, et al. A hybrid particle swarm optimization algorithm[C]//2017 3rd IEEE International Conference on Computer and Communications (ICCC). Chengdu, China, 2017: 2187−2190. [23] KENNEDY J. Bare bones particle swarms[C]//Proceedings of the 2003 IEEE Swarm Intelligence Symposium. SIS'03 (Cat. No. 03EX706). Indianapolis, USA, 2003: 80−87. [24] YUE Caitong, QU Boyang, LIANG Jing. A multiobjective particle swarm optimizer using ring topology for Solving multimodal multiobjective problems[J]. IEEE transactions on evolutionary computation, 2018, 22(5): 805–817. [25] 侯翔, 蒲国林. 协同粒子群优化算法的改进与仿真 [J]. 计算机工程与设计, 2015, 36(6): 1530–1534. HOU Xiang, PU Guolin. Improvement of its cooperative particle swarm optimization algorithm and simulation[J]. Computer engineering and design, 2015, 36(6): 1530–1534. [26] LIN Qiuzhen, LI Jianqiang, DU Zhihua, et al. A novel multi-objective particle swarm optimization with multiple search strategies[J]. European Journal of operational research, 2015, 247(3): 732–744. [27] ZAIN M Z B M, KANESAN J, CHUAH J H, et al. A multi-objective particle swarm optimization algorithm based on dynamic boundary search for constrained optimization[J]. Applied soft computing, 2018, 70: 680–700. [28] COELLO C A C, LECHUGA M S. MOPSO: a proposal for multiple objective particle swarm optimization[C]// [29] Proceedings of the 2002 Congress on Evolutionary Computation. CEC'02 (Cat. No. 02TH8600). Honolulu, USA, 2002, 1051−1056. WANG Hui, WU Zhijian, RAHNAMAYAN S, et al. Enhancing particle swarm optimization using generalized opposition-based learning[J]. Information sciences, 2011, 181(20): 4699–4714. [30] 马灿, 刘坚, 余方平. 混合模拟退火的布谷鸟算法研究 [J]. 小型微型计算机系统, 2016, 37(9): 2029–2034. MA Can, LIU Jian, YU Fangping. Research on cuckoo algorithm with simulated annealing[J]. Journal of Chinese computer systems, 2016, 37(9): 2029–2034. [31] CHENG Ran, JIN Yaochu, OLHOFER M, et al. A reference vector guided evolutionary algorithm for many-objective optimization[J]. IEEE transactions on evolutionary computation, 2016, 20(5): 773–791. [32] CORNE D W, JERRAM N R, KNOWLES J D, et al. PESA-II: region-based selection in evolutionary multiobjective optimization[C]//Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation. Morgan Kaufmann Publishers Inc, 2001: 283−290. [33] 作者简介： 陈强，硕士研究生，主要研究方向 为进化计算和多目标优化。 王宇嘉，副教授，博士，主要研究 方向为进化计算、群智能和目标优 化。发表学术论文 16 篇。 梁海娜，硕士研究生，主要研究方 向为进化计算和群智能。 ·370· 智 能 系 统 学 报 第 16 卷