具有量子行為的粒子群優化算法慣性權重研究及應用

摘 要：在研究慣性權重對基本PSO算法影響的基礎上，根據慣性權重對粒子群算法影響的特點，采用4種慣性權重策略對一種新的具有量子行為的粒子群算法的速度進行調節，比較每種算法的性能，從中找到一種新的性能更好的改進算法，將其用于求解0-1背包問題。實驗結果表明較好地選擇慣性權重參數對算法的性能有很大提高，該改進算法在求解0-1背包問題中具有高效性，提高了最優解的精度，同時具有較快的收斂速度。

關鍵詞：粒子群優化算法；量子行為；慣性權重；遞減策略；0-1背包問題

中圖分類號：TP3016文獻標識碼：B文章編號：1004373X(2008)2015903

Application and Study on Inertia Weight in Particle Swarm Optimization with

Quantum Behavior

HE Wei，QIU Yijiao，TANG Puying

(School of Opto-electronic Information，University of Electronic Science and Technology of China，Chengdu，610054，China)

Abstract：The effect of inertia weight on Particle Swarm Optimization(PSO) is studied，on basis of which adopts f_our kinds of strategies of inertia weight to regulate the speed of a new Quantum Delta Potential Well based Particle Swarm Optimization(QDPSO).A faster and more stabile algorithm，f_ound by comparing the performances of f_our equations regulated the inertia weight，solves 0/1 knapsack problem.The result of experiment shows that the modified algorithm improves the precision of optimal solution and has a faster speed and a higher efficiency in convergence.In a word，choosing a parameter of inertia weight suitably can improve the performance of new QDPSO.

Keywords：particle swarm optimization;quantum behavior;inertia weight;decreasing strategy;0/1 knapsack problem

粒子群優化(PSO)算法是一種群智能優化算法，最早由Kennedy和Eberhart于1995年共同提出，其基本思想是對鳥群捕食行為的仿生模擬^［1］，通過鳥群之間的集體協作，快速搜尋并找到最優解。其基本的進化方程如下：

vt+1=vt+c1·r1(Pt-xt)+c2·r2(Pg-xt)(1)

xt+1=xt+vt+1(2)

其中，r1，r2∈［0，1］為均勻分布的隨機數；C1，C2均是正常數；t表示進化代數；Vt，Xt分別表示每個粒子的速度和位置；Pg，Pt分別是粒子群的全局最優和個體最優。

為了改善基本PSO算法的收斂性能，Y·Shi等人提出了慣性權重的方法^［2］和用模糊控制器來動態自適應地改變慣性權重的技術^［3］。之后Jun Sun等人提出的具有δ函數形式的粒子群算法^［4］(QDPSO) 使粒子群算法的計算更加簡單容易。最近一種新的QDPSO 算法^［5］ 考慮了速度對位置的影響，通過速度的更新選擇位置的更新方程。在經典粒子群算法的可調整參數中，慣性權重是非常重要的參數，較大的權重有利于提高算法的全局搜索能力，而較小的權重會增強算法的局部搜索能力。因此，對這種新的QDPSO算法的速度項引用慣性權重ω，通過研究4種方案，發現慣性權重ω的變化對具有量子行為的粒子群算法的收斂性具有很大改善。可以說慣性權重的適當設置對新的QDPSO算法性能也起著重要的作用。

1 量子行為的粒子群優化算法及其改進

1.1 QDPSO算法

文獻［4］的作者認為，若是在PSO系統下的個體粒子具有量子行為，則該粒子將會以與基本PSO算法中的粒子不同的方式運動。在量子空間，粒子的速度和位置不能再依據“不確定原理”被同時確定，所以提出了QDPSO算法。該算法改變了基本PSO算法的粒子更新策略，只用了粒子的位置向量。QDPSO算法的粒子進化方程如下：

P=(a·pid+b·pgd)/(a+b)(3)

L=(1/g)·abs(xid-p)(4)

xid=p+L·(ln(1/u))(5)

其中，a，b，u∈［0，1］為均勻分布的隨機數；pid是第i個粒子在第d維空間找到的局部最優解，pgd是群體在第d維空間找到的全局最優解；xid表示第i個粒子在第d維空間找到的當前值；而g必須滿足條件：g>ln2，才能保證算法的收斂。

1.2 改進的粒子群算法

新的QDPSO算法利用個體粒子的速度產生一個介于［0，1］之間的數來代替原算法中的由計算機隨機產生的數，用以選擇該粒子的位置更新方程。更新方程和參數設定

參考文獻［5］。

本文考慮到慣性權重隨粒子的迭代次數變化影響個體粒子的速度引導該粒子向最優解靠攏，所以采用4種方案對該改進算法進行研究。通過使慣性權重隨粒子的迭代次數變化，從而影響速度的更新方程：

vt+1=ω·vt+c1·r1(pt-xt)+c2·r2(pg-xt)(6)

其中，采用4種慣性權重ω方案來影響速度的更新，然后與QDPSO算法進行性能比較：

方案1 ω為從(1，0.875)遞減的函數ω=1-k·0.125/genmax。采用這種方案的QDPSO算法稱為w1-QDPSO；

方案2 ω為從(0.9，0.4)遞減的函數ω=0.9-k·0.5/genmax^［6］。采用這種方案的QDPSO算法稱為w2-QDPSO；

方案3 ω為一定值0.729 8^［7］，采用這種方案的QDPSO算法稱為w3-QDPSO；

方案4 ω為一凹函數^［8］( ωstart-ωend)(t/tmax)2+(ωstart-ωend) (2t/tmax)+ωstart，其中ωstart=0.95，ωend=0.4，tmax為最大的迭代次數。采用這種方案的QDPSO算法稱為w4-QDPOS。

綜上所述，選擇測試函數F1(x)和F2(x)分別為Sphere和Rastrigin(參數設置見文獻\\)，改進后的算法流程如下：

Step 1 初始化種群粒子的速度和位置；

Step 2 通過對兩個測試函數進行初始化計算，得到每個粒子的當前位置為粒子最佳位置pbest，初始群體粒子位置的最優值為群體最佳位置gbest；

Step 3 重新把粒子的位置代入測試函數進行計算，得到每個粒子新的適應值，將其與pbest比較，若較好，則將pbest設置為新位置；并將其與gbest比較，若較好，則將gbest設置為新位置；

Step 4 根據公式(6)更新粒子的速度；

Step 5 用個體粒子的速度產生用以選擇該粒子位置的更新方程的數據：

rand-q=1/(1+|(vmax-vid)/(vid-vmin)|)(7)

Step 6 由Step 5 產生的數據選擇更新粒子位置的方程：

if rand-q>0.5

xid=p+L·(ln(1/u))

else xid=p-L·(ln(1/u))

Step 7 若未達到終止條件(足夠小的適應值或預設的最大迭代次數)，則返回Step 3。

更新粒子速度時需要注意：如果粒子的速度超出預設的范圍，則采取使粒子反向運動的策略，從而保證算法有效進行。

1.3 算法的結果及數據分析

目標函數為F1(x)和F2(x)，基本參數是：c1=c2=2.05，g=0.968 5，每種算法都在同一臺計算機，同一環境下用Matlab 7.1.0軟件運行。結果如表1所示。

表1 函數F1(x)和F2(x)的平均最優適應值(最小值)

FUNCTIONDGmaxω1-QDPSOω2-QDPSOω3-QDPSOω4-QDPSOQDPSO

F1(x)

101 0005.10E-170.001 20.015 23.30E-47.50E-10

201 5002.52E-051.805 763.800 11.372 50.046 5

302 0000.167 952.668 21.99E+332.001 85.15

F2(x)

101 0001.42E-167.11E-177.11E-172.13E-160

201 5007.11E-171.07E-16001.04E-17

302 0007.11E-177.11E-1703.55E-170

表1的數值是對每個函數在粒子數為20個的條件下，測試50次，然后取平均得到的結果。從表中可以看出，對于函數F1(x)，比較結果可以明顯得知：在隨粒子群維數增加的情況下，ω1-QDPSO是比QDPSO得到更好的解，其他幾種改進方案的解都比較差；函數F2(x)在隨粒子群維數增加的情況下，4種改進方案和QDPSO都能得出比較好的解。

通過實驗，可以看出：對于單峰函數F1(x)，ω的遞減不能太小，從方案ω1-QDPSO和ω2-QDPSO的結果就可以比較出來，而方案ω3-QDPSO和ω4-QDPSO的結果不好，可能是因為它們搜索的區域太小，從而陷入局部最優解。

對于多峰函數F2(x)，ω的變化對測試函數的解的精確度沒有太大影響，說明了改進方案在此方面沒有明顯提高。接下來，我們還對算法的收斂速度進行了比較。結果如表2所示。

表2 各種方案收斂到最優解的平均迭代次數

FunctionDGmaxω1-QDPSOω2-QDPSOω3-QDPSOω4-QDPSOQDPSO

F1(x)

101 000688———993

201 500873 — ———

302 000—————

F2(x)

101 000386223.5108188112

201 500441266.5128226111.5

302 000620280.5127252135

注：表2中“—”表示函數測試50次沒有收斂。

表2是對函數測試50次后取得平均值的結果。可見對于函數F1(x)，ω1-QDPSO和QDPSO都在10維的情況下收斂，而20維時只有ω1-QDPSO收斂，其他函數都沒有收斂，導致這種結果的原因有2種：

(1) 各種方案隨ω的變化，削弱或失去了調節能力，在達到最大迭代次數時也未收斂;

(2) 即使在算法已搜索到最優解附近時，由于局部搜索能力太差，跳過了最優解。對于函數F2(x)，ω3-QDPSO，ω4-QDPSO，QDPSO收斂速度都比較快，ω1-QDPSO和ω2-QDPSO的收斂速度就相對較慢一些。這是由于對多峰函數測試時，各種方案的初始化范圍附近可能存在最優解，所以減少了迭代次數，加快了算法速度。

通過對4種方案的研究，這里選取方案1應用于0-1背包問題，并得到理想的結果。

2 對改進算法應用到0-1背包問題

2.1 0-1背包問題的數學描述

0-1背包問題是一種典型的組合優化問題。0-1背包問題的描述如下：假設有n個物品，其大小和價值分別為wi和ci (其中wi>0，ci >0，i=1，2，…，n)，背包的容量假設為V(V>0)。要求在背包的容量限制內，使所裝物品的總價值最大。該問題的數學模型可表示為：

max f(x1，x2，…，xn)=∑ni=1ni=1 cixi∑ni=1wi·xi≤V，

xi∈［0，1］，(i=1，2，…，n)(8)

其中，當將物品i裝入背包時xi=1;否則xi=0。

2.2 0-1背包問題的改進粒子群算法

改進粒子群算法應用到0-1背包問題的思想：粒子群中粒子的個數與每個粒子的維數相等。先定義二進制數x，x只能取0和1。再把粒子的種群數看作背包的個數n，對于每個粒子xi(其中i=1，2，…，n表示粒子個數)有n個維數，即1個粒子有n個位置。然后初始化每個粒子的速度vij，(其中j=1，2，…，n表示每個粒子位置的維數)，每個粒子的每一維都對應一個初始化了的速度。對公式(8)進行變化：

min f(x1，x2，…，xn)=-∑ni=1cixi(9)

解決背包問題的步驟：

(1) 初始化粒子的速度和位置；

(2) 將初始化的位置向量代入式(9)，在所得每個粒子的解中找到最優解pbest，并令pbest=gbest；

(3) 通過式(6)更新粒子的速度，對所得最優解進行修正，然后再次代入函數方程中繼續尋找新的最優解；

(4) 若達到終止條件，則結束迭代，輸出到存儲向量，即為所求結果；否則，k=k+1，轉步驟(3)。

2.3 實驗仿真

為了驗證ω1-QDPSO求解0/1背包問題的可行性及有效性，這里進行了2組實驗，每組實驗用ω1-QDPSO算法進行測試，每組算法運行50次。

實驗一：取參數popsize＝10，dimsize＝10，c1=c2＝2.05，genmax=1 000，g=0.968 5；N=10，V=269，W＝{95，4，60，32，23，72，80，62，65，46}，C={55，10，47，5，4，50，8，61，85，87}，得到實驗結果是max f=295，收斂平均迭代次數11。

實驗二：取參數popsize＝20，dimsize＝20，c1=c2=2.05，genmax=1 000，g=0.968 5；N=20，V=878，W＝{92，4，43，83，84，68，92，82，6，44，32，18，56，83，25，96，70，48，14，58}，C={44，46，90，72，91，40，75，35，8，54，78，40，77，15，61，17，75，29，75，63}，得到實驗結果是max f=1 024，收斂平均迭代次數23。

ω1-QDPSO算法求解0-1背包問題，與文獻［9］中提出的用帶有死亡罰函數的粒子群優化算法求解0-1背包問題相比，其運行速度明顯提高。

3 結 語

本文通過采用4種方案對具有量子行為的粒子群優化算法的慣性權重研究分析表明，QDPSO改進算法中慣性權重的改變對性能的影響與經典PSO算法相比既具繼承性又具發展性，在算法精度上ω1-QDPSO的結果比較優，而在計算速度上ω3-QDPSO和ω4-QDPSO的結果更優。選擇其中算法性能相對較好的ω1-QDPSO算法應用于0-1背包問題，可以看出改進算法性能的改善在應用中得到更好的體現。

參考文獻

［1］Kennedy J，Eberhart R C.Particle Swarm Optimization［C］.Proc.IEEE International Conference on Neural Networks USA，IEEE Press.，1995(4):1 942-1 948.

［2］Shi Y，Eberhart R C.A Modified Particle Swarm Optimizer ［C］.IEEE International Conference of Evolutionary Computation，Anchorage，Alaska，1998.

［3］Shi Y，Elberhart R C.Fuzzy Adaptive Particle Swarm Optimization ［A］.Proceeding of Congress on Evolutionary Computation［C］.Seoul，Korea，2001.

［4］Sun Jun，Feng Bin，Xu Wenbo.Particle Swarm Optimization with Particles Having Quantum Behavior ［A］.Proc.2004 Congress on Evolutionary Computation［C］.2004:325-331.

［5］馬金玲，唐普英.一種基于量子行為的改進粒子群算法\\.計算機應用研究，2007，43(36):89-90，180.

［6］Shi Y，Elberhart R C.Empirical Study of Partical Swarm Optimization\\.Proceeding of 1999 Congress on Evolutionary Computation.P_iscataway，NJ，IEEE Service Centerm，1999:1 945-1 950.

［7］曾建潮，介婧，崔志華.微粒群算法\\.北京:科學出版社，2004.

［8］陳貴敏，賈建援，韓琪.粒子群優化算法的慣性權值遞減策略研究\\.西安交通大學學報，2006，40(1):53-56，61.

［9］劉華鎣，齊名軍，林玉娥.用帶有死亡罰函數的粒子群優化算法求解0/1背包問題\\.大慶石油學院學報，2006，30(5):87-89.

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