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

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

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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]。本文分析了煙花算法中一個(gè)重要的爆炸半徑公式，指出最優(yōu)煙花所產(chǎn)生的火花由于爆炸半徑趨向于0，對(duì)算法搜索沒(méi)有貢獻(xiàn)，白白浪費(fèi)了計(jì)算量。繼而提出了一個(gè)改進(jìn)的爆炸半徑公式，實(shí)驗(yàn)證明，改進(jìn)算法沒(méi)有增加計(jì)算量，而優(yōu)化效率得到了提高。

1 煙花算法的原理

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

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

⑴

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

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

⑵

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

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

⑶

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

⑷

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

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

⑸

⑹

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

2 算法的分析與改進(jìn)

2.1 算法分析

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

⑺

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

2.2 算法的改進(jìn)

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

⑻

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

3 實(shí)驗(yàn)

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xià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背包問(wèn)題的煙花算法研究[J].武漢工程職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2011.23（3）.

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