標(biāo)準(zhǔn)粒子群算法的優(yōu)化方式綜述

呂柏行 郭志光 趙韋皓 張 凡

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

1 標(biāo)準(zhǔn)粒子群算法

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

2 國內(nèi)外研究應(yīng)用現(xiàn)狀及評述

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

2.1 最大速度限制值的改進(jìn)

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

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

2.2 慣性因子的改進(jìn)

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

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

2.3 學(xué)習(xí)因子的改進(jìn)

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

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

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

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

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

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

2.4.1 被動變異

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

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

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

2.4.2 主動變異

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

或者采用自適應(yīng)策略，對gbest 做自適應(yīng)變異操作（變異值前期大而后期?。善洚a(chǎn)生的新個體對環(huán)境做進(jìn)一步試探，優(yōu)，則取代之[15]。變異種子xm 在各維上的值：

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

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

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

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

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

基于實數(shù)編碼的思想，宋強(qiáng)[16]提出了一種隨機(jī)鍵編碼。文章以VRP 問題為例，利用一串0 到1 之間的隨機(jī)數(shù)來表示一種車輛路徑，先確定編碼長度維度，再進(jìn)行隨機(jī)鍵轉(zhuǎn)化操作，最后進(jìn)行整數(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ā)生變化。這種編碼方式用于粒子群算法，不僅可以減少更新全部種群的運(yùn)算時間，也可以減少計算機(jī)內(nèi)存占用[19]。

3 結(jié)論

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

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

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

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

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