粒子群算法在多目标优化中的应用综述

第30卷第3期

2009年9月渤海大学学报(自然科学版)JournalofBohaiUniversity(NaturalScienceEdition).30No.3VolSep.2009

粒子群算法在多目标优化中的应用综述

薛洪波,伦淑娴

(渤海大学信息科学与工程学院,辽宁锦州121013)

摘　要:粒子群优化算法是一种基于群体智能的全局随机寻优算法。的个体最优解和粒子群体的全局最优解来完成更新优化。的应用。本文主要论述了多目标PSO约束优化的基本思想目标优化中的未来发展方向。

关键词:多目标;粒子群;约束优化;中图分类号:TP311:A:167320569(2009)0320265205

0、相互影响的多个目标组成。人们会经常遇到使多个目标在给定区域上同时尽可能最佳的优化问题,也就是多目标优化问题。优化问题存在的优化目标超过一个并需要同时处理,就成为多目标优化问题(MultiobjectiveOptimizationproblem,简称MOP)。多目标优化问题的结果不是单个解,而是一组均衡解。MOP并不是简单的将多目标优化中的不同的优化目标根据权重组合成一个复合指标函数,然后按单目标线性优化问题处理。实际生活中很难确定各个优化目标的相对权重,更希望多个目标能相互协调。

20世纪80年代中期,人们开始将演化计算应用于多目标优化中,形成了多种多目标演化算法,其中一些已成功应用于工程实践中,从而形成了一个新的热门研究领域。由于多目标优化问题不存在惟一的全局最优解,所以求解多目标优化问题实际上就是要寻找一个解的集合(Pareto最优解集)[1]。1995年,美国心理学家Kennedy和电气工程师Eberhart提出了粒子群优化算法[2]。粒子群算法也是基于群体的随机优化算法,在很多情况下,比遗传算法更有效率,所以PSO算法在多目标优化问题中的应用是一个很有意义的研究方向。近些年,已有一些基于PSO算法求解多目标优化问题的算法被提出,如Hu等应用了动态邻近的PSO算法[3],和Parsopoulos等应用了权重聚合的方法来求解多目标优化问题[4]。本文对粒子群算法在多目标约束优化上的应用做了详细的阐述,并介绍了多目标PSO约束优化算法的基本原理和实现的流程,并展望了PSO算法在多目标优化中的未来发展方向。

1　多目标优化问题的描述一般情况下,多目标优化问题的各个子目标是相互冲突的,一个子目标的改善有可能会引起另一个子目标的降低,也就是,要同时使多个子目标一起达到最优值是不可能的,而只能在它们中间进行协调和折衷处理,使各个子目标都尽可能地达到最优化。与单目标优化问题的本质区别在于,多目标优化问

收稿日期:2009207216.

基金项目:辽宁省自然科学基金(No:20072199)和中国博士后科学基金(No:[1**********]).

作者简介:薛洪波(19822),男,研究生,从事控制理论与控制工程研究.

266渤海大学学报(自然科学版)第30卷题的解并非唯一,而是存在一组最优解集合,集合中的各个元素称为Pareto最优解或非劣最优解。

法国经济学家帕雷托(VilfredoPareto)首次提出向量优化的概念,也即Pareto最优解。所谓的Pareto最优解,就是一个解可能在其中某个目标上是最好的,但在其他目标上是最差的,不一定有在所有目标上都是最优的解。Pareto最优解集内的元素就所有目标而言是彼此不可比较的。它们的地位是等同的。具体的多目标约束优化问题数学形式可以描述为:

　　　　　　miny=f(x)={f(x1),f(x2),f(xm)}

　　　　　　s.t.g(x)={x gi(x)≤0,i=1,

2,p}

　　　　　　x=(x1,x2

,∈X,y=(y1,y2

,yn)∈Y

式中x为决策向量,y为目标向量,gi(x)为第i个约束,X是决策向量形成的决策空间,Y是目标向量形成目标空间。gi(x)≤0确定了可行解集。m个目标函数、p文字描述是,一般MOP由n个决策变量参数、

个约束条件组成,决策变量与目标函数、约束条件是函数关系。xn)

2　粒子群优化算法

,粒子群由n个粒子组成,每个粒子的位置xi。每个解都可以想象成搜索空间上的一个点,,,并且知道自己到目前为止best。除此之外,每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置g,是在所有pbest中的最优值。

下面介绍其数学描述,每个粒子i包含为一个D维的位置向量xi=(xi1,xi2,,xiD和速度向量vi

,piD),在每次=(vi1,vi2,,viD),粒子i搜索解空间时,保存其搜索到的最优经历位置pi=(pi1,pi2,

迭代初,根据自身惯性和经验及群体最优经历位置pg=(pg1,pg2,,pgD)来调整自己的速度向量以调整自身位置。c1,c2为正常数,称之为加速因子。r1,r2为[0,1]中均有分布的随机数。w是惯性权重因子。每个粒子的位置变化按如下公式进行:

　　　　　　xid=xid+vid

　　　vid=wvid+c1r1(pid-xid)+c2r2(pgd-xid)。

式中d为D维中的维数。

3　多目标PSO约束算法

将粒子群优化算法运用于优化问题,关键是如何确定每个粒子的最优位置gbest和群体全局最优位置pbest。对于单目标优化问题解决方法很直接,每个粒子的最优位置由该粒子的历史最优位置决定,全局最优位置由当时群体中的全局最优位置决定。但对于多目标优化问题,由于并无单个的最优解,所以不能直接确定gbest,pbest。

相对于传统的多目标优化方法,PSO算法在解决多目标优化问题上具有很大的优势。第一,它的高效搜索能力有利于得到多目标意义下的最优解。第二,它通过代表整个解集种群,按并行方式同时搜索多个非劣解,也即搜索到多个Pareto最优解。第三,PSO算法的通用性比较好,适合处理多种类型的目标函数和约束,并且容易与传统的优化方法结合,从而改进自身的局限性,达到更高效率的解决问题。

PSO算法在处理多目标约束优化问题时,主要是解决群体和自身最佳位置,对于群体最佳位置的选择,一是要求算法收敛速度好,二是所得到的解要在Pareto边界上具有一定得分散性。对于自身最佳位置的选择要求是通过较少的比较次数达到非劣解的更新。PSO算法在处理约束时,多采用惩罚函数法。Parsopoulos等人提出利用惩罚函数作为粒子适值[5],使得PSO能够解决多目标约束优化问题。

　第3期薛洪波,伦淑娴:粒子群算法在多目标优化中的应用综述267

3.1　PSO约束优化处理方法

约束优化处理的是等式和不等式或者单个约束组成的优化问题。问题的解既要符合约束条件又要达到目标函数的要求。粒子群算法求解约束优化问题的关键在于如何处理约束条件。解决约束优化问题的常规方法一般分为两种途径:一种是改进无约束问题的方法,使它能够用于求解有约束的情况。另一种是把有约束问题转化为无约束问题,再用无约束问题的方法求解。

通常的处理方法是采用惩罚函数法,其基本思想是把约束问题转化为一个或一系列无约束问题。本质上是通过惩罚不可行解将约束问题转化为无约束问题进行求解的方法[6],关键是如何设计一个罚函数p(x),有效地引导搜索达到解空间的最优区域。不可行解和解空间中可行区域的关系,在惩罚不可行解中起到关键作用,不可行解的惩罚值相应于某种测度下的不可行性的测量。具体是通过惩罚不可行解,将约束问题转化为无约束问题。一般采用加法形式的带惩罚项的评估函数,eval(x)=f(x)+

[7]Mp(x),f(x)是目标函数,M>0是常数,称作惩罚因子。

3.2　多目标粒子群约束优化的流程

多目标粒子群约束优化的算法流程同标准PSO8][]群约束优化的流程如下[10]:

(1)初始化粒子群,种群大小为N,xi,vi。

(2)分别计算各个子目标函数值。

(3)(4)PiPg(5),进行比较,选择新的最佳。

(6)vid=wvid+c1r1(pid-xid)+c2r2(pgd-xid)

　　　　　　　　　xid=xid+vid

更新粒子速度和位置,若粒子的某一维超过边界,则重新随机初始化此维数据。

(7)筛选当前粒子群中的非劣解,并加入精英集中,并剔除精英集合中的劣解。

(8)是否满足终止条件,满足,退出,否则返回步骤(2)。

最终精英集即为PSO算法所得非劣解集,也即我们所需要达到的目标。

4　PSO在优化中的应用

目前,粒子群算法在很多领域得到了广泛的应用,用PSO算法解决实际问题已成为当今一个热点。PSO算法的多目标优化应用在以下一些领域得到广泛应用:

4.1　化工领域

[11]CostaJr等利用PSO算法求解苯乙烯聚合反应的最优稳态操作条件,有效地解决了多目标优化

[12]问题。Ourique使用PSO算法来估计在化工动态多目标模型中产生不同动态现象的参数区域,提高了

动态分叉分析速度。

4.2　电力系统领域

[13]Kannan等将PSO算法应用于最低成本发电扩张GEP问题,结合了罚函数法的PSO算法有效地

解决了多目标带有强约束的组合优化问题。王云等将PSO算法用于电力系统的多目标无功优化[14],有效地解决了电网的电压稳定问题。Gaing利用PSO算法有效地解决了满足发电机多目标约束的电力系统经济调度问题[15]。

4.3　经济领域

[16]Nenortaite等利用PSO算法和神经元网络解决了最大利益的股票交易决策多目标优化问题。刘

志东等人把PSO算法应用到油田多目标模型的求解中[17],大大降低了求解计算量。

4.4　图象处理领域

268渤海大学学报(自然科学版)第30卷

[18][19]Caorsi等利用基于PSO算法的微波图象法来确定电磁散射体的绝缘特性。Yin应用Kennedy

等的离散PSO算法处理了多边形的多目标近似问题[20]。丁艳等人将粒子群算法应用到多阈值图象分割中[21],有效地解决了多阈值图象的多目标优化搜索问题。

4.5　生物信息领域

[22]Xiao等利用PSO算法和基于自组织映射的混合聚类方法来解决基因多目标聚类问题。丛琳等

人利用PSO算法求解正交免疫克隆多目标优化问题[23],得到了理想的Pareto最优解。

4.6　数据挖掘领域

段晓东等将PSO算法应用于多目标数据分类规则挖掘,对数据集进行分类规则挖掘[24]。

4.7　神经元网络训练

[25]Engelbrecht等利用PSO多目标优化算法来训练神经元网络。Messerschmidt等利用基于PSO

算法的神经元网络来预测TicTacToegame树叶节点的状态[26],有效的解决了存在的多目标优化问题。5　结语与展望

,。算法与技术方面的研究较少,尤其本身的工作原理、,算法中位置和。应用方面大多是函数优化问题,。

。(1)参数选择与优化。23个部分:惯性部分、社会部分和自身部分在搜索中的作用。,使得算法既能避免早熟又能比较快速地收敛,对工程实践有着重要意义。

(2)粒子群拓扑结构。不同的粒子群邻居拓扑结构是对不同类型社会的模拟,研究不同拓扑结构的适用范围,有利于PSO算法的推广和应用,例如星形连接,环形连接等。

(3)算法的理论研究。注重对算法的收敛速度、参数鲁棒性、收敛性等相关方向研究,包含在多目标、约束条件等环境下的探讨。

(4)算法的应用研究。PSO算法现大量用于连续、单目标优化问题中,但实际优化问题多是多目标、离散的,因此应向此方向上多研究。

(5)与其他多目标优化算法的融合。尝试粒子群算法与遗传算法、神经网络、蚁群算法等相结合,取长补短,来提高算法的自身性能。

(6)在数据挖掘中的应用。随着科学技术的飞速发展,许多领域的大量数据以各种方式存储下来,我们要从这些大量的数据中挖掘出有用的数据,将粒子群算法应用于其中,可以快速、有效的解决数据分类问题。

(7)PSO算法应用到自动化制造业领域。制造业企业中的工艺路径规划问题是企业自动化的难题之一,它直接影响CAPP,CAD及CAM系统的集成。如果将大量的工艺规划经验组成专家系统,再利用相应的模糊控制规则和PSO算法训练人工神经网络,自动生成工艺路径,有效的解决了制造业中的难题。参考文献:

[1]VilfredoPareto.CoursD’.F.Rouge,Lansanne,1896.EconomiePolitique,volumeIandII

[2]J.Kennedy,R.Eberhart,Particleswarmoptimization[C].Proc.IEEEInt.Conf.onNeuralNetworks,Perth,Australia,1995:1942-1948.

[3]XHu,RCEberhart.Multiobjectiveoptimizationusingdynamicneighborhoodparticleswarmoptimization.

EvolutionaryComputation(CEC2002),Honolulu,Hawaii,USA,2002.

[4]KEParsopoulos,MNVrahatis.Particleswarmoptimizationmethodinmultiobjectiveproblems[J].In:ProcoftheACMSymponAppliedComputing2002(SAC2002).NewYork:ACMPress,2002.603-607.IEEECongresson

　第3期薛洪波,伦淑娴:粒子群算法在多目标优化中的应用综述269

[5]Parsopoulos,K.E.andVrahatis,M.N.Particleswarmoptimizationmethodforconstrainedoptimizationproblem.ProceedingsoftheEuro-InternationalSymposiumonComputationalIntelligence2002.

[6]Michalewicz,Z.Asurveyofconstrainthanglingtechniquesinevolutionarycomputationmethod,inMcDonnelletal.pp.135-155.

[7]唐焕文,秦学志.实用最优化方法[M].大连:大连理工大学出版社,1994.

[8]CoelloC.A,PulidoG.T,LechugaM.S.Handlingmultipleobjectiveswithparticleswarmoptimization[J].IEEETransactionsonEvolutionaryComputation,2004,8(3):256-279.

[9]CoelloC.A,LechugaM.S.MOPSO:AProposalformultipleobjectiveparticleswarmoptimization[J].The2002IEEECongressonEvolutionarycomputation.Piscataway,NJ:IEEEPress,2002.1051-1056.

[10]李　宁,邹　彤,孙德宝,秦元庆.基于粒子群的多目标优化算法[J].计算机工程与应用,2005,41(23):43-36.

[11]CostaJrEF,LagePlC,BiscaiaJrEC.Onthenumericalsolutionandoptimizationofstyrenepolymerizationintubularreactors[J].Comput.Chem.Eng.,2003,27:1591-1604.

[12]OuriqueCO.BiscaiaJrEC,PintoJC.Theuseofparticleswarmoptimizationfordynamicalanalysisinchemicalprocesses[J].Comput.Chem.Eng.,2002,26:1783-1793.

[13]KannanS,SlochanalSMR,SubbarajP,etal.Applicationofparticleswarmoptimizationtechniqueanditstogenerationexpansionplanningproblem[J].ElectricPowerSystemsReseach,2004,70:203-210.

[14]王云,张伏生,陈建斌,段光辉.电力系统多目标无功优化研究[J].,217.

[15]GaingZL.Particleswarmoptimizationtosolvingtheeconomicthe[J].IEEETrans.PowerSyst.,2003,18:1187-1195.

[16]NenortaiteJ,SimutisR.Stocks’tradingsystembasedsMonalgorithm[J].InternationalConferenceonComputationalScience.2004:843-.

[17]刘志东,陈华,邹永明,张华.[J].石油天然气学报,2009,31,1:261-263.

[18]CaorisS,,etal.imagingoftwo-dimensionalsc-attersbyusingaparticleswarmalgorithm[J].JournalofApplications,2004,18:481-494.

[19]YinPparticleswarmalgorithmforoptimalpolygonalapproximationofdigitalcurves[J].JournalofVisualCommunicationImageRepresentation,2004,15:241-260.

[20]KennedyJ,EberhartRC.Adiscretebinaryversionoftheparticleswarmalgorithm[J].In:Proc.oftheWorldMulticonferenceonSystemics,CyberneticsandInformatics.1997:4104-4109.

[21]丁艳,金伟其,周海丰.基于粒子群算法的多阈值图像分割方法[J].光学技术,2008,34,4:636-637.

[22]XiaoX,DowER,EberhartR,etal.hybridself-organizingmapsandparticleswarmOptimizationapproach[J].ConcurrencyandComputation-Practice&Experience,2004,16:895-915.

[23]丛琳,焦李成,沙宇恒.正交免疫克隆粒子群多目标优化算法[J].电子与信息学报,2008,30,10:2321-2324.

[24]段晓东,王楠楠,王存睿等.一种基于粒子群算法的分类器设计[J].计算机工程,2005,31(20):107-109.

[25]EngelbrechtAP,IsmailA.Trainingproducttnitneuralnetworks[J].StabilityandControl:TheoryandApplications,1999,2:59274.

[26]MesserschmidtL,EngelbrechtAP.LearningtoplaygamesusingaPSO-basedcompetitivelearningapproach[J].IEEETrans.onEvolut.Comput.2004,8:280-288.

AreviewonappliactionofPSOinmulti2objectiveoptimization

XUEHong2bo,LUNShu2xian

(CollegeofInformationScienceandEngineering,BohaiUniversity,Jinzhou121013,China)

Abstract:PSO(ParticleSwarmOptimization)isaglobalstochasticoptimalalgorithmbasedonswarmintelligence.Tocompletetheupdatedoptimization,PSOsearchesitsownindividualoptimalsolutionparticleswarm’sglobaloptimalsolution,bymeansofparticles.PSOhasbeenappliedinmanyfields.Thebasicoutline,theactualizationsituationandthefuturetrendarereviewedofPSO’smulti2objectiveconstraintoptimization.

Keywords:multi2objective;particleswarm;constraintoptimization;inertiaweight