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

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

3、入點(diǎn)，待解決的背包問(wèn)題以下所示：0-1背包問(wèn)題:關(guān)于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=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擴(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矩陣作為粒子的初始地點(diǎn)v=rand(xSize,Dim);%粒子的初始速度xbest=zeros(xSize,Dim);%單個(gè)粒子的初始最正確地點(diǎn)fxbest=zeros(xSize,1);%xbest的適應(yīng)度gbest=zeros(1,Dim);%粒子群的初始最正確地點(diǎn)fgbest=0;%gbest的適應(yīng)度%粒子群最優(yōu)地點(diǎn)和單個(gè)粒子最優(yōu)地點(diǎn)的選定%迭代循環(huán)算法:iter=0;whileiter269fx(

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

6、x(i,:)=round(rand(1,Dim);%為防備算法墮入局部最優(yōu)，若某個(gè)粒子的地點(diǎn)等于種群最正確地點(diǎn)，將對(duì)該粒子的地點(diǎn)從頭初始化賦值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;%更新粒子群的地點(diǎn)fori=1:xSizeforj=1:Dimifx(i,j)0.5x(i,j)=0;elsex(i,j)=1;endendend%因?yàn)榱Ｗ拥牡攸c(diǎn)只有(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即在背包問(wèn)題的最優(yōu)解決方案是：往背包中放第2、3、4、8、9、10只物件時(shí)，總價(jià)值為295。因?yàn)榇舜伪嘲鼏?wèn)題的解維數(shù)較少，運(yùn)算量小，改正參數(shù)、改變種群數(shù)和迭代次數(shù)對(duì)最后結(jié)果影響不大，獲得的最后結(jié)果不變。此程序存在的主要問(wèn)題有：粒子群算法合用于解決連續(xù)函數(shù)的優(yōu)化問(wèn)題，而0-1背包問(wèn)題