第章粒子群優(yōu)化算法

Contents算法簡介

1基本流程2改進(jìn)研究3相關(guān)應(yīng)用4參數(shù)設(shè)置51目前一頁\總數(shù)三十一頁\編于十八點6.1粒子群優(yōu)化算法簡介粒子群優(yōu)化算法是什么？粒子群優(yōu)化算法（ParticleSwarmOptimization，PSO）是進(jìn)化計算的一個分支，是一種模擬自然界的生物活動的隨機搜索算法。粒子群優(yōu)化算法的思想來源是怎樣的？它由誰提出的？PSO模擬了自然界鳥群捕食和魚群捕食的過程。通過群體中的協(xié)作尋找到問題的全局最優(yōu)解。它是1995年由美國學(xué)者Eberhart和Kennedy提出的，現(xiàn)在已經(jīng)廣泛應(yīng)用于各種工程領(lǐng)域的優(yōu)化問題之中。2目前二頁\總數(shù)三十一頁\編于十八點6.1.1思想來源生物界現(xiàn)象群體行為群體遷徙生物覓食……社會心理學(xué)群體智慧個體認(rèn)知社會影響……粒子群優(yōu)化算法

人工生命鳥群覓食魚群學(xué)習(xí)群理論3目前三頁\總數(shù)三十一頁\編于十八點6.1.2

基本原理鳥群覓食現(xiàn)象鳥群覓食空間飛行速度所在位置個體認(rèn)知與群體協(xié)作找到食物粒子群優(yōu)化算法搜索空間的一組有效解問題的搜索空間解的速度向量解的位置向量速度與位置的更新找到全局最優(yōu)解鳥群覓食現(xiàn)象粒子群優(yōu)化算法類比關(guān)系4目前四頁\總數(shù)三十一頁\編于十八點6.1.2

基本原理鳥群覓食現(xiàn)象粒子群優(yōu)化算法5目前五頁\總數(shù)三十一頁\編于十八點6.2粒子群優(yōu)化算法的基本流程基本流程速度與位置更新公式速度與位置更新示意圖算法流程圖和偽代碼應(yīng)用舉例函數(shù)最小化問題算法的執(zhí)行步驟示意圖6目前六頁\總數(shù)三十一頁\編于十八點粒子的個體速度與位置更新公式更新速度自身速度個體認(rèn)知社會引導(dǎo)7目前七頁\總數(shù)三十一頁\編于十八點速度與位置更新示意圖x1x2P1P2P3gBest8目前八頁\總數(shù)三十一頁\編于十八點速度與位置更新示意圖x2x1P3P1P2PB29目前九頁\總數(shù)三十一頁\編于十八點速度與位置更新示意圖經(jīng)過若干次迭代之后10目前十頁\總數(shù)三十一頁\編于十八點PSO算法流程圖和偽代碼11目前十一頁\總數(shù)三十一頁\編于十八點6.2.2應(yīng)用舉例例6.1

已知函數(shù)，其中，用粒子群優(yōu)化算法求解y的最小值。12目前十二頁\總數(shù)三十一頁\編于十八點運行步驟13目前十三頁\總數(shù)三十一頁\編于十八點14目前十四頁\總數(shù)三十一頁\編于十八點6.3粒子群優(yōu)化算法的改進(jìn)研究PSO研究熱點與方向

算法理論研究混合算法研究算法參數(shù)研究拓?fù)浣Y(jié)構(gòu)研究算法應(yīng)用研究15目前十五頁\總數(shù)三十一頁\編于十八點與PSO相關(guān)的重要學(xué)術(shù)期刊與國際會議重要學(xué)術(shù)期刊IEEETransactionsonEvolutionaryComputationIEEETransactionsonSystems,ManandCybernetics

IEEETransactionson……

MachineLearning

EvolutionaryComputation

……16目前十六頁\總數(shù)三十一頁\編于十八點與PSO相關(guān)的重要學(xué)術(shù)期刊與國際會議重要國際會議IEEECongressonEvolutionaryComputation(CEC)

IEEEInternationalConferenceonSystems,Man,andCybernetics(SMC)

ACMGeneticandEvolutionaryComputationConference(GECCO)

InternationalConferenceonAntColonyOptimizationandSwarmIntelligence(ANTS)

InternationalConferenceonSimulatedEvolutionAndLearning(SEAL)

……17目前十七頁\總數(shù)三十一頁\編于十八點6.3.1理論研究改進(jìn)2006Kadirkamanathan等人2006年在動態(tài)環(huán)境中對PSO的行為進(jìn)行研究，由靜態(tài)分析深入到了動態(tài)分析

2003Trelea2003年指出PSO最終最終穩(wěn)定地收斂于空間中的某一個點，但不能保證是全局最優(yōu)點2002Clerc&Kennedy2002年設(shè)計了一個稱為壓縮因子的參數(shù)。在使用了此參數(shù)之后，PSO能夠更快地收斂2006F.vandenBergh等人2006年對PSO的飛行軌跡進(jìn)行了跟蹤，深入到了動態(tài)的系統(tǒng)分析和收斂性研究18目前十八頁\總數(shù)三十一頁\編于十八點6.3.2拓?fù)浣Y(jié)構(gòu)改進(jìn)靜態(tài)拓?fù)浣Y(jié)構(gòu)全局版本：星型結(jié)構(gòu)局部版本：

環(huán)形結(jié)構(gòu)齒形結(jié)構(gòu)金字塔結(jié)構(gòu)馮諾依曼結(jié)構(gòu)

……動態(tài)拓?fù)浣Y(jié)構(gòu)逐步增長法Suganthan1999最小距離法Hu&Eberhart2002重新組合法Liang&Suganthan2005隨機選擇法Kennedy等人2006

……其它拓?fù)浣Y(jié)構(gòu)社會趨同法Kennedy2000FullyInformedMendes等人2004廣泛學(xué)習(xí)策略Liang等人2006……19目前十九頁\總數(shù)三十一頁\編于十八點幾種典型的拓?fù)浣Y(jié)構(gòu)示意圖全局版本PSO和局部版本PSO在收斂特點：1.GPSO由于其很高的連接度，往往具有比LPSO更快的收斂速度。但是，快速的收斂也讓GPSO付出了多樣性迅速降低的代價2.LPSO由于具有更好的多樣性，因此一般不容易落入局部最優(yōu)，在處理多峰問題上具有更好的性能在解決具體問題的時候，可以遵循以下一些規(guī)律：(A)鄰域較小的拓?fù)浣Y(jié)構(gòu)在處理復(fù)雜的、多峰值的問題上具有優(yōu)勢，例如環(huán)型結(jié)構(gòu)的LPSO(B)隨著鄰域的擴大，算法的收斂速度將會加快，這對簡單的、單峰值的問題非常的有利，例如GPSO在這些問題上就表現(xiàn)很好20目前二十頁\總數(shù)三十一頁\編于十八點6.3.3混合算法改進(jìn)混合其它技術(shù)的改進(jìn)單純形技術(shù)函數(shù)延伸技術(shù)混沌技術(shù)量子技術(shù)協(xié)同技術(shù)小生境技術(shù)物種形成技術(shù)……混合其它搜索算法的改進(jìn)結(jié)合模擬退火算法結(jié)合人工免疫算法結(jié)合差分進(jìn)化算法結(jié)合局部搜索算法……混合進(jìn)化算子的改進(jìn)選擇算子交叉算子變異算子……進(jìn)化規(guī)劃進(jìn)化策略蟻群算法……21目前二十一頁\總數(shù)三十一頁\編于十八點6.3.4混合算法改進(jìn)二進(jìn)制編碼整數(shù)編碼其它形式Kennedy和Eberhart1997年對PSO進(jìn)行了離散化，形成了二進(jìn)制編碼的PSO(BPSO)，并且在對DeJong的五個標(biāo)準(zhǔn)測試函數(shù)的測試中取得較好的效果Salman等人2002年將粒子的位置變量四舍五入為最接近的合法的離散值Yoshida等人2000年將連續(xù)的值域分區(qū)間，每個區(qū)間賦予一個相應(yīng)的離散值Schoofs和Naudts2002年重新定義了PSO的“加減乘”法，并且應(yīng)用到了約束可滿足問題（CSP）中Hu等人2003年將速度定義為位置變量相互交換的概率，從而將PSO離散化并用于解決n皇后問題Clerc2004年為PSO定義了合適的“加減乘”法而實現(xiàn)離散化，并且應(yīng)用于解決旅行商問題（TSP）Chen等人2009年基于集合論的技術(shù)，重新定義了PSO速度和位置的更新公式實現(xiàn)了離散化22目前二十二頁\總數(shù)三十一頁\編于十八點6.4粒子群優(yōu)化算法的相關(guān)應(yīng)用調(diào)度與規(guī)劃優(yōu)化與設(shè)計生物與醫(yī)學(xué)機器學(xué)習(xí)與訓(xùn)練其它……數(shù)據(jù)挖掘與分類應(yīng)用23目前二十三頁\總數(shù)三十一頁\編于十八點6.5粒子群優(yōu)化算法的參數(shù)設(shè)置種群規(guī)模N

粒子的長度D

粒子的范圍R

最大速度Vmax

慣性權(quán)重

壓縮因子

加速系數(shù)c1和c2

終止條件全局和局部PSO同步和異步更新

24目前二十四頁\總數(shù)三十一頁\編于十八點種群規(guī)模N影響著算法的搜索能力和計算量PSO對種群規(guī)模要求不高，一般取20-40就可以達(dá)到很好的求解效果不過對于比較難的問題或者特定類別的問題，粒子數(shù)可以取到100或200

25目前二十五頁\總數(shù)三十一頁\編于十八點粒子的長度D由優(yōu)化問題本身決定，就是問題解的長度粒子的范圍R由優(yōu)化問題本身決定，每一維可以設(shè)定不同的范圍26目前二十六頁\總數(shù)三十一頁\編于十八點最大速度Vmax

決定粒子每一次的最大移動距離，制約著算法的探索和開發(fā)能力Vmax的每一維一般可以取相應(yīng)維搜索空間的10%-20%，甚至100%

也有研究使用將Vmax按照進(jìn)化代數(shù)從大到小遞減的設(shè)置方案

27目前二十七頁\總數(shù)三十一頁\編于十八點慣性權(quán)重

控制著前一速度對當(dāng)前速度的影響，用于平衡算法的探索和開發(fā)能力一般設(shè)置為從0.9線性遞減到0.4，也有非線性遞減的設(shè)置方案可以采用模糊控制的方式設(shè)定，或者在[0.5,1.0]之間隨機取值設(shè)為0.729的同時將c1和c2設(shè)1.49445，有利于算法的收斂28目前二十八頁\總數(shù)三十一頁\編于十八點壓縮因子

限制粒子的飛行速度的，保證算法的有效收斂Clerc等人通過數(shù)學(xué)計算得到取值0.729，同時c1和c2設(shè)為2.0529目前二十九頁\總數(shù)三十一頁\編于十八點加速系數(shù)c1和c2

代表了粒子向自身極值pBest和全局極值gBest推進(jìn)的加速權(quán)值c1和c2通常都等于2.0，代表著對兩個引導(dǎo)方向的同等重視也存在一些c1和c2