基于参考点的多模态多目标粒子群算法

李国森 闫 李* 郭倩倩 周同驰 王永林 岳彩通

1(中原工学院电子信息学院 河南 郑州 450007) 2(郑州大学电气工程学院 河南 郑州 450001) 3(郑州大学产业技术研究院 河南 郑州 450001)

0 引 言

在实际工程应用中，往往存在多个目标相互冲突的多目标优化问题[1]。由于目标之间的冲突性，这类问题不存在多个目标同时最优的唯一解，而是存在一组互不占优的折衷解，称为Pareto最优解集(Pareto-optimal Set,PS)[2]。近年来，许多解决多目标问题的优化算法被相继提出[3]，如NSGA-II[4]、PESA-II[5]、SPEA2[6]和MOEA/D[7]等。这些算法得到的Pareto最优解集在目标空间映射后得到的Pareto前沿(Pareto Front,PF)分布均匀且收敛[8-9]。

在多目标优化问题中，存在一类问题具有多模态的特性，如路径规划问题[10]、背包问题[11]、火箭发动机设计问题[12]和作业车间调度问题[13]。这些问题存在着多个不同的Pareto解集，对应着目标空间中的同一个Pareto前沿[14]，被称为多模态多目标优化问题。如何设计多模态多目标算法使其能够获得多个不同的Pareto解集是解决这类问题的关键。多个Pareto解集有利于决策者根据自己的喜好选择合适的解决方案。

多模态多目标优化问题在提出之后，逐渐获得研究学者的关注。Deb等[14]提出了Omni-optimizer算法，将决策空间中拥挤距离的概念引入到非支配排序方法中以提高解在决策空间中的多样性。Liang等[16]提出了DN-NSGAII算法，采用基于决策空间的非支配排序算法以改善解在决策空间中的分布。Yue等[10]采用基于环形拓扑的小生境方法，并将特殊拥挤距离嵌入到非支配排序方法中以获得更多的Pareto解。Liu等[11]利用双档案机制和重组策略指导种群进化，提高种群的多样性和收敛性。Liang等[17]采用自组织映射网络在决策空间中建立邻域关系，并采用精英学习策略避免算法收敛过快。

但是上述研究在解决多模态多目标问题时仍然存在Pareto解集不完整、收敛性较差等问题，本文以多目标粒子群算法(Multi-objective Particle Swarm Optimization, MOPSO)[18]为框架，提出了一种基于参考点的多模态多目标粒子群算法(RPMOPSO)。通过引入参考点策略以提高种群多样性，并采用扩散机制找到更多的Pareto解。利用十二个测试函数，将RPMOPSO与其他六种算法进行性能比较，结果表明RPMOPSO在寻优性能和收敛性上表现良好。

1 基本概念

1.1 多模态多目标优化问题

如果多目标问题在决策空间中存在多个Pareto解集，且这些解集映射到目标空间中同一Pareto前沿，则称为多模态多目标优化问题(multimodal multi-objective optimization problems,MMOPs)[10]。该优化问题如图1所示，决策空间中Pareto解集PS1、PS2对应着目标空间中相同的PF。例如，A1和A2在决策空间中的位置不同，但对应目标空间中相同的点A′。找到A1和A2这两个解，可以给决策者不同的选择方案。

图1 多模态多目标优化问题

1.2 粒子群算法描述

设种群规模为N的种群，在一个D维的决策空间中进行寻优。在t时刻，第i个粒子在其个体最优位置pi(t)和全局最优位置gi(t)的引导下从当前位置xi(t)以速度vi(t)飞行[19-20]，则该粒子在(t+1)时刻的速度vi(t+1)和位置xi(t+1)可表示为：

vi(t+1)=wvi(t)+c1r1(pi(t)-xi(t))+

c2r2(gi(t)-xi(t))

(1)

xi(t+1)=xi(t)+vi(t+1)

(2)

式中：w为惯性权重；c1和c2为学习因子；r1和r2为区间[0,1]上的随机数。

随后为了进一步控制粒子的飞行速度，将压缩因子χ引入粒子的速度公式[21]，表示如下：

vi(t+1)=χ(vi(t)+c1r1(pi(t)-xi(t))+

c2r2(gi(t)-xi(t)))

(3)

(4)

2 算法设计

2.1 参考点策略

在传统粒子群算法中，每个粒子采用共享的全局最优信息更新自身的位置，以促使种群快速收敛，但在一定程度上降低了解的多样性。

图2 参考点策略示意图

因此，在粒子进行速度更新时，式(3)重新定义为：

vi(t+1)=χ(vi(t)+c1r1(pi(t)-xi(t))+

c2r2(o*-xi(t)))

(5)

2.2 扩散机制

本文采用扩散机制，以帮助粒子跳出局部最优。一方面，传统粒子群算法存在早熟停滞或者陷入局部最优的问题；另一方面，如果过多的粒子在某一次迭代中选择同一参考点，将导致这些粒子聚集在同一最优解附近，从而过度开发某一区域，而难以找到更多最优解。因此，扩散机制的基本思想是改变这些粒子的飞行轨迹，将其扩散到更大的区域，使其有机会选择新的参考点。

(pi(t)-xi(t))

(6)

式中：Levy(λ)是服从参数λ(1<λ≤3)的Levy分布的随机数；‖pi(t)-xi(t)‖表示pi(t)和xi(t)之间的距离。在式(6)中，一方面，Levy分布具有长距离和短距离跳跃相间的特性[24-25]。其长跳跃的搜索方式有利于全局探索，且不容易陷入局部停滞；另一方面，粒子根据历史最优位置和当前位置的距离动态调整搜索范围，以提高算法的全局勘探能力。当pi(t)和xi(t)距离很近时，粒子的搜索范围将变得很大，以搜索到更多的解；反之，粒子不会立即收敛到最优解，避免陷入局部最优。

2.3 算法步骤

步骤1设置算法的种群大小N、学习因子(c1、c2)、最大迭代次数MaxIter，根据佳点集原理初始化种群P，外部档案EXA=P，参考点RP=P，参考点用于保留最优解的档案RPA=P。

步骤2计算第j个(j=1,2,…,N)参考点被所有粒子选择的次数为φj。

步骤3对于第i个(i=1,2,…,N)粒子P{i}，计算该粒子离参考点最近的点(记为RP{j})，则参考点RP{j}所保留的最优信息o*为RPA{j}。根据式(5)计算粒子的速度，然后根据式(2)计算粒子的位置。

步骤5对于第j个参考点RP{j}，计算种群中离其最近的粒子，将该粒子与该参考点保留的最优解RPA{j}进行比较，保留一个非支配解进入档案RPA{j}。

步骤6更新外部档案EXA=[P;EXA]，对外部档案进行非支配排序，选择占优性强且稀疏的前N个解存入EXA。

步骤7若迭代次数达到最大迭代次数MaxIter，输出外部档案；否则，返回步骤2。

3 实 验

3.1 测试函数

本文采用12个经典的多模态多目标测试函数[10]，包括MMF1-MMF8、SYM-PART simple、SYM-PART rotate、SYM-PART rot.+ trans. 和Omni-test函数(D=3)。其中，Omni-test函数在决策空间中的Pareto解集个数最多，用来测试算法在目标空间的寻优能力。

3.2 实验设置

使用六种优化算法与RPMOPSO进行比较，包括三种多模态多目标算法(MO_Ring_PSO_SCD[10]、Omni-optimizer[9]和DN-NSGAII[16])和三种多目标算法(NSGA-II、PESA-II和MOEA/D)。其中，RPMOPSO参数如下：c1=c2=2.05。其他算法的参数值与相应文献中的参数值相同。所有算法的种群大小N和最大迭代次数MaxIter分别设置为800和100[10]，外部归档大小设置为800，独立运行25次。采用MATLAB R2014b进行仿真，运行环境为Intel® CoreTMI7-4790处理器，内存为16 GB。

3.3 评价指标

本文采用Pareto解集近似性(PSP)[10]和超体积(Hv)[26]指标衡量算法性能。PSP用于度量所获得PS的收敛性和分布性。Hv用于评价所获得PF的收敛性和分布性。PSP值越大意味着在决策空间中获得的PS的收敛性和多样性越好。Hv值越大意味着在目标空间中获得的PF越接近真实的PF。

3.4 实验结果

3.4.1策略性能对比

为了验证所提策略在解决多模态多目标问题时的有效性，将RPMOPSO算法和MOPSO[10]、RPMOPSO-I(采用参考点策略的MOPSO算法)和RPMOPSO-II(采用扩散机制的MOPSO算法)进行比较。表1所示为结合不同策略的算法的PSP的均值、标准差，以及Wilcoxon秩和检验的h值。

表1 各策略PSP指标统计

可以看出，RPMOPSO-I的性能优于MOPSO，而RPMOPSO-II的性能略优于MOPSO。因此，参考点策略和扩散机制能有效地改善基本MOPSO的性能。此外，秩和检验的结果表明，两种策略的结合能够使算法性能得到显著的提升。其原因在于参考点策略使RPMOPSO能够找到更多的Pareto最优解。参考点策略可以在决策空间中产生稳定的小生境，每个粒子在自己的小生境邻域内进化，且不会受其他邻域的影响，以提高种群的多样性。扩散机制能够使粒子向更大的范围内寻优，因此陷入局部最优的粒子不仅可以跳出当前的最优解，而且可以捕捉到更多的最优解。

3.4.2算法性能对比

本节将RPMOPSO与三种多模态多目标算法和三种多目标算法进行比较。首先，比较不同算法在决策空间获得PS的能力，不同算法的PSP值如表2所示。结果表明RPMOPSO在所有测试函数中具有较好的表现，其性能优于其他六种算法。MO_Ring_PSO_SCD排第二名，因其使用环形拓扑能够形成小生境，能够找到更多Pareto解。DN-NSGAII和Omni-optimizer的表现紧随其后，两者采用决策空间的拥挤距离作为环境选择提高了算法的性能。NSGA-II、MOEA/D和PESA-II表现较差，其原因在于这三种多目标算法没有考虑决策空间中解的分布。其次，评价算法在目标空间中获得的PF的性能，不同算法的Hv值如表3所示。可以看出RPMOPSO在Hv性能指标上表现不是最好的。实际上，所有算法在同一个测试函数上的Hv值是很接近的。原因是所有的算法都考虑了最优解在目标空间中的分布。

表2 不同算法PSP指标统计

表3 不同算法Hv指标统计

为了进一步比较算法的性能，将所有算法在Omni-test测试函数上获得的PS和PF分别在图3、图4进行展示。Omni-test测试函数有27个PS。从图3可以看出，RPMOPSO获得的Pareto最优解能够比较全面地覆盖真正的PS。MO_Ring_PSO_SCD、DN-NSGAII和Omni-optimizer获得的PS并不完整。NSGA-II、PESA-II和MOEA/D搜索到的PS更少。其中，MOEA/D仅获得一个PS。这说明没有小生境技术很难维持多个PS。从图4可以看出，所有算法在Omni-test测试函数上都能够较好的覆盖整个真实的PF，且能够逼近真正的PF。

图3 各算法所获得的PS对比

图4 各算法所获得的PF对比

综上，在获得近似PF的前提下，RPMOPSO在决策空间中获得的PS分布性良好。

3.4.3算法收敛性比较

为了比较算法的收敛性[10]，将四个多模态多目标算法(RPMOPSO，MO_Ring_PSO_SCD，Omni-optimizer和DN-NSGAII)在测试函数MMF4上进行比较。MMF4在决策空间上有4个PS，如图5所示，其PS的分布将决策空间划分为4个子区域，分别为区域1、区域2、区域3和区域4。这样每个子区域面积相等，且每个子区域均有一个PS。算法的收敛性可以定义为每一代种群分布在每个子区域中解的比例[10]。在理想的情况下，如果算法在测试函数MMF4上收敛性很好，那么每个子区域中解的比例应等于25%。

图5 测试函数MMF4的PS分布

图6为算法迭代过程中，在每个子区域中解的比例变化曲线。从图6(a)中可以看出，本文算法中的区域1、区域2所在的曲线随迭代次数增加而逐渐上升，而区域3、区域4所在的曲线呈下降趋势。在迭代次数接近50时，四个区域的解的比例趋于25%。在第80代至第100代时，每个区域的解的比例基本上接近25%。这说明RPMOPSO具有良好的收敛性。对于MO_Ring_PSO_SCD，图6(b)中每个区域的解的比例最终能够收敛到25%左右，但是区域1、区域2的解的比例略大于区域3、区域4的解的比例，这说明其收敛性略差于RPMOPSO。对于DN-NSGAII，在第30代以后，区域1、区域4的解的比例远低于区域2、区域3的解的比例。对于Omni-optimizer，在第45代以后，区域2、区域3的解的比例低于区域1、区域4的解的比例。在图6(c)、(d)中，每个区域曲线的变化趋势为频繁震荡，并不稳定。这说明DN-NSGAII和Omni-optimizer算法表现出很差的收敛性。

图6 算法的收敛性对比

可以看出，RPMOPSO在收敛性上具有良好的性能。

4 结 语

本文提出了一种基于参考点的多模态多目标粒子群算法(RPMOPSO)。采用了参考点策略和扩散机制，参考点策略的引入促使种群形成若干小生境，每个粒子在它的小生境邻域内独立进化，以提高种群的多样性。扩散机制能够改变粒子的飞行轨迹，扩散粒子到更大的搜索区域，极大地提高了粒子捕捉到更多Pareto解的可能性。通过和多模态多目标算法及多目标优化算法的比较，证明了RPMOPSO能够找到更多的Pareto解，且具有很好的收敛性。未来将尝试把算法应用于求解实际中的多模态多目标问题。