粒子群優(yōu)化算法的改進(jìn)與應(yīng)用

【摘要】粒子群優(yōu)化算法是今年來快速發(fā)展的一種新的進(jìn)化算法。本文以標(biāo)準(zhǔn)粒子群優(yōu)化算法的缺陷為出發(fā)點(diǎn)，從不同的角度來展現(xiàn)粒子群算法的改進(jìn)方向和研究進(jìn)展。討論其在不同領(lǐng)域內(nèi)的應(yīng)用。最后對(duì)粒子群優(yōu)化算法的發(fā)展趨勢(shì)進(jìn)行了展望。

【關(guān)鍵詞】粒子群優(yōu)化算法；改進(jìn)算法及應(yīng)用；發(fā)展趨勢(shì)

1.前言

粒子群優(yōu)化（PSO）算法是由Kennedy和Eberhart在1995年共同提出的，是一種群智能優(yōu)化算法。PSO算法容易實(shí)現(xiàn)，并能有效的解決復(fù)雜優(yōu)化問題，所以發(fā)展速度很快。在標(biāo)準(zhǔn)PSO算法之外，還有很多改進(jìn)算法和混合優(yōu)化算法，在混合優(yōu)化算法方面，Morten[1]等提出將繁殖思想引入的混合粒子群算法，Narsuki[2]等人引入了變異操作并使用高斯分布確定變異粒子的新位置，Marinakis[3]等人設(shè)計(jì)了一種粒子群算法、貪婪隨機(jī)自適應(yīng)搜索和擴(kuò)展鄰域搜索策略相結(jié)合的混合算法用來求解TSP問題。本文首先介紹標(biāo)準(zhǔn)的PSO算法及一些改進(jìn)PSO算法，最后介紹改進(jìn)PSO算法優(yōu)化神經(jīng)網(wǎng)絡(luò)參數(shù)方面的應(yīng)用。

2.標(biāo)準(zhǔn)PSO算法

在N維空間中，粒子i在N維空間的位置表示為，飛行速度表示為，每個(gè)粒子都有一個(gè)由目標(biāo)函數(shù)決定的適應(yīng)值，并且知道自己到目前為止發(fā)現(xiàn)的最好位置（pbest）和現(xiàn)在的位置Xi。此外，每個(gè)粒子還知道到目前為止整個(gè)群體中所有粒子發(fā)現(xiàn)的最好位置（gbest）（gbest是gbest中的最好值）。粒子通過下面的公式來更新自己的速度和位置。

在式（1）（2）中，i=1，2，3，……M，M為粒子群的粒子最大數(shù)量。 Vi是粒子的速度；pbest和gbest如前定義；rand（）是介于（0、1）之間的隨機(jī)數(shù)；Xi是粒子的當(dāng)前位置。c1和c2是學(xué)習(xí)因子，通常取C1=C2=2。上述公式（1）（2）被視為原始PSO算法。

3.幾種改進(jìn)型PSO算法

標(biāo)準(zhǔn)PSO算法雖然收斂速度較快，但是存在著容易陷入局部最優(yōu)解、進(jìn)化后期收斂速度較慢、精度較差等缺陷。針對(duì)這些問題，許多專家學(xué)者對(duì)此進(jìn)行了深入的研究并提出相應(yīng)的改進(jìn)算法。

3.1 基于粒子狀態(tài)更新的改進(jìn)PSO算法

美國楊百翰大學(xué)的Christopher K. Monson和Kevin D.Seppi[4]針對(duì)算法的收斂速度問題提出了一種新的對(duì)粒子狀態(tài)的更新算法，即使用卡爾曼濾波來更新粒子的運(yùn)動(dòng)狀態(tài)，使得改進(jìn)后的算法的收斂速度有了較大的提高并且對(duì)獲取最優(yōu)解的概率沒有壞的影響。

在此文中引入的卡爾曼濾波器功能僅限于正常的噪聲分布、線性過度和傳感功能，因此由幾個(gè)常數(shù)矩陣和向量描述。給定的具體列向量Zi+1，卡爾曼濾波器用它來產(chǎn)生一個(gè)正態(tài)分布，而此多變量分布的參數(shù) mi+1和Vi+1由下列公式所決定：

其中，F(xiàn)和VX用來描述系統(tǒng)的轉(zhuǎn)換模型，H和VZ用來描述系統(tǒng)的傳感器模型，這組公式需要一個(gè)確定的起始點(diǎn)，用帶有參數(shù)M0和V0的正態(tài)分布表示。隨后粒子的狀態(tài)被一個(gè)分布表達(dá)：

上面的描述是如果怎么做卡爾曼濾波，從一個(gè)觀察向量zi產(chǎn)生mi，并獲得下一個(gè)確信的狀態(tài)（8）

卡爾曼群（KSwarm）依靠卡爾曼預(yù)測(cè)定義了粒子運(yùn)動(dòng)，每一個(gè)粒子保持對(duì)自身的mi，Vi和Ki等參數(shù)的追蹤。然后粒子根據(jù)卡爾曼濾波器和下列公式生成觀察：

c為[0，2）的均勻分布中的某值，并且公式的結(jié)果為行向量，完整的觀察向量是位置和速度的行向量的轉(zhuǎn)置矩陣構(gòu)成，這一結(jié)果通過公式（4），（5），（6）來計(jì)算mi+1和Vi+1。

取得濾波值后，使用公式（8）來獲取預(yù)測(cè)值，然后由參數(shù)和Vi+1來構(gòu)造正態(tài)分布，得到（11）

通過對(duì)Sphere，DejongF4，Rosebrock，Griewank和Rastrigin的優(yōu)化實(shí)驗(yàn)表明引入卡爾曼濾波來更新粒子狀態(tài)，能夠在不影響找到最優(yōu)解的概率的情況下大幅度提升收斂速度。

3.2 基于時(shí)變加速系數(shù)的改進(jìn)PSO算法（PSO-TVAC）

Asanga Ratnaweera，Saman K. Halgamuge和 Harry C. Watson，在Shi和Eberhart＼的基于時(shí)變權(quán)重的改進(jìn)PSO算法（PSO-TVIW）的基礎(chǔ)上針對(duì)參數(shù)C1和C2進(jìn)行優(yōu)化，得到基于時(shí)變加速系數(shù)的改進(jìn)PSO算法（PSO-TVAC），改進(jìn)后的算法可以避免過早的收斂于局部最優(yōu)解并且能夠在算法后期改進(jìn)算法的收斂性。

Shi和Eberhart給出的PSO-TVIW的權(quán)重因子公式：

其中和為起始和結(jié)束權(quán)重，iter表示當(dāng)前迭代次數(shù)，Maxiter表示最大允許迭代次數(shù)。

在根據(jù)公式（12）的基礎(chǔ)上，修改后的參數(shù)c1和c2表示為：

和c2i都是常數(shù)，iter表示當(dāng)前迭代次數(shù)，Maxiter表示最大允許迭代次數(shù)，通過Sphere，Rosebrock，Griewank，Rastrigin和Schaffer’s f6的優(yōu)化實(shí)驗(yàn)得到，當(dāng)參數(shù)c1從2.5到0.5，參數(shù)c2從0.5到2.5的時(shí)候，大多數(shù)測(cè)試函數(shù)的性能得到了改進(jìn)。優(yōu)化實(shí)驗(yàn)表明基于時(shí)變加速因此的改進(jìn)PSO算法可有效避免算法過早陷入局部最優(yōu)解。并且作者在上述基礎(chǔ)上進(jìn)行了兩種擴(kuò)展性探索，第一種是在PSO算法中引入“突變”概念作為性能改進(jìn)策略，得到算法“基于時(shí)變加速因子的‘突變’粒子群優(yōu)化算法”（MPSO-TVAC）；第二種是引入新概念“自組織分層粒子群優(yōu)化算法”（HPSO）作為性能改進(jìn)策略，得到算法“基于時(shí)變加速因子的自組織分層粒子群優(yōu)化算法”（HPSO-TVAC），這兩種算法在大多數(shù)測(cè)試函數(shù)的表現(xiàn)中都明顯優(yōu)于標(biāo)準(zhǔn)PSO算法。

3.3 增強(qiáng)型粒子群優(yōu)化算法（EPSO）

華南理工大學(xué)的陳國初等人針對(duì)PSO算法容易陷入局部最優(yōu)解的缺陷，通過對(duì)參數(shù)w的處理、最好粒子和最壞粒子的處理、防止陷入局部最優(yōu)解和穩(wěn)定性變差這三個(gè)方面的改進(jìn)，使得新得到的EPSO算法更容易找到全局最優(yōu)解。

對(duì)參數(shù)w的改進(jìn)后，其公式為

其中為搜索開始時(shí)最大的為搜索結(jié)束時(shí)最小的為迭代所進(jìn)行的步驟，為允許最大迭代步數(shù)。

對(duì)于最好粒子，ESPO算法采取讓最好粒子向適應(yīng)值變高的方向飛行，如果飛行一步后適應(yīng)值變差，則返回原位置重新搜索；對(duì)于最差粒子，EPSO算法使用歷史全局最優(yōu)粒子替代最差粒子。

4.改進(jìn)PSO算法在BP神經(jīng)網(wǎng)絡(luò)的應(yīng)用

高玉明、張仁津等人提出了一種利用GA-PSO算法優(yōu)化的BP神經(jīng)網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)流量預(yù)測(cè)的預(yù)測(cè)模型。傳統(tǒng)的BP神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)模型在網(wǎng)絡(luò)流量預(yù)測(cè)方面有著精度不夠、收斂速度慢等缺陷。

在文中，作者首先利用BP神經(jīng)網(wǎng)絡(luò)建立網(wǎng)絡(luò)流量預(yù)測(cè)模型，隨后使用GA-PSO算法對(duì)BP神經(jīng)網(wǎng)絡(luò)的初始權(quán)值和閥值進(jìn)行優(yōu)化，之后利用歷史數(shù)據(jù)進(jìn)行優(yōu)化測(cè)試。

文本中作者選用遺傳算法（GA）優(yōu)化的BP神經(jīng)網(wǎng)絡(luò)模型、粒子群優(yōu)化（PSO）算法優(yōu)化的BP神經(jīng)網(wǎng)絡(luò)模型和傳統(tǒng)的BP神經(jīng)網(wǎng)絡(luò)模型與GA-PSO算法優(yōu)化的神經(jīng)網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)，并對(duì)比模型的均方誤差MSE，結(jié)果如圖1所示。

通過對(duì)比樣本實(shí)驗(yàn)結(jié)果，能夠表明GA-PSO算法優(yōu)化的BP神經(jīng)網(wǎng)絡(luò)模型顯著的提高收斂速度。

5.結(jié)語

粒子群優(yōu)化算法是一種非常優(yōu)秀的優(yōu)化算法，經(jīng)過近20年的不斷發(fā)展，大量改進(jìn)的粒子群優(yōu)化算法已經(jīng)應(yīng)用到各行各業(yè)當(dāng)中。但是每個(gè)問題都與其他問題的不同之處，所以不可能有一種算法能夠滿足所有問題，因此多種優(yōu)化算法進(jìn)行交叉混合是一種非常適宜的選擇，對(duì)于具體的問題，我們需要針對(duì)問題的特點(diǎn)設(shè)計(jì)適合于問題的混合優(yōu)化算法。

參考文獻(xiàn)

[1]Lovbjerg M.，Thomsa. K.， and Krink T..Hybrid Particle Swarm Optimization with Breeding and Subpopulations[C].Proceedings of the Genetic and Evolutionary Computation Cinference，2001.

[2]Higashi N.，Iba H..Particle Swarm Optimization with Gaussian Mutation[C].Proceeding of the Swarm Intelligence Symposium， SIS2003 and IEEE，2003，2003：72-79.

[3]陳國初，俞金壽. 增強(qiáng)型粒子群算法及其在軟測(cè)量中的應(yīng)用[J].控制與決策，2005，20（4）：377-381.

[4]高玉明，張仁津.一種GA-PSO算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)流量預(yù)測(cè)[J].計(jì)算機(jī)應(yīng)用與軟件，2014，04：106-110.