粒子群算法2015年12月9日粒子群算法2015年12月9日1點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本目錄一.集群智能（SwarmIntelligence）二.粒子群算法（PSO）簡(jiǎn)介三、PSO的一般數(shù)學(xué)模型四、PSO的各種改進(jìn)算法五、PSO的優(yōu)缺點(diǎn)六、PSO的matlab實(shí)現(xiàn)點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本目錄一.集群2一、集群智能（SwarmIntelligence）

Swarm可被描述為一些相互作用相鄰個(gè)體的集合體，蜂群、蟻群、鳥(niǎo)群都是Swarm的典型例子。魚(yú)聚集成群可以有效地逃避捕食者，因?yàn)槿魏我恢霍~(yú)發(fā)現(xiàn)異常都可帶動(dòng)整個(gè)魚(yú)群逃避。螞蟻成群則有利于尋找食物，因?yàn)槿我恢晃浵伆l(fā)現(xiàn)食物都可帶領(lǐng)蟻群來(lái)共同搬運(yùn)和進(jìn)食。一只蜜蜂或螞蟻的行為能力非常有限，它幾乎不可能獨(dú)立存在于自然世界中，而多個(gè)蜜蜂或螞蟻形成的Swarm則具有非常強(qiáng)的生存能力，且這種能力不是通過(guò)多個(gè)個(gè)體之間能力簡(jiǎn)單疊加所獲得的。社會(huì)性動(dòng)物群體所擁有的這種特性能幫助個(gè)體很好地適應(yīng)環(huán)境，個(gè)體所能獲得的信息遠(yuǎn)比它通過(guò)自身感覺(jué)器官所取得的多，其根本原因在于個(gè)體之間存在著信息交互能力。一、集群智能（SwarmIntelligence）3生物社會(huì)學(xué)家E.O.Wilson指出：“至少?gòu)睦碚撋希谒阉魇澄镞^(guò)程中群體中個(gè)體成員可以得益于所有其他成員的發(fā)現(xiàn)和先前的經(jīng)歷。當(dāng)食物源不可預(yù)測(cè)地零星分布時(shí)，這種協(xié)作帶來(lái)的優(yōu)勢(shì)是決定性的，遠(yuǎn)大于對(duì)食物的競(jìng)爭(zhēng)帶來(lái)的劣勢(shì)?！濒~(yú)群覓食模型生物社會(huì)學(xué)家E.O.Wilson指出：“至少?gòu)睦碚撋?二、粒子群算法（PSO）簡(jiǎn)介粒子群算法(particleswarmoptimization，PSO)由Kennedy和Eberhart在1995年提出，該算法模擬鳥(niǎo)集群飛行覓食的行為，鳥(niǎo)之間通過(guò)集體的協(xié)作使群體達(dá)到最優(yōu)目的，是一種基于SwarmIntelligence的優(yōu)化方法。同遺傳算法類似，也是一種基于群體疊代的，但并沒(méi)有遺傳算法用的交叉以及變異，而是粒子在解空間追隨最優(yōu)的粒子進(jìn)行搜索。PSO的優(yōu)勢(shì)在于簡(jiǎn)單容易實(shí)現(xiàn)同時(shí)又有深刻的智能背景，既適合科學(xué)研究，又特別適合工程應(yīng)用，并且沒(méi)有許多參數(shù)需要調(diào)整。RussEberhart二、粒子群算法（PSO）簡(jiǎn)介粒子群算法(partic5產(chǎn)生背景：設(shè)想一個(gè)場(chǎng)景：一群鳥(niǎo)隨機(jī)的分布在一個(gè)區(qū)域中，在這個(gè)區(qū)域里只有一塊食物。所有的鳥(niǎo)都不知道食物在哪里。但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn)。那么找到食物的最優(yōu)策略是什么呢？最簡(jiǎn)單有效的方法就是追尋自己視野中目前離食物最近的鳥(niǎo)。如果把食物當(dāng)作最優(yōu)點(diǎn)，而把鳥(niǎo)離食物的距離當(dāng)作函數(shù)的適應(yīng)度，那么鳥(niǎo)尋覓食物的過(guò)程就可以當(dāng)作一個(gè)函數(shù)尋優(yōu)的過(guò)程。由此受到啟發(fā)，經(jīng)過(guò)簡(jiǎn)化提出了粒子群優(yōu)化算法。產(chǎn)生背景：6基本思想:在PSO中，把一個(gè)優(yōu)化問(wèn)題看作是在空中覓食的鳥(niǎo)群，那么“食物”就是優(yōu)化問(wèn)題的最優(yōu)解，而在空中飛行的每一只覓食的“鳥(niǎo)”就是PSO算法中在解空間中進(jìn)行搜索的一個(gè)“粒子”(Particle)?！叭骸?Swarm)的概念來(lái)自于人工生命，滿足人工生命的五個(gè)基本原則。因此PSO算法也可看作是對(duì)簡(jiǎn)化了的社會(huì)模型的模擬，這其中最重要的是社會(huì)群體中的信息共享機(jī)制，這是推動(dòng)算法的主要機(jī)制?；舅枷?7粒子在搜索空間中以一定的速度飛行，這個(gè)速度根據(jù)它本身的飛行經(jīng)驗(yàn)和同伴的飛行經(jīng)驗(yàn)來(lái)動(dòng)態(tài)調(diào)整。所有的粒子都有一個(gè)被目標(biāo)函數(shù)決定的適應(yīng)值(fitness

value)，這個(gè)適應(yīng)值用于評(píng)價(jià)粒子的“好壞”程度。每個(gè)粒子知道自己到目前為止發(fā)現(xiàn)的最好位置(particlebest，記為pbest)和當(dāng)前的位置，pbest就是粒子本身找到的最優(yōu)解，這個(gè)可以看作是粒子自己的飛行經(jīng)驗(yàn)。除此之外，每個(gè)粒子還知道到目前為止整個(gè)群體中所有粒子發(fā)現(xiàn)的最好位置(globalbest，記為gbest)，gbest是在pbest中的最好值，即是全局最優(yōu)解，這個(gè)可以看作是整個(gè)群體的經(jīng)驗(yàn)。粒子在搜索空間中以一定的速度飛行，這個(gè)速度根據(jù)它本身8(4)(2)(3)(1)當(dāng)前位置當(dāng)前位置與群體最好位置之間的距離當(dāng)前速度當(dāng)前位置與自己最好位置之間的距離每個(gè)粒子使用下列信息改變自己的當(dāng)前位置：(4)(2)(3)(1)當(dāng)前位置當(dāng)前位置與群體最好位置之間的9粒子群算法的基本思想：用隨機(jī)解初始化一群隨機(jī)粒子，然后通過(guò)迭代找到最優(yōu)解。在每一次迭代中，粒子通過(guò)跟蹤兩個(gè)“極值”來(lái)更新自己：一個(gè)是粒子本身所找到的最好解，即個(gè)體極值(pbest)，另一個(gè)極值是整個(gè)粒子群中所有粒子在歷代搜索過(guò)程中所達(dá)到的最優(yōu)解(gbest)即全局極值。找到這兩個(gè)最好解后，接下來(lái)是PSO中最重要的“加速”過(guò)程，每個(gè)粒子不斷地改變其在解空間中的速度，以盡可能地朝pbest和gbest所指向的區(qū)域“飛”去。粒子群算法的基本思想：10三、粒子群優(yōu)化算法的一般數(shù)學(xué)模型假設(shè)在一個(gè)N維空間進(jìn)行搜索，粒子i的信息可用兩個(gè)N維向量來(lái)表示：第i個(gè)粒子的位置可表示為

；速度為；在找到兩個(gè)最優(yōu)解后，粒子即可根據(jù)下式來(lái)更新自己的速度和位置：

：是粒子i在第k次迭代中第d維的速度；

：是粒子i在第k次迭代中第d維的當(dāng)前位置；三、粒子群優(yōu)化算法的一般數(shù)學(xué)模型假設(shè)在一個(gè)N維空間進(jìn)11i=1，2，3…，M：種群大小。c1和c2：學(xué)習(xí)因子（或稱加速系數(shù)），合適的c1和c2既可加快收斂又不易陷入局部最優(yōu)。rand1和rand2：是介于［0,1］之間的隨機(jī)數(shù)。

：是粒子i在第d維的個(gè)體極值點(diǎn)的位置；

：是整個(gè)粒子群在第d維的全局極值點(diǎn)的位置。最大速度vmax：決定了問(wèn)題空間搜索的力度，粒子的每一維速度vid都會(huì)被限制在[-vdmax，+vdmax]之間，粒子每一維的位置xid變化范圍為[-xdmax，+xdmax]

，迭代中若位置和速度超過(guò)邊界范圍則取邊界值。i=1，2，3…，M：種群大小。最大速度vmax：決定了問(wèn)題12“認(rèn)知”部分，僅考慮了粒子自身的經(jīng)驗(yàn)，表示粒子本身的思考“社會(huì)”部分，表示粒子間的群體或領(lǐng)域內(nèi)信息共享粒子先前的速度“認(rèn)知”部分，僅考慮了粒子自身的經(jīng)驗(yàn)，表示粒子本身的思考“社13參數(shù)意義：(1)粒子的長(zhǎng)度N：?jiǎn)栴}解空間的維數(shù)。(2)粒子種群大小M：粒子種群大小的選擇視具體問(wèn)題而定，但是一般設(shè)置粒子數(shù)為20-50。對(duì)于大部分的問(wèn)題10個(gè)粒子已經(jīng)可以取得很好的結(jié)果，不過(guò)對(duì)于比較難的問(wèn)題或者特定類型的問(wèn)題，粒子的數(shù)量可以取到100或200。另外，粒子數(shù)目越多，算法搜索的空間范圍就越大，也就更容易發(fā)現(xiàn)全局最優(yōu)解。當(dāng)然，算法運(yùn)行的時(shí)間也較長(zhǎng)。(3)加速常數(shù)c1和c2：分別調(diào)節(jié)向Pbest和Gbest方向飛行的最大步長(zhǎng)，決定粒子個(gè)體經(jīng)驗(yàn)和群體經(jīng)驗(yàn)對(duì)粒子運(yùn)行軌跡的影響，反映粒子群之間的信息交流。參數(shù)意義：14如果c1=0，則粒子只有群體經(jīng)驗(yàn)，它的收斂速度較快，但容易陷入局部最優(yōu)；如果c2=0，則粒子沒(méi)有群體共享信息，一個(gè)規(guī)模為M的群體等價(jià)于運(yùn)行了M個(gè)各行其是的粒子，得到解的幾率非常小，因此一般設(shè)置c1=c2

。這樣，個(gè)體經(jīng)驗(yàn)和群體經(jīng)驗(yàn)就有了相同重要的影響力，使得最后的最優(yōu)解更精確。改變這些常數(shù)會(huì)改變系統(tǒng)的“張力”，較低的c1

和c2值使得粒子徘徊在遠(yuǎn)離目標(biāo)的區(qū)域，較高的c1

和c2值產(chǎn)生陡峭的運(yùn)動(dòng)或越過(guò)目標(biāo)區(qū)域。Shi和Eberhart建議，為了平衡隨機(jī)因素的作用，一般情況下設(shè)置c1

＝c2，大部分算法都采用這個(gè)建議。粒子群算法(基礎(chǔ)精講)ppt課件15(4)粒子的最大速度vmax

：粒子的速度在空間中的每一維上都有一個(gè)最大速度限制值vdmax

，用來(lái)對(duì)粒子的速度進(jìn)行鉗制，使速度控制在范圍[－vdmax，＋vdmax]內(nèi)，這決定問(wèn)題空間搜索的力度，該值一般由用戶自己設(shè)定。vmax是一個(gè)非常重要的參數(shù)，如果該值太大，則粒子們也許會(huì)飛過(guò)優(yōu)秀區(qū)域；另一方面如果該值太小，則粒子們可能無(wú)法對(duì)局部最優(yōu)區(qū)域以外的區(qū)域進(jìn)行充分的探測(cè)。實(shí)際上，它們可能會(huì)陷入局部最優(yōu)，而無(wú)法移動(dòng)足夠遠(yuǎn)的距離跳出局部最優(yōu)達(dá)到空間中更佳的位置。(5)rand1和rand2是介于［0,1］之間的隨機(jī)數(shù)，增加了粒子飛行的隨機(jī)性。(6)迭代終止條件：一般設(shè)為最大迭代次數(shù)Tmax、計(jì)算精度

或最優(yōu)解的最大停滯步數(shù)△t。(4)粒子的最大速度vmax：粒子的速度在空間中的每一維上16算法流程：算法流程：17四、PSO的各種改進(jìn)算法PSO收斂速度快，特別是在算法的早期，但也存在著精度較低，易發(fā)散等缺點(diǎn)。若加速系數(shù)、最大速度等參數(shù)太大，粒子群可能錯(cuò)過(guò)最優(yōu)解，算法不收斂；而在收斂的情況下，由于所有的粒子都向最優(yōu)解的方向飛去，所以粒子趨向同一化（失去了多樣性），使得后期收斂速度明顯變慢，同時(shí)算法收斂到一定精度時(shí)，無(wú)法繼續(xù)優(yōu)化，所能達(dá)到的精度也不高。因此很多學(xué)者都致力于提高PSO算法的性能。

四、PSO的各種改進(jìn)算法PSO收斂速度快，特別是在18如果沒(méi)有公式(1)的第一部分，PSO的搜索過(guò)程是一個(gè)通過(guò)迭代搜索空間逐漸收縮的過(guò)程，展現(xiàn)出一種局部搜索(exploitation)能力；反之，如果增加了第一部分，粒子就有能力擴(kuò)展搜索空間，展現(xiàn)出一種全局搜索(exploration)的能力。在搜索過(guò)程中，全局搜索能力與局部搜索能力的平衡對(duì)于算法的成功起著至關(guān)重要的作用。引入一個(gè)慣性權(quán)重

到公式(1)，

是與前一次速度有關(guān)的一個(gè)比例因子，較大的

可以加強(qiáng)PSO的全局探測(cè)能力，而較小的

能加強(qiáng)局部搜索能力，也就是這個(gè)

執(zhí)行了全局搜索和局部搜索之間的平衡角色。慣性權(quán)重法是由Shi等提出的，其速度更新公式為：慣性權(quán)重法（InertiaWeight）：

為非負(fù)數(shù)，稱為慣性因子，慣性權(quán)重，是控制速度的權(quán)重如果沒(méi)有公式(1)的第一部分，PSO的搜索過(guò)程是一個(gè)19（1）線性調(diào)整

的策略：允許的最大速度vmax實(shí)際上作為一個(gè)約束，控制PSO能夠具有的最大全局搜索能力。如果vmax較小，那么最大的全局搜索能力將被限制，不論慣性權(quán)重

的大小，PSO只支持局部搜索；如果設(shè)置vmax較大，那么PSO通過(guò)選擇

，有一個(gè)可供很多選擇的搜索能力范圍。由此可以看出，允許的最大速度間接地影響全局搜索能力，而慣性權(quán)重

直接影響全局搜索能力，所以希望找到一個(gè)非常好的慣性權(quán)重來(lái)達(dá)到全局搜索和局部搜索之間的平衡。

類似于人的“原動(dòng)力”，如果原動(dòng)力比較大，當(dāng)達(dá)到某個(gè)目標(biāo)的時(shí)候，會(huì)繼續(xù)向前實(shí)現(xiàn)更高的目標(biāo)：如果原動(dòng)力較小，到達(dá)某個(gè)目標(biāo)就停滯。（1）線性調(diào)整的策略：20Shi和Eberhart提出了一種隨著算法迭代次數(shù)的增加慣性權(quán)重線性下降的方法。慣性權(quán)重的計(jì)算公式如下：

max和

min分別表示權(quán)重的最大及最小值，kn為當(dāng)前迭代次數(shù)，kmax表示最大迭代次數(shù)。文獻(xiàn)試驗(yàn)了將

設(shè)置為從0.9到0.4的線性下降，使得PSO在開(kāi)始時(shí)探索較大的區(qū)域，較快地定位最優(yōu)解的大致位置，隨著

逐漸減小，粒子速度減慢，開(kāi)始精細(xì)的局部搜索。該方法使PSO更好地控制exploration和exploitation能力，加快了收斂速度，提高了算法的性能，稱之為權(quán)重線性下降的粒子群算法，簡(jiǎn)記為L(zhǎng)DW(LinearlyDecreasingInertiaWeight)。Shi和Eberhart提出了一種隨著算法迭代次數(shù)的21(2)模糊調(diào)整

的策略模糊權(quán)重是使用模糊系統(tǒng)來(lái)動(dòng)態(tài)調(diào)節(jié)慣性權(quán)重。下面的文獻(xiàn)給出了一種模糊權(quán)重的設(shè)置方式PSO搜索過(guò)程是一個(gè)非線性的復(fù)雜過(guò)程，讓

線性下降的方法并不能正確反映真實(shí)的搜索過(guò)程。因而，Shi等提出用模糊推理機(jī)來(lái)動(dòng)態(tài)地調(diào)整慣性權(quán)重的技術(shù)。即構(gòu)造一個(gè)2輸入、1輸出的模糊推理機(jī)來(lái)動(dòng)態(tài)地修改慣性因子。模糊推理機(jī)的兩個(gè)輸入分別是當(dāng)前

值，以及規(guī)范化后的當(dāng)前最好性能評(píng)價(jià)值(TheNormalizedCurrentBestPerformanceEvaluation，NCBPE)；而輸出是的

增量。CBPE(TheCurrentBestPerformanceEvaluation，CBPE)是PSO迄今為止發(fā)現(xiàn)的最好候選解的性能測(cè)度。由于不同的優(yōu)化問(wèn)題有不同的性能評(píng)價(jià)值范圍，所以為了讓該模糊系統(tǒng)有廣泛的適用性，通常使用標(biāo)準(zhǔn)化的CBPE(NCBPE)。(2)模糊調(diào)整的策略PSO搜索過(guò)程是一個(gè)非線性的復(fù)22慣性權(quán)重線性下降算法(LDW)是為了提高算法的收斂性能，平衡收斂的全局性和收斂速度，在多峰函數(shù)上效果顯著；

但兩種算法在高維復(fù)雜問(wèn)題尋優(yōu)時(shí)仍然存在早熟收斂、收斂精度比較低的缺點(diǎn)。慣性權(quán)重線性下降算法(LDW)是為了提高算法的收斂性23五、PSO的優(yōu)缺點(diǎn)PSO算法是一種啟發(fā)式的優(yōu)化計(jì)算方法，優(yōu)點(diǎn)：（1）采用實(shí)數(shù)編碼，易于描述，易于理解（2）對(duì)優(yōu)化問(wèn)題定義的連續(xù)性無(wú)特殊要求（3）只有非常少的參數(shù)需要調(diào)整（4）算法實(shí)現(xiàn)簡(jiǎn)單，速度快（5）相對(duì)于其他演化算法，只需要較小的演化群體（6）算法易于收斂（7）無(wú)集中控制約束，不會(huì)因個(gè)體的故障影響整個(gè)問(wèn)題的求解，確保了系統(tǒng)具備很強(qiáng)的魯棒性。五、PSO的優(yōu)缺點(diǎn)PSO算法是一種啟發(fā)式的優(yōu)化計(jì)算方法，優(yōu)點(diǎn)24PSO的缺點(diǎn)：

（1）對(duì)于有多個(gè)局部極值點(diǎn)的函數(shù)，容易陷入到局部極值點(diǎn)中，得不到正確的結(jié)果。

（2）由于缺乏精密搜索方法的配合，PSO方法往往不能得到精確的結(jié)果。

（3）PSO方法提供了全局搜索的可能，但并不能嚴(yán)格證明它在全局最優(yōu)點(diǎn)上的收斂性。PSO的缺點(diǎn)：25六、PSO的matlab實(shí)現(xiàn)計(jì)算如下二元函數(shù)的最小值：（其中自變量x、y的范圍均為[-50,50]）六、PSO的matlab實(shí)現(xiàn)計(jì)算如下二元函數(shù)的最小值：26（1）編寫(xiě)待優(yōu)化函數(shù)程序functionz=test_func(in)nn=size(in);%輸入的是矩陣，即算法中隨機(jī)產(chǎn)生一組x和y，按[x(nn,1),y(nn,1)]排列x=in(:,1);y=in(:,2);

nx=nn(1);

fori=1:nxtemp=0.5*(x(i)-3)^2+0.2*(y(i)-5)^2-0.1;z(i,:)=temp;

end（1）編寫(xiě)待優(yōu)化函數(shù)程序functionz=test_fu27clearclcx_range=[-50,50];%參數(shù)x變化范圍y_range