遗传算法求解0-1背包问题12613.pdf
遗传算法求解0-1背包问题 docx docx 2013.6.11 一、实例一：1.问题描述 假设：背包最大重量为300，物品的数量为 10，物品的价值：95 75 23 73 50 22 6 57 89 98，物品的重量：89 59 19 43 100 72 44 16 7 64 2.Matlab 代码（1）参数初始化，导入本问题的物品的价值和重量数据，并设定背包最大重量。wei=9575 23 73 50 22 6 57 89 98;val=89 59 19 43 100 72 44 16 7 64;w=300;%总重量约束值（2）随机产生数量为 30 的种群。生成 30*10 的 0-1 矩阵。So=round(rand(30,10);So=hardlim(So);%So为随机产生的矩阵,值为 0 或 1 ZQ,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=-10;%betterl 为当前算出的总价值，ip为代数 whileipsp(sindex)sindex=sindex+1;end newSo(i,:)=So(sindex,:);end fori=1:ZQ So(i,:)=newSo(i,:);end（6）设置的交叉概率pc为90%，产生要配对的父代的序号，经过50次顺序调换，将原有顺序打乱，使相邻两个个体作为交叉的父代 fori=1:ZQ weiindex(i)=i;end fori=1:ZQ point=unidrnd(ZQ-i+1);temp=weiindex(i);weiindex(i)=weiindex(i+point-1);weiindex(i+point-1)=temp;end fori=1:2:ZQ p=rand(1);if(ppc)point=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;end end end（7）设置变异的概率为 5%，产生 50*10 的 0-1 矩阵，对 1 的位置进行变异 M=rand(ZQ,Y)0).*(So*wei-w);better1,you1=max(syd);ifupdatef=better1 better1=updatef;So(you1,:)=updatec;end updatef=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);end;（9）将最优值和参数显示出来。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.结果 如图所示，横坐标是迭代次数，纵坐标是每代的最优解。最优染色体解是：1 0 1 0 1 1 1 0 0 1，即对应着问题描述，数值为 1 的物品放入背包，可得到最大的价值为 388，跟该问题的最优值一样，且背包重量为 294，不超过最大限重 300，且解题速度够快，该代码可行。该实例对应的 matlab 文件名为 GAK.M。二、实例二 1.问题描述 假设：背包的最大重量为1000，物品的数量为 100，物品价值：75 64 68 18 83 55 60 10 18 83 53 87 80 14 92 18 67 22 64 15 80 33 79 81 43 93 74 48 74 72 70 94 98 57 75 98 4 46 9 80 18 96 78 96 24 14 37 50 52 66 63 27 30 50 88 63 100 68 50 61 55 63 47 95 52 40 65 43 69 34 46 26 45 18 94 93 67 3 34 79 60 67 48 65 4 9 28 10 49 77 98 47 56 11 23 4 70 28 95 21 物品重量：27 21 14 82 36 94 88 71 86 69 75 60 74 16 38 49 24 68 87 85 32 70 37 36 65 29 91 6 54 13 78 70 95 2 38 84 30 44 85 75 39 24 42 76 15 53 68 78 75 24 53 84 34 99 32 22 5 80 39 92 34 59 17 41 17 19 28 57 31 1 21 44 47 71 28 9 15 71 36 24 36 81 33 40 69 65 68 73 4 19 1 11 50 13 78 93 34 60 41 35 2.Matlab 代码（1）参数初始化，导入本问题的物品的价值和重量数据，并设定背包最大重量。wei=75 64 68 18 83 55 60 10 18 83 53 87 80 14 92 18 67 22 64 15 80 33 79 81 43 93 74 48 74 72 70 94 98 57 75 98 4 46 9 80 18 96 78 96 24 14 37 50 52 66 63 27 30 50 88 63 100 68 50 61 55 63 47 95 52 40 65 43 69 34 46 26 45 18 94 93 67 3 34 79 60 67 48 65 4 9 28 10 49 77 98 47 56 11 23 4 70 28 95 21;val=27 21 14 82 36 94 88 71 86 69 75 60 74 16 38 49 24 68 87 85 32 70 37 36 65 29 91 6 54 13 78 70 95 2 38 84 30 44 85 75 39 24 42 76 15 53 68 78 75 24 53 84 34 99 32 22 5 80 39 92 34 59 17 41 17 19 28 57 31 1 21 44 47 71 28 9 15 71 36 24 36 81 33 40 69 65 68 73 4 19 1 11 50 13 78 93 34 60 41 35;w=1000;%总重量约束值（2）随机产生数量为 50 的种群。生成 50*100 的 0-1 矩阵。So=round(rand(50,100);So=hardlim(So);%So为随机产生的矩阵,值为 0 或 1 ZQ,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.结果 如图所示，横坐标是迭代次数，纵坐标是每代的最优解。最优染色体解是:0 0 0 1 0 1 1 1 1 0 1 0 0 1 0 1 0 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 1 1 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 1 1 1 1 0 0 0 0 0 1 1 1 0 1 0 1，即对应着问题描述，数值为 1 的物品放入背包，可得到最大的价值为2426，该问题的理论最优值是2460，与理论最优值相近，且背包重量小于1000，解题速度够快，该代码可行。该实例对应的代码程序为 GAK2.M。
