粒子群算法簡介及使用

粒子群算法題目：求f(x)旦x2的最小值ii=11粒子群簡介粒子群優(yōu)化算法PSO也是起源對簡單社會(huì)系統(tǒng)的模擬。最初設(shè)想是模擬鳥群覓食的過程。粒子群優(yōu)化算法是由Kennedy和Eberhart通過對鳥群、魚群和人類社會(huì)某些行為的觀察研究，于1995年提出的一種新穎的進(jìn)化算法。PSO算法屬于進(jìn)化算法的一種，和遺傳算法相似，它也是從隨機(jī)解出發(fā)，通過迭代尋找最優(yōu)解，它也是通過適應(yīng)度來評價(jià)解的品質(zhì)，但它比遺傳算法規(guī)則更為簡單，它沒有遺傳算法的“交叉”和“變異”操作，它通過追隨當(dāng)前搜索到的最優(yōu)值來尋找全局最優(yōu)。這種算法以其實(shí)現(xiàn)容易、精度高、收斂快等優(yōu)點(diǎn)引起了學(xué)術(shù)界的重視，并且在解決實(shí)際問題中展示了其優(yōu)越性。2算法的原理PSO從這種模型中得到啟示并用于解決優(yōu)化問題。PSO中，每個(gè)優(yōu)化問題的潛在解都是搜索空間中的一只鳥，稱之為粒子。所有的粒子都有一個(gè)由被優(yōu)化的函數(shù)決定的適值(fitnessvalue)，每個(gè)粒子還有一個(gè)速度決定它們飛翔的方向和距離。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索。PSO初始化為一群隨機(jī)粒子(隨機(jī)解)，然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個(gè)極值來更新自己；第一個(gè)就是粒子本身所找到的最優(yōu)解，這個(gè)解稱為個(gè)體極值；另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解，這個(gè)極值是全局極值。另外也可以不用整個(gè)種群而只是用其中一部分作為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。假設(shè)在一個(gè)D維的目標(biāo)搜索空間中，有N個(gè)粒子組成一個(gè)群落，其中第，個(gè)粒子表示為一個(gè)D維的向量X二(x,x,…,x)i=1,2,—,Ni i1i2iD，第i個(gè)粒子的“飛行”速度也是一個(gè)D維的向量，記為V=(v,v，…,v)i=1,2,…3TOC\o"1-5"\h\zi i1i2 iD，第i個(gè)粒子迄今為止搜索到的最優(yōu)位置稱為個(gè)體極值，記為P二(P,P，…,P)i=1,2,…,Nbest i1i2 iD，整個(gè)粒子群迄今為止搜索到的最優(yōu)位置為全局極值，記為g二(P,P，…,P)

best g1g2 gD在找到這兩個(gè)最優(yōu)值時(shí)，粒子根據(jù)如下的公式(2.1)和(2.2)來更新自己的速度和位置：v二w*v+cr(p-x)+cr(p-x)id id11idid22gdid (2.1)x=x+vididid (2.2)其中：Ci和C2為學(xué)習(xí)因子，也稱加速常數(shù)，ri和r2為［0，1］范圍內(nèi)的均勻隨機(jī)數(shù)。式(2.1)右邊由三部分組成，第一部分為“慣性”或“動(dòng)量”部分，反映了粒子的運(yùn)動(dòng)“習(xí)慣”，代表粒子有維持自己先前速度的趨勢；第二部分為“認(rèn)知”部分，反映了粒子對自身歷史經(jīng)驗(yàn)的記憶或回憶，代表粒子有向自身歷史最佳位置逼近的趨勢；第三部分為“社會(huì)”部分，反映了粒子間協(xié)同合作與知識(shí)共享的群體歷史經(jīng)驗(yàn)，代表粒子有向群體或鄰域歷史最佳位置逼近的趨勢，根據(jù)經(jīng)驗(yàn)，通常Ci=C2=2。=陀…,D。寫是粒子的速度，vidE［-vmax,vmax］，"max是常數(shù)，由用戶設(shè)定用來限制粒子的速度。ri和^是介于［0,1］之間的隨機(jī)數(shù)。探索是偏離原來的尋優(yōu)軌跡去尋找一個(gè)更好的解，探索能力是一個(gè)算法的全局搜索能力。開發(fā)是利用一個(gè)好的解，繼續(xù)原來的尋優(yōu)軌跡去搜索更好的解，它是算法的局部搜索能力。如何確定局部搜索能力和全局搜索能力的比例，對一個(gè)問題的求解過程很重要。帶有慣性權(quán)重的改進(jìn)粒子群算法。其進(jìn)化過程為：2.3)v(t+1)=wv(t)+cr(t)(p(t)一x(t))+cr(t)(p(t)一x(t2.3)TOC\o"1-5"\h\zij ij 11 ij ij 22 gi ijx(t+1)=x(t)+v(t+1) /24)ij ijij (2.4)在式(2.1)中，第一部分表示粒子先前的速度，用于保證算法的全局收斂性能；第二部分、第三部分則是使算法具有局部收斂能力?？梢钥闯?，式(2.3)中慣性權(quán)重w表示在多大程度上保留原來的速度。w較大，全局收斂能力強(qiáng)，局部收斂能力弱；w較小，局部收斂能力強(qiáng)，全局收斂能力弱。當(dāng)w二1時(shí)，式(2.3)與式(2.1)完全一樣，表明帶慣性權(quán)重的粒子群算法是基本粒子群算法的擴(kuò)展。實(shí)驗(yàn)結(jié)果表明，w在[0?8-1.2]之間時(shí)，pso算法有更快的收斂速度，而當(dāng)w>I-2時(shí)，算法則易陷入局部極值。3基本粒子群算法流程算法的流程如下：初始化粒子群，包括群體規(guī)模N，每個(gè)粒子的位置x和速度V.ii計(jì)算每個(gè)粒子的適應(yīng)度值F[i]；it對每個(gè)粒子，用它的適應(yīng)度值F[i]和個(gè)體極值p⑺比較，如果it bestF[i]>p (i)，則用Fit[i]替換掉p(i)；it best best對每個(gè)粒子，用它的適應(yīng)度值Fit[i]和全局極值g比較，如果bestF[i]>p (i)則用F[i]替g；it best it best根據(jù)公式(2.1)，(2.2)更新粒子的速度v和位置x；ii如果滿足結(jié)束條件(誤差足夠好或到達(dá)最大循環(huán)次數(shù))退出，否則返回②。4參數(shù)的設(shè)定PSO的參數(shù)主要包括最大速度、兩個(gè)加速常數(shù)和慣性常數(shù)或收縮因等。1．群體大小mm是個(gè)整形參數(shù)，m很小的時(shí)候，陷入局優(yōu)的可能性很大。當(dāng)m很大時(shí)，PSO的優(yōu)化能力很好，可是收斂速度將非常慢，并且當(dāng)群體數(shù)目增長至一定的水平時(shí)，再增長將不會(huì)有顯著的作用。2．最大速度max的選擇如式(2.1)所示的粒子速度是一個(gè)隨機(jī)變量，由粒子位置更新公式(2.2)產(chǎn)生的運(yùn)動(dòng)軌跡是不可控的，使得粒子在問題空間循環(huán)跳動(dòng)。為了抑制這種無規(guī)律的跳動(dòng)，速度往往被限制在LSax'Vmax內(nèi)。"max增大，有利于全局探索；"max減小，則有利于局部開發(fā)。但是"max過高，粒子運(yùn)動(dòng)軌跡可能失去規(guī)律性，甚至越過最優(yōu)解所在區(qū)域，導(dǎo)致算法難以收斂而陷入停滯狀態(tài)；相反"max太小，粒子運(yùn)動(dòng)步長太短，算法可能陷入局部極值。"max的選擇通常憑經(jīng)驗(yàn)給定，并一般設(shè)定為問題空間的10-20%。3?學(xué)習(xí)因子C1和C2式(1)中的學(xué)習(xí)因子C2和C2分別用于控制粒子指向自身或鄰域最佳位置的運(yùn)動(dòng)。建議ci+c2-4?°，并通常取ci=c2=2。Ratnaweera等人則提出自適應(yīng)時(shí)變調(diào)整策略，即ci隨著進(jìn)化代數(shù)從2.5線性遞減至0.5,c2隨著進(jìn)化代數(shù)從0.5

線性遞增至2.5。與傳統(tǒng)PSO取正數(shù)加速常數(shù)不同，Riget和Vesterstrom提出一種增加種群多樣性的粒子群算法，根據(jù)群體多樣性指標(biāo)調(diào)整加速常數(shù)的正負(fù)號(hào)，動(dòng)態(tài)地改變“吸引”和“擴(kuò)散”狀態(tài)，以改善算法過早收斂問題。4．慣性權(quán)值和收縮因子當(dāng)PSO的速度更新公式采用式(1)時(shí)，即使vmax和兩個(gè)加速因子選擇合適，粒子仍然可能飛出問題空間，甚至趨于無窮大，發(fā)生群體“爆炸”現(xiàn)象。有兩種方法控制這種現(xiàn)象：慣性常數(shù)和收縮因子。帶慣性常數(shù)PSO的速度更新公式如下：vt=wvt—1+cr(p-xt)+cr(t)(p一xt)ijij11ijij22ijij (4.1)-xt)+cr(t)(p-xt)?? ?? ??ij22ijij4.2)-xt)+cr(t)(p-xt)?? ?? ??ij22ijij4.2)vt=xvt-1+cr(pijij11ij2x=其中 2-9-沖2-4*，申=c1+c2>4.0；通常申=4.1從而x二0.729,c=c=1.4944512。雖然慣性權(quán)值和收縮因子對典型測試函數(shù)表現(xiàn)出各自的優(yōu)勢，但由于慣性常數(shù)方法通常采用慣性權(quán)值隨更新代數(shù)增加而遞減的策略，算法后期由于慣性權(quán)值過小，會(huì)失去探索新區(qū)域的能力，而收縮因子方法則不存在此不足。當(dāng)慣性權(quán)重較大時(shí)，具有更好的搜索能力，而慣性權(quán)重較小時(shí)，具有更好的開發(fā)能力。?領(lǐng)域拓?fù)浣Y(jié)構(gòu)全局版本粒子群優(yōu)化算法將整個(gè)群體作為粒子的鄰域，速度快，不過有時(shí)會(huì)陷入局部最優(yōu)；局部版本粒子群優(yōu)化算法將索引號(hào)相近或者位置相近的個(gè)體作為粒子的鄰域，收斂速度慢一點(diǎn)，不過很難陷入局部最優(yōu)。?停止準(zhǔn)則一般使用最大迭代次數(shù)或者可以接受的滿意解作為停止準(zhǔn)則。?粒子空間的初始化較好地選擇粒子的初始化空間，將大大的縮減收斂時(shí)間。這個(gè)依賴于具體問題。5方針實(shí)驗(yàn)1.完全模型：即按原公式進(jìn)行速度更新。選擇參數(shù)w=l,Cl=2,C2=2方針的結(jié)果為：圖5-1

2.只有自我認(rèn)知：即速度上只考慮第一項(xiàng)和第二項(xiàng)。選擇參數(shù)w=l,Cl=2,C2=0方針的結(jié)果為:圖5-23.只有社會(huì)經(jīng)驗(yàn)：即速度更新只考慮第一項(xiàng)和第三項(xiàng)。選擇參數(shù)w=1,C1=0,C2=2方針的結(jié)果為：圖5-34?帶有收縮因子的粒子群優(yōu)化算法:選擇參數(shù)w=0.729,Cl=1.494,C2=1.494方針的結(jié)果為：r-ir-i迭代欣皺圖5-46結(jié)論由圖5-1，圖5-2，圖5-3對比可知，自我認(rèn)知的模型收斂最慢，只是因?yàn)椴煌牧Ｗ娱g缺乏信息交流，沒