粒子群算法簡(jiǎn)介及使用

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)粒子群算法題目：求的最小值1粒子群簡(jiǎn)介粒子群優(yōu)化算法PSO 也是起源對(duì)簡(jiǎn)單社會(huì)系統(tǒng)的模擬。最初設(shè)想是模擬鳥群覓食的過(guò)程。粒子群優(yōu)化算法是由Kennedy和Eberhart通過(guò)對(duì)鳥群、魚群和人類社會(huì)某些行為的觀察研究，于1995年提出的一種新穎的進(jìn)化算法。PSO 算法屬于的一種，和相似，它也是從隨機(jī)解出發(fā)，通過(guò)迭代尋找，它也是通過(guò)來(lái)評(píng)價(jià)解的品質(zhì)，但它比遺傳算法規(guī)則更為簡(jiǎn)單，它沒(méi)有遺傳算法的“交叉”和“” 操作，它通過(guò)追隨當(dāng)前搜索到的來(lái)尋找全局最優(yōu)。這種算法以其實(shí)現(xiàn)容易、精

2、度高、收斂快等優(yōu)點(diǎn)引起了學(xué)術(shù)界的重視，并且在解決實(shí)際問(wèn)題中展示了其優(yōu)越性。2算法的原理PSO從這種模型中得到啟示并用于解決優(yōu)化問(wèn)題。PSO 中，每個(gè)優(yōu)化問(wèn)題的潛在解都是搜索空間中的一只鳥，稱之為粒子。所有的粒子都有一個(gè)由被優(yōu)化的函數(shù)決定的適值( fitness value) ，每個(gè)粒子還有一個(gè)速度決定它們飛翔的方向和距離。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索。PSO初始化為一群隨機(jī)粒子(隨機(jī)解)，然后通過(guò)迭代找到最優(yōu)解。在每一次迭代中，粒子通過(guò)跟蹤兩個(gè)極值來(lái)更新自己；第一個(gè)就是粒子本身所找到的最優(yōu)解，這個(gè)解稱為個(gè)體極值；另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解，這個(gè)極值是全局極值。另外也可

3、以不用整個(gè)種群而只是用其中一部分作為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。假設(shè)在一個(gè)維的目標(biāo)搜索空間中，有個(gè)粒子組成一個(gè)群落，其中第個(gè)粒子表示為一個(gè)維的向量，第個(gè)粒子的“飛行 ”速度也是一個(gè)維的向量，記為 ，第個(gè)粒子迄今為止搜索到的最優(yōu)位置稱為個(gè)體極值，記為 ，整個(gè)粒子群迄今為止搜索到的最優(yōu)位置為全局極值，記為 在找到這兩個(gè)最優(yōu)值時(shí)，粒子根據(jù)如下的公式(2.1)和( 2.2)來(lái)更新自己的速度和位置： (2.1) (2. 2)其中：和為學(xué)習(xí)因子，也稱加速常數(shù)，和為0，1范圍內(nèi)的均勻隨機(jī)數(shù)。式(2.1)右邊由三部分組成，第一部分為“慣性”或“動(dòng)量”部分，反映了粒子的運(yùn)動(dòng)“習(xí)慣”，代表粒子

4、有維持自己先前速度的趨勢(shì)；第二部分為“認(rèn)知”部分，反映了粒子對(duì)自身歷史經(jīng)驗(yàn)的記憶或回憶，代表粒子有向自身歷史最佳位置逼近的趨勢(shì)；第三部分為“社會(huì)”部分，反映了粒子間協(xié)同合作與知識(shí)共享的群體歷史經(jīng)驗(yàn)，代表粒子有向群體或鄰域歷史最佳位置逼近的趨勢(shì)，根據(jù)經(jīng)驗(yàn)，通常。是粒子的速度，是常數(shù)，由用戶設(shè)定用來(lái)限制粒子的速度。和是介于0,1之間的隨機(jī)數(shù)。探索是偏離原來(lái)的尋優(yōu)軌跡去尋找一個(gè)更好的解，探索能力是一個(gè)算法的全局搜索能力。開發(fā)是利用一個(gè)好的解，繼續(xù)原來(lái)的尋優(yōu)軌跡去搜索更好的解，它是算法的局部搜索能力。如何確定局部搜索能力和全局搜索能力的比例，對(duì)一個(gè)問(wèn)題的求解過(guò)程很重要。帶有慣性權(quán)重的改進(jìn)粒子群算法。其

5、進(jìn)化過(guò)程為： （2.3） （2.4）在式(2.1)中，第一部分表示粒子先前的速度，用于保證算法的全局收斂性能；第二部分、第三部分則是使算法具有局部收斂能力?？梢钥闯觯剑?.3)中慣性權(quán)重表示在多大程度上保留原來(lái)的速度。較大，全局收斂能力強(qiáng)，局部收斂能力弱；較小，局部收斂能力強(qiáng)，全局收斂能力弱。當(dāng)時(shí)，式(2.3)與式(2.1)完全一樣，表明帶慣性權(quán)重的粒子群算法是基本粒子群算法的擴(kuò)展。實(shí)驗(yàn)結(jié)果表明，在之間時(shí)，PSO算法有更快的收斂速度，而當(dāng)時(shí)，算法則易陷入局部極值。3 基本粒子群算法流程算法的流程如下： 初始化粒子群，包括群體規(guī)模，每個(gè)粒子的位置和速度 計(jì)算每個(gè)粒子的適應(yīng)度值； 對(duì)每個(gè)粒子，用

6、它的適應(yīng)度值和個(gè)體極值比較，如果 ，則用替換掉； 對(duì)每個(gè)粒子，用它的適應(yīng)度值和全局極值比較，如果則用替； 根據(jù)公式（2.1），（2.2）更新粒子的速度和位置 ； 如果滿足結(jié)束條件(誤差足夠好或到達(dá)最大循環(huán)次數(shù))退出，否則返回。4參數(shù)的設(shè)定PSO的參數(shù)主要包括最大速度、兩個(gè)加速常數(shù)和慣性常數(shù)或收縮因等。 群體大小mm是個(gè)整形參數(shù)，m很小的時(shí)候，陷入局優(yōu)的可能性很大。當(dāng)m很大時(shí)，PSO的優(yōu)化能力很好，可是收斂速度將非常慢，并且當(dāng)群體數(shù)目增長(zhǎng)至一定的水平時(shí)，再增長(zhǎng)將不會(huì)有顯著的作用。最大速度的選擇如式(2.1)所示的粒子速度是一個(gè)隨機(jī)變量，由粒子位置更新公式(2.2)產(chǎn)生的運(yùn)動(dòng)軌跡是不可控的，使得粒

7、子在問(wèn)題空間循環(huán)跳動(dòng)。為了抑制這種無(wú)規(guī)律的跳動(dòng)，速度往往被限制在內(nèi)。增大，有利于全局探索；減小，則有利于局部開發(fā)。但是過(guò)高，粒子運(yùn)動(dòng)軌跡可能失去規(guī)律性，甚至越過(guò)最優(yōu)解所在區(qū)域，導(dǎo)致算法難以收斂而陷入停滯狀態(tài)；相反太小，粒子運(yùn)動(dòng)步長(zhǎng)太短，算法可能陷入局部極值。的選擇通常憑經(jīng)驗(yàn)給定，并一般設(shè)定為問(wèn)題空間的 。學(xué)習(xí)因子C1和C2式(1)中的學(xué)習(xí)因子和分別用于控制粒子指向自身或鄰域最佳位置的運(yùn)動(dòng)。建議，并通常取。Ratnaweera 等人則提出自適應(yīng)時(shí)變調(diào)整策略，即隨著進(jìn)化代數(shù)從2.5線性遞減至0.5，隨著進(jìn)化代數(shù)從0.5線性遞增至2.5。與傳統(tǒng)PSO取正數(shù)加速常數(shù)不同，Riget和Vesterstr

8、om提出一種增加種群多樣性的粒子群算法，根據(jù)群體多樣性指標(biāo)調(diào)整加速常數(shù)的正負(fù)號(hào)，動(dòng)態(tài)地改變“吸引”和“擴(kuò)散”狀態(tài)，以改善算法過(guò)早收斂問(wèn)題。 慣性權(quán)值和收縮因子當(dāng)PSO的速度更新公式采用式(1)時(shí)，即使和兩個(gè)加速因子選擇合適，粒子仍然可能飛出問(wèn)題空間，甚至趨于無(wú)窮大，發(fā)生群體“爆炸”現(xiàn)象。有兩種方法控制這種現(xiàn)象：慣性常數(shù)和收縮因子。帶慣性常數(shù)PSO的速度更新公式如下： （4.1）其中為慣性常數(shù)。建議隨著更新代數(shù)的增加從0.9線性遞減至0.4。近來(lái)，通過(guò)采用隨機(jī)近似理論分析PSO的動(dòng)態(tài)行為，提出了一種隨更新代數(shù)遞減至0的取值策略，以提高算法的搜索能力。帶收縮因子PSO由Clerc 和 Kenned

9、y提出，其最簡(jiǎn)單形式的速度更新 公式如下： （4.2）其中，；通常從而，。雖然慣性權(quán)值和收縮因子對(duì)典型測(cè)試函數(shù)表現(xiàn)出各自的優(yōu)勢(shì)，但由于慣性常數(shù)方法通常采用慣性權(quán)值隨更新代數(shù)增加而遞減的策略，算法后期由于慣性權(quán)值過(guò)小，會(huì)失去探索新區(qū)域的能力，而收縮因子方法則不存在此不足。 當(dāng)慣性權(quán)重較大時(shí)，具有更好的搜索能力，而慣性權(quán)重較小時(shí)，具有更好的開發(fā)能力。領(lǐng)域拓?fù)浣Y(jié)構(gòu)全局版本粒子群優(yōu)化算法將整個(gè)群體作為粒子的鄰域，速度快，不過(guò)有時(shí)會(huì)陷入局部最優(yōu)；局部版本粒子群優(yōu)化算法將索引號(hào)相近或者位置相近的個(gè)體作為粒子的鄰域，收斂速度慢一點(diǎn)，不過(guò)很難陷入局部最優(yōu)。停止準(zhǔn)則一般使用最大迭代次數(shù)或者可以接受的滿意解作為停

10、止準(zhǔn)則。粒子空間的初始化較好地選擇粒子的初始化空間，將大大的縮減收斂時(shí)間。這個(gè)依賴于具體問(wèn)題。5方針實(shí)驗(yàn)完全模型：即按原公式進(jìn)行速度更新。選擇參數(shù)w=1，C1=2，C2=2方針的結(jié)果為：圖5-1只有自我認(rèn)知：即速度上只考慮第一項(xiàng)和第二項(xiàng)。選擇參數(shù)w=1，C1=2，C2=0方針的結(jié)果為： 圖5-2只有社會(huì)經(jīng)驗(yàn)：即速度更新只考慮第一項(xiàng)和第三項(xiàng)。選擇參數(shù)w=1，C1=0，C2=2方針的結(jié)果為： 圖5-3帶有收縮因子的粒子群優(yōu)化算法：選擇參數(shù)w=0.729，C1=1.494，C2=1.494方針的結(jié)果為：圖5-46結(jié)論由圖5-1，圖5-2，圖5-3對(duì)比可知，自我認(rèn)知的模型收斂最慢，只是因?yàn)椴煌牧Ｗ娱g缺乏信息交流，沒(méi)有社會(huì)信息共享，導(dǎo)致找到最優(yōu)概率變小。與此相反社會(huì)經(jīng)驗(yàn)?zāi)Ｐ涂梢院芸斓倪_(dá)到收斂，這是因?yàn)榱Ｗ又g社會(huì)信息共享導(dǎo)致進(jìn)化加快。但對(duì)于復(fù)雜問(wèn)題只考慮社會(huì)經(jīng)驗(yàn)，將導(dǎo)致粒子群過(guò)早收斂，從而陷入局優(yōu)。而只考慮個(gè)體經(jīng)驗(yàn)，將使群體很難收斂進(jìn)化速度過(guò)慢。相對(duì)而言，完全模型是較好的選擇。由圖5-1和圖5-4對(duì)比，改進(jìn)型帶有收縮因子的粒子群優(yōu)化算法，擁有非常好的收斂效果，收斂速度也十分