基于差分變異算子的煙花算法*

郭京蕾,趙孝豪,郭亞軍

(華中師范大學計算機學院，湖北 武漢 430079)

1 引言

優化問題廣泛存在于生產、生活等實際應用問題中，即在有限的時間內找到滿足特征和要求的最優或較優解決方案。煙花算法FWA(FireWorks Algorithm )[1]自提出以來，已經證明了其在處理優化問題方面的效率。因其優越的特性而受到不同領域科研工作者的關注，并在工程領域取得了廣泛應用。

目前，煙花算法的研究工作主要集中在以下3個方面：(1)對煙花算法中的算子進行改進。Li等[2]提出只保留爆炸操作的骨架煙花算法，該算法具有簡單易行、參數少等優點。Yu等[3]提出具有突變的動態煙花算法dynFWACM(dynamic FireWorks Algorithm with Covariance Mutation)，引入協方差變異算子，利用較好火花的信息，計算平均值和協方差矩陣，產生具有良好分布特性的變異火花，增強了局部搜索能力。Zheng等[4]提出了一種基于煙花算法的合作框架CoFFWA(Cooperative Framework for FireWorks Algorithm),提出了避免擁擠的合作策略增加全局開采能力，在CEC2013測試集上CoFFWA表現出良好性能。(2)將FWA與其他群智能算法融合生成混合型煙花算法。Tan等[5]提出在煙花算法中，加入圖形圖像處理器GPU技術加快優化過程，縮短算法運行時間。Zhang等[6]將生物地理學優化方法BBO(Biogeography-Based Optimization)的遷移操作引入到FWA中，以增強種群之間的信息共享，從而改善解決方案的多樣性以避免過早收斂。Ma等[7]提出了一種基于小波支持向量機w-SVM(wavelet Support Vector Machine)和量子煙花QFWA(Quantum FireWorks Algorithm)的混合算法的預測組合模型。(3)應用FWA解決工業生產中的實際問題。Tuba等[8]提出利用煙花算法提取二維視網膜圖像配準的剛性變換最佳參數。Bacanin等[9]提出將帶約束的煙花算法用于解決投資組合優化問題。Babu等[10]提出一種提取光伏模塊雙二極管模型未知參數的煙花算法。

標準煙花算法將在第2節進行論述，第3節論述差分變異算子的構造、動態爆炸火花策略，提出差分變異算子的煙花算法DEFWA(FireWorks Algorithm with Differential mutant operator)，第4節進行了實驗結果的分析和比較，最后進行總結。

2 標準煙花算法

為了不失一般性，優化問題可以定義為式(1)所示：

Minimizef(X)∈R,Xmin≤X≤Xmax

(1)

其中，X=[x1,x2,…,xD]表示煙花在搜索空間中的位置，D表示搜索空間的維數，f(X)表示該位置所對應的目標函數，Xmin和Xmax表示可行域空間的搜索邊界。

煙花算法模擬煙花的爆炸過程，屬于群體隨機搜索算法，主要包含爆炸算子、高斯火花算子和選擇算子。

2.1 爆炸算子

煙花算法的每個煙花根據其適應值不同，產生的火花數目不同，第i個煙花產生的爆炸火花數目si如式(2)所示：

(2)

其中，Xi為第i個煙花的位置，m表示爆炸火花總數，ymax=max(f(Xi)),i=1,2,…,n,表示n個煙花中的最大適應值，ε表示較小的正常數。

從式(2)可看出,為了平衡全局探索能力和局部開發能力，種群中具有較小適應值的煙花比具有較大適應度值的煙花能產生更多的火花。為了避免算法的早熟收斂，需要防止適應值較優煙花產生過多的火花，而質量較差的煙花產生較少甚至不能產生火花。故定義爆炸火花數目si如式(3)所示。

(3)

其中，a和b表示限制種群大小范圍的常數參數(a

在種群中具有較小適應度值的煙花比具有較大適應度值的煙花具有更小的爆炸幅度。所以定義每個煙花的爆炸幅度Ai如式(4)所示:

(4)

算法1爆炸算子

z=round(D·rand(0,1));

計算爆炸幅度Ai并計算h:h=Ai·rand(-1,1);

end if

end for

2.2 高斯變異算子

算法2高斯變異算子

z=round(D·rand(0,1));

計算高斯爆炸系數：e=Gaussian(1,1);

end if

end for

2.3 選擇算子

R(Xi)=∑j∈Qd(Xi,Xj)=∑j∈Q‖Xi-Xj‖

(5)

其中，Q表示煙花和火花所有當前位置的集合。

個體的選擇概率如式(6)所示：

(6)

在計算距離時，可以使用包括歐幾里德距離、曼哈頓距離、基于角度的距離等距離測量方法進行測量，在傳統煙花算法中采用的是歐幾里德距離。

3 差分變異算子的煙花算法(DEFWA)

3.1 差分變異算子

在傳統的DE(Differential Evolution)差分算子中：“best/1”“current-to-best/1”“best/2”能夠加速向最優值附近收斂；“rand/1”“rand/2”能夠增加種群多樣性。為了有效平衡全局搜索能力和收斂速度，本文采用“current-to-rand/1”變異算子，如式(7)所示：

(7)

通過二項式雜交方法，如式(8)所示,生成差分變異火花。

(8)

其中，k=1,2,…,D,krand是分布在[1,D]的隨機數,CR為雜交概率。

算法3“current-to-rand/1”差分變異算子

按式(7)生成V；

fork=1 toDdo

end if

end for

利用“current-to-rand/1”差分變異算子取代煙花算法的高斯變異算子，可通過成對的差分向量信息，有效地將群體中多個個體信息與當前粒子結合，增強種群的多樣性。

3.2 動態爆炸火花策略

(9)

3.3 DEFWA算法流程

算法4DEFWA算法

隨機初始化n個煙花并評價適應值;

while stop criteria等于false do

for 每一個煙花的位置Xido

根據式(2)和式(4)計算每一個煙花的火花數si和爆炸范圍Ai;

根據算法1產生爆炸火花;

end for

隨機選擇一個煙花Xi;

根據算法3產生差分變異火花;

end for

評價爆炸火花和差分變異火花;

選出最優個體，保存到下一代；

根據式(9)設置最優煙花的爆炸個數；

根據式(6)從煙花和火花中選擇其他n-1個個體保存到下一代;

end while

4 差分變異的混合煙花算法

4.1 測試函數

選取文獻[13]的12個函數作為測試集，其中包括單峰函數、多峰函數等多種類型，表1列出了測試函數的序號、名稱、維數、搜索范圍、最優位置和最優值。

各函數將在每個維度中產生移位，移位量大小為0.7*(Xmax-Xmin)/2。

4.2 爆炸火花個數參數選取

在算法中，爆炸火花的個數將影響到算法的勘探與開采能力，因此將DEFWA爆炸火花總數m分別設置為25,50,75,100，a=0.04,b=0.8,即smin=a·m，smax=b·m。DEFWA算法在表1的12個30維測試函數上獨立運行30次，得到的平均值與方差如表2所示。

Table 1 Test functions表1 測試函數

從表2可看出，當m=50時，相比其他3種取值，在12個函數上均取得了最好均值。在后續的實驗中將爆炸火花數設置為50。

4.3 算法對比

將DEFWA算法與FWA[1]和3種經典改進型煙花算法(EFWA[12]、dynFWA[13]、GFWA(Guided FireWorks Algorithm)[14])在表1的12個30維測試函數上，獨立運行30次，迭代次數為3.0*105，得到的平均值與方差如表3所示。在實驗中DEFWA參數設置如下：煙花個數為5，爆炸火花數m=50，差分變異火花數為5，雜交概率CR在集合{0.1,0.2,1.0}中隨機取值，F在集合{0.6,0.8,1.0}中隨機取值。

在12個測試問題中，FWA算法在函數f8、f9上取得了最優均值，EFWA算法在函數f8、f9、f10上取得了最優均值，dynFWA算法在9個函數(f1、f2、f3、f4、f8、f9、f10、f11、f12)上取得了最優均值，GFWA算法在函數f6、f8上取得了最優均值，DEFWA算法在9個函數(f1、f2、f5、f7、f8、f9、f10、f11、f12)上取得了最優均值。根據表3的實驗結果，對算法進行了Friedman檢驗，結果如表4所示。

Table 2 Experiment result of the different number on explosion sparks表2 爆炸火花數實驗結果

Table 3 Experiment results of FWA, EFWA, dynFWA, GFWA and DEFWA表3 FWA、EFWA、dynFWA、GFWA、DEFWA算法實驗結果

DEFWA、FWA、EFWA、dynFWA、GFWA在函數f1、f3、f5、f7、f9、f11上的收斂曲線如圖1所示。

Table 4 Friedman testing result表4 Friedman檢驗結果

Figure 1 Convergence curve of algorithms圖1 算法收斂曲線圖

圖1中，在函數f1上僅有FWA未搜索到全局最優值，DEFWA和dynFWA的收斂過程相似，但在整個過程中DEFWA的收斂速度快，GFWA在搜索早期收斂速度較快，但中后期明顯減慢。在函數f3的收斂圖中，DEFWA搜索到了最小值，其它幾種對比算法都未能達到。在函數f5中，依舊只有DEFWA搜索到了最小值，其它4種對比算法均出現了后期收斂性能不足的缺點。在函數f7收斂圖中，DEFWA搜索到了最小值，其它4種對比算法也同樣出現后期收斂性能不足的弊端，同時dynFWA陷入了局部最優。在函數f9收斂圖中，DEFWA和其他4種對比算法均能在搜索早期較快地收斂。在函數f11收斂圖中，DEFWA后期收斂速度快并且搜索到最小值，dynFWA性能次之，其中GFWA在搜索初期明顯好于其他算法，但搜索的后期則陷入局部最優。

5 結束語

本文將差分變異算子和動態爆炸火花策略加入了煙花算法中，為了增強種群的多樣性提出了差分變異算子的DEFWA算法，為了加快收斂速度，對最佳煙花采用了動態火花爆炸策略。在標準測試集上，將DEFWA算法與FWA和3個改進型的FWA(EFWA、dynFWA、GFWA)進行了實驗對比，結果表明DEFWA在尋優的精度和速度方面優于對比算法。