美賽數(shù)模智能算法之粒子群優(yōu)化算法

1、美賽數(shù)模智能算法之 粒子群算法（PSO）,主講人：老教練,智能算法,向大自然學(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ì)退火過程,由Kennedy和Eberhart于1995年提出 群體迭代，粒子在解空間追隨最優(yōu)的粒子進行搜索. 簡單易行 粒子群算法: 收斂速度快 設(shè)置參數(shù)少 已成為現(xiàn)代優(yōu)化方法領(lǐng)域研究的熱點,粒子群算法發(fā)展歷史簡介,粒子群算法的基本思想,粒子群算法的思想源于對鳥群捕食行為的研究 模擬鳥集群

2、飛行覓食的行為，鳥之間通過集體的協(xié)作使群體達到最優(yōu)目的，是一種基于Swarm Intelligence的優(yōu)化方法。 馬良教授在他的著作蟻群優(yōu)化算法一書的前言中寫到： 大自然對我們的最大恩賜！,“自然界的蟻群、鳥群、魚群、 羊群、牛群、蜂群等，其實時時刻刻都在給予 我們以某種啟示，只不過我們常常忽略了 大自然對我們的最大恩賜！.”,粒子群算法的基本思想,設(shè)想這樣一個場景：一群鳥在隨機搜索食物,在這塊區(qū)域里只有一塊食物;,所有的鳥都不知道食物在哪里;,但它們能感受到當(dāng)前的位置離食物還有多遠.,已知,那么:找到食物的最優(yōu)策略是什么呢？,搜尋目前離食物最近的鳥的周圍區(qū)域 根據(jù)自己飛行的經(jīng)驗判斷食物的所

3、在。,PSO正是從這種模型中得到了啟發(fā),PSO的基礎(chǔ):,信息的社會共享,生物學(xué)家對鳥(魚)群捕食的行為研究 社會行為 (Social-Only Model) 個體認(rèn)知 (Cognition-Only Model),粒子群特性,算法介紹,每個尋優(yōu)的問題解都被想像成一只鳥，稱為“粒子”。所有粒子都在一個D維空間進行搜索。 所有的粒子都由一個fitness function 確定適應(yīng)值以判斷目前的位置好壞。 每一個粒子必須賦予記憶功能，能記住所搜尋到的最佳位置。 每一個粒子還有一個速度以決定飛行的距離和方向。這個速度根據(jù)它本身的飛行經(jīng)驗以及同伴的飛行經(jīng)驗進行動態(tài)調(diào)整。,粒子群優(yōu)化算法求最優(yōu)解,D維空

4、間中，有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) 通常，在第d（1dD）維的位置變化范圍限定在 內(nèi)， 速度變化范圍限定在 內(nèi)（即在迭代中若 超出了邊界值，則該維的速度或位置被限制為該維最大速度或邊界 位置）,粒子群算法迭代過程,粒子i的第d維速度更新公式： 粒子i的第d維位置更新公式： 第k次迭代粒子i飛行速度矢量的第d維分量 第k次迭代粒子i位置矢量的第d維分量 c

5、1,c2加速度常數(shù)，調(diào)節(jié)學(xué)習(xí)最大步長 r1,r2兩個隨機函數(shù)，取值范圍0，1，以增加搜索隨機性 w 慣性權(quán)重，非負數(shù)，調(diào)節(jié)對解空間的搜索范圍,粒子速度更新公式包含三部分： 第一部分為粒子先前的速度 第二部分為“認(rèn)知”部分，表示粒子本身的思考，可理解為粒子i當(dāng)前位置與自己最好位置之間的距離。 第三部分為“社會”部分，表示粒子間的信息共享與合作，可理解為粒子i當(dāng)前位置與群體最好位置之間的距離。,區(qū)域 最佳解,全域 最佳解,運動向量,慣性向量,Study Factor,pg,算法流程,Initial： 初始化粒子群體（群體規(guī)模為n），包括隨機位置和速度。 Evaluation： 根據(jù)fitness

6、function ，評價每個粒子的適應(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)度值的增量小于某個給定的閾值時算法停止。,粒子群

7、優(yōu)化算法流程圖,2維簡例,Note,合理解,目前最優(yōu)解,區(qū)域最佳解,全域,區(qū)域,粒子群算法的構(gòu)成要素 -群體大小 m,m 是一個整型參數(shù),m 很小:,m 很大:,當(dāng)群體數(shù)目增長至一定水平時，再增長將不再有顯,但收斂速度慢,著的作用,陷入局優(yōu)的可能性很大,PSO的優(yōu)化能力很好，,粒子群算法的構(gòu)成要素 -權(quán)重因子,權(quán)重因子：慣性因子 、學(xué)習(xí)因子,失去對粒子本身 的速度的記憶,社會經(jīng)驗部分,前次迭代中自身的速度,自我認(rèn)知部分,基本粒子群算法,粒子的速度更新主要由三部分組成：,慣性因子,粒子群算法的構(gòu)成要素-權(quán)重因子,權(quán)重因子：慣性因子 、學(xué)習(xí)因子,社會經(jīng)驗部分,前次迭代中自身的速度,自我認(rèn)知部分,粒

8、子的速度更新主要由三部分組成：,學(xué)習(xí)因子,無私型粒子群算法,“只有社會，沒有自我”,迅速喪失群體多樣性， 易陷入局優(yōu)而無法跳出,粒子群算法的構(gòu)成要素 -權(quán)重因子,權(quán)重因子：慣性因子 、學(xué)習(xí)因子,社會經(jīng)驗部分,前次迭代中自身的速度,自我認(rèn)知部分,粒子的速度更新主要由三部分組成：,自我認(rèn)知型粒子群算法,“只有自我，沒有社會”,完全沒有信息的社會共享， 導(dǎo)致算法收斂速度緩慢,學(xué)習(xí)因子,粒子群算法的構(gòu)成要素-權(quán)重因子,權(quán)重因子：慣性因子 、學(xué)習(xí)因子,社會經(jīng)驗部分,前次迭代中自身的速度,自我認(rèn)知部分,粒子的速度更新主要由三部分組成：,c1,c2都不為0，稱為 完全型粒子群算法,完全型粒子群算法更容易保持

9、收斂速度和搜索效果的均衡，是較好的選擇,粒子群算法的構(gòu)成要素-最大速度,但,在于維護算法的探索能力與開發(fā)能力的平衡,Vm較大時，探索能力增強，,作用:,Vm較小時，開發(fā)能力增強，,Vm一般設(shè)為每維變量變化范圍的1020.,但,粒子容易飛過最優(yōu)解,容易陷入局部最優(yōu),粒子群算法的構(gòu)成要素- 鄰域的拓撲結(jié)構(gòu),全局粒子群算法和局部粒子群算法,粒子群算法的鄰域拓撲結(jié)構(gòu)包括兩種，,一種是將群體內(nèi)所有個體都作為粒子的鄰域，,另一種是只將群體中的部分個體作為粒子的鄰域,群體歷史最優(yōu)位置,鄰域拓撲結(jié)構(gòu),決定,由此，將粒子群算法分為,粒子群算法的構(gòu)成要素- 鄰域的拓撲結(jié)構(gòu),全局粒子群算法 1. 粒子自己歷史最優(yōu)值

10、 2. 粒子群體的全局最優(yōu)值 局部粒子群算法 1. 粒子自己歷史最優(yōu)值 2. 粒子鄰域內(nèi)粒子的最優(yōu)值 鄰域隨迭代次數(shù)的增加線性變大，最后鄰域擴展到整個粒子群。 經(jīng)過實踐證明：全局版本的粒子群算法收斂速度快，但是容易陷入局部最優(yōu)。局部版本的粒子群算法收斂速度慢，但是很難陷入局部最優(yōu)?，F(xiàn)在的粒子群算法大都在收斂速度與擺脫局部最優(yōu)這兩個方面下功夫。其實這兩個方面是矛盾的。看如何更好的折中了。,粒子群算法的構(gòu)成要素 -停止準(zhǔn)則,停止準(zhǔn)則一般有如下兩種：,最大迭代步數(shù),可接受的滿意解,粒子群算法的構(gòu)成要素 - 粒子空間的初始化,較好地選擇粒子的初始化空間，將大大縮短收 斂時間初始化空間根據(jù)具體問題的不同

11、而不同， 也就是說，這是問題依賴的,從上面的介紹可以看到，粒子群算法與其他現(xiàn)代 優(yōu)化方法相比的一個明顯特色就是所需調(diào)整的參數(shù)很 少相對來說，慣性因子和鄰域定義較為重要這些 為數(shù)不多的關(guān)鍵參數(shù)的設(shè)置卻對算法的精度和效率有 著顯著影響,3. 粒子群算法示例,例 求解如下四維Rosenbrock函數(shù)的優(yōu)化問題,種群大?。?解 算法的相關(guān)設(shè)計分析如下,編碼：因為問題的維數(shù)是4，所以每個粒子的位置和,即算法中粒子的數(shù)量，取,速度均4 維的實數(shù)向量,設(shè)定粒子的最大速度：,初始位置：,設(shè)各粒子的初始位置 和初始速度 為：,對粒子群進行隨機初始化,包括隨機初始化各粒子的位置和速度,初始速度：,設(shè)各粒子的初始位

12、置 和初始速度 為：,對粒子群進行隨機初始化,包括隨機初始化各粒子的位置和速度,初始速度：,初始位置：,計算每個粒子的適應(yīng)值,歷史最優(yōu)解,更新粒子的速度和位置：,初始速度：,初始位置：,群體歷史最優(yōu)解：,個體歷史最優(yōu)解：,更新速度，得：,初始速度：,初始位置：,群體歷史最優(yōu)解：,個體歷史最優(yōu)解：,更新位置，得：,初始速度：,初始位置：,群體歷史最優(yōu)解：,個體歷史最優(yōu)解：,不強行拉回解空間,更新位置，得：,初始速度：,初始位置：,群體歷史最優(yōu)解：,個體歷史最優(yōu)解：,重復(fù)上述步驟，將迭代進行下去,歷史最優(yōu)解,從上述結(jié)果，可以看出，經(jīng)過10000次迭代， 粒子群算法得到了比較好的適應(yīng)值.,4. 粒子

13、群算法流程,第2步 計算每個粒子的適應(yīng)值,第1步 在初始化范圍內(nèi)，對粒子群進行隨機初始化，,第5步 更新粒子的速度和位置，公式如下,第3步 更新粒子個體的歷史最優(yōu)位置,第6步 若未達到終止條件，則轉(zhuǎn)第2步,包括隨機位置和速度,第4步 更新粒子群體的歷史最優(yōu)位置,慣性權(quán)重,1998年，Shi和Eberhart引入了慣性權(quán)重w，并提出動態(tài)調(diào)整慣性權(quán)重以平衡收斂的全局性和收斂速度，該算法被稱為標(biāo)準(zhǔn)PSO算法 慣性權(quán)重w描述粒子上一代速度對當(dāng)前代速度的影響。w值較大，全局尋優(yōu)能力強，局部尋優(yōu)能力弱；反之，則局部尋優(yōu)能力強。當(dāng)問題空間較大時，為了在搜索速度和搜索精度之間達到平衡，通常做法是使算法在前期有較高的全局搜索能力以得到合適的種子，而在后期有較高的局部搜索能力以提高收斂精度。所以w不宜為一個固定的常數(shù)。,線性遞減權(quán)值,最大慣性權(quán)重， 最小慣性權(quán)重，run當(dāng)前迭代次數(shù)，runmax為算法迭代總次數(shù) 較大的w有較好的全局收斂能力，較小的w則有較強的局部收斂能力。因此，隨著迭代次數(shù)的增加，慣性權(quán)重w應(yīng)不斷減少，從而使得粒子