遺傳算法求解0-1背包問題

1、遺傳算法求解0-1背包問題docxdocx2013.6.11實例一：1. 問題描述假設：背包最大重量為300，物品的數(shù)量為10，物品的價值：9575237350226578998，物品的重量：895919431007244167642. Matlab代碼( 1) 參數(shù)初始化，導入本問題的物品的價值和重量數(shù)據(jù)，并設定背包最大重量。wei=9575237350226578998;val=89591943100724416764;w=300;%總重量約束值( 2) 隨機產(chǎn)生數(shù)量為30的種群。生成30*10的0-1矩陣。So=round(rand(30,10);So=hardlim(So);%So為隨

2、機產(chǎn)生的矩陣,值為0或1ZQ,Y=size(So);( 3) 迭代次數(shù)為50代，交叉概率為90%，變異概率為5%.ds=50;pc=0.9;pm=0.05;( 4) 設置適應度函數(shù)，利用懲罰函數(shù)降低不合格解的適應度，懲罰因子設為1.5.pu=1.5;syd=So*val'-pu*So*val'./(So*wei').*(So*wei'-w)>0).*(So*wei'-w);figure(1);holdon;( 5) 用輪盤賭進行選擇操作，用選擇出的個體構成的種群替代舊的種群better1=1;ip=1;updatef=-10;%betterl為當前

3、算出的總價值，ip為代數(shù)whileip<=dsfori=1:ZQfi(i)=syd(i)-min(syd)+1;endfori=1:ZQsp(i)=fi(i)/sum(fi);endfori=2:ZQsp(i)=sp(i-1)+sp(i);endfori=1:ZQp=rand(1);sindex=1;whilep>sp(sindex)sindex=sindex+1;endnewSo(i,:)=So(sindex,:);endfori=1:ZQSo(i,:)=newSo(i,:);end6) 設置的交叉概率pc為90%，產(chǎn)生要配對的父代的序號，經(jīng)過50次順序調(diào)換，將原有順序打亂，使相

4、鄰兩個個體作為交叉的父代fori=1:ZQweiindex(i)=i;endfori=1:ZQpoint=unidrnd(ZQ-i+1);temp=weiindex(i);weiindex(i)=weiindex(i+point-1);weiindex(i+point-1)=temp;endfori=1:2:ZQp=rand(1);if(p<pc)point=unidrnd(Y-1)+1;forj=point:(Y-1)ch=So(weiindex(i),j);So(weiindex(i),j)=So(weiindex(i+1),j);So(weiindex(i+1),j)=ch;end

5、endend7) 設置變異的概率為5%，產(chǎn)生50*10的0-1矩陣，對1的位置進行變異M=rand(ZQ,Y)<=pm;So=So-2.*(So.*M)+M;8) 產(chǎn)生精英染色體，you1是適應度最大的染色體，you2為適應度最小的染色體，最優(yōu)解為不超過背包容量的適應度最大的syd2數(shù)組，better3即為每代的最優(yōu)值，并用粉色星號畫出來。syd=So*val'-pu*So*val'./(So*wei').*(So*wei'-w)>0).*(So*wei'-w);better1,you1=max(syd);ifupdatef>=bett

6、er1better1=updatef;So(you1,:)=updatec;endupdatef=better1;updatec=So(you1,:);better2,you2=min(syd);So(you2,:)=So(you1,:);syd=So*val'-pu*So*val'./(So*wei').*(So*wei'-w)>0).*(So*wei'-w);media=mean(syd);ip=ip+1;syd2=So*val'-So*val'.*(So*wei'-w)>0);better3,you3=max(s

7、yd2);plot(ip,better3,'-*m');end;(9)將最優(yōu)值和參數(shù)顯示出來。syd2=So*val'-So*val'.*(So*wei'-w)>0);better3,you3=max(syd2);best=better3;P=So;disp(sprintf('代數(shù):%d',ds);disp(sprintf('種群大?。?d',ZQ);disp(sprintf('交叉概率:%.3f,pc);disp(sprintf('變異概率:%.3f,pm);disp(sprintf('最優(yōu)

8、解:%.2f',best);3.結果代數(shù);50種群大?。?0交叉概率；0.900變異極率:。.050最優(yōu)麟：385,00如圖所示，橫坐標是迭代次數(shù)，縱坐標是每代的最優(yōu)解。最優(yōu)染色體解是：10 101110 01,即對應著問題描述，數(shù)值為1的物品放入背包，可得到最大的價值為388,跟該問題的最優(yōu)值一樣，且背包重量為294,不超過最大限重300,且解題速度夠快，該代碼可行。該實例對應的matlab文件名為GAK.M二、實例二1.問題描述假設：背包的最大重量為1000,物品的數(shù)量為100,物品價值：75 64686415803379980189678506155634718 83 55 60

9、 1081 43 93 74 4896 24 14 37 5095 52 40 65 4318835387807472709498526663273069344626451492186722577598446508863100 6818949367334796067486549281049779847561123470289521物品重量：272114823694887186697560741638492468878532703736652991541378709538843044857539244276155368787524538434993222803992345917411719285

10、731121444771281571362436813340696568731911150137893346041352.Matlab代碼1)參數(shù)初始化，導入本問題的物品的價值和重量數(shù)據(jù)，并設定背包最大重量。wei=756468188355601018835387801492186722641580337981439374487472709498577598446801896789624143750526663273050886310068506155634795524065436934462645189493673347960674865281049779847561123470289521

11、;val=27211482369488718669756074163849246887853270373665299154137870953884304485753924427615536878752453843499322258039923459174117192857312144477128157136243681334069656873191115013789334604135;w=1000;%總重量約束值2)隨機產(chǎn)生數(shù)量為50的種群。生成50*100的0-1矩陣。So=round(rand(50,100);So=hardlim(So);%So為隨機產(chǎn)生的矩陣,值為0或1ZQ,Y=siz

12、e(So);3)迭代次數(shù)為500代，交叉概率為90%，變異概率為3%.ds=500;pc=0.9;pm=0.03;(4)設置適應度函數(shù)，利用懲罰函數(shù)降低不合格解的適應度，懲罰因子設為1.1.pu=1.1;%懲罰系數(shù)syd=So*val'-pu*So*val'./(So*wei').*(So*wei'-w)>0).*(So*wei'-w);figure。);holdon;其他代碼與上述實例一樣，在此不做贅述3.結果代教；5。0種群大?。?0交叉概率：0.900變異概率；0.Q3。最優(yōu)解：2426.00如圖所示，橫坐標是迭代次數(shù)，縱坐標是每代的最優(yōu)解。最優(yōu)染色體解是:000101111010010100 010