群智能算法的混合策略研究

(廣東司法警官職業學院信息管理系，廣東 廣州510520）

群智能算法是以模擬群體生物行為為特征的仿生類進化算法，采用分布式計算機制、魯棒性強、可擴充性好、優化效率高、并且簡單易于實現，已在傳統NP問題求解和諸多優化領域中展現其卓越性能和巨大的發展潛力。蟻群算法和粒子群算法是最典型的群智能算法，蟻群算法是對螞蟻群落食物采集過程的模擬，適合于離散優化問題。粒子群優化算法則是模擬鳥群覓食過程，適合連續優化問題。這2種算法性能優越但也各存缺點，為了提高算法的優化性能，在算法引入其它啟發式算法已成為一個研究熱點，筆者在介紹蟻群算法和粒子群算法基礎上對上述算法的各種混合策略進行分析比較，為該問題的研究提供參考。

1 蟻群算法

蟻群算法(Ant Colony Algorithm，ACA）于20世紀90年代由Colorni等[1]提出，該算法模擬蟻群的群體協作覓食過程，由若干個螞蟻共同構造解路徑，通過在解路徑上遺留并交換信息素提高解的質量，進而達到優化的目的。

蟻群算法具有正反饋性、并行性、魯棒性等優點，特別適合于離散領域的優化，但該算法存在著初始信息素缺乏、收斂速度慢、容易陷入局部最優等缺點。針對這些缺點，很多學者在ACA中結合其他優化技術，產生一種新的混合優化算法，并將其應用于實際問題中，以進一步提高ACA的優化性能。

1．1 蟻群算法與遺傳算法混合

遺傳算法(Genetic Algorithm，GA）是一種強有力的自適應全局優化概率搜索方法，對于各種搜索問題都可以使用。劉立東等[2]提出了一類融入遺傳算法的混合蟻群算法：蟻群算法在每代進化中保留最優解和次優解的公共解集后引入遺傳操中的交叉算子和變異算子進行運算。交叉和變異操作擴大了解的搜索空間，避免陷入局部最優，對優秀解公共解集的保留則加快了算法收斂速度。丁建強等[3]采用遺傳算法生成信息素分布，利用蟻群算法求精確解，優勢互補。高尚等[4]提出的混合算法是首先由遺傳算法產生較優解，較優路徑上留下信息素，其他不改變。蟻群算法完成一次遍歷后，再作遺傳算法的交叉和變異操作，如果交叉和變異后得到的解得到改善，則代替原來路徑。

1．2 蟻群算法與模擬退火混合

模擬退火算法(Simulated Annealing，SA）是一種典型的局部搜索算法，其具有的突跳能力能有效幫助ACA跳出局部最優。主要混合策略有以下2種：①在模擬退火算法中運用蟻群算法思想找鄰域的解；②采用模擬退火生成信息素分布，蟻群算法尋優過程中采用模擬退火在鄰域內找另外一個解。

1．3 蟻群算法與差分演化結合

差分演化算法(Differential Evolution，DE）是一種基于種群的并行隨機搜索算法，該算法從初始種群開始，通過交叉、變異和選擇等操作生成新種群，不斷進化以搜索全局最優解。差分演化算法擅長連續問題的優化，蟻群算法控制參數連續變化，可以利用DE對其進行參數優化，進而改善蟻群算法的性能。崔嬌等[5]將差分演化算法應用到蟻群算法的參數選取中，將蟻群算法的參數作為差分演化算法解空間的向量元素，自適應地尋找蟻群算法最優參數組合的同時求解問題的最優解。新算法對于蟻群算法中的參數進行自適應調整，避免了大量盲目測試，而且擴大了蟻群算法的搜索空間，提高了全局搜索能力。此外，蟻群算法還可以與禁忌搜索、集束搜索、模糊系統、免疫系統等結合以提高算法優化性能。

2 粒子群算法

粒子群優化算法(Particle Swarm Optimization，PSO）是繼蟻群算法后，由Kennedy等[6]于1995年提出的另一種著名群智能算法，該算法是受鳥群覓食行為的啟發而提出的。PSO是一種基于群體迭代的啟發式算法，其基本思想是隨機初始化一群粒子，每個粒子視為優化問題的一個可行解，粒子的質量由適應度函數確定。粒子以一定速度追隨當前的最優粒子在可行解空間中探索，通過迭代得到最優解。在每一代中，粒子通過跟蹤本身所找到的最優解和整個種群目前找到的最優解來進行更新。

標準PSO模型中，設搜索空間為D維，粒子數為n，第i個粒子位置表示為向量Xi＝（xi1，xi2，…，xid，…，xiD），飛行速度為Vi＝(vi1，vi2，…，viD），其歷史最優位置為Pi＝(pi1，pi2，…，piD），Pg為所有Pi（i＝1，…，n）中的最優。每個粒子的位置按式（1）和（2）進行更新：

式中，c1和c2為加速因子；rand（）為[0，1]間的隨機數；ω為慣性因子。

粒子群初始位置和速度隨機產生，然后進行迭代，直至找到最優解。實現步驟如下：①初始化粒子群，隨機產生每個粒子的位置和速度；②計算每個粒子的適應度；③對每個粒子，將其適應度值與pid比較，如果較好，則替換pid；④對每個粒子，將其適應度值與pgd比較，如果較好，則替換pgd；⑤更新每個粒子的速度和位置；⑥如果滿足約束條件(誤差足夠好或達到最大循環次數）退出，否則返回②。

粒子群算法概念簡單、容易實現、可調參數少，而且具有擴展性，容易與其他算法結合，適用于處理連續優化問題。但是該算法存在著容易早熟收斂、局部尋優能力差以及搜索性能對參數設置具有依賴性等缺點。很多學者嘗試在PSO中結合其他啟發式算法，以克服傳統PSO的不足，提高算法整體性能。

2．1 蟻群算法與粒子群算法混合

將粒子群算法引入到蟻群算法中，讓螞蟻也具有粒子的特性。兩者融合不僅可以提高數據搜索的范圍而且可以避免早熟，在時間效率上優于蟻群算法，在求解精度上優于粒子群算法。支成秀等[7]利用粒子群算法較強的全局搜索能力，經過一定的迭代次數得到問題的次優解，利用問題的次優解調整蟻群算法中的信息素的初始分布，再利用蟻群算法的正反饋機制求出問題的精確解，從而提高時間效率和求解精度。高尚等[4]提出的算法首先通過蟻群算法進行搜索，然后用粒子群算法對蟻群算法得到的有效路徑進行調整：將每只螞蟻的當前路徑分別與全局最優和個體最優交叉，然后以一定概率變異，如果新路徑的目標函數較優，則接受新值，否則拒絕。

2．2 粒子群算法與遺傳算法結合

Angeline[8]提出了混合群體，首次將GA的錦標賽選擇算子結合到PSO中，通過保留具有較高適應值的粒子進行復制來加快收斂速度，但仍然容易陷入局部最優。Lovbjerg等[9]提出了帶有繁殖和子種群的混合PSO算法，在每次迭代中按交叉率選擇一定數量的粒子放入一個池中，池中粒子隨機兩兩交叉，產生具有新的空間坐標和速度的子代以取代父代，并且把種群分為若干子種群，交叉可以在同一子種群內進行，也可在不同種群間進行。該混合算法使粒子增強搜索能力，易于跳出局部最優。Ratnaweera等[10]則將GA的變異算子引入到PSO中，將粒子與當前最優距離小于一定值時，按一定變異率讓粒子隨機初始化，該算法保證了群體的多樣性。鐘文亮[11]等針對PSO在優化多峰函數時容易早熟的缺點，在PSO中引入啟發性變異機制，擴展了算法的搜索區域，提高了算法的速度和精度且不容易陷入局部最優。

2．3 粒子群算法與模擬退火結合

PSO早期時收斂速度快，但后期受隨機振蕩現象的影響，容易停滯于局部最優點。為解決該問題，在PSO中引入SA后可以跳出局部最優。高鷹等[12]提出以PSO為主體運算流程，引入模擬退火機制，并混合了基于遺傳算法思想的雜交運算和帶高斯變異的SA-PSO算法。在保持PSO算法簡單容易實現基礎上，提高PSO算法擺脫局部極值的能力，避免算法陷入局部最優，提高算法的收斂速度和精度。王聯國等[13]把SA引入到PSO算法中，提出了一種混合優化算法。該算法在各溫度下依次進行PSO和SA搜索，結合了PSO的并行搜索和SA的概率突跳性的特點，從而有效防止PSO算法陷入局部極小。

2．4 粒子群算法與差分演化結合

許多學者嘗試把PSO和DE的優點結合起來實現逃離局部最優點。池元成等[14]提出的混合算法首先利用DE的變異和選擇算法產生新的群體，然后使用PSO和交叉、選擇算法進行局部搜索。李麗等[15]提出了一種新型的混合全局優化算法，即采用雙種群進化策略，其中一個種群按PSO操作進化，另一個種群按DE操作進化，每次進化過程中通過信息交流搜尋信息，以避免各種群陷入局部最優。倪霖等[16]通過在PSO種群和DE種群之間建立一種信息交流機制，使信息能夠在兩個種群中傳遞，以避免個體因錯誤的信息判斷而陷入局部最優點，并通過實例驗證了算法在資源受限項目調度優化問題上的有效性。

此外，粒子群算法還可以結合混沌優化、進化策略和進化規劃等技術提高性能。

3 結 語

各種群智能算法都有其自身特點和獨特優勢，但同時也存在各種不足。對于不同的優化問題，采用單一的優化算法往往在運行速度或優化精度上難以獲得滿意的效果。根據各優化算法的優缺點，采用一定的混合策略使各種算法形成優勢互補關系，從而提升算法性能和拓寬算法應用領域。

[1]Colorni A，Dorigo M，Theraulaz G．Swarm intelligence：From natural to artificial systems [M]．New York：Oxford Universyty Press，1999．

[2]劉立東，蔡淮．融入遺傳算法的混合蟻群算法 [J]．計算機工程與設計，2008，29（5）：1248-1252．

[3]丁建立，陳增強，袁著祉．遺傳算法與螞蟻算法的融合 [J]．計算機研究與發展，2003，40（9）：1351-1356．

[4]高尚，楊靜宇．群智能算法及其應用 [M]．北京：中國水利水電出版社，2006：108-111．

[5]崔嬌，黃少榮．基于差分演化的自適應參數控制蟻群算法 [J]．計算機工程，2011，37（6）：190-193．

[6]Kennedy J，Eberhart R．Particle Swarm Optimization [R]．IEEE International Conference on Neural Networks，Piscataway，NJ：IEEE Service Center，1995：1942-1948．

[7]支成秀，梁正友．融合粒子群優化算法與蟻群算法的隨機搜索算法 [J]．廣西科學院學報，2006，22（4）：231-233．

[8]Angeline P J．Using selection to improve particle swarm optimization [A]．Proc of the IEEE International Conference on Evolutionary Computation [C]．Piscataway，NJ：IEEE Service Center，1998：84-89．

[9]Lovbjerg M，Rasmussen T K，Krink T．Hybrid particle swarm optimizer with breeding and subpopulations [A]．Proceedings of the Genetic and Evolutionary Computation Conference [C]．San Francisco，2001：469-476．

[10]Ratnaweera A，Halgamuge S．Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients[J]．Evolutionary Computation，2004，8(3）：240-255．

[11]鐘文亮，張惠森，張軍，等．帶啟發性變異的粒子群優化算法 [J]．計算機工程與設計，2008，29（13）：3402-3406．

[12]高鷹，謝勝利．基于模擬退火的粒子群優化算法 [J]．計算機工程與應用，2004，40（1）：47-50．

[13]王聯國，洪毅，趙付青，等．一種模擬退火和粒子群混合優化算法 [J]．計算機仿真，2009，25（11）：179-182．

[14]池元成，方杰，蔡國飆．基于差分進化和粒子群優化算法的混合優化算法 [J]．計算機工程與設計，2009，30（12）：2963-2965．

[15]李麗，牛奔．粒子群優化算法 [M]．北京：冶金工業出版社，2009．

[16]倪霖，段超，賈春蘭．差分進化混合粒子群算法求解項目調度問題 [J]．計算機應用研究，2011，28（4）：286-1289．