基于三方竞争机制的反向多目标粒子群优化算法

韩 飞， 郑明鹏

(1. 江苏大学 计算机科学与通信工程学院, 江苏 镇江 212013; 2. 江苏大学 江苏省工业网络空间安全技术重点实验室, 江苏 镇江 212013)

优化问题在很多实际应用 (如科学研究和工程实践) 中非常普遍.大多数的实际优化问题通常是由多个需要同时优化、相互冲突的目标构成的，这一类优化问题通常称为多目标优化问题(multi-objective optimization problems, MOPs).这一类优化问题通常比单目标优化问题更加棘手，因为适用于1个函数的解可能并不适用于其他函数，即此类问题中不存在唯一的最优解，只能寻找一组能均衡目标之间优劣的最佳折中解的集合，使所有目标尽可能达到最优.

为了获得MOPs的优化解，具有收敛速度快、易于实现等优点的多目标粒子群优化算法(multi-objective particle swarm optimization, MOPSO)获得了国内外学者的广泛关注.然而在将MOPSO应用于解决多目标优化问题时，除了需要考虑如外部存档的维护等其他进化算法所共有的一些策略之外，个体最优解和种群最优解的选择以及多样性和收敛性的平衡等方面仍然存在着挑战.

不同于传统的MOPSO更新策略，ZHANG X. Y.等[1]将两两竞争机制引入多目标优化领域，提出了一种基于竞争机制的多目标粒子群优化算法(competitive mechanism based multi-objective particle swarm optimizer, CMOPSO)，该算法首先选取一部分最优粒子作为精英粒子，在每次竞争中从这些精英粒子中随机挑选2个精英粒子参与竞争，获胜的精英粒子将用来引导其他粒子进化.该算法能够有效减少种群进化过程中外部存档维护带来的计算成本，并且在很多MOPs上都表现出了较好的性能.基于CMOPSO算法，刘明等[2]提出了一种基于定期竞争机制的MOPSO算法，该算法采用定期竞争机制将全局最优粒子选择策略和竞争学习机制结合起来，每隔一定代数便使用竞争学习机制对种群进行更新，在防止算法陷入局部最优的同时，提高了种群的多样性.TIAN Y.等[3]提出了一种求解大规模MOPs的多目标粒子群优化算法，该算法基于两两竞争机制提出了一种竞争失败者粒子2阶段位置更新策略，进一步提高了算法跳出局部最优的能力.鉴于CMOPSO算法在解决超多目标优化问题方面的不足，YANG W. S.等[4]提出了一种基于竞争机制的超多目标粒子群优化算法(multi/many-objective particle swarm optimization algorithm based on competition mechanism, CMaPSO)，该算法使用了与CMOPSO算法相同的学习方法，但提出了一种新的环境选择策略，利用普通个体和极值点之间的最大角度和最小角度来选择最优个体进入下一代种群，进一步提高了算法的性能.综上所述，传统的两两竞争机制在多目标优化领域得到了广泛的应用并取得了较为优秀的表现，但算法的多样性和收敛性仍然有进一步提升的空间.

文中提出一种基于三方竞争机制的多目标粒子群优化算法(opposition-based multi-objective particle swarm optimization algorithm based on tripartite competition mechanism, MOPSO-TCOL).在所提出算法中，除了预选的精英粒子直接进入下一代之外，其他粒子均参与竞争，其主要思想是允许粒子在空间中进行更广泛的搜索，以保持算法的多样性.根据三方竞争机制的特点，提出一种基于反向学习的渐进式粒子更新策略，部分粒子进行反向学习以避免算法陷入局部最优，其他粒子通过向指定的更优粒子学习进行更新，借助亚军粒子良好的反向学习能力，避免算法陷入局部最优.最后，通过对比试验验证MOPSO-TCOL算法的性能.

1 基本概念

1.1 多目标优化

多目标优化问题一般可以描述如下：

minF(x)=(f1(x),f2(x),…,fm(x))T,

s.t.gp(x)≤0,p=1,2,…,P,hq(x)=0,

q=1,2,…,Q,

(1)

式中：x=(x1,x2,…,xn)是一个n维的决策向量；

fi(x)为第i个目标函数值；m为目标的个数；gp(x)≤0表示第p个不等式约束；hq(x)=0表示第q个等式约束.

Pareto支配及Pareto最优解集定义[5]如下.

定义1(Pareto支配)给定2个解x和y，称x支配y(记为xy)，当且仅当

∀i∈{1,2,…,k},fi(x)≤fi(y)∧∃i∈{1,2,…,k},fi(x)

(2)

定义2(Pareto最优解集)所有Pareto最优解的集合称为Pareto最优解集(Pareto optimal set,POS)，即

POS={x|∃y∈Ω,yx}.

(3)

1.2 基本粒子群优化算法

MOPSO算法的概念来源于PSO算法.在PSO算法中，设第k个粒子的速度属性为Vk=(vk,1,vk,2,…,vk,D)，位置属性为Xk=(xk,1,xk,2,…,xk,D)，k=1,2,…,N，其中N为种群规模大小.则第k个粒子在第t+1次迭代时的更新公式如下：

vk,d(t+1)=wvk,d(t)+c1r1(pbestk,d-

xk,d(t))+c2r2(gbestd-xk,d(t)),

(4)

xk,d(t+1)=xk,d(t)+vk,d(t+1),

(5)

式中：d=1,2,…,D，D为决策向量的维度；w为惯性权重；c1和c2为2个加速度系数，也称为学习因子；r1和r2为2个分布在[0,1]的随机数；pbestk,d和gbestd分别为第k个粒子的历史最优位置和种群最优位置.

1.3 竞争性粒子群优化算法

竞争性粒子群优化算法CSO是CHENG R.等[6]提出的一种元启发式算法，其中提出的两两竞争机制能够有效提升算法的性能.该算法本质上受到PSO算法的启发，但在概念上却有很大的不同.在每次竞争中，从种群中随机挑选2个粒子进行比较，赢得竞争的粒子将直接进入下一代，而竞争失败的粒子则需要通过向胜利者学习来更新自己的位置和速度，直到种群中一半的粒子被更新为止.在第k轮竞争后，竞争失败者粒子的速度及位置更新公式如下：

Vl,k(t+1)=r1Vl,k(t)+r2(Xw,k(t)-

(6)

Xl,k(t+1)=Xl,k(t)+Vl,k(t+1),

(7)

1.4 反向学习

反向学习(opposition-based learning, OBL)的思想是于2005年提出的，其已被证明能够有效提升算法的搜索效率和寻优速度.一些与反向学习策略相关的概念如下.

(8)

(9)

式中：k为一个[0,1]内的随机数；xj∈[aj,bj]，daj和dbj分别是当前代中种群搜索空间中第j维上的最小值和最大值，即

daj=min(Vj),dbj=max(Vj),

(10)

式中：Vj为种群个体在第j维上所有取值的集合.

2 基于三方竞争机制的反向MOPSO算法

2.1 算法框架

算法1MOPSO-TCOL算法.输入：种群规模N，最大迭代次数tmax.输出:最终种群Ptmax.算法流程如下：

P0←RandomInitialize(N);

whilet

Pt′=TripartiteCompetitionBasedLearning(Pt);

Pt+1=EnvironmentalSelection(Pt′∪Pt);

t=t+1;

end while

returnPtmax

由算法可见，MOPSO-TCOL拥有一个非常简单的算法框架，主要包含2个部分：基于三方竞争机制的粒子更新策略和环境选择策略.首先初始化一个大小为N的粒子群Pt，然后使用提出的三方竞争机制来更新种群中的每个粒子，再使用多项式变异(polynomial mutation, PM)对更新后的粒子进行扰动，最终得到一个新的种群Pt′，最后利用环境选择策略从混合种群(Pt′∪Pt)(规模为2N)中选出N个更好的粒子作为下一代种群进入下一次迭代直至达到算法终止条件.为简单起见，文中借鉴了NSGA-Ⅲ[7]算法中的环境选择策略来筛选粒子.

2.2 基于三方竞争的学习机制

在初始化生成N个粒子后，MOPSO-TCOL算法使用三方竞争机制来更新粒子，与CSO算法中采用的两两竞争机制不同，除精英粒子直接进入下一代之外，种群中其他所有的粒子都有机会向更好的粒子学习来更新自己.基于三方竞争的学习机制包括3个部分：精英粒子选择策略、三方竞争策略和粒子更新策略，其详细过程如算法2所示.

算法2基于三方竞争的学习机制.输入： 当前种群P.输出：新种群P′.算法流程如下：

P′←∅;

/*精英粒子选择策略 */

L← 根据非支配排序和拥挤距离排序结果从当前种群P中选出λ个粒子构建精英粒子集L；

P*←CLP；

Fitness← 应用式(11)、(12)计算种群P*中每个粒子的适应度值；

while |P*|>1 do

/* 三方竞争策略*/

{p,q,r}←随机从种群P*中选择3个粒子；

P*←P*-{p,q,r}；

假设Fitness(p)≥Fitness(q)≥Fitness(r)

Xw(t)←p,Xmw(t)←q,Xl(t)←r；

/* 粒子更新策略 */

Xe←从精英粒子集中随机挑选一个精英粒子；

应用式(14)更新粒子Xw(t)；

应用式(15)更新粒子Xmw(t)；

应用式(19)更新粒子Xl(t)；

利用多项式变异对粒子Xw(t)、Xmw(t)、Xl(t)进行扰动；

P′←P′∪{Xw(t),Xmw(t),Xl(t)}；

end while

P′←P′∪L；

returnP′

在某种意义上来说，种群中几乎所有的粒子都是通过间接地向精英粒子学习来更新自己的速度和位置，也就是说精英粒子间接被用来引导整个种群进化，因此选择的精英粒子必须同时具备良好的收敛性和多样性，精英粒子的好坏也会直接影响算法性能的优劣.

基于三方竞争的学习机制采用了非支配排序和拥挤距离排序[8]相结合的方式来挑选精英粒子.在进行精英粒子的选择时，首先对当前种群P中的所有粒子进行非支配排序以获得种群中每个粒子的Pareto前沿面编号F1,F2,…,Fn.当需要挑选λ个精英粒子时，首先要确定满足条件的Pareto前沿面编号.假设前k个前沿上的粒子数大于或等于λ，即|F1∪F2∪…∪Fk|≥λ，并且前k-1个前沿上的粒子数小于或等于λ，即|F1∪F2∪…∪Fk-1|≤λ.首先将前k-1个前沿面上的所有粒子加入精英粒子集，剩下的精英粒子在第k个前沿上基于拥挤距离排序结果选取.

至于种群中每个粒子的适应度值计算，不能采用像单目标PSO算法中直接将每个粒子的目标函数值作为其适应度值的机制，因为在MOPSO算法中每个粒子都有多个目标函数值.文中引入了一种基于Iε+指标和位移密度估计(shift-based density estimation, SDE)的混合指标ISDE+[9]来计算每个粒子的适应度值以评估各个粒子的优劣性.Iε+指标可以促进收敛性，而SDE则能促进种群的多样性，因此ISDE+混合指标能够帮助算法更好地平衡多样性和收敛性.一般而言，具有更高ISDE+值的粒子将被认定为更优.种群P中粒子p的适应度值定义为p与种群中其他粒子q基于ISDE+的最小距离，表示如下：

Fitness(p)=

(11)

(12)

式中：PSB(p)∈P,且q∈PSB(p)，SB(q)

在计算完每个粒子的适应度值之后，利用三方竞争学习机制对种群中除精英粒子之外的所有粒子进行比较.在每次竞争中，从种群中随机挑选3个粒子进行比较，适应度值最大、次之、最小的分别定义为冠军粒子、亚军粒子、季军粒子，它们对应不同的更新策略.

2.3 粒子更新策略

不同于两两竞争机制中的粒子更新方式，文中针对三方竞争机制的特点提出了一种基于反向学习的渐进式粒子更新策略.在改进的粒子更新策略中，每次更新时，首先从精英粒子集L中随机挑选一个精英粒子，冠军粒子首先向预选的精英粒子学习进行更新，然后亚军粒子通过反向学习策略来更新自己，最后季军粒子则向更新后的冠军粒子学习来更新自己的速度和位置，这有利于增强算法的全局搜索能力，并且让粒子更快地逼近真实的Pareto前沿.

假设第t次迭代时，在第k轮竞争后冠军粒子、亚军粒子和季军粒子的位置分别表示为Xw,k、Xmw,k和Xl,k，其速度分别表示为Vw,k、Vmw,k和Vl,k，其中k=1,2,…,(N-λ)/3.则在第t次迭代第k轮竞争后，冠军粒子的更新公式如下：

Vw,k(t+1)=r1Vw,k(t)+r2(Xe,k(t)-Xw,k(t)),

(13)

Xw,k(t+1)=Xw,k(t)+Vw,k(t+1).

(14)

亚军粒子不更新速度，直接基于动态广义反向学习策略来更新自己的位置，即

Xmw,k(t+1)=k(daj+dbj)-Xmw,k(t),

(15)

式中：[daj,dbj]为第j维搜索空间的动态范围，下限、上限分别取值为亚军粒子Xmw,k=(xmw,k1,xmw,k2,…,xmw,kD)在第j维上的最小值和最大值，即

daj=min(xmw,kj),dbj=max(xmw,kj).

(16)

此时需要注意的是，亚军粒子在某代进化中可能会跳出可行解的边界，此时对其在[daj,dbj]内采用随机生成的方法进行重置，即

(17)

季军粒子通过向更新后的冠军粒子学习来更新自己的速度和位置，即

Vl,k(t+1)=r3Vl,k(t)+r4(Xw,k(t+1)-Xl,k(t)),

(18)

Xl,k(t+1)=Xl,k(t)+Vl,k(t+1).

(19)

式(13)-(19)中Xe,k是精英粒子的位置，参数r1-r4均为[0,1]D内的随机向量.值得注意的是，种群中1/3的亚军粒子通过反向学习策略更新自己，有利于引导算法跳出局部最优，而冠军粒子向精英粒子学习，季军粒子又通过向更新后的冠军粒子学习来进行更新，也能够有效避免算法多样性的丧失.

最后，为了进一步增强算法跳出局部最优的能力并提升种群多样性，使用在遗传算法中广泛应用的多项式变异来对更新后的所有粒子施加轻微变异，再将变异后的粒子加入新种群P′，重复上述操作直到种群P中所有的粒子都已被更新.

2.4 时间复杂度分析

由算法1和算法2可知，MOPSO-TCOL算法主要由种群初始化、精英粒子选择、三方竞争学习、速度与位置更新、环境选择策略5个部分组成.对于一个大小为N的种群和一个含有m个目标的多目标优化问题，随机初始化种群的时间复杂度为O(N)，而精英粒子是由非支配排序和拥挤距离排序机制选择的，其最坏情况下的时间复杂度为O(mN2).对于采取的三方竞争机制，在每次竞争中首先从种群中随机挑选3个粒子，然后进行适应度值比较，所需要的时间复杂度为O(3N×log(3N))；然后每个粒子向更优粒子学习或基于反向学习策略来进行更新，这个过程需要的时间复杂度均为O(N).至于环境选择策略，文中借鉴了NSGA-Ⅲ算法中的相关策略从混合种群Pt′∪Pt(大小为2N)筛选出下一代的新种群Pt+1(大小为N)，这在最坏情况下需要的时间复杂度为O(mN2)或O(N2logm-2N).综上所述，MOPSO-TCOL算法在最坏情况下的总的时间复杂度为max{O(N2logm-2N),O(mN2)}，这与NSGA-Ⅲ算法的时间复杂度是一致的.

3 性能测试与试验结果分析

3.1 试验设置

为了综合评估MOPSO-TCOL的性能，进行了一系列全面且多样化的对比试验.首先，将MOPSO-TCOL与4种目前主流的多目标粒子群优化算法进行了比较，包括MPSO/D、MMOPSO、NMPSO和CMOPSO[1]；然后，将MOPSO-TCOL与4种经典的多目标进化算法进行了对比，包括MOEA/D-M2M、RPEA、NSLS和OSP-NSDE.这些算法都是近几年发表在高质量期刊上的算法，因此对比试验能够充分证明所提出算法在性能上的优势.对比算法的参数设置见表1.

表1 对比算法的参数设置

从2种被广泛应用的测试套件中挑选的14个基准测试函数将被用来测试MOPSO-TCOL的性能，包括ZDT(ZDT1- 4, ZDT6)和WFG(WFG1- 9)，其中ZDT测试函数均为2目标函数，而WFG测试函数为3目标函数.将ZDT1-3、ZDT4和ZDT6的决策变量数设置为30、10和10，将所有WFG测试函数的决策变量数设置为12.

在试验中，所有算法的种群大小设置为100.由于MOPSO-TCOL算法使用了三方竞争机制，因此涉及到进化的粒子数需为3的倍数.文中采用CMOPSO算法中的建议值，将参数λ设置为10.所有的对比算法使用迭代次数作为算法终止条件，在2目标、3目标测试函数上的最大迭代次数分别设置为300、500.所有的对比算法均是在平台PlatEMO[10]上运行，并且每个对比算法在每个测试函数上均独立运行30次.

3.2 算法性能评估指标

文中使用inverted generational distance (IGD)[11]作为算法性能评估指标，该指标能够同时评估算法的收敛性和多样性.算法所获得的IGD值越小，就代表算法的综合性能包括收敛性和多样性越好.IGD

值计算公式如下：

(20)

dist(x*,S)=

(21)

3.3 IGD值比较

表2、3分别列出了4种MOPSO算法和4种MOEA算法与MOPSO-TCOL算法在14个基准测试函数上获得IGD值的平均值和标准差(括号中的是标准差)，其中最优值用黑体标出.此外，还采用了显著性水平α=0.05的Wilcoxon秩和检验来确定对比算法的性能在统计意义上的差异，采用符号“+”、“-”和“=”表示对比算法在统计意义上比MOPSO-TCOL算法更好、更差和相当.

表2 MOPSO-TCOL和其他MOPSO算法在测试函数上的IGD值

由表2可见，MOPSO-TCOL与其他4个对比的MOPSO算法相比在性能上具有明显优势.在所有14个测试函数中，MOPSO-TCOL算法在其中9个基准测试函数上获得了最好的平均值和标准差，而MMOPSO、NMPSO和CMOPSO则分别只在其中1、1、3个测试函数上获得了最好的IGD值，而MPSO/D算法则未获得任何最佳的IGD值.根据Wilcoxon秩和检验统计结果，在14个基准测试函数中，MOPSO-TCOL算法的性能分别在统计意义上在12、11、12、10个函数上优于4个MOPSO算法，这说明MOPSO-TCOL算法相比其他4个MOPSO算法拥有更好的多样性和收敛性.

由表3可见，在与4个最近提出的MOEA算法的对比试验中，MOPSO-TCOL在性能上也具有竞争性的优势.在所有14个测试函数中，MOPSO-TCOL算法在其中11个基准测试函数上获得了最好的IGD值，而RPEA则在其中3个测试函数上获得了最好的IGD值，并且MOEA/D-M2M、NSLS和OSP-NSDE算法在所有14个测试函数中均没有取得任何最佳的IGD值.根据Wilcoxon秩和检验统计结果，在14个基准测试函数中，MOPSO-TCOL算法的性能在统计意义上分别在13、11、14、13个函数上优于4个MOEA算法，这说明MOPSO-TCOL算法相比其他4个MOEA算法也拥有更好的性能.

表3 MOPSO-TCOL和其他MOEA算法在测试函数上的IGD值

续表

3.4 Pareto前沿比较和收敛速度比较

图1、2分别展示了MOPSO-TCOL算法和其他8个对比算法在ZDT3和WFG6测试函数上独立运行30次上获得IGD均值相关的非支配解集在目标空间中的分布.图3给出了IGD值的收敛曲线.

图1 所有算法在ZDT3测试函数上的近似帕累托前沿

图2 所有算法在WFG6测试函数上的近似帕累托前沿

图3 所有算法在ZDT3和WFG6测试函数上所获得IGD值的收敛曲线

ZDT3是一个2目标测试函数，其Pareto前沿是不连通的，从图1可见，只有MMOPSO、CMOPSO和MOPSO-TCOL能完整地收敛到真实的Pareto前沿.WFG6为3目标测试函数且具有球形的Pareto前沿.从图2可见，相比于其他8种对比算法，MOPSO-TCOL算法所得到的非支配解均能更整齐且均匀地分布在真实的Pareto前沿上，这充分说明了三方竞争机制能够有效提升算法的多样性和收敛性，并且能在多样性和收敛性之间保持很好的平衡.而其他算法则无法取得令人满意的效果，例如：MOEA/DM2M、RPEA、NSLS和OSP-NSDE算法均只有少量的解能收敛到真实的Pareto前沿，而MMOPSO、NMPSO虽然也能收敛到真实的Pareto前沿，但分布不是很均匀；MPSO/D算法明显陷入了局部最优；只有CMOPSO和MOPSO-TCOL能取得较好的表现，并且MOPSO-TCOL所获得的非支配解集的分布性明显要比CMOPSO算法更好一些.这也间接说明三方竞争机制能够引导算法较好地跳出局部最优.

为了充分衡量算法的性能，另一个重要的评估指标是收敛速度.图3给出了所有算法在ZDT3和WFG6测试函数上所获得IGD值的收敛曲线.

从图3可见，MOPSO-TCOL在ZDT3和WFG6上均具有最快的收敛速度，它能以很小的IGD值快速收敛到真实的Pareto前沿，即使迭代次数还不够多，而此时其他的对比算法可能还没有完全收敛.这也表明三方竞争机制可以很好地提升算法的收敛速度.

基于以上分析和统计结果可见，所提出的MOPSO-TCOL算法的总体性能要优于其他8种比较算法，这充分证明了三方竞争机制和粒子更新策略的有效性.三方竞争机制可以帮助MOPSO-TCOL获得具有更好多样性的非支配解，而基于反向学习的渐进式粒子更新策略则可以在具有较优多样性的进化环境中充分提升算法的收敛速度和求解精度.

4 结 论

1) 提出了一种基于三方竞争机制的学习策略.该策略能够有效减少算法维护外部存档时的计算成本.同时，允许粒子在空间中进行更广泛的搜索，并有效提升算法的多样性和收敛性.

2) 所提出的基于反向学习的渐进式粒子更新策略可以进一步提升算法的搜索效率、收敛速度和求解精度，同时借助较优粒子良好的反向学习能力，能够有效避免算法陷入局部最优.

3) 试验结果表明，所提出的MOPSO-TCOL算法在基准测试函数上能够产生精度更高且分布更好的非支配解集，且拥有更快的收敛速度.