粒子群優(yōu)化算法-課件

粒子群優(yōu)化算法（PS0）Particle

Swarm

Optimization智能算法向大自然學(xué)習(xí)遺傳算法(GA)物競天擇，設(shè)計染色體編碼，根據(jù)適應(yīng)值函數(shù)進行染色體選擇、交叉和變異操作，優(yōu)化求解人工神經(jīng)網(wǎng)絡(luò)算法(ANN)模仿生物神經(jīng)元，透過神經(jīng)元的信息傳遞、訓(xùn)練學(xué)習(xí)、聯(lián)想，優(yōu)化求解模擬退火算法(SA)模模仿金屬物質(zhì)退火過程2解決最優(yōu)化問題的方法傳統(tǒng)搜索方法保證能找到最優(yōu)解Heuristic

Search不能保證找到最優(yōu)解3由Kennedy和Eberhart于1995年提出．群體迭代，粒子在解空間追隨最優(yōu)的粒子進行搜索.粒子群算法:簡單易行

收斂速度快設(shè)置參數(shù)少已成為現(xiàn)代優(yōu)化方法領(lǐng)域研究的熱點．粒子群算法發(fā)展歷史簡介4粒子群算法的基本思想粒子群算法的思想源于對鳥群捕食行為的研究．模擬鳥集群飛行覓食的行為，鳥之間通過集體的協(xié)作使群體達到最優(yōu)目的，是一種基于Swarm

Intelligence的優(yōu)化方法。馬良教授在他的著作《蟻群優(yōu)化算法》一書的前言中寫到：“自然界的蟻群、鳥群、魚群、羊群、牛群、蜂群等，其實時時刻刻都在給予我們以某種啟示，只不過我們常常忽略了大自然對我們的最大恩賜！......”56粒子群算法的基本思想設(shè)想這樣一個場景：一群鳥在隨機搜索食物在這塊區(qū)域里只有一塊食物;已知

所有的鳥都不知道食物在哪里;但它們能感受到當(dāng)前的位置離食物還有多遠.那么:找到食物的最優(yōu)策略是什么呢？搜尋目前離食物最近的鳥的周圍區(qū)域．根據(jù)自己飛行的經(jīng)驗判斷食物的所在。PSO正是從這種模型中得到了啟發(fā)．PSO的基礎(chǔ):信息的社會共享7生物學(xué)家對鳥(魚)群捕食的行為研究社會行為(Social-Only

Model)個體認知(Cognition-Only

Model)8粒子群特性9算法介紹每個尋優(yōu)的問題解都被想像成一只鳥，稱為“粒子”。所有粒子都在一個D維空間進行搜索。所有的粒子都由一個fitness

function

確定適應(yīng)值以判斷目前的位置好壞。每一個粒子必須賦予記憶功能，能記住所搜尋到的最佳位置。每一個粒子還有一個速度以決定飛行的距離和方向。這個速度根據(jù)它本身的飛行經(jīng)驗以及同伴的飛行經(jīng)驗進行動態(tài)調(diào)整。10粒子群優(yōu)化算法求最優(yōu)解D維空間中，有N個粒子；粒子i位置：xi=(xi1,xi2,…xiD)，將xi代入適應(yīng)函數(shù)f(xi)求適應(yīng)值；粒子i速度：vi=(vi1,vi2,…viD)粒子i個體經(jīng)歷過的最好位置：pbesti=(pi1,pi2,…piD)種群所經(jīng)歷過的最好位置：gbest=(g1,g2,…gD)內(nèi)，通常，在第d（1≤d≤D）維的位置變化范圍限定在速度變化范圍限定在 內(nèi)（即在迭代中若超出了邊界值，則該維的速度或位置被限制為該維最大速度或邊界位置）11粒子i的第d維速度更新公式：粒子i的第d維位置更新公式：—第k次迭代粒子i飛行速度矢量的第d維分量—第k次迭代粒子i位置矢量的第d維分量

c1,c2—加速度常數(shù)，調(diào)節(jié)學(xué)習(xí)最大步長r1,r2—兩個隨機函數(shù)，取值范圍[0，1]，以增加搜索隨機性w—慣性權(quán)重，非負數(shù)，調(diào)節(jié)對解空間的搜索范圍12粒子速度更新公式包含三部分：第一部分為粒子先前的速度第二部分為“認知”部分，表示粒子本身的思考，可理解為粒子i當(dāng)前位置與自己最好位置之間的距離。第三部分為“社會”部分，表示粒子間的信息共享與合作，可理解為粒子i當(dāng)前位置與群體最好位置之間的距離。13區(qū)域最佳解全域最佳解Study

Factor14運動向量pg慣性向量15算法流程Initial：初始化粒子群體（群體規(guī)模為n），包括隨機位置和速度。Evaluation：根據(jù)fitnessfunction，評價每個粒子的適應(yīng)度。Find

the

Pbest：對每個粒子，將其當(dāng)前適應(yīng)值與其個體歷史最佳位置（pbest）對應(yīng)的適應(yīng)值做比較，如果當(dāng)前的適應(yīng)值更高，則將用當(dāng)前位置更新歷史最佳位置pbest。Find

the

Gbest：對每個粒子，將其當(dāng)前適應(yīng)值與全局最佳位置（gbest）對應(yīng)的適應(yīng)值做比較，如果當(dāng)前的適應(yīng)值更高，則將用當(dāng)前粒子的位置更新全局最佳位置gbest。Update

the

Velocity：根據(jù)公式更新每個粒子的速度與位置。如未滿足結(jié)束條件，則返回步驟2通常算法達到最大迭代次數(shù) 或者最佳適應(yīng)度值的增量小于某個給定的閾值時算法停止。16粒子群優(yōu)化算法流程圖開始初始化粒子群計算每個粒子的適應(yīng)度根據(jù)適應(yīng)度更新pbest、gbest，更新粒子位置速度noyes結(jié)束達到最大迭代次數(shù)或全局最優(yōu)位置滿足最小界限？172維簡例Note合理解目前最優(yōu)解區(qū)域最佳解全域區(qū)域18粒子群算法的構(gòu)成要素19-群體大小

mm是一個整型參數(shù)．m很小:陷入局優(yōu)的可能性很大．m很大:PSO的優(yōu)化能力很好，當(dāng)群體數(shù)目增長至一定水平時，再增長將不再有顯著的作用．粒子群算法的構(gòu)成要素-權(quán)重因子權(quán)重因子：慣性因子 、學(xué)習(xí)因子失去對粒子本身的速度的記憶社會經(jīng)驗部分自我認知部分基本粒子群算法粒子的速度更新主要由三部分組成：前次迭代中自身的速度慣性因子20粒子群算法的構(gòu)成要素-權(quán)重因子權(quán)重因子：慣性因子 、學(xué)習(xí)因子社會經(jīng)驗部分前次迭代中自身的速度自我認知部分粒子的速度更新主要由三部分組成：學(xué)習(xí)因子無私型粒子群算法

“只有社會，沒有自我”迅速喪失群體多樣性，21易陷入局優(yōu)而無法跳出．粒子群算法的構(gòu)成要素-權(quán)重因子權(quán)重因子：慣性因子 、學(xué)習(xí)因子社會經(jīng)驗部分前次迭代中自身的速度自我認知部分粒子的速度更新主要由三部分組成：自我認知型粒子群算法“只有自我，沒有社會”完全沒有信息的社會共享學(xué)習(xí)因子導(dǎo)致算法收斂速度緩慢22粒子群算法的構(gòu)成要素-權(quán)重因子權(quán)重因子：慣性因子 、學(xué)習(xí)因子社會經(jīng)驗部分自我認知部分粒子的速度更新主要由三部分組成：前次迭代中自身的速度c1,c2都不為0，稱為完全型粒子群算法完全型粒子群算法更容易保持收斂速度和搜索效果的均衡，是較好的選擇．23粒子群算法的構(gòu)成要素-最大速度作用:在于維護算法的探索能力與開發(fā)能力的平衡．Vm較大時，探索能力增強，但粒子容易飛過最優(yōu)解．Vm較小時，開發(fā)能力增強，但容易陷入局部最優(yōu)．Vm一般設(shè)為每維變量變化范圍的10％~20％.24粒子群算法的構(gòu)成要素-鄰域的拓撲結(jié)構(gòu)粒子群算法的鄰域拓撲結(jié)構(gòu)包括兩種，一種是將群體內(nèi)所有個體都作為粒子的鄰域，另一種是只將群體中的部分個體作為粒子的鄰域．群體歷史最優(yōu)位置鄰域拓撲結(jié)構(gòu)決定25由此，將粒子群算法分為全局粒子群算法和局部粒子群算法．粒子群算法的構(gòu)成要素-鄰域的拓撲結(jié)構(gòu)全局粒子群算法粒子自己歷史最優(yōu)值粒子群體的全局最優(yōu)值局部粒子群算法粒子自己歷史最優(yōu)值粒子鄰域內(nèi)粒子的最優(yōu)值鄰域隨迭代次數(shù)的增加線性變大，最后鄰域擴展到整個粒子群。

經(jīng)過實踐證明：全局版本的粒子群算法收斂速度快，但是容易陷入局部最優(yōu)。局部版本的粒子群算法收斂速度慢，但是很難陷入局部最優(yōu)?，F(xiàn)在的粒子群算法大都在收斂速度與擺脫局部最優(yōu)這兩個方面下功夫。其實這兩個方面是矛盾的?？慈绾胃玫恼壑辛恕?6粒子群算法的構(gòu)成要素-停止準則27停止準則一般有如下兩種：最大迭代步數(shù)

可接受的滿意解粒子群算法的構(gòu)成要素-粒子空間的初始化較好地選擇粒子的初始化空間，將大大縮短收斂時間．初始化空間根據(jù)具體問題的不同而不同，也就是說，這是問題依賴的．從上面的介紹可以看到，粒子群算法與其他現(xiàn)代優(yōu)化方法相比的一個明顯特色就是所需調(diào)整的參數(shù)很少．相對來說，慣性因子和鄰域定義較為重要．這些為數(shù)不多的關(guān)鍵參數(shù)的設(shè)置卻對算法的精度和效率有著顯著影響．28第九講daili粒子群算法293.

粒子群算法示例例

求解如下四維Rosenbrock函數(shù)的優(yōu)化問題．解

算法的相關(guān)設(shè)計分析如下．種群大小：即算法中粒子的數(shù)量，取編碼：因為問題的維數(shù)是4，所以每個粒子的位置和速度均4維的實數(shù)向量．設(shè)定粒子的最大速度：第九講daili

粒子群算法30對粒子群進行隨機初始化包括隨機初始化各粒子的位置和速度設(shè)各粒子的初始位置 和初始速度 為：初始位置：第九講daili

粒子群算法31對粒子群進行隨機初始化包括隨機初始化各粒子的位置和速度設(shè)各粒子的初始位置 和初始速度 為：初始速度：第九講daili粒子群算法32初始位置：初始速度：計算每個粒子的適應(yīng)值按照計算適應(yīng)值歷史最優(yōu)解第九講daili粒子群算法33取

，,得到速度和位置的更新函數(shù)為初始位置：初始速度：群體歷史最優(yōu)解：個體歷史最優(yōu)解：更新粒子的速度和位置：第九講daili粒子群算法34初始位置：初始速度：群體歷史最優(yōu)解：個體歷史最優(yōu)解：更新速度，得：第九講daili粒子群算法35更新位置，得：初始位置：初始速度：群體歷史最優(yōu)解：個體歷史最優(yōu)解：不強行拉回解空間第九講daili粒子群算法36初始位置：初始速度：群體歷史最優(yōu)解：個體歷史最優(yōu)解：更新位置，得：按照計算適應(yīng)值第九講daili粒子群算法37重復(fù)上述步驟，將迭代進行下去．按照計算適應(yīng)值歷史最優(yōu)解第九講daili粒子群算法38從上述結(jié)果，可以看出，經(jīng)過10000次迭代，粒子群算法得到了比較好的適應(yīng)值.第九講daili粒子群算法39第5步 更新粒子的速度和位置，公式如下．第6步 若未達到終止條件，則轉(zhuǎn)第2步．4.

粒子群算法流程第1步 在初始化范圍內(nèi)，對粒子群進行隨機初始化，包括隨機位置和速度．第2步 計算每個粒子的適應(yīng)值．第3步 更新粒子個體的歷史最優(yōu)位置．第4步更新粒子群體的歷史最優(yōu)位置．慣性權(quán)重1998年，Shi和Eberhart引入了慣性權(quán)重w，并提出動態(tài)調(diào)整慣性權(quán)重以平衡收斂的全局性和收斂速度，該算法被稱為標準PSO算法慣性權(quán)重w描述粒子上一代速度對當(dāng)前代速度的影響。

w值較大，全局尋優(yōu)能力強，局部尋優(yōu)能力弱；反之，則局部尋優(yōu)能力強。當(dāng)問題空間較大時，為了在搜索速度和搜索精度之間達到平衡，通常做法是使算法在前期有較高的全局搜索能力以得到合適的種子，而在后期有較高的局部搜索能力以提高收斂精度。所以w不宜為一個固定的常數(shù)。40線性遞減權(quán)值wmax最大慣性權(quán)重，wmin最小慣性權(quán)重，run當(dāng)前迭代次數(shù)，runmax為算法迭代總次數(shù)較大的w有較好的全局收斂能力，較小的w則有較強的局部收斂能力。因此，隨著迭代次數(shù)的增加，慣性權(quán)重w應(yīng)不斷減少，從而使得粒子群算法在初期