基于自適應(yīng)選擇的多策略粒子群算法

蔡 銘，李 響

(北京理工大學(xué)宇航學(xué)院，北京，100081)

1 引言

粒子群優(yōu)化算法是一種基于種群智能的優(yōu)化算法，其結(jié)構(gòu)簡單且收斂速度快。近幾年，粒子群算法仍然被廣泛應(yīng)用于各個領(lǐng)域，如軌跡優(yōu)化[1]，數(shù)據(jù)辨識[2]和特征選擇[3]等。但是相比與其它進(jìn)化算法，粒子群算法在解決復(fù)雜的多峰問題容易陷入局部最優(yōu)[4]。針對該缺點(diǎn)，不少學(xué)者提出了很多改進(jìn)的粒子群算法。最為典型的便是CLPSO算法[5]，該算法通過提高粒子的多樣性來提高算法對于多峰問題的解決能力，但是與此同時其收斂速度也隨之降低。為了提高算法對不同類型問題的適用性，本文提出了，基于自適應(yīng)選擇的多策略粒子群算法。試驗(yàn)表明：與其它4種改進(jìn)的粒子群算法相比，本文所提的算法具備更高的全局收斂精度與更快的收斂速度。

2 粒子群優(yōu)化算法

粒子群算法是由Kennedy和Eberhart于1995年提出[6，7]。與遺傳算法和差分進(jìn)化算法類似，粒子群算法是一種基于種群的智能進(jìn)化算法。粒子群算法模擬自然界中鳥類覓食與遷徙行為對問題的解空間進(jìn)行搜索。每個粒子具有位置矢量與速度矢量，其位置矢量對應(yīng)解空間中的一個解。粒子的位置矢量通過速度矢量進(jìn)行更新，而速度矢量則根據(jù)粒子自身的歷史最優(yōu)位置pbest與種群的歷史最優(yōu)位置gbest進(jìn)行更新。通過多次迭代得到的種群歷史最優(yōu)位置即為粒子群算法對該問題求解所得的最優(yōu)解。對于粒子i而言，其速度矢量vi和位置矢量xi的更新可表示為

(1)

(2)

3 基于自適應(yīng)選擇的多策略粒子群

3.1 策略池的建立

傳統(tǒng)的粒子群算法以及大多的粒子群改進(jìn)算法的速度更新策略僅有一種，即式(1)或?qū)κ?1)進(jìn)行改進(jìn)。單策略的速度更新往往無法兼顧算法解決不同類型問題的能力，如CLPSO[5]增強(qiáng)了算法對復(fù)雜多峰問題的解決能力，但其對單峰問題的收斂速度有所降低；PSO-cf[8]提高了算法對單峰問題的收斂性能，但在解決復(fù)雜多峰問題時算法容易陷入局部最優(yōu)。單策略型粒子群算法能否解決問題取決于其策略是否適合，但問題的類型可能不明確，逐個嘗試的方法來尋找合適的策略其工作量過大。多策略型粒子群算法其包含多種速度更新策略，因此對不同類型問題的優(yōu)化求解有更好的適用性。

受SLPSO啟發(fā)，本文建立了包含以下4種不同策略的策略池[9]：

1)探索

(3)

2)開發(fā)

(4)

3)跳躍

(5)

4)收斂

(6)

3.2 自適應(yīng)選擇機(jī)制

對于多策略型粒子群算法，在建立了包含多種速度更新策略后，還需要為算法制定自適應(yīng)選擇機(jī)制，讓粒子在更新迭代的過程中能夠根據(jù)自己的自身情況選擇適合的策略。在介紹自適應(yīng)選擇機(jī)制前，不妨對四種策略的性質(zhì)與功能進(jìn)行表述：

1)探索策略：僅包含“自我認(rèn)知”部分，采用該策略的粒子僅向其自身的歷史最優(yōu)位置學(xué)習(xí)，對于處在“坡”處的粒子，該策略效果最佳[9]

2)開發(fā)策略：賦予粒子向其它粒子的歷史最優(yōu)位置學(xué)習(xí)的能力，相比于探索策略該策略對多峰問題的處理更有效

3)跳躍策略：通過種群的平均速度與正態(tài)分布的隨機(jī)數(shù)，使得粒子能夠在陷入局部最優(yōu)時具備一定的逃逸能力

4)收斂策略：僅包含“社會認(rèn)知”部分，該策略能讓粒子向種群的歷史最優(yōu)位置靠攏。當(dāng)搜索環(huán)境較為簡單時，其效果最佳。但當(dāng)種群的歷史最優(yōu)位置為局部最優(yōu)，過多粒子使用該策略可能使得算法出現(xiàn)早熟。

理論上，自適應(yīng)選擇機(jī)制可以讓種群中的粒子根據(jù)其自身情況選擇出最佳的策略來更新自己的速度與位置。SaDE[10]與SaLPSO[11]的自適應(yīng)選擇機(jī)制是基于種群的機(jī)制，其每個粒子是根據(jù)之前整個種群的反饋進(jìn)行選擇策略，這種做法可能使得一些粒子被迫選擇不適合自己的策略。為了避免出現(xiàn)這種狀況，本文的自適應(yīng)選擇機(jī)制其實(shí)施對象為種群中的每個個體，而非是整個種群。也就是說，每個粒子的速度更新策略的選擇是根據(jù)自身的反饋而并非整個種群的反饋。

(7)

(8)

不妨把長度為LP的反饋結(jié)果記錄在成功表格與失敗表格中。隨著粒子的迭代，其成功與失敗表格也隨之更新。表格更新主要是將最舊的信息(即代數(shù)最低的數(shù)據(jù))替換為最新的信息。如圖1所示為第i個粒子從g代進(jìn)化到g+1代，其成功表格的更新，在更新后g-LP代的信息被抹除，取而代之的是g代的信息。

圖1 第i個粒子g代到g+1代的成功表格更新

至此，自適應(yīng)選擇機(jī)制便完成建立。但仍有一些情況需要說明：

1)學(xué)習(xí)周期LP為預(yù)先給定的一個整數(shù)。當(dāng)代數(shù)g小于等于LP時，由于各個粒子成功與失敗的表格并沒完全建成，因此每個粒子4種策略被選中的概率均相等即0.25，當(dāng)代數(shù)g大于LP時，各個粒子的成功與失敗表格便開始更新，各粒子4種策略被選中的概率便可通過式(7)和式(8)進(jìn)行計算求解。

3)自適應(yīng)機(jī)制對粒子自身情況的變化響應(yīng)要足夠較快。對于復(fù)雜的多峰函數(shù)而言，各個粒子需要在迭代過程中，根據(jù)自身的情況盡早的舍棄原有的策略而選擇出合適的策略。例如，對于粒子i，可能在某個階段最佳策略均為探索策略，因此其策略被選中的概率趨近于1，而其它策略被選中的概率趨近于0，但隨著局部搜索情況的變化，最佳的策略變?yōu)樘S策略。而跳躍策略若以極低的被選概率被選中且成功了，則其被選中概率便會迅速上升，相應(yīng)的探索策略被選中的概率隨之降低。

3.3 基于自適應(yīng)選擇的多策略粒子群算法的整體框架

基于自適應(yīng)選擇的多策略粒子群算法的整體框架如下所示。

Algorithm 3 MPSO-AS Algorithm

1) initialize the position and velocity of particles in the swarm randomly;

2) set the nfe=0，generation number g=0;

3) while nfe

4) if g>LP then

5) update probability of 4 strategies for each particle according to (8)

6) end if

7) for each particle i do

8) select the strategy k by roulette wheel selection;

9) update the position and velocity of particle i;

10) if f(xi(g))

12) else

14) end if

15) if f(xi(g))

16) pbesti=xi(g);

17) if f(xi(g))

18) gbest=xi(g);

19) end if

20) end if

21) end for

22) g=g+1;

23) end while

3.4 算法復(fù)雜度

與標(biāo)準(zhǔn)粒子群算法相比，基于自適應(yīng)選擇的多策略粒子群算法的額外計算量主要在于自適應(yīng)選擇機(jī)制中各個粒子4種策略選中概率的計算。而在選中概率的計算過程中，沒有額外的適應(yīng)值計算。

總體來說，若算法共進(jìn)行Ite次迭代，則基于自適應(yīng)選擇的多策略粒子群算法的總計算復(fù)雜度為O(PS)。

4 試驗(yàn)結(jié)果與分析

4.1 測試函數(shù)

為了測試基于自適應(yīng)選擇的多策略粒子群算法的性能，本次試驗(yàn)采用8個標(biāo)準(zhǔn)測試函數(shù)，可將其分為三組。

1)第一組為4個標(biāo)準(zhǔn)測試函數(shù)，其中包括：

2個單峰函數(shù)(f1，f2)

2個多峰函數(shù)(f3，f4)

2)第二組為病態(tài)條件下的標(biāo)準(zhǔn)測試函數(shù)，其是在標(biāo)準(zhǔn)測試函數(shù)的基礎(chǔ)上加入噪聲、平移和旋轉(zhuǎn)的操作，從而提高測試函數(shù)的復(fù)雜。

其中，平移函數(shù)為Shifted Schwefeil 1.2函數(shù)，具體可以表示為：

o為平移量，也是全局最優(yōu)的解;fbias為函數(shù)值偏移量，此處fbias=-450。

旋轉(zhuǎn)操作的方法參考CLPSO中的方法，具體可以表示為

M為正交矩陣。

噪聲操作可表示為：

8個測試函數(shù)的搜索范圍，以及全局最優(yōu)如表1所示。

表1 測試函數(shù)的搜索范圍與全局最優(yōu)

4.2 相關(guān)算法的參數(shù)設(shè)置

本次試驗(yàn)，通過與其它4種改進(jìn)的粒子群算法進(jìn)行對比來測試基于自適應(yīng)選擇的多策略粒子群算法的性能，這些算法的參數(shù)設(shè)置如表2所示。

表2 算法參數(shù)參數(shù)設(shè)置

PSO-w是最典型的一種粒子群改進(jìn)算法，其慣性權(quán)重w是隨迭代次數(shù)線性減小。CLPSO通過提高種群中的粒子多樣性來提高算法對多峰問題的解決能力。ALPSO采用基于候選代的自適應(yīng)學(xué)習(xí)策略與基于預(yù)測的競爭學(xué)習(xí)策略來平衡算法的探索與開發(fā)能力。

為了保證在對各個算法試驗(yàn)結(jié)果進(jìn)行對比的公平，對試驗(yàn)的基本參數(shù)進(jìn)行統(tǒng)一設(shè)置，如種群大小(PS)和最大適應(yīng)值計算次數(shù)nfemax。在本次實(shí)驗(yàn)中，設(shè)置維度D=30，其對應(yīng)的種群大小PS=20，最大適應(yīng)值計算次數(shù)nfemax=100000。所有算法分別獨(dú)立對測試函數(shù)進(jìn)行30計算。

4.3 基于平均值與方差的對比

5種算法均獨(dú)立對測試函數(shù)進(jìn)行30次計算。對于每個測試函數(shù)，記錄其30次計算的最優(yōu)值f(xtest)與函數(shù)真正的全局最優(yōu)值f(x*)差(即誤差)的絕對值。5種算法對8個測試算法30次獨(dú)立計算的誤差平均值與方差如表4所示。表4數(shù)據(jù)括號內(nèi)的值為誤差的方差，括號外的值為誤差的平均值。此外，在5個算法中，最優(yōu)的值以加粗的形式來體現(xiàn)。

由表3可得，對于單峰測試函數(shù)(f1-f2)，MPSO-AS的求解結(jié)果明顯優(yōu)于其它算法。第3個測試函數(shù)(f3)為復(fù)雜的多峰函數(shù)，雖然MPSO-AS的誤差平均值要大于CLPSO，但是其方差較大，這個原因在于，MPSO-AS在30次求解第3個函數(shù)時，有21次找到了全局最優(yōu)解0，但其它9次求解并未找到。CLPSO雖然誤差均值要小，但在30次重復(fù)運(yùn)行中，沒有一次找到全局最優(yōu)。同時，MPSO-AS對于另外一個多峰測試函數(shù)(f4)的均值方差均為零，這表明MPSO-AS在30次獨(dú)立的求解后，每次都能在給定的計算量內(nèi)找到全局最優(yōu)。對于病態(tài)的測試函數(shù)(f5-f8)的測試結(jié)果可以看出，平移f5和噪聲的操作對所有算法的求解精度都有所影響，但MPSO-AS求解結(jié)果依然優(yōu)于其它算法。相比于其它算法，旋轉(zhuǎn)操作的加入對MPSO-AS算法的求解影響較小。由于第6個函數(shù)(f6)和第7個函數(shù)(f7)分別是在第3個函數(shù)(f3)和第4個函數(shù)(f4)的基礎(chǔ)上加入正交矩陣?？梢詮谋?看出，MPSO-AS算法對第7個函數(shù)(f7)的求解結(jié)果和其對第4個函數(shù)(f4)的求解結(jié)果一樣。相比于未加入旋轉(zhuǎn)操作的第3個測試函數(shù)(f3)結(jié)果而言，對于第6個函數(shù)(f6)，MPSO-AS的求解結(jié)果優(yōu)于CLPSO的求解結(jié)果。

表3 12個測試函數(shù)的平均值與方差

4.4 基于收斂速度的對比

在試驗(yàn)過程中，對于每個測試函數(shù)，每個算法在每次獨(dú)立運(yùn)算過程中隨著適應(yīng)值計算次數(shù)nfe的增加其最小的誤差值均被記錄。故可以根據(jù)誤差值求得平均最小誤差值error(nfe)，通過平均最小誤差值則可畫出每個算法對于每個測試函數(shù)的收斂圖。具體地，平均最小誤差值error(nfe)可表示為

(9)

式(12)中xbest(nfe)為一次獨(dú)立運(yùn)行過程中適應(yīng)值計算次數(shù)為nfe時算法求得的歷史最優(yōu)位置。f(x*)為該測試函數(shù)的全局最優(yōu)解。

本次試驗(yàn)中，5種算法對8個函數(shù)求解的收斂圖如圖2所示。

圖2 測試函數(shù)收斂圖

由圖2.(a)和圖2.(b)可以看出，對于2個單峰測試函數(shù)，MPSO-AS的收斂速度隨著迭代的進(jìn)行不斷加快，相比于其它4種算法，MPSO-AS的收斂速度有著顯著的優(yōu)勢。對于f4多峰測試函數(shù)，MPSO-AS均在一半的適應(yīng)值計算次數(shù)之后其收斂速度迅速變快，且在給定的適應(yīng)值計算次數(shù)內(nèi)收斂到全局最優(yōu)。對于f3多峰測試函數(shù)，MPSO-AS收斂速度在中后期趨于平緩的原因如上文所述，在30次的求解中有幾次并未找到全局最優(yōu)。對于病態(tài)的測試函數(shù) (f5，f6，f7，f8)，MPSO-AS的搜索速度受平移、旋轉(zhuǎn)和噪聲的干擾并不大，其它算法如PSO-w在迭代中期進(jìn)入阻滯狀態(tài)，MPSO-AS算法在中后期仍保持較高的收斂速度。

5 結(jié)論

本文通過建立策略池以及自適應(yīng)選擇機(jī)制，實(shí)現(xiàn)粒子在不同情況下能根據(jù)自身情況選擇最佳的速度更新策略。試驗(yàn)表明，對于8個標(biāo)準(zhǔn)測試函數(shù)，MPSO-AS的收斂性能(收斂精度與收斂速度)比其它四種粒子群改進(jìn)算法更好。