具有量子行為的粒子群優(yōu)化算法慣性權(quán)重研究
本文引用地址:http://butianyuan.cn/article/148708.htm
(1)各種方案隨ω的變化,削弱或失去了調(diào)節(jié)能力,在達到最大迭代次數(shù)時也未收斂;
(2)即使在算法已搜索到最優(yōu)解附近時,由于局部搜索能力太差,跳過了最優(yōu)解。對于函數(shù)F2(x),ω3-QDPSO,ω4-QDPSO,QDPSO收斂速度都比較快,ω1=QDPSO和ω2-QDPSO的收斂速度就相對較慢一些。這是由于對多峰函數(shù)測試時,各種方案的初始化范圍附近可能存在最優(yōu)解,所以減少了迭代次數(shù),加快了算法速度。
通過對4種方案的研究,這里選取方案1應(yīng)用于0-1背包問題,并得到理想的結(jié)果。
2 對改進算法應(yīng)用到0-1背包問題
2.1 0-1背包問題的數(shù)學(xué)描述
0-1背包問題是一種典型的組合優(yōu)化問題。0-1背包問題的描述如下:假設(shè)有n個物品,其大小和價值分別為wi和ci(其中wi>0,ci>0,i=1,2,…,n),背包的容量假設(shè)為V(V>0)。要求在背包的容量限制內(nèi),使所裝物品的總價值最大。該問題的數(shù)學(xué)模型可表示為:
其中,當(dāng)將物品i裝入背包時xi=1;否則xi=0。
2.2 0-1背包問題的改進粒子群算法
改進粒子群算法應(yīng)用到0-1背包問題的思想:粒子群中粒子的個數(shù)與每個粒子的維數(shù)相等。先定義二進制數(shù)x,x只能取0和1。再把粒子的種群數(shù)看作背包的個數(shù)n,對于每個粒子xi(其中i=1,2,…,n表示粒子個數(shù))有n個維數(shù),即1個粒子有n個位置。然后初始化每個粒子的速度vij,(其中j=1,2,…,n表示每個粒子位置的維數(shù)),每個粒子的每一維都對應(yīng)一個初始化了的速度。對公式(8)進行變化:
解決背包問題的步驟:
(1)初始化粒子的速度和位置;
(2)將初始化的位置向量代人式(9),在所得每個粒子的解中找到最優(yōu)解pbest,并令pbest=gbest;
(3)通過式(6)更新粒子的速度,對所得最優(yōu)解進行修正,然后再次代入函數(shù)方程中繼續(xù)尋找新的最優(yōu)解;
(4)若達到終止條件,則結(jié)束迭代,輸出到存儲向量,即為所求結(jié)果;否則,k=k+1,轉(zhuǎn)步驟(3)。
2.3 實驗仿真
為了驗證ω1-QDPSO求解0/1背包問題的可行性及有效性,這里進行了2組實驗,每組實驗用ω1-QDPSO算法進行測試,每組算法運行50次。
實驗一:取參數(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),得到實驗結(jié)果是max f=295,收斂平均迭代次數(shù)11。
實驗二:取參數(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},得到實驗結(jié)果是max f=1024,收斂平均迭代次數(shù)23。
ω1-QDPSO算法求解0-1背包問題,與文獻[9]中提出的用帶有死亡罰函數(shù)的粒子群優(yōu)化算法求解0-1背包問題相比,其運行速度明顯提高。
3 結(jié) 語
本文通過采用4種方案對具有量子行為的粒子群優(yōu)化算法的慣性權(quán)重研究分析表明,QDPSO改進算法中慣性權(quán)重的改變對性能的影響與經(jīng)典PSO算法相比既具繼承性又具發(fā)展性,在算法精度上ω1-QDPSO的結(jié)果比較優(yōu),而在計算速度上ω3-QDPSO和ω4-QDPSO的結(jié)果更優(yōu)。選擇其中算法性能相對較好的ω1-QDPSO算法應(yīng)用于0-1背包問題,可以看出改進算法性能的改善在應(yīng)用中得到更好的體現(xiàn)
pid控制相關(guān)文章:pid控制原理
評論