粒子群算法的改進算法研究

魏曉艷

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

關鍵詞：粒子群 自適應 早熟收斂 交叉操作

中圖分類號： TP301.6 文獻標識碼：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 引言

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

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

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

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

2 改進PSO算法研究

2.1 基本PSO算法

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

假設一個由個粒子組成的粒子種群在維的

搜索空間中按照一定的速度進行飛行。粒子在時刻的狀態屬性設置如下：

位置：

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

速度：

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

個體最優值位置：

全局最優值位置：

其中：，。

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

（1）

式中，、都為均勻分布在（0，1）區間的隨機數；、是學習因子，一般取2。

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

2.2 粒子群算法的改進算法研究

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

1）慣性權重模型

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

（2）

式中為最大慣性權重，一般取0.9，為最小慣性權重，一般取0.4。

2）學習因子模型

學習因子、表示粒子向個體最優值和全局最優值進化的隨機加速權值。當、都等于0時，粒子會按照當前速度進行飛行，直到運動至邊界處。當學習因子較小時，粒子將會在遠離最優值區域內發生振蕩現象；較大的學習因子則可以促使粒子快速向最優解區域內移動。所以本文中采用自適應模型，如下式所示：

（3）

式中為最大學習因子， 為最小學習因子，為最大迭代次數，t為當前迭代次數。

3）粒子位置更新方程的改進

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

（4）

式中，是均值為0，方差為1的高斯變量，是個粒子中的最小適應函數值，即當前最優值，是尺度因子，通常取0.6。

4）早熟收斂的改進策略

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

（5）

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

3 仿真實驗

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

為了驗證改進粒子群算法的有效性，本文中選取標準的測試函數，分別利用基本粒子群算法和改進后的粒子群算法對函數進行優化，尋找適應度函數的最優解。

測試函數：Griewank函數

（6）

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

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

圖1 Griewank函數三維圖形

Fig.1 3D image of Griewank

本文在進行仿真實驗過程中的相關參數設置如下：學習因子，，粒子個數n=100，粒子維數D=10，粒子位置范圍，最大迭代次數選取為100次，交叉操作過程中的閾值g取0.5，尺度因子取0.6。仿真結果如下，圖中描述的是函數的最優適應值與迭代次數之間的關系。

圖2 算法有效性比較結果

Fig.2 Comparison of the validity of two algorithms

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

4 結論

本文在基本PSO的基礎上，對參數的選擇進行了調整，同時引入高斯算子及交叉操作過程。仿真結果證明，改進后的算法收斂效果較好。

參考文獻

[1]. 張必蘭. 改進的粒子群優化算法及應用研究[D].重慶大學，碩士學位論文， 2007.

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

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

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

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

[6]. 劉逸. 粒子群優化算法的改進及應用研究[D]西安電子科技大學，博士學位論文， 2013.