群體智能算法——煙花算法
煙花算法是我在觀察現(xiàn)實(shí)中的煙花在空中爆炸這一現(xiàn)象，受到啟發(fā)而提出的一種具有爆炸搜索機(jī)制的全局優(yōu)化求解的新型群體智能算法，它在求解復(fù)雜優(yōu)化問題中表現(xiàn)出了非常優(yōu)良的性能和很高的效率，已經(jīng)逐漸獲得了業(yè)界的高度關(guān)注和跟蹤研究。通過近5年的發(fā)展，已經(jīng)相繼提出了二十余種煙花算法的改進(jìn)方法、收斂性分析和多項(xiàng)典型應(yīng)用，逐漸發(fā)展成為一種十分有效的群體智能算法。
記得小的時(shí)候在四川老家，每逢一年中最重要的節(jié)日春節(jié)到來時(shí)，我都會(huì)邀上幾位要好的小伙伴或同學(xué)一起到空曠的操場(chǎng)或人煙稀少的街道上，盡情燃放一種在空中爆炸的爆竹花炮。有時(shí)，幾個(gè)小伙伴還會(huì)一起進(jìn)行比賽，看看誰的爆竹扔得高、放得響，在空中燃放出最美麗的圖像。這些都是伴隨著我們兒時(shí)快樂和美好的時(shí)光，在我兒時(shí)的腦海里留下了很深的印跡。
2006 年春節(jié)，我來北京大學(xué)任教將近一年了。在這段時(shí)間里，我對(duì)進(jìn)化計(jì)算投入了較多的精力，進(jìn)行了深入的研究。因此，在這段時(shí)間不管在干什么和遇到什么新鮮的事物都會(huì)看看它們是否與進(jìn)化計(jì)算能聯(lián)系上。恰好在這一年春節(jié)期間，北京將禁放煙花爆竹的規(guī)定改為限放，首都市民都迫切地期待著除夕之夜的到來，盼望著過一個(gè)更加熱鬧和歡慶的春節(jié)。這年的除夕之夜，北京的天空盡情地開放，市民們都爭相燃放。人們?nèi)挤懦隽舜罅拷k麗多彩的禮花，將漆黑的夜空照得亮如白晝，五彩斑斕的煙花，燃放出各種美麗的圖像，激發(fā)了我內(nèi)心深處的兒時(shí)回憶，心情無比的暢快和愉悅。
此時(shí)，我的腦海里突然將煙花的爆炸圖像與進(jìn)化計(jì)算中隨機(jī)搜索建立起了聯(lián)系，產(chǎn)生了一種可以用像煙花爆炸圖像一樣的方式來對(duì)問題解空間進(jìn)行有效搜索的新方式。
通過模擬煙花爆炸的方式來進(jìn)行多點(diǎn)同時(shí)爆炸式搜索，這也許是一種高效的搜索方式，是有別于現(xiàn)有其他方法的新型搜索方法，從而有了研究這種爆炸搜索方式的想法，當(dāng)時(shí)為其取名煙花算法(fireworks algorithm，F(xiàn)WA)。
雖然煙花算法這個(gè)名稱比較直觀和簡潔，但是由于它沒有直接與優(yōu)化等求解問題建立直接的聯(lián)系，此后有些研究人員有時(shí)也用其他別稱來稱呼我們的煙花算法，如煙花優(yōu)化算法、煙花爆炸算法、煙花爆炸優(yōu)化算法、煙花爆炸搜索算法、爆炸搜索方法等。盡管有這些不同的別稱，這里統(tǒng)一采用原始的名稱煙花算法，以免混淆。
我們對(duì)煙花算法的研究動(dòng)機(jī)是希望尋求一種求解復(fù)雜問題的全局最優(yōu)解的高效方法。尤其是對(duì)具有多模特性的復(fù)雜優(yōu)化問題能夠找到高效求解的新途徑。
在2006 年的夏季學(xué)期，我招收了來自吉林大學(xué)的朱元春同學(xué)做我的直博生，并安排他來我的實(shí)驗(yàn)室從事畢業(yè)設(shè)計(jì)工作。我將之前的想法和研究煙花算法的任務(wù)交代給他來實(shí)現(xiàn)，并將他的畢業(yè)設(shè)計(jì)題目擬定為“煙花算法的研究與實(shí)現(xiàn)”，與他一道開始了對(duì)煙花算法的全面研究。
經(jīng)過半年時(shí)間的深入研究，我們共同設(shè)計(jì)了煙花算法的各個(gè)主要要素、組成和基本框架，并以“爆炸算子”為基礎(chǔ)搭建了基本的煙花算法。到2007 年5 月份，我們就完成了對(duì)煙花算法的基本研究工作。
但是，在接下來的近兩年的時(shí)間里，因?yàn)槊τ谥鞒忠豁?xiàng)國家863 計(jì)劃項(xiàng)目，只得暫緩了對(duì)煙花算法的相關(guān)研究工作，直到2009 年夏才有機(jī)會(huì)重新展開對(duì)煙花算法的研究。2010 年，在首屆國際群體智能大會(huì)上發(fā)表了題為“Fireworks algorithm for optimization”的開創(chuàng)性學(xué)術(shù)論文。自此煙花算法的研究開始受到業(yè)界的關(guān)注，對(duì)其的研究才開始在群體智能領(lǐng)域逐漸展開。
群體智能(swarm intelligence，SI) 是指由許多簡單個(gè)體組成的群體呈現(xiàn)出的涌現(xiàn)(emergence) 行為所表現(xiàn)出的集體智能，是單個(gè)個(gè)體所不具備的強(qiáng)大能力，如生物群體系統(tǒng)有蟻群、鳥群、蜂群、魚群、蜘蛛、螢火蟲、細(xì)菌等。鳥群掠過天空、蟻群尋覓食物、魚群在水中游蕩、煙花在空中爆炸、蜘蛛的爬行等，這種群體的運(yùn)動(dòng)稱為群體行為。盡管這些群體中的每個(gè)個(gè)體都非常簡單，但大量個(gè)體組成的群體所表現(xiàn)出的集體行為卻是非常復(fù)雜的，呈現(xiàn)出了智能的特色。
群體智能是進(jìn)化計(jì)算的一個(gè)活躍分支，隸屬于計(jì)算智能的范疇。近幾十年來，計(jì)算智能領(lǐng)域取得了豐富的研究成果，包括人工神經(jīng)網(wǎng)絡(luò)、模糊邏輯與系統(tǒng)、進(jìn)化計(jì)算、混沌計(jì)算、模擬退火、禁忌搜索，以及各種混合策略等，都是通過模擬或揭示某些自然現(xiàn)象或過程來實(shí)現(xiàn)的。
優(yōu)化問題是一個(gè)古老且永恒的研究問題，也是解決眾多問題的基礎(chǔ)。大量學(xué)者和實(shí)際工作者都致力于對(duì)其進(jìn)行不懈的研究。不同于經(jīng)典優(yōu)化算法采用確定性規(guī)則的方式，群體智能優(yōu)化算法利用一種概率轉(zhuǎn)移方式，通過各種隨機(jī)因素結(jié)合元啟發(fā)性規(guī)則，采用群體中的多個(gè)個(gè)體同時(shí)對(duì)解空間進(jìn)行并行搜索的方式，通過群體中個(gè)體的相互協(xié)作與競(jìng)爭來實(shí)現(xiàn)對(duì)優(yōu)化問題的最優(yōu)解的有效搜索，具有隨機(jī)性、自適應(yīng)性、魯棒性、并行性等顯著特點(diǎn)。在求解復(fù)雜優(yōu)化問題時(shí)，群體智能優(yōu)化算法表現(xiàn)出了非常明顯的優(yōu)勢(shì)，引起了人們的高度重視，成為目前的研究熱點(diǎn)。
群體智能優(yōu)化算法可以分為基于生物群體的群體智能優(yōu)化方法和基于非生物群體的群體智能優(yōu)化方法。
前者包括蟻群優(yōu)化、粒子群優(yōu)化、魚群搜索、虛擬蜜蜂算法、螢火蟲算法-I、螢火蟲算法-II、布谷鳥算法、蝙蝠算法、人工蜂群算法、人工魚群算法、磷蝦群算法、細(xì)菌覓食優(yōu)化算法等。后者包括煙花算法、水滴算法、頭腦風(fēng)暴優(yōu)化算法(BSO)、磁鐵優(yōu)化算法等。目前，群體智能算法研究主要包括理論、算法、求解問題類型、應(yīng)用。其發(fā)展趨勢(shì)包括混合算法、求解大規(guī)模問題(面臨維數(shù)災(zāi)難、大數(shù)據(jù)難題)、新型改進(jìn)算法、理論分析等。
通常，群體智能優(yōu)化算法都有一定的共性，即由組成群體的多個(gè)個(gè)體(社會(huì)昆蟲、或粒子) 的相互協(xié)同，具有交互傳遞信息(直接或間接地) 和交互式地適應(yīng)環(huán)境的能力，使群體中的個(gè)體對(duì)環(huán)境的適應(yīng)性逐代變得越來越好，逐漸求得問題的全局最優(yōu)解的足夠好的近似解。
群體智能優(yōu)化算法所具有的這種協(xié)同交互能力能夠打破沒有免費(fèi)午餐(NFL)定理的魔咒，預(yù)示了存在并且能夠發(fā)展出具有性能更加優(yōu)良的高效算法。
這預(yù)示著對(duì)群體智能優(yōu)化算法的深入研究將可能給我們帶來難以預(yù)想的益處，因此激勵(lì)更多的研究人員從事群體智能的研究和在更多的實(shí)際領(lǐng)域里積極采用群體智能的最新研究成果，使得群體智能可以更好地為人類社會(huì)服務(wù)。
3、煙花算法的組成與研究內(nèi)容
煙花算法的基本組成框架如下圖所示，主要由爆炸算子(explosive operator)、變異操作(mutation operation)、映射規(guī)則(mapping rule) 和選擇策略(selection strategy) 四大部分組成。爆炸算子包括爆炸強(qiáng)度、爆炸幅度、位移變異等操作；變異操作主要包括高斯變異操作等；映射規(guī)則包括有模運(yùn)算規(guī)則，鏡面反射規(guī)則和隨機(jī)映射規(guī)則等操作；選擇策略包括有基于距離的選擇和隨機(jī)選擇等操作。
圖 煙花算法的基本組成框架圖
煙花算法的工作過程與一般群體智能優(yōu)化算法相似，首先隨機(jī)選擇N個(gè)煙花初始化群體，然后讓群體中的每個(gè)煙花經(jīng)歷爆炸操作和變異操作，并應(yīng)用映射規(guī)則保證變異后的個(gè)體仍處于可行域內(nèi)，最后在保留最優(yōu)個(gè)體(即精英策略) 的前提下，應(yīng)用選擇策略從生成的所有個(gè)體(煙花和火花) 中選擇出余下的N-1 個(gè)個(gè)體共同組成下一代的群體。這樣周而復(fù)始，逐一迭代下去。通過這種交互傳遞信息(直接或間接地) 使群體對(duì)環(huán)境的適應(yīng)性逐代變得越來越好，從而求得問題的全局最優(yōu)解的足夠好的近似解。
目前，對(duì)煙花算法的研究工作主要包括理論分析、算法研究、求解問題類型和應(yīng)用研究。
(1) 理論分析。研究煙花算法的求解機(jī)理、收斂性質(zhì)、演化軌跡特點(diǎn)，各參數(shù)對(duì)算法性能的影響等理論問題，為開發(fā)新的算法和改進(jìn)現(xiàn)有算法提供理論指導(dǎo)。
(2) 算法研究方面。在算法研究方面，通過對(duì)煙花算法基本組成的各個(gè)成分進(jìn)行深入分析和調(diào)整，不斷改進(jìn)煙花算法的性能(收斂性、解的精度、時(shí)間效率)，提出了各種不同的改進(jìn)煙花算法。同時(shí)，通過與其他方法的結(jié)合，取長補(bǔ)短，發(fā)展出高效的混合型方法。
(3) 求解問題類型。由于煙花算法的通用性，可以用于求解下列不同類型的問題，即單目標(biāo)優(yōu)化問題、約束單目標(biāo)優(yōu)化問題、多目標(biāo)優(yōu)化問題、約束多目標(biāo)優(yōu)化問題、許多目標(biāo)優(yōu)化問題、組合優(yōu)化問題(combinatorial optimization problem，COP)、動(dòng)態(tài)優(yōu)化問題(dynamic optimization problem，DOP)、其他優(yōu)化問題。
(4) 應(yīng)用。煙花算法是一類群體智能優(yōu)化方法，具有求解復(fù)雜問題的全局最優(yōu)解的能力，同時(shí)對(duì)求解問題的目標(biāo)要求很低，不要求問題的目標(biāo)函數(shù)的梯度信息，所以具有廣泛的適應(yīng)性。因此，煙花算法可以應(yīng)用到許多實(shí)際應(yīng)用領(lǐng)域，求解人們可能遇到的各類問題。
煙花算法不僅繼承了現(xiàn)有群體智能優(yōu)化算法的許多優(yōu)點(diǎn)，還具有明顯的自身特色，歸納起來，煙花算法具有下面一些優(yōu)點(diǎn)。
（1）爆發(fā)性(explosive)。每次迭代開始，需要讓煙花進(jìn)行爆炸，在輻射范圍內(nèi)產(chǎn)生許多與該煙花本身不同的火花。之后，依據(jù)特定選擇策略選擇N 個(gè)火花或煙花做為下一代煙花群體，恢復(fù)煙花數(shù)目，并為下次爆炸過程做好準(zhǔn)備。
（2）瞬時(shí)性(instantaneity)。煙花算法中爆炸產(chǎn)生的火花，如果沒有在選擇策略中被選中成為下一代的煙花，這些火花或煙花本身都將在本次迭代中消亡，也就是說，一次特定的爆炸只存在于一次特定的迭代之中，具有瞬時(shí)存在性。
（3）簡單性(simplicity)。每個(gè)個(gè)體只能感知局部信息，個(gè)體的能力或遵循的規(guī)則非常簡單，因此算法的組成和實(shí)現(xiàn)都非常簡單。
（4）局部覆蓋性(locality)。對(duì)于某一個(gè)煙花而言，它的爆炸范圍是整個(gè)自變量取值范圍的一個(gè)小部分，其爆炸出的火花是這個(gè)爆炸范圍內(nèi)的一些局部點(diǎn)，只是對(duì)爆炸范圍的區(qū)域內(nèi)的點(diǎn)有一定程度的隨機(jī)覆蓋，但是不會(huì)涉及爆炸范圍外的點(diǎn)，因此說這種爆炸具有一定的局部性。
（5）涌現(xiàn)性(emergent properties)。使用簡單交互規(guī)則，通過協(xié)同與競(jìng)爭方式個(gè)體間相互作用，其群體總體表現(xiàn)出來的單個(gè)個(gè)體不具有的復(fù)雜行為，呈現(xiàn)出智能的特點(diǎn)。涌現(xiàn)現(xiàn)象是以相互作用為中心的, 它比單個(gè)行為的簡單累加要復(fù)雜得多。
（6）分布并行性(distributed parallelism)。群體中個(gè)體相對(duì)簡單，沒有一個(gè)直接的中心控制約束，每個(gè)個(gè)體進(jìn)行局部相互作用，本質(zhì)上是一個(gè)分布式方法，呈現(xiàn)出高度并行的特色，特別適合并行化處理。
（7）多樣性(diversity)。首先，煙花個(gè)體的多樣性，我們通過一定的選擇機(jī)制，使選擇保留下來的煙花具有不同的位置，以保證算法的多樣性特征。其次，爆炸強(qiáng)度和爆炸幅度的多樣性，即在爆炸強(qiáng)度的作用下，根據(jù)各個(gè)煙花的優(yōu)良度不同(適應(yīng)度函數(shù)值大小不同)，各個(gè)煙花產(chǎn)生不同個(gè)數(shù)的火花。在爆炸幅度的作用下，根據(jù)各個(gè)煙花不同的優(yōu)良度，各個(gè)煙花產(chǎn)生的火花擁有不同的變異幅度。最后，爆炸算子中的多種變異共存，正如煙花有多個(gè)隔層那樣，我們?cè)O(shè)計(jì)出的爆炸幅度中存在有多種變異。目前有兩種變異：一種是位移變異；另一種是高斯變異。其中，第一種位移變異是跟自變量的取值區(qū)間，以及粒子本身的優(yōu)良度(決定了變異幅度的大小) 相關(guān)的一種變異；第二種高斯變異只與煙花本身的位置有關(guān)。這兩種變異是本質(zhì)上不同的變異，保證了變異的多樣性。
（8）可擴(kuò)充性(scalability)。由于個(gè)體相對(duì)獨(dú)立，個(gè)體間的協(xié)作通常通過間接的方式實(shí)現(xiàn)信息交流，增加或減少部分個(gè)體，對(duì)系統(tǒng)的影響都不劇烈，從而保證系統(tǒng)具有很強(qiáng)的可擴(kuò)展性。
（9）適應(yīng)性(adaptability)。由于只使用各個(gè)個(gè)體的適應(yīng)性來對(duì)系統(tǒng)求解能力進(jìn)行評(píng)估，因此對(duì)所求解問題的要求非常低，甚至不要求所求解問題具有顯式的表達(dá)。
本文由劉四旦摘編自譚營著《煙花算法引論》一書。《煙花算法引論》系統(tǒng)描述了作者提出的一種新型群體智能算法——煙花算法,它的產(chǎn)生、算法實(shí)現(xiàn)、理論分析、算法改進(jìn)及其應(yīng)用,為讀者勾勒出了煙花算法的全景圖像。主要內(nèi)容包括:煙花算法的基本原理與實(shí)現(xiàn)及其性能分析、收斂性和時(shí)間復(fù)雜度分析、多種改進(jìn)算法、混合方法、離散煙花算法、煙花算法的并行化實(shí)現(xiàn),以及幾種應(yīng)用實(shí)例。書中重點(diǎn)介紹了煙花算法的參數(shù)設(shè)定,各種改進(jìn)方法、并行化實(shí)現(xiàn)、與典型群體智能算法的性能對(duì)比分析等、書中還包括了煙花算法的最新資料和一些重要算法的流程圖,以及源代碼的鏈接,供感興趣讀者參閱和使用。
