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

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

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

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

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

5、身所找到的最好解，即個體極值(pbest)，另一個 極值是整個粒子群中所有粒子在歷代搜索過程中所達到的最優(yōu) 解(gbest)即全局極值。 找到這兩個最好解后，接下來是PSO中最重要的“加速”過程， 每個粒子不斷地改變其在解空間中的速度，以盡可能地朝pbest 和gbest所指向的區(qū)域“飛”去。 粒子群算法的基本思想 2021-8-1 8 假設在一個N維空間進行搜索，粒子i的信息可用兩個N維向量 來表示： 第i個粒子的位置可表示為 速度為 在找到兩個最優(yōu)解后，粒子即可根據(jù)下式來更新自己的速度和 位置： 粒子群優(yōu)化算法的一般數(shù)學模型 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維的當前位置； 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：學習因子，或稱加速系數(shù)，合適的c1和c2既可加快收 斂又不易陷入局部最優(yōu)。 rand1和rand2：是介于0,1之間的隨機數(shù)。 是粒子i在第d維的個體極值點的位置； 是整個種群在第d維的全局極值點的位置。 k id Pbes

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

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

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

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

11、，用來對粒子的速度進行鉗制，使速 度控制在范圍vdmax，vdmax 內(nèi)，這決定問題空間搜索的力 度，該值一般由用戶自己設定。 vmax是一個非常重要的參數(shù)，如果該值太大，則粒子們也許會飛 過優(yōu)秀區(qū)域；另一方面如果該值太小，則粒子們可能無法對局 部最優(yōu)區(qū)域以外的區(qū)域進行充分的探測。實際上，它們可能會 陷入局部最優(yōu)，而無法移動足夠遠的距離跳出局部最優(yōu)達到空 間中更佳的位置。 (5) rand1和rand2是介于0,1之間的隨機數(shù)，增加了粒子飛行 的隨機性。 (6)迭代終止條件：一般設為最大迭代次數(shù)Tmax、計算精度或最 優(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的各種改進算法 PSO收斂速度快，特別是在算法的早期，但也存在著精度較低， 易發(fā)散等缺點。 若加速系數(shù)、最大速度等參數(shù)太大，粒子群可能錯過最優(yōu)解， 算法不收斂； 而在收斂的情況下，由于所有的粒子都向最優(yōu)解

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

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

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

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

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

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

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

21、2021-8-1 25 粒子群算法的應用范圍粒子群算法的應用范圍 函數(shù)優(yōu)化 PSO算法最初被應用于函數(shù)優(yōu)化，但 后來的學者經(jīng)過研究發(fā)現(xiàn)，粒子群算法在解決一 些經(jīng)典的函數(shù)優(yōu)化問題，甚至一些非線性函數(shù)時 也展示出了良好的性能。 粒子群優(yōu)化算法已提出就受到了廣泛的關(guān)注，各種 粒子群算法應用研究的成果不斷涌現(xiàn)，它的應用領(lǐng) 域已從最初的函數(shù)優(yōu)化和神經(jīng)網(wǎng)絡的訓練擴展到更 加開闊的領(lǐng)域，有力地促進了粒子群優(yōu)化算法的研 究。目前粒子群優(yōu)化算法的主要應用在如下幾個方 面： 2021-8-1 26 神經(jīng)網(wǎng)絡訓練 將PSO算法用于神經(jīng)網(wǎng)絡訓練也取得 了良好的效果，研究表明，PSO是一種很有潛力的神經(jīng) 網(wǎng)絡訓練算法，如用于市區(qū)環(huán)境狀況的分析和預測等取 得了較高的成功率。 工程領(lǐng)域應用 很多工程中的實際問題，本質(zhì)上都是 優(yōu)化問題，因此PSO算法自然就可以應用到實際的工程 問題來，將PSO肅反和BP神經(jīng)網(wǎng)絡算法相結(jié)合訓練神經(jīng) 網(wǎng)絡已用于對電動汽車燃料電池組充