基本介紹
- 中文名：煙花算法
- 外文名：Firework Algorithm
研究現狀,實現,特點,未來發展,
研究現狀
自從煙花算法的開創性論文由譚營教授等人於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、 更廣泛的套用研究
