淺談群體智能算法

摘 要：本文介紹了群智能算法的特點，PSO的基本原理、算法的改進，特別對相關國際發展現狀進行了分析，讓初學者輕松入門；給出了國內外具有重要影響的各種改進形式，不僅可以讓初學者得到提高的機會，也讓資深讀者從中受到啟發。

關鍵詞：粒子群，群智能

1群體智能

1975年，美國Michigan大學的John Holland[1]教授發表了其開創性的著作《Adapatation in Natural and Artficial System 》，在該著作中作者對智能系統及其自然界中的自適應變化機制進行了詳細的闡述，并提出了計算機程序的自適應變化機制，該著作的發表被認為是群體智能[2]算法的開山之作。隨后John Holland 和他的學生對該算法機制進行了推廣，并正式將該算法命名為遺傳算法，遺傳算法的出現和成功，極大地鼓舞了廣大研究工作者向大自然現象學習的熱情。經過多年的發展，已經誕生出了大量的群體智能算法，包括：遺傳算法、蟻群算法，差異演化算法、粒子群優化算法等對智能系統及自然界中的自適應變化機制進行了詳細闡述。

群體智能算法的特點：

（1）智能型

群體智能算法通過向大自然界中某些生命現象或自然現象學習，實現對于問題的求解，這一算法中包含了自然界生命現象所具有的自組織、自學習和自適應等特點，在運算過程中，通過獲得的計算信息自行組織種群對解空間進行搜索。種群在搜索過程中依據事先設定的適應度函數值，采用適者生存、優勝略汰的方式進化，所以算法具有已經的智能性。

（2） 隱含本質并行性

群體智能算法通過設定相應的種群進化機制完成計算，而種群內的個體則具有一定的獨立性。個體之間完全是一種本質上的并行機制。如果使用分布式多處理機來完成群體智能算法，可以將算法設置為多個種群并分別放置于不同的處理機實現進化，迭代期間完成一定的信息交流就可以，迭代完成后，根據適應度進行優勝略汰。所以，群體智能算法這種隱含的本質并行性，能夠更充分利用多處理器機制，實現并行編程，提高算法的求解能力。更加適合目前云計算等分布式計算技術迅速發展的背景。

（3） 解的近似性

群體智能算法通常來對大自然中某種生命或其他事物的智能協作進化現象的模擬，利用某種機制指導種群對解空間進行搜索。由于該類算法缺乏嚴格的數學理論支持，對于問題的解空間采用反復迭代的概率性搜索，所以群體智能算法會存在早熟或解精度較低等問題，而這也是所有群體智能算法幾乎都存在的弱點，所以很多時候對求解的問題來說，群體智能算法僅僅得到的是是一種最佳解的近似解。

自然界中一些昆蟲的行為，如空中的鳥群和蜂群，地上的蟻群，水中的魚群，它們單個個體的結構都非常簡單，然而這些個體之間通過協同工作表現出來的行為能力卻十分復雜，這種群體的運動稱為群行為，研究人員受這些社會性生物群體行為的啟發，通過對它們的進化過程或覓食過程的模擬，建立了一系列解決最優化問題的新方法。

2.粒子群優化算法的兩種模式

Kennedy等人在觀察鳥群覓食的過程中注意到，通常飛鳥并不一定看到鳥群中其他所有飛鳥的位置和動向，往往只是看到相鄰的飛鳥的位置和動向。因此他在研究粒子群算法時，同時開發了兩種模式：全局最優（Gbest）和局部最優（Lbest）[3]。

3粒子群算法基本原理

粒子群優化算法最原始的工作可追溯到1987年Reynolds對鳥群社會系統Boids（Reynolds對其仿真鳥群系統的命名）仿真研究[6] 。通常，群體的行為可以由幾條簡單的規則進行建模，雖然每個個體具有簡單的行為規則，但是卻群體的行為卻是非常的復雜，所以他們在鳥類仿真中，即Boids系統中采取了下面的三條簡單的規則：

（1）飛離最近的個體（鳥），避免與其發生碰撞沖突；

（2）盡量使自己與周圍的鳥保持速度一致；

（3）盡量試圖向自己認為的群體中心靠近。

1995年Kennedy和Eberhart在Reynolds等人的研究基礎上創造性地提出了粒子群優化算法，應用于連續空間的優化計算中 。Kennedy和Eberhart在boids中加入了一個特定點，定義為食物，每只鳥根據周圍鳥的覓食行為來搜尋食物。Kennedy和Eberhart的初衷是希望模擬研究鳥群覓食行為，但試驗結果卻顯示這個仿真模型蘊含著很強的優化能力，尤其是在多維空間中的尋優。最初仿真的時候，每只鳥在計算機屏幕上顯示為一個點，而“點”在數學領域具有多種意義，于是作者用“粒子（particle）”來稱呼每個個體，這樣就產生了基本的粒子群優化算法[4]。

假設在一個D 維搜索空間中，有m個粒子組成一粒子群，其中第i 個粒子的空間位置為 ，它是優化問題的一個潛在解，將它帶入優化目標函數可以計算出其相應的適應值，根據適應值可衡量xi的優劣；第i個粒子所經歷的最好位置稱為其個體歷史最好位置，記為

相應的適應值為個體最好適應值 Fi ；同時，每個粒子還具有各自的飛行速度 。所有粒子經歷過的位置中的最好位置稱為全局歷史最好位置，記為 ，相應的適應值為全局歷史最優適應值 。在基本PSO算法中，對第n 代粒子，其第 d 維（1≤d≤D ）元素速度、位置更新迭代如式（1）、（2）：

（1）

（2）

4結論與展望

粒子群優化（PSO）是一種新興的基于群體智能的啟發式全局隨機搜索算法，具有易理解、易實現、全局搜索能力強等特點，為各個領域的研究人員提供了一種有效的全局優化技術。本文對PSO的基本原理、在科學與工程實踐領域，關心PSO的讀者的共同興趣所在是PSO本身，即“PSO是什么”和“有些什么樣的改進形式”，而“用PSO怎樣解決某個具體問題”則依賴于相應領域的專業知識[4]；為了讓盡可能多的國內讀者從中受益而不局限于具體的工業背景，綜述內容側重于對基本PSO原理、算法改進，特別是相關國際發展現狀進行分析。

由于PSO畢竟是一種新興的智能優化算法，在以下方面仍然值得進一步研究：但是由于提出時間不長，算法還缺乏深刻的理論分析和堅實的數學基礎， 還存在許多不完善的地方，還有很多問題有待進一步解決。（1）算法的理論分析。包括 PSO 算法的收斂性分析，魯棒性分析，計算復雜性分析，參數設置的理論分析以及如何避免陷入局部最優等問題。（2）與其他演化算法的結合。PSO 算法主要的一個缺點是容易陷入局部最優，因此如何與其他演化算法，比如遺傳算法，模擬退火算法，免疫算法，禁忌搜索算 法等等相結合，優勢互補，揚長避短，組成一個混和的高性能的優化算法，亦將是未來研究的一個熱點.（3）粒子群算法的生物學基礎。如何根據群體進行行為完善算法，將群體智能引入算法中，借鑒生物群體進化規則和進化的智能性也是學者關注的問題。（4）粒子群優化算法與其他進化類算法的比較研究。與其他進化算法的融合，如何讓將其他進化算法的優點和粒子群優化算法相結合，構造出有特色有實用價值的混合算法是當前算法改進的一個重要方向。

參考文獻：

[1]Holland，J.H.Outline for a logical theory of adaptive systems. J. ACM 9（3）， 297-314

[2王培崇，群體智能算法及其應用.北京：電子工業出版社，2015

[3]徐星，熱力學粒子群優化算法研究及其應用.天津： 天津大學出版社，2011

[4]趙波，曹一家.電力系統無功優化的多智能體粒子群優化算法.中國電機工程學報，第25卷第5期。

作者簡介：

林輝（1982-），男，陜西西安人，工程師，碩士，研究方向為網絡安全。