第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] 作为 NSGA￾II 的改进版本，为了增强算法处理高维多目标优 化问题的能力，在筛选同一等级的个体时，采用 了基于参考点的方法来代替拥挤距离，然而该算 法仅在某些具有特定形状的 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] 采用 Hyper￾volume 指标选取非支配解，该方法在处理高维多 目标问题时无法保证分布性。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·