淺談群體智能算法

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

關(guān)鍵詞：粒子群，群智能

1群體智能

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

群體智能算法的特點：

（1）智能型

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

（2） 隱含本質(zhì)并行性

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

（3） 解的近似性

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

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

2.粒子群優(yōu)化算法的兩種模式

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

3粒子群算法基本原理

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

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

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

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

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

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

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

（1）

（2）

4結(jié)論與展望

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

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

參考文獻：

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

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

[3]徐星，熱力學(xué)粒子群優(yōu)化算法研究及其應(yīng)用.天津： 天津大學(xué)出版社，2011

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

作者簡介：

林輝（1982-），男，陜西西安人，工程師，碩士，研究方向為網(wǎng)絡(luò)安全。