帶柯西變異的自學習改進煙花算法

曾 敏,趙志剛,李智梅

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

1 引 言

煙花算法(Firework Algorithm,FWA)[1]是在2010年由Tan等人提出來的一種新型群智能優(yōu)化算法,通過模擬煙花在空中爆炸的行為來建立相關的數(shù)學模型,通過隨機因素以及選擇策略形成的一種并行爆炸式搜索方式,具有求解速度快、隱并行性的特點,成為了能夠求解復雜優(yōu)化問題最優(yōu)解的一種全局概率搜索方法.現(xiàn)已被廣泛的運用在各種實際優(yōu)化問題的求解,包括優(yōu)化調(diào)度[2]、微波成像[3]、電網(wǎng)營運管理[4]、圖像識別[5]、聚類[6]、路徑規(guī)劃[7]等.截止2019年三月,Google學術搜索顯示,煙花算法的首創(chuàng)論文已經(jīng)被應用了470次.

和其他智能優(yōu)化算法類似,煙花算法存在有收斂速度慢、求解精度不高等缺陷.對煙花算法的優(yōu)化主要分為兩類:一是對基本煙花算法算子進行分析與改進.文獻[8,9]分別提出了對火花生成策略和爆炸半徑進行改進的EFWA和AFWA;文獻[10]通過引入反向?qū)W習策略和動態(tài)記憶反饋的機制,提出一種煙花算法優(yōu)化算法;文獻[11]充分利用了爆炸火花的信息,從信息利用的角度提出了 GFWA.文獻[12]改進選擇策略,提出了ISSFWA;二是與其他啟發(fā)式算法相結合提出混合算法.文獻[13]將差分算法的差分變異替代煙花算法的高斯變異,提出了 FWA-DM.文獻[14]將生物地理學優(yōu)化算法中的遷移算子引入煙花算法提出了的 BBO-FWA 算法,具有較強的勘探能力.文獻[15]將進煙花算法和蟻群算法相結合提出一種混合算法并應用在避障路徑規(guī)劃.

為了進一步提高標準煙花算法的性能,本文提出一種新的改進煙花算法.該算法將高斯變異算子更換為全局搜索能力更強的柯西變異算子;用全局最優(yōu)煙花個體和歷史柯西火花的位置信息來構造新的爆炸半徑;并提出一種可以同時兼顧煙花質(zhì)量與分布的挑選策略.使用10個常用的基準測試函數(shù)和10個0-1背包問題對該改進算法的性能進行測試,并將其與經(jīng)典的蝙蝠算法(BA)、粒子群算法(SPSO)、帶高斯擾動的粒子群算法(GPSO)、煙花算法(FWA)、增強煙花算法(EFWA)、自適應煙花算法(AFWA)進行對比實驗.

2 分種群自學習改進煙花算法

2.1 柯西變異策略

在大規(guī)模數(shù)據(jù)集下,算法解決這類解空間較大的問題要求較高的全局搜索能力.因此,改進算法將標準煙花算法中的高斯變異算子更換為全局搜索能力更強的柯西變異算子,增大變異范圍,提高全局搜索能力.柯西分布的圖形似一個鐘形,兩翼寬,加大了尋優(yōu)范圍,如圖1所示,標準柯西分布在零點附近的波峰低于標準高斯分布,但兩邊趨向于零的速度比高斯分布要慢,由此可見柯西變異的擾動能力比高斯變異強,變異范圍更廣,較容易跳出局部最優(yōu).

圖1 標準高斯分布和標準柯西分布概率密度曲線對比圖Fig.1 Comparison of probability density curves of standard gaussian distribution and standard cauchy distribution

柯西變異的計算公式為：

(1)

其中,Cauchy(0,1)是標準柯西分布函數(shù),p為隨機變異概率.

2.2 自適應爆炸半徑

在煙花算法中,根據(jù)煙花種群個體的適應度值來計算爆炸火花數(shù)量以及爆炸半徑,適應度值較好(較小)的煙花個體往往擁有較小的爆炸半徑,即在較優(yōu)煙花個體周圍進行更加詳細的局部搜索;適應度值較差(較大)的煙花個體擁有較大的爆炸半徑,及達到擴大搜索范圍發(fā)揮全區(qū)搜索的效果,以此來平衡全區(qū)搜索和局部搜索的能力.在基本煙花算法中,爆炸幅度按照公式(2)計算.

(2)

當前煙花的適應度值等于Ymin時,此時煙花即為目前為止找到的最好的煙花,此時當前最好煙花所對應的爆炸幅度過小,起不到局部開發(fā)的作用,甚至會喪失局部挖掘能力,這樣就會浪費當前找到的最好煙花的資源.且從標準煙花算法的選擇策略可知,沒有被選為下一代的候選集高斯變異火花被丟棄,這樣則浪費了大量候選集火花資源.

為了使改進算法的爆炸半徑能及時地對搜索方向進行引導和限制,最理想的狀態(tài)是迭代初期,爆炸半徑較大來加強全局探索能力;迭代后期,爆炸半徑較小來以增強局部搜索能力,加快算法收斂.使算法求解精度與搜索速度達到一種平衡.

本文以信息利用的角度,以爆炸火花個數(shù)作為分種群依據(jù),將煙花種群分為3類:在每一次迭代的煙花種群中,對于一個最小化問題,處于目前最優(yōu)位置的煙花為核心煙花,擁有大于均值爆炸火花數(shù)的煙花為優(yōu)質(zhì)煙花,擁有小于均值爆炸火花數(shù)的煙花為良好煙花,不同類型煙花能夠自適應的調(diào)整爆炸半徑.為充分利用核心煙花,在核心煙花附近進行高斯擾動來進行更為詳細的局部搜索;優(yōu)質(zhì)煙花向目前為止找到的最好的煙花位置學習,達到向?qū)Ξ斍胺N群內(nèi)最優(yōu)秀的個體gbest學習的效果;良好煙花則向柯西火花歷史位置CauchySparkPbest學習,增加種群多樣性.煙花個體分種群的自適應爆炸半徑如下:

(3)

其中,CPbesti為柯西火花歷史位置信息,gbest為當前最好煙花即最優(yōu)煙花的位置信息,SNi為第i個煙花產(chǎn)生的爆炸火花數(shù)量,SNavg為種群爆炸火花數(shù)的平均值,N(0,1)是服從均值為0,方差為1的高斯分布函數(shù).

2.3 精英-隨機選擇策略

標準煙花算法中,選擇策略是基于歐式距離的,這種計算方式導致時間消耗很大,因此改進算法采取“精英-隨機”選擇策略,即從煙花、爆炸火花、柯西火花組成的候選集,選取適應度值最好的一個個體作為下一代煙花的“精英”,其余popsize-1個則從候選集中隨機選取(可以重復選擇).這樣既保證了保留最優(yōu)個體對煙花種群的領導,又保證了種群的多樣性且降低了計算復雜度.

2.4 算法流程

根據(jù)2.1～2.3小節(jié),在標準煙花算法的基礎上,本文提出了一種新的煙花算法改進算法——帶柯西變異的自學習改進煙花算法(Self-Learning Improved Fireworks Algorithm with Cauchy Mutation,SiFWA),該算法的算法流程如下:

算法1.分種群的自學習改進煙花算法步驟

輸入:煙花種群初始位置

輸出:煙花種群的位置和全局最優(yōu)解

Begin

1.初始化煙花種群；

2.確定生成子代火花數(shù)量;

3.根據(jù)公式3和2.2小節(jié)按不同種群分別計算爆炸半徑;

4.根據(jù)2.2小節(jié)生成子代爆炸火花;

5.母代煙花根據(jù)公式1生成柯西火花;

6.按照公式6對超出邊界的火花進行越界處理;

7.在煙花母代、爆炸煙花子代、柯西火花組成的候選集中,根據(jù)“精英-隨機”選擇策略選出下一代煙花;

8.重復Step 2-Step 7,直到達到終止條件,停止迭代.

End

在步驟2中,第i個煙花產(chǎn)生爆炸火花個數(shù)Si定義為:

(4)

為了限制煙花爆炸產(chǎn)生火花的數(shù)量,進行以下條件限制:

(5)

在尋優(yōu)的過程中,需要對越界的煙花進行如下越界處理:

(6)

3 實驗設置與結果分析

3.1 實驗設計

10個基準測試函數(shù)如表1所示,其中f1～f6維度為30dim,

表1 基準測試函數(shù)
Table 1 Benchmark functions

FunNameFuntionDimDomain最優(yōu)點最優(yōu)值Spheref1=∑ni=1x2i30[-100,100]d(0,0,…,0)0Rosenbrockf2=∑ni=1[100(xi+1-xi)2+(xi-1)2]30[-30,30]d(0,0,…,0)0Griewankf3=14000∑ni=1x2i-∏ni=1cos(xii)+130[-600,600]d(0,0,…,0)0Rastriginf4=∑ni=1(x2i-10cos(2πxi)+10)30[-5.12,5.12]d(0,0,…,0)0Ackleyf5=-20exp(-0.2∑ni=1x2i)-exp(1n)∑ni=1cos(2πxi)+20+e30[-32,32]d(0,0,…,0)0Schwefelf6=∑ni-1(∑ij=1xj)230[-100,100]d(0,0,…,0)0Six-Hump Camel-Backf7=4x21-2.1x41+13x61+x1x2-4x22+4x422[-5,5]2?-1.0316285Goldstein Pricef8=[1+(x1+x2+1)2(19-14x1+3x21-14x2+6x1x2+3x22)]·a[30+(2x1-3x2)2(18-32x1+12x21+48x2-36x1x2+27x22)]2[-2,2]2(0,-1)3Schaffer’s F6f9=sin2x21+x22-0.5[1+0.001(x21+x22)]2+0.52[-100,100]2(0,0)0Braninf10=(x2-5.14π2x21+5πx1-6)2+10(1-18π)cosx1+102-5

f7～f10維度為2dim.“*”表示該函數(shù)不止一個最優(yōu)點.并與蝙蝠算法(BA)[16]、標準粒子群算法(SPSO)[17]、帶高斯擾動的粒子群算法(GPSO)[18]、標準煙花算法(FWA)[1]、增強煙花算法(EFWA)[8]、自適應煙花算法(AFWA)[9]進行對比實驗.

改進算法的煙花種群大小設置為5,火花總數(shù)設置為50,柯西火花數(shù)量設置為5.BA算法的參數(shù)設置參考文獻[16],SPSO算法的參數(shù)設置參考文獻[17],GPSO算法的參數(shù)設置參考文獻[18],FWA算法的參數(shù)設置參考文獻[1],EFWA算法的參數(shù)設置參考文獻[8],AFWA算法的參數(shù)設置參考文獻[9].為估計改進算法的性能,且保證模擬仿真實驗的公平性,我們將對表1的基準測試函數(shù)設定獨立運行次數(shù)為run_num=51,最大評價次數(shù)MaxIteration=104×dim次.種群初始解的質(zhì)量在一定程度上影響最終解的質(zhì)量,為了避免初始位置對實驗的影響,在同一測試函數(shù)上,7種算法均使用同一組初始位置.測試得到最壞值worst、最好值best、平均值avg、標準方差std見表2,尋優(yōu)成功率SR見表3、將10個測試函數(shù)尋優(yōu)的平均值作為衡量算法收斂性的指標,以標準方差值作為衡量魯棒性的指標.

表2 7種算法實驗結果對比
Table 2 Comparison of experimental results of the 7 algorithms

algfunworstbestavgstdfunworstbestavgstdBA1.06E-036.95E-049.10E-049.92E-054.44E-118.47E-185.43E-129.30E-12SPSO7.47E-015.37E-022.67E-011.53E-010000GPSO00000000FWAf10000f61.08E-1371.71E-2032.31E-1391.51E-138EFWA1.23E-015.10E-029.07E-021.62E-024.10E-085.38E-125.81E-099.13E-09AFWA4.12E-183.00E-224.34E-199.01E-190000SiFWA00000000BA2.95E+011.67E+012.44E+012.87E+00-1.0316280-1.0316285-1.03162849.83E-08SPSO6.66E+033.75E+016.86E+021.35E+03-1.0316285-1.0316285-1.03162852.61E-16GPSO2.87E+012.82E+012.86E+011.16E-01-1.0316285-1.0316285-1.03162852.61E-16FWAf22.85E+012.47E+012.56E+015.39E-01f7-1.0316284-1.0316285-1.03162842.55E-09EFWA5.05E+033.33E+014.96E+021.06E+03-1.0316285-1.0316285-1.03162851.72E-11AFWA9.60E+022.07E+011.59E+022.48E+02-1.0316285-1.0316285-1.03162853.52E-16SiFWA2.46E+012.38E+012.42E+011.61E-01-1.0316284-1.0316285-1.03162851.75E-09BA5.61E-053.23E-054.59E-055.90E-0630.00002193.00000016.70588659.38E+00SPSO9.79E-029.21E-034.28E-022.01E-023.00000003.00000003.00000001.58E-15GPSO00003.00000003.00000003.00000001.58E-15

續(xù)表

3.2 收斂性分析

為了對收斂速度和收斂精度的觀察更加的直觀,文中給出圖2至圖7的尋優(yōu)進化曲線.為縮減篇幅,僅給出部分基準測試函數(shù)的尋優(yōu)進化曲線.其中縱坐標中的適應度值均取對數(shù)log10,即log10(Fitness).

圖2 f1尋優(yōu)進化曲線Fig.2 Evolution curve of f1

圖3 f3尋優(yōu)進化曲線Fig.3 Evolution curve of f3

在f1、f3、f4、f6、f9的尋優(yōu)過程中,分析圖2,圖3,圖4,圖5,圖7:在尋優(yōu)前期,在相同的評價次數(shù)下,SiFWA的收斂速度和收斂精度都優(yōu)于其他6種對比算法.分析表2中所對應的平均解avg:SiFWA均找到了最優(yōu)解,且不亞于其他6種對比算法.

圖4 f4尋優(yōu)進化曲線Fig.4 Evolution curve of f4

圖5 f6尋優(yōu)進化曲線Fig.5 Evolution curve of f6

在f2、f5的尋優(yōu)過程中,分析表2中所對應的平均解avg:迭代結束時對于f2,SiFWA所尋平均解avg優(yōu)于其他6種對比算法;對于f5,SiFWA所尋平均解avg不亞于其他6種對比算法.

在f7、f8、f10的尋優(yōu)過程中,分析表2中所對應的平均解avg:尋優(yōu)結束后SiFWA所尋平均解avg不亞于其他6種對比算法.

綜上所述,SiFWA算法的總體收斂性能優(yōu)于其他6種對比算法.

圖6 f8尋優(yōu)進化曲線Fig.6 Evolution curve of f8

圖7 f9尋優(yōu)進化曲線Fig.7 Evolution curve of f9

3.3 尋優(yōu)成功率分析

尋優(yōu)精度設置為λ=10-5,也就是說如果所尋解的絕對值與理論最優(yōu)解的絕對值的差值小于或等于該精度值時,記錄尋優(yōu)成功一次.表3所對應的尋優(yōu)成功率可知:對于f2、f107種算法均沒有找到理論最優(yōu)值;對于f1、f3、f4、f5、f6、f7、f8、f9,SiFWA的尋優(yōu)成功率均為100%,優(yōu)于其他6種對比算法.

綜上所述,MAFWA算法的總體尋優(yōu)成功率優(yōu)于其他6種對比算法.

表3 7種算法尋優(yōu)成功率(%)
Table 3 Success rate of seven algorithms(%)

algf1f3f4f5f6f7f8f9f2,f10BA000010010082.3566.670SPSO000010010010066.670GPSO10010010010010010010066.670FWA1001001001001001001001000EFWA000010010010098.040AFWA10049.0221.5772.510010010049.020SiFWA1001001001001001001001000

3.4 魯棒性分析

算法魯棒性可反映在標準方差std上,std值越小,算法魯棒性越好;std值越大,算法魯棒性則越差.分析表2中對應的標準方差std一欄:在f1、f3、f4、f5、f6、f9的尋優(yōu)過程中,SiFWA算法所得的標準方差std均為0,表現(xiàn)出較好的穩(wěn)定性.在基準測試函數(shù)f2的尋優(yōu)過程中,SiFWA算法所得的標準方差std比BA、SPSO、FWA、EFWA、AFWA小,大于GPSO;在f7的尋優(yōu)過程中,SiFWA算法所得的標準方差std比BA、FWA小,大于SPSO、AFWA、GPSO、EFWA;在基準測試函數(shù)8的尋優(yōu)過程中,SiFWA算法所得的標準方差std比BA、FWA小,略大于SPSO、GPSO、EFWA、AFWA;在基準測試函數(shù)f10的尋優(yōu)過程中,SiFWA算法所得的標準方差std比BA、SPSO、GPSO、EFWA小,略大于FWA、AFWA.

綜上所述,SiFWA的總體魯棒性能優(yōu)于其他6種對比算法.

3.5 討論

綜上所述,本文出的改進SiFWA算法,使用全局搜索能力更強的柯西變異算子來替代高斯變異算子,增大變異范圍,提高全局搜索能力,增加了種群多樣性;從“信息利用”的角度,用全局最優(yōu)煙花個體和歷史柯西火花的位置信息來構造新的爆炸半徑,解決了爆炸幅度設定困難的問題,自適應式的爆炸半徑使得煙花種群能在在迭代過程中學習有價值的歷史信息,使其不僅能夠繼承和學習歷史信息,而且能夠自適應地調(diào)整步長;并使用“精英-隨機”選擇策略,同時兼顧煙花質(zhì)量與分布.由仿真實驗結果可知,改進算法有效的平衡了全局搜索和局部開發(fā)能力,在求解精度和穩(wěn)定性表現(xiàn)出較好的性能.

4 算法應用

4.1 0-1背包問題

通過仿真實驗,SiFWA在解決連續(xù)優(yōu)化問題上有較好表現(xiàn),離散優(yōu)化是最優(yōu)領域一個非常重要的分支,是應用數(shù)學和計算機科學中優(yōu)化問題的重要分支.為了進一步驗證本文提出的算法的有效性,我們將其應用于離散優(yōu)化問題中的求解 0-1 背包問題(Knapsack Problem,KP).0-1背包問題的數(shù)學模型如下:

(7)

(8)

其中,n為物品的數(shù)量,pi和vi表示第i個物品擁有的價值和體積,Vmax表示背包的最大體積限制,自變量xi表示物品的狀態(tài),0表示沒有被裝進背包,1表示被裝進背包.其中每個物品最多被裝入背包一次,且只能完全裝入,不允許部分裝入.

現(xiàn)需考慮在不超過背包容積的前提下,怎樣使裝入背包中的物品總價值最大.使用罰函數(shù)法最大化問題轉(zhuǎn)化為最小化問題,0-1背包問題轉(zhuǎn)化為:

(9)

4.2 算法離散化應用

0-1背包問題屬于離散類型問題,在算法應用時應將煙花種群個體的位置信息進行離散化處理,其具體操作如下:

(10)

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

SiFWA算法求解0-1背包問題的偽代碼參照2.4小節(jié),但是在計算個體的適應度值之前,需要根據(jù)公式(10)對其位置進行離散化處理.

4.3 對比實驗

對于其他6種對比算法(BA,SPSO,GPSO,FWA,EFWA,AFWA)進行同樣的離散化處理之后,對實驗結果進行比較.算法比較過程選用文獻[19]中的10個常見的0-1背包問題.

求解0-1背包問題的相關參數(shù)設置:最大迭代次數(shù)為104×dim次;設置獨立重復運行次數(shù)為30次;其他參數(shù)設置參照3.1小節(jié),對比實驗的結果如表4所示.

表4 0-1背包問題結果分析
Table 4 Results analysis of 0-1 knapsack problem

algexampleworstbestavgstdSR(%)exampleworstbestavgstdSR(%)BA29529529501005252520100SPSOf11252295289.531.14E+01434752511.58E+0060GPSO252295289.631.29E+0150f16495251.578.60E-0177FWA288295294.571.38E+0087455251.571.33E+0080EFWA29529529501005252520100AFWA29529529501005252520100SiFWA29529529501005252520100BA10241024102401001071071070100SPSO9191024981.272.57E+0113f1793107105.32.81E+0050GPSOf129291024980.732.71E+017102107104.931.39E+0017FWA9021024973.933.39E+01796107106.632.01E+0097EFWA10241024102401001071071070100AFWA10241024102401001071071070100SiFWA10241024102401001071071070100BA3535350100976197679764.071.93E+0010SPSO3535350100974197679754.87.01E+003GPSOf13333534.933.70E-0197f189727976797558.55E+003FWA3535350100973497659755.57.44E+000EFWA35353501009767976797670100AFWA35353501009767976797670100SiFWA35353501009767976797670100BA23232301001301301300100SPSO2323230100118130128.83.66E+0090GPSOf142323230100118130129.62.19E+0097FWA2323230100f19109130125.88.54E+0080EFWA23232301001301301300100AFWA23232301001301301300100SiFWA23232301001301301300100BA481.0694481.0694481.06942.89E-131001025102510250100SPSO398.3123481.0694456.85128.26408931025978.833.53E+0117GPSO408.0508481.0694459.333323.143390710259823.30E+013FWAf15386.816481.0694464.738531.7467f208661011949.33.69E+010EFWA481.069368481.069368481.0693683.44523E-131001025102510250100AFWA481.069368481.069368481.0693683.44523E-131001025102510250100SiFWA481.069368481.069368481.0693682.89E-131001025102510250100

表4的實驗結果顯示:由均值avg這一欄可知,SiFWA算法找到的均值不亞于其他6種對比算法,由std這一欄可知:SiFWA算法的魯棒性不亞于其他6種對比算法.由SR這一欄可知:SiFWA算法的總體尋優(yōu)成功率不亞于其他6種對比算法.綜上,SiFWA算法在求解文獻[19]中給出的10個常見的0-1背包問題時,總體性能不亞于其他6種對比算法.

5 結 論

在煙花算法中,爆炸幅度的設定與選擇策略是影響算法整體性能的關鍵.本文提出了一種改進的煙花算法——帶柯西變異的自學習改進煙花算法.該算法以搜索能力更強的柯西變異代替高斯變異火花,通過學習利用煙花的歷史爆炸信息,自適應地估計后代煙花的爆炸幅度,解決了爆炸幅度這個參數(shù)難以設定的問題.使得改進算法在尋優(yōu)過程中可以很好的平衡全局搜索和局部開發(fā)的能力.為了檢測算法的有效性,將其應用在了基準測試函數(shù)的優(yōu)化以及求解典型0-1背包問題中,通過對比實驗,我們可以知道:與其他6種對比算法相比,帶柯西變異的自學習改進煙花算法可以以相對少的評價次數(shù)找尋到更好的解,擁有更快的收斂速度和更高的收斂精度.在未來的工作中,將對帶柯西變異的自學習改進煙花算法進行更加深入的理論研究,將其應用到更多的工程實踐之中.