唐志崇

（廣東工業(yè)大學計算機學院，廣州510000）

0 引言

群體智能從20 世紀80 年代一出現(xiàn)，就引起了多個學科領域研究人員的關注，在許多領域上發(fā)揮著重要作用。主要應用領域有函數(shù)優(yōu)化（目標函數(shù)可以是不可微的、多模型的、多組多目標的；搜索空間即可行域也可以是非線性或是不連續(xù)的。），以及可以把工程應用中能轉(zhuǎn)成目標函數(shù)來優(yōu)化的求解優(yōu)化問題。例如機器人學中路徑規(guī)劃、細胞機器的結(jié)構(gòu)優(yōu)化；控制學中的管道控制、導彈控制；生產(chǎn)學中的任務分配、經(jīng)濟調(diào)度指派；組合優(yōu)化NP 難問題中的TSP 問題、背包問題；深度學習中的模式識別、圖像處理、神經(jīng)網(wǎng)絡訓練、閾值分割、聚類分析、特征子集選擇；信號處理學中的電路設計、數(shù)字濾波器設計、布局優(yōu)化；多輸入多輸出電力系統(tǒng)，直流電機最優(yōu)控制等。相對于傳統(tǒng)的工程優(yōu)化算法（牛頓法，梯度下降法，共軛梯度下降法）；群體智能算法對目標函數(shù)和可行域的要求更低，可以在不連續(xù)、非規(guī)則、有噪音、無須導數(shù)或其他輔助信息的情況下，能更廣泛地應用在工程優(yōu)化中。此外，群體智能算法在操作上具有高度的并行性，更適合并行處理的新一代計算機體系結(jié)構(gòu)[1]。

群體智能算法大部分是從自然界的行為學習研究中獲得靈感啟發(fā)得來的，也叫做元啟發(fā)式算法，是一類分散自組織系統(tǒng)的集體智能行為算法的總稱。是一種可視為一組簡單的個體，其中個體與個體、個體與環(huán)境之間存在交互作用，沒有中心控制，簡單的規(guī)則最終卻能表現(xiàn)出智能的系統(tǒng)算法。是人類模擬自然界種群自組織與自適應機制求解問題同時保留著鮮明的生物特征的算法。目前主要的群體智能算法有粒子群算法、遺傳算法、蟻群算法、人工魚群算法、烏鴉搜索算法、人工蜂群算法、細菌覓食算法、狼群算法、還有較新的蝙蝠算法、貓群算法、蛙跳算法、帝國競爭算法、布谷鳥算法、鴿群算法等。本文從算法的原理介紹，參數(shù)、結(jié)構(gòu)的改進以及融合優(yōu)化和應用領域角度對已有的算法進行了分類綜述；并對這些算法改進進行了橫向?qū)Ρ确治?，提出了基于獎懲系?shù)的收斂理論，對未來的研究內(nèi)容和改進方向進行展望。

1 算法

1.1 進化算法

遺傳算法，差分進化，進化策略，進化規(guī)劃等都是演化計算的分支，統(tǒng)稱為進化算法。進化算法是以自然界中生物的進化過程為自適應全局優(yōu)化搜索過程的借鑒對象，而不同的角度出發(fā)來模擬生物進化過程衍生出幾種算法[2]。

（1）算法原理

初始化種群以及參數(shù)-交叉繁殖-變異操作-適值函數(shù)計算-取舍選擇-迭代重復后面的環(huán)節(jié)。差分進化與遺傳算法主要區(qū)別是取舍選擇環(huán)節(jié)的不同（是否讓父代參與）隨著算法的發(fā)展，這些區(qū)分界限也不重要了。

（2）改進

參數(shù)設置對算法的收斂性以及收斂速度影響較大，需要根據(jù)經(jīng)驗類確定相應的參數(shù)?；诔跏挤N群改進，張國輝提出了一種全局搜索遺傳算法，改進了初始化方法，提升了初始化質(zhì)量[3]。

基于遺傳算子改進：即是交叉繁殖與變異環(huán)節(jié)的改進。常用的交叉有很多（單點、多點、部分匹配、次序、循環(huán)）交叉[4]等。變異的改進是為了讓算法可以更好的跳出局部最優(yōu)，即是需要讓變異環(huán)節(jié)的操作步伐遠超過領域搜尋的步伐。

基于取舍選擇的改進：這個環(huán)節(jié)的改進有輪盤法、選擇法等。

基于適應值函數(shù)改進：在適應值函數(shù)可以求得變化率時，將變化率加入取舍選擇的衡量因素可以明顯改善算法的性能。此外，目標函數(shù)不等于適應值函數(shù)，目標函數(shù)需要經(jīng)過數(shù)學映射轉(zhuǎn)換成非負的適應著函數(shù)，如果能對適應值函數(shù)進行優(yōu)化減輕計算機運算，可以很大程度提升算法收斂時間。

（3）應用

進化算法的應用可以分成三大類：第一類是機器學習中的分類系統(tǒng)；第二類是組合優(yōu)化問題；第三類是復雜的函數(shù)優(yōu)化問題[5]。

1.2 粒子群算法

對比前面的進化算法，粒子群算法更具有種群多樣性。進化算法由于交叉環(huán)節(jié)，整個種群共享信息，以一個優(yōu)雅的姿勢向著最優(yōu)解的方向移動。粒子群算法中，個體受個體最優(yōu)與群體最優(yōu)的影響，算法結(jié)束后會留下很多有意思的方案，不會像進化算法因為迭代損失過程中的數(shù)據(jù)。

（1）算法原理

初始化種群以及參數(shù)-個體的適應值函數(shù)計算以及當前最優(yōu)值更新-代入標準公式生成下一代粒子的速度與位置-一直迭代到算法滿足結(jié)束條件。

（2）改進

基于參數(shù)設置改進：慣性權(quán)重系數(shù)w 的改進，實驗總結(jié)表明w 在0.8-1.2 之間會有較好收斂速度。此外還有基于算法結(jié)構(gòu)的各個環(huán)節(jié)改進方案。

1.3 蟻群算法

蟻群算法相比于前面的粒子群算法與進化算法有著獨特的演化策略。利用正反饋達到“能者多勞占得多”與適應值函數(shù)判斷有著一樣的作用；迭代的效果不一樣，不能使用迭代次數(shù)來判斷是否結(jié)束收斂。

（1）算法原理

初始化種群以及參數(shù)-算法運行生成螞蟻行程路線-信息激素更新地圖更新-根據(jù)新的地圖的信息素概率選擇路線。

（2）改進

舉例一種基于算法結(jié)構(gòu)的改進：多信息素的蟻群算法被提出，幾種信息素有著不同的更新策略與選擇概率系數(shù)。

（3）應用

蟻群算法的算法結(jié)構(gòu)演化策略是根據(jù)路徑短從而獲得正反饋，不能處理多目標函數(shù)的優(yōu)化，工程優(yōu)化和應用領域中也相應受限。

1.4 人工魚群算法

人工魚群算法相比于前面的算法，增加了一個行為選擇以及視距概念，是基于行為的自下而上策略的人工智能算法。

（1）算法原理

初始化種群（包括位置，各種數(shù)據(jù)）；個體根據(jù)視野選擇行動模式（覓食行為、群聚行為、追尾行為）；更新公示牌；迭代至次數(shù)滿足算法結(jié)束條件。

（2）算法改進

人工魚群算法的參數(shù)是較多的，參數(shù)的設置也是依靠實驗總結(jié)的經(jīng)驗，缺乏理論支撐。此外，魚群算法是一種個體集群搜索算法，有集群擁擠系數(shù)控制，這個系數(shù)前期要調(diào)大，后期調(diào)小?？梢愿纳扑惴ê笃谑諗康睦щy。

1.5 人工蜂群算法

作為早期的智能算法，在同類開創(chuàng)了分工策略；是第一個在種群內(nèi)部有著分工分類的算法，可以有效的保持了種群的多樣性，也為獎懲系數(shù)提供了新的表現(xiàn)。

（1）算法原理

初始化種群以及相關數(shù)據(jù)-分工分類（引領蜂、跟隨蜂、偵查蜂）-根據(jù)各個種類的規(guī)則更新數(shù)據(jù)以及閾值判斷（更換工種）-迭代至滿足算法結(jié)束條件。

（2）改進

文獻[6]提出了一種人工蜂群-差分算法；利用差分進化算法的思想，增加了一個淘汰環(huán)節(jié)，從而提升了算法性能。

1.6 其他算法

（1）細菌覓食算法

細菌覓食也是一個分行為的算法，趨化行為、復制行為、驅(qū)散行為。

算法原理：初始化種群以及參數(shù)-個體根據(jù)算法判斷選擇行為-迭代終止條件。很明顯，這個算法，有局部優(yōu)秀解時，會很快繁殖，在懲罰時，就會大概率留下這個局部的解。

（2）烏鴉搜索算法

初始種群數(shù)據(jù)-各個烏鴉根據(jù)視野選擇行為-更新各個烏鴉的收藏的解-迭代；烏鴉會搜素新的更好的解，也會回到自己最好的解，跟蹤、反跟蹤。

（3）狼群算法

狼群算法作為較新的群體智能算法，也是分工分類策略。簡略介紹如下：初始化種群以及參數(shù)-以適應值為主對種群個體等級調(diào)整（分工分類）-高等級決定搜素方向，低等級受高等級影響負責騷擾與包圍獵物-迭代至終止條件。

（4）蝙蝠算法

蝙蝠算法是針對“視野”的視距策略算法。主要特點表現(xiàn)在個體的位置不輕易改變，通過低頻率大振幅搜素獵物即是保持一個較大的步長、視距搜索領域；在發(fā)現(xiàn)較優(yōu)解時，小步長小視距搜索領域并移動到較優(yōu)解的位置。

（5）貓群算法

貓群算法是分行為策略算法，有搜尋模式、跟蹤模式、移動模式。此外輔助有線性變化追蹤，當個體貓群發(fā)現(xiàn)有一個步長內(nèi)變化較大的解時會追逐到解的位置，同時其他的個體有概率吸引過來。

（6）蛙跳算法

蛙跳算法有一個能保住種群多樣性的環(huán)節(jié)-劃分子群體。設置了步長判斷，在連續(xù)幾次迭代中的取舍選擇只對子群體起效，哪怕一個子群體在幾次迭代后都是適應值靠后的個體，也會保留了大部分。

（7）帝國競爭算法

利用殖民地初始覆蓋，然后向帝國中心（當前最優(yōu)的一組解）移動中搜尋最優(yōu)解。當?shù)蹏y(tǒng)一后，算法結(jié)束。顯然能否得到理論最優(yōu)解太過于看運氣了。

（8）鴿群

兩種行為模式：自行搜索或者參照其他鴿子移動。與貓群算法很像。

（9）布谷鳥算法

布谷鳥算法的核心是在一個有限的列表中存儲當前較優(yōu)的解，同時也會概率丟棄。很顯然，標準的布谷鳥算法的收斂性差。

煙花算法與上面的算法有著很大的區(qū)別，不屬于一類型算法。不在此闡述。

我們知道，最優(yōu)參數(shù)的設置是主要的優(yōu)化方法之一。以遺傳算法為例，交叉概率、變異概率、解群大小、最大迭代次數(shù)等都是影響著算法性能的因素。最優(yōu)參數(shù)設置是一個很復雜的問題，群體智能算法都是非線性智能計算模型，很難用數(shù)學方法來準確預測運行結(jié)果。求解實際問題時，主要憑經(jīng)驗確定[7]。

此外，群體智能算法主要改進思路是算法結(jié)構(gòu)改進。①對算法自身機構(gòu)的改進，如有周昊天提出的簡化粒子群優(yōu)化方法，直接用位置更新取代了速度更新。②融合其他群體智能算法改進，也就是混合算法將在后面單獨列出。

群體智能的標準算法、改進的算法以及混合算法廣泛的應用函數(shù)優(yōu)化領域、路徑規(guī)劃學、控制學、生產(chǎn)學、組合優(yōu)化問題、深度學習、信號處理學、電力系統(tǒng)，成為工程優(yōu)化的重要方法。在群智能發(fā)展的今天，各種算法的應用領域區(qū)別不大也沒必要區(qū)分。因為群體智能算法的本質(zhì)是一樣的，都是在一個個測試適應值，模仿演化中向著最優(yōu)解的方向?qū)ふ摇?/p>

2 融合改進

融合其他算法的混合算法其實是算法結(jié)構(gòu)改進的一種，結(jié)合其他算法可以很好的改善原算法的不足，提升算法的性能。群體智能算法（標準算法）都是在自然界一個部落群體中學習，并參照這個群體的行為制定一些簡單的規(guī)則，使得整個群體向最優(yōu)解的方向有序的前進。改進分類有兩個：①參數(shù)重設。②算法結(jié)構(gòu)改進。上一章的改進大部分都是參數(shù)重設和基于算法單個環(huán)節(jié)改進。在當前性能最好的是融合改進的混合算法。其中除了群體智能算法內(nèi)部的算法融合，常用于融合算法有混沌理論、量子理論、模擬退火、禁忌算法等。

（1）前沿研究

南云等提出了一種具有雙層結(jié)構(gòu)的交替迭代式遺傳模擬算法，為制定不確定裝備車間生產(chǎn)計劃與調(diào)度方式提供了一種合理解決方案。Li 等人[8]提出了一種遺傳禁忌算法。羅德[9]提出了一種粒子融合人工魚群算法，一部分運用粒子群算法，一部分運用魚群算法，當前最優(yōu)值的公告共用，從而提升收斂速度。人工蜂群混沌混合算法[10]被提出，可以利用混沌運動的隨機性，遍歷性，讓偵查蜂有著更好的全局搜索能力。文獻[11]提出了粒子群-細菌覓食混合算法，解決了細菌覓食算法的收斂慢的缺點。文獻[12]對細菌覓食算法的趨化行為作出改進，加入差分進化思想，可以更好的逼近最優(yōu)解。

（2）收斂理論

群體智能算法能夠在沒有中心控制，個體遵循簡單的規(guī)則，卻能在整個種群涌現(xiàn)智能。主要的核心在于迭代思想，在于每一次迭代后，對種群的個體適應值給出了獎勵或是懲罰。根據(jù)演化-達爾文思想，在若干次迭代后，就會涌現(xiàn)出向著更好的適應值群體演變。其中影響著演變速度的正是獎勵或者懲罰的程度即是獎懲系數(shù)。優(yōu)秀群體智能算法的獎罰系數(shù)應當在算法前期應當保持低的獎懲系數(shù)，可以保持種群的多樣性，同時緩慢的全局搜素；算法中期，獎懲系數(shù)緩慢加速上升，但總體還在較低的水平，算法可以避免陷入局部最優(yōu)解；在后期用較高的獎懲系數(shù)讓算法快速收斂到全局最優(yōu)值。

文獻[13]提到的試驗，粒子群算法的改進中將慣性權(quán)重參數(shù)w 設置從0.9 到0.4 線性下降使算法的性能得到明顯提升。慣性權(quán)重參數(shù)w 越大，個體越有自主性即少受當前最優(yōu)值影響，也等于個體表現(xiàn)不良受到的懲罰??；后期參數(shù)w 變小，個體受到當前最優(yōu)值的影響變大即是如果個體表現(xiàn)不良受到懲罰變大，同時表現(xiàn)最優(yōu)的個體及當前最優(yōu)吸引其他個體的能力變大即獎勵變大。

很多算法與模擬退火融合后總能提升性能，正是模擬退火的前期大概率不接受取舍選擇的結(jié)構(gòu)，獎懲系數(shù)較低。后期大概率接受取舍選擇的結(jié)果，獎懲系數(shù)較高。與禁忌算法融合的混合算法中，禁忌列表不讓吸引過多，也是獎罰系數(shù)調(diào)整的體現(xiàn)。因此，群體智能的融合改進的核心是獎罰系數(shù)的調(diào)整，使之符合算法前期保持種群多樣性，后期快速收斂。

3 結(jié)語

對于群體智能算法，應用領域十分廣泛，長久以來都是研究熱點。當今群體智能算法的發(fā)展已經(jīng)陷入瓶頸了。雖然陸續(xù)有新的算法出現(xiàn)，但再也無法模擬當年蟻群算法剛被提出來時的帶給學術(shù)界的震驚。重要的原因是，理論依舊弱于實驗數(shù)據(jù)，一個算法是否有更好的性能，總要通過基準函數(shù)測試或者具體實驗案例對比分析。這個跟我們認知模式是不符合的。

本文有選擇地介紹了群體智能算法的原理、改進方案，以及混合算法。提出了基于獎懲系數(shù)的收斂理論。需要經(jīng)過大量的實驗測試對比確定性能的提升；此外，還需要更進一步研究獎懲系數(shù)對收斂的量化表現(xiàn)。