粒子群優(yōu)化算法綜述

趙乃剛 鄧景順

摘 要：粒子群優(yōu)化算法是一種新的群智能算法。它是受自然界中鳥群、魚群等生物的群覓食行為的啟發(fā)提出的。由于該算法結(jié)構(gòu)簡單、需要調(diào)節(jié)的參數(shù)少，容易實(shí)現(xiàn)，已被很多學(xué)者研究并應(yīng)用到了大量實(shí)際問題中。該文詳細(xì)介紹了粒子群算法的基本原理、主要改進(jìn)方法和在實(shí)際問題中的應(yīng)用。

關(guān)鍵詞：粒子群優(yōu)化 元啟發(fā)式算法 參數(shù) 應(yīng)用

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2015）09（b）-0216-02

粒子群優(yōu)化算法[1-2]是1995年由美國的心理學(xué)家Kenndy和電氣工程師Eberhart首次提出來的一種新型的并行元啟發(fā)式算法。該算法是模擬自然界鳥群、魚群等生物的群覓食行為中的相互合作機(jī)制從而找到問題的最優(yōu)解。由于它結(jié)構(gòu)構(gòu)造簡單、需要調(diào)節(jié)的參數(shù)較少、涉及的專業(yè)知識(shí)少、容易實(shí)現(xiàn)，因此已經(jīng)受到了國內(nèi)外大量研究人員的廣泛關(guān)注，并將它應(yīng)用到了許多實(shí)際問題中。其中包括多目標(biāo)優(yōu)化問題[3]、非線性整數(shù)和混合整數(shù)約束優(yōu)化問題[4]、信號(hào)處理[5]、神經(jīng)網(wǎng)絡(luò)訓(xùn)練[6]等。

該文首先介紹了標(biāo)準(zhǔn)粒子群算法的基本工作原理和算法迭代步驟，然后分別介紹了現(xiàn)今對(duì)粒子群算法的不同改進(jìn)方法和算法在現(xiàn)實(shí)生活中的實(shí)際應(yīng)用。在文章的結(jié)論中給出了粒子群算法下一步的研究方向。

1 標(biāo)準(zhǔn)粒子群算法

與其他的基于群體智能的算法相似，粒子群優(yōu)化算法也是通過群體中不同粒子之間的相互合作和相互競爭來實(shí)現(xiàn)在尋優(yōu)空間中的搜索過程以找到所求問題的最優(yōu)位置。粒子群算法首先隨機(jī)的初始化一群均勻分布在給定的尋優(yōu)空間中的粒子（種群規(guī)模一般為30），然后所有的粒子根據(jù)兩個(gè)極值來更新自身的速度：一個(gè)是個(gè)體極值（）；另一個(gè)是群體極值（）。目前廣泛使用的標(biāo)準(zhǔn)粒子群算法的數(shù)學(xué)描述為：設(shè)粒子群中粒子的總數(shù)為，粒子的維數(shù)為，算法的終止條件（即最大迭代次數(shù)）為，第個(gè)粒子在時(shí)刻的飛行速度和在搜索空間中的位置分別為，，粒子在時(shí)刻的個(gè)體極值和群體極值分別為 ， ， 。所有的粒子按照如下的更新方式在搜索空間中飛行以找到最優(yōu)解。

（1）

（2）

其中，為慣性權(quán)重系數(shù)，決定了上次迭代速度保留的多少。它是粒子群算法的重要參數(shù)之一。在粒子群算法中，可以通過調(diào)節(jié)它的大小來平衡算法的全局搜索和局部搜索的能力。研究分析表明，在粒子群算法的算法初期，選擇較大的慣性權(quán)重值可以使得算法有很強(qiáng)的全局搜索能力；而在粒子群算法的算法后期選擇較小的慣性權(quán)重值可以使得粒子逐漸收斂到全局最優(yōu)。因此，在很多改進(jìn)的粒子群算法中，慣性權(quán)重采用了線性遞減的方式進(jìn)行更新。，為算法的學(xué)習(xí)因子，它們分別影響著粒子的“自我學(xué)習(xí)”能力和“社會(huì)學(xué)習(xí)”能力。一般認(rèn)為，設(shè)置較大的，會(huì)使得所有粒子過多的在局部范圍內(nèi)徘徊，不利于算法的全局搜索；而設(shè)置較大的，則會(huì)使得粒子過早的陷入局部極值，降低解的精度。和是介于[0，1]之間的隨機(jī)數(shù)。標(biāo)準(zhǔn)粒子群算法的流程可以描述如下。

（1）設(shè)置種群規(guī)模、變量范圍、慣性權(quán)重、學(xué)習(xí)因子等參數(shù)，并隨機(jī)的初始化一群均勻分布在給定的尋優(yōu)空間中的粒子（包含速度和位置信息）。

（2）計(jì)算群體中各個(gè)粒子的適應(yīng)度值（即函數(shù)值）。設(shè)置第個(gè)粒子的適應(yīng)度值為它的當(dāng)前個(gè)體極值，所有粒子中的最好粒子設(shè)置為群體的全體極值。

（3）根據(jù)公式（1）、（2）更新每個(gè)粒子的速度和位置。

（4）對(duì)所有粒子，將其當(dāng)前的函數(shù)值與它以前找到過的最好位置進(jìn)行比較，如果當(dāng)前位置較好，則將個(gè)體最優(yōu)位置設(shè)置為這個(gè)粒子的位置，然后再對(duì)群體的全局極值更新。

（5）判斷給定的終止條件是否滿足。若滿足終止條件，停止搜索，輸出需要的結(jié)果；否則，返回（3）繼續(xù)搜索。

2 粒子群算法的改進(jìn)

粒子群算法本身也存在如下缺點(diǎn)。

（1）尋找到的最優(yōu)解可能是局部最優(yōu)解而不是全局最優(yōu)解。

（2）算法搜索初期收斂速度快而搜索后期收斂速度變慢。

（3）參數(shù)選擇的隨機(jī)性。

為此，研究者們針對(duì)這些缺點(diǎn)對(duì)粒子群算法做了不同方面的改進(jìn)。

2.1 添加壓縮因子

Clerc M等[7]將壓縮因子引入粒子群算法中，改進(jìn)了算法的速度更新方式，具體如下：

（3）

（4）

其中，。一般情況下，取4.1。壓縮因子的引入可以控制粒子群算法的收斂，使得粒子有機(jī)會(huì)搜索空間中不同的區(qū)域，并獲得高質(zhì)量的粒子。實(shí)驗(yàn)結(jié)果表明，它大大提高了粒子群算法的收斂速度和收斂精度。

2.2 協(xié)同粒子群算法

Vanden B F等人[8]提出了一種協(xié)同粒子群算法。該方法的具體步驟為：假設(shè)粒子的維數(shù)為，將整個(gè)粒子分為個(gè)小部分，然后算法分別對(duì)粒子的每個(gè)小部分（1維）分別進(jìn)行優(yōu)化，評(píng)價(jià)適應(yīng)度值后合并成一個(gè)完整的粒子。結(jié)果表明了算法在很多問題上有更快的收斂速度，取得了很好的結(jié)果。

2.3 粒子群混合算法

粒子群混合算法是在粒子群算法中引入其它算法的一些比較好的思想，以提高粒子群算法的性能。這些算法包括：磷蝦群算法、遺傳算法、蝙蝠算法、螢火蟲算法、差分進(jìn)化算法等。由于這些算法有自身的優(yōu)點(diǎn)，因此研究者們已經(jīng)將它們的思想與粒子群算法結(jié)合來提高粒子群算法的性能。

2.3.1 基于自然選擇機(jī)制的粒子群算法

Angeline P J [9]將自然界中的自然選擇機(jī)制引入粒子群算法中，形成基于自然選擇的粒子群算法。其核心思想為，當(dāng)算法更新完所有的粒子后，計(jì)算粒子的適應(yīng)度值并對(duì)粒子進(jìn)行適應(yīng)度值排序。然后根據(jù)排序結(jié)果，用粒子群體中最好的一半粒子替換粒子群體中最差的一半粒子，但是保留原來粒子的個(gè)體最優(yōu)位置信息。實(shí)驗(yàn)結(jié)果表明，自然選擇機(jī)制的引入增強(qiáng)了粒子的全局尋優(yōu)能力，提高了解的精度。

2.3.2 基于模擬退火的粒子群算法

高鷹等人[10]提出的基于模擬退火的粒子群算法是將模擬退火機(jī)制、雜交算子、高斯變異引入粒子群算法中，以便更好的優(yōu)化粒子群體。算法的基本流程是首先隨機(jī)的初始一組解，通過粒子群算法的公式（1）、（2）來更新粒子，然后對(duì)所有粒子進(jìn)行雜交運(yùn)算和高斯變異運(yùn)算，最后對(duì)每個(gè)粒子進(jìn)行模擬退火運(yùn)算。算法隨著迭代的不斷進(jìn)行，溫度逐漸下降，接受不良解的概率逐漸下降，從而提高了算法的收斂性。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的混合算法不僅保存了標(biāo)準(zhǔn)粒子群算法結(jié)構(gòu)簡單、容易實(shí)現(xiàn)等優(yōu)點(diǎn)，而且由于模擬退火的引入，提高了算法的全局搜索能力、加快了算法的收斂速度、大大提高了解的精度。

3 粒子群算法應(yīng)用

由于粒子群優(yōu)化算法結(jié)構(gòu)簡單、需要調(diào)節(jié)的參數(shù)少、需要的專業(yè)知識(shí)少、實(shí)現(xiàn)方式容易，它一經(jīng)提出，研究者們就開始嘗試將它應(yīng)用于各種自然科學(xué)和工程問題中去。如今，它已經(jīng)被廣泛的應(yīng)用于函數(shù)優(yōu)化、多目標(biāo)優(yōu)化、求解整數(shù)約束和混合整數(shù)約束優(yōu)化問題、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、信號(hào)處理等實(shí)際問題中。Tan Y等人[11]提出了一種新的混沌搜索策略，并將它引入粒子群算法中用于求解非線性整數(shù)和混合整數(shù)約束規(guī)劃問題。實(shí)驗(yàn)結(jié)果表明，新算法大大提高了算法的收斂速度和魯棒性；Ramadan Rabab M等人[12]將粒子群算法進(jìn)行了改進(jìn)并應(yīng)用到了人臉識(shí)別系統(tǒng)中；劉元等人[13]用粒子群算法來實(shí)現(xiàn)鋅電解優(yōu)化調(diào)度；原文林等人[14]提出了基于協(xié)同進(jìn)化的粒子群算法，建立了相應(yīng)的懲罰因子算法評(píng)價(jià)機(jī)制，并將它用于求解比較復(fù)雜的高維梯級(jí)水庫短期發(fā)電優(yōu)化調(diào)度，實(shí)驗(yàn)結(jié)果證明了該方法的可行性和高效性，從而為求解此類問題提供了一種新的途徑。

4 結(jié)語

粒子群算法一經(jīng)提出便引起許多學(xué)者的廣泛關(guān)注，由于它的諸多優(yōu)點(diǎn)，它已經(jīng)被改進(jìn)并廣泛的應(yīng)用于不同現(xiàn)實(shí)領(lǐng)域中，但該算法仍然存在著許多問題值得我們進(jìn)一步研究和探討。

雖然粒子群算法的性能在不同的改進(jìn)方法上有了顯著的提高，但有關(guān)粒子群算法的理論基礎(chǔ)、理論分析還很薄弱。因此，加強(qiáng)粒子群算法的理論分析是未來的一個(gè)重要研究方向。

針對(duì)粒子群算法易陷入局部最優(yōu)、收斂性差等缺點(diǎn)，尋找更好的改進(jìn)方法以提高其性能是必要的。

由于粒子群算法結(jié)構(gòu)簡單、容易實(shí)現(xiàn)，將它應(yīng)用到更多的實(shí)際問題中也是一個(gè)熱點(diǎn)。

參考文獻(xiàn)

[1] Poli R，Kennedy J，Blackwell T. Particle swarm optimization[J].Swarm intelligence，2007（1）：33-57.

[2] Kennedy J.Particle swarm optimization[M].Encyclopedia of Machine Learning.Springer US，2010：760-766.

[3] Reyes-Sierra M，Coello C A C.Multi-objective particle swarm optimizers：A survey of the state-of-the-art[J].International journal of computational intelligence research，2006，2（3）：287-308.

[4] He Q，Wang L.An effective co-evolutionary particle swarm optimization for constrained engineering design problems[J].Engineering Applications of Artificial Intelligence，2006，20（1）：89-99.

[5] Melgani F， Bazi Y.Classification of electrocardiogram signals with support vector machines and particle swarm optimization[J].Information Technology in Biomedicine，IEEE Transactions on，2008，12（5）：667-677.

[6] Zhang J R，Zhang J， Lok T M， et al.A hybrid particle swarm optimization–back-propagation algorithm for feedforward neural network training[J]. Applied Mathematics and Computation，2006，185（2）：1026-1037.

[7] Clerc M，Kennedy，Télécom F. The particle swarm-explosion， stability，and convergence in a multidimensional complex space[J].Evolutionary Computation，IEEE，2002，6（1）：58-73.

[8] Vanden B F，Engelbrecht A P.Using cooperative particle swarm optimization to train product unit neural Networks[C].IEEE International Joint Conference on Neural Networks，Washington D C，USA， 2001.

[9] Angeline P J.Evolutionary optimization versus particle swarm optimization： Philosophy and performance differences[J]. Lecture Notes in Computer Science，1998：601-610.

[10] 高鷹，謝勝利.基于模擬退火的粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究，2004（1）：47-50.

[11] Tan Y， Tan G， Deng S. Hybrid particle swarm optimization with chaotic search for solving integer and mixed integer programming problems[J].Journal of Central South University，2014，21（7）：2731-2742.

[12] Ramadan Rabab M，Abdel-Kader Rehab.Particle swarm optimization for human face recognition[C].IEEE International Symposiumon Signal Processing And Information Technology，ISSPIT2009，2009：579-584.

[13] 劉元，陽春華，李勇剛，等.粒子群算法在鋅電解優(yōu)化調(diào)度中的應(yīng)用[J].自動(dòng)化與儀表，2006（4）：11-14.

[14] 原文林，吳澤寧，黃強(qiáng)，等.梯級(jí)水庫短期發(fā)電優(yōu)化調(diào)度的協(xié)進(jìn)化粒子群算法應(yīng)用研究[J].系統(tǒng)工程理論與實(shí)踐，2012（5）：1136-1142.