帶有自適應合并策略和導向算子的增強型煙花算法

李克文，馬祥博*，候文艷

（1.中國石油大學（華東）計算機科學與技術學院，山東青島 266580；2.中國石油大學（華東）海洋與空間信息學院，山東青島 266580）

0 引言

在中國的傳統(tǒng)文化中，每逢新年人們通常都會燃放大量的煙花來慶祝，眾所周知，好的煙花爆炸時能產(chǎn)生數(shù)量較多，均勻分布和五彩斑斕的火花；相反差的煙花只能產(chǎn)生圖形單一且數(shù)量較少的火花。煙花算法（FireWorks Algorithm，F(xiàn)WA）［1］是由北京大學譚營教授2010 年提出的，是一種模擬煙花爆炸并結(jié)合進化計算的隨機搜索而提出的群智能算法。相較于其他群智能算法，煙花算法具有明顯的自身特點如多樣性、爆炸性等。自煙花算法被提出以來，已經(jīng)吸引了許多學者的研究，相關改進算法不斷被提出，從而使得煙花算法開始廣泛應用于各個領域。但是到目前為止煙花算法仍有一些不足有待改進，例如尋優(yōu)過程中粒子間缺少有效交互［2-5］以及爆炸半徑對搜索范圍的限制［6-9］等。

本文針對以上提到的兩個問題進行深入研究，主要貢獻如下：

1）本文提出了一種帶有自適應合并策略和導向算子的增強型煙花算法（Enhanced FireWork Algorithm with adaptive Merging strategy and Guidance operator，EFWA-GM），相較于傳統(tǒng)煙花算法能夠提高算法的尋優(yōu)精度和收斂速度；

2）在迭代過程中，利用切比雪夫距離度量煙花粒子爆炸范圍之間的位置關系，對尋優(yōu)空間中重疊的爆炸范圍進行自適應合并，提高算法的尋優(yōu)精度；

3）通過將火花粒子劃分為4 個等級，充分利用優(yōu)質(zhì)粒子的位置信息，引入導向算子引導次優(yōu)粒子進化，提高算法的收斂速度；

4）應用不同標準測試函數(shù)的實驗結(jié)果表明本文提出的帶有自適應合并策略和導向算子的增強型煙花算法相較于傳統(tǒng)煙花算法，在尋優(yōu)精度和尋優(yōu)速度方面有更好的優(yōu)化性能。

1 相關工作

自2010 年，Tan 等［1］基于煙花的爆炸結(jié)合進化計算的隨機搜索提出了煙花算法，該算法由于具有較強的優(yōu)化問題求解能力受到研究者的廣泛關注。此后，許多改進算法相繼被提出，該算法便廣泛應用于各個領域。目前，對煙花算法的改進仍存在一些問題有待解決，如尋優(yōu)過程中粒子間缺少有效交互以及爆炸半徑對搜索范圍的限制。

Liu 等［2］針對煙花算法進行了改進，提出了一種新穎的爆炸火花數(shù)量和爆炸幅度的計算方式，設計了一種傳遞函數(shù)將煙花的等級傳遞到火花數(shù)量和爆炸幅度的計算上，并采用一種新穎的隨機變異算子來增加煙花算法的多樣性。Pei 等［3］利用精英選擇策略研究了近似算法對提高煙花算法收斂速度的影響，并通過實驗驗證了可以有效提高煙花算法的收斂能力。Zheng 等［4］詳細地分析了不同自適應煙花算法的改進策略以及效果，并對自適應煙花算法的常見改進策略進行了分析。Yu 等［5］首先分析了不同改進煙花算法的性能，然后提出了動態(tài)搜索煙花算法，引入了指數(shù)遞減的爆炸范圍計算策略從而增強其局部搜索能力。Zheng 等［6］對煙花算法的算子進行了詳細的分析，針對煙花算法的缺點進行了相應的改進，包括爆炸半徑的大小、爆炸火花的產(chǎn)生方式、變異算子、映射規(guī)則和選擇策略，提出了增強型煙花算法（Enhanced FireWorks Algorithm，EFWA）。Yu 等［7］提出了動態(tài)搜索煙花算法（dynamic FireWorks Algorithm，dynFWA），在dynFWA 中將煙花種群分為核心煙花（適應度值最優(yōu)的粒子）和非核心煙花，核心煙花的爆炸半徑根據(jù)動態(tài)搜索策略進行自適應調(diào)整，并且去掉了高斯變異算子使dynFWA 的時間消耗相對較小。Li等［8］提出了自適應煙花算法（Adaptive FireWorks Algorithm，AFWA），將爆炸火花中的最差個體與最優(yōu)個體之間的距離作為下一次迭代的爆炸半徑，在初始階段能夠根據(jù)局部區(qū)域的大小進行調(diào)整，在最后的微調(diào)階段能夠使爆炸半徑逐漸減小從而找到極值點，因此AFWA 表現(xiàn)出了較好的尋優(yōu)性能。Li等［9］在煙花算法中引入了一種導向算子（guided sparks），提出了有導煙花算法（Guided FireWorks Algorithm，GFWA）。

以上改進方法相對傳統(tǒng)煙花算法性能有了較大的提升，但都沒能很好地解決上述兩個問題。本文提出一種帶有自適應合并策略和導向算子的增強型煙花算法，利用自適應合并策略，降低爆炸過程中的半徑限制，并通過導向算子利用優(yōu)質(zhì)粒子的位置信息引導次優(yōu)粒子進化，提高優(yōu)化能力。通過12個標準的測試函數(shù)檢驗了算法的有效性和魯棒性。

2 增強型煙花算法

煙花算法模擬夜空中煙花爆炸的現(xiàn)象，通過初始化N個煙花粒子，經(jīng)過爆炸和變異生成新的火花，并基于歐氏距離從煙花粒子、火花粒子和高斯變異粒子選擇新一代的N個煙花粒子，開始迭代直到滿足問題的精度或者達到最大函數(shù)評估次數(shù)。

增強型煙花算法（EFWA）由Zheng等［6］于2013年提出，針對FWA 的缺陷對各個算子進行了改進，從而提高了算法的尋優(yōu)能力，本文提出的帶有自適應合并策略和導向算子的增強型煙花算法（EFWA-GM）基于EFWA提出。

2.1 小爆炸半徑檢測

EFWA 中引入最小爆炸半徑檢測機制，如果煙花粒子的爆炸半徑小于某一閾值，則將其設置為默認值，如式（1）：

對于如何確定Amin，k，EFWA 提出了非線性遞減策略，如式（2）：

其中：Ainit和Afinal表示迭代過程中的最初和最終的爆炸半徑閾值，t表示當前函數(shù)的評估次數(shù)，evaltimes表示最大函數(shù)評估次數(shù)。

2.2 爆炸火花產(chǎn)生方式

FWA 中煙花爆炸產(chǎn)生火花時在所有維度上的權重是相同的，但是不同維度上相同的權重會降低火花的多樣性，因此EFWA 在每個維度上使用不同的權重值。此外，在FWA 中當一個爆炸或者高斯變異產(chǎn)生的火花在維度k上超出邊界，會通過式（3）的映射規(guī)則將花火映射到邊界內(nèi)區(qū)域，即FWA 中煙花爆炸產(chǎn)生火花時在所有維度上的權重是相同的，但是不同維度上相同的權重會降低火花的多樣性，因此EFWA 在每個維度上使用不同的權重值。此外，在FWA 中當一個爆炸或者高斯變異產(chǎn)生的火花在維度k上超出邊界，會通過式（3）的映射規(guī)則將花火映射到邊界內(nèi)區(qū)域，即：

其中：XLB，k、XUB，k為解空間在維度k上的下邊界和上邊界。在這種情況下，在維度k上超出邊界的火花會被映射到距離原點較近的位置。為了解決這一問題，EFWA 使用式（4）來處理超出邊界的火花：

其中：XUB，k、XLB，k為可行域在維度k的上邊界和下邊界，U（0，1）表示在區(qū)間（0，1）的均勻分布。

2.3 高斯變異算子

為避免FWA 中高斯變異花火的缺陷，在EFWA 中使用一種新型高斯變異算子，計算公式為：

其中：XBk表示當前種群中適應度值最優(yōu)的煙花粒子的第k個維度，g～N（0，1）。

3 帶有自適應合并策略和導向算子的增強型煙花算法

當煙花粒子爆炸產(chǎn)生火花時，火花粒子的位置及適應度值包含了大量的尋優(yōu)信息［10］，但是傳統(tǒng)的煙花算法并沒有充分利用這些信息來指導煙花粒子的尋優(yōu)過程，同時煙花粒子的爆炸半徑限制了火花粒子的搜索范圍，導致收斂速度變慢、尋優(yōu)精度降低。本文針對這兩個問題提出了帶有自適應合并策略和導向算子的增強型煙花算法。

3.1 自適應合并策略

傳統(tǒng)煙花算法特殊的爆炸機制將火花粒子的搜索范圍限制在煙花粒子的爆炸半徑之內(nèi)，若兩個煙花粒子的距離較近，煙火粒子的爆炸范圍很可能相交，如圖1（a）所示。本文中認為，經(jīng)過煙花粒子的多輪爆炸和重新選擇，兩個煙花粒子爆炸范圍相交能夠表明當前決策區(qū)域較大可能存在優(yōu)質(zhì)解［11-12］。那么，當前迭代輪次，區(qū)域A 作為相交區(qū)域的鄰近區(qū)域，應當具有與區(qū)域B、C 相同的概率產(chǎn)生優(yōu)質(zhì)解，即區(qū)域A、B、C 獲得搜索的地位是相同的，同時本文實驗結(jié)果也證明對相交區(qū)域的鄰近區(qū)域的搜索是高回報的，但是傳統(tǒng)煙花算法中區(qū)域A、B、C 的獲得搜索的地位是不相等，這導致優(yōu)化精度和收斂速度的降低。針對此問題，本文提出了自適應合并策略，當煙花粒子的爆炸邊界相交時，通過合并煙火粒子的爆炸范圍來使區(qū)域A、B、C 獲得相同的搜索地位，以提高算法的優(yōu)化性能，如圖1（b）所示。通過自適應合并策略，煙火粒子在新的爆炸范圍以相同的概率產(chǎn)生火花粒子，如圖1（c）所示。

圖1 自適應合并策略示意圖Fig.1 Schematic diagram of adaptive merging strategy

考慮煙花粒子間的距離，本文認為當煙花粒子的所有維度距離都較近時，才認為兩個煙花粒子距離相近或相交，這樣能夠避免不必要的爆炸范圍合并，提高算法的收斂速度，因此本文中選擇切比雪夫距離［13］作為自適應合并策略的距離度量，計算公式如下：

其中：Di，j表示煙火粒子i和j的切比雪夫距離，Xi、Xj表示煙火粒子i、j的位置。

自適應合并策略通過重新計算煙花粒子的爆炸范圍，在新的爆炸范圍內(nèi)產(chǎn)生火花粒子進行搜索，如式（7）～（8）所示：

其中：Ai、Aj分別表示煙花粒子i、j的爆炸范圍，Amax表示最大爆炸范圍表示新確定的爆炸范圍。

自適應合并策略具體的實現(xiàn)方法如算法1所示。

算法1 自適應合并策略。

3.2 導向算子

在增強型煙花算法中，由于尋優(yōu)過程中煙花粒子間缺少有效的信息交互，限制了普通粒子的搜索能力。本文提出一種利用導向算子來緩解這一問題，將適應度值最優(yōu)的三個粒子分別定義為L1、L2和L3，通過L1、L2、L3指導其他次優(yōu)粒子向著目標最優(yōu)解搜索，其余的粒子被定義為L4，它們圍繞著L1、L2或L3更新自己的位置?；鸹Ｗ拥牡燃壢鐖D2所示。

圖2 火花粒子的等級Fig.2 Levels of spark particles

在優(yōu)化問題的決策空間中，對最優(yōu)解的位置并不了解，因此適應度值較優(yōu)的L1、L2 和L3 粒子更了解最優(yōu)解的潛在位置［9］。本文通過引入一個導向算子，利用優(yōu)質(zhì)煙花粒子的位置來預測目標最優(yōu)解的潛在位置，同時引導次優(yōu)粒子更新其位置逐漸逼近目標最優(yōu)解。導向算子引導煙花粒子更新位置的示意圖如圖3所示。

圖3 導向算子引導煙花粒子更新位置的機制Fig.3 Mechanism of guidance operator guiding fireworks particles to update their positions

如圖3中，L4等級的火花粒子基于與L1、L2、L3等級粒子之間的距離向量DL1、DL2、DL3，計算L4 等級粒子的位置更新方向和步長，L′4表示位置更新后的粒子，距離向量DL1、DL2和DL3的計算公式如式（9）所示：

其中，DL1、DL2和DL3分別表示L1、L2 和L3 煙花粒子與其他粒子間的距離，XL1、XL2、XL3分別表示L1、L2和L3煙花粒子的當前位置，X表示當前粒子的位置，C1、C2、C3是隨機向量。

式（10）分別定義了煙花種群中L4 等級的個體向高等級的L1、L2和L3前進的步長和方向，式（11）定義了L4個體經(jīng)導向算子調(diào)整后的最終位置，其中A和C是系數(shù)向量，A和C的計算公式如下：

其中：a是收斂因子，隨著函數(shù)評估次數(shù)從2 線性遞減到0，r1和r2取［0，1］區(qū)間的隨機數(shù)。

3.3 隨機變異算子

由于EFWA采用的高斯變異算子是在當前粒子位置和坐標原點之間產(chǎn)生變異火花，容易將火花變異到原點附近的位置，導致EFWA算法易于求解原點附近的最優(yōu)值，而對于遠離原點的最優(yōu)值則表現(xiàn)出較差的優(yōu)化性能，故將高斯變異算子改為隨機變異，公式如下

其中：XB，j、XW，j分別表示當前煙花種群中適應度值最低、最高的煙花在第j維度上的位置，Xi，j表示第i個粒子在第j維度上的位置，rand（0，1）表示在區(qū)間［0，1］區(qū)間均勻分布的隨機數(shù)。

3.4 EFWA-GM流程

算法2 EFWA-GM。

步驟1 對N、FWmax、dim、a、b、Amax、maxEva等參數(shù)進行初始化，N為初始煙花個數(shù)，F(xiàn)Wmax為種群中最大粒子數(shù)量，dim為測試函數(shù)的維度，a、b為給定的常數(shù)用來限制爆炸火花的數(shù)量和范圍，Amax為最大爆炸范圍的閾值、maxEva為最大函數(shù)評估次數(shù)；

步驟2 根據(jù)EFWA 中爆炸火花的范圍和數(shù)量計算公式計算t=1時每個煙花的爆炸半徑和火花數(shù)量；

步驟3 根據(jù)式（6）～（8）對煙花粒子的爆炸范圍進行合并，并按照式（4）結(jié)合新的爆炸范圍產(chǎn)生火花粒子；

步驟4 根據(jù)式（9）～（13）計算導向算子并引導L4等級粒子進行位置更新；

步驟5 根據(jù)式（14）產(chǎn)生變異火花，并由EFWA 的選擇策略選擇下一代煙花種群；

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

采用自適應合并策略，EFWA-GM 一定程度上能夠緩解隨機搜索受限于爆炸半徑的問題，提高算法的收斂速度；引入導向算子，能夠增強煙花粒子間的信息交互，提高種群的全局搜索能力；采用隨機搜索算子能夠提高最優(yōu)值遠離原點的測試函數(shù)的優(yōu)化性能。

4 實驗分析

4.1 小爆炸半徑檢測

為檢驗本文提出的EFWA-GM 在尋優(yōu)精度、收斂速度方面的性能，選擇12 個標準測試函數(shù)進行測試分析，比較EFWA-GM、標準粒子群優(yōu)化（Standard Particle Swarm Optimization，SPSO）算法、增強型煙花算法以及較先進的自適應煙花算法、動態(tài)自適應煙花算法、導向煙花算法的優(yōu)化性能，表1給出了標準測試函數(shù)表達式、最優(yōu)值、搜索維度。

表1 標準測試函數(shù)Tab.1 Benchmark functions

本文實驗平臺是Python3.6.7（Centos7；Intel Core i5-8300H CPU 2.3 GHz；16 GB RAM）。對于每一個測試函數(shù)，EFWA 參數(shù)的設定參考文獻［8］，具體如下：初始煙花數(shù)目N=5，高斯變異煙花數(shù)目p=5，最大種群數(shù)目FWmax=50，a=0.04，b=0.8，最大爆炸幅度Amax=40；EFWA-GM 和EFWA 參數(shù)設定相同；AFWA 參數(shù)的設定參考文獻［10］，其中最大種群數(shù)目FWmax=100，最大爆炸幅度Amax=100，參數(shù)λ=1.3，其余參數(shù)設置與EFWA 相同；文獻［14］和文獻［15］出了SPSO 的實驗結(jié)果。實驗中EFWA、AFWA和EFWA-GM設置最大函數(shù)評估次數(shù)為300 000，PSO 設置最大迭代次數(shù)為2 000，每個測試函數(shù)獨立運行30次。

4.2 實驗結(jié)果

4.2.1 搜索精度分析

表2 列出了EFWA-GM、SPSO、EFWA、AFWA、dynFWA、GFWA 在12 個標準測試函數(shù)上的實驗結(jié)果，并統(tǒng)計了6 種算法在12 個測試函數(shù)上的均值和方差，加粗數(shù)據(jù)為最優(yōu)值。由表2 中數(shù)據(jù)可以得知：SPSO 的搜索精度最差且魯棒性較低，AFWA 在Schwefel、Zakharov 兩個測試函數(shù)上搜索精度取得最優(yōu)，dynFWA 和GFWA 在Sphere 測試函數(shù)上取得最優(yōu)，EFWAGM 在其余9個測試函數(shù)上取的最優(yōu)值；并且不同維度的測試函數(shù)結(jié)果可見EFWA-GM 的表現(xiàn)也要優(yōu)于其余算法。綜合可得EFWA-GM 在極值函數(shù)的尋優(yōu)精度方面要優(yōu)于其他的5 種算法；而且，根據(jù)方差也可以發(fā)現(xiàn)，EFWA-GM 比其他3種算法表現(xiàn)更加穩(wěn)定。

表2 實驗結(jié)果對比Tab.2 Comparison of experimental results

4.2.2 收斂速度分析

為了比較EFWA-GM、EFWA和AFWA在收斂速度方面的表現(xiàn)，本文針對表1中的12個標準測試函數(shù)，以函數(shù)評估次數(shù)為橫軸，以最優(yōu)適應度值作為縱軸來描述算法的優(yōu)化軌跡。如圖4 所示，EFWA-GM 在Sphere、Rastrigrin、Griewank、Cigar、Ellipse、Ackley 測試函數(shù)上收斂速度明顯優(yōu)于EFWA 和AFWA，在其余6 個測試函數(shù)上收斂速度基本持平，由此可見EFWA-GM 的收斂速度要優(yōu)于EFWA 和AFWA。這表明EFWA-GM 在收斂速度上比EFWA 和AFWA 有所加強，更加有利于解決復雜的優(yōu)化問題。

圖4 標準測試函數(shù)的進化曲線Fig.4 Evolution curves of benchmark functions

由此可見，EFWA-GM 無論在尋優(yōu)精度還是在收斂速度方面均有較優(yōu)的表現(xiàn)。這樣的結(jié)果主要得益于兩方面：一方面引入導向算子增加了煙花粒子間的有效交互，提高了粒子的搜索能力；另一方面采用自適應半徑搜索策略，一定程度上降低了爆炸半徑對搜索范圍的限制，提高了算法的收斂速度，此外采用隨機變異算子替代高斯變異解決了對最優(yōu)值遠離原點的測試函數(shù)表現(xiàn)較差的問題。

5 結(jié)語

本文針對增強型煙花算法粒子間缺少有效交互以及在搜索過程中受爆炸半徑影響限制搜索范圍的問題，提出一種帶有自適應合并策略和導向算子的增強型煙花算法。該算法采用自適應合并策略，根據(jù)煙花粒子間距離對爆炸范圍進行自適應合并，從而保證對相交區(qū)域鄰近區(qū)域均等的搜索，提高算法的收斂速度；通過引入導向算子，將煙花種群劃分為4 個等級，利用優(yōu)質(zhì)粒子的位置信息引導次優(yōu)粒子向全局最優(yōu)解靠近，提高算法的優(yōu)化性能。實驗表明本文提出的EFWA-GM在尋優(yōu)精度和收斂速度方面均有較好的表現(xiàn)。