基于自適應選擇的多策略粒子群算法

蔡 銘，李 響

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

1 引言

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

2 粒子群優化算法

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

(1)

(2)

3 基于自適應選擇的多策略粒子群

3.1 策略池的建立

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

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

1)探索

(3)

2)開發

(4)

3)跳躍

(5)

4)收斂

(6)

3.2 自適應選擇機制

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

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

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

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

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

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

(7)

(8)

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

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

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

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

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

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

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

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 算法復雜度

與標準粒子群算法相比，基于自適應選擇的多策略粒子群算法的額外計算量主要在于自適應選擇機制中各個粒子4種策略選中概率的計算。而在選中概率的計算過程中，沒有額外的適應值計算。

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

4 試驗結果與分析

4.1 測試函數

為了測試基于自適應選擇的多策略粒子群算法的性能，本次試驗采用8個標準測試函數，可將其分為三組。

1)第一組為4個標準測試函數，其中包括：

2個單峰函數(f1，f2)

2個多峰函數(f3，f4)

2)第二組為病態條件下的標準測試函數，其是在標準測試函數的基礎上加入噪聲、平移和旋轉的操作，從而提高測試函數的復雜。

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

o為平移量，也是全局最優的解;fbias為函數值偏移量，此處fbias=-450。

旋轉操作的方法參考CLPSO中的方法，具體可以表示為

M為正交矩陣。

噪聲操作可表示為：

8個測試函數的搜索范圍，以及全局最優如表1所示。

表1 測試函數的搜索范圍與全局最優

4.2 相關算法的參數設置

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

表2 算法參數參數設置

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

為了保證在對各個算法試驗結果進行對比的公平，對試驗的基本參數進行統一設置，如種群大小(PS)和最大適應值計算次數nfemax。在本次實驗中，設置維度D=30，其對應的種群大小PS=20，最大適應值計算次數nfemax=100000。所有算法分別獨立對測試函數進行30計算。

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

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

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

表3 12個測試函數的平均值與方差

4.4 基于收斂速度的對比

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

(9)

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

本次試驗中，5種算法對8個函數求解的收斂圖如圖2所示。

圖2 測試函數收斂圖

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

5 結論

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