自適應學習因子的混沌二進制粒子群優(yōu)化算法

邱飛岳,王京京

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

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

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

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

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

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

(1)

(2)

(3)

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

2 自適應學習因子的二進制粒子群優(yōu)化算法

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

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

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

(4)

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

(5)

2.2 混沌初始化策略

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

Xn+1=μXn(1-Xn)

(6)

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

2.3 粒子成長因子

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

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

gf=fit+dd=|dc-dg|

(7)

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

(8)

2.4 自適應學習因子

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

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

(9)

社會學習因子c2更新方式為

(10)

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

2.5 SABPSO步驟

SABPSO算法采用混沌策略初始化粒子種群，能夠有效提高初始種群數量；利用成長因子檢測粒子的成長狀態(tài)，并根據成長狀態(tài)實現學習因子的自適應更新，能夠實現學習因子更新的針對性。采用自適應學習因子更新策略的SABPSO算法步驟如下：

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

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

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

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

步驟5利用步驟4中的成長因子實現學習因子的自適應更新，用公式(9，10)計算學習因子。

步驟6計算粒子適應度值。

步驟7若達到輸出條件，則輸出結果；否則，返回步驟2。

步驟8算法結束。

SABPSO算法的偽代碼為

1) INPUT：種群規(guī)模N，最大迭代次數T，當前迭代次數t，慣性權重w，初始自我學習因子c1，初始社會學習因子c2=2，最大速度值Vmax。

2) OUTPUT：適應度值fitness

3) BEGIN

4) 初始化種群。

5) FORt=1 TOT

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

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

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

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

10) END

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

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

13) END

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

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

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

17) 更新自我學習因子。

18) 更新社會學習因子。

19) END

20) END

3 實驗仿真

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

3.1 實驗設置

測試函數采用2 個經典的單峰函數Sphere，Step和2 個經典的多峰函數Rastrigin，Griewangk對所提SABPSO算法的性能進行測試，測試函數如表1所示。

表1 基準測試函數Table 1 The Benchmark function

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

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

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

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

3.2 對比標準

實驗采用3 種標準判斷算法的收斂性能，即

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

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

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

3.3 實驗結果分析

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

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

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

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

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

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

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

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

圖1 函數F1Fig.1 Function F1

圖2 函數F2Fig.2 Function F2

圖3 函數F3Fig.3 Function F3

圖4 函數F4Fig.4 Function F4

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

圖5 測試函數F1Fig.5 Test function F1

圖6 測試函數F2Fig.6 Test function F2

圖7 測試函數F3Fig.7 Test function F3

圖8測試函數F4Fig.8 Test function F4

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

4 結 論

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