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