具有自適應步長與協同尋優的蝙蝠煙花混合算法

莫海淼,趙志剛,曾 敏,石 靜,溫 泰

(廣西大學 計算機與電子信息學院,南寧 530004)

1 前 言

煙花算法(Fireworks Algorithm,FWA)[1]是由Tan等人于2010年提出的,并且被廣泛應用于JSP問題的求解[2]、聚類[3]、網絡規劃[4]、圖像識別[5]、函數優化[6]等領域.

從此之后,煙花算法吸引了越來越多的學者對其進行深入的研究.通過對原始煙花算法進行深入的研究分析,并針對FWA的不足,一些研究者提出了相關的改進方法.改進煙花算法主要可以被分為兩類[7],一類是在基本煙花算法的基礎上進行算子的分析和改進,另一類是與其他啟發式算法的混合算法的研究.第一類對煙花算法改進的工作主要有:Liu等提出一種構造型煙花算法(IFWA)[8],它引入一種新型的爆炸半徑和爆炸火花數目計算方式,讓擁有較好適應度值的煙花在更小的爆炸半徑內產生更多的爆炸火花.Zheng等[9]人針對算子存在的缺陷提出了相應的改進策略,最終提出EFWA.文獻[10]和文獻[11]均是對最優的煙花個體引入了自適應的爆炸半徑,并提高了算法的性能.李席廣等[12]將反向學習與動態記憶反饋的思想引入煙花算法,提出了一種新的煙花算法,并得到不錯的實驗效果.Li 等[13]從信息利用的角度,在煙花算法中充分利用了爆炸火花的信息,并提出了 GFWA.方柳平等[14]通過嵌入一種利用歷史成功信息生成兩種不同的學習因子來改進dynFWA,來平衡算法的局部搜索和全局搜索能力.第二類對煙花算法改進的工作主要有:Gao 等[15]人將文化算法和煙花算法混合,改變了煙花算法中爆炸火花產生方式和選擇策略,提出了CA-FWA算法.Yu等[16]人將差分演化算法的差分變異算子替換煙花算法的高斯變異算子,并提出了FWA-DM.Zhang等[17]將生物地理學優化算法的遷移算子引入煙花算法,提出了具有較強勘探能力的BBO-FWA算法.為了進一步提高標準煙花算法的性能,本文將蝙蝠算法(Bat Algorithm,BA)[18]的局部搜索機制引入到煙花算法,以協助煙花算法尋優;并利用蝙蝠種群與煙花種群的位置信息構造了新的爆炸半徑,使其能夠自適應地調整步長;最后,使用“精英-隨機”策略選擇下一代煙花,以及對全局最優個體進行高斯擾動,來保證種群的多樣性,避免過快地陷入局部最優解.基于以上的思想,本文提出了蝙蝠煙花混合算法,并使用十個常用的基準函數以及五個0-1背包問題對蝙蝠煙花混合算法的性能進行測試,并與經典的蝙蝠算法、粒子群算法、煙花算法等五種算法進行對比實驗.

2 混合算法

2.1 協同尋優

蝙蝠個體根據回聲定位的原理,以及發出的脈沖和響度信息來判斷獵物的位置來定位獵物,即當蝙蝠個體在當前最優解gbest附近進行局部搜索時,如果它所處的位置更接近獵物,則將脈沖調整變大,同時把響度調小,然后繼續搜尋和定位獵物,并不斷地靠近獵物.這就是蝙蝠算法局部搜索的基本原理.將蝙蝠算法的局部搜索引入煙花算法,并協助煙花算法尋優,把這個過程稱作協同尋優.協同尋優是指在尋優過程中,蝙蝠種群根據蝙蝠發出的脈沖和響度在最優煙花gbest附近協助煙花種群尋優,并且加強兩個種群在尋優過程中的信息交流,其主要操作是初始化一個蝙蝠種群BatX(用來存放全局最優煙花gbest附近產生的局部解),假設第i個蝙蝠個體發出的脈沖r(i)小于隨機脈沖時,則對gbest進行高斯擾動之后產生一個局部解BatX(i),然后對該蝙蝠個體的位置信息BatX(i)進行評價:假如該蝙蝠個體的適應度值優于煙花種群的第i個煙花X(i),且它產生的響度A(i)大于隨機生成的響度時,則該蝙蝠個體被加入煙花種群中,其操作如公式(1)和公式(2)所示.

BatX(i)=gbest*(N(0,1)+1),as r(i)

(1)

其中,i=1,2,…,popsize;N(0,1)是服從均值為0,方差為1的高斯分布函數;r(i)是第i個蝙蝠個體發出的脈沖;rand是[0,1]范圍內服從均勻分布的隨機數.

X(i)=BatX(i),asf(BatX(i))rand

(2)

其中,X(i)是第i個煙花所在的位置;A(i)是第i個蝙蝠發出的響度;rand是[0,1]范圍內服從均勻分布的隨機數.

蝙蝠種群通過發出的脈沖信息在全局最優煙花gbest附近產生一個局部解;并使用蝙蝠個體發出的響度、脈沖與所處位置的優劣來更新煙花種群.這樣,蝙蝠種群與煙花種群不斷地進行交互,協同尋優,而公式(1)和公式(2)相結合則加強蝙蝠種群和粒子群在尋優過程中的信息交互,協同尋優.協同尋優的操作如算法1所示.

算法1.協同尋優.

輸入:蝙蝠種群的位置BatX.

輸出:煙花種群的位置X和全局最優煙花個體gbest.

Begin

1. for i=1:popsize

2. if r(i)

3. 按公式(1)產生一個局部解;

4. endif

5. 越界處理;

6. 計算該局部解的適應度值f(BatX(i));

7. iff(BatX(i))rand

8. X(i)= BatX(i);

9. 更新脈沖r(i)和響度A(i);

10. endif

11. iff(BatX(i))

12. gbest = BatX(i);

13. endif

14. endfor

End

2.2 自適應步長

當煙花的爆炸火花數達到當前最大時,本文使用蝙蝠算法在最優位置附近產生局部解的位置BatX、蝙蝠發出的頻率Q、煙花位置X、全局最優煙花個體gbest來構造新的爆炸半徑,其具體操作如公式(3)所示.

(3)

其中,X(i)是第i個煙花的位置;BatX(i)的含義與公式(1)相同;Si是指第i個煙花個體產生的爆米花數量;Qi是指第i個蝙蝠個體產生的頻率;AvgS是指此時煙花種群產生爆炸火花數量的平均值,即

(4)

其中,popsize是指煙花個體的數量.

將公式(3)代入公式(4)之后,可知:當第i個煙花個體的爆炸火花數量大于平均爆炸火花數時,則該煙花個體往全局最優附近產生的一個局部解Batx(i)靠攏;當煙花個體產生的爆炸火花數小于平均爆炸火花數時,則該煙花個體往gbest靠攏.假設此時產生爆炸火花數量最多的煙花個體也往gbest靠攏,就相當于該煙花個體沒有產生位移,這樣便浪費了該煙花個體的資源;若該煙花個體向gbest附近的局部解BatX(i)靠攏時,則充分發揮了該煙花個體的作用,并使它在全局最優gbest附近進行詳細的局部搜索,而蝙蝠發射出隨機的頻率Qi,則保證了該煙花個體在gbest附近搜索的隨機性.使用蝙蝠與煙花的位置信息來構造新的爆炸半徑,這樣便能使粒子能夠自適應地調整步長.此時,煙花位移操作如下:

Xnew(i)=X(i)+R(i)

(5)

2.3 “精英-隨機”策略

本文采取 “精英-隨機”選擇策略來選擇下一代的煙花,即從煙花、煙花產生高斯變異之后的高斯煙花、煙花爆炸后產生的所有爆炸火花這三者共同組成候選集,從候選集中選取適應度值最好的個體作為下一代煙花的“精英”(僅有一個),其他popsize-1個下一代的煙花則從候選集中隨機選取(可以重復選擇).選擇下一代煙花的具體操作為:將候選集以適應度值進行升序排序,然后選擇適應度值最好的個體作為下一代的其中一個煙花,下一代其他煙花的選取則根據候選集的下標進行隨機選取.

2.4 混合算法

綜上所述,本文提出一種新的算法——蝙蝠煙花混合算法(the hybrid Bat and Fireworks Algorithm,BAFWA).BAFWA算法的偽代碼如算法2所示.

算法2.本文蝙蝠煙花混合算法的具體過程.

輸入:蝙蝠種群的位置、煙花種群的位置.

輸出:蝙蝠種群更新之后的位置、煙花種群更新之后的位置、全局最優個體gbest.

Begin

1.初始化蝙蝠種群BatX、煙花種群X、最優個體gbest以及兩個種群的相關參數;

2.使用蝙蝠種群協助煙花種群尋優:具體參照算法1;

3.計算爆炸火花的數量;

4.按公式(3)和公式(4)來計算爆炸半徑;

5.產生爆炸火花,并按公式(5)進行位移操作;

6.越界處理;

7.產生高斯煙花;

8.用2.3小節的“精英-隨機”策略來選擇下一代煙花;

9.重復步驟2至步驟8,若達到終止條件(一般為達到設定的尋優精度或者達到最大的迭代次數),則停止迭代.

End

表1 基準函數
Table 1 Benchmark functions

FunNameFuntionDomainDimOptimumSpheref1(x)=∑ni=1x2i[-100,100]d300Rosenbrockf2(x)=∑ni=1[100(xi+1-xi)2+(xi-1)2][-10,10]d300Griewankf3(x)=14000∑ni=1x2i-∏ni=1cos(xii)+1[-600,600]d300Rastriginf4(x)=∑ni=1(x2i-10cos(2πxi)+10)[-5.12,5.12]d300Ackleyf5(x)=-20exp(-0.2∑ni=1x2i)-exp(1n)∑ni=1cos(2πxi)+20+e[-32,32]d300Schwefelf6(x)=∑ni=1(∑nj=1xj)2[-100,100]d300Six-HumpCamel-Backf7(x)=4x21-2.1x41+13x61+x1x2-4x22+4x42[-5,5]22-1.0316285GoldsteinPricef8(x)=[1+(x1+x2+1)2(19-14x1+3x21-14x2+6x1x2+3x22)]·[30+(2x1-3x2)2(18-32x1+12x21+48x2-36x1x2+27x22)][-2,2]223Schaffer′sF6f9(x)=sin2x21+x22-0.5[1+0.001(x21+x22)]2+0.5[-100,100]220Braninf10(x)=(x2-5.14π2x21+5πx1-6)2+10(1-18π)cosx1+10-5

3 仿真實驗

3.1 測試函數

本文選用了如表1所示的10個測試函數來測試BAWFA混合算法的性能,并與蝙蝠算法BA、煙花算法FWA、標準粒子群算法[19,20](Standard Particle Swarm Optimization,SPSO)、增強煙花算法(Enhanced Fireworks Algorithm,EFWA)[9]、 自適應煙花算法(Adaptive Fireworks Algorithm,AFWA)[11]進行對比實驗.

3.2 參數設置

本文對比實驗的相關參數是根據相關文獻的建議來進行設置的.其中,蝙蝠算法的參數設置參照文獻[18];標準粒子群算法的參數設置參照文獻[19,20];煙花算法的參數設置參照文獻[1];增強煙花算法的參數設置參照文獻[9];自適應煙花算法的參數設置參照文獻[11];蝙蝠煙花混合算法的最小頻率設置為0.1,最大頻率設置為100,popsize設置為10,其他參數設置參照蝙蝠算法與煙花算法;六種算法的尋優精度均設置為λ=10-5,即到達尋優精度時,則標記成功尋優一次.本文對表1的測試函數做了100次獨立重復實驗,最大迭代次數MaxIteration=1000.

3.3 收斂性分析

對表1的10個測試函數進行測試得到最差值worst、最好值best、平均值avg、標準偏差std如表2所示;尋優成功率SR如表3所示.為了縮減篇幅,本文只給出部分的演化曲線圖,如圖1-圖6(測試函數進化曲線的適應度值均取對數log10,即其縱坐標為log10Fitness)所示.

圖1 f1尋優演化曲線Fig.1 Evolution curve of f1

由圖1可知,在優化f1函數的過程中,BA、SPSO、EFWA和AFWA的收斂曲線較平緩,說明這4種算法的種群多樣性較差,極易陷入局部最優解;而BAFWA的收斂曲線較陡峭,其收斂速度優于其他5種算法;在尋優過程中,BAFWA不到100次迭代,就已經尋找到最優解0(由于尋優曲線圖的縱坐標是log10Fitness,而尋找到最優解0時,即Fitness=0,此時的尋優曲線在圖上無法顯示);而其他5種算法在迭代終止時也沒有尋找到最優解0.由表2中f1的實驗數據可知,在迭代結束(iteration=1000)時,BAFWA尋找到的平均解avg均優于其他5種算法,故BAFWA的收斂精度優于其他5種算法.綜上可知,在f1函數的尋優過程中,BAFWA的收斂性能優于其他5種算法.

圖2 f3尋優演化曲線Fig.2 Evolution curve of f3

由圖2、圖3、圖5和圖6可知,在優化函數f3、f4、f6和f9的過程中,在迭代結束之后BAFWA和FWA都尋找到最優解,其他四種算法沒有尋找到最優解且在尋優后期陷入局部最優解;在迭代次數相同時,BAFWA的收斂速度和收斂精度均優于其他5種算法.由表2中f3、f4、f6和f9的實驗數據可知,在迭代結束時,BAFWA和FWA尋找到的平均解均相同,且優于其他4種算法.綜上可知,在f3、f4、f6和f9的尋優過程中,BAFWA的收斂性能均優于其他5種算法.

圖3 f4尋優演化曲線Fig.3 Evolution curve of f4

圖4 f5尋優演化曲線Fig.4 Evolution curve of f5

由圖4可知:在優化f5函數的過程中,在迭代結束之后6種算法均沒有尋找到最優解;在尋優前期,迭代次數相同時,BAFWA的收斂速度和收斂精度均優于其他5種算法.由表2中f5的實驗數據可知,在迭代結束后,BAFWA和FWA尋找到的平均解均相同,且優于其他4種算法.綜上可知,在f5函數的尋優過程中,BAFWA的收斂性能均優于其他5種算法.

圖5 f6尋優演化曲線Fig.5 Evolution curve of f6

由表2中f2的實驗數據可知:在迭代結束之后,6種算法均沒有尋找到最優解,但是BAFWA尋找到的平均解avg優于其他5種算法.

圖6 f9尋優演化曲線Fig.6 Evolution curve of f9

由表2中f7的實驗數據可知:在迭代結束之后,BAFWA尋找到的平均解avg劣于SPSO、AFWA、EFWA,卻不亞于其他3種算法.

由表2中f8的實驗數據可知:在迭代結束之后,BAFWA尋找到的平均解avg與SPSO、AFWA、EFWA相同,并且優于其他2種算法.

由表2中f10的實驗數據可知:在迭代結束之后,BAFWA尋找到的平均解avg優于FWA,卻劣于其他4種算法.

3.4 魯棒性分析

標準偏差的大小反映了算法魯棒性的好壞,即標準偏差越小,則算法的魯棒性越好;反之,則算法的魯棒性越差.

由表2的實驗數據std可知,在f1、f3、f4、f5和f9尋優過程中,BAFWA和FWA的魯棒性一樣好(在f5的尋優過程中,雖然EFWA的魯棒性與BAFWA相同,但它的平均解avg劣于BAFWA),且均優于其他4種算法;在f2的尋優過程中,BAFWA的魯棒性優于其他5種算法;在f6的尋優過程中,BAFWA和SPSO的魯棒性一樣好,且均優于其他4種算法;在f7的尋優過程中,BAFWA的魯棒性優于BA、FWA,卻劣于其他3種算法;在f8的尋優過程中,BAFWA的魯棒性優于BA、FWA、EFWA,卻劣于其他2種算法;在f10的尋優過程中,BAFWA的魯棒性優于FWA,卻劣于其他4種算法.因此,綜上所述,在十個基準函數的尋優過程中,BAFWA的魯棒性總體較好.

表2 十種基準函數的四種算法比較
Table 2 Comparison of four algorithms for ten benchmark functions

3.5 尋優成功率分析

表3 十個基準函數的尋優成功率
Table 3 Success rate(%)for ten benchmark functions

由表3可知,將尋優精度設置為λ=10-5,則在迭代結束后,6種算法在f2和f10的尋優成功率均為0%,而BAFWA在剩余其他8個基準函數的尋優成功率均為100%;FWA尋優成功率為100%的只有6個基準函數;BA、SPSO、EFWA和AFWA的整體尋優成功率稍差.因此,在十個基準函數的尋優過程中,BAFWA總體的尋優成功率優于其他五種算法.

綜上所述,本文提出的混合算法比其他五種算法具有更好的優化性能源自以下幾個方面:

1)煙花算法引入了蝙蝠算法的局部搜索機制.蝙蝠算法具有極強的局部搜索能力,并且利用蝙蝠算法在全局最優個體gbest附近進行詳細的局部搜索,以提高種群的收斂性能.

2)利用蝙蝠種群和煙花種群的位置信息構造新的爆炸半徑,新的爆炸半徑不僅繼承了兩個種群的信息,而且能夠自適應地調整步長.

3)“精英-隨機”策略和高斯擾動,使種群在尋優過程中保持多樣性,避免過快地陷入局部最優解.

4)蝙蝠種群和煙花種群協同尋優,并且加強了兩個種群之間的信息交互,也能提高混合算法的收斂性能.

4 算法應用

4.1 0-1背包問題

背包問題是一個典型的NP完全問題.為了進一步驗證本文提出的算法的有效性,本文將其應用于求解0-1背包問題(Knapsack Problem,KP).0-1背包問題的數學模型如下:

(6)

(7)

其中,n 為物品的數量,第i個物品擁有的價值和體積分別為pi和vi,背包的最大體積限制用Vmax表示,自變量xi用來表征物品的狀態,有 0 和 1 兩個數值可選.當xi的值為1時,表示該物品i已經被裝入包中,反之,如沒有裝入包中,xi取值為0.每個物品最多被裝入背包一次,只能全部裝入,不允許部分裝入.

0-1背包問題是具有復雜約束的最大化問題,對于這些約束,采用外部罰函數法進行處理.同時,將最大化問題轉化為最小化問題,將f(x)轉化為-f(x).這樣,0-1背包問題就轉化為:

(8)

4.2 混合算法離散化設計

由于0-1背包問題是離散問題,因此,需要將煙花個體和蝙蝠個體的位置進行離散化處理,其具體操作如下:

(9)

其中,x′(i,j)是第i個個體第j維所在離散化處理之前的位置信息,x(i,j)是第i個個體的第j維所在離散化處理之后的位置信息.

混合算法求解0-1背包問題的偽代碼參照算法1和算法2,但是在計算個體的適應度值之前,需要對其所在的位置進行離散化處理(參照公式(9)).

4.3 對比實驗

其他5種對比算法(BA、SPSO、FWA、EFWA、AFWA)的離散化處理操作具體如下:

(10)

在算法比較的過程中,選用了5個0-1背包問題[21],具體如表4所示.

表4 五個常見的背包問題
Table 4 Five common knapsack problems

問題dimf?參數f11435w=(6,5,9,7)Vmax=20p=(9,11,13,15)f12423w=(2,4,6,7)Vmax=11p=(6,10,12,13)f131052w=(30,25,20,18,17,11,5,2,1,1)Vmax=60p=(20,18,17,15,15,10,5,3,1,1)f147107w=(31,10,20,19,4,3,6)Vmax=50p=(70,20,39,37,7,5,10)f155130w=(15,20,17,8,31)Vmax=80p=(33,24,36,37,12)

4.4 實驗結果與分析

在求解0-1背包問題的過程中,設置最大的迭代次數為500,其他參數設置則參照3.2小節,并且進行50次獨立重復實驗,其對比實驗結果如表5所示.根據表5的實驗結果:由max可知,6種算法均能尋找到最優解f*;由方差std可知,在求解5個0-1背包問題的過程中,BAFWA的魯棒性不亞于其他5種算法;由尋優成功率SR可知,BAFWA的總體尋優成功率不亞于其他五種算法.因此,綜上可知,BAFWA算法在求解表4的0-1背包問題的整體性能不亞于其他五種算法.

表5 5個背包問題的對比實驗結果
Table 5 Comparation results of 5 knapsack problems

algfmaxavgminstdSR(%)BAf113535350100SPSO3535350100FWA3532.82243.055E+0052AFWA3535350100EFWA3535350100BAFWA3535350100BAf122323230100SPSO2323230100FWA2322.74196.642E-0180AFWA2323230100EFWA2323230100BAFWA2323230100BAf135251.98511.141E-0198SPSO5251.44497.866E-0160FWA5246.94383.644E+006AFWA5252520100EFWA5252520100BAFWA5252520100BAf141071071070100SPSO107104.98933.133E+0050FWA107100.96746.960E+0034AFWA1071071070100EFWA1071071070100BAFWA1071071070100BAf151301301300100SPSO130129.341093.390E+0096FWA130109.8721.446E+0120AFWA1301301300100EFWA1301301300100BAFWA1301301300100

5 結 論

從本文的仿真對比實驗中,可以得出這樣的結論:在求解本文仿真實驗中的相關問題時,相比其他五種對比算法,本文提出的蝙蝠煙花混合算法具有相對更快的收斂速度,更高的收斂精度以及更好的魯棒性.在未來的工作中,將對蝙蝠煙花混合算法進行更深入的理論研究,并將其運用到更多的具體工程實踐中.