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

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

1群體智能

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

群體智能算法的特點(diǎn)：

（1）智能型

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

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

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

（3） 解的近似性

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

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

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

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

3粒子群算法基本原理

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

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

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

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

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

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

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

（1）

（2）

4結(jié)論與展望

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

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

參考文獻(xiàn)：

[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)無(wú)功優(yōu)化的多智能體粒子群優(yōu)化算法.中國(guó)電機(jī)工程學(xué)報(bào)，第25卷第5期。

作者簡(jiǎn)介：

林輝（1982-），男，陜西西安人，工程師，碩士，研究方向?yàn)榫W(wǎng)絡(luò)安全。