自適應(yīng)爆炸半徑的改進(jìn)煙花算法

趙志剛，李智梅，莫海淼，曾 敏，溫 泰

(廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004)

0 引 言

Tan等[1]提出了煙花算法(fireworks algorithm，F(xiàn)WA)，該算法收斂速度快，易于實(shí)現(xiàn)，且具有爆發(fā)性、多樣性和隨機(jī)性等特點(diǎn)，目前被廣泛應(yīng)用于網(wǎng)絡(luò)定位[2]、JSP問(wèn)題求解[3]、投資組合優(yōu)化問(wèn)題[4]、聚類(lèi)[5]等多個(gè)領(lǐng)域。煙花算法在應(yīng)用到某些實(shí)際的過(guò)程中表現(xiàn)力不從心，因此眾多學(xué)者對(duì)煙花算法進(jìn)行改進(jìn)，主要是對(duì)FWA算法的算子分析及改進(jìn)以及與其它啟發(fā)式算法結(jié)合成混合算法[6]。Barraza等[7]基于模糊邏輯，對(duì)爆炸火花數(shù)目以及爆炸振幅進(jìn)行調(diào)整，提高了煙花算法的性能。Zhang等[8]提出了BBO-FWA算法，將生物地理學(xué)優(yōu)化算法的遷移算子引入煙花算法，表現(xiàn)出了較強(qiáng)勘探能力。Babu等[9]基于粒子群算法和遺傳算法的改進(jìn)煙花算法來(lái)精確識(shí)別光伏(PV)模塊的雙二極管模型未知參數(shù)，有效地解決了這一建模問(wèn)題。Bao等[10]提出了一種改進(jìn)的混沌煙花算法，在求解多目標(biāo)JSP問(wèn)題上具有較高的準(zhǔn)確性和魯棒性。Xue等[11]提出了一種自適應(yīng)煙花算法(SaFWA)來(lái)優(yōu)化分類(lèi)模型，利用4種候選解生成策略(CSGSS)來(lái)提高解的多樣性。Yan等[12]提出了具有線性降維策略的動(dòng)態(tài)搜索煙花算法(ld-dynFWA)，提高了算法的效平衡率和穩(wěn)定性，并將其應(yīng)用于求解條件非線性最優(yōu)攝動(dòng)CNOP問(wèn)題。

以上方法沒(méi)有考慮到被丟棄的爆炸火花信息利用的問(wèn)題。為了更好地提高煙花算法的性能，利用被丟棄的爆炸火花的信息，改進(jìn)爆炸機(jī)制，提出了一種具有自適應(yīng)學(xué)習(xí)改進(jìn)煙花算法。該算法從信息利用、自適應(yīng)步長(zhǎng)及種群多樣性的增加3個(gè)角度對(duì)FWA算法進(jìn)行改進(jìn)，以爆炸火花的數(shù)目為分種群依據(jù)，利用爆炸火花的位置信息來(lái)構(gòu)建爆炸半徑，并對(duì)全局最優(yōu)進(jìn)行高斯變異。為了對(duì)改進(jìn)煙花算法進(jìn)行性能測(cè)試實(shí)驗(yàn)，選擇10個(gè)比較常見(jiàn)的基準(zhǔn)測(cè)試函數(shù)以及幾種經(jīng)典的群智能優(yōu)化算法(如標(biāo)準(zhǔn)粒子群算法PSO、帶高斯擾動(dòng)的粒子群算法GPSO、蝙蝠算法BA、煙花算法FWA、自適應(yīng)煙花算法AFWA、增強(qiáng)煙花算法EFWA)進(jìn)行對(duì)照并分析。

1 煙花算法

煙花算法是根據(jù)煙花在夜空中爆炸的現(xiàn)象而提出的一種新型群智能優(yōu)化算法，該算法主要包括四大部分：爆炸算子(爆炸強(qiáng)度、爆炸幅度和位移操作)、變異算子、映射規(guī)則和選擇策略。

1.1 爆炸強(qiáng)度

煙花爆炸時(shí)，煙花種群的每個(gè)煙花都會(huì)生成相應(yīng)的爆炸火花子種群。適應(yīng)度值越好的煙花爆炸強(qiáng)度越大，爆炸火花的數(shù)量就越多；相反，爆炸強(qiáng)度越小，爆炸火花的數(shù)量就越少[13]。爆炸強(qiáng)度的計(jì)算如式(1)所示

(1)

式中：Si表示第i個(gè)煙花產(chǎn)生爆炸火花的數(shù)量；m是限制爆炸火花數(shù)量的常量；Ymax是煙花中最差適應(yīng)度值的個(gè)體；f(xi)是第i個(gè)煙花的目標(biāo)函數(shù)的適應(yīng)度值；θ是極小的機(jī)器數(shù)；pop是指煙花種群數(shù)目。

使用式(2)來(lái)控制爆炸火花數(shù)量的大小

(2)

其中，round()為四舍五入的取整函數(shù)；α和β均為常數(shù)變量。

1.2 映射規(guī)則

在尋優(yōu)的過(guò)程中，需對(duì)越界的煙花個(gè)體進(jìn)行如下越界處理

(3)

1.3 選擇策略

FWA算法是基于歐氏距離來(lái)計(jì)算任意兩個(gè)煙花個(gè)體間的距離，計(jì)算公式如下

(4)

其中，d(xi,xj) 是任意兩個(gè)煙花xi與xj間的歐式距離；R(xi) 是煙花個(gè)體xi到其它個(gè)體的距離的總和；l∈K是第l個(gè)位置屬于集合K；K表示煙花、爆炸算子和變異算子產(chǎn)生火花的煙花種群位置集合。

在進(jìn)行下一代煙花種群選擇時(shí)，其策略是采用輪盤(pán)賭的方式，與其它個(gè)體具有更遠(yuǎn)距離的煙花個(gè)體具有更大的可能性被選擇，每個(gè)個(gè)體被選中的概率用p(xi)表示，即

(5)

1.4 變異算子

高斯變異是對(duì)煙花隨機(jī)選擇若干個(gè)維度進(jìn)行操作，該操作具體為

(6)

2 改進(jìn)的煙花算法

在FWA算法中，由1.3小節(jié)選擇策略可知，沒(méi)有被選中為下一代煙花的爆炸火花則完全被丟棄，這浪費(fèi)了被丟棄的爆炸火花的信息。針對(duì)這一點(diǎn)，引入sparkpBest來(lái)表示在尋優(yōu)過(guò)程中每個(gè)煙花所產(chǎn)生的最優(yōu)爆炸火花個(gè)體的集合，并將其和最優(yōu)煙花個(gè)體gBest來(lái)構(gòu)造新的爆炸半徑，同時(shí)對(duì)gBest進(jìn)行變異算子操作進(jìn)一步增加種群的多樣性，避免煙花算法有“早熟”的情況。

2.1 新的位移操作和爆炸半徑

位移操作是對(duì)煙花的每一維度進(jìn)行操作，在FWA算法中，由于一個(gè)煙花爆炸時(shí)在每個(gè)維度上產(chǎn)生了相同位移偏移的爆炸火花，煙花算法的多樣性有所降低。改進(jìn)的煙花算法在煙花個(gè)體產(chǎn)生爆炸火花的過(guò)程中，因?yàn)槭褂昧藷熁ǖ奈恢眯畔?lái)構(gòu)造新的爆炸半徑，能夠自適應(yīng)地調(diào)整步長(zhǎng)，這就使得在各個(gè)維度上可以采取不同的位移偏移來(lái)進(jìn)行位移操作，其更新公式如下

xlast(l)=x(i)+r*EA(i)

(7)

其中，l=1,2,…,Si；x(i) 是第i個(gè)煙花未爆炸前的位置，xlast(l)是第i個(gè)煙花爆炸后對(duì)應(yīng)子種群的第l個(gè)爆炸火花的位置；r是在[0,1]內(nèi)的隨機(jī)數(shù)，服從均勻分布；EA(i) 是第i個(gè)煙花爆炸產(chǎn)生的火花相對(duì)原始煙花的范圍(煙花的爆炸半徑)。

爆炸半徑是指煙花個(gè)體發(fā)生爆炸之后所發(fā)生的位移，通過(guò)FWA算法中爆炸半徑的計(jì)算公式可得，煙花的爆炸半徑是利用煙花的適應(yīng)度值來(lái)獲取，這是不科學(xué)的，這是因?yàn)閷?duì)于多維空間問(wèn)題而言，可能會(huì)存在多個(gè)煙花的適應(yīng)度值相等而位置不一樣的情況，即無(wú)法判斷實(shí)際的位置，因此改用位置信息。另外，根據(jù)式(4)，沒(méi)有被選中為下一代煙花的爆炸火花則完全被丟棄，這浪費(fèi)了被丟棄的爆炸火花的信息。針對(duì)這一點(diǎn)，引入sparkpBest來(lái)表示在尋優(yōu)過(guò)程中每個(gè)煙花所產(chǎn)生的最優(yōu)爆炸火花個(gè)體的集合，并將其和最優(yōu)煙花個(gè)體gBest來(lái)構(gòu)造新的爆炸半徑，以爆炸火花數(shù)目作為分種群的依據(jù)，將煙花種群分為兩類(lèi)，爆炸強(qiáng)度小于平均爆炸強(qiáng)度的煙花為次好煙花，次好煙花向sparkpBest靠攏，即擴(kuò)大搜索范圍進(jìn)行全局搜索；爆炸強(qiáng)度大于或者等于平均爆炸強(qiáng)度的煙花為優(yōu)質(zhì)煙花，優(yōu)質(zhì)煙花向此時(shí)最優(yōu)煙花位置靠攏，即向當(dāng)前種群最優(yōu)gBest學(xué)習(xí)，在gBest附近進(jìn)行詳細(xì)的局部搜索提高收斂速度。

新的爆炸半徑計(jì)算公式具如下所示

(8)

其中，sparkpBest(i)是第i個(gè)煙花產(chǎn)生的爆炸火花子種群中的個(gè)體最優(yōu)；AvgS是此時(shí)所有爆炸火花的均值，即

(9)

2.2 全局最優(yōu)個(gè)體的高斯變異

式(6)是隨機(jī)選擇幾個(gè)維度來(lái)進(jìn)行高斯變異，在此基礎(chǔ)上，再對(duì)全局最優(yōu)個(gè)體gBest進(jìn)行高斯變異，即對(duì)該最優(yōu)個(gè)體的所有維度進(jìn)行變異算子操作，以便能夠增加煙花算法中種群的多樣性，使得改進(jìn)煙花算法的全局搜索能力得到增強(qiáng)，提高其運(yùn)算結(jié)果，具體操作如下

gBest=gBest*(N(0,1)+1)

(10)

其中，N(0,1) 是服從均值為0，方差為1的高斯分布函數(shù)。

2.3 ARFWA算法

綜上所述，提出了一種改進(jìn)的煙花算法，即自適應(yīng)爆炸半徑的改進(jìn)煙花算法(improved fireworks algorithm with adaptive explosion radius，ARFWA)。ARFWA算法的偽代碼如下：

步驟1 初始化煙花種群x，全局最優(yōu)gBest，每個(gè)煙花所產(chǎn)生的最優(yōu)爆炸火花個(gè)體的集合sparkpBest；

步驟2 獲取每一個(gè)煙花的適應(yīng)度值；

步驟3 將gBest狀態(tài)更新；

步驟4 通過(guò)式(10)和式(3)對(duì)gBest前后進(jìn)行高斯變異和越界處理操作；

步驟5 通過(guò)式(1)來(lái)計(jì)算煙花的爆炸強(qiáng)度；

步驟6 通過(guò)式(8)和式(9)來(lái)計(jì)算每一個(gè)煙花的爆炸半徑；

步驟7 通過(guò)式(7)來(lái)進(jìn)行位移操作，并更新sparkpBest；

步驟8 使用式(6)產(chǎn)生高斯火花；

步驟9 根據(jù)1.3小節(jié)的選擇策略來(lái)選擇下一代煙花；

步驟10 不斷執(zhí)行步驟2～步驟9，符合終止條件時(shí)就停止操作。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)測(cè)試函數(shù)

為了評(píng)估改進(jìn)的煙花算法在函數(shù)優(yōu)化的有效性，實(shí)驗(yàn)選取了10個(gè)基準(zhǔn)測(cè)試函數(shù)進(jìn)行算法對(duì)比，如表1所示，包含其域，最優(yōu)值以及維度信息。

表1 基準(zhǔn)測(cè)試函數(shù)

3.2 參數(shù)設(shè)置

ARFWA算法和FWA算法的參數(shù)設(shè)置均參見(jiàn)文獻(xiàn)[1]，SPSO算法參見(jiàn)文獻(xiàn)[14]，GPSO算法參見(jiàn)文獻(xiàn)[15]，BA算法參見(jiàn)文獻(xiàn)[16]，自適應(yīng)煙花算法參見(jiàn)文獻(xiàn)[17]，增強(qiáng)煙花算法參見(jiàn)文獻(xiàn)[18]。為了客觀對(duì)比，7種算法的種群大小均為10，尋優(yōu)精度設(shè)置為10-5。本次實(shí)驗(yàn)運(yùn)行次數(shù)設(shè)置為100次，最大迭代次數(shù)設(shè)置為1000次。實(shí)驗(yàn)平臺(tái)是Matlab 2016Ra，Inter(R) Xeon(R) CPU E5-1620 v3 @3.5 GHz,window10操作系統(tǒng)。

3.3 收斂性能分析

對(duì)表1的函數(shù)進(jìn)行仿真實(shí)驗(yàn)，得到各個(gè)函數(shù)的求解質(zhì)量，如表2所示(worst是最差值、best是最佳值、avg是平均值、std是方差值)，avg的平均排名結(jié)果見(jiàn)表3，尋優(yōu)成功率用SR表示，見(jiàn)表4，各算法的尋優(yōu)進(jìn)化曲線圖展示如圖1至圖10所示。為了方便對(duì)比分析，f7的適應(yīng)度值是負(fù)數(shù)沒(méi)有取對(duì)數(shù)，保持原始值不變，剩余函數(shù)的曲線圖中縱坐標(biāo)log10(Fitness)代表其適應(yīng)度值均取對(duì)數(shù)log10。各函數(shù)(除了f1、f3、f4和f9外)的演化曲線出現(xiàn)部分重疊的情況。

表2 各個(gè)函數(shù)求解質(zhì)量

表3 在測(cè)試函數(shù)上的平均排名

表4 f1～f10：7種算法尋優(yōu)成功率SR/%

觀察f1、f3、f4、f6和f9函數(shù)尋優(yōu)進(jìn)化曲線圖(圖1、圖3、圖4、圖6和圖9)可知，當(dāng)算法迭代的次數(shù)是一樣時(shí)，ARFWA表現(xiàn)出的收斂性能(收斂速度和收斂精度)明顯比其它對(duì)比算法更出眾。由表2對(duì)應(yīng)函數(shù)的結(jié)果avg可得，ARFWA與GPSO具有一樣的avg，且比其它對(duì)比算法更優(yōu)。

圖1 f1尋優(yōu)進(jìn)化曲線

圖2 f2尋優(yōu)進(jìn)化曲線

圖3 f3尋優(yōu)進(jìn)化曲線

圖4 f4尋優(yōu)進(jìn)化曲線

圖5 f5尋優(yōu)進(jìn)化曲線

圖6 f6尋優(yōu)進(jìn)化曲線

圖7 f7尋優(yōu)進(jìn)化曲線

圖8 f8尋優(yōu)進(jìn)化曲線

圖9 f9尋優(yōu)進(jìn)化曲線

圖10 f10尋優(yōu)進(jìn)化曲線

觀察f2、f5函數(shù)尋優(yōu)進(jìn)化曲線圖(圖2和圖5)可知，在算法迭代前期，迭代的次數(shù)一樣時(shí)，ARFWA表現(xiàn)出的收斂性能(收斂速度和收斂精度)均比其它對(duì)比算法更優(yōu)秀；但是在算法迭代后期，這7種算法均有“早熟”的情況，局部搜索能力沒(méi)有很好發(fā)揮。由表2的f2函數(shù)的對(duì)應(yīng)avg可得，ARFWA的avg比其它對(duì)比算法更優(yōu)。由表2的f5函數(shù)的avg可得，ARFWA的搜索能力比AFWA算法略差，但是比其它對(duì)比算法更優(yōu)秀。

觀察f7函數(shù)尋優(yōu)進(jìn)化曲線圖(圖7)可知，當(dāng)算法的迭代次數(shù)相等時(shí)，ARFWA呈現(xiàn)出的收斂性能(收斂速度和收斂精度)與其它對(duì)比算法相比實(shí)力相當(dāng)，不分伯仲。由表2的f7的實(shí)驗(yàn)結(jié)果avg可知，ARFWA尋找到的平均解avg不亞于其它對(duì)比算法。

觀察f8函數(shù)尋優(yōu)進(jìn)化曲線圖(圖8)可知，當(dāng)算法的迭代次數(shù)相等時(shí)，ARFWA呈現(xiàn)出的收斂性能(收斂速度和收斂精度)稍差于AFWA，但是比其它對(duì)比算法更優(yōu)秀。由表2的f8函數(shù)的結(jié)果avg可知，ARFWA、AFWA和EFWA求得的avg是一樣的，但是比其它對(duì)比算法更優(yōu)。

觀察f10函數(shù)尋優(yōu)進(jìn)化曲線圖(圖10)可知，在尋優(yōu)前期，當(dāng)算法迭代次數(shù)相等時(shí)，ARFWA的收斂性能(收斂速度和收斂精度)稍差于AFWA，但是比其它對(duì)比算法突出；在算法尋優(yōu)后期，7種算法均呈現(xiàn)出“早熟”的情況，局部搜索能力需要進(jìn)一步提高。由表2的f10函數(shù)的avg可知，ARFWA求得的avg不亞于其它6種對(duì)比算法。

綜上可知，ARFWA總體的收斂性能優(yōu)于其它6種對(duì)比算法。

3.4 各算法在測(cè)試函數(shù)的平均排名

為了更直觀看出各個(gè)算法的搜索能力，由表2的avg得到各算法在測(cè)試函數(shù)上的平均排名見(jiàn)表3，從表中可知，ARFWA在7種算法中排名第一，遠(yuǎn)遠(yuǎn)優(yōu)于其它6種算法，即改進(jìn)的煙花算法的整體搜索能力優(yōu)于其它6種算法。

3.5 魯棒性分析

魯棒性的強(qiáng)弱可以通過(guò)標(biāo)準(zhǔn)偏差std的大小來(lái)判定。如果std越小，表示算法的魯棒性越強(qiáng)；反之，其魯棒性越弱。通過(guò)表2的實(shí)驗(yàn)結(jié)果，對(duì)于f1、f3、f4、f5和f9測(cè)試函數(shù)，ARFWA、FWA和GPSO表現(xiàn)出的實(shí)力相當(dāng)?shù)聂敯粜?，且比其?種對(duì)比算法更優(yōu)秀；對(duì)于f2測(cè)試函數(shù)，ARFWA的魯棒性比FWA和GPSO兩種算法略弱，但是比其它4種對(duì)比算法更強(qiáng)；對(duì)于f6測(cè)試函數(shù)，ARFWA、SPSO和GPSO具有實(shí)力相當(dāng)?shù)聂敯粜?，且比其?種對(duì)比算法更強(qiáng)；對(duì)于f7測(cè)試函數(shù)，ARFWA的魯棒性處于中等的實(shí)力，比SPSO、GPSO和AFWA這3種對(duì)比算法略弱，但比其它3種對(duì)比算法更強(qiáng)；在f8尋優(yōu)過(guò)程中，ARFWA的魯棒性稍遜于AFWA，但是優(yōu)于其它5種算法；在f10尋優(yōu)過(guò)程中，ARFWA的魯棒性稍遜于SPSO、GPSO、EFWA，但優(yōu)于其它3種算法。所以，綜上可得，在10個(gè)基準(zhǔn)函數(shù)尋優(yōu)過(guò)程中，ARFWA的魯棒性總體來(lái)說(shuō)是比較好的。

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

尋優(yōu)成功一次是指在優(yōu)化函數(shù)過(guò)程中，一次尋優(yōu)的結(jié)果與理論最優(yōu)值差值的絕對(duì)值不大于實(shí)驗(yàn)設(shè)置的精度。由表4得，在迭代結(jié)束時(shí)，ARFWA尋優(yōu)成功率均為100%的有8個(gè)基準(zhǔn)函數(shù)；GPSO尋優(yōu)成功率均為100%的有7個(gè)基準(zhǔn)函數(shù)；FWA尋優(yōu)成功率為100%的有6個(gè)基準(zhǔn)函數(shù)；AFWA尋優(yōu)成功率均為100%的有3個(gè)基準(zhǔn)函數(shù)；SPSO、EFWA尋優(yōu)成功率均為100%的只有2個(gè)基準(zhǔn)函數(shù)；BA尋優(yōu)成功率為100%的只有1個(gè)基準(zhǔn)函數(shù)。所以，整體而言，在10個(gè)基準(zhǔn)函數(shù)的尋優(yōu)過(guò)程中，ARFWA的尋優(yōu)成功率比較好。

3.7 討 論

通過(guò)實(shí)驗(yàn)對(duì)比分析可以知道，改進(jìn)的煙花算法ARFWA的整體性能比其它6種對(duì)比算法的更優(yōu)秀體現(xiàn)在如下幾個(gè)方面：

(1)將粒子群算法的記憶機(jī)制引入改進(jìn)的煙花算法中，借鑒了全局最優(yōu)和個(gè)體最優(yōu)的概念。本文引入sparkpBest來(lái)表示在尋優(yōu)過(guò)程中每個(gè)煙花所產(chǎn)生的最優(yōu)爆炸火花個(gè)體的集合以及gBest來(lái)表示全局最優(yōu)煙花。當(dāng)煙花的爆炸火花的數(shù)目大于或者等于平均爆炸火花的數(shù)目，說(shuō)明該煙花向gBest學(xué)習(xí)，此時(shí)的煙花位于相對(duì)比較好的區(qū)域；反之，當(dāng)煙花的爆炸火花數(shù)目小于平均爆炸火花數(shù)目時(shí)，說(shuō)明煙花向sparkpBest學(xué)習(xí)，此時(shí)煙花處于相對(duì)比較差的區(qū)域；

(2)對(duì)全局最優(yōu)gBest進(jìn)行高斯擾動(dòng)，以便增加種群的多樣性，避免出現(xiàn)“早熟”的現(xiàn)象；

(3)構(gòu)造了新的爆炸半徑計(jì)算公式，標(biāo)準(zhǔn)的煙花算法對(duì)未被選擇的爆炸火花全部丟棄，沒(méi)有充分利用到被丟棄的爆炸火花的信息，而改進(jìn)的煙花算法恰恰利用到這一點(diǎn)，將其充分利用，提高了煙花種群的信息利用率。

4 結(jié)束語(yǔ)

煙花算法是一種新穎的群智能算法，針對(duì)煙花算法后期收斂速度慢和求解精度不高的問(wèn)題，充分利用了被舍棄的爆炸火花個(gè)體的信息，構(gòu)造新的爆炸半徑計(jì)算公式，以便能夠自適應(yīng)地調(diào)整步長(zhǎng)；另外，在尋優(yōu)的過(guò)程中，在原來(lái)高斯擾動(dòng)的基礎(chǔ)上，對(duì)全局最優(yōu)個(gè)體進(jìn)行高斯擾動(dòng)，以此平衡局部和全局搜索能力，避免煙花種群過(guò)快陷入局部最優(yōu)，增強(qiáng)收斂速度和收斂精度。由仿真實(shí)驗(yàn)可得：相對(duì)其它6種算法，整體而言，改進(jìn)的煙花算法整體呈現(xiàn)出比較優(yōu)秀的性能，表現(xiàn)在收斂性能方面(收斂速度更快、收斂精度更高)和魯棒性更強(qiáng)。

在接下來(lái)的研究工作中，將對(duì)ARFWA算法進(jìn)行進(jìn)一步的優(yōu)化，并將其應(yīng)用于實(shí)際中。