標準粒子群算法的優化方式綜述

呂柏行 郭志光 趙韋皓 張 凡

（中國建筑土木建設有限公司，北京 100071）

1 標準粒子群算法

Kennedy 和Eberhart 在1995 年提出經典PSO 算法，后被Shi 等修改，形成了目前的標準PSO 算法。式（1）為標準PSO 算法的速度迭代公式，其核心思想是在有限空間中創建N 個粒子，每個粒子單獨搜尋最優解并將最優解由整個粒子群共享，從而達到優化的目的。

2 國內外研究應用現狀及評述

由于標準粒子群算法容易陷入局部最優、收斂精度低，學者們常對粒子群算法進行優化，以完成各種實際問題的求解。本文將常用的優化方法分為五大類，包括對最大速度、慣性因子、學習因子進行改進、優化變異策略及優化編碼方式。

2.1 最大速度限制值的改進

算法中常常需要用粒子的最大速度限制值vmax來限制其運動軌跡，防止粒子群快速飛過最優區域。一般算法采用單一極值限制方式，超出則取最大或最小值。

但這種方式的局限性也很明顯，即每代粒子的搜索范圍在整個迭代過程中不變。因此有學者采用動態限制方式：隨著迭代次數的增加，降低粒子的最大速度，以保證后期精細的局部搜索[1]。其中：T 為最大迭代次數，δ 是0-1 的隨機數。

2.2 慣性因子的改進

針對多目標粒子群空間優化效率較低的問題，楊震倫[5]引入了一種慣性權重周期變化的調節方法，能夠在(T/m)個周期內完成反復搜索。其中m 是單個周期的迭代次數，mod(t,m)表示t 對m 取余數。

以上對于ω 的調整均為全局性的。董文永[6]提出了一種慣性權重自適應調節法，使每個粒子能夠獨立思考，并根據群體適應值進行動態調整：在粒子群趨同時提高ω，擴大算法的全局搜索空間，而在粒子群分散時減小ω，保證粒子的局部搜索能力。其中：f1表示粒子i 的適應值，fmin、favg分別表示粒子總體的最小適應值和平均適應值。

2.3 學習因子的改進

慣性因子決定了粒子對于上一代速度的繼承量大小，而學習因子則確定了粒子對于最優位置的學習量大小，包括對個體最優和全局最優的學習。標準PSO 算法設置的固定學習比例，即c1、c2為常數，在多維且局部極值較多的函數中常表現乏力。2004 年，Ratnaweera[7]首次提出了一種隨迭代次數增加而變化的學習因子優化方法，并與Shi 提出的慣性權重線性遞減調節法混合共用，經Benchmark 函數集測試：c1的最佳取值區間為2.5至0.5、c2的最佳取值區間為0.5 至2.5，其表現優于同條件的固定學習因子（c1=c2=2）優化方法，其中 c1i,c1f,c2i,c2f均為常數。

但上述方法在收斂速度方面表現不佳。Chen[8]采用三角函數學習因子平衡前期全局搜索與后期全局趨同的權重，使公式轉為非線性，并在多數函數中表現出了更快的收斂速度和更高的收斂精度。其中，c1、c2的取值區間仍為2.5 至0.5 與0.5 至2.5，?=2,δ =0.5。

除了對學習因子取值的改進外，增加速度系數c3可以使學習因子受到額外的隨機因素影響，從而提高算法的搜索能力。李艷麗[9]將該項速度分量設定地相對隨機，從而提高粒子的全局搜索能力。其中c3為常數，Ri為隨機數。

Benedetti[10]提出一種增強粒子速度記憶的改進方法，期望對環境變化做出快速響應：其第四項速度分量是基于動態變化的歷史精英解集，即每次迭代時將前M 個個體最優解儲存為歷史精英解集，并將當前適應度最差的粒子替換為外部最優解，這在一定程度上可以克服某些干擾因素。其中H 為常數（這里取10），M 為記憶儲存長度，m=1, 2,…,M，r1～ r3為隨機數。

2.4 優化變異策略

變異優化分為主動變異和被動變異，即按一定規則主動觸發變異或預設條件滿足時被動觸發變異。

2.4.1 被動變異

在精英解集連續幾代無改進時，以一定的規則隨機生成N個粒子取代精英解集中最差的N 個粒子，起到幫助群體跳出局部最優的作用[11]。

張建科[12]利用外推技巧對標準PSO 算法的位置公式進行優化，即在粒子尚未到達最優位置時，必定存在一個系數k，使得粒子當前的適應值更小。

他提出的2 個新的位置公式，在高維搜索時，收斂性優于標準PSO 算法。

2.4.2 主動變異

也可以采用概率變異方法，在每個粒子的每次迭代過程中，以加權變異概率替代群體最優[14]。

或者采用自適應策略，對gbest 做自適應變異操作（變異值前期大而后期小），由其產生的新個體對環境做進一步試探，優，則取代之[15]。變異種子xm 在各維上的值：

2.5 優化編碼方式

在解決實際問題的過程中，合理選擇編碼方式可以顯著優化函數性能。

2.5.1 二進制編碼：簡單易行，符合最小字符集編碼原則。以車輛運輸路徑問題（VRP）為例，車輛1 前往工點2，車輛2 前往工點3，車輛3 前往工點1 用二進制矩陣來表示為：

2.5.2 十進制編碼：隨著規模的擴大，二進制占用計算空間急劇增長。而十進制增長速度遠小于二進制，可用整數部分表示車輛前往的目的地，上述問題用(2, 3, 1)即可清晰表達。

2.5.3 實數編碼：隨著問題復雜性提升，采用實數編碼可以擴充粒子群攜帶的信息。仍以上述問題為例，以小數部分表示所載的商品數量，則將(2, 3,1)擴展為(2.4, 3.5, 1.2)后，可以表示車輛1 商品數量400，前往目的地2；車輛2 商品數量500，前往目的地3；車輛3 商品數量200，前往目的地1。

基于實數編碼的思想，宋強[16]提出了一種隨機鍵編碼。文章以VRP 問題為例，利用一串0 到1 之間的隨機數來表示一種車輛路徑，先確定編碼長度維度，再進行隨機鍵轉化操作，最后進行整數解碼操作，用前N 個數字表示工點編號，中間(N+1)～(2N-1)表示單個配送車輛行程分割符，用M 表示配送車輛總數，(2N-1)～[2N+(M-2)]為配送車輛總行程分割符。

2.5.4 概率幅編碼：按照最小編碼單元的不同，以一個量子位為最小編碼單元的被稱為單比特概率幅編碼[17]，以一串量子位的集合為最小編碼單元的被稱為多比特概率幅編碼[18]。

一個量子位可處于“1”狀態、“0”狀態或兩者的線性疊加狀態，而n 個量子位組成的集合可包含2n個不同的狀態，即包含2n個不同的信息。任一量子位的狀態發生變化，整個量子系統的概率幅均發生變化。這種編碼方式用于粒子群算法，不僅可以減少更新全部種群的運算時間，也可以減少計算機內存占用[19]。

3 結論

本文通過對粒子群算法優化方法的梳理和歸納，得到如下結論：

3.1 對粒子群運動速度的改進由線性向非線性發展，由連續向間斷變化。無論變量因子是線性、非線性或三角函數變化、引入隨機因子或是優質解替代，其目的都是調節收斂速度，從而使函數能夠在全局尋優和局部尋優之間靈活切換。具體調節方法分為全局調控和個體調控：全局調控如線性遞減、非線性遞減、余弦函數遞減及周期性調節，個體調控如自適應策略。

3.2 對粒子群的變異策略分為被動變異和主動變異。被動變異如函數連續幾代無改進時觸發變異，利用外推技巧穩定提高適應值，主動變異如加權變異、概率變異、自適應策略變異。

3.3 粒子群的編碼方式由簡至繁發展。從二進制、十進制編碼到實數編碼及量子位編碼，復雜的編碼方式更適應復雜的多解問題。

3.4 總體來說，對于標準粒子群算法的改進方法無好壞之分，需視目標函數而靈活選擇。