粒子群優(yōu)化算法(詳細易懂)

1、粒子群優(yōu)化算法（PS0,Particle Swarm Optimization,智能算法,向大自然學習 遺傳算法(GA) 物競天擇，設計染色體編碼，根據適應值函數進行染色體選擇、交叉和變異操作，優(yōu)化求解 人工神經網絡算法(ANN) 模仿生物神經元，透過神經元的信息傳遞、訓練學習、聯想，優(yōu)化求解 模擬退火算法(SA) 模模仿金屬物質退火過程,解決最優(yōu)化問題的方法,傳統(tǒng)搜索方法 保證能找到最優(yōu)解 Heuristic Search 不能保證找到最優(yōu)解,由Kennedy和Eberhart于1995年提出 群體迭代，粒子在解空間追隨最優(yōu)的粒子進行搜索. 簡單易行 粒子群算法: 收斂速度快 設置參數少 已

2、成為現代優(yōu)化方法領域研究的熱點,粒子群算法發(fā)展歷史簡介,粒子群算法的基本思想,粒子群算法的思想源于對鳥群捕食行為的研究 模擬鳥集群飛行覓食的行為，鳥之間通過集體的協(xié)作使群體達到最優(yōu)目的，是一種基于Swarm Intelligence的優(yōu)化方法。 馬良教授在他的著作蟻群優(yōu)化算法一書的前言中寫到： 大自然對我們的最大恩賜,自然界的蟻群、鳥群、魚群、 羊群、牛群、蜂群等，其實時時刻刻都在給予 我們以某種啟示，只不過我們常常忽略了 大自然對我們的最大恩賜！.,粒子群算法的基本思想,設想這樣一個場景：一群鳥在隨機搜索食物,在這塊區(qū)域里只有一塊食物,所有的鳥都不知道食物在哪里,但它們能感受到當前的位置離食

3、物還有多遠,已知,那么:找到食物的最優(yōu)策略是什么呢,搜尋目前離食物最近的鳥的周圍區(qū)域 根據自己飛行的經驗判斷食物的所在,PSO正是從這種模型中得到了啟發(fā),PSO的基礎,信息的社會共享,生物學家對鳥(魚)群捕食的行為研究 社會行為 (Social-Only Model) 個體認知 (Cognition-Only Model,粒子群特性,算法介紹,每個尋優(yōu)的問題解都被想像成一只鳥，稱為“粒子”。所有粒子都在一個D維空間進行搜索。 所有的粒子都由一個fitness function 確定適應值以判斷目前的位置好壞。 每一個粒子必須賦予記憶功能，能記住所搜尋到的最佳位置。 每一個粒子還有一個速度以決定

4、飛行的距離和方向。這個速度根據它本身的飛行經驗以及同伴的飛行經驗進行動態(tài)調整,粒子群優(yōu)化算法求最優(yōu)解,D維空間中，有N個粒子； 粒子i位置：xi=(xi1,xi2,xiD)，將xi代入適應函數f(xi)求適應值； 粒子i速度：vi=(vi1,vi2,viD) 粒子i個體經歷過的最好位置：pbesti=(pi1,pi2,piD) 種群所經歷過的最好位置：gbest=(g1,g2,gD) 通常，在第d（1dD）維的位置變化范圍限定在 內， 速度變化范圍限定在 內（即在迭代中若 超出了邊界值，則該維的速度或位置被限制為該維最大速度或邊界 位置,粒子i的第d維速度更新公式： 粒子i的第d維位置更新公式

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

6、位置和速度。 Evaluation： 根據fitness function ，評價每個粒子的適應度。 Find the Pbest： 對每個粒子，將其當前適應值與其個體歷史最佳位置（pbest）對應的適應值做比較，如果當前的適應值更高，則將用當前位置更新歷史最佳位置pbest。 Find the Gbest： 對每個粒子，將其當前適應值與全局最佳位置（gbest）對應的適應值做比較，如果當前的適應值更高，則將用當前粒子的位置更新全局最佳位置gbest。 Update the Velocity： 根據公式更新每個粒子的速度與位置。 如未滿足結束條件，則返回步驟2 通常算法達到最大迭代次數 或者最

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

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

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

10、粒子自己歷史最優(yōu)值 2. 粒子群體的全局最優(yōu)值 局部粒子群算法 1. 粒子自己歷史最優(yōu)值 2. 粒子鄰域內粒子的最優(yōu)值 鄰域隨迭代次數的增加線性變大，最后鄰域擴展到整個粒子群。 經過實踐證明：全局版本的粒子群算法收斂速度快，但是容易陷入局部最優(yōu)。局部版本的粒子群算法收斂速度慢，但是很難陷入局部最優(yōu)?，F在的粒子群算法大都在收斂速度與擺脫局部最優(yōu)這兩個方面下功夫。其實這兩個方面是矛盾的?？慈绾胃玫恼壑辛?粒子群算法的構成要素 -停止準則,停止準則一般有如下兩種,最大迭代步數,可接受的滿意解,粒子群算法的構成要素 - 粒子空間的初始化,較好地選擇粒子的初始化空間，將大大縮短收 斂時間初始化空間根據

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

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

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