【正文】 2010屆信息與計算科學專業(yè)畢業(yè)設計粒子群優(yōu)化算法及其參數(shù)設置畢業(yè)設計目 錄摘 要 IIAbstract III 1 研究背景和課題意義 1 參數(shù)的影響 1 應用領(lǐng)域 2 電子資源 2 主要工作 2 3 粒子群算法思想的起源 3 算法原理 4 基本粒子群算法流程 5 特點 6 帶慣性權(quán)重的粒子群算法 7 粒子群算法的研究現(xiàn)狀 8 9 粒子群初始化 9 鄰域拓撲 9 混合策略 12 14 對參數(shù)的仿真研究 14 測試仿真函數(shù) 15 應用單因子方差分析參數(shù)對結(jié)果影響 33 對參數(shù)的理論分析 345結(jié)論與展望 39致謝 43附錄 4479 研究背景和課題意義“人工生命”是來研究具有某些生命基本特征的人工系統(tǒng)。人工生命包括兩方面的內(nèi)容：研究如何利用計算技術(shù)研究生物現(xiàn)象。研究如何利用生物技術(shù)研究計算問題?，F(xiàn)在已經(jīng)有很多源于生物現(xiàn)象的計算技巧。 例如，人工神經(jīng)網(wǎng)絡是簡化的大腦模型。遺傳算法是模擬基因進化過程的?，F(xiàn)在我們討論另一種生物系統(tǒng) 社會系統(tǒng)。也可稱做“群智能”(swarm intelligence)。這些模擬系統(tǒng)利用局部信息從而可能產(chǎn)生不可預測的群體行為。粒子群優(yōu)化算法(PSO) 也是起源對簡單社會系統(tǒng)的模擬。最初設想是模擬鳥群覓食的過程。但后來發(fā)現(xiàn)PSO是一種很好的優(yōu)化工具。優(yōu)化是科學研究、工程技術(shù)和經(jīng)濟管理等領(lǐng)域的重要研究課題。粒子群優(yōu)化算法[1] (簡稱PSO)是由Kennedy和Eberhart通過對鳥群、魚群和人類社會某些行為的觀察研究，于1995年提出的一種新穎的進化算法。雖然PSO算法發(fā)展迅速并取得了可觀的研究成果,但其理論基礎(chǔ)仍相對薄弱，尤其是算法基本模型中的參數(shù)設置和優(yōu)化問題還缺乏成熟的理論論證和研究。鑒于PSO的發(fā)展歷史尚短，它在理論基礎(chǔ)與應用推廣上都還存在一些缺陷，有待解決。本文通過對PSO算法的步驟的歸納、特點的分析，利用統(tǒng)計中的方差分析，通過抽樣實驗方法，論證了該算法中關(guān)鍵參數(shù)因子:慣性權(quán)值、加速因子對算法整體性能的影響效果，并提出了參數(shù)設置的指導原則，給出了關(guān)鍵參數(shù)設置，為PSO算法的推廣與改進提供了思路。 參數(shù)的影響標準粒子群算法中主要的參數(shù)變量為（慣性權(quán)值）， ，（加速因子），本文重點對參數(shù)， ，做數(shù)據(jù)統(tǒng)計實驗。包括不變的情況下通過，變化找出加速因子對算法的影響。還有保持，不變對分別取不同值分析其對算法結(jié)果影響。 應用領(lǐng)域近年來，PSO快速發(fā)展，在眾多領(lǐng)域得到了廣泛應用。本文將應用研究分典型理論問題研究和實際工業(yè)應用兩大類。典型理論問題包括：組合優(yōu)化、約束優(yōu)化、多目標優(yōu)化、動態(tài)系統(tǒng)優(yōu)化等。實際工業(yè)應用有：電力系統(tǒng)、濾波器設計、自動控制、數(shù)據(jù)聚類、模式識別與圖像處理、化工、機械、通信、機器人、經(jīng)濟、生物信息、醫(yī)學、任務分配、TSP等等。 電子資源 身處信息和網(wǎng)絡時代的我們是幸運的，豐富的電子資源能讓我們受益匪淺。如果想較快地對PSO有一個比較全面的了解，借助網(wǎng)絡空間的電子資源無疑是不二之選。對一些初學者而言，哪里能下載得到PSO的源程序，是他們很關(guān)心的話題；即使對一些資深的讀者，為了驗證自己提出的新算法或改進算法，如果能找到高級別國際期刊或會議上最近提出的算法源程序，那也是事半功倍的美事。這里介紹當今PSO研究領(lǐng)域較有影響的一個網(wǎng)址： Maurice Clerc 博士(@)的PSO主頁：該主頁主要介紹Maurice Clerc博士帶領(lǐng)的PSO研究小組的研究成果。除了從中可以得到他們近幾年公開發(fā)表的相關(guān)文獻和源代碼，還可以下載一些未公開發(fā)表的文章。這些未公開發(fā)表的文章往往是Maurice Clerc博士的一些設想，而且在不斷更新，如“Back to random topology”、“Initialisations for particle swarm optimization”、“Some ideas about PSO”等等，對PSO研究人員很有啟發(fā)。 主要工作論文內(nèi)容介紹了基本粒子群算法，用matlab實現(xiàn)標準粒子群算法算法，對兩個不同類型函數(shù)做具體分析，然后對其參數(shù)（慣性權(quán)值），（加速因子）測試。分別對其利用單因子方差分析法，說明不同參數(shù)水平對算法速率性能的影響。并且通過公式計算準確判斷參數(shù)對算法影響。最后說明粒子群優(yōu)化算法在實際中的應用以及對未來展望，最后總結(jié)了算法的優(yōu)缺點，附錄里面附有測試程序和測試函數(shù)。 粒子群算法思想的起源粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法 [1]是Kennedy和Eberhart受人工生命研究結(jié)果的啟發(fā)、通過模擬鳥群覓食過程中的遷徙和群聚行為而提出的一種基于群體智能的全局隨機搜索算法，1995年IEEE國際神經(jīng)網(wǎng)絡學術(shù)會議發(fā)表了題為“Particle Swarm Optimization”的論文，標志著PSO算法誕生(注：國內(nèi)也有很多學者譯為“微粒群優(yōu)化”)。它與其他進化算法一樣，也是基于“種群”和“進化”的概念，通過個體間的協(xié)作與競爭，實現(xiàn)復雜空間最優(yōu)解的搜索；同時，PSO又不像其他進化算法那樣對個體進行交叉、變異、選擇等進化算子操作，而是將群體(swarm)中的個體看作是在D維搜索空間中沒有質(zhì)量和體積的粒子(particle)，每個粒子以一定的速度在解空間運動，并向自身歷史最佳位置pbest和鄰域歷史最佳位置聚集，實現(xiàn)對候選解的進化。PSO算法具有很好的生物社會背景[2]而易理解、參數(shù)少而易實現(xiàn)，對非線性、多峰問題均具有較強的全局搜索能力，在科學研究與工程實踐中得到了廣泛關(guān)注[310]。自然界中各種生物體均具有一定的群體行為，而人工生命的主要研究領(lǐng)域之一是探索自然界生物的群體行為，從而在計算機上構(gòu)建其群體模型。自然界中的鳥群和魚群的群體行為一直是科學家的研究興趣，生物學家Craig Reynolds在1987年提出了一個非常有影響的鳥群聚集模型[7]，在他的仿真中，每一個個體遵循：(1) 避免與鄰域個體相沖撞；(2) 匹配鄰域個體的速度；(3) 飛向鳥群中心，且整個群體飛向目標。仿真中僅利用上面三條簡單的規(guī)則，就可以非常接近的模擬出鳥群飛行的現(xiàn)象。1990年，生物學家Frank Heppner也提出了鳥類模型[8]，它的不同之處在于：鳥類被吸引飛到棲息地。在仿真中，一開始每一只鳥都沒有特定的飛行目標，只是使用簡單的規(guī)則確定自己的飛行方向和飛行速度（每一只鳥都試圖留在鳥群中而又不相互碰撞），當有一只鳥飛到棲息地時，它周圍的鳥也會跟著飛向棲息地，這樣，整個鳥群都會落在棲息地。1995年，美國社會心理學家James Kennedy和電氣工程師Russell Eberhart共同提出了粒子群算法，其基本思想是受對鳥類群體行為進行建模與仿真的研究結(jié)果的啟發(fā)。他們的模型和仿真算法主要對Frank Heppner的模型進行了修正，以使粒子飛向解空間并在最好解處降落。Kennedy在他的書中描述了粒子群算法思想的起源。自20世紀30年代以來，社會心理學的發(fā)展揭示：我們都是魚群或鳥群聚集行為的遵循者。在人們的不斷交互過程中，由于相互的影響和模仿，他們總會變得更相似，結(jié)果就形成了規(guī)范和文明。人類的自然行為和魚群及鳥群并不類似，而人類在高維認知空間中的思維軌跡卻與之非常類似。思維背后的社會現(xiàn)象遠比魚群和鳥群聚集過程中的優(yōu)美動作復雜的多：首先，思維發(fā)生在信念空間，其維數(shù)遠遠高于3；其次，當兩種思想在認知空間會聚于同一點時，我們稱其一致，而不是發(fā)生沖突。 算法原理PSO從這種模型中得到啟示并用于解決優(yōu)化問題。PSO 中，每個優(yōu)化問題的潛在解都是搜索空間中的一只鳥，稱之為粒子。所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適值( fitness value) ，每個粒子還有一個速度決定它們飛翔的方向和距離。然后粒子們就追隨當前的最優(yōu)粒子在解空間中搜索[1]。PSO初始化為一群隨機粒子(隨機解)，然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個極值來更新自己；第一個就是粒子本身所找到的最優(yōu)解，這個解稱為個體極值；另一個極值是整個種群目前找到的最優(yōu)解，這個極值是全局極值。另外也可以不用整個種群而只是用其中一部分作為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。假設在一個維的目標搜索空間中，有個粒子組成一個群落，其中第個粒子表示為一個維的向量。第個粒子的“飛行 ”速度也是一個維的向量，記為 。第個粒子迄今為止搜索到的最優(yōu)位置稱為個體極值，記為 。整個粒子群迄今為止搜索到的最優(yōu)位置為全局極值，記為 在找到這兩個最優(yōu)值時，粒子根據(jù)如下的公式()和( )來更新自己的速度和位置[12]： () (2. 2)其中：和為學習因子，也稱加速常數(shù)(acceleration constant)，和為[0，1]范圍內(nèi)的均勻隨機數(shù)。式()右邊由三部分組成，第一部分為“慣性(inertia)”或“動量(momentum)”部分，反映了粒子的運動“習慣(habit)”，代表粒子有維持自己先前速度的趨勢；第二部分為“認知(cognition)”部分，反映了粒子對自身歷史經(jīng)驗的記憶(memory)或回憶(remembrance)，代表粒子有向自身歷史最佳位置逼近的趨勢；第三部分為“社會(social)”部分，反映了粒子間協(xié)同合作與知識共享的群體歷史經(jīng)驗，代表粒子有向群體或鄰域歷史最佳位置逼近的趨勢，根據(jù)經(jīng)驗，通常。是粒子的速度，是常數(shù)，由用戶設定用來限制粒子的速度。和是介于之間的隨機數(shù)[2][5]。 基本粒子群算法流程算法的流程如下：① 初始化粒子群，包括群體規(guī)模，每個粒子的位置和速度② 計算每個粒子的適應度值；③ 對每個粒子，用它的適應度值和個體極值比較，如果 ，則用替換掉；④ 對每個粒子，用它的適應度值和全局極值比較，如果則用替；⑤ 根據(jù)公式（），（）更新粒子的速度和位置 ；⑥ 如果滿足結(jié)束條件(誤差足夠好或到達最大循環(huán)次數(shù))退出，否則返回②。輸出結(jié)果根據(jù)方程()對粒子的位置進行進化根據(jù)方程()對粒子的速度進行進化求出整個群體的全局最優(yōu)值求出每個粒子的個體最優(yōu)計算每個粒子的適應值初始化每個粒子的速度和位置是否滿足結(jié)束條件是否開 始. PSO算法流程圖 特點式()中第1部分可理解為粒子先前的速度或慣性；第2部份可理解為粒子的“認知”行為，表示粒子本身的思考能力；第3部分可理解為粒子的“社會”行為，表示粒子之間的信息共享與相互合作。公式() 表示了粒子在求解空間中，由于相互影響導致的運動位置調(diào)整。整個求解過程中，慣性權(quán)重、加速因子和和最大速度共同維護粒子對全局和局部搜索能力的平衡。粒子群優(yōu)化算法初期，其解群隨進化代數(shù)表現(xiàn)了更強的隨機性，正是由于其產(chǎn)生了下一代解群的較大的隨機性，以及每代所有解的“信息”的共享性和各個解的“自我素質(zhì)”的提高。PSO 的一個優(yōu)勢就是采用實數(shù)編碼，不需要像遺傳算法一樣采用二進制編碼(或者采用針對實數(shù)的遺傳操作) 。例如對于問題求解， 粒子可以直接編碼為 ，而適應度函數(shù)就是 。粒子具有“記憶”的特性，它們通過“自我”學習和向“他人”學習，使其下一代解有針對性的從“先輩”那里繼承更多的信息，從而能在較短的時間內(nèi)找到最優(yōu)解。與遺傳算法相比，粒子群優(yōu)化算法的信息共享機制是很不同的:在遺傳算法中，染色體互相共享信息，所以整個種群的移動是比較均勻的向最優(yōu)區(qū)域移動。在粒子群優(yōu)化算法中，信息流動是單向的，即只有將信息給其他的粒子，這使得整個搜索更新過程跟隨當前解。 帶慣性權(quán)重的粒子群算法探索是偏離原來的尋優(yōu)軌跡去尋找一個更好的解，探索能力是一個算法的全局搜索能力。開發(fā)是利用一個好的解，繼續(xù)原來的尋優(yōu)軌跡去搜索更好的解，它是算法的局部搜索能力。如何確定局部搜索能力和全局搜索能力的比例，對一個問題的求解過程很重要。1998年，Yuhui Shi[9]提出了帶有慣性權(quán)重的改進粒子群算法。其進化過程為： （） （）在式()中，第一部分表示粒子先前的速度，用于保證算法的全局收斂性能；第二部分、第三部分則是使算法具有局部收斂能力。可以看出，式（)中慣性權(quán)重表示在多大程度上保留原來的速度。較大，全局收斂能力強，局部收斂能力弱；較小，局部收斂能力強，全局收斂能力弱。當時，式()與式()完全一樣，表明帶慣性權(quán)重的粒子群算法是基本粒子群算法的擴展。實驗結(jié)果表明，在之間時，PSO算法有更快的收斂速度，而當時，算法則易陷入局部極值。 粒子群算法的研究現(xiàn)狀在算法的理論研究方面。目前PSO算法還沒有成熟的理論分析，少部分研究者對算法的收斂性進行了分析，大部分研究者在算法的結(jié)構(gòu)和性能改善方面進行研究，包括參數(shù)分析，拓撲結(jié)構(gòu)，粒子多樣性保持，算法融合和性能比較等。PSO由于有簡單、易于實現(xiàn)、設置參數(shù)少、無需梯度信息等特點，其在連續(xù)非線性優(yōu)化問題和組合優(yōu)化問題中都表現(xiàn)出良好的效果。由于PSO中粒子向自身歷史最佳位置和鄰域或群體歷史最佳位置聚集，形成粒子種群的快速趨同效應，容易出現(xiàn)陷入局部極值、早熟收斂或停滯現(xiàn)象[1214]。同時，PSO的性能也依賴于算法參數(shù)[15]。為了克服上述不足，各國研究人員相繼提出了各種改進措施。本文將這些改進分為4類：粒子群初始化、鄰域拓撲、參數(shù)選擇和混合策略。 粒子群初始化 研究表明，粒子群初始化對算法性能產(chǎn)生一定影響[16]。為了初始種群盡可能均勻覆蓋整個搜索空間，提高全局搜索能力，Richard 和Ventura[17]提出了基于centroidal voronoi tessellations (CVTs)的種群初始化方法；薛明志等人[18]采用正交設計方法對種群進行初始化；Campana 等人[19]將標準PSO迭代公式改寫成線性動態(tài)系統(tǒng)，并基于此研究粒子群的初始位置，使它們具有正交的運動軌跡；文獻[16]認為均