基于速度约束和全局多样性的MOPSO算法

赵 晶，曲相宇

(齐鲁工业大学(山东省科学院)计算机科学与技术学院，山东 济南 250353)

1 引言

在多目标优化问题中，这些目标往往互相矛盾，没有一个单一的解决方案可以同时优化所有目标，因此其解集并不是唯一的[1-2]。如果想让优化问题中的每个目标函数值达到最佳效果，需要对这些目标函数进行进一步的处理，目前有很多算法用于求解多目标优化问题，如基于参考点的非支配排序遗传算法(A Fast and Elitist Multi-objective Genetic Algorithm，NSGA-Ⅱ)[3]，基于分解的多目标进化算法(A Multi-objective Evolutionary Algorithm Based on Decomposition，MOEA/D)[4]。在各种智能优化算法中，粒子群优化算法(Particle Swarm Optimization，PSO)是处理多目标优化问题的主流算法之一[5]。

在MOPSO算法中，如何提高算法所得的非支配解的收敛性和多样性是算法亟待解决的主要难题，国内外专家对此作了很多研究[6]。粒子群优化算法的显著特点是群中所有个体之间的协作，每个粒子都被群体中的全局最优(gBest)和自己的个体最优(pBest)所吸引从而改变自己的飞行方向，因此协作搜索策略使得粒子群算法具有更好的全局搜索能力[7-8]。另外，与其他进化计算算法相比，粒子群优化算法具有计算量小、收敛速度快的特点[9]。粒子群优化算法的相对简单性和作为单目标优化算法的成功，促使研究者将粒子群算法的应用从单目标优化问题扩展到多目标优化问题。然而，除了档案维护外，MOPSO仍有两个问题有待进一步解决。

第一个是gBest和pBest的更新，多目标问题因为没有绝对的最佳解决方案，而是一组非支配的解决方案。根据gBest和pBest的不同策略，可以从非支配集合中选择不同的候选对象，gBest和pBest的不同选择会导致粒子的飞行方向不同，这对粒子的收敛性以及MOPSO的多样性有重要影响[10]。Knowles[11]等人通过增强多目标问题中非支配解的多样性，提出了自适应超网格选择全局最优解策略，但该方法会使得全局最优解朝着非代表性的支配前沿靠近，没有兼顾到粒子的收敛性。Zhan[12]等人提出一种自适应粒子群优化算法，该算法预先定义粒子的4种进化状态，从而对惯性因子、加速因子及其它参数达到自动控制的目的，有效平衡了解集的收敛性和多样性。Zheng等人[13]通过综合学习策略引入了一种新的MOPSO算法，该算法能够保持群体的多样性，并显著提高进化粒子的性能。Lee 等人[15]提出了一种基于偏好排序的MOPSO算法，将用户的偏好引入进化过程中，以确定非支配解的相对优缺点，以选择合适的gBest和pBest。在每一次优化后，通过选择全局评价值最高的方法来选择最优的粒子作为gBest。结果表明，用户的偏好在优化后的解中得到了很好的反映，而不损失整体解的质量和多样性，但在粒子收敛性方面还有待加强。Liu等人[17]提出了一种基于平衡收敛性和多样性的个体适应度计算策略(NMPSO)来定义解的新适应度，用于更好地寻找gBest和pBest，结果表明，NMPSO在某些多目标问题的表现不够稳定。对于上述算法，如何选择合适的具有适当收敛性和分布性的gBest和pBest仍然是一个挑战[18-19]。

MOPSO的第二个问题是收敛性，为了实现MOPSO的快速收敛，人们提出了许多不同的策略。Nebro和Durillo等人提出了基于速度约束的多目标粒子群优化算法(Speed-constrained Multi-objective PSO，SMPSO)[16],该算法在传统PSO基础上引入收缩因子φ控制速度更新，提高了算法的收敛性，并跳出局部最优。但在算法多样性方面表现欠佳。Li和Xiao[20]提出了一个动态MOPSO，在该模型中，群的数量在整个搜索过程中都是自适应调整的。动态MOPSO算法分配适当数量的群以支持收敛和分集准则。结果表明，在一些标准的基准问题上，所提出的动态MOPSO算法与所选算法相比具有一定的竞争力。韩等人[14]提出了一种基于种群多样性信息的飞行参数调整机制来增强粒子收敛性，但在某些收敛时期易发生陷入局部最优的风险。在这些MOPSO算法中，为了获得更好的性能，还开发了其它策略(如模糊聚类、协同协同进化等)[21，22]。然而，如何将MOPSO算法的收敛性和多样性相结合的研究仍然不多[23]。

基于以上分析和回顾，本文提出一种基于速度约束和全局多样性信息的多目标粒子群优化算法(SGDMOPSO)，SGDMOPSO算法主要从以下几个方面进行了改进，原因如下：

1)速度更新方法中融入了速度收缩因子φ和新的由pBest到gBest的搜索方向，以提高整个粒子群的收敛速度，平衡粒子的全局搜索能力和局部开发能力。

2)采用基于精英库多样性信息的外部档案维护策略，从非支配解的多样性考虑，运用多个指标剔除劣势解，能够保持外部档案中非劣解的多样性。

3)从整个精英库中的非支配解的多样性考虑，非支配解的多样性信息表征着算法在分布性方面的优劣，将此指标作为选取全局最优粒子的选择机制，而全局最优解在本算法中影响着新的搜索方向，因此同时兼具了收敛性和多样性，当精英库中非支配解的多样性好时，全局最优解的指标为收敛度最高的解；当精英库中非支配解的多样性不好时，全局最优解的指标为密集属性最大的解。

通过上述改进，使得该算法在进化过程中具有更快的收敛速度和更高的处理MOPs的效率。

本文第二部分详细介绍了SGDMOPSO算法：包括速度更新策略、外部存档更新、算法流程；第三部分为仿真及结果分析；第四部分为总结。

2 SGDMOPSO算法

2.1 PSO算法及改进

1)PSO

粒子群优化算法(PSO)[24-25]是1995年由Kennedy和Eberhart提出的一种仿生启发式算法，它模拟鸟群聚集的社会行为，算法结构简单、参数少、收敛速度比较快。自从摩尔和查普曼在1999年首次将其扩展到多目标优化问题[26]以来，PSO算法已经成为解决多目标优化问题的一种非常流行的方法[14]。

PSO中的每个粒子有两个属性：位置x和速度v，它们由以下公式更新：

vi(t+1)=ω×v(t)+c1×r1×(pbesti-xi(t))

+c2×r2×(gbest-xi(t))

(1)

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

(2)

其中，xi为第t代粒子群中的第i个粒子，它的当前速度为vi(t)，当前位置为xi(t)，历史最优位置为pbesti；整个粒子群的历史最优位置为gbest；ω为惯性权重，用于调节粒子的飞行速度，如果ω大于1，会导致粒子的速度增加到无穷大，因此ω一般取小于1的随机数；c1和c2分别表示向个体历史最优和历史全局最优的学习因子，r1和r2是两个0到1之间的随机数。

2)改进MOPSO速度控制

为了平衡PSO算法的全局搜索能力和局部开采能力，Zhan等人对惯性权重ω进行改进，使其在一定数值区间内作随机调整[27]。Nebro和Durillo等人提出了基于速度约束的多目标粒子群优化算法(Speed-constrained Multi-objective PSO，SMPSO)，该算法在传统PSO基础上引入收缩因子φ控制速度更新，φ由学习因子c1和c2决定，其定义为[16]

(3)

Liu等人提出了一种平衡适应度值估计的多目标粒子群优化算法(A Balanceable Fitness Estimation for Many-objective PSO，NMPSO)，在速度更新过程中加入pbest到gbest的搜索方向[17]。为了避免加入新的搜寻方向对粒子寻优影响过大而削弱学习因子c1和c2的作用，更好地提升算法收敛速度和精度，本文在NMPSO的思想上，对PSO算法的速度更新策略做了进一步的改进，融入了由两个学习因子c1和c2决定的速度收缩因子，使得粒子在新速度更新中既增加了方向的精细性，又保持了全局搜索能力和局部勘探能力。提出新的SMOPSO(Multi-objective Particle Swarm Optimization based on Speed-constraints,SMOPSO)算法，在该算法中，定义第i个粒子xi的速度更新公式为：

(4)

其中c1、c2、c3为学习因子；r1、r2、r3为0到1之间的随机数。改进SMOPSO中xi的位置更新依然如PSO算子的式(2)一样。通过在速度更新过程中增加由pbest到gbest的搜索方向，引导粒子群中的粒子向全局最优方向进化，加快粒子群的收敛速度。

在SMOPSO算法的速度控制策略中，进一步对粒子的速度中每一维元素越界做了压缩控制

(5)

其中，Δj=0.5×(uj-dj),j=1,2，…,m,m为目标数，uj和dj分别为每个粒子速度第j元素的上下界限。

2.2 基于精英库的外部档案更新

外部档案主要用于存储粒子在迭代过程中求得的较好的非支配解，当非支配解的数量达到最大容量时，在MOPSO算法[28]中，本文提出基于精英库的多样性信息的外部存档更新机制，将不同时期的外部存档用多种规则灵活地进行更新，保留当前外部存档时期最合适的非支配解，最大程度上维护解集的多样性。基本思路如下：设At为第次迭代后产生的精英库，At由第t次迭代产生的非支配解集Bt和前t-1次迭代保留下来的非支配解集Ct-1组成。如果在第t次迭代后算法产生的解被t-1代精英库At-1中的解支配时，该解不是非支配解，不能进入精英库At；如果精英库At-1中的解被第t次迭代产生的解所支配时，精英库中该支配解不再为非支配解，将其放入集合Dt-1中。

定义1(密集属性)：一个非支配解的密集属性为该非支配解与其相邻的两个非支配解的平均欧氏距离，即

(6)

其中，Disti是第i个非支配解密集属性，dist1i、dist2i是与第i个非支配解相邻非支配解的欧氏距离。非支配解的密集属性越小，表示该非支配解附近越拥挤。

定义2(支配属性)：一个解x∈Bt的支配属性EA(x)是x在精英库At中能够支配的解y∈Dt-1的数目，即

EA(x)=|{y|y∈Dt-1∧x>y∧x∈Bt}|

(7)

其中Bt是第t次迭代产生的精英库At中的非支配解集，Dt-1是第t次迭代产生的精英库At中所支配的解的集合。当EA(x)为零时，该解支配属性为零。

这里，非支配解集Bt中的解包含两种：一种是可以支配Dt-1集合中的解(支配不为零)；另一种是不可以支配Dt-1集合中的解(支配属性为零)。

定义3(收敛属性)：一个解x∈Bt的收敛属性是其与所有被其支配的解yi∈Dt-1的平均欧氏距离，即

(8)

其中，Dave(x)是解x的收敛属性，yi是被解x支配的第i个解。非支配解集Ct-1中解的收敛属性为零，无支配属性的解其收敛属性也为零。

精英库At更新的具体流程如下：

Step1：若精英库At容量未满，则非支配解直接进入。

Step2：若精英库At容量已满，执行以下操作：从精英库At中非支配解的多样性考虑，计算精英库At中每个非支配解的密集属性，删减解集Ct-1中密集属性较小的解和非支配解集Bt中支配属性为零的解。

Step3：如果删减完密集属性较小和支配属性为零的解后仍然超出精英库容量，考虑删减Dt-1集合中支配属性不为零的解。计算此时精英库中非支配解的收敛属性Dave，删减Dave较小的解，若Dave相等，则执行Step4。

Step4：计算解集Bt中解的支配属性，比较支配属性大小，优先删减支配属性较小的解。

2.3 全局最优选择机制

由于PSO算法优化过程中容易出现早熟现象，导致算法陷入局部最优，为了更好地跳出局部最优，收敛至全局最优，在保证收敛性的情况下根据多样性信息选择最优的全局最优解。

定义4(多样性信息)：本文的多样性信息一共分为两种，一种为种群多样性信息，一种为精英库非支配解的多样性信息。

种群多样性信息：从整个粒子群考虑，种群多样性能反映种群的粒子分布情况。种群多样性不好，有可能导致算法优化过程中寻优速度慢、精度不够。其表达式为

(9)

式中，SPp(t+1)是第t+1次迭代粒子群的种群多样性信息，dpt(t+1)是在第t+1次迭代第i个粒子与其它粒子之间最小的曼哈顿距离，dpi(t+1)是所有的dpi(t+1)的平均值，n1是粒子的个数。

非支配解多样性信息：从精英库中非支配解的多样性考虑，非支配解的多样性代表了算法在分布性方面的性能，非支配解多样性越好表示算法分布多样性越好。其表达式为

(10)

根据式(10)计算的非支配解多样性信息可以作为精英库中非支配解集的多样性度量指标，通过比较非支配解多样性SPn(t+1)值与α值的大小关系(α为非支配解多样性信息SPn(t+1)优劣性的分界值，在文中方法中定义α=0.05)，判断当前整个精英库中非支配解集的分布状态。

全局最优解选择机制为：

1)若SPn(t+1)≤α，说明整个精英库非支配解的多样性比较好，从算法角度考虑应提高算法收敛速度，此时全局最优解应选取收敛属性最大的非支配解。

2)若SPn(t+1)>α，说明整个精英库非支配解的多样性比较差，从算法角度考虑应增加粒子分布的多样性，此时全局最优解应选取密集属性最大的非支配解。

2.4 SGDMOPSO算法流程

Step1：参数初始化：设置种群规模，最大迭代次数，个体粒子的速度、位置、惯性权重、学习因子，并将各粒子的初始位置设为其当前个体最优位置pbesti。

Step2：计算各粒子的适应度值，根据适应度值得到精英库，根据式(6)(7)和(8)分别计算各个非支配解的密集属性、支配属性和收敛属性。

Step3：计算当前整个精英库非支配解多样性SPn(t+1)，根据1.3节全局最优选择策略确定全局最优解。

Step4：比较Step2中精英库中各个非支配解的密集属性、支配属性和收敛属性的值，按照精英库更新策略，生成新的精英库。

Step5：按照式(1)和(2)更新粒子的位置和速度。

Step6：判断是否达到迭代次数，如达到迭代次数，则结束更新，否则转到Step2。

3 实验

3.1 MOP测试函数

1)性能标准

在多目标优化问题中，衡量一个算法应从收敛性和多样性的角度来评价，因此本文采用以下两个定量指标来说明算法效果。

①反向世代距离Inverted Generational Distance(IGD)：IGD通过计算所求得的近似Pareto最优解集前沿面的距离来综合评价算法的收敛性与多样性，IGD可定义为

(11)

其中，dist(x,P)为真实前沿P*中一个解x和所获Pareto前沿之间的最小欧氏距离，|P*|表示真实的Pareto最优解集上的点的数量。IGD越小表明算法的收敛性和多样性越好。

(12)

其中，Vol(·)表示勒贝格测度。其中P中所有的解都应能支配zr，如果不能支配，则将该解从P中删除。HV越大表明算法的多样性和收敛性越好。

2)标准测试函数

为了验证SGDMOPSO算法的性能，本文采用标准测试函数ZDT1、ZDT2、ZDT3、ZDT4、ZDT6、DTLZ2和DTLZ7对4种算法进行测试。

为了对比不同算法的有效性能，将SGDMOPSO算法与SMPSO算法[16]、NSGA-Ⅱ算法[3]、NMOPSO算法[17]的测试数据相比较。在比较实验中，算法执行时的参数设置为：各算法种群大小和精英库外部存档的最大容量均为100，最大迭代次数为2000。各算法的具体参数设置如表1所示，测试函数的参数设置如表2所示。

表1 算法参数设置

表2 测试函数参数设置

3.2 实验结果与分析

表3和表4分别列出了4种算法在ZDT和DTLZ系列测试函数上的IGD和HV，Mean和Std分别表示同一算法在相同测试问题上独立运行30次后的均值和方差，它们的最优数据用粗斜体表示，由此可反映出IGD和HV测试性能的综合评价效果。图1～6为4种算法得到的非劣支配解和真实的非劣支配解之间的相互关系。

从表3和表4可以看出，算法SGDMOPSO在给定的7个测试问题中分别获得5个最优IGD值和4个HV值，可见SGDMOPSO算法在这7个测试问题的多样性和收敛性表现优秀，在以上几种测试问题上几乎都优于其它3种算法。对于ZDT4测试问题，SGDMOPSO性能上要稍逊于NSGA-Ⅱ，在其它测试问题均优于NSGA-Ⅱ；对于DTLZ2和DTLZ7测试问题，SGDMOPSO性能上要稍逊于NMOPSO，在其它测试问题上都优于NMOPSO。从总体结果来看，本文算法在综合性能优于其它的3种比较算法。

图1 ZDT1的Pareto曲线

图2 ZDT2的Pareto曲线

图3 ZDT3的Pareto曲线

图4 ZDT4的Pareto曲线

图5 ZDT6的Pareto曲线

图6 DTLZ2的Pareto曲线

表3 SGDMOPSO算法与其它算法的IGD指标

表4 SGDMOPSO算法与其它算法的HV指标

从图1～6可以看出，SGDMOPSO在测试问题ZDT1、ZDT2、ZDT3、ZDT4、ZDT6和DTLZ2求得的非支配解的分布性和收敛性均较好。对于ZDT1、ZDT2和ZDT3测试问题，4种算法虽然都能够较好地求得Pareto前沿，但SGDMOPSO算法得到的非支配解的分布性更加均匀。对于ZDT4测试问题，NMPSO算法所求得的Pareto前沿效果分布性较差,SGDMOPSO算法求得的Pareto前沿分布依然最均匀。对于ZDT6测试问题，SGDMOPSO算法获得的Pareto前沿分布效果比其它3种算法好，不仅能够较好地与真实Pareto前沿趋于吻合，且解的分布情况也比较均匀。对于三维测试问题DTLZ2，SGDMOPSO算法和NMPSO算法在DTLZ2的测试效果要好于其它两种算法。换句话说，SGDMOPSO算法在大部分测试目标上都优于其它3种算法。

4 结语

为了更好地提高收敛速率和避免陷入局部最优，本文提出SGDMOPSO算法，通过改进速度更新公式和全局多样性信息选取最优解来提升算法的性能，将粒子速度方向控制、全局最优选择策略、精英库外部档案维护策略较好地统一在一起。实验结果表明，提出的算法能够获得较好的Pareto最优前沿分布特性和较快的收敛速率。尽管SGDMOPSO算法已经能够获得较高地收敛精度和较好的多样性，但是对于处理某些具体实际问题还存在一定局限性，下一步的研究考虑融入其它智能优化算法的思想，如微分进化算法、遗传算法等，从而更好地从多样性和收敛性两方面来探究求解高维多目标优化问题的有效性和可行性。