用粒子群算法解決01背包問題

1、用粒子群算法解決0/1背包問題背包問題(KnapsackProblem)是有名的NP問題，也是一個典型的組合優(yōu)化問題。這里要解決的背包問題的描繪以下：ai：第i個物件的體積；ci：第i個物件的價值；b：背包的重量限制；背包問題就是在總的體積有限的條件下,追求總價值最大的有效資源分派問題。有界的整數(shù)背包問題可轉(zhuǎn)變成等價的0-1背包問題，定義變量攜帶第i個物件xi1i1,2,n不攜帶第i個物件n目標(biāo)函數(shù)轉(zhuǎn)變?yōu)椋簃axcixii1n拘束條件：s.t.aixibi1xi0,1粒子群算法速度和地點的迭代公式為：Vit1wVitc1rand()PiXitc2rand()PjXitXit1XitVit1此中

2、，c1，c2為正常數(shù)，稱為加快因子；rand()為0,1之間的隨機數(shù)；w為慣性因子；t表示某一次迭代；Pi為粒子的最優(yōu)地點；Pj為種群最優(yōu)地點背包問題中的X是一個0-1序列，每一個粒子的地點能夠用向量粒子的地點就表示一個可行解，粒子的適應(yīng)值函數(shù)就能夠表示為X來表示，nfXvixi（,背包內(nèi)物件的價值總和）i1粒子群算法的尋優(yōu)能夠表示為求取使得f(X)值最大的X粒子群中的速度定義為物件選擇的變換集，即為兩次地點的距離，用V表示，則|V|表示速度所含的互換的數(shù)量，進而該速度可定義為VX1X2vi|vi0,1,i1,2,n,此中vi0:x1ix2i1:x1ix2i以此作為用粒子群算法解決背包問題的切

3、入點，待解決的背包問題以下所示：0-1背包問題:關(guān)于n個體積為aj、價值分別為cj的物件，怎樣將它們裝入整體積為b的背包中，使得所選物件的總價值最大。n10aj=95,4,60,32,23,72,80,62,65,46cj=55,10,47,5,4,50,8,61,85,87b=269使用MATLAB編寫以下程序：a=9546032237280626546;%物件的體積b=269;%背包的重量限制%初始化程序:Dim=10;%粒子的維數(shù)xSize=20;%種群數(shù)MaxIt=30;%最大迭代次數(shù)c1=0.7;c2=0.7;%定義加快因子w=0.8;%定義慣性因子%A=repmat(a,xSize

4、,1);%將a擴展成一個30*10的矩陣C=repmat(c,xSize,1);%將c擴展成一個30*10的矩陣x=round(rand(xSize,Dim);%隨機取一個30*10的0/1矩陣作為粒子的初始地點v=rand(xSize,Dim);%粒子的初始速度xbest=zeros(xSize,Dim);%單個粒子的初始最正確地點fxbest=zeros(xSize,1);%xbest的適應(yīng)度gbest=zeros(1,Dim);%粒子群的初始最正確地點fgbest=0;%gbest的適應(yīng)度%粒子群最優(yōu)地點和單個粒子最優(yōu)地點的選定%迭代循環(huán)算法:iter=0;whileiter269fx(

5、i)=0;%當(dāng)被包內(nèi)物件的體積超出限制時,將期適應(yīng)度設(shè)置為1endendfori=1:xSizeiffxbest(i)fx(i)fxbest(i)=fx(i);xbest(i,:)=x(i,:);end%當(dāng)粒子的適應(yīng)度fx(i)大于其最正確適應(yīng)度時fxbest(i),用其代替本來粒子的最正確適應(yīng)度,并記下此解endiffgbestmax(fxbest)fgbest,g=max(fxbest);gbest=xbest(g,:);%當(dāng)存在粒子的最正確適應(yīng)度fxbest(i)大于種群的最正確適應(yīng)度時,用其代替本來種群的最正確適應(yīng)度,并記下此解endfori=1:xSizeifx(i,:)=gbest

6、x(i,:)=round(rand(1,Dim);%為防備算法墮入局部最優(yōu)，若某個粒子的地點等于種群最正確地點，將對該粒子的地點從頭初始化賦值endendR1=rand(xSize,Dim);R2=rand(xSize,Dim);v=v*w+c1*R1.*(xbest-x)+c2*R2.*(repmat(gbest,xSize,1)-x);%用速度迭代公式產(chǎn)生新的速度x=x+v;%更新粒子群的地點fori=1:xSizeforj=1:Dimifx(i,j)0.5x(i,j)=0;elsex(i,j)=1;endendend%因為粒子的地點只有(0,1)兩種狀態(tài),此處以0.5為分界點對函數(shù)值進行調(diào)整end%fgbestsgbest=sum(a.*gbest)Gbest迭代10次，最有結(jié)果為：fgbest=295sgbest=269gbest=0111000111即在背包問題的最優(yōu)解決方案是：往背包中放第2、3、4、8、9、10只物件時，總價值為295。因為此次背包問題的解維數(shù)較少，運算量小，改正參數(shù)、改變種群數(shù)和迭代次數(shù)對最后結(jié)果影響不大，獲得的最后結(jié)果不變。此程序存在的主要問題有：粒子群算法合用于解決連續(xù)函數(shù)的優(yōu)化問題，而0-1背包問題