粒子群優(yōu)化算法詳細(xì)易懂很多例子

粒子群優(yōu)化算法詳細(xì)易懂很多例子演示文稿目前一頁\總數(shù)四十四頁\編于十六點(diǎn)（優(yōu)選）粒子群優(yōu)化算法詳細(xì)易懂很多例子目前二頁\總數(shù)四十四頁\編于十六點(diǎn)解決最優(yōu)化問題的方法傳統(tǒng)搜索方法保證能找到最優(yōu)解HeuristicSearch不能保證找到最優(yōu)解目前三頁\總數(shù)四十四頁\編于十六點(diǎn)

由Kennedy和Eberhart于1995年提出．群體迭代，粒子在解空間追隨最優(yōu)的粒子進(jìn)行搜索.簡(jiǎn)單易行粒子群算法:收斂速度快設(shè)置參數(shù)少已成為現(xiàn)代優(yōu)化方法領(lǐng)域研究的熱點(diǎn)．粒子群算法發(fā)展歷史簡(jiǎn)介

目前四頁\總數(shù)四十四頁\編于十六點(diǎn)粒子群算法的基本思想粒子群算法的思想源于對(duì)鳥群捕食行為的研究．模擬鳥集群飛行覓食的行為，鳥之間通過集體的協(xié)作使群體達(dá)到最優(yōu)目的，是一種基于SwarmIntelligence的優(yōu)化方法。馬良教授在他的著作《蟻群優(yōu)化算法》一書的前言中寫到：大自然對(duì)我們的最大恩賜！“自然界的蟻群、鳥群、魚群、羊群、牛群、蜂群等，其實(shí)時(shí)時(shí)刻刻都在給予我們以某種啟示，只不過我們常常忽略了大自然對(duì)我們的最大恩賜！......”目前五頁\總數(shù)四十四頁\編于十六點(diǎn)目前六頁\總數(shù)四十四頁\編于十六點(diǎn)粒子群算法的基本思想

設(shè)想這樣一個(gè)場(chǎng)景：一群鳥在隨機(jī)搜索食物在這塊區(qū)域里只有一塊食物;所有的鳥都不知道食物在哪里;

但它們能感受到當(dāng)前的位置離食物還有多遠(yuǎn).

已知那么:找到食物的最優(yōu)策略是什么呢？

搜尋目前離食物最近的鳥的周圍區(qū)域．根據(jù)自己飛行的經(jīng)驗(yàn)判斷食物的所在。PSO正是從這種模型中得到了啟發(fā)．

PSO的基礎(chǔ):

信息的社會(huì)共享

目前七頁\總數(shù)四十四頁\編于十六點(diǎn)生物學(xué)家對(duì)鳥(魚)群捕食的行為研究

社會(huì)行為(Social-OnlyModel)個(gè)體認(rèn)知(Cognition-OnlyModel)目前八頁\總數(shù)四十四頁\編于十六點(diǎn)粒子群特性目前九頁\總數(shù)四十四頁\編于十六點(diǎn)算法介紹

每個(gè)尋優(yōu)的問題解都被想像成一只鳥，稱為“粒子”。所有粒子都在一個(gè)D維空間進(jìn)行搜索。所有的粒子都由一個(gè)fitnessfunction

確定適應(yīng)值以判斷目前的位置好壞。每一個(gè)粒子必須賦予記憶功能，能記住所搜尋到的最佳位置。每一個(gè)粒子還有一個(gè)速度以決定飛行的距離和方向。這個(gè)速度根據(jù)它本身的飛行經(jīng)驗(yàn)以及同伴的飛行經(jīng)驗(yàn)進(jìn)行動(dòng)態(tài)調(diào)整。目前十頁\總數(shù)四十四頁\編于十六點(diǎn)粒子群優(yōu)化算法求最優(yōu)解

D維空間中，有N個(gè)粒子；粒子i位置：xi=(xi1,xi2,…xiD)，將xi代入適應(yīng)函數(shù)f(xi)求適應(yīng)值；粒子i速度：vi=(vi1,vi2,…viD)

粒子i個(gè)體經(jīng)歷過的最好位置：pbesti=(pi1,pi2,…piD)

種群所經(jīng)歷過的最好位置：gbest=(g1,g2,…gD)通常，在第d（1≤d≤D）維的位置變化范圍限定在內(nèi)，速度變化范圍限定在內(nèi)（即在迭代中若超出了邊界值，則該維的速度或位置被限制為該維最大速度或邊界位置）

目前十一頁\總數(shù)四十四頁\編于十六點(diǎn)粒子i的第d維速度更新公式：

粒子i的第d維位置更新公式：

—第k次迭代粒子i飛行速度矢量的第d維分量

—第k次迭代粒子i位置矢量的第d維分量

c1,c2—加速度常數(shù)，調(diào)節(jié)學(xué)習(xí)最大步長(zhǎng)

r1,r2—兩個(gè)隨機(jī)函數(shù)，取值范圍[0，1]，以增加搜索隨機(jī)性

w—慣性權(quán)重，非負(fù)數(shù)，調(diào)節(jié)對(duì)解空間的搜索范圍目前十二頁\總數(shù)四十四頁\編于十六點(diǎn)粒子速度更新公式包含三部分：第一部分為粒子先前的速度第二部分為“認(rèn)知”部分，表示粒子本身的思考，可理解為粒子i當(dāng)前位置與自己最好位置之間的距離。第三部分為“社會(huì)”部分，表示粒子間的信息共享與合作，可理解為粒子i當(dāng)前位置與群體最好位置之間的距離。目前十三頁\總數(shù)四十四頁\編于十六點(diǎn)區(qū)域最佳解全域最佳解運(yùn)動(dòng)向量慣性向量

StudyFactorpg目前十四頁\總數(shù)四十四頁\編于十六點(diǎn)目前十五頁\總數(shù)四十四頁\編于十六點(diǎn)算法流程Initial：

初始化粒子群體（群體規(guī)模為n），包括隨機(jī)位置和速度。Evaluation：

根據(jù)fitnessfunction，評(píng)價(jià)每個(gè)粒子的適應(yīng)度。FindthePbest：對(duì)每個(gè)粒子，將其當(dāng)前適應(yīng)值與其個(gè)體歷史最佳位置（pbest）對(duì)應(yīng)的適應(yīng)值做比較，如果當(dāng)前的適應(yīng)值更高，則將用當(dāng)前位置更新歷史最佳位置pbest。FindtheGbest：

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

根據(jù)公式更新每個(gè)粒子的速度與位置。如未滿足結(jié)束條件，則返回步驟2通常算法達(dá)到最大迭代次數(shù)或者最佳適應(yīng)度值的增量小于某個(gè)給定的閾值時(shí)算法停止。目前十六頁\總數(shù)四十四頁\編于十六點(diǎn)粒子群優(yōu)化算法流程圖

開始初始化粒子群計(jì)算每個(gè)粒子的適應(yīng)度根據(jù)適應(yīng)度更新pbest、gbest，更新粒子位置速度結(jié)束noyes達(dá)到最大迭代次數(shù)或全局最優(yōu)位置滿足最小界限？目前十七頁\總數(shù)四十四頁\編于十六點(diǎn)2維簡(jiǎn)例Note合理解目前最優(yōu)解區(qū)域最佳解全域區(qū)域目前十八頁\總數(shù)四十四頁\編于十六點(diǎn)粒子群算法的構(gòu)成要素

-群體大小m

m是一個(gè)整型參數(shù)．

m

很小:

m很大:

當(dāng)群體數(shù)目增長(zhǎng)至一定水平時(shí)，再增長(zhǎng)將不再有顯

但收斂速度慢．著的作用．陷入局優(yōu)的可能性很大．

PSO的優(yōu)化能力很好，目前十九頁\總數(shù)四十四頁\編于十六點(diǎn)粒子群算法的構(gòu)成要素-權(quán)重因子

權(quán)重因子：慣性因子、學(xué)習(xí)因子

失去對(duì)粒子本身的速度的記憶

社會(huì)經(jīng)驗(yàn)部分

前次迭代中自身的速度

自我認(rèn)知部分

基本粒子群算法粒子的速度更新主要由三部分組成：

慣性因子

目前二十頁\總數(shù)四十四頁\編于十六點(diǎn)粒子群算法的構(gòu)成要素-權(quán)重因子

權(quán)重因子：慣性因子、學(xué)習(xí)因子

社會(huì)經(jīng)驗(yàn)部分

前次迭代中自身的速度

自我認(rèn)知部分

粒子的速度更新主要由三部分組成：

學(xué)習(xí)因子

無私型粒子群算法

“只有社會(huì)，沒有自我”迅速喪失群體多樣性，易陷入局優(yōu)而無法跳出．目前二十一頁\總數(shù)四十四頁\編于十六點(diǎn)粒子群算法的構(gòu)成要素-權(quán)重因子

權(quán)重因子：慣性因子、學(xué)習(xí)因子

社會(huì)經(jīng)驗(yàn)部分

前次迭代中自身的速度

自我認(rèn)知部分

粒子的速度更新主要由三部分組成：

自我認(rèn)知型粒子群算法

“只有自我，沒有社會(huì)”完全沒有信息的社會(huì)共享，導(dǎo)致算法收斂速度緩慢

學(xué)習(xí)因子

目前二十二頁\總數(shù)四十四頁\編于十六點(diǎn)粒子群算法的構(gòu)成要素-權(quán)重因子

權(quán)重因子：慣性因子、學(xué)習(xí)因子

社會(huì)經(jīng)驗(yàn)部分

前次迭代中自身的速度

自我認(rèn)知部分

粒子的速度更新主要由三部分組成：

c1,c2都不為0，稱為完全型粒子群算法

完全型粒子群算法更容易保持收斂速度和搜索效果的均衡，是較好的選擇．

目前二十三頁\總數(shù)四十四頁\編于十六點(diǎn)粒子群算法的構(gòu)成要素-最大速度

但

在于維護(hù)算法的探索能力與開發(fā)能力的平衡．

Vm較大時(shí)，探索能力增強(qiáng)，

作用:

Vm較小時(shí)，開發(fā)能力增強(qiáng)，

Vm一般設(shè)為每維變量變化范圍的10％~20％.

但

粒子容易飛過最優(yōu)解．

容易陷入局部最優(yōu)．

目前二十四頁\總數(shù)四十四頁\編于十六點(diǎn)粒子群算法的構(gòu)成要素-

鄰域的拓?fù)浣Y(jié)構(gòu)

全局粒子群算法和局部粒子群算法．

粒子群算法的鄰域拓?fù)浣Y(jié)構(gòu)包括兩種，一種是將群體內(nèi)所有個(gè)體都作為粒子的鄰域，另一種是只將群體中的部分個(gè)體作為粒子的鄰域．群體歷史最優(yōu)位置

鄰域拓?fù)浣Y(jié)構(gòu)決定

由此，將粒子群算法分為目前二十五頁\總數(shù)四十四頁\編于十六點(diǎn)粒子群算法的構(gòu)成要素-

鄰域的拓?fù)浣Y(jié)構(gòu)

全局粒子群算法1.粒子自己歷史最優(yōu)值2.

粒子群體的全局最優(yōu)值局部粒子群算法1.粒子自己歷史最優(yōu)值2.粒子鄰域內(nèi)粒子的最優(yōu)值

鄰域隨迭代次數(shù)的增加線性變大，最后鄰域擴(kuò)展到整個(gè)粒子群。經(jīng)過實(shí)踐證明：全局版本的粒子群算法收斂速度快，但是容易陷入局部最優(yōu)。局部版本的粒子群算法收斂速度慢，但是很難陷入局部最優(yōu)?，F(xiàn)在的粒子群算法大都在收斂速度與擺脫局部最優(yōu)這兩個(gè)方面下功夫。其實(shí)這兩個(gè)方面是矛盾的?？慈绾胃玫恼壑辛?。目前二十六頁\總數(shù)四十四頁\編于十六點(diǎn)

粒子群算法的構(gòu)成要素-停止準(zhǔn)則

停止準(zhǔn)則一般有如下兩種：

最大迭代步數(shù)

可接受的滿意解

目前二十七頁\總數(shù)四十四頁\編于十六點(diǎn)

粒子群算法的構(gòu)成要素-

粒子空間的初始化

較好地選擇粒子的初始化空間，將大大縮短收斂時(shí)間．初始化空間根據(jù)具體問題的不同而不同，也就是說，這是問題依賴的．

從上面的介紹可以看到，粒子群算法與其他現(xiàn)代優(yōu)化方法相比的一個(gè)明顯特色就是所需調(diào)整的參數(shù)很少．相對(duì)來說，慣性因子和鄰域定義較為重要．這些為數(shù)不多的關(guān)鍵參數(shù)的設(shè)置卻對(duì)算法的精度和效率有著顯著影響．目前二十八頁\總數(shù)四十四頁\編于十六點(diǎn)3.粒子群算法示例

例求解如下四維Rosenbrock函數(shù)的優(yōu)化問題．種群大?。?/p>

解算法的相關(guān)設(shè)計(jì)分析如下．

編碼：因?yàn)閱栴}的維數(shù)是4，所以每個(gè)粒子的位置和即算法中粒子的數(shù)量，取速度均4維的實(shí)數(shù)向量．設(shè)定粒子的最大速度：目前二十九頁\總數(shù)四十四頁\編于十六點(diǎn)初始位置：

設(shè)各粒子的初始位置和初始速度為：

對(duì)粒子群進(jìn)行隨機(jī)初始化包括隨機(jī)初始化各粒子的位置和速度

目前三十頁\總數(shù)四十四頁\編于十六點(diǎn)初始速度：設(shè)各粒子的初始位置和初始速度為：

對(duì)粒子群進(jìn)行隨機(jī)初始化包括隨機(jī)初始化各粒子的位置和速度目前三十一頁\總數(shù)四十四頁\編于十六點(diǎn)初始速度：初始位置：

計(jì)算每個(gè)粒子的適應(yīng)值

按照計(jì)算適應(yīng)值歷史最優(yōu)解目前三十二頁\總數(shù)四十四頁\編于十六點(diǎn)更新粒子的速度和位置：取，

,得到速度和位置的更新函數(shù)為初始速度：初始位置：

群體歷史最優(yōu)解：個(gè)體歷史最優(yōu)解：目前三十三頁\總數(shù)四十四頁\編于十六點(diǎn)更新速度，得：初始速度：初始位置：

群體歷史最優(yōu)解：個(gè)體歷史最優(yōu)解：目前三十四頁\總數(shù)四十四頁\編于十六點(diǎn)更新位置，得：初始速度：初始位置：

群體歷史最優(yōu)解：個(gè)體歷史最優(yōu)解：不強(qiáng)行拉回解空間目前三十五頁\總數(shù)四十四頁\編于十六點(diǎn)更新位置，得：初始速度：初始位置：

群體歷史最優(yōu)解：個(gè)體歷史最優(yōu)解：按照計(jì)算適應(yīng)值目前三十六頁\總數(shù)四十四頁\編于十六點(diǎn)重復(fù)上述步驟，將迭代進(jìn)行下去．

按照計(jì)算適應(yīng)值歷史最優(yōu)解目前三十七頁\總數(shù)四十四頁\編于十六點(diǎn)從上述結(jié)果，可以看出，經(jīng)過10000次迭代，粒子群算法得到了比較好的適應(yīng)值.

目前三十八頁\總數(shù)四十四頁\編于十六點(diǎn)4.粒子群算法流程第2步計(jì)算每個(gè)粒子的適應(yīng)值．第1步在初始化范圍內(nèi)，對(duì)粒子群進(jìn)行隨機(jī)初始化，第5步更新粒子的速度和位置，公式如下．第3步更新粒子個(gè)體的歷史最優(yōu)位置．第6步若未達(dá)到終止條件，則轉(zhuǎn)第2步．包括隨機(jī)位置和速度．第4步更新粒子群體的歷史最優(yōu)位置．目前三十九頁\總數(shù)四十四頁\編于十