群智能優化算法研究

摘要:群智能優化算法是一種新型的優化算法。該文介紹了幾種常見的群智能優化算法，包括粒子群優化算法、蟻群優化算法、人工免疫算法、人工魚群算法，分析了它們的優缺點及使用情況，提出了群智能優化算法的發展方向。

關鍵詞:智能優化算法;粒子群優化算法;蟻群優化算法;人工免疫算法;人工魚群算法

中圖分類號:TP18 文獻標識碼:A文章編號:1009-3044(2010)21-5845-02

Research on Swarm Intelligence Optimization Algorithm

WANG Da-jiang1， CAI Rui-ying2， XU Xin-wei1

(1.Army Command College， Experimental Operations Center， Nanjing 210045，China; 2.Nanjing University of Technology， Information Science and Engineering， Nanjing 210009， China)

Abstract: Intelligence optimization algorithm is a new type optimization algorithm. This paper presents several common Swarm optimization algorithms， such as particle swarm optimization algorithm， ant colony optimization algorithm， artificial immune algorithm and artificial fish swarm algorithm， suggests evolutional trend of intelligence optimization algorithm based on analyzing characteristics.

Key words: intelligence optimization algorithm; particle swarm optimization algorithm; ant colony optimization algorithm; artificial immune algorithm; artificial fish swarm algorithm

優化算法的研究是優化技術研究的關鍵內容，它基于某種思想和機制，通過一定的途徑或規則來得到滿足用戶要求的問題的解。傳統的優化算法有線性規劃和非線性規劃法、動態規劃法、網絡流優化算法等，其算法復雜度一般很大，只適于求解小規模問題，在實際工程中往往不適用。20世紀80年代以來，一種新穎的優化算法，如遺傳算法、模擬退火算法、蟻群算法、粒子群算法、人工免疫算法及其混合優化策略等，通過模擬或揭示某些自然現象或過程而得到發展，為那些傳統優化技術難以處理的組合優化問題提供了切實可行的解決方法。在優化領域，由于這些算法構造的直觀性與自然機理，因此通常稱作智能優化算法。

1 群智能優化算法

智能優化算法是模擬自然界生物系統，各個生物體依賴自身的本能，通過無意識的進化、尋優行為來優化生存狀態，以適應環境的依賴優化方法，具有許多與傳統優化算法不同的特點。智能優化算法根據其中個體的數量，可分為基于個體的和基于群的兩種，如，模擬退火算法是基于個體的，而蟻群優化算法、粒子群優化算法、人工免疫算法和人工魚群算法是基于種群的。以下對幾種常用的群智能優化算法作簡要研究。

1.1 粒子群優化算法

粒子群優化(Particle Swarm Optimization，PSO)算法是J.Kennedy和R.C.Eberhart于1995年提出的一種高效的群集智能協同優化算法，其基本思想來源于對鳥群社會模型的研究及行為模擬，以個體的協作與競爭來完成對復雜搜索空間內優解的搜索，即所有粒子根據個體經驗和群體經驗不斷調整自己的速度和位置，朝著個體最優和群體最優的目標飛行來完成更新優化，具有概念簡單，收斂速度快，可調參數少等優點，非常適用于復雜環境中的優化問題求解。但粒子群算法在后期難以維持種群的多樣性，而且易陷入局部極值。自提出以來，很多研究者從參數設置、收斂性、拓撲結構、與其它算法融合等角度對傳統PSO進行研究，并針對其不足提出了各種改進，以提高算法性能。如文獻[1]提出的動態離散粒子群優化算法較好地解決了動態環境下離散優化問題。文獻[2]提出的并行粒子群優化算法，較好地解決了網絡系統中具有異構性和動態性的資源分配優化問題。文獻[3]基于混沌思想模糊自適應參數策略的粒子群優化算法，有效提高了算法的收斂速度，改善了多維空間的全局搜索能力。目前，PSO已經廣泛的應用于函數優化，人工神經網絡訓練，模式識別，模糊控制、車輛調度等領域。

1.2 蟻群優化算法

蟻群優化(Ant Colony Optimization，ACO)算法是根據自然界中螞蟻群體尋優的行為提出來的一種全局啟發式優化算法，它是對真實蟻群協作過程的模擬，每只螞蟻在候選的空間中獨立搜索解，并在所尋得的解上留下一定的信息量。解的性能越好螞蟻留在其上的信息量越大，而信息量越大的解被再次選擇的可能性也越大。所有解上的初始信息量相同，隨著算法的推進，較優解上的信息量逐漸增加，最終收斂到最優解或近似最優解。該算法具有很強的發現較優解的能力、魯棒性強、易于計算機實現等優點，在動態環境下表現出高度的靈活性和健壯性，但也存在著一些問題，如需要較長的搜索時間，搜索速度慢，且容易出現停滯現象，不能對解空間進行全面搜索。人們針對其不足提出了多種改進，如文獻[4]提出的基于混合行為的自適應蟻群算法，通過引入具有多行為的混合螞蟻來擴大搜索空間，避免早熟和停滯現象。目前，蟻群優化算法在求解TSP問題、分配問題、job-shop調度問題等方面取得了大量較好的實驗結果。

1.3 人工免疫算法

人工免疫(Artificial Immune)算法是基于生物免疫系統提出的一種新型智能算法，它將要分析的數據看作抗原，將算法產生反映抗原特征的數據看作抗體，模擬免疫網絡抗體抗原之間的相互刺激和作用，按照一定的算法實現數據處理，該算法能夠有效提取目標函數的絕大部分局部峰值，并具備群體數量自動調節和實數編碼等優良特性，具有搜索效率高、維持多樣性好和學習記憶力強等優點，為優化問題提供了新穎的解決方法和途徑。但該算法頻繁地抽取疫苗和接種疫苗花費了大量時間，使效率低下;求解全局最優解需要的群體規模相對較大，從而增加了計算量。針對其不足，人們提出了多種改進，如文獻[5]提出的協作型人工免疫網絡模型，新增記憶細胞間的協作算子，實現記憶細胞之間既競爭又協作的新型關系，提高了收斂速度，縮短了執行時間，保證了全局尋優能力。目前，人工免疫算法已應用于控制、數據處理、優化學習和故障診斷等領域。

1.4 人工魚群算法

人工魚群(Artificial Fish Swarm)算法是基于動物行為的自治體尋優模式，通過模擬魚群的覓食和生存活動來實現在空間中尋求全局最優的一種新思路。該算法采用自下而上的設計方法，即首先構造人工魚的個體模型;用公告板記錄最優人工魚個體的狀態，確定行為評價方法和終止條件;個體在尋優的過程中自適應地選擇合適的行為;最后全局最優結果通過群體或某個個體表現出來。該算法具有良好的全局搜索力，并具有對初值、參數選擇不敏感、魯棒性強、簡單、易實現等優點。但也存在一些缺陷，如搜索精度不高，后期收斂慢等。針對不足，近年來人們提出了多種改進方法，如文獻[6]提出的簡化人工魚群算法，在一次迭代進化中同時根據人工魚覓食結果、種群中心位置和種群最優位置，調整下一步位置，從而增強了該算法的全局搜索能力，提高了運行速度。文獻[7]提出的基于變異算子的人工魚群算法，引入變異算子增加了群體的多樣性，避免了人工魚群算法陷入局部最優，并提高了收斂速度。目前，人工魚群算法在機器人路徑規劃、電力系統優化等方面得到了應用，取得了較好的使用效果。

2 總結與展望

各種群智能優化算法都有其應用的優勢與不足，從解決實際優化問題角度出發，融合不同類型機制的優化算法，充分發揮它們各自優勢，是解決問題的必然發展趨勢。近年來，國內外學者正是采用智能優化算法和傳統優化算法相結合、智能優化算法與智能優化算法相結合等各種混合算法，成功解決了大量實際工程問題 。但從現有的成果來看，這些智能融合算法很多都是針對具體問題來進行的，所解決的問題不同，其融合策略也就存在著很多差異，不具備系統性和一般性。因此，在現有成果的基礎上繼續進行深入研究，努力探索智能優化算法之間或與其他優化算法相融合的統一機制將是一個非常具有理論意義和應用價值的課題。

參考文獻:

[1] 羅桂蘭.動態離散粒子群優化算法[J].計算機工程與設計，2009，30(24):5708-5711.

[2] 李志潔.改進粒子群算法在網格資源分配中的優化[J].計算機集成制造系統，2009，15(12):2375-2382.

[3] 孫勇.基于混沌思想模糊自適應參數策略的粒子群優化算法[J].計算機應用研究，2010，27(1):39-41.

[4] 王運濤.基于混合行為的自適應蟻群算法[J].計算機仿真，2009，26(12):151-153.

[5] 劉麗.基于全局粒子群的協作型人工免疫網絡優化算法[J].模式識別與人工智能，2009，22(4):653-658.

[6] 王聯國.一種簡化的人工魚群算法[J].小型微型計算機系統，2009，30(8):1663-1667.

[7] 黃華娟.基于變異算子的人工魚群混合算法[J].計算機工程與應用，2009，45(33):28-30.

[8] 李福東.聯合循環發電系統燃料熱值智能優化控制[J].清華大學學報，2008，48(2):1737-1741.

[9] 劉波.融合粒子群與蟻群算法優化XML群體智能搜索[J].計算機研究與發展，2008，45(8):1371-1378.

[10] 黃平.改進的粒子群優化算法求解電力經濟調度[J].華中科技大學學報，2010，38(1):121-124.