1、第二章粒子群優(yōu)化算法粒子群優(yōu)化（PSO）是一種基于群體智能的數(shù)值優(yōu)化算法，由社會(huì)心理學(xué)家JamesKennedy和電氣工程師RussellEberhart于1995年提出。自PSO誕生以來(lái)，它在許多方面都得到了改進(jìn)，這一部分將介紹基本的粒子群優(yōu)化算法原理和過(guò)程。2.1 粒子群優(yōu)化粒子群優(yōu)化（PSO）是一種群智能算法，其靈感來(lái)自于鳥(niǎo)類(lèi)的群集或魚(yú)群學(xué)習(xí)，用于解決許多科學(xué)和工程領(lǐng)域中出現(xiàn)的非線性、非凸性或組合優(yōu)化問(wèn)題。圖1RusselEberhart和JamesKennedy2.1.1 算法思想許多鳥(niǎo)類(lèi)都是群居性的，并由各種原因形成不同的鳥(niǎo)群。鳥(niǎo)群可能大小不同，出現(xiàn)在不同的季節(jié)，甚至可能由群體中可以

2、很好合作的不同物種組成。更多的眼睛和耳朵意味著有更多的及時(shí)發(fā)現(xiàn)食物和捕食者的機(jī)會(huì)。鳥(niǎo)群在許多方面對(duì)其成員的生存總是有益的：覓食：社會(huì)生物學(xué)家E.O.Wilson說(shuō)，至少在理論上，群體中的個(gè)體成員可以從其他成員在尋找食物過(guò)程中的發(fā)現(xiàn)和先前的經(jīng)驗(yàn)中獲益1。如果一群鳥(niǎo)的食物來(lái)源是相同的，那么某些種類(lèi)的鳥(niǎo)就會(huì)以一種非競(jìng)爭(zhēng)的方式聚集在一起。這樣，更多的鳥(niǎo)類(lèi)就能利用其他鳥(niǎo)類(lèi)對(duì)食物位置的發(fā)現(xiàn)。抵御捕食者：鳥(niǎo)群在保護(hù)自己免受捕食者侵害方面有很多優(yōu)勢(shì)。更多的耳朵和眼睛意味著更多的機(jī)會(huì)發(fā)現(xiàn)捕食者或任何其他潛在的危險(xiǎn);一群鳥(niǎo)可能會(huì)通過(guò)圍攻或敏捷的飛行來(lái)迷惑或壓制捕食者；在群體中，互相間的警告可以減少任何一只鳥(niǎo)的危險(xiǎn)

3、?？諝鈩?dòng)力學(xué)：當(dāng)鳥(niǎo)類(lèi)成群飛行時(shí)，它們經(jīng)常把自己排成特定的形狀或隊(duì)形。鳥(niǎo)群中鳥(niǎo)的數(shù)量不同，每只鳥(niǎo)煽動(dòng)翅膀時(shí)產(chǎn)生不同的氣流，這都會(huì)導(dǎo)致變化的風(fēng)型，這些隊(duì)形會(huì)充分利用不同的分型，從而使得飛行中的鳥(niǎo)類(lèi)能夠以最節(jié)能的方式利用周?chē)目諝?。粒子群算法的發(fā)展需要模擬鳥(niǎo)群的一些優(yōu)點(diǎn)，然而，為了了解群體智能和粒子群優(yōu)化的一個(gè)重要性質(zhì)，值得提一下是鳥(niǎo)群的一些缺點(diǎn)。當(dāng)鳥(niǎo)類(lèi)成群結(jié)隊(duì)時(shí)，也會(huì)給它們帶來(lái)一些風(fēng)險(xiǎn)。更多的耳朵和眼睛意味著更多的翅膀和嘴，這導(dǎo)致更多的噪音和運(yùn)動(dòng)。在這種情況下，更多的捕食者可以定位鳥(niǎo)群，對(duì)鳥(niǎo)類(lèi)造成持續(xù)的威脅。一個(gè)更大的群體也會(huì)需要更多的食物，這導(dǎo)致更多食物競(jìng)爭(zhēng)，從而可能淘汰群體中一些較弱的鳥(niǎo)類(lèi)。這

4、里需要指出的是，PSO并沒(méi)有模擬鳥(niǎo)類(lèi)群體行為的缺點(diǎn)，因此，在搜索過(guò)程中不允許殺死任何個(gè)體，而在遺傳算法中，一些較弱的個(gè)體會(huì)消亡。在PSO中，所有的個(gè)體都將存活，并在整個(gè)搜索過(guò)程中努力讓自己變得更強(qiáng)大。在粒子群算法中，潛在解的改進(jìn)是合作的結(jié)果，而在進(jìn)化算法中則是因?yàn)楦?jìng)爭(zhēng)。這個(gè)概念使得群體智能不同于進(jìn)化算法。簡(jiǎn)而言之，在進(jìn)化算法中，每一次迭代都有一個(gè)新的種群進(jìn)化，而在群智能算法中，每一代都有個(gè)體使自己變得更好。個(gè)體的身份不會(huì)隨著迭代而改變。Mataric2給出了以下鳥(niǎo)群規(guī)則：1 .安全漫游：鳥(niǎo)類(lèi)飛行時(shí)，不存在相互間或與障礙物間的碰撞;2 .分散：每只鳥(niǎo)都會(huì)與其他鳥(niǎo)保持一個(gè)最小的距離；3 .聚合：每

5、只鳥(niǎo)也會(huì)與其他鳥(niǎo)保持一個(gè)最大的距離；4 .歸巢：所有的鳥(niǎo)類(lèi)都有可能找到食物來(lái)源或巢穴。在設(shè)計(jì)粒子群算法時(shí)，并沒(méi)有采用這四種規(guī)則來(lái)模擬鳥(niǎo)類(lèi)的群體行為。在Kennedy和Eberhart開(kāi)發(fā)的基本粒子群優(yōu)化模型中,對(duì)agent的運(yùn)動(dòng)不遵循安全漫游和分散規(guī)則。換句話說(shuō)，在基本粒子群優(yōu)化算法的運(yùn)動(dòng)過(guò)程中，允許粒子群優(yōu)化算法中的代理盡可能地靠近彼此。而聚合和歸巢在粒子群優(yōu)化模型中是有效的。在粒子群算法中，代理必須在特定的區(qū)域內(nèi)飛行，以便與任何其他代理保持最大距離。這就相當(dāng)于在整個(gè)過(guò)程中，搜索始終停留在搜索空間的邊界內(nèi)或邊界處。第四個(gè)規(guī)則，歸巢意味著組中的任何代理都可以達(dá)到全局最優(yōu)。在PSO模型的發(fā)展過(guò)程

6、中，Kennedy和Eberhart提出了五個(gè)判斷一組代理是否是群體的基本原則：1 .就近原則：代理群體應(yīng)該能夠進(jìn)行簡(jiǎn)單的空間和時(shí)間計(jì)算;2 .質(zhì)量原則：代理群體能夠?qū)Νh(huán)境中的質(zhì)量因素作出反應(yīng)；3 .多響應(yīng)原則：代理群體不應(yīng)在過(guò)于狹窄的通道從事活動(dòng)；4 .穩(wěn)定性原則：代理群體不能每次環(huán)境變化時(shí)就改變其行為模式；5 .適應(yīng)性原則：計(jì)算代價(jià)不大時(shí)，代理群體可以改變其行為模式。2.1.2 粒子群優(yōu)化過(guò)程考慮到這五個(gè)原則，Kennedy和Eberhart開(kāi)發(fā)了一個(gè)用于函數(shù)優(yōu)化的PSO模型。在粒子群算法中，采用隨機(jī)搜索的方法，利用群體智能進(jìn)行求解。換句話說(shuō)，粒子群算法是一種群智能搜索算法。這個(gè)搜索是由一

7、組隨機(jī)生成的可能解來(lái)完成的。這種可能解的集合稱(chēng)為群，每個(gè)可能解都稱(chēng)為粒子。在粒子群優(yōu)化算法中，粒子的搜索受到兩種學(xué)習(xí)方式的影響。每一個(gè)粒子都在向其他粒子學(xué)習(xí)，同時(shí)也在運(yùn)動(dòng)過(guò)程中學(xué)習(xí)自己的經(jīng)驗(yàn)。向他人學(xué)習(xí)可以稱(chēng)為社會(huì)學(xué)習(xí)，而從自身經(jīng)驗(yàn)中學(xué)習(xí)可以稱(chēng)為認(rèn)知學(xué)習(xí)。由于社會(huì)學(xué)習(xí)的結(jié)果，粒子在它的記憶中存儲(chǔ)了群中所有粒子訪問(wèn)的最佳解，我們稱(chēng)之為gbest通過(guò)認(rèn)知學(xué)習(xí)，粒子在它的記憶中儲(chǔ)存了迄今為止它自己訪問(wèn)過(guò)的最佳解，稱(chēng)為pbest任何粒子的方向和大小的變化都是由一個(gè)叫做速度的因素決定的，速度是位置相對(duì)于時(shí)間的變化率。對(duì)于PSO,迭代的是時(shí)間。這樣，對(duì)于粒子群算法，速度可以定義為位置相對(duì)于迭代的變化率。由

8、于迭代計(jì)數(shù)器單位增加，速度v的維數(shù)與位置x相同。對(duì)于D維搜索空間，在時(shí)間步t下群體中的第ith個(gè)粒子由D維向量*=(xt1j|,xD)T來(lái)表示，其速度由另一個(gè)D維向量vt=(vj|mD)t表示。第ith個(gè)粒子訪問(wèn)過(guò)的最優(yōu)解位置用pt=(p；川，品T表示，群體中最優(yōu)粒子的索引為"g：第ith個(gè)粒子的速度和位置分別由下式進(jìn)行更新：v/1=vd+切(Pid-Xid)+c2r2(p；dxd)(1)乂/=乂；+婷(2)其中d=1,2,|,D為維度，i=1,2,III,S為粒子索引，S是群體大小。G和Q為常數(shù)，分別稱(chēng)為認(rèn)知和社交縮放參數(shù)，或簡(jiǎn)單地稱(chēng)為加速系數(shù)。1和七是滿足均勻分布0,1之間的隨機(jī)

9、數(shù)。上面兩個(gè)式子均是對(duì)每個(gè)粒子的每個(gè)維度進(jìn)行單獨(dú)更新，問(wèn)題空間中不同維度之間唯一的聯(lián)系是通過(guò)目標(biāo)函數(shù)引入的，也就是當(dāng)前所找到的最好位置gbest和pbest30PSO的算法流程如下：創(chuàng)建一個(gè)大小為S的D維群體，并初始化對(duì)應(yīng)的速度向量；fort=1to最大迭代次數(shù)dofori=1toSdoford=1toDdo應(yīng)用速度更新等式（1）;應(yīng)用位置更新等式（2）;end計(jì)算位置更新后的適應(yīng)度值；如果需要，更新pbest和gbest的歷史信息；end如果gbest滿足問(wèn)題需求，則終止算法；end算法1：基礎(chǔ)粒子群優(yōu)化算法2.1.3 解讀更新等式速度更新等式（1）的右側(cè)包括三部分3:1 .前一時(shí)間的速度v

10、,可以認(rèn)為是一動(dòng)量項(xiàng)，用于存儲(chǔ)之前的運(yùn)動(dòng)方向，其目的是防止粒子劇烈地改變方向。2 .第二項(xiàng)是認(rèn)知或自我部分，通過(guò)這一項(xiàng)，粒子的當(dāng)前位置會(huì)向其自己的最好位置移動(dòng)，這樣在整個(gè)搜索過(guò)程中，粒子會(huì)記住自己的最佳位置，從而避免自己四處游蕩。這里需要注意的是，p；-x：是一個(gè)方向從x：到ptd的向量，從而將當(dāng)前位置向粒子的最佳位置吸引，兩者的順序不能改變，否則當(dāng)前位置會(huì)遠(yuǎn)離最佳位置。3 .第三項(xiàng)是社交部分，負(fù)責(zé)通過(guò)群體共享信息。通過(guò)該項(xiàng)，粒子向群體中最優(yōu)的個(gè)體移動(dòng)，即每個(gè)個(gè)體向群體中的其他個(gè)體學(xué)習(xí)。同樣兩者應(yīng)該是p；d-£。可以看出，認(rèn)知尺度參數(shù)cl調(diào)節(jié)的是粒子在其最佳位置方向上的最大步長(zhǎng)，而社

11、交尺度參數(shù)c2調(diào)節(jié)的是全局最優(yōu)粒子方向上的最大步長(zhǎng)。圖2給出了粒子在二維空間中運(yùn)動(dòng)的典型幾何圖形。VpdicedPaiirioDVdM油圖2粒子群優(yōu)化過(guò)程中粒子移動(dòng)的幾何說(shuō)明CtrrHPoiiiiojk從更新方程可以看出，Kennedy和Eberhart的PSO設(shè)計(jì)遵循了PSO的五個(gè)基本原則。在粒子群優(yōu)化過(guò)程中，在d維空間中對(duì)一系列時(shí)間步進(jìn)行計(jì)算。在任何時(shí)間步，種群都遵循gbest和pbest的指導(dǎo)方向，即種群對(duì)質(zhì)量因素作出反應(yīng)，從而遵循質(zhì)量原則。由于速度更新方程中有均布隨機(jī)數(shù)r1和r2,在pbest和gbest之間的當(dāng)前位置隨機(jī)分配，這證明了響應(yīng)原理的多樣性。在粒子群優(yōu)化過(guò)程中，只有當(dāng)粒子群

12、從gbest中接收到較好的信息時(shí)，才會(huì)發(fā)生隨機(jī)運(yùn)動(dòng)，從而證明了粒子群優(yōu)化過(guò)程的穩(wěn)定性原則。種群在gbest變化時(shí)發(fā)生變化，因此遵循適應(yīng)性原則。2.2粒子群優(yōu)化中的參數(shù)任何基于種群的算法的收斂速度和尋優(yōu)能力都受其參數(shù)選擇的影響。通常，由于這些算法的參數(shù)高度依賴(lài)于問(wèn)題參數(shù)，因此不可能對(duì)這些算法的參數(shù)設(shè)置給出一般性的建議。但是，已有的理論和/或?qū)嶒?yàn)研究，給出了參數(shù)值的一般范圍。與其他基于種群的搜索算法類(lèi)似，由于在搜索過(guò)程中存在隨機(jī)因素r1和r2,因此通用PSO的參數(shù)調(diào)整一直是一項(xiàng)具有挑戰(zhàn)性的任務(wù)。PSO的基礎(chǔ)版本只需要很少的參數(shù)。本章只討論了4中介紹的PSO基礎(chǔ)版本的參數(shù)一個(gè)基本的參數(shù)是群體規(guī)模，它

13、通常是根據(jù)問(wèn)題中決策變量的數(shù)量和問(wèn)題的復(fù)雜性經(jīng)驗(yàn)地設(shè)置的。一般建議20-50個(gè)粒子。另一個(gè)參數(shù)是縮放因子cl和c20如前所述，這些參數(shù)決定了下一個(gè)迭代中粒子的步長(zhǎng)。也就是說(shuō)，cl和c2決定了粒子的速度。在PSO的基礎(chǔ)版本中，選擇c1=c2=20在這種情況下，粒子s速度的增加是不受控制的，這有利于更快的收斂速度，但不利于更好地利用搜索空間。如果我們令c1=c2>0,那么粒子會(huì)吸引到pbest和gbest的平均值。c1>c2設(shè)置有利于多模態(tài)問(wèn)題，而c2>c1有利于單模態(tài)問(wèn)題。在搜索過(guò)程中，cl和c2的值越小，粒子軌跡越平滑，而c1和c2的值越大，粒子運(yùn)動(dòng)越劇烈，加速度越大。研究人

14、員也提出了自適應(yīng)加速系數(shù)5。停止準(zhǔn)則不僅是粒子群算法的參數(shù)，也是任何基于種群的元啟發(fā)式算法的參數(shù)。常用的停止準(zhǔn)則通?；诤瘮?shù)評(píng)估或迭代的最大次數(shù)，該次數(shù)與算法所花費(fèi)的時(shí)間成正比。一個(gè)更有效的停止準(zhǔn)則是基于算法的搜索能力，如果一個(gè)算法在一定的迭代次數(shù)內(nèi)沒(méi)有顯著地改進(jìn)解，那么應(yīng)該停止搜索。參考文獻(xiàn)1. O.Wilson,E.,Sociobiology:TheNewSynthesis1976.2. JMatari'c,M.andA.Brooks,InteractionandIntelligentBehavior.1999.3. Trelea,I.C.,Theparticleswarmoptimizationalgorithm:convergenceanalysisandparameterselection.InformationProcessingLetters,2003.85(6):p.317-325.4. Kennedy,J.andR.Eberhart.Particleswarmoptimization.in