基于速度交流的多种群多目标粒子群算法研究

刘 彬, 刘泽仁, 赵志彪, 李 瑞, 闻 岩, 刘浩然

(1.燕山大学 电气工程学院, 河北 秦皇岛 066004； 2.燕山大学 信息科学与工程学院, 河北 秦皇岛 066004；3.燕山大学 机械工程学院, 河北 秦皇岛 066004)

1 引 言

科学研究与工程实践中存在很多个互相冲突的目标,多目标优化就是在这些目标中寻找“折中”的方案[1～2]。基于群体搜索的进化方法可以并行处理多个目标函数,适用于求解多目标优化问题。粒子群优化算法(particle swarm optimization,PSO)便是一种基于鸟类觅食行为的群体智能优化算法,其结构简单,参数设置少,收敛速度快,被广泛用于解决多目标优化问题[3]。但粒子群算法在解决多目标优化问题时也面临一些问题：其快速收敛特性易使种群陷入局部最优Pareto前沿；单一的搜索模式易导致粒子收敛精度不高。因此,一些学者对多目标粒子群(multi-objective particle swarm optimization,MOPSO)算法提出了改进：Yang J M[4]等提出自适应混沌MOPSO优化算法,利用一种新型动态加权方法选择全局最优粒子；谢承旺[5]等提出应用档案精英学习和反向学习的MOPSO算法,应用档案精英学习增强算法的全局搜索能力,并使用动态反向学习机制构成变异算子,增加粒子跳出局部最优的可能性。基于单种群的优化算法虽然在一定程度上提高了MOPSO算法性能,但由于算法单一的搜索模式易使每个粒子趋向于种群的“社会部分”,导致解的多样性降低,搜索性能差[6]。有学者提出将算法的单一种群拆分成多个子种群的方法,采用多个种群并行搜索,以提高种群的多样性和算法的收敛能力：刘衍民[7]等提出基于动态多种群的MOPSO算法,采用动态的方法构建多个子种群并行搜索,并用K-均值聚类算法确定子种群的搜索行为,提高粒子的多样性以及跳出局部最优的能力；刘慧慧[8]等提出基于多种群协同的MOPSO算法,将多目标优化问题分解为多个单目标优化问题,每个种群优化一个目标,同时将非劣解存储在外部档案。

基于以上分析,采用多种群的优化算法可以提高粒子的搜索能力,探索更广阔的解空间,因此,本文提出一种基于速度交流的多种群MOPSO算法(research on multi-population MOPSO algorithm based on velocity communication,MVCMOPSO)。算法将单种群划分为多个子种群并引入速度交流机制,子种群间通过速度交流分享信息,使粒子飞向不同的方向,探索更多的未知领域,改善粒子单一的搜索模式,提高粒子全局搜索能力,得到质量更好的解。此外,算法采用混沌映射优化惯性权重,应用到粒子的速度和位置更新,提高粒子搜索的遍历性和全局性。粒子在算法运行后期易出现“聚集”现象,为避免粒子陷入局部最优Pareto前沿,对各子种群执行不同的变异操作,并将算法得到的非劣解存储在外部档案[9]。仿真实验采用多目标测试问题和先进多目标优化算法进行对比,实验结果验证了算法的有效性。

2 多目标优化和粒子群算法

2.1 多目标优化

以多目标最小化问题为例,具有n个决策变量、m个优化目标的多目标问题[10]可以表示为：

(1)

式中：x=(x1,…,xn)∈X⊂Rn为n维的决策向量,X为n维的决策空间；y=(y1,…,ym)∈Y⊂Rm为m维的目标向量,Y为m维的目标空间。目标函数F(x)定义了m个由决策空间向目标空间的映射函数；gi(x)≥0代表q个不等式约束；hj(x)=0 代表p个等式约束。

在多目标优化问题中,并不存在一个能够使所有目标值同时达到最优的解,而是得到一个Pareto最优解集合,在此给出几个常用的重要定义。

定义1(Pareto支配)[11]称决策向量xv=(v1,v2,…,vn)对xu=(u1,u2,…,un)是Pareto支配的,记为xv

定义2(Pareto最优解集)[11]如果P*={x∈Rn|x′∈Rn,x′

定义3(Pareto前沿PF*)[11]Pareto解集在目标函数上的映射为PF*={F(x)|x∈P*},映射之后的集合称为Pareto前沿。

由定义可知,Pareto支配关系决定了多目标优化算法迭代过程中个体的优劣；Pareto最优解集是算法运行结束后所有非支配解集的集合；Pareto前沿是最优解集对应的目标函数映射值的集合。

2.2 粒子群算法

PSO是一种基于群体智能的优化算法,每个粒子由速度和位置2个要素构成[12]。速度决定粒子的飞行方向和运动步长,它的改变会导致位置也发生相应的改变。在第t+1次迭代时,种群中粒子i的速度和位置更新公式为：

vi,d(t+1)=wvi,d(t)+c1r1(pi,d(t)-

xi,d(t))+c2r2(pg,d(t)-xi,d(t))

(2)

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

(3)

式中：w为惯性权重,vi,d(t)和xi,d(t)分别为第t次迭代时粒子i的第d维变量的速度和位置,pi,d(t)和pg,d(t)分别为第t次迭代时粒子i的第d维变量历史最优和全局最优的位置,c1和c2为学习因子,r1和r2为[0,1]区间上均匀分布的随机值。

3 基于速度交流的多种群MOPSO算法

MVCMOPSO算法将单种群划分为多个子种群,采用速度交流机制实现粒子速度信息共享,使粒子不仅能探索更多的未知领域,还会朝着更好的方向进化；加入混沌序列优化惯性权重,进一步提高粒子全局搜索能力；为减少粒子陷入局部最优Pareto前沿的可能性,算法在运行后期对每个子种群实行不同的变异操作。

3.1 多种群速度交流机制

大多数MOPSO算法采用单一种群的搜索模式,所有操作只限定在一个种群中进行,如果个体趋向于一致,算法易陷入局部最优Pareto前沿,导致解的分布性比较差。采用多种群进化能很好地提高粒子搜索能力,降低陷入局部最优的可能性[13]。粒子群算法中的多种群策略大部分是基于粒子间位置信息的共享,很少考虑粒子的速度信息。本文则将速度信息作为种群间的媒介进行信息交换。根据种群间的速度信息交流机制进行子种群的划分,即种群数量固定,速度信息动态交流,从而对子种群进行规划,有效实现子种群搜索领域的分割,从而增强算法的探索与开发能力。速度信息交流机制如图1所示。

图1 多种群速度信息交流Fig.1 Multi-population speed information exchange

MVCMOPSO根据速度交流机制选择合适的种群数量,将单种群等分为4个子种群P1、P2、P3、P4,设定P1和P2为基本子种群,执行标准的PSO搜索行为；P1和P2把各自种群的速度信息分享给子种群P3,进而调整自身种群的运动行为,探索不同于P1和P2的搜索领域；子种群P1、P2和P3再分别将各自种群速度信息分享给子种群P4,以影响子种群P4的搜索行为,使整个粒子群飞向更广阔的解空间。该方法使4个子种群具有各自的搜索行为,改善了粒子单一的搜索模式,既能满足子种群间自由竞争,又可以实现子种群间的信息交流,有效提高了粒子的全局搜索能力。

(4)

(5)

式中：vi,d(t)和xi,d(t)分别为第t次迭代时粒子i的第d维变量的速度和位置,w(t)为采用混沌映射优化的惯性权重。

(6)

(7)

(8)

(9)

为更清晰地解释速度交流机制的运行,以二维最小值目标为例,从4个子种群中各选择一个粒子作为代表,假设分别为x1、x2、x3、x4,对应的任意给定速度分别为v1、v2、v3,如图2(a)所示。算法在第t次迭代时,利用速度交流机制得到的新的粒子速度分别为v1′、v2′、v3′、v4′,对应位置分别为x1′、x2′、x3′、x4′,算法最终目的是使粒子收敛于真实Pareto前沿。算法在第t+1次迭代时,粒子间再采用速度交流机制分享信息后迭代更新如图2(b)所示,更新后的粒子速度分别为v1″、v2″、v3″、v4″,对应位置分别为x1″、x2″、x3″、x4″。由图2可见,粒子间分享速度信息后,相互协调向着不同的方向运动,探索更多的未知领域,快速向真实Pareto前沿靠近,进一步实现全局搜索。

图2 粒子协同进化Fig.2 Particle coevolution

将单种群等分为4个子种群P1、P2、P3和P4并引入速度交流机制,实现了子种群间的速度信息交流,使解空间得到合理有效的搜索规划,改善种群的单一搜索模式,极大地提高了种群的全局探索和开发能力。

3.2 混沌映射优化惯性权重

MOPSO算法常因收敛快速而陷入局部最优,粒子不能有效探索整个解空间。混沌系统具有遍历性、随机性和稳定性的特点[14],为进一步提高算法搜索性能,促进粒子可以在整个解空间进行探索,本文采用混沌映射来优化粒子速度,更新式(4)和式(6)中的惯性权重。利用Logistic映射来产生混沌变量：

zt+1=μzt(1-zt)

(10)

式中：μ为控制参数。设0≤z0≤1,t为当前迭代次数,t=0,1…；μ=4时系统完全处于混沌状态。对于Logistic映射,初值z0不能取0、0.25、0.5、0.75和1这5个值,因为这5个取值都会使序列陷入不动点0或0.75。

利用式(10)优化惯性权重,将优化结果映射到区间[wmin,wmax]中：

w(t)=wmin+(wmax-wmin)zt

(11)

式中[wmin,wmax]为惯性权重的取值范围,一般取[0.4,0.9][15]。

再将优化以后的惯性权重[式(11)]代入式(4)和式(6)中,使粒子具有遍历性,提高粒子全局搜索能力。为说明混沌映射对惯性权重的优化作用,图3给出了惯性权重在100次迭代过程中的取值变化。由图3可见,利用Logistic映射优化的惯性权重数值变化不定(随机性),但是取值在[0.4,0.9]区间(稳定性),使惯性权重尽可能遍历所有取值而又在给定范围内,从而使粒子能够更好地探索解空间。

图3 混沌映射优化惯性权重Fig.3 Chaotic map optimize inertia weight

3.3 多种变异协同操作

算法在运行后期,粒子运动速度逐渐减慢,搜索能力降低,易出现“聚集”现象,陷入局部最优Pareto前沿。为降低粒子在算法后期陷入局部最优的可能性,需添加扰动使粒子能够及时跳出局部最优继续探索。本文利用变异机制对粒子施加扰动,考虑到各子种群的搜索模式不尽相同,以进化代数作为变异的触发条件,对4个子种群同时进行4种不同的变异操作,使粒子分散并飞向不同的方向,进行不同路径的搜索,增大粒子飞向更好解的概率。

设定多种变异触发条件为Lt,当进化代数t

基本子种群P1的搜索模式采用标准粒子群的搜索模式,若使粒子跳出局部最优,变异程度应该大一些。本文选用反向学习变异[16]对粒子施加扰动,使粒子向着反方向进化,变异后的解可描述为：

(12)

基本子种群P2的搜索模式同样采用标准粒子群的搜索模式,因此也宜采用变异程度较大的扰动方式。本文选用高斯变异[17],在原个体位置基础上增加一个高斯分布随机向量,变异后的解可描述为：

(13)

式中Gaussi(0,1)为服从均值为0,方差为1的高斯分布。

子种群P3的速度融合了基本子种群P1和P2的速度信息,从而携带了前两者的变异信息,因此只需进行程度较小的变异即可。本文选用柯西变异[18],使粒子在原位置基础上进行小幅度变化,变异后的解可描述为：

(14)

(15)

子种群P4的速度同时受到P1、P2和P3速度的影响,携带的变异信息比较多,因此宜采用最小的扰动方式。本文选用非均匀变异[19],变异后的解为：

(16)

式中：

UB和LB分别为子种群P4粒子的位置上限和下限;T为最大迭代次数,b为系统参数(决定变异运算的非均匀度)。非均匀变异步长Δ(t,y)是一种自适应调节步长的变异算子,在算法运行后期达到变异触发条件后,搜索半径依概率减小,到算法临近结束仅在当前解的狭小邻域中搜索,这样能够保证对最优解的准确定位,减小从当前邻域中“逃逸”的概率。

不同的子种群采用不同的变异方式,搜索能力也不同,共同协助种群在算法后期跳出局部最优Pareto前沿,飞向不同的方向继续对解空间进行探索。

3.4 算法步骤

MVCMOPSO算法的步骤如下：

Step1：参数初始化：种群大小为4 N,初始化外部档案A(0)=Φ,设置最大容量与种群规模相同为4 N；迭代次数t=0;迭代次数为Gmax；

Step2：初始化4个大小为N的子种群,根据Pareto支配,将非支配解加入A(0),形成A(1)；

Step3：根据拥挤距离,选择每个粒子的全局最优领导粒子：在A(t)中随机选取2个粒子,选择拥挤度距离大的粒子作为全局最优领导粒子；

Step4：令t=t+1,进入循环迭代；

Step5：判断是否达到变异条件：若迭代次数t

Step6：将多种群合并为单种群,并将单种群中的个体与A(t)中的非劣解进行Pareto支配比较,如果不被A(t)中的非劣解支配,则加入到A(t)中,判断A(t)中的解数量是否大于4 N,如果是,则删除拥挤距离小的多余的解；

Step7：根据Pareto支配分别更新子种群粒子历史最优值：若当前解支配历史最优解,则令当前解替代粒子历史最优解；若历史最优解支配当前解,则粒子历史最优解不变,若两者互不支配,则随机选择一个作为粒子历史最优解；更新粒子全局最优解；

Step8：终止条件判定：若t

3.5 计算复杂度分析

假设优化问题含有m个目标,种群大小为4 N,外部档案最大容量为A*。种群函数评价复杂度为O(4mN),拥挤度距离的复杂度为O(mA*logA*)(假设使用快速非支配排序算法),种群和档案进行Pareto支配比较。如果外部档案最大容量与种群数量相同,则MVCMOPSO的计算复杂度为O(16mN2)。

4 仿真验证与分析

4.1 性能评价指标和实验参数设定

为验证本文提出算法的有效性,将MVCMOPSO与NSGA-Ⅱ[20]、SPEA2[21]、AbYSS[22]、MOPSO[11]、SMPSO[23]、GWASF-GA[24]先进算法进行对比。选取ZDT系列测试函数[25]ZDT1、ZDT2、ZDT3、ZDT6,以及Schaffer[26]、Kursawe[27]、Viennet2和Viennet3[28]测试函数进行测试和对比,如表1所示。

表1 多目标优化测试函数Tab.1 Multi-objective optimization test functions

在求解不同多目标优化问题时,通过收敛性和多样性评估指标,验证多目标优化算法的性能。为更清晰定量评价不同的多目标优化算法的性能,选用3个指标IGD[29](Inverse Generational Distance,反世代距离)、GD[30](Generational Distance,世代距离)、SP[31](Spread,分布性)综合评价算法的收敛性和多样性。

1) IGD指标：IGD可用来综合评价算法的收敛性和多样性。IGD指标定义为：

(17)

式中：di为真实前沿PFtrue与得到的Pareto最优解之间最短欧氏距离；n为外部档案中粒子个数。IGD值越小,表明得到解集的收敛性和多样性越好。

2) GD指标：GD可用来评价得到解集的收敛性。GD指标定义为：

(18)

式中：di为外部档案中第i个粒子到真实前沿PFtrue最短欧氏距离,n为外部档案中粒子个数。GD值越小,表明得到解集的收敛性越好。

3) SP指标：SP可用来评价得到解集的分布性,即均匀分布在真实Pareto前沿附近的特性。SP指标定义为：

(19)

对各个算法在同一测试问题上独立运行30次并统计结果,对于两目标测试函数,种群规模设置为100,涉及到应用外部档案的算法,外部档案规模同样设置为100,其他算法实验参数按照对应的参考文献设置。

对于三目标测试函数,种群规模设置为200。多种变异操作触发的迭代次数Lt设为100,迭代次数均为300。

4.2 实验结果分析

7种算法的性能对比结果如表2～表4所示,其中粗体字表示所有对比算法在对应行测试问题中的最优评价指标。

表2 7种算法IGD性能指标的均值结果Tab.2 Mean results of 7 algorithms IGD performance indicators

表3 7种算法GD性能指标的均值结果Tab.3 Mean results of 7 performance GD performance indicators

由表2可知,MVCMOPSO在8个测试问题中获得2个最优IGD值,其中在ZDT2测试问题中明显优于其他算法,NSGA-Ⅱ和SPEA2均获得1个最优值,AbYSS和SMPSO均获得2个最优值。除在ZDT6测试问题中MOPSO比MVCMOPSO取得的效果好,其他测试函数中MVCMOPSO的综合性能均优于MOPSO,说明本文对MOPSO所采取的改进方法是有效的。在ZDT2和Schaffer测试问题中,本文算法均获得了收敛性和多样性最好(IGD值最小)的解,说明算法引入的速度交流机制实现了子种群间的信息共享,使粒子能够在解空间中进行不同区域的搜索,极大地提高了粒子的全局搜索性能。

由表3可知,MVCMOPSO在8个测试问题中获得2个最优GD值,NSGA-Ⅱ和MOPSO均获得1个最优值,SMPSO和GWASF-GA均获得2个最优值。表2中,SMPSO在ZDT3和Kursawe测试问题中均取得了最好的IGD值,表现出良好的优越性,但从表3可得,MVCMOPSO在ZDT3和Kursawe测试问题中的收敛性指标却优于SMPSO,说明MVCMOPSO采用的多种变异协同操作能够协助粒子及时跳出局部最优,使得到的非支配解能更好地收敛于真实Pareto前沿。

由表4的SP评价指标结果可见,本文算法在8个测试问题中获得3个最优值,NSGA-Ⅱ、AbYSS和MOPSO均获得1个最优值,SMPSO获得2个最优值。在解决ZDT1、Schaffer以及Viennet2测试问题中,本文算法获得的解集分布性最好,说明算法采用混沌序列优化的惯性权重,提高了粒子的遍历性,促进粒子能均匀分布在真实Pareto前沿。

表4 7种算法SP性能指标的均值结果Tab.4 Mean results of 7 performance SP performance indicators

为直观展示各算法所得解集的收敛性和分布性,图4和图5给出7种算法在Kursawe(二维非连续)和Viennet3(三维连续)测试函数上的Pareto前沿,图4(a)和图5(a)为测试函数真实Pareto前沿,图4(b)～图4(h)和图5(b)～图5(h)所得Pareto前沿。

由图4可见,在解决Kursawe(二维非连续)测试函数中,SMPSO得到的解收敛性和分布性最好。GWASF-GA得到的解没有均匀分布在非连续前沿的第一段前沿,表现为部分密集部分稀松。

由表4也可知,GWASF-GA的SP指标最大,解集的分布性最差。MVCMOPSO得到的解集能很好地收敛于真实Pareto前沿,且分布均匀,说明算法在解决非连续问题时具有一定的优势,速度交流机制的运用,改善了粒子单一的搜索模式,提高了解的质量。

图4 7种算法在Kursawe测试函数上的对比Fig.4 Comparison of 7 algorithms on Kursawe test function

图5 7种算法在Viennet 3测试函数上的对比Fig.5 Comparison of 7 algorithms on Viennet 3 test function

由图5可见,GWASF-GA在优化Viennet3(三维连续)测试函数时只有部分解收敛于真实前沿,尽管它的GD值是最好的,但它的分布性很差。NSGA-Ⅱ、AbYSS、MOPSO、SMPSO解集分布性良好,只有小部分解没有均匀分布在真实Pareto前沿。MVCMOPSO取得最佳的解集效果,说明算法采取的改进策略有效地提高了待优化函数的解的质量,从而获得收敛性和分布性最好的解。

5 结 论

为更好地权衡多目标粒子群优化算法解集的收敛性和多样性,改善粒子单一的搜索模式,本文提出了基于速度交流的多种群MOPSO算法。结合实验得到如下结论：

1) 将单种群等分为4个子种群P1、P2、P3和P4,并引入速度交流机制,实现了速度信息共享,改善了粒子单一的搜索模式,实现了对解空间不同区域的充分探索,提高了解的全局搜索能力。

2) 采用混沌映射优化粒子惯性权重,应用于粒子速度和位置的更新,提高了粒子的遍历性,使粒子尽可能探索更广阔的解空间。

3) 在算法运行后期,为降低粒子陷入局部最优Pareto前沿的可能性,提出了多种变异协同操作,每个子种群采用一种变异方式,实现不同的路径搜索,协助粒子跳出局部最优获得收敛性和分布性更好的解。

4) 利用不同特征数据验证算法的收敛性和多样性,同时与NSGA-Ⅱ、SPEA2、AbYSS、MOPSO、SMPSO和GWASF-GA算法进行对比,实验结果表明,MVCMOPSO算法能够得到收敛性和多样性更好的Pareto解。