群體智能算法的混合改進綜述

唐志崇

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

0 引言

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

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

1 算法

1.1 進化算法

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

（1）算法原理

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

（2）改進

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

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

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

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

（3）應(yīng)用

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

1.2 粒子群算法

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

（1）算法原理

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

（2）改進

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

1.3 蟻群算法

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

（1）算法原理

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

（2）改進

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

（3）應(yīng)用

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

1.4 人工魚群算法

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

（1）算法原理

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

（2）算法改進

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

1.5 人工蜂群算法

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

（1）算法原理

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

（2）改進

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

1.6 其他算法

（1）細菌覓食算法

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

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

（2）烏鴉搜索算法

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

（3）狼群算法

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

（4）蝙蝠算法

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

（5）貓群算法

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

（6）蛙跳算法

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

（7）帝國競爭算法

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

（8）鴿群

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

（9）布谷鳥算法

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

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

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

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

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

2 融合改進

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

（1）前沿研究

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

（2）收斂理論

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

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

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

3 結(jié)語

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

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