【正文】 xx 指導(dǎo)教師 徐小平 2010 年粒子群優(yōu)化算法及其參數(shù)設(shè)置專 業(yè)：信息與計(jì)算科學(xué)學(xué) 生： xx指導(dǎo)教師： 徐小平摘 要粒子群優(yōu)化是一種新興的基于群體智能的啟發(fā)式全局搜索算法，粒子群優(yōu)化算法通過粒子間的競(jìng)爭(zhēng)和協(xié)作以實(shí)現(xiàn)在復(fù)雜搜索空間中尋找全局最優(yōu)點(diǎn)。它具有易理解、易實(shí)現(xiàn)、全局搜索能力強(qiáng)等特點(diǎn)，倍受科學(xué)與工程領(lǐng)域的廣泛關(guān)注，已經(jīng)成為發(fā)展最快的智能優(yōu)化算法之一。論文中圍繞粒子群優(yōu)化算法的原理、特點(diǎn)、參數(shù)設(shè)置與應(yīng)用等方面進(jìn)行全面綜述，重點(diǎn)利用單因子方差分析方法，分析了粒群優(yōu)化算法中的慣性權(quán)值，加速因子的設(shè)置對(duì)算法基本性能的影響，給出算法中的經(jīng)驗(yàn)參數(shù)設(shè)置。關(guān)鍵詞：粒子群優(yōu)化算法；參數(shù)；方差分析；最優(yōu)解 Particle swarm optimization algorithm and its parameter setSpeciality: Information and Computing ScienceStudent: Ren KanAdvisor: Xu XiaopingAbstractParticle swarm optimization is an emerging global based on swarm intelligence heuristic search algorithm, particle swarm optimization algorithm petition and collaboration between particles to achieve in plex 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 of science and engineering concern, has bee the fastest growing one of the intelligent optimization algorithms. This paper introduces the particle swarm optimization basic principles, and analyzes its features. Paper around the particle swarm optimization principles, characteristics, parameters settings and applications to conduct a thorough review, focusing on a single factor analysis of variance, analysis of the particle swarm optimization algorithm in the inertia weight, acceleration factor setting the basic properties of the algorithm the impact of the experience of the algorithm given parameter setting. Finally, its future researched and prospects are proposed.Key word：Particle swarm optimization。 Variance analysis。人工生命包括兩方面的內(nèi)容：研究如何利用計(jì)算技術(shù)研究生物現(xiàn)象?，F(xiàn)在已經(jīng)有很多源于生物現(xiàn)象的計(jì)算技巧。遺傳算法是模擬基因進(jìn)化過程的。也可稱做“群智能”(swarm intelligence)。粒子群優(yōu)化算法(PSO) 也是起源對(duì)簡(jiǎn)單社會(huì)系統(tǒng)的模擬。但后來發(fā)現(xiàn)PSO是一種很好的優(yōu)化工具。粒子群優(yōu)化算法[1] (簡(jiǎn)稱PSO)是由Kennedy和Eberhart通過對(duì)鳥群、魚群和人類社會(huì)某些行為的觀察研究，于1995年提出的一種新穎的進(jìn)化算法。鑒于PSO的發(fā)展歷史尚短，它在理論基礎(chǔ)與應(yīng)用推廣上都還存在一些缺陷，有待解決。 參數(shù)的影響標(biāo)準(zhǔn)粒子群算法中主要的參數(shù)變量為（慣性權(quán)值）， ，（加速因子），本文重點(diǎn)對(duì)參數(shù)， ，做數(shù)據(jù)統(tǒng)計(jì)實(shí)驗(yàn)。還有保持，不變對(duì)分別取不同值分析其對(duì)算法結(jié)果影響。本文將應(yīng)用研究分典型理論問題研究和實(shí)際工業(yè)應(yīng)用兩大類。實(shí)際工業(yè)應(yīng)用有：電力系統(tǒng)、濾波器設(shè)計(jì)、自動(dòng)控制、數(shù)據(jù)聚類、模式識(shí)別與圖像處理、化工、機(jī)械、通信、機(jī)器人、經(jīng)濟(jì)、生物信息、醫(yī)學(xué)、任務(wù)分配、TSP等等。如果想較快地對(duì)PSO有一個(gè)比較全面的了解，借助網(wǎng)絡(luò)空間的電子資源無疑是不二之選。這里介紹當(dāng)今PSO研究領(lǐng)域較有影響的一個(gè)網(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”等等，對(duì)PSO研究人員很有啟發(fā)。分別對(duì)其利用單因子方差分析法，說明不同參數(shù)水平對(duì)算法速率性能的影響。最后說明粒子群優(yōu)化算法在實(shí)際中的應(yīng)用以及對(duì)未來展望，最后總結(jié)了算法的優(yōu)缺點(diǎn)，附錄里面附有測(cè)試程序和測(cè)試函數(shù)。它與其他進(jìn)化算法一樣，也是基于“種群”和“進(jìn)化”的概念，通過個(gè)體間的協(xié)作與競(jìng)爭(zhēng)，實(shí)現(xiàn)復(fù)雜空間最優(yōu)解的搜索；同時(shí)，PSO又不像其他進(jìn)化算法那樣對(duì)個(gè)體進(jìn)行交叉、變異、選擇等進(jìn)化算子操作，而是將群體(swarm)中的個(gè)體看作是在D維搜索空間中沒有質(zhì)量和體積的粒子(particle)，每個(gè)粒子以一定的速度在解空間運(yùn)動(dòng)，并向自身歷史最佳位置pbest和鄰域歷史最佳位置聚集，實(shí)現(xiàn)對(duì)候選解的進(jìn)化。自然界中各種生物體均具有一定的群體行為，而人工生命的主要研究領(lǐng)域之一是探索自然界生物的群體行為，從而在計(jì)算機(jī)上構(gòu)建其群體模型。仿真中僅利用上面三條簡(jiǎn)單的規(guī)則，就可以非常接近的模擬出鳥群飛行的現(xiàn)象。在仿真中，一開始每一只鳥都沒有特定的飛行目標(biāo)，只是使用簡(jiǎn)單的規(guī)則確定自己的飛行方向和飛行速度（每一只鳥都試圖留在鳥群中而又不相互碰撞），當(dāng)有一只鳥飛到棲息地時(shí)，它周圍的鳥也會(huì)跟著飛向棲息地，這樣，整個(gè)鳥群都會(huì)落在棲息地。他們的模型和仿真算法主要對(duì)Frank Heppner的模型進(jìn)行了修正，以使粒子飛向解空間并在最好解處降落。自20世紀(jì)30年代以來，社會(huì)心理學(xué)的發(fā)展揭示：我們都是魚群或鳥群聚集行為的遵循者。人類的自然行為和魚群及鳥群并不類似，而人類在高維認(rèn)知空間中的思維軌跡卻與之非常類似。 算法原理PSO從這種模型中得到啟示并用于解決優(yōu)化問題。所有的粒子都有一個(gè)由被優(yōu)化的函數(shù)決定的適值( fitness value) ，每個(gè)粒子還有一個(gè)速度決定它們飛翔的方向和距離。PSO初始化為一群隨機(jī)粒子(隨機(jī)解)，然后通過迭代找到最優(yōu)解。另外也可以不用整個(gè)種群而只是用其中一部分作為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。第個(gè)粒子的“飛行 ”速度也是一個(gè)維的向量，記為 。整個(gè)粒子群迄今為止搜索到的最優(yōu)位置為全局極值，記為 在找到這兩個(gè)最優(yōu)值時(shí)，粒子根據(jù)如下的公式()和( )來更新自己的速度和位置[12]： () (2. 2)其中：和為學(xué)習(xí)因子，也稱加速常數(shù)(acceleration constant)，和為[0，1]范圍內(nèi)的均勻隨機(jī)數(shù)。是粒子的速度，是常數(shù)，由用戶設(shè)定用來限制粒子的速度。 基本粒子群算法流程算法的流程如下：① 初始化粒子群，包括群體規(guī)模，每個(gè)粒子的位置和速度② 計(jì)算每個(gè)粒子的適應(yīng)度值；③ 對(duì)每個(gè)粒子，用它的適應(yīng)度值和個(gè)體極值比較，如果 ，則用替換掉；④ 對(duì)每個(gè)粒子，用它的適應(yīng)度值和全局極值比較，如果則用替；⑤ 根據(jù)公式（），（）更新粒子的速度和位置 ；⑥ 如果滿足結(jié)束條件(誤差足夠好或到達(dá)最大循環(huán)次數(shù))退出，否則返回②。公式() 表示了粒子在求解空間中，由于相互影響導(dǎo)致的運(yùn)動(dòng)位置調(diào)整。粒子群優(yōu)化算法初期，其解群隨進(jìn)化代數(shù)表現(xiàn)了更強(qiáng)的隨機(jī)性，正是由于其產(chǎn)生了下一代解群的較大的隨機(jī)性，以及每代所有解的“信息”的共享性和各個(gè)解的“自我素質(zhì)”的提高。例如對(duì)于問題求解， 粒子可以直接編碼為 ，而適應(yīng)度函數(shù)就是 。與遺傳算法相比，粒子群優(yōu)化算法的信息共享機(jī)制是很不同的:在遺傳算法中，染色體互相共享信息，所以整個(gè)種群的移動(dòng)是比較均勻的向最優(yōu)區(qū)域移動(dòng)。 帶慣性權(quán)重的粒子群算法探索是偏離原來的尋優(yōu)軌跡去尋找一個(gè)更好的解，探索能力是一個(gè)算法的全局搜索能力。如何確定局部搜索能力和全局搜索能力的比例，對(duì)一個(gè)問題的求解過程很重要。其進(jìn)化過程為： （） （）在式()中，第一部分表示粒子先前的速度，用于保證算法的全局收斂性能；第二部分、第三部分則是使算法具有局部收斂能力。較大，全局收斂能力強(qiáng)，局部收斂能力弱；較小，局部收斂能力強(qiáng)，全局收斂能力弱。實(shí)驗(yàn)結(jié)果表明，在之間時(shí)，PSO算法有更快的收斂速度，而當(dāng)時(shí)，算法則易陷入局部極值。目前PSO算法還沒有成熟的理論分析，少部分研究者對(duì)算法的收斂性進(jìn)行了分析，大部分研究者在算法的結(jié)構(gòu)和性能改善方面進(jìn)行研究，包括參數(shù)分析，拓?fù)浣Y(jié)構(gòu)，粒子多樣性保持，算法融合和性能比較等。由于PSO中粒子向自身歷史最佳位置和鄰域或群體歷史最佳位置聚集，形成粒子種群的快速趨同效應(yīng)，容易出現(xiàn)陷入局部極值、早熟收斂或停滯現(xiàn)象[1214]。為了克服上述不足，各國研究人員相繼提出了各種改進(jìn)措施。 粒子群初始化 研究表明，粒子群初始化對(duì)算法性能產(chǎn)生一定影響[16]。 鄰域拓?fù)?根據(jù)粒子鄰域是否為整個(gè)群體，PSO分為全局模型和局部模型 [20]。Kennedy[21]指出，模型雖然具有較快的收斂速度，但更容易陷入局部極值。根據(jù)現(xiàn)有的研究成果，本文將鄰域分為空間鄰域(spatial neighborhood)、性能空間(performance space)鄰域和社會(huì)關(guān)系鄰域(sociometric neighborhood)。性能空間指根據(jù)性能指標(biāo)(如適應(yīng)度、目標(biāo)函數(shù)值)劃分的鄰域，如文獻(xiàn)[24]采用適應(yīng)度距離比值(fitnessdistanceratio)來選擇粒子的相鄰粒子。針對(duì)不同的優(yōu)化問題，這些拓?fù)涞男阅鼙憩F(xiàn)各異；但總的來說，隨機(jī)拓?fù)渫鶎?duì)大多數(shù)問題能表現(xiàn)出較好的性能，其次是馮－諾以曼拓?fù)鋄22]。此外，文獻(xiàn)[21]提出動(dòng)態(tài)社會(huì)關(guān)系拓?fù)?Dynamic sociometry)，初始階段粒子采用環(huán)形拓?fù)?ringtype topology)，隨著迭代次數(shù)的增加，逐漸增加粒子間連接，最后形成星形拓?fù)?startype topology)。文獻(xiàn)[19]引入了子種群，子種群間通過繁殖(Breeding)實(shí)現(xiàn)信息交流。X. Li[21]根據(jù)粒子相似性動(dòng)態(tài)地將粒子群體按種類劃分為多個(gè)子種群，再以每個(gè)子種群的最佳個(gè)體作為每個(gè)粒子的鄰域最佳位置。文獻(xiàn)[13]采用主－仆模型(master–slaver model)，其中包含一個(gè)主群體，多個(gè)仆群體，仆群體進(jìn)行獨(dú)立的搜索，主群體在仆群體提供的最佳位置基礎(chǔ)上開展搜索。文獻(xiàn)[15]采用多群體進(jìn)行解的搜索。 在標(biāo)準(zhǔn)的PSO算法中，所有粒子僅僅向自身和鄰域的歷史最佳位置聚集，而沒有向鄰域內(nèi)其他個(gè)體(即使這些個(gè)體很優(yōu)秀)學(xué)習(xí)，造成信息資源的浪費(fèi)，甚至因此而陷入局部極值；考慮到此因素，Kennedy 等人[17]提出了全信息粒子群(fully informed particle swarm, FIPS)，在FIPS中，每個(gè)粒子除了自身和鄰域最佳歷史位置外，還學(xué)習(xí)鄰域內(nèi)其他粒子的成功經(jīng)驗(yàn)。基于這方面的考慮，Van den Bergh等人[18]提出了協(xié)作PSO(Cooperative PSO)算法，其基本思路就是采用協(xié)作行為，利用多個(gè)群體分別在目標(biāo)搜索空間中的不同維度上進(jìn)行搜索，也就是一個(gè)優(yōu)化解由多個(gè)獨(dú)立群體協(xié)作完成，每個(gè)群體只負(fù)責(zé)優(yōu)化這個(gè)解矢量部分維上的分量。近來，ElAbd 等人[20]結(jié)合文獻(xiàn)[18,19]的技術(shù)，提出了等級(jí)協(xié)作PSO(hierarchal cooperative PSO)。J. Liang 等人[4]提出了一種既可以進(jìn)行D維空間搜索、又能在不同維上選擇不同學(xué)習(xí)對(duì)象的新的學(xué)習(xí)策略，稱為全面學(xué)習(xí)PSO (Comprehensive Learning Particle Swarm Optimizer，CLPSO)。CLPSO的速度更新公式為： （）其中為加速因子，為[0,1]內(nèi)的均勻隨機(jī)數(shù)，表示粒子在第維的學(xué)習(xí)對(duì)象，它通過下面的策略決定：產(chǎn)生[0,1]內(nèi)的均勻隨機(jī)數(shù)，如果該隨機(jī)數(shù)大于為粒子預(yù)先給定的學(xué)習(xí)概率，則學(xué)習(xí)對(duì)象為自身歷史最佳位置；否則，從種群內(nèi)隨機(jī)選取兩個(gè)個(gè)體，按錦標(biāo)賽選擇(tournament selection)策略選出兩者中最好的歷史最佳位置作為學(xué)習(xí)對(duì)象。以上的各種鄰域結(jié)構(gòu)，無論是微觀拓?fù)溥€是宏觀鄰域，也無論是在整個(gè)搜索空間進(jìn)行信息交流還是以空間的不同維分量為單位協(xié)作搜索，都不主動(dòng)改變鄰域狀態(tài)，而只是在給定的鄰域內(nèi)進(jìn)行學(xué)習(xí)交流，本文稱之為PSO的被動(dòng)局部模型。Blackwell 等人[3]將粒子分為自然粒子和帶電粒子，當(dāng)帶電粒子過于接近時(shí)產(chǎn)生斥力，使之分開以提高粒子多樣性；L248。 混合策略