邱飛岳,王京京
(浙江工業(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í)因子策略能夠提升算法的收斂精度。
為了克服傳統(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的概率。
自適應(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)全局與局部探索的平衡,提升算法的搜索精度。
SABPSO算法的粒子速度更新采用基本BPSO算法的速度更新公式,映射函數(shù)采用V型映射函數(shù),其計算式為
(4)
粒子位置更新采用VBPSO算法中的非強制性位置更新程序,其計算式為
(5)
基本二進(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。
文獻(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)
學(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的遞減而遞增。
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
利用4 個經(jīng)典的測試函數(shù)驗證所提SABPSO算法的收斂性能,并分別與3 個采用不同學(xué)習(xí)因子更新策略的二進(jìn)制粒子群優(yōu)化算法進(jìn)行對比。由于SABPSO算法在初始化時采用了混沌策略,為了保證實驗數(shù)據(jù)能夠反映不同學(xué)習(xí)因子策略的對比情況,在其他3 個對比算法中也加入混沌策略。
測試函數(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 種標(biāo)準(zhǔn)判斷算法的收斂性能,即
1) 均值:各對比算法在實驗平臺上單獨運行30 次獲得的數(shù)據(jù)平均值。
2) 方差:各對比算法在實驗平臺上單獨運行30 次獲得的數(shù)據(jù)方差。
3) 分布狀態(tài):利用箱須圖檢驗數(shù)據(jù)的分布狀態(tài)。
表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)更新策略能夠提升算法的收斂性能。
通過對學(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)化。