融合扰动策略的多目标粒子群优化算法

王进成,顾银鲁

(银川能源学院 基础部,宁夏 银川 750105)

0 引言

在现实世界中,多目标优化问题广泛存在于工业生产和日常生活中.在多目标优化问题中,由于每个目标之间存在冲突,所以不存在唯一的最优解[1].因此,分析多目标优化问题的目标是找到一组非支配解,而不是单一的解.非支配解称为Pareto解,它们的集合形成了客观空间中的Pareto前沿.此外,在求解多目标优化问题时,有以下3个要求:①尽可能地接近真正的Pareto有效前沿;②尽可能地保持良好的多样性;③尽可能地使粒子分散均匀.目前,出现了许多经典的多目标优化算法.比如Dbe等[2]利用non-dominated sorting提出了NSGA-II,Zitzler等[3]利用强度Pareto支配的思想提出了SPEA2.

粒子群优化算法(Particle Swarm Optimization Algorithm,PSO)是由Kennedy等[4]于1995年提出来的一种群智能算法,它成功地应用于单目标优化.而在实际的工程应用中很多都要解决多目标优化的问题,所以越来越多的研究者已经将其扩展应用到多目标优化.如何选择局部最优和全局最优很重要,而且由于其不可微、不连续、非线性等特点,传统的数学方法已经很难解决此类问题.此时,智能计算方法在该问题中表现出很大的优势.传统的智能算法只是将多目标进行加权,将其转化为单目标,该算法对加权系数的要求较高.因此,PSO算法在各种优化问题中得到了越来越广泛的应用,包括复杂的多目标优化问题[5].用于解决多目标优化问题的粒子群优化算法称为多目标粒子群优化算法(Multi-objective particle swarm algorithm,MOPSO).近年来,研究者通过引入混沌序列[6]和突变[7]来改进MOPSO,有效地提高了算法的搜索性能;文献[8]提出了一种基于类圆映射的多目标粒子群优化算法,提高了种群寻优性能;文献[9]将基于集成学习的两种代理模型分别应用于全局搜索和局部搜索,提出了一种异构集成代理辅助多目标粒子群优化算法,提高了代理模型的搜索能力,减少了评估次数;文献[10]为提高解决多目标优化问题的能力,提出一种改进的多目标粒子群优化算法,实验结果表明,在世代距离GD(Generational Distance)和空间评价方法 SP(Spacing)性能指标上,改进之后的算法与另外几种对等算法相比,具有显著的整体优势.

为进一步增强算法的收敛性及种群多样性,提出了一种融合扰动策略的多目标粒子群优化算法.通过自适应调整粒子参数以及在速度更新公式中增加扰动项,提高了算法的收敛速度;为了增强算法的随机性和多样性,扩大搜索空间,按照某一特定的发生概率对外部档案中的粒子进行维护和扰动.最后,对多目标测试函数进行数值实验,并且与经典的多目标算法NSGA-II、SPEA2和MOPSO对比,结果表明,该算法比其他3种经典的多目标优化算法在GD和SP性能指标上都具有较好的提升.

1 多目标优化问题及基本概念

一般情况下,多目标优化问题(Multi-objective Optimization Problem,MOP)优化两个或两个以上相互冲突的目标,其包含一组目标函数和一些约束条件.一个具有m个目标函数,d个决策变量的多目标优化问题,其数学描述如下:

minf(x)=(f1(x),f2(x),…,fm(x)),

(1)

(2)

以下介绍多目标优化问题中常用的几个基本概念[11-12].

定义1(可行域)在决策空间中,用Ω来表示可行域,其表达式为

(3)

定义2(可行解)对于决策空间中的点x,若x∈Ω,则x为可行解.

定义3(Pareto支配)对于任意向量x1,x2,当且仅当:

∀i∈Rn,fi(x1)≤fi(x2),
且∃j∈Rn,fj(x1)

(4)

则称x1支配x2,记作x1x2.

定义4(Pareto最优解)Pareto最优解也称作非支配解,对于可行域内某一解x*,如果x*不被可行域内任何其他解支配,则称x*为Pareto最优解,其定义如下:

┐∃x∈Ω:xx*.

(5)

定义5(Pareto最优解集,FS)可行域内所有的非支配解组成的集合,称为Pareto最优解集,定义如下:

PS={x*|┐∃x∈Ω:xx*}.

(6)

定义6(Pareto最优前沿,PF)Pareto最优解集对应的目标向量集合为Pareto最优前沿,也称Pareto最优前端或Pareto均衡面,定义如下:

(7)

2 粒子群优化算法

PSO是一种模拟鸟群觅食行为的群智能优化算法,PSO算法的提出激发了许多研究者对群智能优化算法的研究.在PSO算法中,每只鸟都被看作是一个粒子,粒子由gbest和pbest变化来寻找最优解.假设种群规模为N的粒子在D维空间内搜索,粒子的速度和位置更新公式如下:

vij(t+1)=ωvij(t)+
c1r1(gbestj-xij(t))+
c2r2(pbestij-xij(t)),

(8)

xij(t+1)=xij(t)+vij(t+1),

(9)

其中:ω,c1,c2分别表示惯性权重、个体经验系数、社会经验系数,ω由式(10)确定,c1和c2一般取值为2;xi和vi表示第i个粒子的位置和速度;pbesti表示第i个粒子的pbest位置;gbest表示整个种群的gbest位置,在多目标问题上,gbest也被视为非支配解;j为维数;t为当前迭代次数;r1和r2为[0,1]之间的两个随机数.惯性权重ω由下式确定:

ω=ωmax-t*(ωmax-ωmin)/Tmax.

(10)

其中:ωmax,ωmin分别为惯性权重的最大值和最小值,一般取值为0.9和0.4;t表示当前迭代次数;Tmax表示最大迭代次数.

3 融合扰动策略的多目标粒子群优化算法

由于解决多目标问题的最终目标是获得一组均匀分布的非支配解,因此,DSMOPSO算法还需要以下操作.

3.1 外部档案维护策略

用于存储非支配解的集合称为外部档案,它的规模通常跟MOPSO的种群数量是一致的.当非支配解的数量超过外部档案规模时,部分非支配解需要移除.为了进一步提高非支配解的均匀性,根据文献[13]计算粒子的个体密度,计算公式如下:

(11)

其中,PCD(Pi,Pj)表示Pi与Pj之间的平行格距离,计算公式为

(12)

外部档案维护策略具体如下:首先输入待更新的外部档案A、外部档案最大规模K以及进化算法获得新解集P,令B=A∪P,求出B的目标向量值,找出B中的非支配解B′,如果B′中元素的个数B

3.2 个体最优解与全局最优解选取策略

3.2.1 个体最优值选取策略

(13)

3.2.2 全局最优解选取策略

本文采用随机权重的方法将外部档案中的多目标向量转化成单目标,从该权重下随机选取全局最优粒子,具体方法如下:

(14)

(15)

其中,ai为随机产生的权重.

3.3 参数改进策略

众所周知,粒子群优化算法的局部和全局搜索能力很大程度上取决于粒子的三类控制参数.较大的惯性权重可以加强全局搜索能力,较小的惯性权重可以加强局部搜索能力;与社会认知能力相比,较大的自我认知能力将导致粒子在整个搜索空间中搜索,从而加强了算法的局部搜索能力;与自我认知能力相比,较大的社会认知能力将导致粒子进行局部搜索,从而加强了算法的全局搜索能力.

虽然多目标优化的目标通常是获得一组非支配解集,而不是单一的最优解,但如何有效地平衡PSO算法的局部和全局搜索能力,仍然是寻找更好的非支配解集的关键.为了提高粒子群算法的性能,本文提出了一种新的自适应策略,使其能够很好地平衡粒子的局部和全局搜索能力,以找到高质量的非支配解集.其自适应更新公式如下:

ω(t+1)=(ωmax-ωmin)*δ+ωmin,

(16)

c1(t+1)=(c1s-c1f)*δ+c1f,

(17)

c2(t+1)=(c2s-c2f)*δ+c2f,

(18)

(19)

其中,ωmax和ωmin分别为惯性权重的最大值和最小值;c1s和c1f是自我认知参数的初始值和最终值;c2s和c2f是社会认知参数的初始值和最终值;tmax表示最大迭代次数;在自适应策略中,ωmax=0.9,ωmin=0.4,c1s=c2f=2.5,c1f=c2s=0.5,tmax=200.

3.4 扰动策略

通过对粒子群算法中速度更新公式的分析,在算法初期,粒子拥有较大惯性速度,较大的速度会使粒子拥有一个较强的全局搜索能力.在算法后期,粒子趋近最优位置时,粒子速度下降直至为零,很容易陷入局部最优.为了使粒子跳出局部最优,在速度更新公式中添加速度扰动项,不影响算法前期全局搜索,在算法后期确保粒子速度不至于为零,依然给算法一个小速度,有利于增加局部搜素能力,为粒子跳出局部最优提供可能.其更新公式如下:

vij(t+1)=ωvij(t)+c1r1(gbestj-xij(t))+
c2r2(pbestij-xij(t))+a*(t/Tmax)2,

(20)

其中,a为极小的随机数,取值为0.001.

在多目标粒子群算法中,通过算法迭代将不断产生的非支配解都存储到一个外部档案集中,每个粒子的gbest可以从档案中选择,这种选择策略会使处于稠密区域的非支配解有更多的选择机会,从而影响了种群的多样性,容易使算法出现早熟现象.因此,为了使粒子存在多样性以及避免算法陷入局部最优,本文采用以一定的发生概率p对外部存档集进行扰动,以产生新的非劣解,其扰动公式如下:

(21)

3.5 DSMOPSO的步骤及算法流程图

通过以上分析,完整的DSMOPSO算法步骤由上述操作以一定的顺序组成,其具体实现算法步骤如下,流程图如图1所示.

图1 DSMOPSO算法流程图

步骤1:初始化种群中所有粒子的位置和速度;

步骤2:计算每个粒子的目标函数值,保持每个粒子的初始位置和目标函数值;

步骤3:根据式(13)和(14),选择pbest和gbest,构建外部档案;

步骤4:根据式(20)和式(9)更新所有粒子的位置和速度;

步骤5:以一定的发生概率对外部存档集进行扰动,以产生新的非劣解;

步骤6:评价粒子的目标函数;

步骤7:更新粒子的个体最优值,更新粒子的外部档案;

步骤8:判断迭代次数是否满足最大迭代次数,若成立,则转步骤2;否则输出最优结果.

4 仿真实验

4.1 性能指标

(1)世代距离(Generational distance,GD)是估计算法运算求得的Pareto最优解集与真实Pareto前端的趋近程度,定义如下:

(22)

其中:n表示解集中个体的数目;di表示个体i到Pareto真实前端最小的欧几里得距离.di表达式如下:

(23)

GD越小,表明算法得到的Pareto最优解集越逼近真实的Pareto前端,此时算法的收敛性就越好;GD的理想值为0,即算法得到的Pareto最优解在真实的Pareto前端上.

(2)分布均匀度量(Spacing,SP)是用来衡量算法求得的Pareto最优解集中分布性能的好坏.定义为

(24)

(25)

其中,k表示目标函数的个数.

SP的值越小,表明算法得到的解的分布性越好;SP的理想值为0,即算法得到的Pareto最优解在目标空间中是均匀分布的.

4.2 实验分析与对比

为了验证DSMOPSO算法的性能,本文选取经典的多目标测试函数进行数值实验[14-15],并将算法与NSGA-II、SPEA2和CMOPSO算法进行对比,其中CMOPSO表示基于自适应网格的多目标粒子群优化算法.设置种群规模为100,最大迭代次数为300,外部档案集规模为100,分别将算法NSGA-II、SPEA2、CMOPSO、DSMOPSO独立运行30次.测试函数如表1,实验都是在win7系统matlab 2012a中完成的,电脑配置为Intel(R) Core(TM) i5-3317U CPU @ 1.70GHz.

表1 测试函数

各个算法在7种测试函数上所得关于GD指标和SP指标的统计结果见表2、表3.除了DTLZ2、DTLZ4测试函数,DSMOPSO算法对其它5种测试函数都具有较好的收敛性和均匀性.并且明显优于NSGA-II、SPEA2和CMOPSO算法.对测试函数DTLZ2、DTLZ4,DSMOPSO算法所得结果显著优于NSGA-II算法.综上所述,DSMOPSO算法在收敛性和均匀性方面都有所提升.

表2 4中算法7种测试函数上的GD指标比较结果

表3 4中算法7种测试函数上的SP指标比较结果

各种算法在每个测试函数上所得的Pareto前沿如图1-图6所示,从图1-图4可以明显看出,DSMOPSO算法所得的Pareto前沿要比NSAG-II、SPEA2和CMOPSO算法所得结果要好;对测试函数ZDT6,4种算法都具有较好的均匀性,但有部分偏离了真实的Pareto前沿;对测试函数DTLZ2和DTLZ4,DSMOPSO算法所得的Pareto前沿的均匀程度较差.

图1 ZDT1的测试对比

图2 ZDT2的测试对比

图4 ZDT4的测试对比

图5 ZDT6的测试对比

5 结语

针对无约束多目标优化问题,本文提出了一种融合扰动策略的多目标粒子群优化算法.通过自适应调整粒子的参数以及在速度更新公式中增加扰动项,有效地提高了算法的收敛速度.在算法后期,按照某一特定的发生概率对外部档案中的粒子进行扰动,增强了算法的随机性和多样性,并且找到了更多的非支配解.最后,通过测试函数验证了DSMOPSO算法在收敛性和多样性方面都有很大的改善,能有效地解决多目标优化问题.