粒子群優(yōu)化算法的研究現(xiàn)狀與發(fā)展概述

1、第48卷第5期2008年5月電視技術TelecommunicationEngineering Vol.48 No.5May2008文章編號:1001-893X(2008)05-0007-05粒子群優(yōu)化算法的研究現(xiàn)狀與發(fā)展概述王伯成,施錦丹,王 凱23*(1.解放軍91868部隊,海南三亞572000;2.解放軍63961部隊,北京100012;3.第二炮兵駐孝感地區(qū)軍事代表室,湖北孝感432100)摘 要:粒子群優(yōu)化算法(PSO)是基于群體智能的一種優(yōu)化算法。該算法簡單易于實現(xiàn),可調參數(shù)少,得到了廣泛的研究和飛速發(fā)展。介紹了PSO提出的背景、PSO的思想和原理,分析并總結了PSO的優(yōu)缺點。根據

2、PSO算法研究側重點的不同,總結了PSO算法的發(fā)展現(xiàn)狀及特點,分析并展望了PSO還需要完善或繼續(xù)研究的問題,展望了PSO的研究熱點及發(fā)展趨勢。關鍵詞:粒子群優(yōu)化;復雜適應系統(tǒng);群體智能中圖分類號:TP183;TP301.6 文獻標識碼:AResearchStatusandReviewoftheDevelopmentofParticleSwarmOptimizationWANGBo-cheng,SHIJin-dan,WANGKai23(1.Unit91868ofPLA,Shanya675000,China;2.Unit63961ofPLA,Beijing100012,China;或進化包括:新層

3、次的產生;分化和多樣性的出現(xiàn);1 引 言如何利用生物技術研究計算問題是人工智能研究的重要方向之一。隨著復雜適應系統(tǒng)(ComplexAdaptiveSystem,CAS)理論于1994年正式提出,基于該理論的群智能算法也隨之飛速發(fā)展。CAS中的成員稱為主體,主體有適應性,它能夠與環(huán)境及其它主體進行交流,并且在交流的過程中 學習 或 積累經驗 改變自身結構和行為1新的、更大的主體的出現(xiàn)等。CAS有4個基本特點:首先,主體是主動的、活的實體;其次,個體與環(huán)境及其它個體的相互影響、相互作用,是系統(tǒng)演變和進化的主要動力;再次,將宏觀和微觀有機地聯(lián)系起來;最后,系統(tǒng)引入了隨機因素。粒子群優(yōu)化算法(Par-

4、ticleswarmOptimization,PSO)是由Kennedy和Eberhart于1995年提出的一種新的全局優(yōu)化進化算法,也是一種非常有效而被廣泛應用的迭代優(yōu)化。整個系統(tǒng)的演變*收稿日期:2008-02-04;修回日期:2008-03-25第48卷第5期2008年5月電視技術TelecommunicationEngineering Vol.48 No.5May2008算法,該算法模擬鳥群飛行覓食的行為,通過鳥之間的集體協(xié)作使群體達到最優(yōu)。由PSO的原理可知,該算法源于對一個CAS鳥群社會系統(tǒng)的仿真研究,也包含這4個基本特點。從20世紀90年代到今,國內外學者對PSO算法進行了大量的

5、研究,取得了一系列成果,并且在工程上得到了廣泛應用。2, ,m,d=1,2, ,D,學習因子c1和c2是非負常數(shù);r1和r2是介于0,1之間的隨機數(shù);vid -vmax,vmax,vmax是常數(shù),由用戶設定。迭代終止條件根據具體問題一般選為最大迭代次數(shù)或(和)粒子群迄今為止搜索到的最優(yōu)位置滿足預定最小適應閾值。因為Pg是整個粒子群的最優(yōu)位置,因此上述PSO也被稱為全局版PSO。也可以把第i個粒子的鄰居們搜索到的最優(yōu)位置作為Pg,則上述方法又被稱為局部版PSO;全局版PSO收斂速度快,但有時會陷入局部最優(yōu),局部版PSO收斂速度慢一點,但相對的不易陷入局部最優(yōu)。文獻3對式(1)作了如下改動:vid

6、=wvid+c1r1(Pid-xid)+c2r2(Pgd-xgd)(3)其中,w是非負數(shù),稱為慣性因子。而文獻4對式(2)作了以下改動:xid=xid+avid(4)其中,a稱為約束因子,目的是控制速度的權重。目前,也有很多學者把方程(3)、(4)視作基本的PSO?；綪SO需要用戶確定的參數(shù)并不多,而且操作簡單,故使用比較方便。PSO與遺傳算法類似,也是基于群體迭代,但沒有交叉、變異算子,群體在解空間中追隨最優(yōu)粒子進行搜索。2 基本PSO算法的思想和原理2.1 基本PSO算法的思想2PSO的基本概念源于對鳥群捕食行為的研究。設想這樣一個場景:一群鳥在隨機搜尋食物,在這個區(qū)域里只有一塊食物,所

7、有鳥都不知道食物在哪里,但是它們知道當前的位置離食物還有多遠。那么,找到食物的最優(yōu)策略是什么呢?最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。PSO從這種模型中得到啟示并用于解決優(yōu)化問題。PSO中,每個優(yōu)化問題的潛在解都是搜索空間中的一只鳥,稱之為粒子。所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適應值(fitnessvalue),每個粒子還有一個速度決定它們飛翔的方向和距離。然后粒子們就追隨當前的最優(yōu)粒子在解空間中搜索。PSO初始化為一群隨機粒子(隨機解),然后通過迭代找到最優(yōu)解。在每一次迭代中,粒子通過跟蹤兩個極值來更新自己:第一個就是粒子本身所找到的最優(yōu)解,這個解稱為個體極值;另一個極值是

8、整個種群目前找到的最優(yōu)解,這個極值是全局極值。另外也可以不用整個種群而只是用其中一部分作為粒子的鄰居,那么在所有鄰居中的極值就是局部極值。2.2 基本PSO的原理較多關于PSO研究的文獻都對基本PSO的原理進行了介紹,本文就不詳述了。Kennedy和Eberhart最早提出的PSO算法采用下列公式對粒子操作:xid=xid+avid+c1r1(Pid-xid)+c2r2(Pgd-xgd)(1)xid=xid+vid(2)其中,第i個粒子迄今為止搜索到的最優(yōu)位置為Pi=(Pi1,Pi2, ,PiD);整個粒子群迄今為止搜索到的最優(yōu)位置為Pg=(Pg1,Pg2, ,PgD);第i個粒子在D維搜索空

9、間中的位置是i=(xi1,xi2, ,xiD);i=1,83 基本PSO算法的優(yōu)缺點分析參考國內外大量的研究文獻和工程實踐,基本PSO算法優(yōu)缺點可以分別歸納如下:基本PSO的優(yōu)點:(1)PSO算法沒有交叉和變異運算,依靠粒子速度完成搜索,并且在迭代進化中只有最優(yōu)的粒子把信息傳遞給其它粒子,搜索速度快;(2)PSO算法具有記憶性,粒子群體的歷史最好位置可以記憶并傳遞給其它粒子;(3)需調整的參數(shù)較少,結構簡單,易于工程實現(xiàn);(4)采用實數(shù)編碼,直接由問題的解決定,問題解的變量數(shù)直接作為粒子的維數(shù)。基本PSO的缺點:(1)容易陷入局部最優(yōu),導致收斂精度低和不易收斂;第48卷第5期2008年5月電視

10、技術TelecommunicationEngineering5Vol.48 No.5May2008(2)不能有效解決離散及組合優(yōu)化問題;面的研究是將各種先進理論引入到PSO算法,研究各種改進和PSO算法;另一方面是將PSO算法和其它智能優(yōu)化算法相結合,研究各種混合優(yōu)化算法,達到取長補短、改善算法某方面性能的效果。(1)改進PSO算法的研究文獻9建立了PSO算法的慣性權重模型,慣性權重的引入,提高了算法的全局搜索能力;文獻10提出了帶鄰域操作的PSO模型,克服了PSO模型在優(yōu)化搜索后期隨迭代次數(shù)增加搜索結果無明顯改進的缺點;文獻11提出將拉伸技術用于PSO最小化問題的求解,力圖避免PSO算法易陷

11、于局部最小值的缺點;文獻12提出了一種用適應度定標的方法對PSO算法進行改進,該算法在算法收斂的前提下能夠提高粒子間適應度的差異;文獻13進一步提出具有繁殖和子群的HPSO算法,粒子群中的粒子被賦予一個雜交概率,這個雜交概率是用戶確定的,與粒子的適應值無關。在每次迭代中,依據雜交概率選取指定數(shù)量的粒子放入一個池中。池中的粒子隨機地兩兩雜交,產生同樣數(shù)目的孩子粒子,并用孩子粒子代替父母粒子,以保持種群的粒子數(shù)目不變;文獻13、14提出了一種協(xié)同PSO算法,其基本思想是用K個相互獨立的粒子群分別在D維的目標搜索空間中的不同維度方向上進行搜索。還有大量的文獻將混沌技術、神經網絡技術、灰色理論、自適應

12、技術等一系列先進理論引入到PSO算(5)法。各種先進理論的引入,極大地提高了PSO的性能。(2)混合智能優(yōu)化算法的研究文獻1517將進化計算中的選擇操作引入到PSO算法中,并提出了一種改進的PSO算法(HPSO)。該算法的主要思想是將每次迭代產生的新的粒子群根據適應函數(shù)進行選擇,用適應度較高的一半粒子的位置和速度矢量取代適應度較低的一半粒子的相應矢量,而保持后者個體極值不變。該改進算法的優(yōu)點是提高了PSO算法的收斂速度,同時保證了一定的全局搜索能力;不足之處是算法的收斂速度是以犧牲全局搜索能力為前提的。文獻18將進化算法中的交叉操作引入到HPSO模型,提高了粒子間區(qū)域搜索的能力。文獻1對遺傳算

13、法中的變異和PSO相結合進行了研究,其主要思想為:將整個種群分成不同的2個小組,當一個小組的(3)不能有效求解一些非直角坐標系描述問題,如有關能量場或場內粒子運動規(guī)律的求解問題(這些求解空間的邊界大部分是基于極坐標、球坐標或柱坐標的)。4 PSO的研究現(xiàn)狀參考國內關于PSO的文獻可知,有關PSO研究的內容可以分為基礎研究和應用研究兩大類。其中基礎研究主要包括PSO的本身機理和嚴格的數(shù)學基礎研究、PSO的收斂性、魯棒性的數(shù)學證明等;應用研究不外乎發(fā)揚PSO的優(yōu)點、克服PSO的缺點或不足、擴展PSO的應用范圍三大類,主要研究方法是將一些先進技術引入到PSO中設計出一些改進的PSO,或將PSO和其它

14、智能優(yōu)化算法相結合設計出各種混合優(yōu)化算法,或將PSO算法引入到離散系統(tǒng)、組合優(yōu)化系統(tǒng)、非直角坐標描述系統(tǒng),擴展PSO的應用范圍。4.1 PSO基礎研究的現(xiàn)狀文獻4、7對PSO算法的收斂性進行了研究,證明采用收斂因子能夠確保算法的收斂,文章提出的PSO收斂因子模型如下:vi=kvi+c1rand()(Pi-xi)+c2rand()(g-xi)k=|2- - -4 |其中, =c1+c2, >4,xi=xi+vi,rand()為在(0,1)間的隨機數(shù)。通常將 設為4.1,則由計算得到k為0.729。針對算法早期的實驗和應用,普遍認為參用收斂因子模型時,vmax參數(shù)無足輕重,而往往將vmax設

15、置為一個極大值,如100000。文獻8經過研究發(fā)現(xiàn),將其限定為xmax(每個粒子在每一維度上位置允許的變化范圍)可以取得更好的優(yōu)化結果。在公開發(fā)表的文獻當中,關于PSO基礎研究的文獻相對較少,未發(fā)現(xiàn)有關PSO收斂性、收斂速度估計等方面的數(shù)學證明。因此這方面的研究是PSO需要繼續(xù)完善的研究內容之一。4.2 PSO改進研究的現(xiàn)狀PSO算法的改進研究可以歸納為兩方面:一方第48卷第5期2008年5月電視技術TelecommunicationEngineering Vol.48 No.5May2008粒子飛向目前的最優(yōu)解時,另外一個小組向反方向飛行,以避免算法陷入局部最優(yōu)。文獻16、19對一種基于模擬

16、退火和PSO的混合優(yōu)化算法進行了研究,該混合算法與基本PSO算法相比較,提高了擺脫局部極值點的能力,并且提高了收斂速度和精度。同時,也有大量學者對PSO算法和免疫算法、禁忌搜索算法、單純形法、自適應算法等等一系列智能算法相結合進行了研究,得出了大量的混合算法,本文就不一一列了。這些混合智能優(yōu)化算法的共同特點是使得各種算法能夠和PSO算法優(yōu)勢互補,揚長避短,得到了更好的效果?？傊?改進PSO和混合PSO的研究極大地提高了PSO算法的工程適用能力。4.3 PSO擴展研究的現(xiàn)狀針對基本PSO一直未能有效解決離散及組合優(yōu)化問題,文獻20提出了一種廣義粒子群優(yōu)化模型(CPSO),該模型能夠適用于解決離散

17、及組合優(yōu)化問題,但該模型的魯棒性和通用性還有待進一步證明。針對基本PSO無法解決高維多目標優(yōu)化問題的不足,文獻21提出了一種適合求解高維多目標優(yōu)化問題的灰色粒子群算法(GPSO)。該算法能夠根據灰色關聯(lián)度的大小來選取粒子群算法中的全局極值和個體極值,既保證了PSO的智能性,又能掌握全局最優(yōu)的全貌。針對基本PSO在非直角坐標描述系統(tǒng)中應用較少的不足,文獻22提出了一種極坐標粒子群優(yōu)化算法(PPSO),但關于PSO在離散系統(tǒng)、組合優(yōu)化系統(tǒng)、更多非直角坐標描述系統(tǒng)中應用的研究尚還較少,還需要做大量的工作。論的引入,首先可以研究性能良好的新型粒子群拓撲結構。不同的粒子群鄰居拓撲結構是對不同類型社會的模

18、擬,研究不同拓撲結構的適用范圍,對算法推廣和使用有重要意義;其次可以優(yōu)化PSO的參數(shù)及其選擇。參數(shù)w、 2的選擇分別關系到粒子1、速度的3個部分:慣性部分、社會部分和自身部分在搜索中的作用。如何選擇、優(yōu)化和調整參數(shù),使得算法既能避免早熟又能比較快速地收斂,對工程實踐有著重要意義;(3)與其它智能優(yōu)化算法的融合。將PSO和其它優(yōu)化算法進行融合,主要考慮如何將PSO的優(yōu)點和其它智能優(yōu)化算法的優(yōu)點相結合,取長補短,構造出有特色、有實用價值的混合算法;(4)PSO的擴展應用。目前PSO的多數(shù)研究是針對直角坐標系統(tǒng)描述的系統(tǒng)、離散系統(tǒng)和單一優(yōu)化系統(tǒng),而實際系統(tǒng)中,很多系統(tǒng)是非直角坐標系統(tǒng)描述的系統(tǒng)、離散

19、系統(tǒng)、組合優(yōu)化的系統(tǒng),目前在這些系統(tǒng)中應用PSO算法可供參考的研究還較少,廣泛地開拓PSO在這些領域的應用不僅具有實際意義,同時對深化研究PSO也非常有意義。參考文獻:1 馮駿,薛云燦,江金龍.一種新的改進粒子群算法研究J.河海大學常州分校學報,2006,20(1):10-13.2 李愛國,覃征,鮑復民,賀升平.粒子群優(yōu)化算法J.計算機工程與應用,2002,38(21):1-3.3ShiY,EberhartR.AmodifiedparticleswarmoptimizerC IEEEWorldCongressonComputationalItell-igence.IEEE,1998:69-73

20、.4 ClercM.TheSwarmandtheQueen:TowardsaDetermin-isticandAdaptiveParticleSwarmOptimizationC ProcofthecongressofEvolutionaryComputation.1999:1951-1957.5 陳永剛,楊鳳杰,孫吉貴.新的粒子群優(yōu)化算法J.吉林大學學報,2006,24(2):181-183.6 高尚,楊靜宇,吳小俊,等.基于模擬退火算法思想的粒子群優(yōu)化算法J.計算機應用與軟件,2005,22(1):103-104.7 ClercM,KennedyJ.Theparticleswarm-exp

21、losion,sta-bility,andconvergenceinamultidimensionalcomplexspaceJ.IEEETransactionsonEvolutionaryComputa-tion,2002,6(1):58-73.8 FanHY,ShiYH.StudyofVmaxoftheParticleSwarmOptimizationAlgorithmD.PurdueSchoolofEngineer-5 PSO研究展望綜上所述,PSO研究的主要方向和熱點可以歸納如下:(1)算法基理的數(shù)學基礎研究。PSO在實際應用中被證明是有效的,但目前還沒有給出收斂性、收斂速度估計等方面

22、的數(shù)學證明,已有的工作還遠遠不夠;(2)將各種先進理論引入到PSO。各種先進理第48卷第5期2008年5月ingandTechnology,INPUI,2001.電視技術TelecommunicationEngineering Vol.48 No.5May200817 高鷹,謝勝利.基于模擬退火的粒子群優(yōu)化算法J.計算機工程與應用,2004,40(1):47-50.18LovbjergM,RasmussenTk,eta.lHybirdParticleSwarmOptimizationwithBreedingandSubpopulationsC IEEEInternationalConferen

23、ceonEvolutionaryComputation.SanDiego:IEEE,2000.19 李寧,孫德寶,岑翼則,等.帶變異算子的粒子群優(yōu)化算法J.計算機工程與應用,2004,40(17):12-14.20 高海兵,周馳,高亮.廣義粒子群優(yōu)化模型J.計算機學報,2005,28(12):1980-1987.21 于繁華,劉寒冰,戴金波.求解多目標優(yōu)化問題的灰色粒子群算法J.計算機應用,2006,26(12):2950-2952.22 劉蜀陽,張學良,孫大剛,等.基于極坐標復運算的粒子群優(yōu)化算法J.系統(tǒng)仿真學報,2006,18(7):1794-1798.ParticleSwarmmizer

24、C IEEEInternationalConferenceonEvolution-aryComputation.Anchorage:IEEE,1998.10 SuganthanPN.ParticleSwarmOptimizerwithNeigh-borhoodOperatorC ProceedingsofCongressonEv-olutionaryComputation.1999.11ParsopoulosKE.GlobalStretchingTechniqueforObtainingthroughMinimizesOptimizationC ProceedingsoftheWorkshoponPSO.Indianapolis:PurdueschoolofEngineeringandTechnology,INPUI,2001.12 LovbjergM,RasmussenTK,KrinkT.HybridParticleSwarmOptimizerwithBre