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

魏曉艷

摘 要： 粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）是一種高效、動態(tài)的優(yōu)化算法，該算法比較容易實現(xiàn)，也無需調(diào)整太多的參數(shù)；然而算法后期收斂速度慢，最主要的是易陷入局部極值，為了改善這些缺點，學(xué)者們紛紛提出了許多改進(jìn)的算法，并將其已經(jīng)應(yīng)用于科學(xué)和工程等多個領(lǐng)域。本文主要是在基本PSO的基礎(chǔ)上進(jìn)行改進(jìn)，提出了一種新的改進(jìn)算法—LPSO。最后通過仿真實驗證實，改進(jìn)后的算法在收斂速度和收斂精度上都得到了很大提高。

關(guān)鍵詞：粒子群 自適應(yīng) 早熟收斂 交叉操作

中圖分類號： TP301.6 文獻(xiàn)標(biāo)識碼：A 文章編號1672-3791（2015）06（a）-0000-00

Research on improved algorithm of particle swarm optimization

WEI Xiaoyan

（School of Engineering， Xi'an Siyuan University， Xian 710038，china）

Abstract： Basic PSO is an efficient and dynamic optimization algorithm， it is easy to achieve and don't need too much parameters adjustment； however， it has slow convergence， easily failing to local extreme values， in order to improve these disadvantages， some scholars have put forward a lot of improved PSO. In this paper， we introduce an improved PSO， and then prove it effective .

Key words： PSO； adaptation； Local convergence； crossover operation；

1 引言

在現(xiàn)實生活中，無論從事什么樣的職業(yè)，都會遇到優(yōu)化問題。隨著科技的不斷發(fā)展、世界的不斷變化，早前一些靜態(tài)的、傳統(tǒng)的方法，如單純形法、共軛梯度法、模式搜索法以及牛頓法等，已經(jīng)不能夠很好的處理一些復(fù)雜的問題，于是動態(tài)的、高效的粒子群算法（PSO）便成為了眾多學(xué)者研究的熱點【1】。

基本PSO算法雖然比較簡單，實現(xiàn)相對容易，不需要調(diào)整太多的參數(shù)，同時算法的早期收斂速度也比較快；但算法后期會受到隨機振蕩現(xiàn)象的影響，導(dǎo)致算法搜索到全局最優(yōu)解的時間比較長，減慢

了收斂速度；并且在一定程度上使其局部搜索能力表現(xiàn)較差，極易陷入局部最小值，精度降低，易發(fā)

散【2】。針對基本粒子群算法的收斂精度問題，本文提出了一種新的改進(jìn)粒子群優(yōu)化算法—LPSO。

2 改進(jìn)PSO算法研究

2.1 基本PSO算法

隨機初始一群粒子，每個粒子均不包括體積和質(zhì)量信息，將每個粒子都看作為優(yōu)化過程中的一個可行解，粒子的好壞通過一個事先設(shè)定好的適應(yīng)度函數(shù)來進(jìn)行確定。優(yōu)化過程中，每個粒子都將在可行解空間中進(jìn)行運動，由一個速度變量決定其方向和距離。通常情況下粒子將追隨當(dāng)前的最優(yōu)粒子，并經(jīng)過不斷的迭代搜索最后得到全局最優(yōu)解。在每一次迭代過程中，粒子都將會跟蹤兩個最優(yōu)值：一個是粒子本身迄今為止找到的最優(yōu)解，即局部最優(yōu)解；另一個是整個粒子群體到目前為止找到的最優(yōu)解，即全局最優(yōu)解【3】。

假設(shè)一個由個粒子組成的粒子種群在維的

搜索空間中按照一定的速度進(jìn)行飛行。粒子在時刻的狀態(tài)屬性設(shè)置如下：

位置：

其中為搜索空間的下限，為搜索空間的上限；

速度：

其中：為最小速度，為最大速度；

個體最優(yōu)值位置：

全局最優(yōu)值位置：

其中：，。

那么粒子在t+1時刻的位置可以通過下式來得到：

（1）

式中，、都為均勻分布在（0，1）區(qū)間的隨機數(shù)；、是學(xué)習(xí)因子，一般取2。

基本的PSO算法盡管比較簡單，實現(xiàn)也相對容易，并且不需要調(diào)整太多的參數(shù)，早期收斂速度快；但同時也存在其局限性，由于粒子在移動時沒有選擇性，即使下一個粒子位置的評價函數(shù)值較差，粒子還是利用逐個位置來代替當(dāng)前位置，這樣就使得粒子很容易跳出最優(yōu)解附近的某一鄰域，因此在一定程度上表現(xiàn)出較差的局部搜索能力，比較容易陷入局部最小值，降低了精度，也易發(fā)散【4】。鑒于基本粒子群算法還存在一些不足之處，本文提出了一種新的改進(jìn)的粒子群算法，下面將對其做具體介紹。

2.2 粒子群算法的改進(jìn)算法研究

本文所提出的改進(jìn)的粒子群算法主要是在基本粒子群算法基礎(chǔ)上，對以下幾個方面做了改進(jìn)：

1）慣性權(quán)重模型

由于慣性權(quán)重較大時，算法具有較強的全局搜索能力；較小時，則算法局部搜索能力較強。所以本文中采用線性模型，隨著迭代次數(shù)的增加，將由初始的0.9線性遞減至0.4，以達(dá)到期望的優(yōu)化目的。權(quán)重函數(shù)由下式確定：

（2）

式中為最大慣性權(quán)重，一般取0.9，為最小慣性權(quán)重，一般取0.4。

2）學(xué)習(xí)因子模型

學(xué)習(xí)因子、表示粒子向個體最優(yōu)值和全局最優(yōu)值進(jìn)化的隨機加速權(quán)值。當(dāng)、都等于0時，粒子會按照當(dāng)前速度進(jìn)行飛行，直到運動至邊界處。當(dāng)學(xué)習(xí)因子較小時，粒子將會在遠(yuǎn)離最優(yōu)值區(qū)域內(nèi)發(fā)生振蕩現(xiàn)象；較大的學(xué)習(xí)因子則可以促使粒子快速向最優(yōu)解區(qū)域內(nèi)移動。所以本文中采用自適應(yīng)模型，如下式所示：

（3）

式中為最大學(xué)習(xí)因子， 為最小學(xué)習(xí)因子，為最大迭代次數(shù)，t為當(dāng)前迭代次數(shù)。

3）粒子位置更新方程的改進(jìn)

基本PSO算法前期，精度較低，易發(fā)散。如果參數(shù)較大的話，在后期收斂速度會變慢，從而無法繼續(xù)進(jìn)行優(yōu)化。在進(jìn)化規(guī)劃中，算法中若帶有高斯變異和柯西變異算子時，算法都會取得較好的收斂效果，因此，本文中對個體最優(yōu)解加入了高斯算子，每次找到一個個體最優(yōu)值時，將在其周圍利用高斯算子進(jìn)行局部搜索。這樣不僅可以提高算法前期的收斂精度，還可以改進(jìn)算法后期的收斂速度，可以有效避免后期在最優(yōu)解附近發(fā)生振蕩。所以本文中的粒子位置通過下式來進(jìn)行更新：

（4）

式中，是均值為0，方差為1的高斯變量，是個粒子中的最小適應(yīng)函數(shù)值，即當(dāng)前最優(yōu)值，是尺度因子，通常取0.6。

4）早熟收斂的改進(jìn)策略

PSO運行過程中，如果其中一個粒子發(fā)現(xiàn)一個當(dāng)前最優(yōu)位置，此時其他的粒子會快速向其聚集。如果該最優(yōu)位置是個局部極值點，或者兩個粒子均處于局部極值點，此時整個粒子種群將不可能在解空間內(nèi)重新進(jìn)行尋優(yōu)，導(dǎo)致算法失去了搜索能力，陷入局部最優(yōu)，這一現(xiàn)象就稱為早熟收斂。本文對會與當(dāng)前最優(yōu)解重疊的粒子加入交叉操作過程，這樣可以使該粒子狀態(tài)重新更新，尋找新的搜索區(qū)域，從而跳出函數(shù)的局部極值點。首先給定一個閾值，如果其中一個粒子與當(dāng)前最優(yōu)粒子的位置距離小于之前設(shè)定的閾值，則對其進(jìn)行交叉操作。具體的交叉公式如下：

（5）

式中 是粒子位置，為粒子速度，是介于[0，1]之間的一個隨機數(shù)，為局部最優(yōu)解。

3 仿真實驗

1）粒子群算法性能比較仿真

為了驗證改進(jìn)粒子群算法的有效性，本文中選取標(biāo)準(zhǔn)的測試函數(shù)，分別利用基本粒子群算法和改進(jìn)后的粒子群算法對函數(shù)進(jìn)行優(yōu)化，尋找適應(yīng)度函數(shù)的最優(yōu)解。

測試函數(shù)：Griewank函數(shù)

（6）

式（6）中的表示一個粒子，為粒子的每個分量，為每個粒子的維數(shù)【3】。

首先在 [-10，10] 的區(qū)間內(nèi)均勻生成兩組數(shù)，作為初始的粒子種群，數(shù)的個數(shù)為生成粒子的個數(shù)，每個粒子都是二維的，則該函數(shù)的三維圖形如圖1所示。由圖可以看出：該函數(shù)存在多個局部極值點，但只存在唯一的全局最優(yōu)點在（0，0）處。

圖1 Griewank函數(shù)三維圖形

Fig.1 3D image of Griewank

本文在進(jìn)行仿真實驗過程中的相關(guān)參數(shù)設(shè)置如下：學(xué)習(xí)因子，，粒子個數(shù)n=100，粒子維數(shù)D=10，粒子位置范圍，最大迭代次數(shù)選取為100次，交叉操作過程中的閾值g取0.5，尺度因子取0.6。仿真結(jié)果如下，圖中描述的是函數(shù)的最優(yōu)適應(yīng)值與迭代次數(shù)之間的關(guān)系。

圖2 算法有效性比較結(jié)果

Fig.2 Comparison of the validity of two algorithms

由上述仿真結(jié)果可以看出，改進(jìn)的粒子群算法（LPSO）較基本粒子群算法，不管是收斂精度還是循環(huán)迭代次數(shù)，都有所提高，驗證了改進(jìn)算法的有效性。

4 結(jié)論

本文在基本PSO的基礎(chǔ)上，對參數(shù)的選擇進(jìn)行了調(diào)整，同時引入高斯算子及交叉操作過程。仿真結(jié)果證明，改進(jìn)后的算法收斂效果較好。

參考文獻(xiàn)

[1]. 張必蘭. 改進(jìn)的粒子群優(yōu)化算法及應(yīng)用研究[D].重慶大學(xué)，碩士學(xué)位論文， 2007.

[2]. 李麗，牛奔. 粒子群優(yōu)化算法[M].北京：冶金工業(yè)出版社，2009.

[3]. 吳進(jìn)華，吳華麗，周仕. 基于模擬退火的粒子群算法[J].儀器儀表學(xué)報，2008.

[4]. Yumao Li. Particle swarm optimization algorithm research and improvement [D]. Northwestern university master degree thesis，2009.

[5]. 任小波，楊忠秀. 一種動態(tài)擴散粒子群算法[D].寧夏工程學(xué)院，2010-01.

[6]. 劉逸. 粒子群優(yōu)化算法的改進(jìn)及應(yīng)用研究[D]西安電子科技大學(xué)，博士學(xué)位論文， 2013.