粒子群优化算法

5.3粒子群优化算法简介

ResearchontheParticleSwarmOptimizationpse2009pse20091.粒子群优化算法的由来1995年,Eberhart和Kennedy提出粒子群优化算法(ParticleSwarmOptimization,PSO)[1,2]。它的的基本概念源于对人工生命（ArtificialLife，AL）和鸟群觅食行为的研究。名词解释：AL：研究具有某些生命基本特征的人工系统.包括两方面的内容 1.研究如何利用计算技术研究生物现象 2.研究如何利用生物技术研究计算问题现在已经有很多源于生物现象的计算技巧.例如,人工神经网络是简化的大脑模型.遗传算法是模拟基因进化过程的.PSE200921.粒子群优化算法的由来PSO算法最早源于对鸟群觅食行为的研究。研究者发现鸟群在飞行过程中经常会突然改变方向、散开、聚集,其行为不可预测,但其整体总保持一致性,个体与个体间也保持着最适宜的距离。通过对类似生物群体的行为的研究,发现生物群体中存在着一种社会信息共享机制,它为群体的进化提供了一种优势,这也是PSO算法形成的基础。PSE200932.PSO的生物特性(BiologicCharacter)粒子群优化算法(PSO)起源对简单生物-社会系统的模拟.最初设想是模拟鸟群觅食的过程.

设想这样一个场景：一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟都不知道食物在那里，但是它们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢？最简单有效的就是搜寻目前离食物最近的鸟的周围区域。这是由一些简单个体组成的群落与环境以及个体之间的互动行为，是一种“群智能”(SwarmIntelligence)行为,模拟系统利用局部信息从而可能产生不可预测的群体行为。小知识：

群智能：指无智能的主体通过合作表现出智能行为的特性。在计算智能(ComputationalIntelligence)领域有两种基于群智能的算法，蚁群算法(AntColonyOptimization,ACO)和粒子群算法。前者是对蚂蚁群落食物采集过程的模拟，已经成功运用在很多离散优化问题上。PSE200943.PSO的数学描述PartⅠPSO算法就从这种生物种群行为特性中得到启发并用于求解优化问题。

在PSO中，每个优化问题的潜在解都可以想象成D维搜索空间上的一个点，我们称之为“粒子”（Particle），所有的粒子都有一个被目标函数决定的适应值（FitnessValue）。搜索正是在这样一群随机粒子而组成的一个种群中进行的。

PSE200953.PSO的数学描述PartⅠPSO算法中每个粒子就是解空间中的一个解,它根据自己的飞行经验和同伴的飞行经验来调整自己的飞行。每个粒子在飞行过程所经历过的最好位置,就是粒子本身找到的最优解。整个群体所经历过的的最好位置,就是整个群体目前找到的最优解。前者叫做个体极值(pBest),后者叫做全局极值(gBest)。每个粒子都通过上述两个极值不断更新自己,从而产生新一代群体。PSE20096数学描述：

假设在一个D维的目标搜索空间中，有m个代表潜在问题解的粒子组成的一个种群，其中，i＝1，2，…m表示第i个粒子在D维解空间的一个矢量点。

将代入一个与求解问题相关的目标函数可以计算出相应的适应值。用，记录第i个粒子自身搜索到的最好点（所谓最好，是指适应值最好）。而在所有这些粒子中，有一个是最好的，我们将这个粒子的编号记为g,则就是种群搜索到的最好值，其中g∈{1,2,…,m}。用，表示第i个粒子的速度。PSE20097PSO的数学描述最优解搜索过程，其实是在不断迭代中，所有粒子的速度变化和位置的进化。采用下列公式对粒子进行操作的：提示：m—种群规模D—问题维数—i粒子位置—i粒子速度—i粒子自身最好点位置—种群整体最好点位置c1,c2—学习因子，一般取值为2.0r1，r2—随机数，取值范围为[0,1]

(a)(b)PSE200984.PSO的粒子行为描述Part1公式（a）的组成第①部分称为记忆项，表示上次速度大小和方向的影响；

公式的第②部分称为自身认知项，是从当前点指向此粒子自身最好点的一个矢量；公式的第③部分称为群体认知项，是一个从当前点指向种群最好点的一个矢量，反映了粒子间的协同合作。可见，公式（a）是粒子依据先前的速度、自身最好经验、以及群体最好经验这三个因素实现对速度的更新。(a)①③②全局版和局部版PSO：若将看做是整个种群的最好点位置，这就是全局版PSO；而若将看做是一个所处的小群体的最好点位置，这就成了局部PSO。PSE20099PSO的粒子行为描述Part2公式(b)的意义相当明确，即粒子i从当前位置以得到的速度矢量飞向新的位置。

因此，每个迭代步中的粒子的行为可以由右图形象描述。(b)XiPgViXi’PiPSE2009105.PSO算法演示演示使用二维Sphere测试函数两个自变量范围为[-300,300]已知测试函数的极小值为0种群规模m＝20PSE2009116.PSO程序实现基本步骤选定PSO种群规模m；设X[i]为种群中第i个粒子的位置；设fitness[i]为第i个粒子的适应值；设V[i]为第i个粒子的速度；设gBest为种群最好粒子的标号；设Pbest[i]为第i个粒子自身搜索到的最好点位置；设Pbest_fitness[i]为第i个粒子自身搜索到的最好适应值，即Pbest[i]处的适应函数值；Step1:（初始化）对于每一个种群中的粒子i，i=1,2,…,mStep1.1:随机初始化X[i]；Step1.2:随机初始化V[i]；Step1.3:计算fitness[i]，并以此初始化Pbest_fitness[i]Step1.4:以种群中最好适应值的粒子标号初始化gBestStep1.5:以X[i]初始化Pbest[i]Step2:循环迭代，直到满足PSO终止条件（即精度要求及最大迭代数）Step2.1:选择算法控制参数w；Step2.2:对每个粒子，计算其适应值fitness[i]。Step2.3:搜索gBest值：若Pbest_fitness[i]<Pbest_fitness[gBest]，则gBest=i；若fitness[i]<Pbest_fitness[i]，则 Pbest_fitness[i]=fitness[i]，且Pbest[i]=X[i]Step2.4:对每个粒子，依据公式（a）、（b）更新V[i]和X[i]值PSE2009127.PSO的优势与劣势优势：简单容易实现，需要调整的参数很少。收敛速度快（相比较于遗传算法GA,文献[5]）。劣势精度不高。加入惯性因子加入反向转播算法……易发散。加入变异算子加入后退算法……PSE2009138.PSO的研究成果与发展Part①最初的PSO文献[1,2]公式：加入惯性权值w文献[3,4]研究表明：较大的w值有利于跳出局部极小值（Exploration），而较小的w值有利于算法收敛（Exploitation)。公式：优点：精度及收敛速度有了明显的提高。发展：固定权值[4]，线性递减[3]，自适应（模糊规则）[6]等等基本PSO算法（SimplePSO，SPSO）：通常将待调参数不多的一类PSO归为SPSO加入约束因子α文献[10]公式：PSE200914PSO的研究成果与发展Part②杂交PSO算法（HybridPSO）文献[7，8]粒子群中的粒子被赋予一个杂交概率，与粒子的适应值无关。在每次迭代中，依据杂交概率选取指定数量的粒子放入一个池中。池中的粒子随机地两两杂交，产生同样数目的孩子粒子，并用孩子粒子代替父母粒子，以保持种群的粒子数目不变。算法的收敛速度比较快，搜索精度也相对比较高，对一类非线性优化问题可以得到满意的结果。不过引入了较多的待调整参数，对使用者的经验有一定要求。变异PSO算法（MutationPSO）文献[9]粒子群中的粒子被赋予一个变异概率。文献[9]提到用Gaussian变异其中σ取0.1，Gaussian为高斯函数据文献上提到效果优于SPSO及SGA以上研究来源于遗传算法（GeneticAlgorithm，GA）的一些思想个人观点：还可以是种群个别个体的变异。PSE200915PSO的研究成果与发展Part③协同PSO算法（CooperativePSO）文献[11，12]基本思想：用K个相互独立的粒子群分别在D维的目标空间中的不同维度方向上进行搜索。K称为划分因子采用的是局部版PSO的学习策略，容易跳出局部极小点。文献表明有明显的启动延迟，收敛缓慢。离散问题的PSO算法（DiscretePSO）文献[13]提出用于解决优化组合问题的PSO算法文献[14]:TSP问题文献[15]TaskAssignment问题文献[16]WorkShop问题PSE2009169.PSO算法的应用情况PSO主要用于求解连续函数优化问题。ANN权值训练[11,17]多目标优化问题[18,19,20]等等PSO也逐渐应用于离散问题TaskAssignment问题[15]WorkShop问题[16]等等PSE20091710.PSO的进一步问题PSO基础理论基础研究不足。

研究者们还不能对PSO的工作机理给出恰当的数学解释。文献[21]做了有益的探索工作。开拓新的PSO算法的应用领域是一项有价值的工作。

因为PSO算法的生命力也主要在于工程应用方面。PSE20091813.参考文献ⅠKennedy,J.andEberhart,R.C.Particleswarmoptimization.Proc.IEEEint‘lconf.onneuralnetworksVol.IV,pp.1942-1948.IEEEservicecenter,Piscataway,NJ,1995.Eberhart,R.C.andKennedy,J.Anewoptimizerusingparticleswarmtheory.Proceedingsofthesixthinternationalsymposiumonmicromachineandhumansciencepp.39-43.IEEEservicecenter,Piscataway,NJ,Nagoya,Japan,1995.ShiY.EberhartR.Amodifiedparticleswarmoptimizer[C].In.IEEEWorldCongressonComputationalIntelligence.1998.69~73Eberhart,R.C.,Shi,Y.,(1998b).ParameterSelectioninParticleSwarmOptimization,EvolutionaryProgrammingVII,Porto,V.W.,Saravanan,N.Waagen,D.,Eiben,A.E.,1447,591-600,Springer-Verlag.Eberhart,R.C.,Shi,Y.,(1998a).ComparisonbetweenGeneticAlgorithmsandParticleSwarmOptimization,EvolutionaryProgrammingVII,Porto,V.W.,Saravanan,N.Waagen,D.,Eiben,A.E.,1447,611-618,Springer-Verlag.ShiY.EberhartR.C.Fuzzyadaptiveparticleswarmoptimization[C].In.ProcCongressonEvolutionaryComputation.SeoulKorea.2001

P.Angeline,"EvolutionaryOptimizationversusParticleSwarmOptimization:PhilosophyandPerformanceDifferences",ProceedingofTheSeventhAnnualConf.onEvolutionaryProgramming,March1998.Lovbjerg,M.,Rasmussen,T.,K.andKrink,T.(2001).HybridParticleSwarmOptimiserwithBreedingandSubpopulations.In:ProceedingsofthethirdGeneticandEvolutionaryComputationConference(GECCO-2001),vol.1,p.469-476Higashi,N.andIba,H.Particleswarmoptimizationwithgaussianmutation.ProceedingsoftheIEEESwarmIntelligenceSymposium2003(SIS2003),Indianapolis,Indiana,USA.pp.72-79,2003

PSE200919参考文献ⅡClerc,M.Theswarmandthequeen:towardsadeterministicandadaptiveparticleswarmoptimization.EvolutionaryComputation,1999.CEC99.Proceedingsofthe1999Congresson,Volume:3,6-9July1999-1957Vol.3F.vandenBerghandA.PEngelbrecht,"TrainingProductUnitNetworksusingCooperativeParticleSwarmOptimisers,"inProceedingsofIJCNN2001,(WashingtonDC,USA),Jul2001.vandenBergh,F.andEngelbrecht,A.P.Effectsofswarmsizeoncooperativeparticleswarmoptimisers.ProceedingsoftheGeneticandEvoluationaryComputationConference2001,SanFrancisco,USA.2001Kennedy,J.andEberhart,R.C.Adiscretebinaryversionoftheparticleswarmalgorithm.ProceedingsoftheWorldMulticonferenceonSystemics,CyberneticsandInformatics1997,Piscataway,NJ.pp.4104-4109,1997MauriceClerc.DiscreteParticleSwarmOptimizationIllustratedbytheTravelingSalesmanProblem.,2000

Salman,A.,Imtiaz,A.,andAl-Madani,S.Particleswarmoptimizationfortaskassignmentproblem.IASTEDInternationalConferenceonArtificialIntelligenceandApplications(AIA2001),Marbella,Spain.2001Mohan,C.K.andAl-kazemi,B.Discreteparticleswarmoptimization.ProceedingsoftheWorkshoponParticleSwarmOptimization2001,Indianapolis,IN.2001Ismail,A.andEngelbrecht,A.P.TrainingProductUnitsinFeedforwardNeuralNetworksusingParticleSwarmOptimization.ProceedingsoftheInternationalConferenceonArtificialIntelligence,Durban,SouthAfrica.pp.36-40,1999Hu,X.andEberhart,R.C.Multiobjectiveoptimizationusingdynamicneighborhoodparticleswarmoptimization.ProceedingsoftheIEEECongressonEvolutionaryComputation(CEC2002),Honolulu,HawaiiUS