具有量子行為的粒子群優(yōu)化算法慣性權(quán)重研究

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

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

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

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

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

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

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

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

改進(jìn)粒子群算法應(yīng)用到0-1背包問(wèn)題的思想：粒子群中粒子的個(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)行變化：

解決背包問(wèn)題的步驟：

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

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

(3)通過(guò)式(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背包問(wèn)題的可行性及有效性，這里進(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背包問(wèn)題，與文獻(xiàn)[9]中提出的用帶有死亡罰函數(shù)的粒子群優(yōu)化算法求解0-1背包問(wèn)題相比，其運(yùn)行速度明顯提高。

3 結(jié) 語(yǔ)

本文通過(guò)采用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背包問(wèn)題，可以看出改進(jìn)算法性能的改善在應(yīng)用中得到更好的體現(xiàn)