粒子群算法的基本理論及其改進(jìn)研究

黃珍+潘穎+曹曉麗

摘 要 粒子算法是一種隨機(jī)優(yōu)化的技術(shù)，它的理論來(lái)自于兩位博士在觀察鳥(niǎo)群尋找食物和魚(yú)群們學(xué)習(xí)行為中。這樣的理論，在世界上許多領(lǐng)域都被應(yīng)用的十分廣泛。而在優(yōu)化的過(guò)程之中，粒子群算法很多自己獨(dú)特的地方。比如它們需要調(diào)整的參數(shù)不多，結(jié)構(gòu)也不復(fù)雜，收斂速度快。文章著重介紹對(duì)粒子群算法在不同地方的不同作用，討論粒子群算法的改進(jìn)以及未來(lái)的粒子算法的發(fā)展。

關(guān)鍵詞 粒子群算法；學(xué)習(xí)因子；收斂性

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1671-7597（2014）05-0037-01

在1995年，Ebrhart博士和Kennedy博士在日常的學(xué)習(xí)觀察中發(fā)現(xiàn)鳥(niǎo)群在尋找自己的食物時(shí)，魚(yú)群的學(xué)習(xí)行為。粒子群算法是由幾種思想集合而成。它們分別是生命、鳥(niǎo)群覓食、魚(yú)群學(xué)習(xí)、群理論。它還吸納了進(jìn)化算法的特長(zhǎng)之處。標(biāo)準(zhǔn)粒子群算法也被稱為PSO，它的算法的基本原理十分簡(jiǎn)單，它所用到的參數(shù)也很少，在進(jìn)化初期收斂的速度很快，也相對(duì)容易被實(shí)現(xiàn)。很多學(xué)者對(duì)它有極大的關(guān)注，在它被第一次提出來(lái)的時(shí)候。它發(fā)展很快，短短的時(shí)間內(nèi)，就得到極大的發(fā)展。對(duì)于不同的需求方向，粒子群優(yōu)化算法有不同的應(yīng)用。訓(xùn)練博弈代理、圖像和數(shù)據(jù)聚類、優(yōu)化設(shè)計(jì)、模型選擇、生物信息學(xué)、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)與訓(xùn)練、模式識(shí)別、信號(hào)控制、函數(shù)優(yōu)化等等的方面。

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

粒子群算法被提出至今，就在數(shù)學(xué)家，工程師，物理學(xué)家，心理學(xué)家等等不同領(lǐng)域的人們中被進(jìn)行了無(wú)數(shù)次的分析，和無(wú)數(shù)次的實(shí)驗(yàn)中被進(jìn)行了無(wú)數(shù)次的變形和改造。這些不同領(lǐng)域的人們通過(guò)大量實(shí)驗(yàn)得到了十分有益的研究成果很大量有價(jià)值的經(jīng)驗(yàn)資料。他們也為粒子群算法的發(fā)展提出了很多值得注意的假設(shè)和合理的解釋基礎(chǔ)。這些珍貴的資料和合理假設(shè)大大推動(dòng)了粒子群算法的發(fā)展歷程。這些假設(shè)還為實(shí)際工業(yè)應(yīng)用開(kāi)辟了一個(gè)新天地。在第一屆國(guó)際群智能研討會(huì)在美國(guó)的印度第安納州開(kāi)展后，引起的極佳的反響。至此，每年都會(huì)舉辦一次群智能國(guó)際研討會(huì)。因?yàn)樘峁┝艘粋€(gè)平臺(tái)給所有研究它的人，關(guān)于PSO的論文如同雨后春筍般越來(lái)越多。甚至在我國(guó)，PSO的研究也被列為重點(diǎn)項(xiàng)目，并且我國(guó)的科研人員已經(jīng)在這個(gè)項(xiàng)目上取得驕人成績(jī)。

標(biāo)準(zhǔn)粒子群算法的算法和其他演化算法有很多共同之處，它的理論基礎(chǔ)來(lái)自群體，在一個(gè)群體范圍中將每一個(gè)個(gè)體的位置變化都是速度來(lái)體現(xiàn)的。在每個(gè)單獨(dú)的個(gè)體都會(huì)記錄自己曾經(jīng)到達(dá)的最佳位置在它自己的記憶單元之中。它會(huì)改變自己的位置和速度，改變位置和速度是由自己曾經(jīng)到達(dá)的最佳位置和其他粒子到達(dá)過(guò)的最佳位置來(lái)確定的，改變速度和位置從而趨向全局的最優(yōu)值的聚集加速過(guò)程。

在標(biāo)準(zhǔn)粒子群優(yōu)化算法中，它是要要求每一個(gè)粒子維護(hù)兩個(gè)向量。它的運(yùn)動(dòng)方向和它的速率決定著粒子自身的速度，而粒子所在的位置表示它的解在空間中所處的位置。對(duì)比遺傳算法，粒子群算法缺少了一些東西。它們是選擇算子、交叉算子和變異算子。在t+1時(shí)刻的速度以及在這個(gè)時(shí)間段時(shí)的位置更新公式為：

Vt+1lid=X@vtid+c1@r1@（pbesttid-xtid）+c2@r2@（gBesttgd-xtida）

Xt+lid=xtid+vt+lid

在上述公式之中，c1和c2是加速系數(shù)，也被我們叫做學(xué)習(xí)因子，而X是慣性權(quán)重，r1和r2是兩個(gè)（0，1）區(qū)間上的隨機(jī)數(shù)。

2 粒子群算法的流程

粒子群算法的基本計(jì)算流程是這樣的。第一步，任意初始化的種群中每次粒子自身的速度和粒子自身的位置。而且把單獨(dú)個(gè)體在曾經(jīng)達(dá)到的最佳值pBest設(shè)置為當(dāng)前位置，并且將群體中的最優(yōu)個(gè)體作為當(dāng)前的gBest。第二步，在每一次的進(jìn)化中，要去計(jì)算每個(gè)粒子的適應(yīng)度函數(shù)值。第三步，計(jì)算進(jìn)行到第三步。就到了非常重要的一步了，可能粒子會(huì)出現(xiàn)此時(shí)的適應(yīng)度函數(shù)值比歷史最優(yōu)值都要好，此時(shí)就可以用當(dāng)前的位置去替換這個(gè)個(gè)體的歷史最優(yōu)值位置。第四步，粒子在歷史上所達(dá)到的最優(yōu)值要比全局最優(yōu)值都還要好，就有可能發(fā)生全局的最優(yōu)值被代替的情況。第五步則是對(duì)每一個(gè)粒子的i的第d維的速度和位置要按照公式去更新計(jì)算。第六步是最后一步，在這個(gè)時(shí)候如果還沒(méi)有達(dá)成結(jié)束的條件，就要跳轉(zhuǎn)到第二步，否則輸出GBest并且結(jié)束計(jì)算。

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

對(duì)于不一樣的領(lǐng)域，粒子群算法得到了豐富的應(yīng)用。但同樣的，粒子群算法也由于自身的原因受到了很多的局限。比如在問(wèn)題的維數(shù)、粒子的個(gè)數(shù)、加速系數(shù)、慣性權(quán)重、迭次代次數(shù)等等方面的影響。這些不同方面的影響也許會(huì)導(dǎo)致一些問(wèn)題的產(chǎn)生。例如算法的收斂性，精確性都不能達(dá)到應(yīng)用的要求。要改變粒子群算法的性能，就要通過(guò)提高粒子群算法求解最優(yōu)精度問(wèn)題，粒子群算法是一種隨機(jī)性的算法，它在大多數(shù)時(shí)間里都被用于優(yōu)化問(wèn)題，但粒子算法容易進(jìn)入一個(gè)“怪圈”，它的特點(diǎn)是簡(jiǎn)單易懂。但它的不足之處也是因?yàn)樗膮?shù)少，所以容易得到局部最優(yōu)解。至以于，許多研究者在不同的方面對(duì)它進(jìn)行了深入的探討和改進(jìn)方法。要去改進(jìn)粒子群算法，他們從以下幾個(gè)大的方面入手。

1）混合其他智能優(yōu)化算法。當(dāng)我們?cè)谶M(jìn)行粒子群全算法時(shí)，我們計(jì)算的目的和使用進(jìn)化算法本質(zhì)上是一致的。但事實(shí)上，它們兩個(gè)之間存在著很大的不同之處，這是因?yàn)樗鼈冊(cè)诒唤⒅酰⑺鼈兊脑肀揪筒煌Ｆ浯危@兩種算法的技術(shù)方法也存在著很大的不同點(diǎn)。但這不能因?yàn)槟承┓矫婢驼J(rèn)為進(jìn)化算法沒(méi)有一點(diǎn)可取之處。相反的是它們有各自的優(yōu)點(diǎn)與缺點(diǎn)，并且粒子群算法與進(jìn)化算法這兩種方法被放在一起應(yīng)用的時(shí)候，我們就會(huì)得到一個(gè)非常準(zhǔn)確的計(jì)算結(jié)果。我國(guó)的高海兵研究員，就對(duì)此提出了廣義粒子群優(yōu)化模型，這個(gè)廣義粒子群優(yōu)化模型非常適用于解決一些特定的優(yōu)化問(wèn)題，比如組合優(yōu)化的問(wèn)題。廣義粒子群優(yōu)化模型在本質(zhì)上是符合粒子群優(yōu)化原則的。除此之外，它還有許多值得注意的技術(shù)優(yōu)勢(shì)。比如，廣義粒子群優(yōu)化模型的粒子會(huì)根據(jù)情況來(lái)設(shè)計(jì)更新策略。另外，粒子群算法也和微分進(jìn)化算法進(jìn)行混合，同樣也得到了很好的效果。

2）慣性權(quán)重改進(jìn)算法。當(dāng)慣性權(quán)重比普通值還要大的時(shí)候，在這個(gè)時(shí)候非常適合來(lái)進(jìn)行全局搜索。這是因?yàn)槭諗康乃俣群芸欤@樣不容易得到較為精確的結(jié)果，反之我們?cè)谶M(jìn)行局部搜索是會(huì)得到精確的結(jié)果，由于收斂速度慢且有時(shí)會(huì)局部的極值中。由于上述的種種問(wèn)題，研究員們?cè)趯?duì)慣性權(quán)重研究方向上分為了兩個(gè)策略，它們分別為線性策略和非線性策略。線性策略在計(jì)算方法上會(huì)減輕了經(jīng)典遞減策略的局限性，在計(jì)算方法的自身性質(zhì)上會(huì)得到極大的改善。

4 結(jié)束語(yǔ)

經(jīng)過(guò)上述的兩種的改進(jìn)方法，我們可以得到一個(gè)結(jié)論，那就是粒子群算法的改進(jìn)要從混合其他智能優(yōu)化算法和慣性權(quán)重改進(jìn)算法著手。粒子群算法在世界范圍內(nèi)得到了廣泛的應(yīng)用，而在現(xiàn)今的研究中，還有許多關(guān)于優(yōu)化的問(wèn)題需要對(duì)多個(gè)目標(biāo)同時(shí)進(jìn)行優(yōu)化，所以粒子群算法被利用到多目標(biāo)優(yōu)化問(wèn)題。這是未來(lái)粒子群算法研究的重點(diǎn)。

參考文獻(xiàn)

[1]金欣磊，馬龍華，吳鐵軍，錢積新.基于隨機(jī)過(guò)程的PSO收斂性分析[J].自動(dòng)化學(xué)報(bào)，2007（12）.

[2]劉建華，樊曉平，瞿志華.一種慣性權(quán)重動(dòng)態(tài)調(diào)整的新型粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用，2007（07）.

[3]李寧，孫德寶，鄒彤，等.基于差分方程的PSO算法粒子運(yùn)動(dòng)軌跡分析[J].計(jì)算機(jī)學(xué)報(bào)，2006（11）.endprint