基于余弦距离的多目标粒子群优化算法

方欣欣,龚如宾,李大为

(上海理工大学 光电信息与计算机工程学院,上海　200093)



基于余弦距离的多目标粒子群优化算法

方欣欣,龚如宾,李大为

(上海理工大学 光电信息与计算机工程学院,上海200093)

摘要针对粒子群优化算法具有的个体分布不均匀以及重复个体较多等缺陷,提出了一种基于余弦距离的多目标粒子群优化算法,该算法根据外部精英存储策略,利用余弦距离排挤机制来选取最分散的粒子,扩大 Pareto最优解集的收敛性和多样性,增强算法的全局寻优能力。通过采用标准多目标优化问题ZDTl～ZDT3进行仿真实验与粒子群算法、混沌粒子群算法、基于拥挤距离的多目标优化算法对比表明,该算法在Pareto前沿的收敛性和多样性方面均优于基于拥挤距离排挤机制,并具有较高的效率。

关键词余弦距离;拥挤距离;多目标优化;粒子群;非支配解

Multi-objective Particle Swarm Optimization Algorithm Based on Cosine Distance

FANG Xinxin,GONG Rubin,LI Dawei

(School of Optica1-Electrical & Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China)

AbstractA multi-objective particle swarm optimization (PSO) algorithm based on cosine distance is proposed to tackle the drawbacks such as uneven individual distribution redundant overlapping individuals existing in standard particle swarm optimization.Based upon external elite storage strategy,this algorithm utilizes cosine distance crowing mechanism to select the most widely distributed particles.It amplifies the convergence and diversity of best solution set and strengthens the capacity of global optimization.Standard multi-objective optimization ZDTl~ZDT3 are adopted in simulation experiments to compare the proposed algorithm with the particle swarm optimization,chaos particle swarm optimization and multi-objective optimization algorithm based on crowing mechanism.Results show that the proposed algorithm not only outperforms other algorithms in terms of Pareto’s frontier convergence and diversity but also obtains preferable efficiency.

Keywordscosine distance;crowding distance;multi-objective optimization;particle swarm;non-dominated solutions

在科学研究和工程实践中,常会遇到多目标优化问题,如旅行商[1],多播路由[2],车间调度[3]等。解决多目标问题(Multi-Object Problem,MOP)的方法一般分为两类:第一类统称为“目标归一法”[4],这类求解方法按某种策略确定多个目标之间的权衡方式,将多目标问题转换为单目标优化问题,并用这些单目标优化问题最优解构成的解集去近似MOP的Pareto最优集。该类方法包括权值法、约束法、目标规划法等。运用该类方法需要事先已知目标信息,从而在目标之间建立联系,因此在求解许多工程问题上具有极限性。第二类是多目标进化算法(Multi-Object Evaluation Algorithm,MOEA),MOEA 无需事先充分了解各目标的详细信息,而是在搜索空间内获得一组Pareto最优解来权衡各个目标。近年来,越来越多的学者研究并广泛应用MOEA算法,具有代表性的有多目标模拟退火算法、 多目标蚁群优化算法、 多目标粒子群算法等[5]。

粒子群优化算法(Particle Swarm Optimization,PSO)是一种群体智能算法,来源于对鸟群或鱼群觅食行为的模拟。适合求解多目标优化问题[6]。多目标优化算法需保证Pareto前沿的收敛性和多样性特征,因此合理的Pareto解集多样性维持策略和粒子群全局最优值更新操作是关键[7]。当前在多目标粒子群优化算法的研究中,为扩大Pareto解集的多样性,大部分采用拥挤距离排挤机制。当前的研究主要参考NSGA-II[8]算法中的拥挤距离机制代替多目标粒子群优化算法(Multi-objective Particle Swarm Optimization,MOPSO)算法中粒子位置更新策略。杨善学[9]引用了NSGA-II中的拥挤距离,计算出外部档案中非支配解的拥挤度,采用竞标赛选择法,选出每个粒子的全局最优位置,从而引导每个粒子向处于较稀松区间的非支配解搜索,提高解的多样性。李中凯等[10]基于拥挤距离值,引入文化进化框架,从精英知识和条件知识中选择处于最分区域的粒子。魏武等[11]引进拥挤距离排序方法维护外部精英集和更新全局最优值,通过采用小概率变异机制来保持非劣解的多样性。

以上大部分文献主要参考NSGA-II算法对Pareto解集分布性在拥挤距离排挤机制的基础上作改动,由于拥挤距离排挤机制存在不稳定性,导致解集分布性不好,而在此基础上的改进方法并不能消除这个缺点,后续优化也存在不稳定性。本文对拥挤距离排挤机制的缺陷进行深入的分析,引入余弦距离排挤机制来选取最分散的粒子,扩大 Pareto最优解集的收敛性和多样性,增强算法的全局寻优能力。

1多目标粒子群优化算法概述

1.1多目标优化问题描述

多目标优化问题中以一个求目标的最小值为例可以描述为

(1)

式中,x=(x1,…,xn)∈X⊂Rn为n维决策变量;X为n维决策空间,y=(y1,y2,…,ym)∈Y⊂Rm为m维目标向量;Y为m维目标空间;F(x)定义了由决策空间向目标空间的映射关系;g(x)和h(x)分别为q个不等式约束条件和p个等式约束条件。在非支配解集中决策者只能根据具体问题选择最适合的一个非支配解作为最终解。

定义1对于∀x∈X,若满足式(1)的约束条件gi(x)<0,i=1,2,…,q和hj(x)=0,j=1,2,…,p,称x为可行解。

定义2对于X中所有可行解构成的集合记为Xf,满足Xf∈X

定义3若xk,xl∈Xf为满足式(1)的两个可行解,称xkPareto支配xl当且仅当满足式(2)和式(3)两个条件,记为xk≻xl。

∀i=1,2,…,m,fi(xk)≤fi(xl)

(2)

∃j=1,2,…,m,fj(xk)

(3)

定义4若x*∈Xf为Pareto最优解(非支配解),当且仅当满足∃x∈Xf,x*≻x。

定义5所有Pareto最优解x*的集合构成Pareto最优解集(非支配解集),记为P*。

1.2粒子群优化算法(PSO)

粒子群优化算法(PSO)是一种模拟群聚生物的行为而得到的群聚智能算法[12]。该算法中,粒子就相当于解空间的其中一个解,其的飞行状态随自身的飞行经验和同伴的飞行经验而改变,每个个体相当于搜索空间中以一定的速度飞行的一个没有体积没有质量的粒子。

粒子群算法的数学模型描述如下:设有m维搜索空间和N规模的粒子群。在第t代,第i个粒子在搜索空间的位置可表示为Xi(t)=(Xi1,Xi2,…,Xim);局部最优位置Pi(t)是指第i个粒子在m维搜索空间中的历史最优位置;全局最优位置Gi(t)是指整个粒子群的所有粒子在m维搜索空间中的历史最优位置;第i个粒子的速度定义为Vi(t)。每个粒子将按照式(4)和式(5)来更新自己的位置和飞行速度[11]

Vi(t+1)=wVi(t)+c1r1(Pi(t)-Xi(t))+c2r2(Gi(t)-Xi(t))

(4)

Xi(t+1)=Xi(t)+Vi(t+1)

(5)

其中,c1,c2为正常数,称为学习因子;ω是惯性因子;r1,r2是[0,1]间的随机数;设速度变化范围为[vl,vu],粒子的第i个分量的位置变化范围为[pl,pu],在迭代过程中,若该粒子的位置和速度超过了其取值边界范围,则取其边界值。

2多目标粒子群优化算法的改进

2.1基于拥挤距离的缺陷分析

为有效处理约束,采用改进的Pareto最优解不断“排挤”不满足约束条件的解,从而使最后得到的最优解满足约束条件,在NSGA-II算法中拥挤距离是用来估计一个解周围其他解的密集程度。对于每个目标函数,首先采用精英选择策略进行分层排序,结果每个个体均会处于某个层级上,统一层级上与该个体相邻的前后两个个体在各个子目标方向上的距离之和定义为拥挤距离。计算所得拥挤距离越小,则所得的解越密集,其多样性越小,反之说明所得解越稀疏,多样性越大。最后根据计算所得拥挤距离的大小对粒子重新进行降序排列。

如图1所示,X和Y为问题域的两个子目标,个体i的拥挤距离D[i]即图中虚线四边形的长与宽之和。即

(6)

当有K个目标时

(7)

其中,fn(i)为个体i在第n个目标上的适应度值。

图1　拥挤距离计算方法

在NSGA-II算法中,拥挤距离大的个体周围的分布性较好,更有可能被选择;反之,拥挤距离小的个体被淘汰的概率更大。拥挤距离策略的优点是保持种群的分布均匀,解集具有较好的多样性,但该策略存在以下局限性:如图2所示,个体a和个体b的拥挤距离近似无穷大,被拥挤距离策略保留的概率较大。但其代表极端偏向目标Y或X的情况,虽对单目标的适应度较好,但对其他目标的适应度过差,应将其淘汰;个体c和个体d的拥挤距离相同,在精英保留策略中会同时被淘汰或保留。但实际上个体c和个体d距离接近,只需保留一个;在第n+1层上,个体e的分布情况比f好,被保留的概率较大。但从全局考虑,结合第n层级可发现,e周围的个体远比f周围紧密。

由以上分析可知,在拥挤距离策略中存在以下缺陷:(1)极限个体易被保留下;(2)好的个体可能被淘汰而差个体可能会被保留;(3)基于单个层级的拥挤距离考虑欠缺完整性,不能保证在全局的分布。

图2　拥挤距离排挤机制的缺陷分析

2.2余弦距离的引入

每个粒子的全局最优位置不仅决定非支配解的分布,且影响算法的收敛性。基本的多目标粒子群算法基于存档策略,而本文采用一种基于外部档案的方案来存储整个迭代过程中产生的非支配解,从外部档案中随机选择每个粒子全局最优位置,按这种策略选择的大多数是处于稠密区域的非支配解,这样带来种群的多样性的损失,会导致算法陷入局部最优或提前收敛。为确保解的多样性和非支配解分布的均匀性,应使粒子向空间中非支配解相对少的区域搜索。因此,引入了一种基于余弦距离的排挤机制。

余弦距离度量机制在文本分类领域有着广泛的应用。文本空间和多目标空间均属于多维空间,具有一定相似性,在这种启发下,文中将余弦距离度量机制应用到多目标优化算法中,个体的每个目标可看作是向量的一个维度,相应的可建立表示该个体的目标向量,利用目标向量之间的余弦距离,确定个体之间的密集度关系。

假设多目标优化问题中有n个目标:(D1,D2,…,Dn),每个目标都有确定的目标函数。设种群规模为m,对种群内第i个个体,其目标函数值为(Vi1,Vi2,…,Vin)。由于不同目标函数之间的数量级差异可能较大,若直接用函数值计算余弦距离,就不能平均反应出每个目标的特性,所以必须求出个体i的每个目标函数之间的权重比

(8)

其中,Vki是个体i在目标维度k上的实际函数值;ωki为计算获得个体i的目标维度k与所有目标的权重比。

得到个体i的目标向量di=(ωi1,ωi2,…,ωin),根据余弦公式可得两个目标的余弦距离为

(9)

两个目标向量之间的夹角为

〈di,dj〉=arccos(cos(di,dj))

(10)

2.3余弦距离排挤机制

余弦距离排挤机制的主要思想是用目标向量之间的夹角值作为评价个体密集度的主要参数。不失一般性,为方便讨论,选择两个目标x、y进行描述。

步骤1首先计算每个个体在x、y两个目标上的函数值,根据该目标的函数值对每个个体进行分层,保证每层个体相对于下一层都是Pareto非支配解。

步骤4对每个夹角进行降序排序之后,根据预设的临界夹角,分别比较临界向量与单目标向量X和Y的夹角,淘汰极端个体的向量。

2.4加速因子的选取

粒子的搜索过程主要包括全局搜索和局部搜索,若全局搜索较强,则易忽略局部的最优值,而若局部搜索过强,又易使粒子陷入局部最优。因此,在调整参数的过程中,需尽量避免出现两种极端状况,以保证得到最优的Pareto解集。

在式(4)中,c1r1(Pi(t)-Xi(t))为局部认知部分,初期较大的c1值可增强粒子群的局部搜索能力,c2r2(Gi(t)-Xi(t))为社会认知部分,后期较大的c2值能增强粒子群的全局搜索能力。

为平衡粒子在搜索空间中的探测和开发能力,保证粒子的全局寻优能力。c1按照式(11)在2～1范围进行线性递减,c2按照式(12)在1～2范围线性递增

(11)

(12)

其中,currentGen为当前迭代次数,MaxGen为总迭代次数。

2.5外部精英种群的存储策略

多目标粒子群优化算法的关键是如何确定每个粒子的全局最优位置,因其不仅影响算法的收敛性,还对非支配解的多样性起决定作用,在此采用外部精英种群存储策略,将整个迭代过程中产生的非支配解存储于一个外部精英种群中,每个粒子的全局最优位置从外部精英种群中随机选择。

2.6局部最优和全局最优选择策略

设在一次迭代中外部精英种群中的粒子已按余弦距离降序排列,去除极端粒子后,对于个体i的局部最优位置有

(13)

而全局最优值Gbest的选择与局部最优值类似。选取的Gbest应处于Pareto前沿最分散的区域,所以本文选择余弦距离最大的粒子最为全局最优。

3实验与结果分析

3.1多目标优化测试的性能指标

为更加准确的说明两种算法的分布度差异,本文中主要采用Schott在文献[13]中提到的分布性评价方法对两种算法的结果进行定量分析。

(1)非支配解在目标空间上的分布范围SP,定义为

(14)

(2)最大散布范围D,定义为

(15)

表示测量空间中Pareto解集中的两个极值解的距离,反映所得非支配解的散布范围D越大,所获得解的范围越广。

3.2实验对比分析

为评价本文改进的粒子群算法性能,选取3个测试函数对本文算法进行验证。这3个测试函数是Deb在文献[14]中提出的经典ZDT系列函数,其真实Pareto解集曲线分别为凸型、凹型和非连续型,具有一定的代表性。实验中对比PSO、CPSO(Chaos Particle Swarm Optimization)、基于拥挤距离的MOPSO算法,4种算法均采用实数编码方式,参数设置如下:种群规模为100,进化代数为100,被评价的个体为种群规模和进化代数的乘积,即10 000个,惯性权重取0.5,加速因子按照上文策略选取。测试函数ZDT1~ZDT3表达式如下:

ZDT1:

(16)

m=30;0

ZDT2:

(17)

m=30;0

ZDT3:

(18)

m=30;0

图3～图5分别展示了两种算法在ZDT1、ZDT2和ZDT3上的对比实验效果。从图像对比中可看出,本文的改进算法比PSO、CPSO、基于拥挤距离的MOPSO算法具有更好的分布性。

图3　ZDT1的测试曲线

图4　ZDT2 的测试曲线

图5　ZDT3 的测试曲线

从表1和表2的30次实验对比结果可看出,本文所得ZDT1~ZDT3的平均SP值均较小,D值均较大,本文改进算法与基于拥挤距离的MOPSO算法在解集的分布性上相比具有较大的分散性[15-16]。

表1　测试函数ZDT1-ZDT3的SP值结果对比

表2　测试函数ZDT1-ZDT3的D值结果对比

4结束语

本文在现有多目标粒子群算法基础上提出了一种基于余弦距离机制的多目标粒子群优化算法,该算法可提高粒子群的全局搜索能力和局部搜索能力,使粒子群搜索到的非支配解更逼近真实的Pareto前沿,扩大了Pareto最优解集的收敛性和多样性,增强算法的全局寻优能力。通过实验结果分析,与PSO、CPSO、基于拥挤距离的排挤机制MOPSO算法进行比较,证实本文的算法在Pareto前沿的收敛性和多样性方面均优于PSO、CPSO、基于拥挤距离排挤机制,具有较高的效率。

参考文献

[1]Wang B,Hou C.Multicast routing and its qos extension:problems,algorithms and protocols[J].IEEE Network,2000,14(1):22-36.

[2]ZhongW,ZhangJ,ChenW.Anoveldiscreteparticleswarmoptimizationtosolvetravelingsalesmanproblem[C].Singapore:IEEE:CongressonEvolutionaryComputation,2007.

[3]王凌,刘波.微粒群优化与调度算法[M].北京:清华大学出版社,2008.

[4]GuanZ.Operatorsanalyzingofthenodominatedsortinggeneticalgorithm(NSGA)[J].JournalofIndustrialEngineeringManagement,2004(1):56-60.

[5]肖晓伟,肖迪,林锦国,等.多目标优化问题的研究概述[J].计算机应用研究,2011,28(3):805-808,827.

[6]唐贤伦.混沌粒子群优化算法理论及应用研究[D].重庆:重庆大学,2007.

[7]李娟,杨琳,刘金龙,等.基于自适应混沌粒子群优化算法的多目标无功优化[J].电力系统保护与控制,2011,39(9):26-31.

[8]KalyanmoyD,AgrawalS,PratabA,etal.Afastelitistnon-dominatedsortinggeneticalgorithmformulti-objectiveoptimization,KanGALreport200001[R].Kanpur,India:IndianInstituteofTechnology,2000.

[9]杨善学.基于拥挤距离的多目标粒子群算法[J].计算机工程与应用,2009,45(22):24-26.

[10]李中凯,李艾民,朱真才.拥挤距离排序的多目标文化粒子群优化算法[J].控制与决策,2012,27(9):1406-1410.

[11]魏武,郭燕.基于拥挤距离的动态粒子群多目标优化算法[J].计算机工程与设计,2011,47(4):1422-1425.

[12]黄少荣.粒子群优化算法综述计[J].计算机工程与设计,2009(8):1977-1980.

[13]KennedyJ.Theparticleswarm:socialadaptationofknowledge[C].Berlin:EvolutionaryComputation,1997.

[14]SantanaRA,PontesMR,Bastos-FilhoCJA.Amultipleobjectiveparticleswarmoptimizationapproachusing[J].IEEETransactionsonComputerScience,2011,39(2):1511-1519.

[15]Crowdingdistanceandroulettewheel[C].Nanjing:NinthInternationalConferenceonIntelligentSystemsDesignandApplications,2009.

[16]DebK,PratapA,AgarwalS,etal.Afastandelitistmulti-objectivegeneticalgorithm:NSGA-II[J].IEEETransactionsonEvolutionaryComputation,2002,6(2):182-197.

中图分类号TP301.6

文献标识码A

文章编号1007-7820(2016)03-048-06

doi:10.16180/j.cnki.issn1007-7820.2016.03.012

作者简介:方欣欣(1989—),男,硕士研究生。研究方向:人工智能。龚如宾(1963—),男,教授。研究方向:多媒体视觉等。

收稿日期:2015- 08- 15