基于親和力的動態自適應粒子群算法

摘要：針對慣性權重線性遞減粒子群算法(LDWPSO)不能適應復雜的非線性優化搜索過程的問題，提出了一種動態改變慣性權重的自適應粒子群算法（DCWAPSO），在該算法中引入親和力的概念，并根據它對粒子群算法搜索能力的影響，將慣性因子表示為親和力的函數在。每次迭代時算法可根據當前粒子群親和力的大小動態地改變慣性權重，從而使算法具有動態自適應性。對六個典型函數的測試結果表明， DCWAPSO算法的收斂速度明顯優于LDWPSO算法，收斂精度也有所提高。

關鍵詞：粒子群優化；慣性權重；親和力；自適應

中圖分類號：TP18 文獻標志碼：A 文獻標識碼：1009-3044(2008)33-1489-03

Dynamical Adaptive Particle Swarm Algorithm Based on Affinity

GAO Chao，CAI Xiao-nan

(School of Software Engineering in Tongji University， Shang Hai 201804， China)

Abstract: A new adaptive Particle Swarm Optimization algorithm with dynamically changing inertia weight (DCWAPSO) is presented to solve the problem that the linearly decreasing weight (LDWPSO) of the Particle Swarm Optimization algorithm cannot adapt to the complex and nonlinear optimization process. The affinity of the particle swarm is introduced in this new algorithm and the weight is formulated as a function of this factor according to its impact on the search performance of the swarm. In each iteration process， the weight is changed dynamically based on the current affinity value， which provides the algorithm with effective dynamic adaptability. The algorithm of LDWPSO and DCWAPSO are tested with six well-known benchmark functions. The experiments show that the convergence speed of DCWAPSO is significantly superior to LDWPSO ， and the convergence accuracy is increased.

Key words: particle swarm optimization (PSO); inertia weight; affinity; adaptability

1 引言

粒子群優化（Particle Swarm Optimization簡稱PSO）是由Kennedy和Eberhart[1]等提出的一類模擬群體（swarm）智能行為優化算法。其思想來源于對鳥群捕食行的研究，它與遺傳算法和蟻群算法相比，PSO有著算法簡單，容易實現，并且可調整參數少等特點，因此被廣泛地應用于結構設計[2]，電磁場[3]和任務調度[4]等工程優化問題。

在粒子群算法的可調整參數中，慣性權值是最重要的參數，較大的權值有利于提高算法的全局搜索能力，而較小的權值會增強算法的局部搜索能力，為了找到一種能在全局搜索和局部搜索之間取得最佳平衡的慣性權值選取方法，研究人員進行了大量的研究工作，先后提出了線性遞減權值（LDIW）策略[5]，模糊慣性權值（FIW）策略[6]，和隨機慣性權值（RIW）策略[7]。其中，FIW策略需要專家知識建立模糊規則，實現難度較大，RIW策略被用于求解動態系統，LDIW策略相對簡單且收斂速度快，因此被廣泛應用。

本文在遞減慣性權值的基本思想指導下，提出了一種新的基于親和力的自適應慣性權重，當親和力較小時表明粒子距離最優位置較遠，此時應使粒子較快地進入局部搜索，由此提出了一種新的動態自適應粒子群優化算法（DCWAPSO）。通過對六個粒子的測試，表明這種改進的PSO算法既保持了搜索速度快的特點，又提高了全局搜索的能力，搜索成功有了很大的提高。

2 基本的PSO算法及相關概念

PSO以模擬鳥的群體智能為特征，以求解連續變量優化問題為背景。在PSO中，每只鳥被稱之為一個粒子，每個粒子用其幾何位置和速度向量表示，在問題的求解中，每個粒子參考自己的既定方向，所經歷的最優方向和整個鳥群所公共認識到的最優方向來確定自己的飛行。

PSO是Kennedy和Eberhart[1]于1995年首先提出，采用下列的公式對粒子群進行操作：

(1)

(2)

其中i=1，2，…，m，d=1，2，…，D；學習因子c1，c2是非負常數；r1，r2是[0，1]間的隨機數，vid=[-vmax，vmax]；vmax是常數。文獻[8]對(1)作了如下的改動：

(3)

其中w為慣性系數，為非負數，第i個粒子用一個D維的向量xi=(xi1，xi2，…，xiD)表示，它在空間的飛行速度其用vi=(vi1，vi2，…，viD)表；第i個粒子迄今為止搜索到的最優位置用表示pi=(pi1，pi2，…，piD) ，整個粒子群迄今為止搜索到最優位置用pg=(pg1，pg2，…，pgD)表示。

迭代終止條件根據具體問題一般選為最大迭代次數或粒子群迄今為止搜索到的最優位置滿足預定最小適應閥值。方程(1)和(3)是基本的PSO算法迭代公式。

3 親和力的描述

親和力是粒子與pgd的匹配度量，親和力高表示該粒子與pgd較接近，反之較遠離pgd。我們通過計算親和性，以保證粒子的多樣性，下面我們給出新定義的免疫算法中的親和力的概念：

定義1：計算第i個粒子xi的第d維親和力：

（4）

其中Xmax，Xmin分別是優化變量的最大和最小值。第i個粒子總的親和力為各維親和力的平均值，即：

（5）

其中D為粒子的維數，可以看出Ai∈[0，1]。所有粒子的總親和力為：

（6）

4 非線性自適應慣性權重的構造

基本的PSO算法可看作是w=1的情況，可以為w選取合適的值，從而使算法的全局和局部的搜索能力之間達到最佳平衡，也可以在算法迭代過程中根據不同時期搜索的進展情況動態地調節w的取值。為了平衡算法的全局和局部搜索能力，Shi等[5]進一步提出了LDIW策略，即在迭代過程中線性地減小w的值，并表示為：

（7）

其中tmax為最大迭代次數；t為當前的迭代次數，wmax，wmin分別是初始慣性權重要的最大值和最小值，tmax是進化到最大迭代次數的取值。這里，我們給出一種動態自適應的非線性慣性權值遞減函數，具體表達式為：

（8）

這樣構造的目的是讓算法迭代的早期通過加速慣性權值的遞減速度來讓算法較快地進入局部搜索，因此算法的性能相對PSO的收斂非常快，所以應盡快地使算法進入局部搜索，才能獲得更好的求解效率。

5 動態自適應粒子群優化算法及其數值分析

算法DCWAPSO

Step1：隨機初始化粒子群中粒子的位置與速度

Step2：將粒子的pb設置為當前位置，pg設置為初始群體中最佳粒子的位置。

Step3：判斷算法收斂準則是否滿足，如果滿足，轉Step5；否則，執行step4。

Step4：對粒子群中的所有粒子，執行如下操作：

①根據式(1)，(2)，(3)更新粒子的位置與速度；

②根據式(4)，(5)，(6)，(8)計算出總的親和力，計算出動態自適應慣性權值，轉Step2；

Step5：輸出pg，算法運行結束。

本文利用上述提出的LDWPSO算法和DCWAPSO算法對下述的六個函數進行了實驗分析，在實驗中，我們取粒子規模為100，c1=c2=2，wmax=0.8，wmin=0.2，具體函數及參數為：

1）Sphere函數：

其全局最優值f(X*)=0，函數計算時取-100≤xi≤100，xmax=vmax=100 ，維數D=30。此函數對應得程序運行的終止條件是函數值為零，若迭代次數超過NC，認為失敗。在此程序中NC=5000。

2）Shaffer’sf7函數：

其全局最優值f(X*)=0，函數計算時取-100≤xi≤100，xmax=vmax=100 ，維數D=30。

此函數對應得程序運行的終止條件是函數值為零，若迭代次數超過NC，認為失敗。在此程序中NC=2000。

3）Rastrigrin函數：

其全局最優值f(X*)=0，函數計算時取-10≤xi≤10，xmax=vmax=10 ，維數D=30。

此函數對應得程序運行的終止條件是函數值為零，若迭代次數超過NC，認為失敗。在此程序中NC=1000。

4）Shaffer’sf6函數：

其全局最優值f(X*)=0，函數計算時取-100≤xi≤100，xmax=vmax=100。

此函數對應得程序運行的終止條件是函數值為零，若迭代次數超過NC，認為失敗。在此程序中NC=1000。

5）Griewank函數：

其全局最優值f(X*)=0，函數計算時取-100≤xi≤100，xmax=vmax=100 ，維數D=30。

此函數對應得程序運行的終止條件是函數值為零，若迭代次數超過NC，認為失敗。在此程序中NC=1000。

6）Rosenbrock函數

其全局最優值f(X*)=0，函數計算時取-30≤xi≤30，xmax=vmax=100 ，維數D=30。

此函數對應得程序運行的終止條件是函數值為零，若迭代次數超過NC，認為失敗。在此程序中NC=1000。

本文分別用上述給出的LDWPSO算法和DCWAPSO算法各自計算了20次，下面的表1-表6分別給出了六個函數在AMD Athlon XP-M 1700+256MDDR/30G計算機上運行計算的結果比較。

表1 Sphere函數（NC=5000） 表2 Shaffer’sf7函數（NC=2000）

表3 Rastrigrin函數（NC=1000）表4 Shaffer’sf6函數（NC=1000）

表5 Griewank函數（NC=1000） 表6 Rosenbrock函數（NC=1000）

上述表中nmax表示最大迭代次數，navg 表示平均迭代次數，tmax表示最大迭代時間，tavg表示平均迭代時間，k表示搜索到最優解的成功率，favg表示搜索得到最優值得平均值（前三個函數均搜索到最優值故此項均為零）。

下面我們給出分別用LDWPSO和DCWAPSO方法求解上述六個函數當n不同時，函數的平均值，如表7、表8、表9所示。

下面我們畫出了用LDWPSO方法和DCWAPSO方法搜索這幾個函數的極值所需迭代次數的相對的比較如圖1、圖2、圖3所示。

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”