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

唐志崇

（廣東工業大學計算機學院，廣州510000）

0 引言

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

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

1 算法

1.1 進化算法

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

（1）算法原理

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

（2）改進

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

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

基于取舍選擇的改進：這個環節的改進有輪盤法、選擇法等。

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

（3）應用

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

1.2 粒子群算法

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

（1）算法原理

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

（2）改進

基于參數設置改進：慣性權重系數w 的改進，實驗總結表明w 在0.8-1.2 之間會有較好收斂速度。此外還有基于算法結構的各個環節改進方案。

1.3 蟻群算法

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

（1）算法原理

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

（2）改進

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

（3）應用

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

1.4 人工魚群算法

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

（1）算法原理

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

（2）算法改進

人工魚群算法的參數是較多的，參數的設置也是依靠實驗總結的經驗，缺乏理論支撐。此外，魚群算法是一種個體集群搜索算法，有集群擁擠系數控制，這個系數前期要調大，后期調小。可以改善算法后期收斂的困難。

1.5 人工蜂群算法

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

（1）算法原理

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

（2）改進

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

1.6 其他算法

（1）細菌覓食算法

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

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

（2）烏鴉搜索算法

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

（3）狼群算法

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

（4）蝙蝠算法

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

（5）貓群算法

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

（6）蛙跳算法

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

（7）帝國競爭算法

利用殖民地初始覆蓋，然后向帝國中心（當前最優的一組解）移動中搜尋最優解。當帝國統一后，算法結束。顯然能否得到理論最優解太過于看運氣了。

（8）鴿群

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

（9）布谷鳥算法

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

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

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

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

群體智能的標準算法、改進的算法以及混合算法廣泛的應用函數優化領域、路徑規劃學、控制學、生產學、組合優化問題、深度學習、信號處理學、電力系統，成為工程優化的重要方法。在群智能發展的今天，各種算法的應用領域區別不大也沒必要區分。因為群體智能算法的本質是一樣的，都是在一個個測試適應值，模仿演化中向著最優解的方向尋找。

2 融合改進

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

（1）前沿研究

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

（2）收斂理論

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

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

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

3 結語

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

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