遗传算法求解0-1背包问题精编版.doc

1、遗传算法解决 0-1 背包问题北京科技大学物流工程系2013.6.111一、实例一：1. 问题描述假设：背包最大重量为300，物品的数量为10，物品的价值： 9575237350226578998，物品的重量： 89591943100 7244167642. Matlab 代码（1） 参数初始化，导入本问题的物品的价值和重量数据，并设定背包最大重量。wei=95752373 5022 6578998;val=89 591943100 724416764;w=300;%总重量约束值（2） 随机产生数量为 30 的种群。生成 30*10 的 0-1 矩阵。So =round(rand(30,10)

2、;So=hardlim(So);%So为随机产生的矩阵 ,值为 0 或 1ZQ,Y = size(So);（3） 迭代次数为 50 代，交叉概率为90%，变异概率为 5%.ds = 50; pc = 0.9; pm = 0.05;（4） 设置适应度函数， 利用惩罚函数降低不合格解的适应度，惩罚因子设为 1.5.pu=1.5;syd =So*val-pu*So*val./(So*wei).*(So*wei-w)0).*(So*wei-w);figure(1);hold on;（5） 用轮盘赌进行选择操作，用选择出的个体构成的种群替代旧的种群better1=1; ip = 1; updatef=-

3、10;%betterl 为当前算出的总价值， ip 为代数whileipsp(sindex)sindex=sindex+1;endnewSo(i,:)=So(sindex,:);endfori=1:ZQSo(i,:)=newSo(i,:);end（6） 设置的交叉概率pc 为 90%，产生要配对的父代的序号，经过50 次顺序调换，将原有顺序打乱，使相邻两个个体作为交叉的父代fori=1:ZQweiindex(i)=i;endfori=1:ZQpoint=unidrnd(ZQ-i+1);temp=weiindex(i);weiindex(i)=weiindex(i+point-1);weiind

4、ex(i+point-1)=temp;endfori=1:2:ZQp=rand(1);if(ppc)3point=unidrnd(Y-1)+1;for j=point:(Y-1)ch=So(weiindex(i),j);So(weiindex(i),j)=So(weiindex(i+1),j);So(weiindex(i+1),j)=ch;endendend（7） 设置变异的概率为5%，产生 50*10 的 0-1 矩阵，对 1 的位置进行变异M=rand(ZQ,Y)0).*(So*wei-w); better1,you1 = max(syd);ifupdatef=better1better1

5、=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(syd2);plot(ip,better3,-*m);4end;（9） 将最优值和参数显示

6、出来。syd2 =So*val-So*val.*(So*wei-w)0);better3,you3 = max(syd2);best = better3; P = So;disp(sprintf( 代数 : %d,ds);disp(sprintf( 种群大小 : %d,ZQ);disp(sprintf( 交叉概率 : %.3f,pc);disp(sprintf( 变异概率 : %.3f,pm);disp(sprintf( 最优解 : %.2f,best);3. 结果5如图所示，横坐标是迭代次数，纵坐标是每代的最优解。最优染色体解是： 1 0 1 0 1 1 1 0 0 1，即对应着问题描述，数

7、值为 1 的物品放入背包，可得到最大的价值为 388，跟该问题的最优值一样，且背包重量为 294，不超过最大限重 300，且解题速度够快，该代码可行。该实例对应的 matlab 文件名为 GAK.M。二、实例二1. 问题描述假设：背包的最大重量为 1000，物品的数量为 100，物品价值： 75646818835560101883538780149218672264158033798143937448747270949857759844698018967896241437505266632730508863100 6850615563479552406543693446264518949367

8、334796067486549281049779847561123470289521物品重量： 27211482369488718669756074163849246887853270373665299165413787095238843044857539244276155368787524538434993222580399234591741171928573112144477128915713624368133406965687341911150137893346041352. Matlab 代码（1） 参数初始化，导入本问题的物品的价值和重量数据，并设定背包最大重量。wei=75 646

9、818835560101883538780149218672264158033798143937448747270949857759844698018967896241437505266632730508863100 68506155634795524065436934462645189493673347960674865492810497798475611234706289521;val=27 2114823694887186697560741638492468878532703736652991654137870952388430448575392442761553687875245384

10、3499322258039923459174117192857311214447712891571362436813340696568734191115013789334604135;w=1000;%总重量约束值（2） 随机产生数量为 50 的种群。生成 50*100 的 0-1 矩阵。So =round(rand(50,100);So=hardlim(So);%So为随机产生的矩阵 ,值为 0 或 1ZQ,Y = size(So);（3） 迭代次数为 500 代，交叉概率为90%，变异概率为 3%.ds = 500; pc = 0.9; pm = 0.03;（4） 设置适应度函数， 利用惩罚函数降低不合格解的适应度，惩罚因子设为 1.1.pu=1.1;%惩罚系数syd =So*val-pu*So*val./(So*wei).*(So*wei-w)0).*(So*wei-w);figure(1);hold on;其他代码与上述实例一样，在此不做赘述。3. 结果7如图所示，横坐标是迭代次数，纵坐标是每代的最优解。最优染色体解是 :00010111101001010111010010000000000010101000