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

1、 2021-8-1 2 粒子群算法的研究背景 粒子群算法(Particle Swarm Optimization，簡稱PSO)，是一種基 于群體智能的進(jìn)化計(jì)算方法。PSO由Kennedy和Eberhart博士于 1995年提出。 粒子群算法源于復(fù)雜適應(yīng)系統(tǒng)（Complex Adaptive System,CAS）。CAS理論于1994年正式提出，CAS中的成員 稱為主體。比如研究鳥群系統(tǒng)，每個鳥在這個系統(tǒng)中就稱為 主體。主體有適應(yīng)性，它能夠與環(huán)境及其他的主體進(jìn)行交流， 并且根據(jù)交流的過程“學(xué)習(xí)”或“積累經(jīng)驗(yàn)”改變自身結(jié)構(gòu) 與行為。整個系統(tǒng)的演變或進(jìn)化包括：新層次的產(chǎn)生（小鳥 的出生）；分化和多

2、樣性的出現(xiàn)（鳥群中的鳥分成許多小的 群）；新的主題的出現(xiàn)（鳥尋找食物過程中，不斷發(fā)現(xiàn)新的 食物）。 2021-8-1 3 PSO的基本概念源于對鳥群捕食行為的研究： 一群鳥在隨機(jī)搜尋食物，在這個區(qū)域里只有一塊食物，所有鳥 都不知道食物在哪里。但是他們知道當(dāng)前的位置離食物還有多 遠(yuǎn)。 那么找到食物的最優(yōu)策略是什么呢?最簡單有效的就是搜尋目 前離食物最近的鳥的周圍區(qū)域。 粒子群算法的基本原理 2021-8-1 4 PSO算法就從這種生物種群行為特性中得到啟發(fā)并用于求解優(yōu)化 問題。 在PSO中，把一個優(yōu)化問題看作是在空中覓食的鳥群，那么“食 物”就是優(yōu)化問題的最優(yōu)解，而在空中飛行的每一只覓食的 “鳥

3、”就是PSO算法中在解空間中進(jìn)行搜索的一個“粒 子”(Particle)。 “群”(Swarm)的概念來自于人工生命，滿足人工生命的五個基 本原則。因此PSO算法也可看作是對簡化了的社會模型的模擬， 這其中最重要的是社會群體中的信息共享機(jī)制，這是推動算法 的主要機(jī)制。 2021-8-1 5 粒子在搜索空間中以一定的速度飛行，這個速度根據(jù)它本身的 飛行經(jīng)驗(yàn)和同伴的飛行經(jīng)驗(yàn)來動態(tài)調(diào)整。所有的粒子都有一個 被目標(biāo)函數(shù)決定的適應(yīng)值(fitness value)，這個適應(yīng)值用于評價 粒子的“好壞”程度。 每個粒子知道自己到目前為止發(fā)現(xiàn)的最好位置(particle best， 記為pbest)和當(dāng)前的位置

4、，pbest就是粒子本身找到的最優(yōu)解， 這個可以看作是粒子自己的飛行經(jīng)驗(yàn)。 除此之外，每個粒子還知道到目前為止整個群體中所有粒子發(fā) 現(xiàn)的最好位置(global best，記為gbest)，gbest是在pbest中的最 好值，即是全局最優(yōu)解，這個可以看作是整個群體的經(jīng)驗(yàn)。 2021-8-1 6 每個粒子使用下列信息改變自己的當(dāng)前位置： (1)當(dāng)前位置； (2)當(dāng)前速度； (3)當(dāng)前位置與自己最好位置之間的距離； (4)當(dāng)前位置與群體最好位置之間的距離。 2021-8-1 7 用隨機(jī)解初始化一群隨機(jī)粒子，然后通過迭代找到最優(yōu)解。在 每一次迭代中，粒子通過跟蹤兩個“極值”來更新自己： 一個是粒子本

5、身所找到的最好解，即個體極值(pbest)，另一個 極值是整個粒子群中所有粒子在歷代搜索過程中所達(dá)到的最優(yōu) 解(gbest)即全局極值。 找到這兩個最好解后，接下來是PSO中最重要的“加速”過程， 每個粒子不斷地改變其在解空間中的速度，以盡可能地朝pbest 和gbest所指向的區(qū)域“飛”去。 粒子群算法的基本思想 2021-8-1 8 假設(shè)在一個N維空間進(jìn)行搜索，粒子i的信息可用兩個N維向量 來表示： 第i個粒子的位置可表示為 速度為 在找到兩個最優(yōu)解后，粒子即可根據(jù)下式來更新自己的速度和 位置： 粒子群優(yōu)化算法的一般數(shù)學(xué)模型 11 k id k id k id vxx )()( 2211

6、1k id k d kk id k id kk id k id xGbestrandcxPbestrandcvv ：是粒子i在第k次迭代中第d維的速度； ：是粒子i在第k次迭代中第d維的當(dāng)前位置； k id v k id x T iNiii xxxx, 21 T iNiii vvvv, 21 (1) (2) 2021-8-1 9 i=1，2，3，M：種群大小。 c1和c2：學(xué)習(xí)因子，或稱加速系數(shù)，合適的c1和c2既可加快收 斂又不易陷入局部最優(yōu)。 rand1和rand2：是介于0,1之間的隨機(jī)數(shù)。 是粒子i在第d維的個體極值點(diǎn)的位置； 是整個種群在第d維的全局極值點(diǎn)的位置。 k id Pbes

7、t k d Gbest 最大速度vmax：決定了問題空間搜索的力度，粒子的每一維速 度vid都會被限制在vdmax，+vdmax 之間，假設(shè)搜索空間的第d 維定義為區(qū)間xdmax，+xdmax ，則通常vdmax=kxdmax ， 0.1k1.0，每一維都用相同的設(shè)置方法。 2021-8-1 10 公式(1)主要通過三部分來計(jì)算粒子i更新的速度： 粒子i前一時刻的速度 ； 粒子當(dāng)前位置與自己歷史最好位置之間的距離 ； 粒子當(dāng)前位置與群體最好位置之間的距離 。 粒子通過公式(2)計(jì)算新位置的坐標(biāo)。 k id v )( k id k id xPbest )( k id k d xGbest 更新公

8、式的意義 2021-8-1 11 式(1)的第一部分稱為動量部分，表示粒子對當(dāng)前自身運(yùn)動狀 態(tài)的信任，為粒子提供了一個必要動量，使其依據(jù)自身速度進(jìn) 行慣性運(yùn)動； 第二部分稱為個體認(rèn)知部分，代表了粒子自身的思考行為，鼓 勵粒子飛向自身曾經(jīng)發(fā)現(xiàn)的最優(yōu)位置； 第三部分稱為社會認(rèn)知部分，表示粒子間的信息共享與合作， 它引導(dǎo)粒子飛向粒子群中的最優(yōu)位置。 公式(1)的第一項(xiàng)對應(yīng)多樣化(diversification)的特點(diǎn)，第二項(xiàng)、 第三項(xiàng)對應(yīng)于搜索過程的集中化(intensification)特點(diǎn)，這三項(xiàng)之 間的相互平衡和制約決定了算法的主要性能。 2021-8-1 12 參數(shù)意義 (1)粒子的長度N：

9、問題解空間的維數(shù)。 (2)粒子種群大小M：粒子種群大小的選擇視具體問題而定，但 是一般設(shè)置粒子數(shù)為20-50。對于大部分的問題10個粒子已經(jīng)可 以取得很好的結(jié)果，不過對于比較難的問題或者特定類型的問 題，粒子的數(shù)量可以取到100或200。另外，粒子數(shù)目越多，算 法搜索的空間范圍就越大，也就更容易發(fā)現(xiàn)全局最優(yōu)解。當(dāng)然， 算法運(yùn)行的時間也較長。 (3)加速常數(shù)c1和 c2：分別調(diào)節(jié)向Pbest和Gbest方向飛行的最大 步長，決定粒子個體經(jīng)驗(yàn)和群體經(jīng)驗(yàn)對粒子運(yùn)行軌跡的影響， 反映粒子群之間的信息交流。 如果c1=0，則粒子只有群體經(jīng)驗(yàn)，它的收斂速度較快，但容易 陷入局部最優(yōu)； 2021-8-1 1

10、3 如果c2 = 0，則粒子沒有群體共享信息，一個規(guī)模為M的群體等 價于運(yùn)行了M個各行其是的粒子，得到解的幾率非常小，因此 一般設(shè)置c1 = c2 。這樣，個體經(jīng)驗(yàn)和群體經(jīng)驗(yàn)就有了相同重要 的影響力，使得最后的最優(yōu)解更精確。 改變這些常數(shù)會改變系統(tǒng)的“張力”，較低的c1 和 c2值使得粒 子徘徊在遠(yuǎn)離目標(biāo)的區(qū)域，較高的c1 和 c2值產(chǎn)生陡峭的運(yùn)動或 越過目標(biāo)區(qū)域。 Shi和Eberhart建議，為了平衡隨機(jī)因素的作用，一般情況下設(shè) 置c1 c2，大部分算法都采用這個建議。 2021-8-1 14 (4)粒子的最大速度vmax ：粒子的速度在空間中的每一維上都有 一個最大速度限制值vdmax

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

12、16 程序偽代碼 For each particle Initialize particle End Do For each particle Calculate fitness value If the fitness value is better than the best fitness value (pbest) in history set current value as the new pbest End Choose the particle with the best fitness value of all the particles as the gbest For e

13、ach particle Calculate particle velocity according equation (1) Update particle position according equation (2) End While maximum iterations or minimum error criteria is not attained 2021-8-1 17 PSO的各種改進(jìn)算法 PSO收斂速度快，特別是在算法的早期，但也存在著精度較低， 易發(fā)散等缺點(diǎn)。 若加速系數(shù)、最大速度等參數(shù)太大，粒子群可能錯過最優(yōu)解， 算法不收斂； 而在收斂的情況下，由于所有的粒子都向最優(yōu)解

14、的方向飛去， 所以粒子趨向同一化（失去了多樣性），使得后期收斂速度 明顯變慢，同時算法收斂到一定精度時，無法繼續(xù)優(yōu)化，所 能達(dá)到的精度也不高。 因此很多學(xué)者都致力于提高PSO算法的性能。 2021-8-1 18 慣性權(quán)重法（Inertia Weight） 慣性權(quán)重法是由Shi等提出的，其速度更新公式為： )()( 2211 1k id k d kk id k id kk id k id xGbestrandcxPbestrandcvv 為非負(fù)數(shù)，稱為慣性因子，慣性權(quán)重，是控制速度的權(quán)重 如果沒有公式(1)的第一部分，PSO的搜索過程是一個通過迭代 搜索空間逐漸收縮的過程，展現(xiàn)出一種局部搜索(e

15、xploitation) 能力；反之，如果增加了第一部分，粒子就有能力擴(kuò)展搜索空 間，展現(xiàn)出一種全局搜索(exploration)的能力。在搜索過程中， 全局搜索能力與局部搜索能力的平衡對于算法的成功起著至關(guān) 重要的作用。 引入一個慣性權(quán)重到公式(1)， 是與前一次速度有關(guān)的一個 比例因子，較大的可以加強(qiáng)PSO的全局探測能力，而較小的 能加強(qiáng)局部搜索能力，也就是這個執(zhí)行了全局搜索和局部搜 索之間的平衡角色。 (3) 2021-8-1 19 (1)線性調(diào)整的策略 允許的最大速度vmax實(shí)際上作為一個約束，控制PSO能夠具有的 最大全局搜索能力。如果vmax較小，那么最大的全局搜索能力將 被限制，

16、不論慣性權(quán)重的大小，PSO只支持局部搜索；如果設(shè) 置vmax較大，那么PSO通過選擇 ，有一個可供很多選擇的搜索 能力范圍。 由此可以看出，允許的最大速度間接地影響全局搜索能力，而 慣性權(quán)重直接影響全局搜索能力，所以希望找到一個非常好的 慣性權(quán)重來達(dá)到全局搜索和局部搜索之間的平衡。 類似于人的“原動力”，如果原動力比較大，當(dāng)達(dá)到某個目 標(biāo)的時候，會繼續(xù)向前實(shí)現(xiàn)更高的目標(biāo)：如果原動力較小，到 達(dá)某個目標(biāo)就停滯。 2021-8-1 20 Shi和Eberhart提出了一種隨著算法迭代次數(shù)的增加慣性權(quán)重線 性下降的方法。 慣性權(quán)重的計(jì)算公式如下： maxmin max max n k k max和m

17、in分別表示權(quán)重的最大及最小值，kn為當(dāng)前迭代次數(shù)， kmax表示最大迭代次數(shù)。 文獻(xiàn)試驗(yàn)了將設(shè)置為從0.9到0.4的線性下降，使得PSO在開 始時探索較大的區(qū)域，較快地定位最優(yōu)解的大致位置，隨著 逐漸減小，粒子速度減慢，開始精細(xì)的局部搜索。該方法使 PSO更好地控制exploration和exploitation能力，加快了收斂速 度，提高了算法的性能，稱之為權(quán)重線性下降的粒子群算法， 簡記為LDW(Linearly Decreasing Inertia Weight)。 2021-8-1 21 (2)模糊調(diào)整的策略 PSO搜索過程是一個非線性的復(fù)雜過程，讓線性下降的方法 并不能正確反映真實(shí)

18、的搜索過程。因而，Shi等提出用模糊推 理機(jī)來動態(tài)地調(diào)整慣性權(quán)重的技術(shù)。 即構(gòu)造一個2輸入、1輸出的模糊推理機(jī)來動態(tài)地修改慣性因子。 模糊推理機(jī)的兩個輸入分別是當(dāng)前值，以及規(guī)范化后的當(dāng)前 最好性能評價值(The Normalized Current Best Performance Evaluation，NCBPE)；而輸出是的增量。 CBPE (The Current Best Performance Evaluation，CBPE) 是PSO 迄今為止發(fā)現(xiàn)的最好候選解的性能測度。由于不同的優(yōu)化問題 有不同的性能評價值范圍，所以為了讓該模糊系統(tǒng)有廣泛的適 用性，通常使用標(biāo)準(zhǔn)化的CBPE (N

19、CBPE)。 2021-8-1 22 假定優(yōu)化問題為最小化問題，則規(guī)范化后的評價值 其中，CBPEmax和CBPEmin分別是CBPE可能取值的上下限，其 值根據(jù)具體問題而定，且需事先得知或者可估計(jì)，這使得模糊 自適應(yīng)策略的實(shí)現(xiàn)較為困難，無法廣泛使用，但其與線性減小 策略相比，具有更好的性能。 minmax min CBPECBPE CBPECBPE NCBPE 2021-8-1 23 粒子群算法的優(yōu)缺點(diǎn)分析粒子群算法的優(yōu)缺點(diǎn)分析 l PSO算法沒有交叉和變異運(yùn)算，依靠粒子速度完成 搜索，并且在迭代進(jìn)化中只有最優(yōu)的粒子把信息傳 遞給其它粒子，搜索速度快； l PSO算法具有記憶性，粒子群體的歷

20、史最好位置可 以記憶并傳遞給其它粒子； l 需調(diào)整的參數(shù)較少，結(jié)構(gòu)簡單，易于工程實(shí)現(xiàn)； l 采用實(shí)數(shù)編碼，直接由問題的解決定，問題解的變 量數(shù)直接作為粒子的維數(shù)。 （1）粒子群算法的優(yōu)點(diǎn)）粒子群算法的優(yōu)點(diǎn) 2021-8-1 24 （2）粒子群算法的缺點(diǎn)）粒子群算法的缺點(diǎn) l 缺乏速度的動態(tài)調(diào)節(jié)，容易陷入局部最優(yōu)，導(dǎo)致收 斂精度低和不易收斂； l 不能有效解決離散及組合優(yōu)化問題； l 不能有效求解一些非直角坐標(biāo)系描述問題，如有關(guān) 能量場或場內(nèi)粒子運(yùn)動規(guī)律的求解問題(這些求解 空間的邊界大部分是基于極坐標(biāo)、球坐標(biāo)或柱坐標(biāo) 的)； l 參數(shù)控制，對于不同的問題，如何選擇合適的參數(shù) 來達(dá)到最優(yōu)效果。

21、2021-8-1 25 粒子群算法的應(yīng)用范圍粒子群算法的應(yīng)用范圍 函數(shù)優(yōu)化 PSO算法最初被應(yīng)用于函數(shù)優(yōu)化，但 后來的學(xué)者經(jīng)過研究發(fā)現(xiàn)，粒子群算法在解決一 些經(jīng)典的函數(shù)優(yōu)化問題，甚至一些非線性函數(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)用在如下幾個方 面： 2021-8-1 26 神經(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ù)測等取 得了較高的成功率。 工程領(lǐng)域應(yīng)用 很多工程中的實(shí)際問題，本質(zhì)上都是 優(yōu)化問題，因此PSO算法自然就可以應(yīng)用到實(shí)際的工程 問題來，將PSO肅反和BP神經(jīng)網(wǎng)絡(luò)算法相結(jié)合訓(xùn)練神經(jīng) 網(wǎng)絡(luò)已用于對電動汽車燃料電池組充