基于具有量子行為的粒子群優(yōu)化算法慣性權(quán)重研究及應(yīng)用

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

其中，r1，r2∈[0，1]為均勻分布的隨機(jī)數(shù)；C1，C2均是正常數(shù)；t表示進(jìn)化代數(shù)；Vt，Xt分別表示每個(gè)粒子的速度和位置；Pg，Pt分別是粒子群的全局最優(yōu)和個(gè)體最優(yōu)。

為了改善基本PSO算法的收斂性能，Y?Shi等人提出了慣性權(quán)重的方法和用模糊控制器來動(dòng)態(tài)自適應(yīng)地改變慣性權(quán)重的技術(shù)。之后Jun Sun等人提出的具有δ函數(shù)形式的粒子群算法(QDPSO)使粒子群算法的計(jì)算更加簡(jiǎn)單容易。最近一種新的QDPSO算法考慮了速度對(duì)位置的影響，通過速度的更新選擇位置的更新方程。在經(jīng)典粒子群算法的可調(diào)整參數(shù)中，慣性權(quán)重是非常重要的參數(shù)，較大的權(quán)重有利于提高算法的全局搜索能力，而較小的權(quán)重會(huì)增強(qiáng)算法的局部搜索能力。因此，對(duì)這種新的QDPSO算法的速度項(xiàng)引用慣性權(quán)重ω，通過研究4種方案，發(fā)現(xiàn)慣性權(quán)重ω的變化對(duì)具有量子行為的粒子群算法的收斂性具有很大改善?？梢哉f慣性權(quán)重的適當(dāng)設(shè)置對(duì)新的QDPSO算法性能也起著重要的作用。

1 量子行為的粒子群優(yōu)化算法及其改進(jìn)

1.1 QDPS0算法

文獻(xiàn)[4]的作者認(rèn)為，若是在PSO系統(tǒng)下的個(gè)體粒子具有量子行為，則該粒子將會(huì)以與基本PSO算法中的粒子不同的方式運(yùn)動(dòng)。在量子空間，粒子的速度和位置不能再依據(jù)“不確定原理”被同時(shí)確定，所以提出了QDPSO算法。該算法改變了基本PSO算法的粒子更新策略，只用了粒子的位置向量。QDPSO算法的粒子進(jìn)化方程如下：

其中，a，b，u∈[0，1]為均勻分布的隨機(jī)數(shù)；pid是第i個(gè)粒子在第d維空間找到的局部最優(yōu)解，pgd是群體在第d維空間找到的全局最優(yōu)解；xid表示第i個(gè)粒子在第d維空間找到的當(dāng)前值；而g必須滿足條件：，才能保證算法的收斂。

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

新的QDPSO算法利用個(gè)體粒子的速度產(chǎn)生一個(gè)介于[0，1]之間的數(shù)來代替原算法中的由計(jì)算機(jī)隨機(jī)產(chǎn)生的數(shù)，用以選擇該粒子的位置更新方程。更新方程和參數(shù)設(shè)定參考文獻(xiàn)[5]。

本文考慮到慣性權(quán)重隨粒子的迭代次數(shù)變化影響個(gè)體粒子的速度引導(dǎo)該粒子向最優(yōu)解靠攏，所以采用4種方案對(duì)該改進(jìn)算法進(jìn)行研究。通過使慣性權(quán)重隨粒子的迭代次數(shù)變化，從而影響速度的更新方程：

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

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

方案2 ω為從(0.9，0.4)遞減的函數(shù)甜ω=0.9-k?0.5／genmax。采用這種方案的QDPSO算法稱為ω2-QDPSO；

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

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

綜上所述，選擇測(cè)試函數(shù)F1(x)和F2(x)分別為Sphere和Rastrigin(參數(shù)設(shè)置見文獻(xiàn)[4])，改進(jìn)后的算法流程如下：

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

Step 2 通過對(duì)兩個(gè)測(cè)試函數(shù)進(jìn)行初始化計(jì)算，得到每個(gè)粒子的當(dāng)前位置為粒子最佳位置Pbest，初始群體粒子位置的最優(yōu)值為群體最佳位置gbest；

Step 3 重新把粒子的位置代入測(cè)試函數(shù)進(jìn)行計(jì)算，得到每個(gè)粒子新的適應(yīng)值，將其與Pbest比較，若較好，則將Pbest設(shè)置為新位置；并將其與gbest比較，若較好，則將gbest設(shè)置為新位置；

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

Step 5 用個(gè)體粒子的速度產(chǎn)生用以選擇該粒子位置的更新方程的數(shù)據(jù)；

Step 6 由Step 5產(chǎn)生的數(shù)據(jù)選擇更新粒子位置的方程；

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

更新粒子速度時(shí)需要注意：如果粒子的速度超出預(yù)設(shè)的范圍，則采取使粒子反向運(yùn)動(dòng)的策略，從而保證算法有效進(jìn)行。

1.3 算法的結(jié)果及數(shù)據(jù)分析

目標(biāo)函數(shù)為F1(x)和F2(x)，基本參數(shù)是：c1=c2=2.05，g=0.968 5，每種算法都在同一臺(tái)計(jì)算機(jī)，同一環(huán)境下用Matlab 7.1.0軟件運(yùn)行。結(jié)果如表1所示。

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

通過實(shí)驗(yàn)，可以看出：對(duì)于單峰函數(shù)F1(x)，ω的遞減不能太小，從方案ω1-QDPSO和ω2-QDPSO的結(jié)果就可以比較出來，而方案ω3-QDPSO和ω4-QDPSO的結(jié)果不好，可能是因?yàn)樗鼈兯阉鞯膮^(qū)域太小，從而陷入局部最優(yōu)解。

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

表2是對(duì)函數(shù)測(cè)試50次后取得平均值的結(jié)果?？梢妼?duì)于函數(shù)F1(x)，ω1-QDPSO和QDPSO都在10維的情況下收斂，而20維時(shí)只有ω1-QDPSO收斂，其他函數(shù)都沒有收斂，導(dǎo)致這種結(jié)果的原因有2種：

(1)各種方案隨ω的變化，削弱或失去了調(diào)節(jié)能力，在達(dá)到最大迭代次數(shù)時(shí)也未收斂；

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

通過對(duì)4種方案的研究，這里選取方案1應(yīng)用于0-1背包問題，并得到理想的結(jié)果。

2 對(duì)改進(jìn)算法應(yīng)用到0-1背包問題

2.1 0-1背包問題的數(shù)學(xué)描述

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

其中，當(dāng)將物品i裝入背包時(shí)xi=1；否則xi=0。

2.2 0-1背包問題的改進(jìn)粒子群算法

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

解決背包問題的步驟：

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

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

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

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

2.3 實(shí)驗(yàn)仿真

為了驗(yàn)證ω1-QDPSO求解0／1背包問題的可行性及有效性，這里進(jìn)行了2組實(shí)驗(yàn)，每組實(shí)驗(yàn)用ω1-QDPSO算法進(jìn)行測(cè)試，每組算法運(yùn)行50次。

實(shí)驗(yàn)一：取參數(shù)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)，得到實(shí)驗(yàn)結(jié)果是max f=295，收斂平均迭代次數(shù)11。

實(shí)驗(yàn)二：取參數(shù)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}，得到實(shí)驗(yàn)結(jié)果是max f=1024，收斂平均迭代次數(shù)23。

ω1-QDPSO算法求解0-1背包問題，與文獻(xiàn)[9]中提出的用帶有死亡罰函數(shù)的粒子群優(yōu)化算法求解0-1背包問題相比，其運(yùn)行速度明顯提高。

3 結(jié) 語

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