粒子群算法及其參數(shù)設置 畢業(yè)設計

1、<p><b>　　畢 業(yè) 論 文</b></p><p>　　題 目 粒子群算法及其參數(shù)設置 </p><p>　　專 業(yè) 信息與計算科學 </p><p>　　班 級 計算061 </p><p>　　學 號

2、 </p><p>　　學 生 xx </p><p>　　指導教師 </p><p>　　2010 年</p><p>　　粒子群優(yōu)化算法及其參數(shù)設置</p><p><b>　　摘

3、要</b></p><p>　　粒子群優(yōu)化是一種新興的基于群體智能的啟發(fā)式全局搜索算法，粒子群優(yōu)化算法通過粒子間的競爭和協(xié)作以實現(xiàn)在復雜搜索空間中尋找全局最優(yōu)點。它具有易理解、易實現(xiàn)、全局搜索能力強等特點，倍受科學與工程領域的廣泛關注，已經(jīng)成為發(fā)展最快的智能優(yōu)化算法之一。論文介紹了粒子群優(yōu)化算法的基本原理，分析了其特點。論文中圍繞粒子群優(yōu)化算法的原理、特點、參數(shù)設置與應用等方面進行全面綜述，重點利用單

4、因子方差分析方法，分析了粒群優(yōu)化算法中的慣性權值，加速因子的設置對算法基本性能的影響，給出算法中的經(jīng)驗參數(shù)設置。最后對其未來的研究提出了一些建議及研究方向的展望。</p><p>　　關鍵詞：粒子群優(yōu)化算法；參數(shù)；方差分析；最優(yōu)解 </p><p>　　Particle swarm optimization algorithm and its parameter set</p>

5、<p><b>　　Abstract</b></p><p>　　Particle swarm optimization is an emerging global based on swarm intelligence heuristic search algorithm, particle swarm optimization algorithm competition a

6、nd collaboration between particles to achieve in complex search space to find the global optimum. It has easy to understand, easy to achieve, the characteristics of strong global search ability, and has never wide field

7、of science and engineering concern, has become the fastest growing one of the intelligent optimization algorithms. This pap</p><p>　　Key word：Particle swarm optimization; Parameter; Variance analysis; Optima

8、l solution</p><p><b>　　目 錄</b></p><p><b>　　摘 要II</b></p><p>　　AbstractIII</p><p><b>　　1.引言1</b></p><p>　　1.1 研究背景和課題

9、意義1</p><p>　　1.2 參數(shù)的影響1</p><p>　　1.3 應用領域2</p><p>　　1.4 電子資源2</p><p>　　1.5 主要工作2</p><p>　　2.基本粒子群算法3</p><p>　　2.1 粒子群算法思想的起源3</p>

10、<p>　　2.2 算法原理4</p><p>　　2.3 基本粒子群算法流程5</p><p><b>　　2.4 特點6</b></p><p>　　2.5 帶慣性權重的粒子群算法7</p><p>　　2.7 粒子群算法的研究現(xiàn)狀8</p><p>　　3.粒子群優(yōu)化

11、算法的改進策略9</p><p>　　3.1 粒子群初始化9</p><p>　　3.2 鄰域拓撲9</p><p>　　3.3 混合策略12</p><p><b>　　4.參數(shù)設置14</b></p><p>　　4.1 對參數(shù)的仿真研究14</p><p>

12、;　　4.2 測試仿真函數(shù)15</p><p>　　4.3 應用單因子方差分析參數(shù)對結果影響33</p><p>　　4.4 對參數(shù)的理論分析34</p><p><b>　　5結論與展望39</b></p><p><b>　　致謝43</b></p><p>&

13、lt;b>　　附錄44</b></p><p><b>　　1.引言</b></p><p>　　1.1 研究背景和課題意義</p><p>　　“人工生命”是來研究具有某些生命基本特征的人工系統(tǒng)。人工生命包括兩方面的內容：</p><p>　　1、研究如何利用計算技術研究生物現(xiàn)象。</p>

14、;<p>　　2、研究如何利用生物技術研究計算問題。</p><p>　　現(xiàn)在已經(jīng)有很多源于生物現(xiàn)象的計算技巧。 例如，人工神經(jīng)網(wǎng)絡是簡化的大腦模型。遺傳算法是模擬基因進化過程的?，F(xiàn)在我們討論另一種生物系統(tǒng)- 社會系統(tǒng)。也可稱做“群智能”(swarm intelligence)。這些模擬系統(tǒng)利用局部信息從而可能產生不可預測的群體行為。</p><p>　　粒子群優(yōu)化算法(PS

15、O) 也是起源對簡單社會系統(tǒng)的模擬。最初設想是模擬鳥群覓食的過程。但后來發(fā)現(xiàn)PSO是一種很好的優(yōu)化工具。</p><p>　　優(yōu)化是科學研究、工程技術和經(jīng)濟管理等領域的重要研究課題。粒子群優(yōu)化算法[1] (簡稱PSO)是由Kennedy和Eberhart通過對鳥群、魚群和人類社會某些行為的觀察研究，于1995年提出的一種新穎的進化算法。雖然PSO算法發(fā)展迅速并取得了可觀的研究成果,但其理論基礎仍相對薄弱，尤其是算

16、法基本模型中的參數(shù)設置和優(yōu)化問題還缺乏成熟的理論論證和研究。鑒于PSO的發(fā)展歷史尚短，它在理論基礎與應用推廣上都還存在一些缺陷，有待解決。本文通過對PSO算法的步驟的歸納、特點的分析，利用統(tǒng)計中的方差分析，通過抽樣實驗方法，論證了該算法中關鍵參數(shù)因子:慣性權值、加速因子對算法整體性能的影響效果，并提出了參數(shù)設置的指導原則，給出了關鍵參數(shù)設置，為PSO算法的推廣與改進提供了思路。</p><p><b>

17、　　1.2 參數(shù)的影響</b></p><p>　　標準粒子群算法中主要的參數(shù)變量為（慣性權值）， ，（加速因子），，本文重點對參數(shù)， ，做數(shù)據(jù)統(tǒng)計實驗。包括不變的情況下通過，變化找出加速因子對算法的影響。還有保持，不變對分別取不同值分析其對算法結果影響。</p><p><b>　　1.3 應用領域</b></p><p>　　近

18、年來，PSO快速發(fā)展，在眾多領域得到了廣泛應用。本文將應用研究分典型理論問題研究和實際工業(yè)應用兩大類。典型理論問題包括：組合優(yōu)化、約束優(yōu)化、多目標優(yōu)化、動態(tài)系統(tǒng)優(yōu)化等。</p><p>　　實際工業(yè)應用有：電力系統(tǒng)、濾波器設計、自動控制、數(shù)據(jù)聚類、模式識別與圖像處理、化工、機械、通信、機器人、經(jīng)濟、生物信息、醫(yī)學、任務分配、TSP等等。</p><p><b>　　1.4 電子資

19、源 </b></p><p>　　身處信息和網(wǎng)絡時代的我們是幸運的，豐富的電子資源能讓我們受益匪淺。如果想較快地對PSO有一個比較全面的了解，借助網(wǎng)絡空間的電子資源無疑是不二之選。對一些初學者而言，哪里能下載得到PSO的源程序，是他們很關心的話題；即使對一些資深的讀者，為了驗證自己提出的新算法或改進算法，如果能找到高級別國際期刊或會議上最近提出的算法源程序，那也是事半功倍的美事。這里介紹當今PSO研究

20、領域較有影響的一個網(wǎng)址： </p><p>　　Maurice Clerc 博士(Maurice.Clerc@WriteMe.com)的PSO主頁：http://clerc.maurice.free.fr/pso/</p><p>　　該主頁主要介紹Maurice Clerc博士帶領的PSO研究小組的研究成果。除了從中可以得到他們近幾年公開發(fā)表的相關文獻和源代碼，還可以下載一些未公開發(fā)表的

21、文章。這些未公開發(fā)表的文章往往是Maurice Clerc博士的一些設想，而且在不斷更新，如“Back to random topology”、“Initialisations for particle swarm optimization”、“Some ideas about PSO”等等，對PSO研究人員很有啟發(fā)。 </p><p><b>　　1.5 主要工作</b></p>

22、;<p>　　論文內容介紹了基本粒子群算法，用matlab實現(xiàn)標準粒子群算法算法，對兩個不同類型函數(shù)做具體分析，然后對其參數(shù)（慣性權值），，（加速因子）測試。分別對其利用單因子方差分析法，說明不同參數(shù)水平對算法速率性能的影響。并且通過公式計算準確判斷參數(shù)對算法影響。最后說明粒子群優(yōu)化算法在實際中的應用以及對未來展望，最后總結了算法的優(yōu)缺點，附錄里面附有測試程序和測試函數(shù)。</p><p><b

23、>　　2.基本粒子群算法</b></p><p>　　2.1 粒子群算法思想的起源</p><p>　　粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法 [1]是Kennedy和Eberhart受人工生命研究結果的啟發(fā)、通過模擬鳥群覓食過程中的遷徙和群聚行為而提出的一種基于群體智能的全局隨機搜索算法，1995年IEEE國際神經(jīng)網(wǎng)絡學術會議

24、發(fā)表了題為“Particle Swarm Optimization”的論文，標志著PSO算法誕生(注：國內也有很多學者譯為“微粒群優(yōu)化”)。它與其他進化算法一樣，也是基于“種群”和“進化”的概念，通過個體間的協(xié)作與競爭，實現(xiàn)復雜空間最優(yōu)解的搜索；同時，PSO又不像其他進化算法那樣對個體進行交叉、變異、選擇等進化算子操作，而是將群體(swarm)中的個體看作是在D維搜索空間中沒有質量和體積的粒子(particle)，每個粒子以一定的速度在

25、解空間運動，并向自身歷史最佳位置pbest和鄰域歷史最佳位置聚集，實現(xiàn)對候選解的進化。PSO算法具有很好的生物社會背景[2]而易理解、參數(shù)少而易實現(xiàn)，對非線性、多峰問題均具有較強的全局搜索能力，在科學研究與工程實踐中得到了廣泛關注[3-10]。</p><p>　　自然界中各種生物體均具有一定的群體行為，而人工生命的主要研究領域之一是探索自然界生物的群體行為，從而在計算機上構建其群體模型。自然界中的鳥群和魚群的群

26、體行為一直是科學家的研究興趣，生物學家Craig Reynolds在1987年提出了一個非常有影響的鳥群聚集模型[7]，在他的仿真中，每一個個體遵循：</p><p>　　(1) 避免與鄰域個體相沖撞；</p><p>　　(2) 匹配鄰域個體的速度；</p><p>　　(3) 飛向鳥群中心，且整個群體飛向目標。</p><p>　　仿真中

27、僅利用上面三條簡單的規(guī)則，就可以非常接近的模擬出鳥群飛行的現(xiàn)象。1990年，生物學家Frank Heppner也提出了鳥類模型[8]，它的不同之處在于：鳥類被吸引飛到棲息地。在仿真中，一開始每一只鳥都沒有特定的飛行目標，只是使用簡單的規(guī)則確定自己的飛行方向和飛行速度（每一只鳥都試圖留在鳥群中而又不相互碰撞），當有一只鳥飛到棲息地時，它周圍的鳥也會跟著飛向棲息地，這樣，整個鳥群都會落在棲息地。</p><p>　　

28、1995年，美國社會心理學家James Kennedy和電氣工程師Russell Eberhart共同提出了粒子群算法，其基本思想是受對鳥類群體行為進行建模與仿真的研究結果的啟發(fā)。他們的模型和仿真算法主要對Frank Heppner的模型進行了修正，以使粒子飛向解空間并在最好解處降落。Kennedy在他的書中描述了粒子群算法思想的起源。自20世紀30年代以來，社會心理學的發(fā)展揭示：我們都是魚群或鳥群聚集行為的遵循者。在人們的不斷交互過程

29、中，由于相互的影響和模仿，他們總會變得更相似，結果就形成了規(guī)范和文明。人類的自然行為和魚群及鳥群并不類似，而人類在高維認知空間中的思維軌跡卻與之非常類似。思維背后的社會現(xiàn)象遠比魚群和鳥群聚集過程中的優(yōu)美動作復雜的多：首先，思維發(fā)生在信念空間，其維數(shù)遠遠高于3；其次，當兩種思想在認知空間會聚于同一點時，我們稱其一致，而不是發(fā)生沖突。</p><p><b>　　2.2 算法原理</b><

30、/p><p>　　PSO從這種模型中得到啟示并用于解決優(yōu)化問題。PSO 中，每個優(yōu)化問題的潛在解都是搜索空間中的一只鳥，稱之為粒子。所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適值( fitness value) ，每個粒子還有一個速度決定它們飛翔的方向和距離。然后粒子們就追隨當前的最優(yōu)粒子在解空間中搜索[1]。</p><p>　　PSO初始化為一群隨機粒子(隨機解)，然后通過迭代找到最優(yōu)解。在每

31、一次迭代中，粒子通過跟蹤兩個極值來更新自己；第一個就是粒子本身所找到的最優(yōu)解，這個解稱為個體極值；另一個極值是整個種群目前找到的最優(yōu)解，這個極值是全局極值。另外也可以不用整個種群而只是用其中一部分作為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。</p><p>　　假設在一個維的目標搜索空間中，有個粒子組成一個群落，其中第個粒子表示為一個維的向量</p><p><b>　　

32、，。</b></p><p>　　第個粒子的“飛行 ”速度也是一個維的向量，記為</p><p><b>　　，。</b></p><p>　　第個粒子迄今為止搜索到的最優(yōu)位置稱為個體極值，記為</p><p><b>　　，。</b></p><p>　　整個粒

33、子群迄今為止搜索到的最優(yōu)位置為全局極值，記為</p><p>　　在找到這兩個最優(yōu)值時，粒子根據(jù)如下的公式(2.1)和( 2.2)來更新自己的速度和位置[12]：</p><p><b>　　(2.1)</b></p><p><b>　　(2. 2)</b></p><p>　　其中：和為學習因子

34、，也稱加速常數(shù)(acceleration constant)，和為[0，1]范圍內的均勻隨機數(shù)。式(2.1)右邊由三部分組成，第一部分為“慣性(inertia)”或“動量(momentum)”部分，反映了粒子的運動“習慣(habit)”，代表粒子有維持自己先前速度的趨勢；第二部分為“認知(cognition)”部分，反映了粒子對自身歷史經(jīng)驗的記憶(memory)或回憶(remembrance)，代表粒子有向自身歷史最佳位置逼近的趨勢；第

35、三部分為“社會(social)”部分，反映了粒子間協(xié)同合作與知識共享的群體歷史經(jīng)驗，代表粒子有向群體或鄰域歷史最佳位置逼近的趨勢，根據(jù)經(jīng)驗，通常。。是粒子的速度，，是常數(shù)，由用戶設定用來限制粒子的速度。和是介于之間的隨機數(shù)[2][5]。</p><p>　　2.3 基本粒子群算法流程</p><p><b>　　算法的流程如下：</b></p><

36、p>　?、?初始化粒子群，包括群體規(guī)模，每個粒子的位置和速度</p><p>　　② 計算每個粒子的適應度值；</p><p>　?、?對每個粒子，用它的適應度值和個體極值比較，如果 ，則用替換掉；</p><p>　　④ 對每個粒子，用它的適應度值和全局極值比較，如果則用替；</p><p>　　⑤ 根據(jù)公式（2.1），（2.2）更新

37、粒子的速度和位置 ；</p><p>　　⑥ 如果滿足結束條件(誤差足夠好或到達最大循環(huán)次數(shù))退出，否則返回②。</p><p>　　圖2.1. PSO算法流程圖</p><p><b>　　2.4 特點</b></p><p>　　1、式(2.1)中第1部分可理解為粒子先前的速度或慣性；第2部份可理解為粒子的“認知”行

38、為，表示粒子本身的思考能力；第3部分可理解為粒子的“社會”行為，表示粒子之間的信息共享與相互合作。公式(2.2) 表示了粒子在求解空間中，由于相互影響導致的運動位置調整。整個求解過程中，慣性權重、加速因子和和最大速度共同維護粒子對全局和局部搜索能力的平衡。</p><p>　　2、粒子群優(yōu)化算法初期，其解群隨進化代數(shù)表現(xiàn)了更強的隨機性，正是由于其產生了下一代解群的較大的隨機性，以及每代所有解的“信息”的共享性和各

39、個解的“自我素質”的提高。</p><p>　　3、PSO 的一個優(yōu)勢就是采用實數(shù)編碼，不需要像遺傳算法一樣采用二進制編碼(或者采用針對實數(shù)的遺傳操作) 。例如對于問題求解， 粒子可以直接編碼為 ，而適應度函數(shù)就是 。</p><p>　　4、粒子具有“記憶”的特性，它們通過“自我”學習和向“他人”學習，使其下一代解有針對性的從“先輩”那里繼承更多的信息，從而能在較短的時間內找到最優(yōu)解。&

40、lt;/p><p>　　5、與遺傳算法相比，粒子群優(yōu)化算法的信息共享機制是很不同的:在遺傳算法中，染色體互相共享信息，所以整個種群的移動是比較均勻的向最優(yōu)區(qū)域移動;在粒子群優(yōu)化算法中，信息流動是單向的，即只有將信息給其他的粒子，這使得整個搜索更新過程跟隨當前解。</p><p>　　2.5 帶慣性權重的粒子群算法</p><p>　　探索是偏離原來的尋優(yōu)軌跡去尋找一個更

41、好的解，探索能力是一個算法的全局搜索能力。開發(fā)是利用一個好的解，繼續(xù)原來的尋優(yōu)軌跡去搜索更好的解，它是算法的局部搜索能力。如何確定局部搜索能力和全局搜索能力的比例，對一個問題的求解過程很重要。1998年，Yuhui Shi[9]提出了帶有慣性權重的改進粒子群算法。其進化過程為：</p><p><b>　　（2.3） </b></p><p><b>

42、　　（2.4）</b></p><p>　　在式(2.1)中，第一部分表示粒子先前的速度，用于保證算法的全局收斂性能；第二部分、第三部分則是使算法具有局部收斂能力。可以看出，式（2.3)中慣性權重表示在多大程度上保留原來的速度。較大，全局收斂能力強，局部收斂能力弱；較小，局部收斂能力強，全局收斂能力弱。</p><p>　　當時，式(2.3)與式(2.1)完全一樣，表明帶慣性權

43、重的粒子群算法是基本粒子群算法的擴展。實驗結果表明，在之間時，PSO算法有更快的收斂速度，而當時，算法則易陷入局部極值。</p><p>　　2.7 粒子群算法的研究現(xiàn)狀</p><p>　　在算法的理論研究方面。目前PSO算法還沒有成熟的理論分析，少部分研究者對算法的收斂性進行了分析，大部分研究者在算法的結構和性能改善方面進行研究，包括參數(shù)分析，拓撲結構，粒子多樣性保持，算法融合和性能比

44、較等。PSO由于有簡單、易于實現(xiàn)、設置參數(shù)少、無需梯度信息等特點，其在連續(xù)非線性優(yōu)化問題和組合優(yōu)化問題中都表現(xiàn)出良好的效果。</p><p>　　3.粒子群優(yōu)化算法的改進策略</p><p>　　由于PSO中粒子向自身歷史最佳位置和鄰域或群體歷史最佳位置聚集，形成粒子種群的快速趨同效應，容易出現(xiàn)陷入局部極值、早熟收斂或停滯現(xiàn)象[12-14]。同時，PSO的性能也依賴于算法參數(shù)[15]。為了

45、克服上述不足，各國研究人員相繼提出了各種改進措施。本文將這些改進分為4類：粒子群初始化、鄰域拓撲、參數(shù)選擇和混合策略。 </p><p>　　3.1 粒子群初始化 </p><p>　　研究表明，粒子群初始化對算法性能產生一定影響[16]。為了初始種群盡可能均勻覆蓋整個搜索空間，提高全局搜索能力，Richard 和Ventura[17]提出了基于centroidal voronoi tes

46、sellations (CVTs)的種群初始化方法；薛明志等人[18]采用正交設計方法對種群進行初始化；Campana 等人[19]將標準PSO迭代公式改寫成線性動態(tài)系統(tǒng)，并基于此研究粒子群的初始位置，使它們具有正交的運動軌跡；文獻[16]認為均勻分布隨機數(shù)進行初始化實現(xiàn)容易但尤其對高維空間效果差，并另外比較了3種初始化分布方法。 </p><p><b>　　3.2 鄰域拓撲 </b>&l

47、t;/p><p>　　根據(jù)粒子鄰域是否為整個群體，PSO分為全局模型和局部模型 [20]。對于模型，每個粒子與整個群體的其他粒子進行信息交換，并有向所有粒子中的歷史最佳位置移動的趨勢。Kennedy[21]指出，模型雖然具有較快的收斂速度，但更容易陷入局部極值。為了克服全局模型的缺點，研究人員采用每個粒子僅在一定的鄰域內進行信息交換，提出各種局部模型[21,]。根據(jù)現(xiàn)有的研究成果，本文將鄰域分為空間鄰域(spatia

48、l neighborhood)、性能空間(performance space)鄰域和社會關系鄰域(sociometric neighborhood)。空間鄰域直接在搜索空間按粒子間的距離(如歐式距離)進行劃分，如Suganthan[23]引入一個時變的歐式空間鄰域算子：在搜索初始階段，將鄰域定義為每個粒子自身；隨著迭代次數(shù)的增加，將鄰域范圍逐漸擴展到整個種群。性能空間指根據(jù)性能指標(如適應度、目標函數(shù)值)劃分的鄰域，如文獻[24]采用適

49、應度距離比值(fitness-distance-ratio)來選擇粒子的相鄰粒子。社會關系鄰域通常按粒子存儲陣列的索引編號進行劃分[25]，這也是研究最多的一種劃</p><p>　　此外，還有其它一些主要對群體進行劃分的鄰域結構(本文暫稱“宏觀鄰域”；則上述鄰域稱為“微觀鄰域”)。文獻[19]引入了子種群，子種群間通過繁殖(Breeding)實現(xiàn)信息交流。Kennedy[20]提出了社會趨同(Stereotyp

50、ing)模型，使用簇分析將整個粒子群劃分為多個簇，然后用簇中心代替帶收縮因子PSO中的粒子歷史最佳位置或群體歷史最佳位置。X. Li[21]根據(jù)粒子相似性動態(tài)地將粒子群體按種類劃分為多個子種群，再以每個子種群的最佳個體作為每個粒子的鄰域最佳位置。Stefan Janson等人[22]提出等級PSO(hierarchical particle swarm optimizer, HPSO)，采用動態(tài)等級樹作為鄰域結構，歷史最佳位置更優(yōu)的粒子

51、處于上層，每個粒子的速度由自身歷史最佳位置和等級樹中處于該粒子上一個節(jié)點的粒子的歷史最佳位置決定。文獻[13]采用主－仆模型(master–slaver model)，其中包含一個主群體，多個仆群體，仆群體進行獨立的搜索，主群體在仆群體提供的最佳位置基礎上開展搜索。文獻[14]將小生境(niche)技術引入到PSO中，提出了小</p><p>　　在標準的PSO算法中，所有粒子僅僅向自身和鄰域的歷史最佳位置聚集，

52、而沒有向鄰域內其他個體(即使這些個體很優(yōu)秀)學習，造成信息資源的浪費，甚至因此而陷入局部極值；考慮到此因素，Kennedy 等人[17]提出了全信息粒子群(fully informed particle swarm, FIPS)，在FIPS中，每個粒子除了自身和鄰域最佳歷史位置外，還學習鄰域內其他粒子的成功經(jīng)驗。 </p><p>　　上述粒子間學習是在整個維空間中構造鄰域進行的，這樣當搜索空間維數(shù)較高時往往容易

53、遭受“維數(shù)災(curse of dimensionality)”的困擾[14]。基于這方面的考慮，Van den Bergh等人[18]提出了協(xié)作PSO(Cooperative PSO)算法，其基本思路就是采用協(xié)作行為，利用多個群體分別在目標搜索空間中的不同維度上進行搜索，也就是一個優(yōu)化解由多個獨立群體協(xié)作完成，每個群體只負責優(yōu)化這個解矢量部分維上的分量。Baskar和Suganthan[19]提出一種類似的協(xié)作PSO，稱為并發(fā)PSO(

54、concurrent PSO， CONPSO)，它采用兩個群體并發(fā)地優(yōu)化一個解矢量。近來，El-Abd 等人[20]結合文獻[18,19]的技術，提出了等級協(xié)作PSO(hierarchal cooperative PSO)。 </p><p>　　無論是粒子群在D-維的搜索還是多個粒子群在不同維上的協(xié)作搜索，其目的都是為了每個粒子能夠找到有利于快速收斂到全局最優(yōu)解的學習對象。J. Liang 等人[4]提出了一種

55、既可以進行D-維空間搜索、又能在不同維上選擇不同學習對象的新的學習策略，稱為全面學習PSO (Comprehensive Learning Particle Swarm Optimizer，CLPSO)。與傳統(tǒng)PSO只向自身歷史最佳位置和鄰域歷史最佳位置學習不同，CLPSO的每個粒子都隨機地向自身或其它粒子學習，并且其每一維可以向不同的粒子學習；該學習策略使得每個粒子擁有更多的學習對象，可以在更大的潛在空間飛行，從而有利于全局搜索。CL

56、PSO的速度更新公式為： </p><p><b>　?。?.1）</b></p><p>　　其中為加速因子，為[0,1]內的均勻隨機數(shù)，表示粒子在第維的學習對象，它通過下面的策略決定：產生[0,1]內的均勻隨機數(shù)，如果該隨機數(shù)大于為粒子預先給定的學習概率，則學習對象為自身歷史最佳位置；否則，從種群內隨機選取兩個個體，按錦標賽選擇(tournament select

57、ion)策略選出兩者中最好的歷史最佳位置作為學習對象。同時，為了確保粒子盡可能向好的對象學習而不把時間浪費在較差的對象上，上述學習對象選擇過程設定一個更新間隔代數(shù)(refreshing gap)，在此期間的學習對象保持上次選擇的學習對象不變。</p><p>　　以上的各種鄰域結構，無論是微觀拓撲還是宏觀鄰域，也無論是在整個搜索空間進行信息交流還是以空間的不同維分量為單位協(xié)作搜索，都不主動改變鄰域狀態(tài)，而只是在給

58、定的鄰域內進行學習交流，本文稱之為PSO的被動局部模型。還有一類局部模型就是主動改變粒子鄰域空間，避免碰撞和擁擠，本文稱之為PSO的主動局部模型。Blackwell 等人[3]將粒子分為自然粒子和帶電粒子，當帶電粒子過于接近時產生斥力，使之分開以提高粒子多樣性；Løvbjerg 等人為每個粒子引入與相鄰粒子距離成反比的自組織危險度(self-organized criticality)指標，距離越近則危險度越高，當達到一定閾值

59、后，對該粒子進行重新初始化或推開一定距離降低危險度，達到提高群體多樣性的目的；文獻[15]提出一種帶空間粒子擴展的PSO，為每個粒子賦一半徑，以檢測兩個粒子是否會碰撞，并采取隨機彈離、實際物理彈離、簡單的速度—直線彈離等措施將其分開。 </p><p><b>　　3.3 混合策略 </b></p><p>　　混合策略混合PSO就是將其它進化算法或傳統(tǒng)優(yōu)化算法或其它

60、技術應用到PSO中，用于提高粒子多樣性、增強粒子的全局探索能力，或者提高局部開發(fā)能力、增強收斂速度與精度。這種結合的途徑通常有兩種：一是利用其它優(yōu)化技術自適應調整收縮因子/慣性權值、加速常數(shù)等；二是將PSO與其它進化算法操作算子或其它技術結合。文獻[16]將螞蟻算法與PSO結合用于求解離散優(yōu)化問題；Robinson 等人[17]和Juang[18]將GA與PSO結合分別用于天線優(yōu)化設計和遞歸神經(jīng)網(wǎng)絡設計；文獻[19]將種群動態(tài)劃分成多個

61、子種群，再對不同的子種群利用PSO或GA或爬山法進行獨立進化；Naka等人[10]將GA中的選擇操作引入到PSO中，按一定選擇率復制較優(yōu)個體；Angeline [11]則將錦標賽選擇引入PSO 算法，根據(jù)個體當前位置的適應度，將每一個個體與其它若干個個體相比較，然后依據(jù)比較結果對整個群體進行排序，用粒子群中最好一半的當前位置和速度替換最差一半的位置和速度，同時保留每個個體所記憶的個體最好位置；El-Dib 等人[12]對粒子位置和速度進

62、行交叉操作；Higashi [13]將高斯變異引入到PSO中；M</p><p>　　此外，其它一些搜索技術與PSO結合以提高算法的局部搜索能力，如文獻[9]提出一種基于PSO和Levenberg-Marquardt的混合方法;文獻[10]將PSO與單純形法相結合；文獻將PSO與序貫二次規(guī)劃相結合；文獻[12]將模擬退火與PSO結合；文獻[13]將禁忌技術與PSO結合；文獻[8]將爬山法與PSO結合；文獻[15]

63、將PSO與擬牛頓法結合。 </p><p>　　還有作者引入其它一些機制，以改進PSO的性能。文獻[6]根據(jù)耗散結構的自組織性，提出一種耗散粒子群優(yōu)化算法(dissipative PSO)。該算法通過附加噪聲持續(xù)為粒子群引入負熵(negative entropy)，使得系統(tǒng)處于遠離平衡態(tài)的狀態(tài)，又由于群體中存在內在的非線性相互作用，從而形成自組織耗散結構，使粒子群能夠“持續(xù)進化”，抑制早熟停滯。文獻[7]將自然進

64、化過程中的群體滅絕現(xiàn)象引入PSO，在微粒的位置和速度更新之后，按照一個預先定義的滅絕間隔重新初始化所有微粒的速度。文獻[8]通過模擬自然界的被動聚集(Passive Congregation)行為修改速度更新公式，實現(xiàn)種群內信息充分共享，防止了微粒因缺乏足夠的信息而判斷失誤所導致陷入局部極小。文獻[9]將引力場模型引入到PSO。此外，還有其它一些混合PSO： </p><p>　　1）高斯PSO：由于傳統(tǒng)PSO往

65、往是在全局和局部最佳位置的中間進行搜索，搜索能力和收斂性能嚴重依賴加速常數(shù)和慣性權值的設置，為了克服該不足，Secrest等人[10]將高斯函數(shù)引入PSO算法中，用于引導粒子的運動；GPSO不再需要慣性權值，而加速常數(shù)由服從高斯分布的隨機數(shù)產生。 </p><p>　　2）拉伸PSO(Stretching PSO, SPSO)：SPSO將所謂的拉伸技術(stretching technique)[11]以及偏轉和

66、排斥技術應用到PSO中，對目標函數(shù)進行變換，限制粒子向已經(jīng)發(fā)現(xiàn)的局部最小解運動，從而利于粒子有更多的機會找到全局最優(yōu)解[4, 6]。 </p><p>　　混沌粒子群優(yōu)化：混沌是自然界一種看似雜亂、其實暗含內在規(guī)律性的常見非線性現(xiàn)象，具有隨機性、遍歷性和規(guī)律性特點。文獻[3]利用混沌運動的遍歷性以粒子群的歷史最佳位置為基礎產生混沌序列，并將此序列中的最優(yōu)位置隨機替代粒子群中的某個粒子的位置，提出混沌PSO (ch

67、aos particle swarm optimization, CPSO)。除此之外，文獻[4]利用慣性權值自適應于目標函數(shù)值的自適應PSO進行全局搜索、利用混沌局部搜索對最佳位置進行局部搜索，提出一種PSO與混沌搜索相結合的混沌PSO；文獻[15]則利用混沌序列確定PSO的參數(shù)(慣性權值和加速常數(shù));文獻[9]提出一種不含隨機參數(shù)、基于確定性混沌Hopfield神經(jīng)網(wǎng)絡群的粒子群模型。 </p><p>　　

68、3）免疫粒子群優(yōu)化：生物免疫系統(tǒng)是一個高度魯棒性、分布性、自適應性并具有強大識別能力、學習和記憶能力的非線性系統(tǒng)。文獻[6]將免疫系統(tǒng)的免疫信息處理機制(抗體多樣性、免疫記憶、免疫自我調節(jié)等)引入到PSO中，分別提出了基于疫苗接種的免疫PSO和基于免疫記憶的免疫PSO。 </p><p>　　4）量子粒子群優(yōu)化：文獻[9]采用量子個體提出離散PSO；文獻[9]則基于量子行為更新粒子位置。 </p>

69、<p>　　5）卡爾曼PSO：文獻[9]利用Kalman濾波更新粒子位置。 </p><p>　　主成分PSO：文獻[10]結合主成分分析技術，粒子不僅按照傳統(tǒng)算法在維的x空間飛行，而且還在維的z空間同步飛行。</p><p><b>　　4.參數(shù)設置</b></p><p>　　4.1 對參數(shù)的仿真研究</p><

70、;p>　　PSO的參數(shù)主要包括最大速度、兩個加速常數(shù)和慣性常數(shù)或收縮因等。 </p><p>　　a) 最大速度的選擇：如式(2.1)所示的粒子速度是一個隨機變量，由粒子位置更新公式(2.2)產生的運動軌跡是不可控的，使得粒子在問題空間循環(huán)跳動[3, 6]。為了抑制這種無規(guī)律的跳動，速度往往被限制在內。增大，有利于全局探索(global exploration)；減小，則有利于局部開發(fā)(local expl

71、oitation)[3]。但是過高，粒子運動軌跡可能失去規(guī)律性，甚至越過最優(yōu)解所在區(qū)域，導致算法難以收斂而陷入停滯狀態(tài)；相反太小，粒子運動步長太短，算法可能陷入局部極值[16]。的選擇通常憑經(jīng)驗給定，并一般設定為問題空間的 [3]。此外，文獻[17]提出了的動態(tài)調節(jié)方法以改善算法性能；而文獻[48]提出了自適應于群體最佳和最差適應度值的選擇方法。</p><p>　　b) 加速常數(shù)的選擇：式(1)中的加速常數(shù)和分

72、別用于控制粒子指向自身或鄰域最佳位置的運動。文獻[20]建議，并通常取。Ratnaweera 等人[13]則提出自適應時變調整策略，即隨著進化代數(shù)從2.5線性遞減至0.5，隨著進化代數(shù)從0.5線性遞增至2.5。與傳統(tǒng)PSO取正數(shù)加速常數(shù)不同，Riget和Vesterstrom[11]提出一種增加種群多樣性的粒子群算法，根據(jù)群體多樣性指標調整加速常數(shù)的正負號，動態(tài)地改變“吸引”(Attractive)和“擴散”(Repulsive)狀態(tài)，

73、以改善算法過早收斂問題。 </p><p>　　c) 慣性權值或收縮因子的選擇：當PSO的速度更新公式采用式(1)時，即使和兩個加速因子選擇合適，粒子仍然可能飛出問題空間，甚至趨于無窮大，發(fā)生群體“爆炸(explosion)”現(xiàn)象[12]。有兩種方法控制這種現(xiàn)象：慣性常數(shù)(inertia constant)[3]和收縮因子(constriction factor)[12]。帶慣性常數(shù)PSO的速度更新公式如下：&l

74、t;/p><p><b>　　（4.1）</b></p><p>　　其中為慣性常數(shù)。文獻[8]建議隨著更新代數(shù)的增加從0.9線性遞減至0.4。近來，文獻[15]通過采用隨機近似理論(stochastic approximation theory)分析PSO的動態(tài)行為，提出了一種隨更新代數(shù)遞減至0的取值策略，以提高算法的搜索能力。帶收縮因子PSO由Clerc 和 Kenn

75、edy[12]提出，其最簡單形式[20]的速度更新 公式如下： </p><p><b>　?。?.2）</b></p><p>　　其中，；通常從而，。</p><p>　　11122{()( 雖然慣性權值PSO和收縮因子PSO對典型測試函數(shù)表現(xiàn)出各自的優(yōu)勢[16

76、]，但由于慣性常數(shù)方法通常采用慣性權值隨更新代數(shù)增加而遞減的策略，算法后期由于慣性權值過小，會失去探索新區(qū)域的能力，而收縮因子方法則不存在此不足[18]。 </p><p>　　4.2 測試仿真函數(shù)</p><p>　　例1. 函數(shù)對于適應度函數(shù)fitness對其參數(shù)，，做出不同方式的比較已測試其對函數(shù)結果影響。</p><p><b>　　（1）當，，。

77、</b></p><p>　　當慣性權值不變的情況下對取不同的值1.5和2。</p><p>　　程序（1）運行結果為：</p><p>　　圖4.1 粒子群位置初始化</p><p>　　圖4.2 粒子群速度初始化</p><p>　　圖4.3 迭代結果對比</p><p><

78、;b>　　最優(yōu)點坐標（1）：</b></p><p>　　[0.452429778718878 0.320640272233576 0.521629692208334 -0.037721251936116 -0.587907547759961 -0.197327841733574 0.059472309970162 -0.105031512919075 -0.060192285

79、082351 0.840740574648050]</p><p><b>　　最優(yōu)點坐標（2）：</b></p><p>　　[-0.295863893648182 -0.228564770714395 0.244463764764120 0.475115714243873 -0.330571564292149 -0.153811057636018

80、 -0.262874734324870 -0.134696331837768 -0.249466572982610 0.248526708588574]</p><p>　　適應度值（1）為：1.690633278729210</p><p>　　適應度值（2）為：0.769455496424646</p><p>　?。?）當于對比（加速因子與正常情況

81、對比）且運行程序（2）得如下結果：</p><p>　　圖4.4 初始化速度</p><p>　　圖4.5 初始化速度</p><p>　　圖4.6 迭代結果對比</p><p><b>　　最優(yōu)點坐標（1）：</b></p><p>　　[-0.301082521586939 0.13017

82、6903218111 0.149468203209848 -0.002964214272033 -0.101420705756867 -0.123775878581260 -0.888573463449087 0.505280093056671 0.707421391133458 -0.243136586226299]</p><p><b>　　最優(yōu)點坐標（2）：</b&

83、gt;</p><p>　　[-0.541610401047606 -0.107148776434457 -0.066670850819150 0.669477968063575 -0.349186281873742 0.605184616096295 0.051863122302620 -0.101089710356064 0.406977740018377 0.00976411114

84、4065]</p><p>　　適應度值（1）為：1.759984065528661</p><p>　　適應度值（2）為：1.424283049626009</p><p>　?。?）當于對比（加速因子與正常情況對比）的結果為：</p><p>　　圖4.7 初始化位置</p><p>　　圖4.8 初速度位置<

85、;/p><p>　　圖4.9 迭代結果對比</p><p><b>　　最優(yōu)點坐標（1）：</b></p><p>　　[0.032596367547015 -0.253447234013828 0.220174027850755 -0.184050929120391 -0.060526233943504 0.325089660099

86、637 -0.505184051372427 0.081261771085495 0.495050821497124 -0.194148350056426]</p><p><b>　　最優(yōu)點坐標（2）：</b></p><p>　　[-1.099975300165443 0.213471891229638 0.230838988305651

87、0.620982109338000 -0.022759191613578 0.136151982169503 0.595836418318090 0.059545555995647 0.132504460404116 -0.344875728471985]</p><p>　　適應度值（1）為：0.801579381651326</p><p>　　適應度值（2）為：2

88、.208540081759679</p><p>　?。?）當，分別對其取值，，，。分析結果如下：</p><p>　　圖4.10 初始化位置</p><p>　　圖4.11 初始化速度</p><p>　　圖4.12 迭代結果對比</p><p><b>　　最優(yōu)點坐標（1）：</b></

89、p><p>　　[-0.069619159841467 0.488557857942322 -0.587877368802422 0.577000714765126 -0.255019353943860 -0.326212573465861 -0.630693562346744 -0.360652175419648 0.104997980821461 0.624967

90、732306244]</p><p><b>　　最優(yōu)坐標（2）：</b></p><p>　　[0.360645808223021 -0.462713179464868 0.172157445992416 0.161165210517313 0.158416597461891 -0.805569345032097<

91、/p><p>　　0.640951653807223 -0.309321710810512 0.519209219049760 0.010556466456078]</p><p>　　適應度值（1）為：2.022968351158053</p><p>　　適應度值（2）為：1.850007680165146</p><p>　?。?）對

92、，對分別取，對比其迭代影響</p><p>　　圖4.13 初始化位置</p><p>　　圖4.14 初速度位置</p><p>　　圖4.15 迭代結果</p><p><b>　　最優(yōu)點坐標（1）：</b></p><p>　　[0.148332996728680 0.464843694

93、691154 -0.379559837826470 0.656268331316766 0.104011057125470 0.550631814306402 -0.069905771435114 -0.607186822378544 -0.044385131261800 0.060375755047727</p><p><b>　　最優(yōu)坐標（2）：</b>&

94、lt;/p><p>　　[-0.078496311635274 0.053450658106748 0.040978014348305 0.070447936565837 0.034324881708865 -0.189785878868686 0.032804423901163 -0.038580266459785 0.221247950866089 0.061389486373012

95、]</p><p>　　適應度值（1）為：1.506027752348302</p><p>　　適應度值（2）為：108141522528168</p><p>　　（6）標準粒子群算法無參數(shù)對比，</p><p>　　圖4.16 粒子群位置初始化</p><p>　　圖4.17 粒子群初始化速度</p>

96、<p>　　圖4.18 迭代結果</p><p>　　在以上仿真中，我們5個實驗實數(shù)的選擇分別對，，不同情況做出對比得出結論：</p><p>　　慣性權重的不同取值對PSO的影響</p><p>　　試驗表明權值將影響PSO 的全局與局部搜優(yōu)能力，值較大，全局搜優(yōu)能力強，局部搜優(yōu)能力弱;反之，則局部搜優(yōu)能力增強，而全局搜優(yōu)能力減弱。線性慣性權的引入使

97、PSO可以調節(jié)算法的全局與局部搜優(yōu)能力，但，還有兩個缺點:其一，迭代初期局部搜索能力較弱，即使初始粒子已接近于全局最優(yōu)點，也往往錯過;其二，在迭代后期，則因全局搜索能力變弱，而易陷入局部極值。時，粒子群優(yōu)化算法的搜索效率和搜索精度高。實驗結果證明:按照方差分析選擇適應的參數(shù)設置水平，能夠獲得穩(wěn)健和高效的優(yōu)化效果。</p><p>　　4.3 應用單因子方差分析參數(shù)對結果影響</p><p>

98、;　　按照方差分析選擇適應的參數(shù)設置水平，能夠獲得穩(wěn)健和高效的優(yōu)化效果。關鍵參數(shù)設置如下:粒子種群大小N:較小的群能充分探索解空間，避免了過多的適應值評估和計算時間。一般取[20 -40]，對于大部分的問題， 10個粒子已經(jīng)足夠取得好的結果，對于比較難的問題或者特定類別的問題，粒子數(shù)可以取到100，200。粒子的長度(空間維數(shù)) :這是由優(yōu)化問題決定，就是問題解的長度。粒子的坐標范圍:由優(yōu)化問題決定，每一維可以設定不同的范圍。決定粒子在

99、一個循環(huán)中最大的移動距離，通常設為粒子的范圍寬度。學習因子： 和通常等于2，不過文獻中也有其它的取值，一般，且范圍在0和4之間。終止條件:按最大循環(huán)數(shù)及最小偏差要求，這個終止條件由具體問題確定。例如，最小錯誤可以設定為1 個錯誤分類，最大循環(huán)數(shù)設定為2000。慣性權值: 控制著速度前一變化量對當前變化量的影響，如果較大，則影響較大，能夠搜索以前所未能達到的區(qū)域，整個算法的全局搜索能力加強，有利于跳出局部極小點；而值較小，則前一動量項的影

100、響較小，主要是在當前解的附近搜索，局部搜索能力較強，有利于算法收斂。研究表明，讓慣性權值隨著疊代次數(shù)的增加在1. 4到0之間逐</p><p>　　4.4 對參數(shù)的理論分析</p><p>　　方差分析是分析試驗數(shù)據(jù)的一種方法。利用此方法亦可分析算法中同一參數(shù)的不同水平或者不同參數(shù)的各個水平對算法性能影響的差異性，從而探究不同參數(shù)設置范圍與算法系統(tǒng)性能之間的潛在關系。單因子方差分析是通過觀

101、察一個因子的量值變化，分析這個因子變化對整個試驗的影響程度。利用這種方法可考查PSO中和這兩個關鍵的參數(shù)因子各自對算法性能的影響。在試驗中影響指標的因素稱為因子，因子所處的狀態(tài)，所取的等級稱為因子水平。本文采取相等的試驗次數(shù)進行方差分析。首先，假定因子有個水平，在每種水平下，做次試驗，在每次試驗后可得一試驗值，記做它表示在第個水平下的第個試驗值;， 如表1 所示，在考察因子對試驗結果的影響程度時，把因子的個水平看成是個正態(tài)總體，因此可設

102、， ， 。其中， ，是因子的第水平所引起的差異。因此檢驗因子的各水平之間是否有顯著的差異，相當于判斷公式(4.2)：或(3)利用公式(4.1) 表述的平方和分解公式可將總的離差平方和進行分解，從而將因子水平不同而造成的結果差異與隨機因素影響而造成的結果差異從量值上區(qū)分開來。</p><p>　　， （4.3）</p><p><b>　　其中，<

103、/b></p><p><b>　　，，</b></p><p>　　總離差平方和是所有觀察值與其總平均值之差的平方和，是描述全部數(shù)據(jù)離散程度的數(shù)量指標。由于是服從正態(tài)分布的隨機量，當公式(4.2) 成立時是獨立同分布。同正態(tài)分布的隨機變</p><p>　　量， 則有公式(4.3) 是服從的分布:</p><p>

104、;<b>　?。?.4）</b></p><p>　　是觀察值與組內平均值之差的平方和，也就是組內平均和，它反映了組內(同一水平下) 樣本的隨機波動，其自由度為，是組內平均值與總平均值之差的平方和，即組間平方和。它在一定程度上反映了因子各個水平不同而引起的差異，其自由度為。平方和分解公式說明觀察值關于其總平均值之的差異是由組內平方和組間平方和組成的。因此，公式(4.4) 表示的和之間的比值F

105、就是反映了兩種差異所占的比重。</p><p><b>　　（4.5）</b></p><p>　　F越大說明因子各水平不同引起的差異越顯著，所以統(tǒng)計量可用來檢驗各因子的影響效應。慣性權值、加速常數(shù)和的不同設置水平，每個設置水平進行10次測試，通過單因子方差分析，說明不同參數(shù)水平對算法速率性能—迭代次數(shù)和算法優(yōu)化性能———近似最優(yōu)解的影響能力，能夠獲得比較一致的迭代次

106、數(shù)均值， 且在此范圍內進行更細致的單因子方差分析進一步證明較小的慣性權值能夠提高算法速率。在需要較高計算速率的應用中，可適當減小慣性權值。</p><p>　　針對本程序（適應函數(shù)）令，做單因子方差分析，判斷因子對程序的影響。運行程序（6），在此基礎作5次試驗的結果。</p><p>　　第一組實驗對應的迭代次數(shù)為43，適應值為0.043133738358137</p>&l

107、t;p>　　第一組實驗對應的迭代次數(shù)為20，適應值為0.978441955858031</p><p>　　第一組實驗對應的迭代次數(shù)為9，適應值為1.704780367886482</p><p>　　第一組實驗對應的迭代次數(shù)為7，適應值為3.165437900832790</p><p>　　第二組實驗對應的迭代次數(shù)為45， 適應值為0.116223586

108、568965</p><p>　　第二組實驗對應的迭代次數(shù)為132，適應值為0.024791910872392</p><p>　　第二組實驗對應的迭代次數(shù)為8， 適應值為1.434014355783529</p><p>　　第二組實驗對應的迭代次數(shù)為7， 適應值為4.109304406313233</p><p>　　第三組實驗對應的迭