煙花算法研究改進(jìn)綜述

北京信息科技大學(xué)計(jì)算機(jī)學(xué)院 崔光松

1.帶有遺傳因子的煙花算法(GAFEO)

隨著人工智能的快速發(fā)展，越來(lái)越多的機(jī)器人具有了和人類(lèi)一樣的能力，為了讓機(jī)器人更加智能，不斷有科學(xué)家對(duì)相關(guān)算法進(jìn)行改進(jìn)。帶有遺傳因子的煙花算法是基于煙花算法改進(jìn)的一種算法。該算法在煙花算法[1]中融入了遺傳算法思想，與原算法相比在尋優(yōu)能力和尋優(yōu)精度等方面具有較高性能。GAFEO算法主要在原算法里添加了爆點(diǎn)分析、智能分布式搜索以及生物學(xué)中的種間更替思想。爆點(diǎn)分析[2]的引入主要解決了在爆點(diǎn)范圍較大的情況下，爆炸產(chǎn)生的目標(biāo)發(fā)生聚集而產(chǎn)生不相關(guān)搜索影響算法搜尋效率的問(wèn)題；智能分布式搜索的引入主要解決了因爆炸瞬間產(chǎn)生局部和全局分層現(xiàn)象而降低搜索精度的問(wèn)題；生物學(xué)中的種間更替思想的引入主要優(yōu)化改善了原算法僅在當(dāng)前爆點(diǎn)區(qū)域內(nèi)搜索而錯(cuò)失其他區(qū)域最優(yōu)解的缺點(diǎn)，讓其在搜索完本區(qū)域最優(yōu)解的同時(shí)憑借超強(qiáng)的擾動(dòng)能力在相鄰或其他區(qū)域再次搜尋最有解，然后將最終的搜尋結(jié)果進(jìn)行分析比對(duì)，得出最最終最優(yōu)解。這些改進(jìn)有效改善了原算法停留在部分最優(yōu)、弱化部分搜索、缺乏智能分析等不足。

2.改進(jìn)的動(dòng)態(tài)搜索煙花算法

改進(jìn)的動(dòng)態(tài)搜索煙花算法在原算法中加入了智能因子，在不斷搜索過(guò)程中，該算法能夠向已搜索出來(lái)的最優(yōu)解進(jìn)行學(xué)習(xí)，然后根據(jù)學(xué)習(xí)結(jié)果改變自身的方向以及搜尋精度，進(jìn)而合理分配部分搜索和全局搜索的力度。改進(jìn)后的算法主要改善優(yōu)化了原算法過(guò)快收斂、搜索精度差、最優(yōu)解不唯一等問(wèn)題。此外改進(jìn)的算法融入了特征分析策略，使得在尋找最優(yōu)解的過(guò)程中算法可以將具有相同特征的因子有效結(jié)合，進(jìn)而縮短搜尋最優(yōu)解的時(shí)間。由于在搜尋過(guò)程中會(huì)產(chǎn)生很多特征，改進(jìn)后的算法會(huì)對(duì)這些特征進(jìn)行分析，通過(guò)具有這些特征的因子的數(shù)量的多少以及這些因子所占的權(quán)重決定哪些特征是有效的特征，分析出有效特征后再將無(wú)效特征剔除然后重復(fù)比對(duì)分析有效特征進(jìn)而得出最優(yōu)解，這樣做的目的一來(lái)將距離爆點(diǎn)較遠(yuǎn)的因?yàn)榭紤]在內(nèi)，二來(lái)在分析搜尋的初始階段就將無(wú)效因子剔除在外，防止浪費(fèi)過(guò)多時(shí)間影響搜尋效率。

3.二進(jìn)制反向?qū)W習(xí)煙花算法[3]

二進(jìn)制反向?qū)W習(xí)煙花算法引入01數(shù)學(xué)符號(hào)，將一些在搜索過(guò)程中的最優(yōu)分析離散化，進(jìn)而解決求解效率低下或者根本求解不出最優(yōu)解的問(wèn)題。一般情況下，最優(yōu)解是通過(guò)對(duì)隨機(jī)節(jié)的不斷提煉篩選獲得的，而分析提煉隨機(jī)解的過(guò)程是尋找最優(yōu)解中最耗時(shí)的過(guò)程，主要原因是，一旦算法沿著某一依據(jù)一直分析下去，可能因?yàn)橐婚_(kāi)始的方向就是錯(cuò)誤的，不管之后采用多么精確的算法，多么智能的分析策略，多難以得出最優(yōu)解。二進(jìn)制反向?qū)W習(xí)煙花算法就很好的解決的這個(gè)弊病，當(dāng)算法沿著某一反向在規(guī)定時(shí)間內(nèi)依舊無(wú)法得出我們預(yù)期的最優(yōu)解時(shí)，算法將同時(shí)分析當(dāng)前方向的反方向的隨機(jī)解，并且賦予反方向的隨機(jī)解以更大的權(quán)重，這樣就能有效避免算法一直沿著某一錯(cuò)誤的方向繼續(xù)下去。因?yàn)橐坏┧惴ǖ姆较蝈e(cuò)誤，不管是繼續(xù)下去還是反方向回去都是費(fèi)時(shí)費(fèi)力的，繼續(xù)分析下去肯定是 無(wú)果而終，返回起始點(diǎn)則更是耗時(shí)的操作，本算法則不讓其回到起始位置，而是從其相反方向與當(dāng)前方向并行分析，這樣總能在有限時(shí)間內(nèi)找到最優(yōu)解。

4.雙種群煙花算法

我們都知道在煙花爆炸之后，其收斂速度是非常慢的，如果不認(rèn)為的干擾，這是不利于我們尋找最優(yōu)解的。雙種群煙花算法用兩個(gè)種群同時(shí)并發(fā)運(yùn)行的方式有效解決了原煙花算法易陷入部分最優(yōu)解、收斂周期長(zhǎng)等問(wèn)題。該算法的主要思路是在煙花演化過(guò)程中，算法一方面執(zhí)行爬山因素，同時(shí)在另一方面還執(zhí)行協(xié)作因素，爬山因素主要是加強(qiáng)在煙花高斯變異過(guò)程中局部搜索能力，協(xié)助因素則是減弱由于局部搜索能力加強(qiáng)所帶來(lái)的負(fù)面效應(yīng)。并行執(zhí)行不但增加了算法對(duì)隨機(jī)解的選擇能力，同時(shí)由于并行算法相當(dāng)于兩個(gè)單一算法的融合，其將爆炸算子、協(xié)作因素、特征選擇、隨機(jī)解分析同時(shí)多方面執(zhí)行，使得最優(yōu)解的得出更加高效，此外由于收斂速度加快，所得出的最優(yōu)解也不再是局部最優(yōu)解，而是全局最優(yōu)解。

5.引入慣性權(quán)重的煙花算法

引入慣性權(quán)重的煙花算法的提出主要是為了尋找全局最優(yōu)解，因?yàn)樵兴惴〞?huì)因?yàn)楦鞣N因素的影響而陷入局部最優(yōu)解。該算法融入了一種帶有權(quán)重的慣性量，該慣性量隨著煙花變異次數(shù)的 增加而成遞減趨勢(shì)。該算法在每次分析隨機(jī)解的過(guò)程中都保留了上一次的分析記錄，通過(guò)對(duì)前面的分析記錄的比對(duì)，來(lái)進(jìn)一步確定當(dāng)前所獲得的最優(yōu)解是否為真正的最優(yōu)解。這樣做的好處一來(lái)避免了無(wú)用的搜索分析，二來(lái)使得所得到的最優(yōu)解得到有效驗(yàn)證。

[1]Tan Y,Zhu Y.Fireworks algorithm for optimization[J].Tan Y,Shi YuHui,et al.Advances in swarm intelligence[C].Springer Berlin Heidelberg,2010:355-364.

[2]Hsieh Sheng-Ta,Sun Tung-Ying,Liu Changcheng.Potential Offspring Production Strategies:An Improved Genetic Algorithm for Global Numerrical Optimizatioin[J].Expert Systems with Applications,2006,36(8):11088-11098.

[3]吳虎勝,張鳳鳴,戰(zhàn)仁軍,等.利用改進(jìn)的二進(jìn)制狼群算法求解多維背包問(wèn)題[J].系統(tǒng)工程與技術(shù),2015,37(5):1084-1091.