集群智能算法綜述

秦小林，羅 剛，李文博，張國華

（1.中國科學(xué)院成都計算機應(yīng)用研究所，成都 610041；2.中國科學(xué)院大學(xué)，北京 100049；3.中國航天科工飛航技術(shù)研究院磁懸浮與電磁推進技術(shù)總體部，北京 100074）

1 引 言

針對工程技術(shù)領(lǐng)域中復(fù)雜的優(yōu)化問題，眾多學(xué)者選擇從自然界的現(xiàn)實模型中尋求解決方法，由此開啟了自然啟發(fā)式計算（Nature-inspired computation）的研究。在過去幾十年里，自然啟發(fā)式計算是最受研究者關(guān)注的人工智能研究分支之一，平均每年有數(shù)百個優(yōu)秀的新算法提出，且這一增長趨勢仍在繼續(xù)。這些算法在適應(yīng)性、自學(xué)習(xí)能力、魯棒性及高效性等方面都有很好的表現(xiàn)。自然啟發(fā)式計算中有一類關(guān)注簡單行為個體組成的集群通過自組織完成復(fù)雜任務(wù)的工作，稱作集群智能(Swarm Zntelligence)，如圖1。

圖1 集群智能與人工智能的關(guān)系Fig.1 The relationship between Swarm Intelligence and Artificial Intelligence

1993年，Dario等研究了移動機器人系統(tǒng)，并提出了集群智能的概念[1]，指出簡單的有序系統(tǒng)即可產(chǎn)生非平凡的智能行為。Kordon[2]將集群智能定義為基于無中心、自組織群體行為的智能計算技術(shù)。而Bonabeau[3]為群體智能給出了更簡單的定義，即由簡單的個體組成的群體所產(chǎn)生的集體智慧。一個典型的集群智能系統(tǒng)由若干個可以相互通信的、只能完成簡單行為的代理（agent）組成，這些代理沒有控制中心，行為簡單，但往往可以通過相互之間的簡單交互完成十分復(fù)雜的任務(wù)，整體上表現(xiàn)出智能。集群智能系統(tǒng)表現(xiàn)出智能的現(xiàn)象常稱為“涌現(xiàn)”[4]。集群智能發(fā)揮了集群的所有優(yōu)勢，自組織、無中心控制、高魯棒性、靈活且低消耗，面對大規(guī)模的復(fù)雜問題時仍能給出最優(yōu)解。

最早的集群智能算法包括如蟻群優(yōu)化算法[4]（Ant Colony Optimization, ACO）和粒子群優(yōu)化算法[5]（Particle Swarm Optimization, PSO）等都受到了廣泛的關(guān)注和應(yīng)用，在很多領(lǐng)域都大獲成功，如經(jīng)典的旅行商問題等。它們普遍具有結(jié)構(gòu)簡單、參數(shù)少、實現(xiàn)容易等特點。如今已廣泛應(yīng)用于函數(shù)優(yōu)化、多目標(biāo)優(yōu)化、求解整數(shù)約束和混合整數(shù)約束優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、信號處理、路由算法等實際問題，實踐結(jié)果證明了這些算法的可行性和高效性[6]。這些年來，學(xué)界對解決復(fù)雜計算任務(wù)的集群智能算法研究呈爆炸趨勢增長，如圖2所示。

圖2 集群智能算法文章趨勢（數(shù)據(jù)來自Scopus）Fig.2 Tendency of Swarm Intelligence algorithm articles (data from Scopus)

上述研究大多與優(yōu)化問題相關(guān)，主要集中在健康衛(wèi)生、社交網(wǎng)絡(luò)、交通運輸、能源氣候、工業(yè)4.0等領(lǐng)域，都取得了很好的效果[7-11]。除了應(yīng)用研究，針對集群智能算法本身性質(zhì)的理論研究也同樣引人關(guān)注。集群的簡單交互如何涌現(xiàn)出智能；面對同一個問題，不同的集群智能算法卻表現(xiàn)千差萬別，如何從理論上分析這種區(qū)別；問題的建模方法與算法求解效率關(guān)系；算法搜索的精度和廣度的平衡等。某些問題已取得了一些喜人的進展，然而更多的理論研究則收效甚微，仍極具挑戰(zhàn)性。

本文接下來安排如下：第2節(jié)簡單回顧最重要的兩個集群智能算法——粒子群優(yōu)化算法和蟻群優(yōu)化算法；第3節(jié)介紹部分集群智能表現(xiàn)優(yōu)異的應(yīng)用場景；第4節(jié)討論集群智能的理論研究及發(fā)展方向；第5節(jié)為總結(jié)。

2 集群智能算法介紹

2.1 粒子群算法

1995年，社會心理學(xué)家Kennedy與電氣工程師Eberhart受鳥群或魚群覓食行為的啟發(fā)，進而提出了粒子群優(yōu)化算法用于解決日益復(fù)雜的優(yōu)化問題[5]。他們將族群中的個體（粒子）當(dāng)作給定優(yōu)化問題的一個解，粒子在解空間中按照某種策略移動或游走，試圖找到問題的最優(yōu)解。粒子群優(yōu)化中粒子的移動策略參考的是鳥群覓食行為，并非完全漫無目的地在區(qū)域內(nèi)“碰運氣”，而是會向群體分享自己的知識，并參考種群中最好的經(jīng)驗和自己記憶中最好的地點，綜合決定下一步去尋找食物的位置。粒子群優(yōu)化中這兩個參考因素分別是種群最優(yōu)（gbest）及個體最優(yōu)（pbest），粒子根據(jù)這兩個因素來更新自己的移動速度向量。假設(shè)待解決問題在D維搜索空間，在t時間下群體中的第i個粒子的當(dāng)前位置由D維向量來表示，其速度由另一個D維向量表示，第i個粒子訪問過的最優(yōu)解位置用表示，群體中最優(yōu)粒子的索引為“g”，則在每次搜索迭代中，第i個粒子的速度和位置分別由下式進行更新：

原始的粒子群優(yōu)化算法的流程如下：創(chuàng)建一個大小為S的D維群體，并初始化速度向量；for t=1 to 最大迭代次數(shù) do for i=1 to S do應(yīng)用速度更新等式（1）；應(yīng)用位置更新等式（2）；計算位置更新后的適應(yīng)度值；如果需要，更新pbest和gbest的歷史信息；end如果gbest滿足問題需求，則終止算法；end

其中：i=1,2,…,S為粒子索引，S是群體大小，ω是慣性權(quán)重；c1和c2為加速系數(shù)，用于調(diào)整粒子向全局最優(yōu)及自身最優(yōu)運動的最大步長，也可稱為學(xué)習(xí)因子，表示粒子“自我學(xué)習(xí)”和“社會學(xué)習(xí)”的能力；r1和r2是滿足均勻分布(0,1)的隨機數(shù)?？梢钥吹?，速度更新時考慮了三部分的內(nèi)容：第一部分是自身運動的慣性，記錄自己原本的運動方向，其目的是防止粒子劇烈地改變方向；第二部分是認(rèn)知或自我部分，通過這一項，粒子的當(dāng)前位置會向其自己的最好位置移動，這樣在整個搜索過程中，粒子會記住自己的最佳位置，從而避免自己四處游蕩；第三部分是社交部分，負(fù)責(zé)通過群體共享信息，為保證粒子向群體中最優(yōu)的個體移動，即每個個體向群體中的其他個體學(xué)習(xí)。

公式（1）與公式（2）描述的是粒子群優(yōu)化算法的原始形式，其在多個數(shù)據(jù)集上都取得了十分不錯的效果，但是算法本身還存在諸多問題。例如，粒子群算法易陷入局部最優(yōu)；算法的收斂速度會逐漸變得緩慢；算法的參數(shù)選擇隨機，需要經(jīng)過多次調(diào)整才能取得好的效果。針對這些問題，眾學(xué)者提出了很多改進方案，例如Clerc等[12]在粒子群優(yōu)化算法中引入壓縮因子用于控制算法收斂；Bergh等[13]將搜索空間按維度進行分割，分別使用粒子群優(yōu)化算法得到最優(yōu)解后合并成完整的解；除算法本身的改進外，還有很多研究者將粒子群優(yōu)化算法與其他算法結(jié)合，提出性能更優(yōu)的混合算法[14-15]。

2.2 蟻群優(yōu)化算法

蟻群優(yōu)化算法模仿螞蟻的合作行為來解決復(fù)雜的組合優(yōu)化問題[4]。螞蟻是一種高度社會化的生物，它們覓食時可快速越過障礙物，找到蟻巢與食物之間的最短路徑。如圖3，蟻群覓食過程中，如果蟻巢到食物源已存在最短路徑，則螞蟻會按此路徑搬運食物；當(dāng)前路徑如被障礙物阻隔，需要尋找新的路徑，蟻群會按照所有可能的方向出發(fā)尋找新的路徑，最后的路徑就是最優(yōu)路徑。Dorigo等[4]經(jīng)過研究后將這一過程分為路徑構(gòu)建與信息素更新兩步，進而提出了蟻群優(yōu)化算法。初始化時，螞蟻會漫無目的地按照隨機選取的方向搜索食物，并在搜索過程中釋放信息素；沿途的信息素會隨時間揮發(fā)，因此較短的路徑相比于較長的路徑會殘留更多的信息素；后續(xù)的螞蟻根據(jù)信息素的指引選擇路徑，因此會有更多的螞蟻選擇信息素殘留較多也就是較短的路徑。這些螞蟻在搜索過程中同樣也會釋放信息素，使較短的路徑又會累計更多信息素進而吸引更多螞蟻。這樣的正反饋機制下，最終蟻群會找到最短路徑也就是問題的最優(yōu)解。蟻群優(yōu)化算法用于搜索最優(yōu)路徑在旅行商問題上取得了非常好的效果。因其分布式并行、強魯棒性、易與其他算法結(jié)合等特點受到學(xué)界的廣泛關(guān)注，并針對性地提出了很多的改進算法和混合算法，用于無線網(wǎng)絡(luò)、作業(yè)調(diào)度、路徑規(guī)劃、數(shù)據(jù)挖掘等領(lǐng)域。

圖3 蟻群覓食圖例Fig.3 Figure of ant colony foraging

除了粒子群優(yōu)化算法與蟻群優(yōu)化算法外，集群智能領(lǐng)域還有很多非常優(yōu)秀的優(yōu)化算法。文獻[16]提出了一種模擬蜜蜂覓食行為的人工蜂群優(yōu)化（Artificial Bee Colony，ABC）算法，ABC算法中除了蜜蜂的基礎(chǔ)選擇機制與蜜蜂間的簡單交互外，還引入了一些局部與全局搜索機制，在人工神經(jīng)網(wǎng)絡(luò)訓(xùn)練、組合優(yōu)化、電力系統(tǒng)優(yōu)化、系統(tǒng)和工程設(shè)計等多個領(lǐng)域得到廣泛應(yīng)用；蜘蛛猴優(yōu)化[17]靈感來自蜘蛛猴在覓食過程中的裂變?nèi)诤仙鐣?Fission-Fusion Social)結(jié)構(gòu)，巧妙地描述了群體智能最重要的兩個基本概念：自組織和分工；還有其他的集群智能算法，如細(xì)菌算法、布谷鳥搜索、螢火蟲算法、蝙蝠算法、細(xì)菌覓食優(yōu)化、煙花算法等都在很多領(lǐng)域取得了良好效果。在此，我們總結(jié)了一些經(jīng)典的集群智能算法，如表1所示。

表1 主要集群智能算法Table 1 Main Swarm Intelligence algorithms

3 集群智能應(yīng)用

集群智能作為優(yōu)化算法，涉及的應(yīng)用領(lǐng)域極其廣泛。本部分僅選取近年來的部分熱門領(lǐng)域作簡單介紹。需要了解的是不同的集群智能算法面對不同的應(yīng)用問題有不同的性能表現(xiàn)，如粒子群優(yōu)化算法在分布式資源管理、定位、資源分配、最大化/最小化、全局優(yōu)化自適應(yīng)學(xué)習(xí)等領(lǐng)域表現(xiàn)優(yōu)異，而蟻群優(yōu)化算法則擅長網(wǎng)絡(luò)分析、旅行商問題、路由算法、聚類問題、博弈論等。

Ad Hoc網(wǎng)絡(luò)是集群智能算法尤其是蟻群優(yōu)化算法應(yīng)用最成功的領(lǐng)域之一。我們知道，集群智能的一個非常重要的特性就是無中心、自組織，這是Ad Hoc網(wǎng)絡(luò)區(qū)別于傳統(tǒng)網(wǎng)絡(luò)最鮮明的特點，因此集群智能算法在Ad Hoc網(wǎng)絡(luò)中得到了極為廣泛的應(yīng)用。以路由協(xié)議為例，自20世紀(jì)90年代開始，有大量的基于蟻群優(yōu)化算法的Ad Hoc路由協(xié)議開發(fā)出來，包括基本網(wǎng)絡(luò)通信路由協(xié)議，如 AntNet(2018)[58]、ARA[59]、PERA[60]、AntHocNet[61]等，以及滿足特定應(yīng)用需求的路由算法，如ACO-EEAODR[62]、AntHocMMP[63]、POSANT[64]等。

大數(shù)據(jù)技術(shù)與機器學(xué)習(xí)作為近些年的研究熱點，同樣有許多集群智能算法的身影。以特征提取過程為例，粒子群優(yōu)化算法、蟻群優(yōu)化算法、螢火蟲算法、布谷鳥搜索等都取得了很不錯的效果，Abdi等[65]于2013年提出的用于紅皮病的診斷模型，便是利用基于粒子群優(yōu)化算法與支持向量機（Support Vector Machine，SVM）的方法作特征提取。Chen等[66]利用蟻群優(yōu)化算法結(jié)合粗糙集理論提取最小特征集，并得到了很好的結(jié)果。Huang[67]則結(jié)合蟻群優(yōu)化算法和SVM方法提取小而優(yōu)的特征集，所提出的基于蟻群優(yōu)化算法的分類器極大地提高了分類精度。Kadri等[68]提出的基于二進制編碼的蟻群優(yōu)化算法通過消除噪聲特征的方法提取最優(yōu)特征集。

集群智能算法在智能電網(wǎng)中也得到了廣泛的應(yīng)用[69-70]，文獻[71]將粒子群優(yōu)化算法用于分布式發(fā)電機系統(tǒng)來減少系統(tǒng)的能量損失，文獻[72]應(yīng)用粒子群算法優(yōu)化分布式能源系統(tǒng)中的效益成本比，同樣粒子群優(yōu)化算法還用于實現(xiàn)智能電網(wǎng)的需求側(cè)管理系統(tǒng)[73]，類似的工作還有文獻[74-75]。這些工作都成功地減少了系統(tǒng)的能源損耗，展現(xiàn)了集群智能算法在能源系統(tǒng)與智能電網(wǎng)領(lǐng)域的應(yīng)用潛力。集群智能算法同樣促進了城市智能交通領(lǐng)域的發(fā)展，文獻[76]將車輛的燃料損耗加入算法的評估函數(shù)中，使用蟻群優(yōu)化算法做路徑規(guī)劃，在得到最優(yōu)路徑的同時有效地節(jié)省了車輛的整體燃料消耗。文獻[77-78]使用粒子群優(yōu)化算法來優(yōu)化電池使用，以延長電動車輛的電池使用壽命。文獻[79]將粒子群優(yōu)化用于車輛避碰，所提出的PID控制器，不僅可使CCAS實現(xiàn)基本功能，還可實現(xiàn)車輛動態(tài)穩(wěn)定性、行駛舒適性和燃油經(jīng)濟性的改善。粒子群優(yōu)化在文獻[80]中用于交通流量預(yù)測，同樣的任務(wù)，文獻[81]則采用了人工神經(jīng)網(wǎng)絡(luò)與蟻群優(yōu)化算法的混合算法。關(guān)于智能交通中集群智能算法的應(yīng)用，更多可參考文獻[82-83]，而文獻[84]與文獻[85-86]分別是應(yīng)用智能算法解決智慧交通系統(tǒng)的信號燈控制問題與交通擁塞問題的綜述性文章。近些年其他的研究熱點，如社交網(wǎng)絡(luò)分析[87-88]、醫(yī)療與衛(wèi)生系統(tǒng)[89-91]、網(wǎng)絡(luò)空間安全[92-93]、游戲AI[94-95]等同樣具有集群智能算法的身影。

4 集群智能理論研究

集群智能自誕生以來就廣受工業(yè)與學(xué)術(shù)界關(guān)注，一個重要的原因是其神秘的運行機制。其在很多問題上都能取得極優(yōu)秀的結(jié)果，但是學(xué)界始終不能揭示出這其中的理論基礎(chǔ)，這些困惑始終激勵著研究者對其進行更深入的研究。這些研究可以總結(jié)為三個主要問題：集群智能算法智能行為的產(chǎn)生機制；不同集群智能算法面對同一問題的性能表現(xiàn)不同的原因；在選定場景后，使集群智能算法性能最優(yōu)的設(shè)計方法。這些問題的任何一點進展都是集群智能優(yōu)化領(lǐng)域的極大突破，吸引研究者的持續(xù)投入。

研究者首先想要弄清楚，智能從何而來？已經(jīng)被學(xué)術(shù)界所知的是，集群智能這一特性并非所有種群都具有，它只存在于具有社會性特征的群居個體之間進行交互的活動中。研究者普遍從生物界出發(fā)研究這一問題，Bonabeau[3]研究了生物蟻群的覓食、運輸、分工等行為，并在分析后建模構(gòu)造了集群智能算法。更普遍的結(jié)論是由Kennedy等[96]給出的，他們研究了鳥群的協(xié)同運動后認(rèn)為：集群智能產(chǎn)生于社會交往，文化和認(rèn)知也是人類社交的結(jié)果。

智能產(chǎn)生于交互，那為什么在同一個問題中不同的集群智能算法性能差距如此巨大，即為什么一個集群智能算法在某些問題中要比其他集群智能算法好那么多？這一問題在宏觀上可以用“沒有免費的午餐（No Free Lunch）”原理解釋[97]，它表明了不存在任何一個優(yōu)化算法可以在所有場景中都優(yōu)于其他所有的算法。所以研究者轉(zhuǎn)而對算法特性做更深入的研究，首先就是對集群智能比傳統(tǒng)算法最大的優(yōu)勢特性——收斂性和計算復(fù)雜性的分析。其中最重要的研究之一就是對集群智能算法收斂性的分析，即研究在給定條件下算法能夠保證的收斂速度，包括馬爾可夫模型、不動點理論、變量分析、動態(tài)系統(tǒng)等模型都已用于這方面的研究[98]，如文獻[99-100]利用動態(tài)系統(tǒng)和 Logistic映射等方法研究了粒子群優(yōu)化，螢火蟲算法中保證算法收斂的參數(shù)值的范圍；文獻[101]則采用馬爾可夫鏈蒙特卡羅方法對集群智能算法內(nèi)部代理之間的交互建模進而研究其收斂性。

在理解不同算法對同一問題的性能差異后，還需要知道面對特定問題集群智能算法求解性能與問題建模方式之間有什么關(guān)系，或者說給定應(yīng)用場景后如何選擇設(shè)計策略使集群智能算法的性能最優(yōu)？有學(xué)者引入適應(yīng)度曲面分析[102]的方法，分析解空間與集群智能算法設(shè)計之間的關(guān)系，例如文獻[103]使用帶隨機游走的適應(yīng)度曲面分析方法選擇合適的啟發(fā)式算法用于解決蛋白質(zhì)結(jié)構(gòu)預(yù)測問題。然而，目前這些工作都是針對特定問題，難以用于推廣解決更一般的問題。

集群智能算法的搜索效率同樣是值得關(guān)心的問題，這一問題通常是研究算法搜索的收斂性和多樣性的平衡[104-105]。搜索候選解集的多樣性通常是算法成功找到最優(yōu)解的前提，但是多樣性的增加會導(dǎo)致收斂性降低并直接影響搜索效率。根據(jù)這一原則，目前的研究者主要是根據(jù)自己特定的問題需求調(diào)節(jié)參數(shù)[106]實現(xiàn)算法的高效率搜索。

5 結(jié)束語

近年來，關(guān)于集群智能算法的研究增長迅速，但是這一領(lǐng)域所遺留下的問題同樣很多。首先，學(xué)術(shù)界仍缺乏一個適用于所有算法的收斂性分析框架，雖然研究者提出了很多針對某些經(jīng)典集群算法，如粒子群優(yōu)化或蟻群優(yōu)化算法的收斂性分析方法，但是卻很難將之推廣到其他算法上。其次，針對特定問題，算法的參數(shù)選擇如種群大小、學(xué)習(xí)率等仍然只能依靠經(jīng)驗與實驗測試，而沒有確定性的理論指導(dǎo)。更重要的是，在集群智能算法性能對比中，還沒有一個研究工作是公認(rèn)的很好的方法，多數(shù)研究者在做性能測試時都只能對比給定計算結(jié)果所需的迭代次數(shù)或給定迭代次數(shù)下的計算結(jié)果，這樣的結(jié)果受算法參數(shù)和評估函數(shù)選取的影響極大，不具有推廣價值，還需要找到一個通用可推廣的集群智能算法性能評估方法。

未來針對集群智能算法的研究仍然以優(yōu)化應(yīng)用為主，但是理論研究所占的比重也將會逐步增加。沒有免費的午餐原理告訴我們，沒有單一的算法可以被指定為最佳算法，只要它經(jīng)過足夠多的問題的測試，總是會激勵研究人員開發(fā)新的計算智能算法。

總體而言，目前對集群智能的了解十分有限，任何一項微小的理論成果都是這一領(lǐng)域的巨大突破。雖然困難重重，但是需要相信不管未來如何發(fā)展，集群智能算法與集群智能研究都會在各領(lǐng)域扮演更加重要的角色。