粒子群算法簡(jiǎn)介優(yōu)缺點(diǎn)及其應(yīng)用課件

2024/2/131粒子群算法12024/2/132粒子群算法的研究背景粒子群算法(ParticleSwarmOptimization，簡(jiǎn)稱PSO)，是一種基于群體智能的進(jìn)化計(jì)算方法。PSO由Kennedy和Eberhart博士于1995年提出。粒子群算法源于復(fù)雜適應(yīng)系統(tǒng)（ComplexAdaptiveSystem,CAS）。CAS理論于1994年正式提出，CAS中的成員稱為主體。比如研究鳥群系統(tǒng)，每個(gè)鳥在這個(gè)系統(tǒng)中就稱為主體。主體有適應(yīng)性，它能夠與環(huán)境及其他的主體進(jìn)行交流，并且根據(jù)交流的過程“學(xué)習(xí)”或“積累經(jīng)驗(yàn)”改變自身結(jié)構(gòu)與行為。整個(gè)系統(tǒng)的演變或進(jìn)化包括：新層次的產(chǎn)生（小鳥的出生）；分化和多樣性的出現(xiàn)（鳥群中的鳥分成許多小的群）；新的主題的出現(xiàn)（鳥尋找食物過程中，不斷發(fā)現(xiàn)新的食物）。22024/2/133PSO的基本概念源于對(duì)鳥群捕食行為的研究：一群鳥在隨機(jī)搜尋食物，在這個(gè)區(qū)域里只有一塊食物，所有鳥都不知道食物在哪里。但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn)。那么找到食物的最優(yōu)策略是什么呢?最簡(jiǎn)單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。粒子群算法的基本原理32024/2/134PSO算法就從這種生物種群行為特性中得到啟發(fā)并用于求解優(yōu)化問題。在PSO中，把一個(gè)優(yōu)化問題看作是在空中覓食的鳥群，那么“食物”就是優(yōu)化問題的最優(yōu)解，而在空中飛行的每一只覓食的“鳥”就是PSO算法中在解空間中進(jìn)行搜索的一個(gè)“粒子”(Particle)?！叭骸?Swarm)的概念來自于人工生命，滿足人工生命的五個(gè)基本原則。因此PSO算法也可看作是對(duì)簡(jiǎn)化了的社會(huì)模型的模擬，這其中最重要的是社會(huì)群體中的信息共享機(jī)制，這是推動(dòng)算法的主要機(jī)制。42024/2/135粒子在搜索空間中以一定的速度飛行，這個(gè)速度根據(jù)它本身的飛行經(jīng)驗(yàn)和同伴的飛行經(jīng)驗(yàn)來動(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)。52024/2/136每個(gè)粒子使用下列信息改變自己的當(dāng)前位置：

(1)當(dāng)前位置；

(2)當(dāng)前速度；

(3)當(dāng)前位置與自己最好位置之間的距離；

(4)當(dāng)前位置與群體最好位置之間的距離。62024/2/137用隨機(jī)解初始化一群隨機(jī)粒子，然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個(gè)“極值”來更新自己：一個(gè)是粒子本身所找到的最好解，即個(gè)體極值(pbest)，另一個(gè)極值是整個(gè)粒子群中所有粒子在歷代搜索過程中所達(dá)到的最優(yōu)解(gbest)即全局極值。找到這兩個(gè)最好解后，接下來是PSO中最重要的“加速”過程，每個(gè)粒子不斷地改變其在解空間中的速度，以盡可能地朝pbest和gbest所指向的區(qū)域“飛”去。粒子群算法的基本思想72024/2/138假設(shè)在一個(gè)N維空間進(jìn)行搜索，粒子i的信息可用兩個(gè)N維向量來表示：第i個(gè)粒子的位置可表示為速度為在找到兩個(gè)最優(yōu)解后，粒子即可根據(jù)下式來更新自己的速度和位置：粒子群優(yōu)化算法的一般數(shù)學(xué)模型

：是粒子i在第k次迭代中第d維的速度；：是粒子i在第k次迭代中第d維的當(dāng)前位置；(1)(2)82024/2/139i=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：決定了問題空間搜索的力度，粒子的每一維速度vid都會(huì)被限制在[－vdmax，+vdmax]之間，假設(shè)搜索空間的第d維定義為區(qū)間[－xdmax，+xdmax]

，則通常vdmax=kxdmax

，0.1

k

1.0，每一維都用相同的設(shè)置方法。92024/2/1310公式(1)主要通過三部分來計(jì)算粒子i更新的速度：粒子i前一時(shí)刻的速度；粒子當(dāng)前位置與自己歷史最好位置之間的距離；粒子當(dāng)前位置與群體最好位置之間的距離。粒子通過公式(2)計(jì)算新位置的坐標(biāo)。更新公式的意義102024/2/1311

式(1)的第一部分稱為動(dòng)量部分，表示粒子對(duì)當(dāng)前自身運(yùn)動(dòng)狀態(tài)的信任，為粒子提供了一個(gè)必要?jiǎng)恿?，使其依?jù)自身速度進(jìn)行慣性運(yùn)動(dòng)；第二部分稱為個(gè)體認(rèn)知部分，代表了粒子自身的思考行為，鼓勵(lì)粒子飛向自身曾經(jīng)發(fā)現(xiàn)的最優(yōu)位置；第三部分稱為社會(huì)認(rèn)知部分，表示粒子間的信息共享與合作，它引導(dǎo)粒子飛向粒子群中的最優(yōu)位置。公式(1)的第一項(xiàng)對(duì)應(yīng)多樣化(diversification)的特點(diǎn)，第二項(xiàng)、第三項(xiàng)對(duì)應(yīng)于搜索過程的集中化(intensification)特點(diǎn)，這三項(xiàng)之間的相互平衡和制約決定了算法的主要性能。112024/2/1312參數(shù)意義(1)粒子的長(zhǎng)度N：?jiǎn)栴}解空間的維數(shù)。(2)粒子種群大小M：粒子種群大小的選擇視具體問題而定，但是一般設(shè)置粒子數(shù)為20-50。對(duì)于大部分的問題10個(gè)粒子已經(jīng)可以取得很好的結(jié)果，不過對(duì)于比較難的問題或者特定類型的問題，粒子的數(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)行軌跡的影響，反映粒子群之間的信息交流。如果c1=0，則粒子只有群體經(jīng)驗(yàn)，它的收斂速度較快，但容易陷入局部最優(yōu)；122024/2/1313如果c2=0，則粒子沒有群體共享信息，一個(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)或越過目標(biāo)區(qū)域。Shi和Eberhart建議，為了平衡隨機(jī)因素的作用，一般情況下設(shè)置c1

＝c2，大部分算法都采用這個(gè)建議。132024/2/1314(4)粒子的最大速度vmax

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

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

或最優(yōu)解的最大停滯步數(shù)△t。142024/2/1315算法流程152024/2/1316程序偽代碼Foreachparticle—InitializeparticleEndDo—Foreachparticle——Calculatefitnessvalue——Ifthefitnessvalueisbetterthanthebestfitnessvalue(pbest)inhistory——setcurrentvalueasthenewpbest—End—Choosetheparticlewiththebestfitnessvalueofalltheparticlesasthegbest—Foreachparticle——Calculateparticlevelocityaccordingequation(1)——Updateparticlepositionaccordingequation(2)—EndWhilemaximumiterationsorminimumerrorcriteriaisnotattained162024/2/1317PSO的各種改進(jìn)算法PSO收斂速度快，特別是在算法的早期，但也存在著精度較低，易發(fā)散等缺點(diǎn)。若加速系數(shù)、最大速度等參數(shù)太大，粒子群可能錯(cuò)過最優(yōu)解，算法不收斂；而在收斂的情況下，由于所有的粒子都向最優(yōu)解的方向飛去，所以粒子趨向同一化（失去了多樣性），使得后期收斂速度明顯變慢，同時(shí)算法收斂到一定精度時(shí)，無法繼續(xù)優(yōu)化，所能達(dá)到的精度也不高。因此很多學(xué)者都致力于提高PSO算法的性能。172024/2/1318慣性權(quán)重法（InertiaWeight）慣性權(quán)重法是由Shi等提出的，其速度更新公式為：

為非負(fù)數(shù)，稱為慣性因子，慣性權(quán)重，是控制速度的權(quán)重如果沒有公式(1)的第一部分，PSO的搜索過程是一個(gè)通過迭代搜索空間逐漸收縮的過程，展現(xiàn)出一種局部搜索((exploitation)能力；反之，如果增加了第一部分，粒子就有能力擴(kuò)展搜索空間，展現(xiàn)出一種全局搜索(exploration)的能力。在搜索過程中，全局搜索能力與局部搜索能力的平衡對(duì)于算法的成功起著至關(guān)重要的作用。引入一個(gè)慣性權(quán)重

到公式(1)，

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

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

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

執(zhí)行了全局搜索和局部搜索之間的平衡角色。(3)182024/2/1319(1)線性調(diào)整

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

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

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

直接影響全局搜索能力，所以希望找到一個(gè)非常好的慣性權(quán)重來達(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)就停滯。192024/2/1320Shi和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在開始時(shí)探索較大的區(qū)域，較快地定位最優(yōu)解的大致位置，隨著

逐漸減小，粒子速度減慢，開始精細(xì)的局部搜索。該方法使PSO更好地控制exploration和exploitation能力，加快了收斂速度，提高了算法的性能，稱之為權(quán)重線性下降的粒子群算法，簡(jiǎn)記為L(zhǎng)DW(LinearlyDecreasingInertiaWeight)。202024/2/1321(2)模糊調(diào)整

的策略

PSO搜索過程是一個(gè)非線性的復(fù)雜過程，讓

線性下降的方法并不能正確反映真實(shí)的搜索過程。因而，Shi等提出用模糊推理機(jī)來動(dòng)態(tài)地調(diào)整慣性權(quán)重的技術(shù)。即構(gòu)造一個(gè)2輸入、1輸出的模糊推理機(jī)來動(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)化問題有不同的性能評(píng)價(jià)值范圍，所以為了讓該模糊系統(tǒng)有廣泛的適用性，通常使用標(biāo)準(zhǔn)化的CBPE(NCBPE)。212024/2/1322假定優(yōu)化問題為最小化問題，則規(guī)范化后的評(píng)價(jià)值其中，CBPEmax和CBPEmin分別是CBPE可能取值的上下限，其值根據(jù)具體問題而定，且需事先得知或者可估計(jì)，這使得模糊自適應(yīng)策略的實(shí)現(xiàn)較為困難，無法廣泛使用，但其與線性減小策略相比，具有更好的性能。222024/2/1323粒子群算法的優(yōu)缺點(diǎn)分析PSO算法沒有交叉和變異運(yùn)算，依靠粒子速度完成搜索，并且在迭代進(jìn)化中只有最優(yōu)的粒子把信息傳遞給其它粒子，搜索速度快；PSO算法具有記憶性，粒子群體的歷史最好位置可以記憶并傳遞給其它粒子；需調(diào)整的參數(shù)較少，結(jié)構(gòu)簡(jiǎn)單，易于工程實(shí)現(xiàn)；采用實(shí)數(shù)編碼，直接由問題的解決定，問題解的變量數(shù)直接作為粒子的維數(shù)。（1）粒子群算法的優(yōu)點(diǎn)232024/2/1324（2）粒子群算法的缺點(diǎn)缺乏速度的動(dòng)態(tài)調(diào)節(jié)，容易陷入局部最優(yōu)，導(dǎo)致收斂精度低和不易收斂；不能有效解決離散及組合優(yōu)化問題；不能有效求解一些非直角坐標(biāo)系描述問題，如有關(guān)能量場(chǎng)或場(chǎng)內(nèi)粒子運(yùn)動(dòng)規(guī)律的求解問題(這些求解空間的邊界大部分是基于極坐標(biāo)、球坐標(biāo)或柱坐標(biāo)的)；參數(shù)控制，對(duì)于不同的問題，如何選擇合適的參數(shù)來達(dá)到最優(yōu)效果。242024/2/1325粒子群算法的應(yīng)用范圍函數(shù)優(yōu)化PSO算法最初被應(yīng)用于函數(shù)優(yōu)化，但后來的學(xué)者經(jīng)過研究發(fā)現(xiàn)，粒子群算法在解決一些經(jīng)典的函數(shù)優(yōu)化問題，甚至一些非線性函數(shù)時(shí)也展示出了良好的性能。粒子群優(yōu)化算法已提出就受到了廣泛的關(guān)注，各種粒子群算法應(yīng)用研究的成果不斷涌現(xiàn)，它的應(yīng)用領(lǐng)域已從最初的函數(shù)優(yōu)化和神經(jīng)網(wǎng)絡(luò)的訓(xùn)練擴(kuò)展到更加開闊的領(lǐng)域，有力地促進(jìn)了粒子群優(yōu)化算法的研究。目前粒子群優(yōu)化算法的主要應(yīng)用在如下幾個(gè)方面：252024/2/1326神經(jīng)網(wǎng)絡(luò)訓(xùn)練將PSO算法用于神經(jīng)網(wǎng)絡(luò)訓(xùn)練也取得了良好的效果，研究表明，PSO是一種很有潛力的神經(jīng)網(wǎng)絡(luò)訓(xùn)練算法，如用于市區(qū)環(huán)境狀況的分析和預(yù)測(cè)等取得了較高的成功率。工程領(lǐng)域應(yīng)用很多工程中的實(shí)際問題，本質(zhì)上都是優(yōu)化問題，因此PSO算法自然就可以應(yīng)用到實(shí)際的工程問題來，將PSO肅反和BP神經(jīng)網(wǎng)絡(luò)算法相結(jié)合