呂柏行 郭志光 趙韋皓 張 凡

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

1 標準粒子群算法

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

2 國內外研究應用現(xiàn)狀及評述

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

2.1 最大速度限制值的改進

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

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

2.2 慣性因子的改進

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

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

2.3 學習因子的改進

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

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

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

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

2.4 優(yōu)化變異策略

變異優(yōu)化分為主動變異和被動變異，即按一定規(guī)則主動觸發(fā)變異或預設條件滿足時被動觸發(fā)變異。

2.4.1 被動變異

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

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

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

2.4.2 主動變異

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

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

2.5 優(yōu)化編碼方式

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

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

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

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

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

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

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

3 結論

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

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

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

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

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