張水平，李殷俊，高 棟，梁 文

江西理工大學(xué) 信息工程學(xué)院，江西 贛州 341000

1 引言

群體智能是進化計算中的活躍分支，包括基于生物和非生物的優(yōu)化算法。煙花算法便是模擬煙花的爆炸結(jié)合進化計算的隨機搜索而產(chǎn)生的新型搜索算法，由Tan等[1]于2010年提出。

此后，許多改進算法相繼被提出[2-11]并總結(jié)了研究進展[12]。Pei 等[13]提出基于適應(yīng)度函數(shù)估計的加速型煙花算法，使用種群的適應(yīng)度值信息估計搜索空間的形狀，將形狀最優(yōu)位置作為啟發(fā)式信息進行加速搜索，相比煙花算法基于距離信息的估計在性能加速方面有一定提升。Zheng 等[14]提出增強煙花算法，對算法存在的缺陷進行逐一改進，重在將輪盤賭方法改為精英-隨機選擇策略，減少了算法的時間消耗。Liu 等[15]提出自適應(yīng)煙花算法，通過最優(yōu)個體和一個特定個體間的距離計算新的爆炸半徑，加強了算法的局部搜索能力。以上改進算法均只對煙花算法的部分進行強化，本文則對各個組成進行詳細分析做出改進，相比基本煙花算法有了全面的提升。

現(xiàn)有改進研究采用的測試函數(shù)，其最優(yōu)值在原點或原點附近，由于煙花算法映射規(guī)則和變異算子加強了原點附近的搜索，所以算法易于求解原點附近的最優(yōu)值；若優(yōu)化函數(shù)的最優(yōu)值遠離原點，則煙花算法表現(xiàn)出較差的性能。為了減少煙花算法的缺陷，本文在整體提升的基礎(chǔ)上引入動態(tài)調(diào)整爆炸半徑的策略來加強局部搜索及跳出局部收斂的能力，同時提高算法搜索精度。通過實驗驗證了所提出算法的有效性。

2 煙花算法

FWA（Fireworks Algorithm）模擬煙花爆炸的現(xiàn)象，通過初始的N個煙花經(jīng)歷爆炸和變異生成新的火花，采用映射規(guī)則爆炸保證所有火花在可行域內(nèi)，基于歐式距離從煙花和火花中選擇新一代的N個煙花。開始迭代直到滿足問題的精度或者達到最大函數(shù)評估次數(shù)。

2.1 算法框架

煙花算法的執(zhí)行流程圖如圖1所示。

圖1 煙花算法執(zhí)行流程圖

具體實現(xiàn)包括以下步驟：

（1）在給定的解空間內(nèi)隨機產(chǎn)生N個初始煙花，每個煙花表示解空間內(nèi)的一個解。初始煙花集合X=[x1,x2,…,xN]，煙花的維度為D。

（2）根據(jù)適應(yīng)度函數(shù)計算每個煙花的適應(yīng)度值f(xi)，通過f(xi)計算每個煙花的爆炸半徑Ai和爆炸數(shù)量Si，進而產(chǎn)生爆炸火花。爆炸半徑集合A=[A1,A2,…,AN]，每個煙花爆炸的數(shù)量集合S=[S1,S2,…,SN]，產(chǎn)生的火花集合Y=[yi1,yi2,…,yij,…,yiSi]，其中i∈[1,N]，j∈[1,Si]。煙花爆炸半徑的計算公式為：

產(chǎn)生火花數(shù)量的計算公式為：

其中，m是一個常數(shù)，用來限制火花數(shù)量的最大值，Ymax是當前種群適應(yīng)度值最優(yōu)的結(jié)果，參數(shù)ε的含義與式（1）等同。

火花數(shù)量的限制計算公式為：

其中，round()是取整函數(shù)，a和b是給定的常數(shù)。

煙花位移產(chǎn)生火花的計算公式為：

（3）對部分煙花進行高斯變異，變異火花的集合G=[G1,G2,…,Gi]，計算公式為：

其中，gs是服從均值和方差都為1 的高斯分布的隨機數(shù)，×是乘運算。

對超出邊界的火花采用映射規(guī)則，計算公式為：

其中，是第k維的上界是下界，%是模運算。

（4）煙花和火花的總集合C={X?Y?G}從C中選擇N個個體作為下一代的初始煙花。采用歐式距離計算兩個個體間的距離，計算公式為：

其中，xi和xj表示集合C中任意兩個個體。Dis(xi)是個體xi與其余個體的距離總和。

采用輪盤賭計算選擇的概率，計算公式為：

（5）循環(huán)步驟（1）～（4），直到滿足終止條件。

2.2 煙花算法分析

算法的爆炸半徑和爆炸火花數(shù)量根據(jù)式（1）和（2）得到，可以看出適應(yīng)度值越差，生成的爆炸半徑越大，由此產(chǎn)生的火花數(shù)量越少，因此擴大搜索范圍，增加個體多樣性；適應(yīng)度值越好，生成的爆炸半徑越小，產(chǎn)生的火花數(shù)量越多，從而縮小搜索范圍。這樣的火花產(chǎn)生機制并不能確保煙花種群的多樣性，因為大范圍的火花數(shù)量過少，在選擇機制中可能無法被選上。

通常測試函數(shù)的全局最優(yōu)點在原點、搜索空間的上下邊界對稱且超出邊界的都是一個很小的值，這種映射規(guī)則會使得超出邊界的點被人為設(shè)定到原點位置附近，從而無意中加速了算法的收斂性。假設(shè)目標函數(shù)的搜索范圍是[-10,10]，當火花在第k維度上的位置上是11，即超過邊界時，根據(jù)式（6）該維度會被映射到y(tǒng)ikj=-10+|11|%(20)=1，這距離原點很近。同時，高斯變異算子也容易將解變異到原點位置附近，當隨機產(chǎn)生的服從高斯分布的隨機變量g接近0時，高斯變異煙花的位置就會接近于0，并且后期難以跳出，這就導(dǎo)致許多變異煙花的位置靠近原點。因此一個解的位置如果已經(jīng)十分接近原點位置，那么高斯變異將很難使得該點的位置跳出原點位置附近的區(qū)域，易陷入局部最優(yōu)。

3 動態(tài)爆炸半徑的增強煙花算法

在分析各個算子后提出了不同于EFWA（Enhanced Fireworks Algorithm）的改進算子，并引入動態(tài)爆炸半徑機制，控制搜索范圍的變化，避免算法陷入早熟并提高尋優(yōu)結(jié)果的精度。具體改進如下。

3.1 煙花種群初始化的改進

圖2 初始種群過于集中的煙花爆炸圖

煙花算法中種群初始化采用隨機策略，若初始化的解過于集中，如圖2 所示，那么搜索前期將浪費較多的資源進行局部搜索；若初始化的解比較分散，則圖3 是前期所期望進行的全局搜索。因此將整個解空間N等分，N=5，每一部分隨機生成一組解以確保前期的全局范圍。因為煙花種群數(shù)N的設(shè)定很小，所以無需采用混沌初始化等方法，這樣調(diào)控會帶來在可接受范圍內(nèi)的小幅度的計算開銷。圖4 是5 等分下的種群示意圖，煙花在爆炸范圍內(nèi)產(chǎn)生下一代火花，避免可能存在的初始解過于集中的問題，也更加符合期望的先全局后局部的搜索策略。

圖3 期望種群初始化下的煙花爆炸圖

圖4 解空間5等分下的煙花爆炸圖

3.2 對變異算子的改進

由于高斯變異(xij=xijg)在當前位置和原點之間產(chǎn)生火花，容易將解變異到原點位置附近，故將高斯變異改為隨機變異，公式如下：

其中，g是一個高斯分布的隨機變量，xij是第i個煙花在第j維上的位置，是第i個煙花在第j維上的下界，是第i個煙花在第j維上的上界，rand(0,1)是0到1之間均勻分布的隨機數(shù)。

3.3 對映射規(guī)則的改進

當一個火花在某一維度上超出邊界，可以通過映射規(guī)則將其映射到一個新的位置，同高斯變異一樣，F(xiàn)WA的映射規(guī)則容易將解映射到搜索空間原點附近的位置，故將其改為隨機映射規(guī)則，即

其中，XUB,k和XLB,k分別表示該優(yōu)化問題的上邊界和下邊界，U( 0,1) 是在[0，1]區(qū)間上的均勻隨機分布隨機數(shù)。

3.4 對選擇策略的改進

在基本煙花算法中，采用的是基于歐式距離的輪盤賭的方法，但這種方法比較耗時，于是提出了一種雙精英-錦標賽選擇策略。競標賽方法相比輪盤賭所需時間更少，為了提高個體的多樣性，除了首先選擇歐式距離最大的個體以外，也保留了最優(yōu)適應(yīng)度值的個體，即為雙精英保持策略。接著對剩下的煙花采取錦標賽方法，從煙花和火花的總集合C={X?Y?G}中隨機選擇5個個體，再選擇其中最優(yōu)的個體進入下一代種群直至達到原來的種群規(guī)模，即

其中，f(X)min是集合X中最小適應(yīng)度值，Dis(X)max是最大歐式距離。

3.5 引入爆炸半徑動態(tài)調(diào)整機制

引入爆炸半徑的調(diào)整機制是為了提高煙花算法跳出局部收斂的能力以及全局搜索能力，由于爆炸半徑是煙花算法中的一個關(guān)鍵算子，它嚴重影響著算法的性能，因此將爆炸半徑作為主要改進的環(huán)節(jié)?；緹熁ㄋ惴ǖ陌霃绞歉鶕?jù)式（1）所得，由A?限制其最大值，每一次迭代的每個煙花爆炸半徑均為隨機產(chǎn)生。為了加強算法局部搜索以及全局搜索能力，因此采取動態(tài)調(diào)整A?的方式，從而達到控制全部煙花爆炸半徑最大值的效果。

DER（Dynamic Explosion Radius）如算法1所示：

算法1計算n+1 代爆炸半徑

1.Amax=ub-lb

2.ifYmin＜fmin:then

3.s=Amax*As

4.else:s=Amax*Ab

5.endif

6.ifs＜1:then

7.s=Amax

8.As=As-0.01

9.end if

其中，Amax為初始半徑兼最大半徑，Ymin是該次迭代的最優(yōu)適應(yīng)度值，fmin 為上次迭代的最優(yōu)適應(yīng)度值，As、Ab是常數(shù)，控制半徑s的變化，*表示相乘。算法1的計算復(fù)雜度是O( 1) ，額外的計算開銷并不大，通過這樣一個自適應(yīng)的半徑，可以對搜索范圍進行微調(diào)，使算法能夠更加精細的局部搜索和更寬廣的全局搜索。

圖5給出了爆炸半徑的變化示意圖，根據(jù)算法1，初始半徑由函數(shù)的上界和下界決定，從圖中可以看出，半徑隨迭代次數(shù)的增加而曲線下降，即搜索范圍逐漸下降，從而產(chǎn)生更多的火花進行局部搜索，由于前期搜索范圍很大，因此不可避免地減慢了前期的收斂速度。相比煙花算法的固定半徑，動態(tài)縮小半徑能夠提高算法求解的精度，當達到最小爆炸范圍后，將現(xiàn)有半徑重置為初始半徑，動態(tài)增大半徑用以跳出局部收斂，同時減小As，使得半徑曲線獲得更快的下降速度，避免算法收斂過慢，直至達到迭代次數(shù)。

圖5 爆炸半徑曲線變化圖

3.6 EFWA-DER流程

步驟1對N、dim、lb、ub、a、b、m、A?、T等參數(shù)進行初始化，N為初始煙花個數(shù)，dim為目標函數(shù)的維度，lb、ub分別是函數(shù)搜索范圍的上下界，a、b、m、A?分別是給定的常數(shù)用來限制爆炸火花的半徑和數(shù)量，T為函數(shù)評估次數(shù)。

步驟2根據(jù)式（1）～（3）計算t=1 時每個煙花產(chǎn)生的爆炸半徑和火花數(shù)量，由式（4）和式（8）分別產(chǎn)生爆炸火花和變異火花。

步驟3如果產(chǎn)生的火花超出了搜索范圍，則按照式（9）將其映射到可行域內(nèi)。

滑窗寬度的取值與飽和度存在一定聯(lián)系，圖4為最優(yōu)滑窗寬度與飽和點數(shù)的關(guān)系，當飽和點數(shù)小于初始窗寬W0時，最優(yōu)窗寬在初始窗寬周圍波動，當飽和點數(shù)大于W0時，最優(yōu)窗寬與飽和點數(shù)大致成線性關(guān)系.

步驟4根據(jù)式（10）選擇下一代煙花種群。

步驟5根據(jù)2.1 節(jié)的算法控制t=2 之后的爆炸半徑變化，代入式（1）中。

步驟6循環(huán)步驟2～步驟5，直至達到最大函數(shù)評估次數(shù)。

引入動態(tài)爆炸半徑算子之后，改進煙花算法爆炸半徑能夠根據(jù)上一代最優(yōu)解自適應(yīng)地改變，增加爆炸半徑以提高全局搜索能力，或者減小半徑以增強局部搜索，采用雙精英的策略以保證個體的多樣性，避免陷入局部最優(yōu)。

3.7 算法時間復(fù)雜度對比

3.7.1 FWA時間復(fù)雜度

根據(jù)FWA流程，種群初始化的時間復(fù)雜度為O(N)，生成爆炸半徑的時間復(fù)雜的為O(N)，產(chǎn)生火花的時間復(fù)雜度為O(N)，越界處理的時間復(fù)雜度為O(N)，計算歐式距離的時間復(fù)雜度為O(N×M)，輪盤賭法選擇下一代種群的時間復(fù)雜度為O(N+N×M)，其中N是煙花種群數(shù)，M是煙花產(chǎn)生的火花數(shù)。所有步驟經(jīng)過T次迭代，得到FWA時間復(fù)雜度如下：

3.7.2 EFWA-DER時間復(fù)雜度

TFWA(n)-TEFWA-DER(n)=O(5n2+2n3)-O(6n2+n+n3)=O(n3-n2-n),因此EFWA-DER 的時間復(fù)雜度小于FWA的時間復(fù)雜度。

4 實驗分析

4.1 實驗設(shè)計

選擇9 個包含單峰和多峰的標準測試函數(shù)，測試EFWA-DER 與FWA、SPSO2011 的尋優(yōu)精度、收斂速度等性能。由于FWA 本身的缺點，對于原點和原點附近的最優(yōu)值有較強的求解能力，所以增加了偏移函數(shù)的測試。文獻[14]給出了EFWA 和FWA 的實驗結(jié)果，EFWA在12 個標準測試函數(shù)上都表現(xiàn)出比FWA 差的性能，只在偏移函數(shù)的測試中性能更好，所以本文雖在改進的算子方面與EFWA 有所區(qū)別，但也不必將EFWA 加入比較。表1 給出9 個測試函數(shù)的表達式、搜索范圍、最優(yōu)點、最優(yōu)值以及維度。

實驗用Python實現(xiàn)，設(shè)置隨機數(shù)種子確保各算法的隨機數(shù)相同。FWA 和EFWA-DER 的參數(shù)設(shè)置如下：煙花N=5，爆炸數(shù)量參數(shù)m=50,a=0.04,b=0.8,爆炸半徑參數(shù)A?=40,As=0.99,Ab=1.01 ，SPSO2011 的參數(shù)設(shè)置參考文獻[16]，偏移參數(shù)設(shè)置如表2 所示，SI 是偏移指數(shù)，SV 是偏移量。函數(shù)評估次數(shù)為1萬次，設(shè)置20 個不同的 seed 值，運行 20 次，實驗環(huán)境：Python3.7.3；Win10；Intel Corei5-8300H 2.3 GHz；8 GBRAM。

4.2 實驗結(jié)果

4.2.1 標準測試函數(shù)結(jié)果

比較了3 種算法的在9 種函數(shù)上消耗的時間，F(xiàn)WA的運行時間為1，其余為FWA 的相對運行時間，由圖6得出SPSO2011 的耗時最嚴重，在函數(shù)f1、f2、f5、f6、f8上EFWA-DER 小于FWA，而在f3、f4、f7、f9上則相反，EFWA-DER的平均耗時優(yōu)于FWA。

表3 是測試函數(shù)在20 種不同隨機數(shù)種子下運行取得的最優(yōu)值和最差值，加粗數(shù)據(jù)為最優(yōu)值。由表中數(shù)據(jù)可得，EFWA-DER、FWA在f3、f7、f9上均取得全局最優(yōu)值，在f1上取得相同局部最優(yōu)值。EFWA-DER 在f2、f4、f5、f8上的搜索結(jié)果相比FWA 有更高的求解精度，在f6上取得全局最優(yōu)值。綜合可得EFWA-DER的尋優(yōu)結(jié)果要優(yōu)于FWA。

表1 標準測試函數(shù)

表2 測試函數(shù)的偏移信息

圖6 兩種算法相對FWA的運行時間

圖7 給出了9 個函數(shù)的收斂曲線，為了明顯地觀察各種算法的曲線變化，對9個函數(shù)選擇各自適合的迭代次數(shù)，根據(jù)圖7和表3得出，在f1、f3、f6、f8、f9上EFWADER 的收斂速度低于FWA，在f2、f4、f7上EFWA-DER與FWA的收斂速度相差不大。因此，在不排除FWA本身存在缺陷的情況下，EFWA-DER的收斂速度不如FWA。

綜上所述，F(xiàn)WA-DER 的尋優(yōu)時間和搜索結(jié)果均優(yōu)于FWA，在收斂速度上不如FWA。

表3 不同隨機數(shù)下各算法的尋優(yōu)結(jié)果

4.2.2 偏移測試函數(shù)結(jié)果

9種測試函數(shù)中，算法僅在f3、f7、f8、f9上不受隨機數(shù)影響并取得了最優(yōu)值，所以只對它們進行偏移測試。表4給出了具體的實驗數(shù)據(jù)，由于數(shù)據(jù)并不直觀，圖8顯示了2 種算法偏移結(jié)果的折線圖。由圖8 可見，EFWADRE在偏移條件下的曲線更平穩(wěn)，且偏移程度更小，因此FWA 易在原點或原點附近尋優(yōu)的缺陷是顯而易見的，EFWA-DER則不存在這樣的問題。

圖7 標準測試函數(shù)的收斂曲線

4.3 實驗結(jié)果分析

4.3.1 基準測試函數(shù)實驗結(jié)果分析

FWA 易于在原點或原點附近尋優(yōu)，這是由于其映射規(guī)則和高斯變異均會將解映射和變異到原點附近導(dǎo)致的。從基準測試函數(shù)實驗結(jié)果中可以看出，因為測試函數(shù)的最優(yōu)點為原點或原點附近的值，所以FWA 的前期收斂速度很快，能夠以較少的迭代次數(shù)搜索到原點或原點附近的解，但這并非是算法本身的智能產(chǎn)生的，同時隨著迭代次數(shù)的增加，其跳出原點附近，即局部最優(yōu)的能力并不足夠強。相比之下，F(xiàn)WA-DER 通過改進算子解決了該問題，不易在原點或原點附近尋優(yōu)，而是正常的智能尋優(yōu)，由于動態(tài)調(diào)整了搜索范圍，所以FWADER前期是在整個解空間進行大范圍的全局搜索，隨著迭代次數(shù)逐漸增加，搜索范圍隨之減小，F(xiàn)WA-DER的局部搜索能力逐漸加強，搜索精度因此提高。

4.3.2 偏移測試函數(shù)實驗結(jié)果分析

在偏移實驗下，F(xiàn)WA表現(xiàn)出了糟糕的結(jié)果，因為此時基準測試函數(shù)的最優(yōu)點經(jīng)過了偏移，不再處于原點或原點附近，其映射規(guī)則和高斯變異又不斷產(chǎn)生原點附近的解，反而導(dǎo)致了算法的性能下降。FWA-DER 則不存在這方面的問題，相比FWA表現(xiàn)出更好的效果。

4.3.3 FWA與FWA-DER尋優(yōu)能力分析

FWA的尋優(yōu)范圍是根據(jù)式（1）計算，搜索的上限為A?，每個煙花產(chǎn)生一個相應(yīng)的爆炸范圍，較大的范圍內(nèi)產(chǎn)生少量火花作為全局搜索，較小的范圍內(nèi)產(chǎn)生大量火花作為局部搜索。FWA-DER 使得全局搜索的范圍更大，局部搜索的范圍更小，通過算法1 完成搜索范圍曲線的動態(tài)調(diào)整從而提高全局尋優(yōu)能力和局部尋優(yōu)能力。

5 結(jié)論

基于煙花算法中存在的缺陷，本文結(jié)合增強煙花算法思想提出了一種帶有動態(tài)爆炸半徑算子的增強型煙花算法EFWA-DER。EFWA-DER 改進了基本算子，解決了煙花算法易于原點或原點附近尋優(yōu)的缺陷，也使得算法耗時更少，同時動態(tài)爆炸半徑算子加強算法跳出局部收斂的能力，提升算法搜索精度，整體上提高了算法優(yōu)化性能。實驗表明，本文提出的改進算法在前期收斂速度方面存在不足，有進一步提升的空間。

圖8 函數(shù)偏移實驗結(jié)果

表4 不同偏移指數(shù)下的實驗結(jié)果