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

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

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

人工生命鳥群覓食魚群學習群理論2.1.2

基本原理鳥群覓食現(xià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í)行步驟示意圖粒子的個體速度與位置更新公式更新速度自身速度個體認知社會引導速度與位置更新示意圖x1x2P1P2P3gBest速度與位置更新示意圖x2x1P3P1P2PB2速度與位置更新示意圖經(jīng)過若干次迭代之后PSO算法流程圖和偽代碼2.2.2應(yīng)用舉例例

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

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

IEEETransactionson……

MachineLearning

EvolutionaryComputation

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

IEEEInternationalConferenceonSystems,Man,andCybernetics(SMC)

ACMGeneticandEvolutionaryComputationConference(GECCO)

InternationalConferenceonAntColonyOptimizationandSwarmIntelligence(ANTS)

InternationalConferenceonSimulatedEvolutionAndLearning(SEAL)

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

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

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

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

……其它拓撲結(jié)構(gòu)社會趨同法Kennedy2000FullyInformedMendes等人2004廣泛學習策略Liang等人2006……幾種典型的拓撲結(jié)構(gòu)示意圖全局版本PSO和局部版本PSO在收斂特點：1.GPSO由于其很高的連接度，往往具有比LPSO更快的收斂速度。但是，快速的收斂也讓GPSO付出了多樣性迅速降低的代價2.LPSO由于具有更好的多樣性，因此一般不容易落入局部最優(yōu)，在處理多峰問題上具有更好的性能在解決具體問題的時候，可以遵循以下一些規(guī)律：(A)鄰域較小的拓撲結(jié)構(gòu)在處理復雜的、多峰值的問題上具有優(yōu)勢，例如環(huán)型結(jié)構(gòu)的LPSO(B)隨著鄰域的擴大，算法的收斂速度將會加快，這對簡單的、單峰值的問題非常的有利，例如GPSO在這些問題上就表現(xiàn)很好2.3.3混合算法改進混合其它技術(shù)的改進單純形技術(shù)函數(shù)延伸技術(shù)混沌技術(shù)量子技術(shù)協(xié)同技術(shù)小生境技術(shù)物種形成技術(shù)……混合其它搜索算法的改進結(jié)合模擬退火算法結(jié)合人工免疫算法結(jié)合差分進化算法結(jié)合局部搜索算法……混合進化算子的改進選擇算子交叉算子變異算子……進化規(guī)劃進化策略蟻群算法……2.3.4混合算法改進二進制編碼整數(shù)編碼其它形式Kennedy和Eberhart1997年對PSO進行了離散化，形成了二進制編碼的PSO(BPSO)，并且在對DeJong的五個標準測試函數(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)了離散化2.4粒子群優(yōu)化算法的相關(guān)應(yīng)用調(diào)度與規(guī)劃優(yōu)化與設(shè)計生物與醫(yī)學機器學習與訓練其它……數(shù)據(jù)挖掘與分類應(yīng)用2.5粒子群優(yōu)化算法的參數(shù)設(shè)置種群規(guī)模N

粒子的長度D

粒子的范圍R

最大速度Vmax

慣性權(quán)重

壓縮因子

加速系數(shù)c1和c2

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

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

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

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

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

慣性權(quán)重

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

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

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

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