A. 優化演算法筆記（十二）煙花演算法
（以下描述，均不是學術用語，僅供大家快樂的閱讀）
煙花演算法（Firework Algorithm,FWA）是一種受煙花爆炸產生火星，並繼續分裂爆炸這一過程啟發而得出的演算法。演算法的思想簡單，但具體實現復雜。演算法提出時間並不長，但是已經有了不少的改進研究和較為全面的應用。
煙花演算法中，每一個煙花的位置都代表了一個可行解。煙花的爆炸產生的火星有兩種，正常的火星與特別的火星。每個火星都會爆炸產生數個正常火星，某些火星有一定的概率產生一個特別的火星。正常的火星根據當前火星的振幅隨機均勻分布在該火星的周圍，而特別的火星將在當前火星附近以正態分布方式產生。每次迭代產生的火星數量多於每一代應有的火星數，演算法將參照火星位置的優劣，隨機留下指定數量的火星，已保持火星數目的穩定。
煙花演算法的主角毫無疑問就是煙花了。
式（1）為適應度值越小越優的情況，而式（2）則是適應度值越大越優的情況。 為一個極小的值，以保證分母不為0。
每個火星產生的正常火星數量也由其適應度值來決定。
其中 表示第i個火星將要產生的正常火星數， 是產生正常火星的總數為一個常數，從式（3）,（4）可以看出適應度值越好的火星能夠產生更多的正常火星，反之，火星適應度越差，能夠產生的火星數越少。
由於式（3），（4）計算出的值為小數，煙花演算法中使用式（5）將其轉化為整數。
從式（3）和式（4）中可以看出，在每一代中將會產生出 個正常火星。產生的正常火星的位置與當前火星的振幅有關，可以從式（1），（2）看出，適應度越優的火星的振幅越小，那麼它產生的正常火星將在它自己周圍，而適應度越差的火星的振幅越大，它產生的正常火星將會出現在離自己較遠的位置。
當前火星每次爆炸會從D維搜索空間內隨機選擇z維進行更新從而產生新的火星。正常火星的位置由如下公式產生。
其中z為取值1-D的均勻隨機正整數，rand(-1,1)表示-1到1內的均勻隨機數。從式(6)中可以看出，正常火星的位置與其振幅有直接關系，振幅越大產生的新火星距當前火星的距離約遠。
每次迭代過程中，會產生m個特別的火星，即在這N個火星中隨機選擇m個火星，每個火星產生一個特別的火星。特別的火星的由下面的公式產生：
由上面的過程可知，在每一代中，有N個火星，將會產生出 個正常火星以及m個特別的火星。但是每一代中只能從這 個火星中選擇N個火星保留至下一代。
每次會先從 個火星中選擇最優的火星保留至下一代，然後再從中選擇N-1個火星。選擇某個火星的概率如下：
其中R(X)表示該火星距其他所有火星的距離之和，即距其它火星越遠的火星，被選擇保留至下一代的概率較大。
個火星，而且
,所有煙花演算法每次迭代的計算復雜度要大於其他演算法，這簡直就是一個作弊行為。別的演算法每次只搜索了N個位置，而煙花演算法卻搜索了 個位置。與其他優化演算法對比時，其他演算法的種群數量應該取 ，否則這將是一場不公正的對決。
適應度函數還是這個簡單的小白鼠
實驗一 ：標准煙花演算法
以上數據來自原論文，現在看一看實驗的圖像以及實驗結果。
從圖像可以看出每次只選擇保留了5個火星，它們的收斂速度很慢，實驗結束時距離目標點還有一段距離。
看看實驗結果
從實驗結果可以看出，演算法的性能很不穩定，而造成這一點的原因很可能是其收斂速度較慢，演算法仍在收斂過程中，所以結果看上去很差。將最大迭代次數修改為100代，重新試驗，其結果如下：
結果好了一些但還是難以接受，為什麼煙花演算法的結果不理想呢？
原因可能是保留機制（2.3節）的問題，煙花演算法中保留火星的概率是根據該火星與其他火星的距離和，距離群體越大的個體被保留下的概率越大。這樣做有什麼好處呢？好處是火星相對分散，這是一個對抗局部最優的策略，但是，距離群體較遠的個體是一個較差的個體的概率非常大，壞處就是，集中於當前最優位置的火星被保留的概率較小，演算法的局部搜索能力將較弱。
實驗二 . 隨機選擇的方式保留火星
為了加快煙花演算法的收斂速度，增強局部搜索能力，我移除了標准煙花演算法的選擇過程，使用隨機選擇的方式保留火星，當然，最優個體依然會被保留至下一代。其他參數保持不變。
可以看出這次的圖像相比實驗一收斂速度快了不少，在迭代結束時已經相對在一個較小的區域。這次的結果也明顯優於實驗一。將選擇過程改為隨機選擇後，由於較優的火星產生的較多且分布在自己周圍，因此選擇到這些較優的火星的概率也相對較大，演算法的收斂速度相對較快。與此同時，演算法跳出局部最優的能力比修改前要弱。
對於較簡單的問題來說當然是隨機選擇收斂較快結果較好，而復雜的問題則需要更強的跳出局部最優能力。問題的關鍵仍然是，我們無法在一開始就知道問題的復雜程度。
實驗三 .增加火星的種群數量，減少每代產生的正常火星總數
為什麼要減少產生的正常火星數，這樣演算法搜索的次數減少了，效果不會更差嗎？其實與直覺相反，減少正常火星總數，增加火星總群數，實際上是讓較優的火星產生的正常火星被保留下來的概率變大了，這樣也可以解決實驗一中的問題，加快演算法的收斂速度。
從圖像中可以看出，演算法在50代之前已經收斂，但是之後只在小范圍內進行搜索。實驗圖像與之前的描述相符，收斂速度加快但是跳出局部最優能力減弱。看看實驗結果，實驗結果好了不少且結果更加穩定。
其實實驗二與實驗三，使用了不同的策略，但都達到了同樣的目的——保留更多的優質火星到下一代，它們促進了局部搜索但是擠佔了較劣火星的位置，削弱了種群的多樣性。
每代留下的火星多了，圖像看上去是不是更像煙花？
煙花演算法的探究遠不止如此，幾年前作為一個較新的演算法來學習時卻已經有了大量的論文和書籍，可見大家對煙花演算法已經有了較為深入的研究，而我能做的只是應用演算法解決問題以及稍作改進讓演算法與問題的適應性更高。
煙花演算法產生正常火星的過程為演算法提供了搜索能力，產生特殊火星的過程和選擇過程為演算法提供了跳出局部最優的能力。但是個人認為選擇過程與其他過程的適應性不是很好。標準的選擇過程會丟失掉許多較優的個體，使之前產生的正常火星得到的成果沒有保留。
煙花演算法其實還有比較多的改進點，對演算法產生最大的參數應該就是正常火星的總數以及振幅了。簡單粗暴的改進：在每一代可以對這兩個參數進行變化或者隨機化，讓演算法的搜索能力與跳出局部最優能力在整個流程中動態變化，以均衡兩種能力。
以下指標純屬個人yy,僅供參考
參考文獻
Tan Y , Zhu Y . Fireworks Algorithm for Optimization[C]// Advances in Swarm Intelligence, First International Conference, ICSI 2010, Beijing, China, June 12-15, 2010, Proceedings, Part I. Springer-Verlag, 2010. 提取碼：yaj0
目錄
上一篇 優化演算法筆記（十一）群搜索演算法
下一篇 優化演算法筆記（十三）鯨魚演算法
優化演算法matlab實現（十二）煙花演算法matlab實現