粒子群優(yōu)化算法

5.3粒子群優(yōu)化算法簡介

ResearchontheParticleSwarmOptimizationpse2009pse20091.粒子群優(yōu)化算法的由來1995年,Eberhart和Kennedy提出粒子群優(yōu)化算法(ParticleSwarmOptimization,PSO)[1,2]。它的的基本概念源于對人工生命（ArtificialLife，AL）和鳥群覓食行為的研究。名詞解釋：AL：研究具有某些生命基本特征的人工系統(tǒng).包括兩方面的內(nèi)容 1.研究如何利用計算技術研究生物現(xiàn)象 2.研究如何利用生物技術研究計算問題現(xiàn)在已經(jīng)有很多源于生物現(xiàn)象的計算技巧.例如,人工神經(jīng)網(wǎng)絡是簡化的大腦模型.遺傳算法是模擬基因進化過程的.PSE200921.粒子群優(yōu)化算法的由來PSO算法最早源于對鳥群覓食行為的研究。研究者發(fā)現(xiàn)鳥群在飛行過程中經(jīng)常會突然改變方向、散開、聚集,其行為不可預測,但其整體總保持一致性,個體與個體間也保持著最適宜的距離。通過對類似生物群體的行為的研究,發(fā)現(xiàn)生物群體中存在著一種社會信息共享機制,它為群體的進化提供了一種優(yōu)勢,這也是PSO算法形成的基礎。PSE200932.PSO的生物特性(BiologicCharacter)粒子群優(yōu)化算法(PSO)起源對簡單生物-社會系統(tǒng)的模擬.最初設想是模擬鳥群覓食的過程.

設想這樣一個場景：一群鳥在隨機搜尋食物，在這個區(qū)域里只有一塊食物，所有的鳥都不知道食物在那里，但是它們知道當前的位置離食物還有多遠。那么找到食物的最優(yōu)策略是什么呢？最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。這是由一些簡單個體組成的群落與環(huán)境以及個體之間的互動行為，是一種“群智能”(SwarmIntelligence)行為,模擬系統(tǒng)利用局部信息從而可能產(chǎn)生不可預測的群體行為。小知識：

群智能：指無智能的主體通過合作表現(xiàn)出智能行為的特性。在計算智能(ComputationalIntelligence)領域有兩種基于群智能的算法，蟻群算法(AntColonyOptimization,ACO)和粒子群算法。前者是對螞蟻群落食物采集過程的模擬，已經(jīng)成功運用在很多離散優(yōu)化問題上。PSE200943.PSO的數(shù)學描述PartⅠPSO算法就從這種生物種群行為特性中得到啟發(fā)并用于求解優(yōu)化問題。

在PSO中，每個優(yōu)化問題的潛在解都可以想象成D維搜索空間上的一個點，我們稱之為“粒子”（Particle），所有的粒子都有一個被目標函數(shù)決定的適應值（FitnessValue）。搜索正是在這樣一群隨機粒子而組成的一個種群中進行的。

PSE200953.PSO的數(shù)學描述PartⅠPSO算法中每個粒子就是解空間中的一個解,它根據(jù)自己的飛行經(jīng)驗和同伴的飛行經(jīng)驗來調(diào)整自己的飛行。每個粒子在飛行過程所經(jīng)歷過的最好位置,就是粒子本身找到的最優(yōu)解。整個群體所經(jīng)歷過的的最好位置,就是整個群體目前找到的最優(yōu)解。前者叫做個體極值(pBest),后者叫做全局極值(gBest)。每個粒子都通過上述兩個極值不斷更新自己,從而產(chǎn)生新一代群體。PSE20096數(shù)學描述：

假設在一個D維的目標搜索空間中，有m個代表潛在問題解的粒子組成的一個種群，其中，i＝1，2，…m表示第i個粒子在D維解空間的一個矢量點。

將代入一個與求解問題相關的目標函數(shù)可以計算出相應的適應值。用，記錄第i個粒子自身搜索到的最好點（所謂最好，是指適應值最好）。而在所有這些粒子中，有一個是最好的，我們將這個粒子的編號記為g,則就是種群搜索到的最好值，其中g∈{1,2,…,m}。用，表示第i個粒子的速度。PSE20097PSO的數(shù)學描述最優(yōu)解搜索過程，其實是在不斷迭代中，所有粒子的速度變化和位置的進化。采用下列公式對粒子進行操作的：提示：m—種群規(guī)模D—問題維數(shù)—i粒子位置—i粒子速度—i粒子自身最好點位置—種群整體最好點位置c1,c2—學習因子，一般取值為2.0r1，r2—隨機數(shù)，取值范圍為[0,1]

(a)(b)PSE200984.PSO的粒子行為描述Part1公式（a）的組成第①部分稱為記憶項，表示上次速度大小和方向的影響；

公式的第②部分稱為自身認知項，是從當前點指向此粒子自身最好點的一個矢量；公式的第③部分稱為群體認知項，是一個從當前點指向種群最好點的一個矢量，反映了粒子間的協(xié)同合作。可見，公式（a）是粒子依據(jù)先前的速度、自身最好經(jīng)驗、以及群體最好經(jīng)驗這三個因素實現(xiàn)對速度的更新。(a)①③②全局版和局部版PSO：若將看做是整個種群的最好點位置，這就是全局版PSO；而若將看做是一個所處的小群體的最好點位置，這就成了局部PSO。PSE20099PSO的粒子行為描述Part2公式(b)的意義相當明確，即粒子i從當前位置以得到的速度矢量飛向新的位置。

因此，每個迭代步中的粒子的行為可以由右圖形象描述。(b)XiPgViXi’PiPSE2009105.PSO算法演示演示使用二維Sphere測試函數(shù)兩個自變量范圍為[-300,300]已知測試函數(shù)的極小值為0種群規(guī)模m＝20PSE2009116.PSO程序?qū)崿F(xiàn)基本步驟選定PSO種群規(guī)模m；設X[i]為種群中第i個粒子的位置；設fitness[i]為第i個粒子的適應值；設V[i]為第i個粒子的速度；設gBest為種群最好粒子的標號；設Pbest[i]為第i個粒子自身搜索到的最好點位置；設Pbest_fitness[i]為第i個粒子自身搜索到的最好適應值，即Pbest[i]處的適應函數(shù)值；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:循環(huán)迭代，直到滿足PSO終止條件（即精度要求及最大迭代數(shù)）Step2.1:選擇算法控制參數(shù)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:對每個粒子，依據(jù)公式（a）、（b）更新V[i]和X[i]值PSE2009127.PSO的優(yōu)勢與劣勢優(yōu)勢：簡單容易實現(xiàn)，需要調(diào)整的參數(shù)很少。收斂速度快（相比較于遺傳算法GA,文獻[5]）。劣勢精度不高。加入慣性因子加入反向轉(zhuǎn)播算法……易發(fā)散。加入變異算子加入后退算法……PSE2009138.PSO的研究成果與發(fā)展Part①最初的PSO文獻[1,2]公式：加入慣性權值w文獻[3,4]研究表明：較大的w值有利于跳出局部極小值（Exploration），而較小的w值有利于算法收斂（Exploitation)。公式：優(yōu)點：精度及收斂速度有了明顯的提高。發(fā)展：固定權值[4]，線性遞減[3]，自適應（模糊規(guī)則）[6]等等基本PSO算法（SimplePSO，SPSO）：通常將待調(diào)參數(shù)不多的一類PSO歸為SPSO加入約束因子α文獻[10]公式：PSE200914PSO的研究成果與發(fā)展Part②雜交PSO算法（HybridPSO）文獻[7，8]粒子群中的粒子被賦予一個雜交概率，與粒子的適應值無關。在每次迭代中，依據(jù)雜交概率選取指定數(shù)量的粒子放入一個池中。池中的粒子隨機地兩兩雜交，產(chǎn)生同樣數(shù)目的孩子粒子，并用孩子粒子代替父母粒子，以保持種群的粒子數(shù)目不變。算法的收斂速度比較快，搜索精度也相對比較高，對一類非線性優(yōu)化問題可以得到滿意的結果。不過引入了較多的待調(diào)整參數(shù)，對使用者的經(jīng)驗有一定要求。變異PSO算法（MutationPSO）文獻[9]粒子群中的粒子被賦予一個變異概率。文獻[9]提到用Gaussian變異其中σ取0.1，Gaussian為高斯函數(shù)據(jù)文獻上提到效果優(yōu)于SPSO及SGA以上研究來源于遺傳算法（GeneticAlgorithm，GA）的一些思想個人觀點：還可以是種群個別個體的變異。PSE200915PSO的研究成果與發(fā)展Part③協(xié)同PSO算法（CooperativePSO）文獻[11，12]基本思想：用K個相互獨立的粒子群分別在D維的目標空間中的不同維度方向上進行搜索。K稱為劃分因子采用的是局部版PSO的學習策略，容易跳出局部極小點。文獻表明有明顯的啟動延遲，收斂緩慢。離散問題的PSO算法（DiscretePSO）文獻[13]提出用于解決優(yōu)化組合問題的PSO算法文獻[14]:TSP問題文獻[15]TaskAssignment問題文獻[16]WorkShop問題PSE2009169.PSO算法的應用情況PSO主要用于求解連續(xù)函數(shù)優(yōu)化問題。ANN權值訓練[11,17]多目標優(yōu)化問題[18,19,20]等等PSO也逐漸應用于離散問題TaskAssignment問題[15]WorkShop問題[16]等等PSE20091710.PSO的進一步問題PSO基礎理論基礎研究不足。

研究者們還不能對PSO的工作機理給出恰當?shù)臄?shù)學解釋。文獻[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