智能優(yōu)化方法3-粒子群優(yōu)化算法

第9章智能優(yōu)化方法Contents遺傳算法

1蟻群優(yōu)化算法2粒子群優(yōu)化算法3粒子群優(yōu)化算法Contents算法簡(jiǎn)介

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

人工生命鳥群覓食魚群學(xué)習(xí)群理論2.1.2

基本原理鳥群覓食現(xiàn)象鳥群覓食空間飛行速度所在位置個(gè)體認(rèn)知與群體協(xié)作找到食物粒子群優(yōu)化算法搜索空間的一組有效解問題的搜索空間解的速度向量解的位置向量速度與位置的更新找到全局最優(yōu)解鳥群覓食現(xiàn)象粒子群優(yōu)化算法類比關(guān)系2.1.2

基本原理鳥群覓食現(xiàn)象粒子群優(yōu)化算法2.2粒子群優(yōu)化算法的基本流程基本流程速度與位置更新公式速度與位置更新示意圖算法流程圖和偽代碼應(yīng)用舉例函數(shù)最小化問題算法的執(zhí)行步驟示意圖粒子的個(gè)體速度與位置更新公式更新速度自身速度個(gè)體認(rèn)知社會(huì)引導(dǎo)速度與位置更新示意圖x1x2P1P2P3gBest速度與位置更新示意圖x2x1P3P1P2PB2速度與位置更新示意圖經(jīng)過若干次迭代之后PSO算法流程圖和偽代碼2.2.2應(yīng)用舉例例

已知函數(shù)，其中，用粒子群優(yōu)化算法求解y的最小值。運(yùn)行步驟2.3粒子群優(yōu)化算法的改進(jìn)研究PSO研究熱點(diǎn)與方向

算法理論研究混合算法研究算法參數(shù)研究拓?fù)浣Y(jié)構(gòu)研究算法應(yīng)用研究與PSO相關(guān)的重要學(xué)術(shù)期刊與國(guó)際會(huì)議重要學(xué)術(shù)期刊IEEETransactionsonEvolutionaryComputationIEEETransactionsonSystems,ManandCybernetics

IEEETransactionson……

MachineLearning

EvolutionaryComputation

……與PSO相關(guān)的重要學(xué)術(shù)期刊與國(guó)際會(huì)議重要國(guó)際會(huì)議IEEECongressonEvolutionaryComputation(CEC)

IEEEInternationalConferenceonSystems,Man,andCybernetics(SMC)

ACMGeneticandEvolutionaryComputationConference(GECCO)

InternationalConferenceonAntColonyOptimizationandSwarmIntelligence(ANTS)

InternationalConferenceonSimulatedEvolutionAndLearning(SEAL)

……2.3.1理論研究改進(jìn)2006Kadirkamanathan等人2006年在動(dòng)態(tài)環(huán)境中對(duì)PSO的行為進(jìn)行研究，由靜態(tài)分析深入到了動(dòng)態(tài)分析

2003Trelea2003年指出PSO最終最終穩(wěn)定地收斂于空間中的某一個(gè)點(diǎn)，但不能保證是全局最優(yōu)點(diǎn)2002Clerc&Kennedy2002年設(shè)計(jì)了一個(gè)稱為壓縮因子的參數(shù)。在使用了此參數(shù)之后，PSO能夠更快地收斂2006F.vandenBergh等人2006年對(duì)PSO的飛行軌跡進(jìn)行了跟蹤，深入到了動(dòng)態(tài)的系統(tǒng)分析和收斂性研究2.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)

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

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

粒子的長(zhǎng)度D

粒子的范圍R

最大速度Vmax

慣性權(quán)重

壓縮因子

加速系數(shù)c1和c2

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

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

粒子的長(zhǎng)度D由優(yōu)化問題本身決定，就是問題解的長(zhǎng)度粒子的范圍R由優(yōu)化問題本身決定，每一維可以設(shè)定不同的范圍最大速度Vmax

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

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

慣性權(quán)重

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

限制粒子的飛行速度的，保證算法的有效收斂Clerc等人通過數(shù)學(xué)計(jì)算得到取值0.729，同時(shí)c1和c2設(shè)為2.05加速系數(shù)c1和c2

代表了粒子向自身極值pBest和全局極值gBest推進(jìn)的加速權(quán)值c1和c2通常都等于2.0，代表著對(duì)兩個(gè)引導(dǎo)方向的同等重視也存在一些c1和c2不相等的設(shè)置，但其范圍一般都在0和4之間研究對(duì)c1和c2的自適應(yīng)調(diào)整方案對(duì)算法性能的增強(qiáng)有重要意義終止條件決定算法運(yùn)行的結(jié)束，由具體的應(yīng)用和問題本身確定將最大循環(huán)數(shù)設(shè)定為500，1000，5000，或者最大的函數(shù)評(píng)估次數(shù)，等等也可以使用算法求解得到一個(gè)可接受的解作為終止條件或者是當(dāng)算法在很長(zhǎng)一段迭代中沒有得到任何改善，則可以終止算法全局和局部PSO決定算法如何選擇兩種版本的粒子群優(yōu)化算法—全局版PSO和局部版PSO全局版本PSO速度快，不過有時(shí)會(huì)陷入局部最優(yōu)局部版本PSO收斂速度慢一點(diǎn)，不過不容易陷入局部最優(yōu)在實(shí)際應(yīng)用中，可以根據(jù)具體問題選擇具體的算法版本同步和異步更新

兩種更新方式的區(qū)別在于對(duì)全局的gBest或者局部的lBest的更新方式在同步更新方式中，在每一代中，當(dāng)所有粒子都采用當(dāng)前的gBest進(jìn)行速度和位置的更新