粒子群算法技術分析

粒子群算法2020年12月20日點擊添加文本點擊添加文本點擊添加文本點擊添加文本目錄一.集群智能（SwarmIntelligence）二.粒子群算法（PSO）簡介三、PSO的一般數學模型四、PSO的各種改進算法五、PSO的優(yōu)缺點六、PSO的matlab實現一、集群智能（SwarmIntelligence）

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

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

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

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

：是粒子i在第k次迭代中第d維的當前位置；i=1，2，3…，M：種群大小。c1和c2：學習因子（或稱加速系數），合適的c1和c2既可加快收斂又不易陷入局部最優(yōu)。rand1和rand2：是介于［0,1］之間的隨機數。

：是粒子i在第d維的個體極值點的位置；

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

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

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

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

和c2值產生陡峭的運動或越過目標區(qū)域。Shi和Eberhart建議，為了平衡隨機因素的作用，一般情況下設置c1

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

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

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

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

如果沒有公式(1)的第一部分，PSO的搜索過程是一個通過迭代搜索空間逐漸收縮的過程，展現出一種局部搜索(exploitation)能力；反之，如果增加了第一部分，粒子就有能力擴展搜索空間，展現出一種全局搜索(exploration)的能力。在搜索過程中，全局搜索能力與局部搜索能力的平衡對于算法的成功起著至關重要的作用。引入一個慣性權重

到公式(1)，

是與前一次速度有關的一個比例因子，較大的

可以加強PSO的全局探測能力，而較小的

能加強局部搜索能力，也就是這個

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

為非負數，稱為慣性因子，慣性權重，是控制速度的權重（1）線性調整

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

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

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

直接影響全局搜索能力，所以希望找到一個非常好的慣性權重來達到全局搜索和局部搜索之間的平衡。

類似于人的“原動力”，如果原動力比較大，當達到某個目標的時候，會繼續(xù)向前實現更高的目標：如果原動力較小，到達某個目標就停滯。Shi和Eberhart提出了一種隨著算法迭代次數的增加慣性權重線性下降的方法。慣性權重的計算公式如下：

max和

min分別表示權重的最大及最小值，kn為當前迭代次數，kmax表示最大迭代次數。文獻試驗了將

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

逐漸減小，粒子速度減慢，開始精細的局部搜索。該方法使PSO更好地控制exploration和exploitation能力，加快了收斂速度，提高了算法的性能，稱之為權重線性下降的粒子群算法，簡記為LDW(LinearlyDecreasingInertiaWeight)。(2)模糊調整

的策略模糊權重是使用模糊系統(tǒng)來動態(tài)調節(jié)慣性權重。下面的文獻給出了一種模糊權重的設置方式PSO搜索過程是一個非線性的復雜過程，讓

線性下降的方法并不能正確反映真實的搜索過程。因而，Shi等提出用模糊推理機來動態(tài)地調整慣性權重的技術。即構造一個2輸入、1輸出的模糊推理機來動態(tài)地修改慣性因子。模糊推理機的兩個輸入分別是當前

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

增量。CBPE(TheCurrentBestPerformanceEvaluation，CBPE)是PSO迄今為止發(fā)現的最好候選解的性能測度。由于不同的優(yōu)化問題有不同的性能評價值范圍，所以為了讓該模糊系統(tǒng)有廣泛的適用性，通常使用標準化的CBPE(NCBPE)。慣性權重線性下降算法(LDW)是為了提高算法的收斂性能，平衡收斂的全局性和收斂速度，在多峰函數上效果顯著；

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

（1）對于有多個局部極值點的函數，容易陷入到局部極值點中，得不到正確的結果。

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

（3）PSO方法提供了全局搜索的可能，但并不能嚴格證明它在全局最優(yōu)點上的收斂性。六、PSO的matlab實現計算如下二元函數的最小值：（其中自變量x、y的范圍均為[-50,50]）（1）編寫待優(yōu)化函數程序functionz=test_func(in)nn=size(in);%輸入的是矩陣，即算法中隨機產生一組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;

endclearclcx_ra