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

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

關鍵詞： 煙花算法； 爆炸半徑； 群體智能； 優化算法

中圖分類號：TP301.6 文獻標志碼：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年提出的一種新的群體智能優化算法，具有卓越的優化性能，因此一經提出就引起了世界范圍內的廣泛關注[2-3]。本文分析了煙花算法中一個重要的爆炸半徑公式，指出最優煙花所產生的火花由于爆炸半徑趨向于0，對算法搜索沒有貢獻，白白浪費了計算量。繼而提出了一個改進的爆炸半徑公式，實驗證明，改進算法沒有增加計算量，而優化效率得到了提高。

1 煙花算法的原理

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

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

⑴

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

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

⑵

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

第i（i=1，2，…，n）個煙花產生火花的過程：假設待優化的目標函數是D維函數，隨機選取D維中的z維坐標進行更新，則第i（i=1，2，…，n）個煙花的第j（j=1，2，…，si）個火花的第k（k=1，2，…，z）維坐標更新公式：

⑶

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

⑷

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

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

⑸

⑹

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

2 算法的分析與改進

2.1 算法分析

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

⑺

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

2.2 算法的改進

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

⑻

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

3 實驗

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

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

4 結束語

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

參考文獻：

[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].武漢工程職業技術學院學報，2011.23（3）.

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