深度學習經典算法 | 粒子群算法詳解

粒子群算法（PSO）基本思想

粒子群（PSO）算法最早是由美國電氣工程師Eberhart和社會心理學家Kennedy在1995年基于群鳥覓食提出來的。

群鳥覓食其實是一個最佳決策的過程， 與人類決策的過程相似。Boyd和Re chars on探索了人類的決策過程，并提出了個體學習和文化傳遞的概念。根據他們的研究成果，人們在決策過程中常常會綜合兩種重要的信息：第一種是他們自己的經驗，即他們根據以前自己的嘗試和經歷，已經積累了一定的經驗，知道怎樣的狀態會比較好；第二種是其他人的經驗，即從周圍人的行為獲取知識，從中知道哪些選擇是正面的，哪些選擇是消極的。

同樣的道理，群鳥在覓食的過程中，每只鳥的初始狀態都處于隨機位置，且飛翔的方向也是隨機的。每只鳥都不知道食物在哪里，但是隨著時間的推移，這些初始處于隨機位置的鳥類通過群內相互學習、信息共享和個體不斷積累字覓食物的經驗，自發組織積聚成一個群落，并逐漸朝唯一的目標-—食物前進。每只鳥能夠通過一定經驗和信息估計目前所處的位置對于能尋找到食物有多大的價值，即多大的適應值；每只鳥能夠記住自己所找到的最好位置，稱之為局部最優(p best) 。此外， 還能記住群鳥中所有個體所能找到的最好位置， 稱為全局最優(g best) ， 整個鳥群的覓食中心都趨向全局最優移動， 這在生物學上稱之為“同步效應”。通過鳥群覓食的位置不斷移動，即不斷迭代，可以使鳥群朝食物步步進逼。

在群鳥覓食模型中，每個個體都可以被看成一個粒子，則鳥群可以被看成一個粒子群。假設在一個Ｄ維的目標搜索空間中，有m個粒子組成一個群體，其中第i個粒子(i=1，2，…，m)位置表示為 X i = ( x i 1 ， x i 2 , … ， x i D ) X_{i}=(x_{i}^{1}，x_{i}^{2},…，x_{i}^{D}) Xi =(xi1 ，xi2 ,…，xiD )，即第i個粒子在Ｄ維搜索空間中的位置是 X i X_{i} Xi 。換言之，每個粒子的位置就是一個潛在解，將X，代人目標函數就可以計算出其適應值，根據適應值的大小衡量其優劣。粒子個體經歷過的最好位置記為 P i = ( P i 1 ， P i 2 , … ， P i D ) P_{i}=(P_{i}^{1}，P_{i}^{2},…，P_{i}^{D}) Pi =(Pi1 ，Pi2 ,…，PiD )，整個群體所有粒子經歷過的最好位置記為 P g = ( p g 1 ， p g 2 , … ， p g D ) P_{g}=(p_{g}^{1}，p_{g}^{2},…，p_{g}^{D}) Pg =(pg1 ，pg2 ,…，pgD )。粒子i的速度記為 V i = ( v i 1 ， v i 2 , … ， v i D ) V_{i}=(v_{i}^{1}，v_{i}^{2},…，v_{i}^{D}) Vi =(vi1 ，vi2 ,…，viD )。

粒子群算法采用下列公式對粒子所在的位置不斷更新(單位時間1)：

v i d = ω v i d + c 1 r 1 ( p i d ? x i d ) + c 2 r 2 ( p g d ? x i d ) ( 8 ? 1 ) v_{i}^ec2ec8q=\omega v_{i}^o000o0c+c_{1}r_{1}(p_{i}^ykm28im-x_{i}^6o0yays)+ c_{2}r_{2}(p_{g}^60mk8u0-x_{i}^6k2usou) (8-1) vid =ωvid +c1 r1 (pid ?xid )+c2 r2 (pgd ?xid )(8?1)

x i d = x i d + α v i d ( 8 ? 2 ) x_{i}^s2ca0ai= x_{i}^0a0i2ck+\alpha v_{i}^ummkyqa (8-2) xid =xid +αvid (8?2)

其中，i=1，2，…m；d=1，2，…，D；w是非負數、稱為慣性因子；加速常數c：和ca是非負常數； r 1 r_{1} r1 和 r 2 r_{2} r2 是[0，1]范圍內變換的隨機數；α稱為約束因子，目的是控制速度的權重。

此外， v i d ∈ [ ? v m a x d , v m a x d ] v_{i}^wyyywcu\in [-v_{max}^e0ug0wq,v_{max}^gky2smq] vid ∈[?vmaxd ,vmaxd ] 即粒子i的飛翔速度V， 被一個最大速度 V m a x = ( v m a x 1 , v m a x 2 , … ， v m a x D ） V_{max}=(v_{max}^{1},v_{max}^{2},…，v_{max}^{D}） Vmax =(vmax1 ,vmax2 ,…，vmaxD ）所限制。如果當前時刻粒子在某維的速度 v 1 d v_{1}^yam2k0m v1d 更新后超過該維的最大飛翔速度 v m a x d v_{max}^g00k2ye vmaxd 則當前時刻該維的速度被限制在 v m a x d v_{max}^6qe0saq vmaxd 。 v m a x v_{max} vmax 為常數， 可以根據不同的優化問題設定。

迭代終止條件根據具體問題設定，一般達到預訂最大迭代次數或粒子群且前為止搜索到的最優位置滿足目標函數的最小允許誤差。

PSO算法的優化

近年來， 一些學者將PSO算法推廣到約束優化問題，其關鍵在于如何處理好約束， 即解的可行性。如果約束處理得不好，其優化的結果往往會出現不能收斂和結果是空集的狀況?；赑SO算法的約束優化工作主要分為兩類：

①罰函數法。罰函數的目的是將約束優化問題轉化成無約束優化問題。

②將粒子群的搜索范圍都限制在條件約束簇內，即在可行解范圍內尋優。

Parsopoulos等采用罰函數法，利用非固定多段映射函數對約束優化問題進行轉

圖解Python數據結構與算法-實戰篇

PSO算法的優缺點

PSO算法的搜索性能取決于其全局探索和局部細化的平衡，這在很大程度上依賴于算法的控制參數，包括粒子群初始化、慣性因子w、最大飛翔速度 v m a x v_{max} vmax 和加速常數 c 1 c_{1} c1 與 c 2 c_{2} c2 等。PSO算法具有以下優點：

1)不依賴于問題信息，采用實數求解，算法通用性強。

需要調整的參數少，原理簡單，容易實現，這是PSO算法的最大優點。

3)協同搜索，同時利用個體局部信息和群體全局信息指導搜索。

收斂速度快， 算法對計算機內存和CPU要求不高。

5)更容易飛越局部最優信息。對于目標函數僅能提供極少搜索最優值的信息，在其他算法無法辨別搜索方向的情況下，PSO算法的粒子具有飛越性的特點使其能夠跨過搜索平面上信息嚴重不足的障礙，飛抵全局最優目標值。比如Generalized Rosenbrock函數全局最小值在原占附近.但是此函數全局最優值與可到達的局部最優值之間右一條獨長的山公，曲面山谷中點的最速下降方向幾乎與到函數最小值的最佳方向垂直，找到全局最小值的可能性微乎其微， 但是PSO算法完全有可能找到全局最優值。

同時， PSO算法的缺點也是顯而易見的：

1)算法局部搜索能力較差，搜索精度不夠高。

2)算法不能絕對保證搜索到全局最優解，主要有兩方面的原因：

①有時粒子群在俯沖過程中會錯失全局最優解。粒子飛翔過程中的俯沖動作使搜索行為不夠精細，不容易發現全局最優目標值，所以對粒子的最大飛翔速度進行限制既是為了使粒子不要沖出搜索區域的邊界，同時也是為了使搜索行為不至于太粗糙。

②應用PSO算法處理高維復雜問題時，算法可能會早熟收斂，也就是粒子群在沒有找到全局最優信息之前就陷入停頓狀態，飛翔的動力不夠，粒子群喪失了多樣性，各粒子之間的抱合力增強，緊緊地聚集在一起，并且它們的飛翔速度幾乎為零，雖然此時粒子距離全局最優解并不遠，但是幾乎為零的飛翔速度使其跳出停滯不前的狀態，各個粒子力不從心。這些停滯不前的早熟點未必都是局部最優點，也可能是位于局部最優點鄰域內的其他點，這一點與梯度搜索法不同，梯度搜索法如果出現早熟，通常只會陷人局部最優點，而不可能陷人局部最優點鄰域內的其他點，這一點與梯度搜索算法不同，梯度搜索算法如果出現早熟，通常只會陷入局部最優點，而·不可能陷入局部最優點領域內的其它點。

3)算法搜索性能對參數具有一定的依賴性。對于特定的優化問題，如果用戶經驗不足，參數調整的確是個棘手的問題。參數值的大小直接影響到算法是否收斂以及求解結果的精度。

4)PSO算法是一種概率算法，算法理論不完善，缺乏獨特性，理論成果偏少。從數學角度嚴格證明算法結果的正確性和可靠性還比較困難；缺少算法結構設計和參數選取的實用性指導原則，特別是全局收斂研究和大型多約束非線性規劃的研究成果非常少。

PSO算法程序設計

PSO算法實現的流程圖如下圖所示：

PSO算法設計的具體步驟如下：

步驟1：初始化粒子群（速度和位置）、慣性因子、加速常數、最大迭代次數、算法終止的最小允許誤差。

步驟2：評價每個粒子的初始適應值。

步驟3：將初始適應值作為當前每個粒子的局部最優值，并將各適應值對應的位置作為每個粒子的局部最優值所在的位置。

步驟4：將最佳初始適應值作為當前全局最優值，并將最佳適應值對應的位置作為全局最優值所在的位置。

步驟5：依據式(8-1)更新每個粒子當前的飛翔速度。

步驟6對每個粒子的飛翔速度進行限幅處理，使之不能超過設定的最大飛翔速度。

步驟7依據式(8-2)更新每個粒子當前所在的位置。

步驟8比較當前每個粒子的適應值是否比歷史局部最優值好，如果好，則將當前粒子適應值作為粒子的局部最優值，其對應的位置作為每個粒子的局部最優值所在的位置。

步驟9在當前群中找出全局最優值，并將當前全局最優值對應的位置作為粒子群的全局最優值所在的位置。

步驟10：重復步驟（5）~（9），直到滿足設定的最小誤差或最大迭代次數

步驟11：輸出粒子群的全局最優值和其對應的位置以及每個粒子的局部最優值和其對應的位置。

python簡單實現

import numpy as np import matplotlib.pyplot as plt class PSO(object): def __init__(self, population_size, max_steps): self.w = 0.6 # 慣性權重 self.c1 = self.c2 = 2 self.population_size = population_size # 粒子群數量 self.dim = 2 # 搜索空間的維度 self.max_steps = max_steps # 迭代次數 self.x_bound = [-10, 10] # 解空間范圍 self.x = np.random.uniform(self.x_bound[0], self.x_bound[1], (self.population_size, self.dim)) # 初始化粒子群位置 self.v = np.random.rand(self.population_size, self.dim) # 初始化粒子群速度 fitness = self.calculate_fitness(self.x) self.p = self.x # 個體的最佳位置 self.pg = self.x[np.argmin(fitness)] # 全局最佳位置 self.individual_best_fitness = fitness # 個體的最優適應度 self.global_best_fitness = np.min(fitness) # 全局最佳適應度 def calculate_fitness(self, x): return np.sum(np.square(x), axis=1) def evolve(self): fig = plt.figure() for step in range(self.max_steps): r1 = np.random.rand(self.population_size, self.dim) r2 = np.random.rand(self.population_size, self.dim) # 更新速度和權重 self.v = self.w*self.v+self.c1*r1*(self.p-self.x)+self.c2*r2*(self.pg-self.x) self.x = self.v + self.x plt.clf() plt.scatter(self.x[:, 0], self.x[:, 1], s=30, color='k') plt.xlim(self.x_bound[0], self.x_bound[1]) plt.ylim(self.x_bound[0], self.x_bound[1]) plt.pause(0.01) fitness = self.calculate_fitness(self.x) # 需要更新的個體 update_id = np.greater(self.individual_best_fitness, fitness) self.p[update_id] = self.x[update_id] self.individual_best_fitness[update_id] = fitness[update_id] # 新一代出現了更小的fitness，所以更新全局最優fitness和位置 if np.min(fitness) < self.global_best_fitness: self.pg = self.x[np.argmin(fitness)] self.global_best_fitness = np.min(fitness) print('best fitness: %.5f, mean fitness: %.5f' % (self.global_best_fitness, np.mean(fitness))) pso = PSO(100, 100) pso.evolve() plt.show()

輸出

參考文獻

《matlab在數學建模中的應用》

機器學習 深度學習

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。