煙花算法

煙花算法

煙花算法 (Fireworks Algorithm),縮寫為 FWA,是受到夜空中煙花爆炸的啟發而提出的一種群體智慧型算法。

研究現狀

自從煙花算法的開創性論文由譚營教授等人於2010年發表之後 ,業界對煙花算法的研究逐步深入和鋪開。通過對原始煙花算法的細緻、深入的分析,針對原始煙花算法(FWA)的不足,提出了大量的改進方法,並據此發展了各種改進算法,以及與其他方法的混合方法,大大提高的原始煙花算法的性能,同時研究了煙花算法在求解不同類型最佳化問題的能力,還有大量的研究人員進行了煙花算法的套用研究,給出了一些典型的成功套用案例。

實現

煙花算法 煙花算法

煙花算法開始疊代,依次利用爆炸運算元、變異運算元、映射規則和選擇策略,直到達到終止條件,即滿足問題的精度要求或者達到最大函式評估次數。

煙花算法的實現包括如下的幾個步驟:

1)在特定的解空間中隨機產生一些煙花,每一個煙花代表解空間的一個解。

2)根據適應度函式計算每一個煙花的適應度值,並根據適應度值產生火花。火花的個數是基於免疫學中的免疫濃度的思想來計算的,即適應度值越好的煙花產生火花的數目越多。

3)根據現實中的煙花屬性並結合搜尋問題的實際情況,在煙花的輻射空間內產生火花。(某個煙花的爆炸幅度的大小由該煙花在函式上的適應度值決定,適應度值越大,爆炸幅度越大,反之亦然)。每一個火花代表解空間中的一個解。為了保證種群的多樣性,需要對煙花進行適當變異,如高斯變異。

4)計算種群的最優解,判定是否滿足要求,如果滿足則停止搜尋,沒有滿足則繼續疊代。疊代的初始值為此次循環得到的最好的解和選擇的其他的解。

特點

基本煙花算法具有如下特點 :隨機性、局部性、爆發性、隱並行性、多樣性和瞬時性。下面具體說明煙花算法的這些特點。

2.1 爆發性

在煙花算法的一次疊代開始後,煙花在輻射範圍內爆炸,會產生其他的火花。等本次疊代結束後,煙花算法選擇火花作為下一代的煙花,恢復了煙花的數目,並為下次疊代的爆發做好準備。每一次疊代,煙花都會爆發,說明煙花算法具有爆發性。

2.2 瞬時性

當一次疊代計算開始後,各個煙花依據適應度值的不同,產生不同的火花個數和爆炸幅度。接著,煙花算法將在爆炸運算元和變異運算元的作用下產生火花。最後,首先選出最優個體,再依據距離選擇其他的個體。這些選擇出來的個體將作為下一代爆炸的煙花,其餘的火花不再保留。不保留的火花或煙花將消亡,說明煙花算法具有瞬時性。

2.3 簡單性

和群體智慧型算法一樣,每個煙花只需要感知自身周圍的信息,遵循簡單的規則,完成自身的使命。總體看來,煙花算法本身並不複雜,由簡單個體組成,說明煙花算法具有簡單性。

2.4 局部覆蓋性

在煙花算法中,所有的煙花都會在相應的爆炸幅度內產生火花。除非超出可行域,產生的火花都局限在一定的範圍內。煙花算法的局部性特點體現了煙花算法強大的局部搜尋能力,可以用在算法運算的後期更加精細的搜尋最優解。因此,煙花算法具有局部性。

2.5 湧現性

煙花之間通過競爭與協作,群體之間表現出簡單個體不具有的高度智慧型性。煙花之間相互作用,比單個個體的行為要複雜得多,因此煙花算法具有湧現性。

2.6 分布並行性

在煙花算法的每次疊代過程中,各個煙花在不同坐標範圍內依次爆炸,即對不同的坐標區間進行一次搜尋,在最後會將所有的火花和煙花綜合起來,進行下一代煙花的選擇。在一次疊代中,算法實質上是並行搜尋,表現出煙花算法的分布並行性。

2.7 多樣性

種群多樣性是影響群體最佳化算法性能的關鍵。群體多樣性的保持,可以保證算法跳出局部極值點,從而可以收斂到全局最優點,這正是群體最佳化算法與一般最佳化算法的顯著區別。群體多樣性越大,算法中的個體分布越廣,找到最優值的可能越大,同時還不會明顯影響算法的收斂能力。因此,種群多樣性是煙花算法的一個重要組成部分。煙花算法的多樣性主要體現下面三個方面。

2.7.1 火花個數和爆炸幅度的多樣性

在爆炸運算元的作用下,依據各個煙花的適應度值,其產生不同個數的火花和不同的爆炸幅度。適應度值高的煙花產生更多的火花,爆炸幅度相對較小,而適應度值低的煙花產生更少的火花,爆炸幅度相對較大。因此,保證了火花個數和爆炸幅度的多樣性。

2.7.2 位移操作和高斯變異的多樣性

煙花算法有兩種運算元,第一種是爆炸運算元,第二種是變異運算元。在爆炸運算元的位移操作中,對計算出來的幅度範圍,隨機產生一個位移,將在選中的煙花加上這個隨機位移。在變異運算元的作用下,選中的煙花需要乘以一個滿足高斯分布的隨機數。爆炸運算元與煙花的適應度值有關,變異運算元與煙花本身的坐標值有關。兩種運算元是本質上不同的,都保證了爆炸的多樣性。

2.7.3 煙花的多樣性

通過一定的選擇機制,保留下來的煙花坐標值各不相同,從而保證了煙花算法的多樣性特徵。另外,在選擇策略中,距離其他火花距離更大的火花更容易被選中,也體現出煙花算法中煙花的多樣性特徵。

2.8 可擴充性

煙花算法中煙花和火花的數量不確定,可以依據問題的複雜度來確定。煙花和火花的數目可多可少,增加和減少個體都能有效地求解問題,因此煙花算法具有可擴充性。

2.9 適應性

煙花算法求解問題時,不要求問題具有顯示表達,只要計算適應度值就能求解問題。同時,煙花算法對問題的要求低,也能求解顯示表達的問題。因此煙花算法具有適應性。

未來發展

到2018年為止,煙花算法的研究還是很初步的 。在有些方面,還是空白,在許多方面,還很膚淺,急需廣大有興趣的研究人員對其進行深入研究。煙花算法的未來發展歸納起來,可以有下列幾個方面:

1、 算法的理論基礎和分析 (穩定性、收斂性、收斂特性、參數靈敏度分析)

2、 各種改進方法的深入研究(各種因素對煙花算法性能的影響,如何有效控制和調整。重點是:子煙花間的協同機制建立和研究)

3、 混合方法的研究

4、 大數據問題的求解 (如何處理巨大數據?)

5、 動態最佳化問題的求解 (最佳化目標值隨時間變化的情況, 如:群體機器人的動態目標追蹤搜尋問題)

6、 更廣泛的套用研究

相關詞條

熱門詞條

聯絡我們