【正文】 領(lǐng)域近年來，PSO快速發(fā)展，在眾多領(lǐng)域得到了廣泛應(yīng)用。包括不變的情況下通過，變化找出加速因子對算法的影響。本文通過對PSO算法的步驟的歸納、特點的分析，利用統(tǒng)計中的方差分析，通過抽樣實驗方法，論證了該算法中關(guān)鍵參數(shù)因子:慣性權(quán)值、加速因子對算法整體性能的影響效果，并提出了參數(shù)設(shè)置的指導(dǎo)原則，給出了關(guān)鍵參數(shù)設(shè)置，為PSO算法的推廣與改進提供了思路。雖然PSO算法發(fā)展迅速并取得了可觀的研究成果,但其理論基礎(chǔ)仍相對薄弱，尤其是算法基本模型中的參數(shù)設(shè)置和優(yōu)化問題還缺乏成熟的理論論證和研究。優(yōu)化是科學(xué)研究、工程技術(shù)和經(jīng)濟管理等領(lǐng)域的重要研究課題。最初設(shè)想是模擬鳥群覓食的過程。這些模擬系統(tǒng)利用局部信息從而可能產(chǎn)生不可預(yù)測的群體行為。現(xiàn)在我們討論另一種生物系統(tǒng) 社會系統(tǒng)。 例如，人工神經(jīng)網(wǎng)絡(luò)是簡化的大腦模型。研究如何利用生物技術(shù)研究計算問題。2010屆信息與計算科學(xué)專業(yè)畢業(yè)設(shè)計粒子群優(yōu)化算法及其參數(shù)設(shè)置畢業(yè)設(shè)計目 錄摘 要 IIAbstract III 1 研究背景和課題意義 1 參數(shù)的影響 1 應(yīng)用領(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 應(yīng)用單因子方差分析參數(shù)對結(jié)果影響 33 對參數(shù)的理論分析 345結(jié)論與展望 39致謝 43附錄 4479 研究背景和課題意義“人工生命”是來研究具有某些生命基本特征的人工系統(tǒng)。人工生命包括兩方面的內(nèi)容：研究如何利用計算技術(shù)研究生物現(xiàn)象?，F(xiàn)在已經(jīng)有很多源于生物現(xiàn)象的計算技巧。遺傳算法是模擬基因進化過程的。也可稱做“群智能”(swarm intelligence)。粒子群優(yōu)化算法(PSO) 也是起源對簡單社會系統(tǒng)的模擬。但后來發(fā)現(xiàn)PSO是一種很好的優(yōu)化工具。粒子群優(yōu)化算法[1] (簡稱PSO)是由Kennedy和Eberhart通過對鳥群、魚群和人類社會某些行為的觀察研究，于1995年提出的一種新穎的進化算法。鑒于PSO的發(fā)展歷史尚短，它在理論基礎(chǔ)與應(yīng)用推廣上都還存在一些缺陷，有待解決。 參數(shù)的影響標(biāo)準粒子群算法中主要的參數(shù)變量為（慣性權(quán)值）， ，（加速因子），本文重點對參數(shù)， ，做數(shù)據(jù)統(tǒng)計實驗。還有保持，不變對分別取不同值分析其對算法結(jié)果影響。本文將應(yīng)用研究分典型理論問題研究和實際工業(yè)應(yīng)用兩大類。實際工業(yè)應(yīng)用有：電力系統(tǒng)、濾波器設(shè)計、自動控制、數(shù)據(jù)聚類、模式識別與圖像處理、化工、機械、通信、機器人、經(jīng)濟、生物信息、醫(yī)學(xué)、任務(wù)分配、TSP等等。如果想較快地對PSO有一個比較全面的了解，借助網(wǎng)絡(luò)空間的電子資源無疑是不二之選。這里介紹當(dāng)今PSO研究領(lǐng)域較有影響的一個網(wǎng)址： Maurice Clerc 博士()的PSO主頁：該主頁主要介紹Maurice Clerc博士帶領(lǐng)的PSO研究小組的研究成果。這些未公開發(fā)表的文章往往是Maurice Clerc博士的一些設(shè)想，而且在不斷更新，如“Back to random topology”、“Initialisations for particle swarm optimization”、“Some ideas about PSO”等等，對PSO研究人員很有啟發(fā)。分別對其利用單因子方差分析法，說明不同參數(shù)水平對算法速率性能的影響。最后說明粒子群優(yōu)化算法在實際中的應(yīng)用以及對未來展望，最后總結(jié)了算法的優(yōu)缺點，附錄里面附有測試程序和測試函數(shù)。它與其他進化算法一樣，也是基于“種群”和“進化”的概念，通過個體間的協(xié)作與競爭，實現(xiàn)復(fù)雜空間最優(yōu)解的搜索；同時，PSO又不像其他進化算法那樣對個體進行交叉、變異、選擇等進化算子操作，而是將群體(swarm)中的個體看作是在D維搜索空間中沒有質(zhì)量和體積的粒子(particle)，每個粒子以一定的速度在解空間運動，并向自身歷史最佳位置pbest和鄰域歷史最佳位置聚集，實現(xiàn)對候選解的進化。自然界中各種生物體均具有一定的群體行為，而人工生命的主要研究領(lǐng)域之一是探索自然界生物的群體行為，從而在計算機上構(gòu)建其群體模型。仿真中僅利用上面三條簡單的規(guī)則，就可以非常接近的模擬出鳥群飛行的現(xiàn)象。在仿真中，一開始每一只鳥都沒有特定的飛行目標(biāo)，只是使用簡單的規(guī)則確定自己的飛行方向和飛行速度（每一只鳥都試圖留在鳥群中而又不相互碰撞），當(dāng)有一只鳥飛到棲息地時，它周圍的鳥也會跟著飛向棲息地，這樣，整個鳥群都會落在棲息地。他們的模型和仿真算法主要對Frank Heppner的模型進行了修正，以使粒子飛向解空間并在最好解處降落。自20世紀30年代以來，社會心理學(xué)的發(fā)展揭示：我們都是魚群或鳥群聚集行為的遵循者。人類的自然行為和魚群及鳥群并不類似，而人類在高維認知空間中的思維軌跡卻與之非常類似。 算法原理PSO從這種模型中得到啟示并用于解決優(yōu)化問題。所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適值( fitness value) ，每個粒子還有一個速度決定它們飛翔的方向和距離。PSO初始化為一群隨機粒子(隨機解)，然后通過迭代找到最優(yōu)解。另外也可以不用整個種群而只是用其中一部分作為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。第個粒子的“飛行 ”速度也是一個維的向量，記為 。整個粒子群迄今為止搜索到的最優(yōu)位置為全局極值，記為 在找到這兩個最優(yōu)值時，粒子根據(jù)如下的公式()和( )來更新自己的速度和位置[12]： () (2. 2)其中：和為學(xué)習(xí)因子，也稱加速常數(shù)(acceleration constant)，和為[0，1]范圍內(nèi)的均勻隨機數(shù)。是粒子的速度，是常數(shù)，由用戶設(shè)定用來限制粒子的速度。 基本粒子群算法流程算法的流程如下：① 初始化粒子群，包括群體規(guī)模，每個粒子的位置和速度② 計算每個粒子的適應(yīng)度值；③ 對每個粒子，用它的適應(yīng)度值和個體極值比較，如果 ，則用替換掉；④ 對每個粒子，用它的適應(yīng)度值和全局極值比較，如果則用替；⑤ 根據(jù)公式（），（）更新粒子的速度和位置 ；⑥ 如果滿足結(jié)束條件(誤差足夠好或到達最大循環(huán)次數(shù))退出，否則返回②。公式() 表示了粒子在求解空間中，由于相互影響導(dǎo)致的運動位置調(diào)整。粒子群優(yōu)化算法初期，其解群隨進化代數(shù)表現(xiàn)了更強的隨機性，正是由于其產(chǎn)生了下一代解群的較大的隨機性，以及每代所有解的“信息”的共享性和各個解的“自我素質(zhì)”的提高。例如對于問題求解， 粒子可以直接編碼為 ，而適應(yīng)度函數(shù)就是 。與遺傳算法相比，粒子群優(yōu)化算法的信息共享機制是很不同的:在遺傳算法中，染色體互相共享信息，所以整個種群的移動是比較均勻的向最優(yōu)區(qū)域移動。 帶慣性權(quán)重的粒子群算法探索是偏離原來的尋優(yōu)軌跡去尋找一個更好的解，探索能力是一個算法的全局搜索能力。如何確定局部搜索能力和全局搜索能力的比例，對一個問題的求解過程很重要。其進化過程為： （） （）在式()中，第一部分表示粒子先前的速度，用于保證算法的全局收斂性能；第二部分、第三部分則是使算法具有局部收斂能力。較大，全局收斂能力強，局部收斂能力弱；較小，局部收斂能力強，全局收斂能力弱。實驗結(jié)果表明，在之間時，PSO算法有更快的收斂速度，而當(dāng)時，算法則易陷入局部極值。目前PSO算法還沒有成熟的理論分析，少部分研究者對算法的收斂性進行了分析，大部分研究者在算法的結(jié)構(gòu)和性能改善方面進行研究，包括參數(shù)分析，拓撲結(jié)構(gòu)，粒子多樣性保持，算法融合和性能比較等。由于PSO中粒子向自身歷史最佳位置和鄰域或群體歷史最佳位置聚集，形成粒子種群的快速趨同效應(yīng)，容易出現(xiàn)陷入局部極值、早熟收斂或停滯現(xiàn)象[1214]。為了克服上述不足，各國研究人員相繼提出了各種改進措施。 粒子群初始化 研究表明，粒子群初始化對算法性能產(chǎn)生一定影響[16]。 鄰域拓撲 根據(jù)粒子鄰域是否為整個群體，PSO分為全局模型和局部模型 [20]。Kennedy[21]指出，模型雖然具有較快的收斂速度，但更容易陷入局部極值。根據(jù)現(xiàn)有的研究成果，本文將鄰域分為空間鄰域(spatial neighborhood)、性能空間(performance space)鄰域和社會關(guān)系鄰域(sociometric neighborhood)。性能空間指根據(jù)性能指標(biāo)(如適應(yīng)度、目標(biāo)函數(shù)值)劃分的鄰域，如文獻[24]采用適應(yīng)度距離比值(fitnessdistanceratio)來選擇粒子的相鄰粒子。針對不同的優(yōu)化問題，這些拓撲的性能表現(xiàn)各異；但總的來說，隨機拓撲往往對大多數(shù)問題能表現(xiàn)出較好的性能，其次是馮－諾以曼拓撲[22]。此外，文獻[21]提出動態(tài)社會關(guān)系拓撲(Dynamic sociometry)，初始階段粒子采用環(huán)形拓撲(ringtype topology)，隨著迭代次數(shù)的增加，逐漸增加粒子間連接，最后形成星形拓撲(startype topology)。文獻[19]引入了子種群，子種群間通過繁殖(Breeding)實現(xiàn)信息交流。X. Li[21]根據(jù)粒子相似性動態(tài)地將粒子群體按種類劃分為多個子種群，再以每個子種群的最佳個體作為每個粒子的鄰域最佳位置。文獻[13]采用主－仆模型(master–slaver model)，其中包含一個主群體，多個仆群體，仆群體進行獨立的搜索，主群體在仆群體提供的最佳位置基礎(chǔ)上開展搜索。文獻[15]采用多群體進行解的搜索。 在標(biāo)準的PSO算法中，所有粒子僅僅向自身和鄰域的歷史最佳位置聚集，而沒有向鄰域內(nèi)其他個體(即使這些個體很優(yōu)秀)學(xué)習(xí)，造成信息資源的浪費，甚至因此而陷入局部極值；考慮到此因素，Kennedy 等人[17]提出了全信息粒子群(fully informed particle swarm, FIPS)，在FIPS中，每個粒子除了自身和鄰域最佳歷史位置外，還學(xué)習(xí)鄰域內(nèi)其他粒子的成功經(jīng)驗?；谶@方面的考慮，Van den Bergh等人[18]提出了協(xié)作PSO(Cooperative PSO)算法，其基本思路就是采用協(xié)作行為，利用多個群體分別在目標(biāo)搜索空間中的不同維度上進行搜索，也就是一個優(yōu)化解由多個獨立群體協(xié)作完成，每個群體只負責(zé)優(yōu)化這個解矢量部分維上的分量。近來，ElAbd 等人[20]結(jié)合文獻[18,19]的技術(shù)，提出了等級協(xié)作PSO(hierarchal cooperative PSO)。J. Liang 等人[4]提出了一種既可以進行D維空間搜索、又能在不同維上選擇不同學(xué)習(xí)對象的新的學(xué)習(xí)策略，稱為全面學(xué)習(xí)PSO (Comprehensive Learning Particle Swarm Optimizer，CLPSO)。CLPSO的速度更新公式為： （）其中為加速因子，為[0,1]內(nèi)的均勻隨機數(shù)，表示粒子在第維的學(xué)習(xí)對象，它通過下面的策略決定：產(chǎn)生[0,1]內(nèi)的均勻隨機數(shù)，如果該隨機數(shù)大于為粒子預(yù)先給定的學(xué)習(xí)概率，則學(xué)習(xí)對象為自身歷史最佳位置；否則，從種群內(nèi)隨機選取兩個個體，按錦標(biāo)賽選擇(tournament selection)策略選出兩者中最好的歷史最佳位置作為學(xué)習(xí)對象。以上的各種鄰域結(jié)構(gòu)，無論是微觀拓撲還是宏觀鄰域，也無論是在整個搜索空間進行信息交流還是以空間的不同維分量為單位協(xié)作搜索，都不主動改變鄰域狀態(tài)，而只是在給定的鄰域內(nèi)進行學(xué)習(xí)交流，本文稱之為PSO的被動局部模型。Blackwell 等人[3]將粒子分為自然粒子和帶電粒子，當(dāng)帶電粒子過于接近時產(chǎn)生斥力，使之分開以提高粒子多樣性；L248。 混合策略 混合策略混合PSO就是將其它進化算法或傳統(tǒng)優(yōu)化算法或其它技術(shù)應(yīng)用到PSO中，用于提高粒子多樣性、增強粒子的全局探索能力，或者提高局部開發(fā)能力、增強收斂速度與精度。文獻[16]將螞蟻算法與PSO結(jié)合用于求解離散優(yōu)化問題；Robinson 等人[17]和Juang[18]將GA與PSO結(jié)合分別用于天線優(yōu)化設(shè)計和遞歸神經(jīng)網(wǎng)絡(luò)設(shè)計；文獻[19]將種群動態(tài)劃分成多個子種群，再對不同的子種群利用PSO或GA或爬山法進行獨立進化；Naka等人[10]將GA中的選擇操作引入到PSO中，按一定選擇率復(fù)制較優(yōu)個體；Angeline [11]則將錦標(biāo)賽選擇引入PSO 算法，根據(jù)個體當(dāng)前位置的適應(yīng)度，將每一個個體與其它若干個個體相比較，然后依據(jù)比較結(jié)果對整個群體進行排序，用粒子群中最好一半的當(dāng)前位置和速度替換最差一半的位置和速度，同時保留每個個體所記憶的個體最好位置；ElDib 等人[12]對粒子位置和速度進行交叉操作；Higashi [13]將高斯變異引入到PSO中；Miranda等人[14]則使用了變異、選擇和繁殖多種操作同時自適應(yīng)確定速度更新公式中的鄰域最佳位置以及慣性權(quán)值和加速常數(shù)；Zhang等人[8]利用差分進化(DE)操作選擇速度更新公式中的粒子最佳位置；而Kannan 等人[18]則利用DE來優(yōu)化PSO的慣性權(quán)值和加速常數(shù)。文獻[10]將PSO與單純形法相結(jié)合；文獻將PSO與序貫二次規(guī)劃相結(jié)合；文獻[12]將模擬退火與PSO結(jié)合；文獻[13]將禁忌技術(shù)與PSO結(jié)合；文獻[8]將爬山法與PSO結(jié)合；文獻[15]將PSO與擬牛頓法結(jié)合。文獻[6]根據(jù)耗散結(jié)構(gòu)的自組織性，提出一種耗散粒子群優(yōu)化算法(dissipative PSO)。文獻[7]將自然進化過程中的群體滅絕現(xiàn)象引入PSO，在微粒的位置和速度更新之后，按照一個預(yù)先定義的滅絕間隔重新初始化所有微粒的速度。文獻[9]將引力場模型引入到PSO。 2）拉伸PSO(Stretching PSO, SPSO)：SPSO將所謂的拉伸技術(shù)(stretching technique)[11]以及偏轉(zhuǎn)和排斥技術(shù)應(yīng)用到PSO中，對目標(biāo)函數(shù)進行變換，限制粒子向已經(jīng)發(fā)現(xiàn)的局部最小解運動，從而利于粒子有更多的機會