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

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

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

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

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

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

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

假設(shè)在一個(gè)D維的目標(biāo)搜索空間中，有m個(gè)代表潛在問(wèn)題解的粒子組成的一個(gè)種群，其中，i＝1，2，…m表示第i個(gè)粒子在D維解空間的一個(gè)矢量點(diǎn)。

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

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

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

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

研究者們還不能對(duì)PSO的工作機(jī)理給出恰當(dāng)?shù)臄?shù)學(xué)解釋。文獻(xiàn)[21]做了有益的探索工作。開(kāi)拓新的PSO算法的應(yīng)用領(lǐng)域是一項(xiàng)有價(jià)值的工作。

因?yàn)镻SO算法的生命力也主要在于工程應(yīng)用方面。PSE20091813.參考文獻(xiàn)Ⅰ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參考文獻(xiàn)Ⅱ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