邱飛岳,王京京

(浙江工業(yè)大學(xué) 教育科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

粒子群優(yōu)化算法是一種模擬鳥群覓食行為的群體智能優(yōu)化算法[1]，由于粒子群優(yōu)化算法與其他算法相比具有參數(shù)少、實現(xiàn)簡單等優(yōu)點，因此被廣泛地應(yīng)用到了實際的眾多優(yōu)化問題中[2-5]。不論是用于解決連續(xù)性質(zhì)問題的粒子群算法，還是解決離散問題的二進(jìn)制粒子群算法[6]，二者都涉及到種群的全局與局部兩種搜索能力，這兩種能力決定了算法的收斂性能。而粒子群算法中的學(xué)習(xí)因子對算法的全局與局部搜索能力有著重要影響，傳統(tǒng)的粒子群算法采用固定學(xué)習(xí)因子方式，不能隨著種群的進(jìn)化狀態(tài)實現(xiàn)動態(tài)調(diào)整。為了緩解粒子群優(yōu)化算法出現(xiàn)的早熟收斂現(xiàn)象，提升算法的收斂性能，相關(guān)學(xué)者提出了不同改進(jìn)策略的粒子群優(yōu)化算法。受慣性權(quán)重隨時間變化策略的啟發(fā)，Wang等[7-8]通過學(xué)習(xí)因子初始值與迭代次數(shù)共同實現(xiàn)學(xué)習(xí)因子的動態(tài)調(diào)整，使學(xué)習(xí)因子隨時間的變化而變化；董輝等[9]提出學(xué)習(xí)因子與尋優(yōu)代數(shù)成反比變化的更新策略；但是只根據(jù)尋優(yōu)代數(shù)簡單的關(guān)系進(jìn)行學(xué)習(xí)因子調(diào)整，并不能利用種群進(jìn)化狀態(tài)精確調(diào)整學(xué)習(xí)因子。趙遠(yuǎn)東等[10-11]提出學(xué)習(xí)因子隨慣性權(quán)重變化而變化的策略，在慣性權(quán)重隨時間改變時，學(xué)習(xí)因子發(fā)出相應(yīng)的遞減或遞增策略，通過慣性權(quán)重與學(xué)習(xí)因子的相互作用實現(xiàn)算法全局與局部搜索能力的平衡。雖然學(xué)習(xí)因子隨著慣性權(quán)重的變化能夠?qū)崿F(xiàn)參數(shù)調(diào)整的靈活性與針對性，但慣性權(quán)重主要是對粒子速度產(chǎn)生影響，卻不能反映當(dāng)前種群的整體尋優(yōu)狀態(tài)。Jadon等[12]提出自適應(yīng)學(xué)習(xí)因子的粒子優(yōu)化算法，通過當(dāng)前適應(yīng)度值與最大適應(yīng)度值的比值實現(xiàn)學(xué)習(xí)因子的自適應(yīng)更新，增強算法跳出局部最優(yōu)的能力；邵鵬等[13]提出一種學(xué)習(xí)因子與慣性權(quán)重自適應(yīng)調(diào)節(jié)算法，該算法將參數(shù)x映射到0～1表示算法進(jìn)度，夠確定的最大適應(yīng)度評估次數(shù)時利用迭代次數(shù)與全部評估次數(shù)計算算法進(jìn)度，不能確定時利用精度與全局歷史最優(yōu)計算算法進(jìn)度；利用算法進(jìn)度優(yōu)化學(xué)習(xí)因子提高了算法搜索能力。利用種群進(jìn)化信息實現(xiàn)對學(xué)習(xí)因子的自適應(yīng)調(diào)整的研究并不多，特別是在二進(jìn)制粒子群算法中的研究更少。

上述研究通過不同的策略實現(xiàn)了粒子群算法性能的提升，但粒子群算法的收斂性能依然有著較大的提升空間。筆者提出一種自適應(yīng)學(xué)習(xí)因子的混沌二進(jìn)制粒子群優(yōu)化算法(SABPSO)。SABPSO算法通過混沌策略提升初始粒子種群的質(zhì)量，并根據(jù)適應(yīng)度值、當(dāng)前粒子與最優(yōu)粒子間距離設(shè)計成長因子，用于檢測當(dāng)前粒子的成長狀態(tài)；最后根據(jù)粒子成長狀態(tài)信息和迭代次數(shù)實現(xiàn)學(xué)習(xí)因子的自適應(yīng)更新，提升算法收斂精度。通過在4 個經(jīng)典基準(zhǔn)函數(shù)上對SABPSO算法性能測試的實驗，結(jié)果表明：所提算法具有較好的收斂性能，混沌策略和自適應(yīng)學(xué)習(xí)因子策略能夠提升算法的收斂精度。

1 基本的二進(jìn)制粒子群優(yōu)化算法

為了克服傳統(tǒng)粒子群算法無法直接應(yīng)用離散問題的弊端，Kennedy和Eberhart于1997年提出了二進(jìn)制粒子群優(yōu)化算法BPSO。BPSO通過修改PSO中的速度和位置更新過程實現(xiàn)了粒子群算法在離散空間的應(yīng)用。在BPSO中，粒子的位置變化是通過區(qū)間[0,1]上的概率值來表示的。粒子速度更新公式、S型映射函數(shù)以及粒子位置更新公式分別為

vij(t+1)=wvij(t)+c1r1(pbestij(t)-xij(t))+c2r2(gbestij(t)-xij(t))

(1)

(2)

(3)

式中：t為第t次迭代；i，j取1到N中的整數(shù)，N為種群數(shù)量；w為慣性權(quán)重；c1，c2為學(xué)習(xí)因子，用來平衡局部最優(yōu)和全局最優(yōu)在搜索過程中的影響；r1，r2為0到1之間的隨機數(shù)；vij(t)為粒子i在第j維上第t次迭代的速度；xij(t)為粒子i在第j維上第t次迭代的位置；S(vij)為xij取1的概率。

2 自適應(yīng)學(xué)習(xí)因子的二進(jìn)制粒子群優(yōu)化算法

自適應(yīng)學(xué)習(xí)因子的二進(jìn)制粒子群優(yōu)化算法(SABPSO)將種群的進(jìn)化過程定義為種群的成長過程。SABPSO算法首先設(shè)計粒子成長因子，根據(jù)粒子成長因子判斷當(dāng)前種群的成長狀態(tài)；其次依據(jù)粒子當(dāng)前成長狀態(tài)自適應(yīng)調(diào)整學(xué)習(xí)因子，實現(xiàn)全局與局部探索的平衡，提升算法的搜索精度。

2.1 SABPSO算法的速度與位置更新方式

SABPSO算法的粒子速度更新采用基本BPSO算法的速度更新公式，映射函數(shù)采用V型映射函數(shù)，其計算式為

(4)

粒子位置更新采用VBPSO算法中的非強制性位置更新程序，其計算式為

(5)

2.2 混沌初始化策略

基本二進(jìn)制粒子群優(yōu)化算法采用隨機策略生成的初始種群質(zhì)量不高，分布狀態(tài)不佳，為了提升初始種群質(zhì)量，SABPSO算法采用混沌策略生成初始種群，其計算式為

Xn+1=μXn(1-Xn)

(6)

式中：μ=4；如果Xn<0.5，則取Xn=0；如果Xn≥0.5，則取Xn=1。

2.3 粒子成長因子

文獻(xiàn)[14-16]中表明進(jìn)化信息對算法尋優(yōu)性能有著重要影響，合理利用算法的進(jìn)化信息能夠提高算法的收斂性能。因此在設(shè)計成長因子更新方式之前，首先提出利用粒子成長因子反映種群的進(jìn)化狀態(tài)；在粒子在進(jìn)化過程中，將粒子的尋優(yōu)過程定義為粒子的成長過程，通過成長因子探測粒子的成長狀態(tài)。

成長因子由適應(yīng)度值、當(dāng)前粒子與全局最優(yōu)粒子之間的距離共同決定，粒子的成長因子為

gf=fit+dd=|dc-dg|

(7)

式中：d為當(dāng)前粒子與全局最優(yōu)粒子之間的距離；dc為當(dāng)前粒子；dg為全局最優(yōu)粒子。在實際編程時，將成長因子轉(zhuǎn)換為0到1之間的值，歸一化處理方式為

(8)

2.4 自適應(yīng)學(xué)習(xí)因子

學(xué)習(xí)因子對粒子群算法的全局搜索與局部開采能力有著重要的影響；自我學(xué)習(xí)因子的大小決定著粒子向自身歷史最優(yōu)學(xué)習(xí)的程度，社會學(xué)習(xí)因子決定著粒子向全局最優(yōu)學(xué)習(xí)的程度。自我學(xué)習(xí)因子c1值較大，則粒子更多的向pbest學(xué)習(xí)，算法的全局搜索能力增加；較小，則全局搜索能力減弱。社會學(xué)習(xí)因子c2值較大，則粒子更多的向gbest學(xué)習(xí)，算法的局部開采能力增加；較小，則局部開采能力減弱。合理的c1，c2值能夠有效均衡算法的局部與全局搜索能力，實現(xiàn)算法收斂性能的提升。

鑒于學(xué)習(xí)因子參數(shù)對算法性能有著重要影響，設(shè)計學(xué)習(xí)因子自適應(yīng)更新方式，利用粒子的成長狀態(tài)和迭代次數(shù)共同實現(xiàn)學(xué)習(xí)因子的自適應(yīng)調(diào)整，使粒子在不同的成長狀態(tài)下具有不同的學(xué)習(xí)因子更新方式，提高學(xué)習(xí)因子優(yōu)化的針對性。自我學(xué)習(xí)因子c1更新方式為

(9)

社會學(xué)習(xí)因子c2更新方式為

(10)

當(dāng)成長因子gf值小時，說明粒子與最優(yōu)解距離較遠(yuǎn)；此時應(yīng)增加自我學(xué)習(xí)系數(shù)c1值，減小社會學(xué)習(xí)系數(shù)c2值，加強算法的全局探索能力。當(dāng)成長因子gf值大時，說明粒子與最優(yōu)解距離較近；此時應(yīng)增加社會學(xué)習(xí)系數(shù)c2值，減小自我學(xué)習(xí)系數(shù)c1值，加強算法的局部開采能力。因此設(shè)計式(9)為遞增函數(shù)，自我學(xué)習(xí)系數(shù)c1隨著成長因子gf的遞增而遞增，隨著gf的遞減而遞減；設(shè)計式(10)為遞減函數(shù)，社會學(xué)習(xí)系數(shù)c2隨著gf的遞增而遞減，隨著gf的遞減而遞增。

2.5 SABPSO步驟

SABPSO算法采用混沌策略初始化粒子種群，能夠有效提高初始種群數(shù)量；利用成長因子檢測粒子的成長狀態(tài)，并根據(jù)成長狀態(tài)實現(xiàn)學(xué)習(xí)因子的自適應(yīng)更新，能夠?qū)崿F(xiàn)學(xué)習(xí)因子更新的針對性。采用自適應(yīng)學(xué)習(xí)因子更新策略的SABPSO算法步驟如下：

步驟1采用混沌策略初始化SABPSO算法種群。

步驟2利用公式(1)更新粒子速度。

步驟3利用公式(6)更新粒子位置。

步驟4利用成長因子檢測粒子成長狀態(tài)，用公式(7)計算成長因子。

步驟5利用步驟4中的成長因子實現(xiàn)學(xué)習(xí)因子的自適應(yīng)更新，用公式(9，10)計算學(xué)習(xí)因子。

步驟6計算粒子適應(yīng)度值。

步驟7若達(dá)到輸出條件，則輸出結(jié)果；否則，返回步驟2。

步驟8算法結(jié)束。

SABPSO算法的偽代碼為

1) INPUT：種群規(guī)模N，最大迭代次數(shù)T，當(dāng)前迭代次數(shù)t，慣性權(quán)重w，初始自我學(xué)習(xí)因子c1，初始社會學(xué)習(xí)因子c2=2，最大速度值Vmax。

2) OUTPUT：適應(yīng)度值fitness

3) BEGIN

4) 初始化種群。

5) FORt=1 TOT

6) 計算粒子速度和位置，并更新。

7) 計算粒子適應(yīng)度值fitness，若當(dāng)前值優(yōu)于上一代，則更新fitness。

8) IF當(dāng)前適應(yīng)度值優(yōu)于個體最優(yōu)

9) 更新個體歷史最優(yōu)pbest。

10) END

11) IF當(dāng)前適應(yīng)度值優(yōu)于全局最優(yōu)

12) 更新全局最優(yōu)gbest。

13) END

14) 計算當(dāng)前粒子與全局最優(yōu)的距離。

15) 根據(jù)式(7)計算粒子成長因子。

16) 根據(jù)式(8)進(jìn)行成長因子的歸一化處理。

17) 更新自我學(xué)習(xí)因子。

18) 更新社會學(xué)習(xí)因子。

19) END

20) END

3 實驗仿真

利用4 個經(jīng)典的測試函數(shù)驗證所提SABPSO算法的收斂性能，并分別與3 個采用不同學(xué)習(xí)因子更新策略的二進(jìn)制粒子群優(yōu)化算法進(jìn)行對比。由于SABPSO算法在初始化時采用了混沌策略，為了保證實驗數(shù)據(jù)能夠反映不同學(xué)習(xí)因子策略的對比情況，在其他3 個對比算法中也加入混沌策略。

3.1 實驗設(shè)置

測試函數(shù)采用2 個經(jīng)典的單峰函數(shù)Sphere，Step和2 個經(jīng)典的多峰函數(shù)Rastrigin，Griewangk對所提SABPSO算法的性能進(jìn)行測試，測試函數(shù)如表1所示。

表1 基準(zhǔn)測試函數(shù)Table 1 The Benchmark function

對比算法選擇3 個與筆者改進(jìn)角度相同的算法：采用固定學(xué)習(xí)因子的二進(jìn)制粒子群優(yōu)化算法VBPSO[14]；帶有權(quán)重函數(shù)學(xué)習(xí)因子的二進(jìn)制粒子群優(yōu)化算法WFBPSO[10]；動態(tài)改變學(xué)習(xí)因子的二進(jìn)制粒子群優(yōu)化算法DFBPSO[17]；其中，WFBPSO算法和DFBPSO算法只采用原始文獻(xiàn)中對學(xué)習(xí)因子改進(jìn)的策略，其他部分與基本的BPSO算法相同。因此各算法采用策略如表2所示。

表2 各算法策略Table 2 The Algorithmic strategies

實驗參數(shù)設(shè)置：種群數(shù)量N分別設(shè)置20，40，50，維度分別設(shè)置100，300，500 維，對應(yīng)的最大迭代次數(shù)T分布設(shè)置為300，500，1 000。在不同種群規(guī)模、不同維度和不同迭代次數(shù)下觀察SABPSO算法的收斂性能，驗證SABPSO算法的魯棒性。慣性權(quán)重w=2，慣性權(quán)重最大值wmax=0.9，慣性權(quán)重最小值wmin=0.4，自我學(xué)習(xí)因子c1=2，社會學(xué)習(xí)因子c2=2，最大速度值vmax=6。

實驗采用Matlab語言編程，Window 7操作系統(tǒng)，Intel(R) Core(TM) i5-3230M CPU @ 2.60 GHz；4 G內(nèi)存。

3.2 對比標(biāo)準(zhǔn)

實驗采用3 種標(biāo)準(zhǔn)判斷算法的收斂性能，即

1) 均值：各對比算法在實驗平臺上單獨運行30 次獲得的數(shù)據(jù)平均值。

2) 方差：各對比算法在實驗平臺上單獨運行30 次獲得的數(shù)據(jù)方差。

3) 分布狀態(tài)：利用箱須圖檢驗數(shù)據(jù)的分布狀態(tài)。

3.3 實驗結(jié)果分析

表3～6為3 個對比算法和筆者所提SABPSO算法在不同種群規(guī)模、不同維度和不同迭代次數(shù)下，單獨運行30 次獲得的實驗數(shù)據(jù)。表3～6中：N為算法的種群規(guī)模；D為維度；T為最大迭代次數(shù)。

表3 算法在測試函數(shù)F1上的實驗結(jié)果Table 3 The experimental results of the algorithm on the on the test function F1

表4 算法在測試函數(shù)F2上的實驗結(jié)果Table 4 The experimental results of the algorithm on the on the test function F2

表5 算法在測試函數(shù)F3上的實驗結(jié)果Table 5 The experimental results of the algorithm on the on the test function F3

表6 算法在測試函數(shù)F4上的實驗結(jié)果Table 6 The experimental results of the algorithm on the test function F4

在單峰函數(shù)F1，F(xiàn)2上，從表3，4中可以看出：SABPSO算法在3 個不同的種群規(guī)模、不同的維度和不同的迭代次數(shù)上具有最小的均值，說明SABPSO算法具有最佳的收斂精度；DFBPSO算法的均值小于WFBPSO算法，但差于VBPSO算法，VBPSO算法的收斂精度僅次于筆者所提的SABPSO算法，WFBPSO算法收斂精度最差。SABPSO算法在維度為100，500時具有最小的方差，說明SABPSO算法在穩(wěn)定性上具有較好表現(xiàn)。在多峰函數(shù)F3，F(xiàn)4上，從表5，6中可以看出：對于多峰函數(shù)F3，SABPSO算法在3 個維度上都有最小的均值和方差，說明收斂精度和穩(wěn)定性優(yōu)于對比算法；對于函數(shù)F4，SABPSO算法在維度100，300時獲得了最小的方差，但收斂精度表現(xiàn)略差；VBPSO算法在多峰函數(shù)F4上具有最小的均值，表現(xiàn)最佳。

從表3～6中的均值和方差數(shù)據(jù)可以看出：SABPSO算法在大部分測試函數(shù)上的收斂性能優(yōu)于對比算法，這是因為SABPSO算法利用粒子的成長信息對學(xué)習(xí)因子進(jìn)行調(diào)整，當(dāng)粒子與全局最優(yōu)粒子較遠(yuǎn)時，采用較大的c1值，較小的c2值，增強算法的全局探索能力，當(dāng)粒子與全局最優(yōu)粒子較近時，采用較小的c1值，較大的c2值，增強算法的局部開采能力。利用粒子成長信息實現(xiàn)學(xué)習(xí)因子自適應(yīng)更新的策略有效提升了算法的搜索精度。

圖1～4展示了SABPSO算法在種群為40、維度為300、迭代次數(shù)為500的條件下，在4 個測試函數(shù)上的尋優(yōu)過程曲線，從圖1～4中可以看出：由于4 個算法都采用了混沌初始化策略，因此在尋優(yōu)初期4 個算法的收斂性能接近；算法的尋優(yōu)后期，SABPSO算法在大部分函數(shù)能夠很好地跳出局部最優(yōu)，實現(xiàn)收斂精度的提升。在相同的500 次迭代中，SABPSO算法在大部分函數(shù)上都能找到比其他算法更好的解，這是因為SABPSO算法根據(jù)粒子的成長狀態(tài)信息進(jìn)行學(xué)習(xí)因子的自適應(yīng)更新，在尋優(yōu)過程中，學(xué)習(xí)因子自適應(yīng)更新策略能夠更好地均衡算法局部與全局搜索的平衡，進(jìn)而實現(xiàn)算法收斂性能的提升。

圖1 函數(shù)F1Fig.1 Function F1

圖2 函數(shù)F2Fig.2 Function F2

圖3 函數(shù)F3Fig.3 Function F3

圖4 函數(shù)F4Fig.4 Function F4

圖5～8是各算法在維度為300時的解集分布情況，從圖5～8中可以看出：WFBPSO算法和DFBPSO算法在兩個測試函數(shù)上都出現(xiàn)了異常值，VBPSO算法和筆者所提SABPSO算法只有在一個測試函數(shù)上出現(xiàn)了異常值。在單峰函數(shù)F1，F(xiàn)2和多峰函數(shù)F3上，SABPSO算法得到的解集比對比算法更加接近x軸，說明SABPSO算法得到的解精度更高；在多峰函數(shù)F4上，VBPSO算法的解更加接近x軸，但是數(shù)據(jù)范圍比較大，穩(wěn)定性不如其他3 個算法。SABPSO算法在大部分測試函數(shù)上的數(shù)據(jù)范圍都相對較小，說明穩(wěn)定性較好。

圖5 測試函數(shù)F1Fig.5 Test function F1

圖6 測試函數(shù)F2Fig.6 Test function F2

圖7 測試函數(shù)F3Fig.7 Test function F3

圖8測試函數(shù)F4Fig.8 Test function F4

從上述分析可知：SABPSO算法具有較好的收斂性能和較好的穩(wěn)定性，這充分證明了利用粒子成長信息實現(xiàn)學(xué)習(xí)因子的自適應(yīng)更新策略能夠提升算法的收斂性能。

4 結(jié) 論

通過對學(xué)習(xí)因子的分析，提出一種自適應(yīng)學(xué)習(xí)因子的混沌二進(jìn)制粒子群優(yōu)化算法。該算法借助成長因子實現(xiàn)學(xué)習(xí)因子的自適應(yīng)更新，充分利用了種群的進(jìn)化信息。仿真實驗結(jié)果表明：SABPSO算法在單峰函數(shù)和多峰函數(shù)上都具有比對比算法更好的收斂精度，同時算法的解集箱須圖證明了算法具有更好的穩(wěn)定性。在下一步的研究工作中，將對SABPSO算法解決實際問題的能力進(jìn)行驗證并不斷優(yōu)化。