煙花算法中爆炸半徑的改進研究

摘 要： 煙花算法是最近出現(xiàn)的一種優(yōu)化算法，分析了算法中一個關(guān)鍵參數(shù)即爆炸半徑。分析表明，由最優(yōu)煙花所產(chǎn)生的火花由于其爆炸半徑趨于0，所以在計算中幾乎是無用的，而且增加了計算代價。為此，給出了一個改進的爆炸半徑的算法，實驗表明，改進算法在收斂速度和精度方面都優(yōu)于原始算法。

關(guān)鍵詞： 煙花算法； 爆炸半徑； 群體智能； 優(yōu)化算法

中圖分類號：TP301.6 文獻標(biāo)志碼：A 文章編號：1006-8228（2013）01-28-02

Study on improvement of explosion radius in fireworks algorithm

Du Zhenxin

（Hanshan Normal University， chaozhou， Guangdong 521041， China）

Abstract： Fireworks algorithm is a new optimization algorithm. The fireworks algorithm is analyzed and the shortage of the crucial parameter explosion radius is pointed out. The analysis manifests that because their explosion radius tends to zero， the sparks produced by the best firework are useless and the computing process is wasted. An improved explosion radius formula is proposed in the paper， and experimental results show that the improved algorithm's performance is better than the original one in convergence velocity and accuracy.

Key words： fireworks algorithm； explosion radius； swarm intelligence； optimization algorithm

0 引言

煙花算法是由Ying Tan和Yuanchun Zhu[1]在2010年提出的一種新的群體智能優(yōu)化算法，具有卓越的優(yōu)化性能，因此一經(jīng)提出就引起了世界范圍內(nèi)的廣泛關(guān)注[2-3]。本文分析了煙花算法中一個重要的爆炸半徑公式，指出最優(yōu)煙花所產(chǎn)生的火花由于爆炸半徑趨向于0，對算法搜索沒有貢獻，白白浪費了計算量。繼而提出了一個改進的爆炸半徑公式，實驗證明，改進算法沒有增加計算量，而優(yōu)化效率得到了提高。

1 煙花算法的原理

煙花算法來自于對煙花爆炸過程的模擬。當(dāng)煙花爆炸后，火花的散落將充滿煙花周圍的局部空間，爆炸產(chǎn)生的火花又作為新的煙花繼續(xù)爆炸，從而逐步充滿整個天空。把煙花爆炸過程看作搜索最優(yōu)解的過程，用算法實現(xiàn)，如圖1所示（求最小值）。

第i（i=1，2，…，n）個煙花爆炸產(chǎn)生的火花數(shù)目可以用式⑴表示：

⑴

式⑴中，m表示由n個煙花所產(chǎn)生的火花的總數(shù)目，ymax=max（f（xi））（i=1，2，…，n）表示n個煙花對應(yīng)目標(biāo)函數(shù)的最大值（即最壞值），ξ表示計算機所能表示的最小正常數(shù)，用于防止式⑴出現(xiàn)除零錯誤。

第i（i=1，2，…，n）個煙花爆炸的半徑是：

⑵

式⑵中，表示預(yù)先設(shè)定的最大爆炸半徑，ymin=min（f（xi））表示n個煙花代表的目標(biāo)函數(shù)的最小值（即最好值），ξ的含義同式⑴中的ξ。

第i（i=1，2，…，n）個煙花產(chǎn)生火花的過程：假設(shè)待優(yōu)化的目標(biāo)函數(shù)是D維函數(shù)，隨機選取D維中的z維坐標(biāo)進行更新，則第i（i=1，2，…，n）個煙花的第j（j=1，2，…，si）個火花的第k（k=1，2，…，z）維坐標(biāo)更新公式：

⑶

式⑶中的rand（-1，1）表示[-1，1]之間的隨機數(shù)。上面的過程中，由n個煙花總共產(chǎn)生了m個火花。另外，為了增加種群多樣性，按照高斯分布額外產(chǎn)生個火花，其中第j（j=1，2，…，）個火花的第k（k=1，2，…，z）維坐標(biāo)更新如下：

⑷

式⑷中，Gaussian（1，1）是一個均值和方差都為1的服從高斯分布的隨機數(shù)。

上述火花全部產(chǎn)生以后，在產(chǎn)生的總共K=n+m+個煙花（火花）中按照濃度原則選擇新的n個火花，參與下一輪爆炸。第i（i=1，2，…，K）個煙花（火花）被選中的概率是：

⑸

⑹

式⑸中，d（xi-xj）表示第i個煙花或火花與第j個煙花或火花之間的距離，可以是歐氏距離，也可以是適應(yīng)度的差值。由式⑹看出，距離相近的煙花（火花），被選中的概率較低，這就避免了優(yōu)勢煙花增長過快，增加了種群多樣性。

2 算法的分析與改進

2.1 算法分析

公式⑵的主要原理是優(yōu)秀的粒子爆炸的半徑小，因為優(yōu)秀粒子周圍存在全局最優(yōu)解的可能性較大，所以要給予較小的爆炸半徑，加強周圍的搜索。但也存在問題：對上次爆炸產(chǎn)生的最好煙花，帶入式⑵可得：

⑺

由于ξ是一個計算機所能表示的最小常數(shù)，用于防止除零錯誤，例如matlab系統(tǒng)中，ξ一般可以設(shè)置為1e-250，分母中的遠大于ξ，因此式⑺趨近于0。而由式⑴可知，最優(yōu)煙花總是產(chǎn)生最多數(shù)量的火花。這意味著最優(yōu)煙花產(chǎn)生的最多數(shù)量的火花的爆炸半徑都是0，即原樣復(fù)制了最優(yōu)煙花，沒有進行任何搜索，在下一輪爆炸的時候，根據(jù)式⑹，這些火花幾乎都被拋棄，所以這些火花都是沒有價值的，既增加了計算量，又減少了搜索的機會。

2.2 算法的改進

改進后的算法對于最優(yōu)火花，爆炸半徑不再參照公式⑵，而是按照公式⑻計算：

⑻

式⑻中，t是爆炸搜索的代數(shù)，T是預(yù)設(shè)的總的搜索代數(shù)，是預(yù)設(shè)的爆炸半徑最小值。顯然，隨著爆炸代數(shù)t的增加，Ai逐漸減小，這就使得算法一開始搜索半徑較大，側(cè)重于全局搜索，后期接近找到最優(yōu)值的時候減少爆炸半徑，有利于在局部精細搜索。

3 實驗

同樣采用文獻[1]中的測試函數(shù)，測試條件保持不變，本文對新增加的參數(shù)取值10-6。實驗結(jié)果見表1。

從表1中可以看出，在所有測試函數(shù)中，除了Sphere函數(shù)效果保持不變，其余測試函數(shù)在同樣計算次數(shù)下，都取得了比原算法更好的結(jié)果。

4 結(jié)束語

本文分析并改進了煙花算法中的爆炸半徑公式，使得每次爆炸中最優(yōu)煙花不再產(chǎn)生無用的個體。改進后的算法在沒有增加計算量的前提下，提高了搜索精度。

參考文獻：

[1] Tan Y.， Zhu Y. C..Fireworks Algorithms for Optimization[J]. Proc.of Int. Conf. on Swarm Intelligence （ICSI2010），Part II， LNCS 6145， Beijing， China， 2010.12-15（6）：355-364

[2] 張家琴.求解0/1背包問題的煙花算法研究[J].武漢工程職業(yè)技術(shù)學(xué)院學(xué)報，2011.23（3）.

[3] 曹炬，李婷婷，賈紅.帶有遺傳算子的煙花爆炸優(yōu)化算法[J].計算機工程，2010.36（23）.