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

1、用粒子群算法解決0/1 背包問題背包問題 ( Knapsack Problem)是著名的 NP 問題，也是一個(gè)典型的組合優(yōu)化問題。這里要解決的背包問題的描述如下：ai：第 i 個(gè)物品的體積；ci：第 i 個(gè)物品的價(jià)值；b：背包的重量限制；背包問題就是在總的體積有限的條件下 ,追求總價(jià)值最大的有效資源分配問題。有界的整數(shù)背包問題可轉(zhuǎn)化成等價(jià)的 0-1 背包問題，定義變量0 攜帶第 i個(gè)物品xi1i1,2, ,n不攜帶第 i個(gè)物品n目標(biāo)函數(shù)轉(zhuǎn)化為：maxci xii 1n約束條件：s.t .ai xibi 1xi 0,1粒子群算法速度和位置的迭代公式為：Vi t1wVi t c1rand ()Pi

2、 X i tc2rand ()Pj X itX it 1X it Vi t 1其中， c1， c2為正常數(shù)，稱為加速因 子； rand ()為 0,1 之間的隨機(jī)數(shù)； w為慣性因子；t表示某一次迭代； Pi為粒子的最優(yōu)位置； Pj 為種群最優(yōu)位置背包問題中的 X 是一個(gè) 0-1 序列，每一個(gè)粒子的位置可以用向量粒子的位置就表示一個(gè)可行解，粒子的適應(yīng)值函數(shù)就可以表示為X 來表示，nf Xvi xi（,背包內(nèi)物品的價(jià)值總和）i1粒子群算法的尋優(yōu)可以表示為求取使得f (X)值最大的 X粒子群中的速度定義為物品選擇的變換集，即為兩次位置的距離，用V 表示，則 |V|表示速度所含的交換的數(shù)目，從而該速度

3、可定義為VX1X2vi | vi0,1 , i 1,2, ,n ,其中vi0 : x1ix2i1 : x1ix2i以此作為用粒子群算法解決背包問題的切入點(diǎn)，待解決的背包問題如下所示：0-1背包問題 :對(duì)于 n個(gè)體積為 aj、價(jià)值分別為 cj的物品，如何將它們裝入總體積為 b的背包中，使得所選物品的總價(jià)值最大。n10aj=95, 4, 60, 32, 23, 72, 80, 62, 65, 46cj=55, 10, 47, 5, 4, 50, 8, 61, 85, 87b=269使用 MATLAB 編輯如下程序：a=95 4 60 32 23 72 80 62 65 46; % 物品的體積c=5

4、5 10 47 5 4 50 8 61 85 87; %物品的價(jià)值b=269;%背包的重量限制%初始化程序 :Dim=10; %粒子的維數(shù)xSize=20; %種群數(shù)MaxIt=30; %最大迭代次數(shù)c1=0.7;c2=0.7;% 定義加速因子w=0.8; %定義慣性因子%A=repmat(a,xSize,1); %將 a擴(kuò)展成一個(gè) 30*10 的矩陣C=repmat(c,xSize,1); %將 c擴(kuò)展成一個(gè) 30*10 的矩陣 x=round(rand(xSize,Dim); %隨機(jī)取一個(gè) 30*10 的 0/1矩陣作為粒子的初始位置 v=rand(xSize,Dim); %粒子的初始速度

5、xbest=zeros(xSize,Dim); %單個(gè)粒子的初始最佳位置fxbest=zeros(xSize,1); %xbest的適應(yīng)度gbest=zeros(1,Dim); % 粒子群的初始最佳位置fgbest=0;%gbest的適應(yīng)度%粒子群最優(yōu)位置和單個(gè)粒子最優(yōu)位置的選定%迭代循環(huán)算法 :iter=0;while iter<MaxItiter=iter+1;fx=sum(C.*x)'); %計(jì)算粒子群的適應(yīng)度 ,即背包內(nèi)物品的價(jià)值 sx=sum(A.*x)'); %限制函數(shù) ,背包內(nèi)物品的體積 for i=1:xSizeif sx(i)>269fx(i)=0

6、; %當(dāng)被包內(nèi)物品的體積超過限制時(shí),將期適應(yīng)度設(shè)置為1endendfor i=1:xSizeif fxbest(i)<fx(i)fxbest(i)=fx(i);xbest(i,:)=x(i,:);end% 當(dāng)粒子的適應(yīng)度 fx(i) 大于其最佳適應(yīng)度時(shí) fxbest(i), 用其替代原來粒子的最佳適應(yīng)度 ,并記下此解endif fgbest<max(fxbest)fgbest,g=max(fxbest);gbest=xbest(g,:);%當(dāng)存在粒子的最佳適應(yīng)度fxbest(i) 大于種群的最佳適應(yīng)度時(shí),用其替代原來種群的最佳適應(yīng)度,并記下此解endfor i=1:xSizeif

7、x(i,:)=gbestx(i,:)=round(rand(1,Dim); %為防止算法陷入局部最優(yōu)，若某個(gè)粒子的位置等于種群最佳位置，將對(duì)該粒子的位置重新初始化賦值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; %更新粒子群的位置for i=1:xSizefor j=1:Dimif x(i,j)<0.5x(i,j)=0;else x(i,j)=1;endendend%由于粒子的位置只有(0,1)兩種狀態(tài) ,此處以 0.5為分界點(diǎn)對(duì)函數(shù)值進(jìn)行調(diào)整end%fgbestsgbest=sum(a.*gbest)')Gbest迭代 10 次，最有結(jié)果為：fgbest =295sgbest =269gbest =0111000111即在背包問題的最優(yōu)解決方案是：往背包中放第2、3、4、8、9、10 只物品時(shí)，總價(jià)值為 295。由于這次背包問題的解維數(shù)較少， 運(yùn)算量小， 修改參數(shù)、改變種群數(shù)和迭代次數(shù)對(duì)最終結(jié)果影響不大，得到的最終結(jié)果不變。此程序存在的主要問題有：粒子群算法適用于解決連續(xù)函