第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:WIF<FnD点≥Dis.Y,eA.处于B区 fi=diu ，i=1,2,…,n (4) 域的个体，其收敛性较好，分布性较差。 1 式中：m表示目标函数的个数；d,。表示个体i到参 C:YF,>FDis,≤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) <0.005,t>10 的个体进人外部文档。当B和C中的个体个数 Imin(f (11) 不能满足条件时，最后选取D中的个体。 Imax(f)-max(f10 <0.005,1>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 xi<xaminllxi>xdmas 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 < xdmin||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 )| < 0.005 , t > 10 |max(f t i )−max(f t−10 i )| |max(f t i )| < 0.005 , t > 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 卷