郭京蕾,趙孝豪,郭亞軍
(華中師范大學(xué)計(jì)算機(jī)學(xué)院,湖北 武漢 430079)
優(yōu)化問題廣泛存在于生產(chǎn)、生活等實(shí)際應(yīng)用問題中,即在有限的時(shí)間內(nèi)找到滿足特征和要求的最優(yōu)或較優(yōu)解決方案。煙花算法FWA(FireWorks Algorithm )[1]自提出以來(lái),已經(jīng)證明了其在處理優(yōu)化問題方面的效率。因其優(yōu)越的特性而受到不同領(lǐng)域科研工作者的關(guān)注,并在工程領(lǐng)域取得了廣泛應(yīng)用。
目前,煙花算法的研究工作主要集中在以下3個(gè)方面:(1)對(duì)煙花算法中的算子進(jìn)行改進(jìn)。Li等[2]提出只保留爆炸操作的骨架煙花算法,該算法具有簡(jiǎn)單易行、參數(shù)少等優(yōu)點(diǎn)。Yu等[3]提出具有突變的動(dòng)態(tài)煙花算法dynFWACM(dynamic FireWorks Algorithm with Covariance Mutation),引入?yún)f(xié)方差變異算子,利用較好火花的信息,計(jì)算平均值和協(xié)方差矩陣,產(chǎn)生具有良好分布特性的變異火花,增強(qiáng)了局部搜索能力。Zheng等[4]提出了一種基于煙花算法的合作框架CoFFWA(Cooperative Framework for FireWorks Algorithm),提出了避免擁擠的合作策略增加全局開采能力,在CEC2013測(cè)試集上CoFFWA表現(xiàn)出良好性能。(2)將FWA與其他群智能算法融合生成混合型煙花算法。Tan等[5]提出在煙花算法中,加入圖形圖像處理器GPU技術(shù)加快優(yōu)化過程,縮短算法運(yùn)行時(shí)間。Zhang等[6]將生物地理學(xué)優(yōu)化方法BBO(Biogeography-Based Optimization)的遷移操作引入到FWA中,以增強(qiáng)種群之間的信息共享,從而改善解決方案的多樣性以避免過早收斂。Ma等[7]提出了一種基于小波支持向量機(jī)w-SVM(wavelet Support Vector Machine)和量子煙花QFWA(Quantum FireWorks Algorithm)的混合算法的預(yù)測(cè)組合模型。(3)應(yīng)用FWA解決工業(yè)生產(chǎn)中的實(shí)際問題。Tuba等[8]提出利用煙花算法提取二維視網(wǎng)膜圖像配準(zhǔn)的剛性變換最佳參數(shù)。Bacanin等[9]提出將帶約束的煙花算法用于解決投資組合優(yōu)化問題。Babu等[10]提出一種提取光伏模塊雙二極管模型未知參數(shù)的煙花算法。
標(biāo)準(zhǔn)煙花算法將在第2節(jié)進(jìn)行論述,第3節(jié)論述差分變異算子的構(gòu)造、動(dòng)態(tài)爆炸火花策略,提出差分變異算子的煙花算法DEFWA(FireWorks Algorithm with Differential mutant operator),第4節(jié)進(jìn)行了實(shí)驗(yàn)結(jié)果的分析和比較,最后進(jìn)行總結(jié)。
為了不失一般性,優(yōu)化問題可以定義為式(1)所示:
Minimizef(X)∈R,Xmin≤X≤Xmax
(1)
其中,X=[x1,x2,…,xD]表示煙花在搜索空間中的位置,D表示搜索空間的維數(shù),f(X)表示該位置所對(duì)應(yīng)的目標(biāo)函數(shù),Xmin和Xmax表示可行域空間的搜索邊界。
煙花算法模擬煙花的爆炸過程,屬于群體隨機(jī)搜索算法,主要包含爆炸算子、高斯火花算子和選擇算子。
煙花算法的每個(gè)煙花根據(jù)其適應(yīng)值不同,產(chǎn)生的火花數(shù)目不同,第i個(gè)煙花產(chǎn)生的爆炸火花數(shù)目si如式(2)所示:
(2)
其中,Xi為第i個(gè)煙花的位置,m表示爆炸火花總數(shù),ymax=max(f(Xi)),i=1,2,…,n,表示n個(gè)煙花中的最大適應(yīng)值,ε表示較小的正常數(shù)。
從式(2)可看出,為了平衡全局探索能力和局部開發(fā)能力,種群中具有較小適應(yīng)值的煙花比具有較大適應(yīng)度值的煙花能產(chǎn)生更多的火花。為了避免算法的早熟收斂,需要防止適應(yīng)值較優(yōu)煙花產(chǎn)生過多的火花,而質(zhì)量較差的煙花產(chǎn)生較少甚至不能產(chǎn)生火花。故定義爆炸火花數(shù)目si如式(3)所示。
(3)
其中,a和b表示限制種群大小范圍的常數(shù)參數(shù)(a
在種群中具有較小適應(yīng)度值的煙花比具有較大適應(yīng)度值的煙花具有更小的爆炸幅度。所以定義每個(gè)煙花的爆炸幅度Ai如式(4)所示:
(4)
算法1爆炸算子
z=round(D·rand(0,1));
計(jì)算爆炸幅度Ai并計(jì)算h:h=Ai·rand(-1,1);
end if
end for
算法2高斯變異算子
z=round(D·rand(0,1));
計(jì)算高斯爆炸系數(shù):e=Gaussian(1,1);
end if
end for
R(Xi)=∑j∈Qd(Xi,Xj)=∑j∈Q‖Xi-Xj‖
(5)
其中,Q表示煙花和火花所有當(dāng)前位置的集合。
個(gè)體的選擇概率如式(6)所示:
(6)
在計(jì)算距離時(shí),可以使用包括歐幾里德距離、曼哈頓距離、基于角度的距離等距離測(cè)量方法進(jìn)行測(cè)量,在傳統(tǒng)煙花算法中采用的是歐幾里德距離。
在傳統(tǒng)的DE(Differential Evolution)差分算子中:“best/1”“current-to-best/1”“best/2”能夠加速向最優(yōu)值附近收斂;“rand/1”“rand/2”能夠增加種群多樣性。為了有效平衡全局搜索能力和收斂速度,本文采用“current-to-rand/1”變異算子,如式(7)所示:
(7)
通過二項(xiàng)式雜交方法,如式(8)所示,生成差分變異火花。
(8)
其中,k=1,2,…,D,krand是分布在[1,D]的隨機(jī)數(shù),CR為雜交概率。
算法3“current-to-rand/1”差分變異算子
按式(7)生成V;
fork=1 toDdo
end if
end for
利用“current-to-rand/1”差分變異算子取代煙花算法的高斯變異算子,可通過成對(duì)的差分向量信息,有效地將群體中多個(gè)個(gè)體信息與當(dāng)前粒子結(jié)合,增強(qiáng)種群的多樣性。
(9)
算法4DEFWA算法
隨機(jī)初始化n個(gè)煙花并評(píng)價(jià)適應(yīng)值;
while stop criteria等于false do
for 每一個(gè)煙花的位置Xido
根據(jù)式(2)和式(4)計(jì)算每一個(gè)煙花的火花數(shù)si和爆炸范圍Ai;
根據(jù)算法1產(chǎn)生爆炸火花;
end for
隨機(jī)選擇一個(gè)煙花Xi;
根據(jù)算法3產(chǎn)生差分變異火花;
end for
評(píng)價(jià)爆炸火花和差分變異火花;
選出最優(yōu)個(gè)體,保存到下一代;
根據(jù)式(9)設(shè)置最優(yōu)煙花的爆炸個(gè)數(shù);
根據(jù)式(6)從煙花和火花中選擇其他n-1個(gè)個(gè)體保存到下一代;
end while
選取文獻(xiàn)[13]的12個(gè)函數(shù)作為測(cè)試集,其中包括單峰函數(shù)、多峰函數(shù)等多種類型,表1列出了測(cè)試函數(shù)的序號(hào)、名稱、維數(shù)、搜索范圍、最優(yōu)位置和最優(yōu)值。
各函數(shù)將在每個(gè)維度中產(chǎn)生移位,移位量大小為0.7*(Xmax-Xmin)/2。
在算法中,爆炸火花的個(gè)數(shù)將影響到算法的勘探與開采能力,因此將DEFWA爆炸火花總數(shù)m分別設(shè)置為25,50,75,100,a=0.04,b=0.8,即smin=a·m,smax=b·m。DEFWA算法在表1的12個(gè)30維測(cè)試函數(shù)上獨(dú)立運(yùn)行30次,得到的平均值與方差如表2所示。
Table 1 Test functions表1 測(cè)試函數(shù)
從表2可看出,當(dāng)m=50時(shí),相比其他3種取值,在12個(gè)函數(shù)上均取得了最好均值。在后續(xù)的實(shí)驗(yàn)中將爆炸火花數(shù)設(shè)置為50。
將DEFWA算法與FWA[1]和3種經(jīng)典改進(jìn)型煙花算法(EFWA[12]、dynFWA[13]、GFWA(Guided FireWorks Algorithm)[14])在表1的12個(gè)30維測(cè)試函數(shù)上,獨(dú)立運(yùn)行30次,迭代次數(shù)為3.0*105,得到的平均值與方差如表3所示。在實(shí)驗(yàn)中DEFWA參數(shù)設(shè)置如下:煙花個(gè)數(shù)為5,爆炸火花數(shù)m=50,差分變異火花數(shù)為5,雜交概率CR在集合{0.1,0.2,1.0}中隨機(jī)取值,F(xiàn)在集合{0.6,0.8,1.0}中隨機(jī)取值。
在12個(gè)測(cè)試問題中,F(xiàn)WA算法在函數(shù)f8、f9上取得了最優(yōu)均值,EFWA算法在函數(shù)f8、f9、f10上取得了最優(yōu)均值,dynFWA算法在9個(gè)函數(shù)(f1、f2、f3、f4、f8、f9、f10、f11、f12)上取得了最優(yōu)均值,GFWA算法在函數(shù)f6、f8上取得了最優(yōu)均值,DEFWA算法在9個(gè)函數(shù)(f1、f2、f5、f7、f8、f9、f10、f11、f12)上取得了最優(yōu)均值。根據(jù)表3的實(shí)驗(yàn)結(jié)果,對(duì)算法進(jìn)行了Friedman檢驗(yàn),結(jié)果如表4所示。
Table 2 Experiment result of the different number on explosion sparks表2 爆炸火花數(shù)實(shí)驗(yàn)結(jié)果
Table 3 Experiment results of FWA, EFWA, dynFWA, GFWA and DEFWA表3 FWA、EFWA、dynFWA、GFWA、DEFWA算法實(shí)驗(yàn)結(jié)果
DEFWA、FWA、EFWA、dynFWA、GFWA在函數(shù)f1、f3、f5、f7、f9、f11上的收斂曲線如圖1所示。
Table 4 Friedman testing result表4 Friedman檢驗(yàn)結(jié)果
Figure 1 Convergence curve of algorithms圖1 算法收斂曲線圖
圖1中,在函數(shù)f1上僅有FWA未搜索到全局最優(yōu)值,DEFWA和dynFWA的收斂過程相似,但在整個(gè)過程中DEFWA的收斂速度快,GFWA在搜索早期收斂速度較快,但中后期明顯減慢。在函數(shù)f3的收斂圖中,DEFWA搜索到了最小值,其它幾種對(duì)比算法都未能達(dá)到。在函數(shù)f5中,依舊只有DEFWA搜索到了最小值,其它4種對(duì)比算法均出現(xiàn)了后期收斂性能不足的缺點(diǎn)。在函數(shù)f7收斂圖中,DEFWA搜索到了最小值,其它4種對(duì)比算法也同樣出現(xiàn)后期收斂性能不足的弊端,同時(shí)dynFWA陷入了局部最優(yōu)。在函數(shù)f9收斂圖中,DEFWA和其他4種對(duì)比算法均能在搜索早期較快地收斂。在函數(shù)f11收斂圖中,DEFWA后期收斂速度快并且搜索到最小值,dynFWA性能次之,其中GFWA在搜索初期明顯好于其他算法,但搜索的后期則陷入局部最優(yōu)。
本文將差分變異算子和動(dòng)態(tài)爆炸火花策略加入了煙花算法中,為了增強(qiáng)種群的多樣性提出了差分變異算子的DEFWA算法,為了加快收斂速度,對(duì)最佳煙花采用了動(dòng)態(tài)火花爆炸策略。在標(biāo)準(zhǔn)測(cè)試集上,將DEFWA算法與FWA和3個(gè)改進(jìn)型的FWA(EFWA、dynFWA、GFWA)進(jìn)行了實(shí)驗(yàn)對(duì)比,結(jié)果表明DEFWA在尋優(yōu)的精度和速度方面優(yōu)于對(duì)比算法。