遗传算法求解0-1背包问题(共9页).docx
精选优质文档-倾情为你奉上遗传算法解决0-1背包问题北京科技大学物流工程系2013.6.11一、 实例一：1. 问题描述假设：背包最大重量为300，物品的数量为10，物品的价值：9575237350226578998，物品的重量：895919431007244167642. Matlab代码（1） 参数初始化，导入本问题的物品的价值和重量数据，并设定背包最大重量。wei=9575237350226578998;val=89591943100724416764;w=300; %总重量约束值（2） 随机产生数量为30的种群。生成30*10的0-1矩阵。So =round(rand(30,10);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=-10; %betterl为当前算出的总价值，ip为代数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;while p >sp(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:ZQ point=unidrnd(ZQ-i+1);temp=weiindex(i);weiindex(i)=weiindex(i+point-1);weiindex(i+point-1)=temp;endfori=1:2:ZQ p=rand(1);if(p<pc)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;endendend（7） 设置变异的概率为5%，产生50*10的0-1矩阵，对1的位置进行变异 M=rand(ZQ,Y)<=pm; So=So-2.*(So.*M)+M;（8） 产生精英染色体，you1是适应度最大的染色体，you2为适应度最小的染色体，最优解为不超过背包容量的适应度最大的syd2数组，better3即为每代的最优值，并用粉色星号画出来。syd =So*val'-pu*So*val'./(So*wei').*(So*wei'-w)>0).*(So*wei'-w); better1,you1 = max(syd); ifupdatef>=better1 better1=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');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. 结果如图所示，横坐标是迭代次数，纵坐标是每代的最优解。最优染色体解是：1010111001，即对应着问题描述，数值为1的物品放入背包，可得到最大的价值为388，跟该问题的最优值一样，且背包重量为294，不超过最大限重300，且解题速度够快，该代码可行。该实例对应的matlab文件名为GAK.M。二、 实例二1. 问题描述假设：背包的最大重量为1000，物品的数量为100，物品价值：756468188355601018835387801492186722641580337981439374487472709498577598446980189678962414375052666327305088631006850615563479552406543693446264518949367334796067486549281049779847561123470289521物品重量：27211482369488718669756074163849246887853270373665299165413787095238843044857539244276155368787524538434993222580399234591741171928573112144477128915713624368133406965687341911150137893346041352. Matlab代码（1） 参数初始化，导入本问题的物品的价值和重量数据，并设定背包最大重量。wei=756468188355601018835387801492186722641580337981439374487472709498577598446980189678962414375052666327305088631006850615563479552406543693446264518949367334796067486549281049779847561123470289521;val=2721148236948871866975607416384924688785327037366529916541378709523884304485753924427615536878752453843499322258039923459174117192857311214447712891571362436813340696568734191115013789334604135;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. 结果如图所示，横坐标是迭代次数，纵坐标是每代的最优解。最优染色体解是:0001011110100101011101001000000000001010100001011001110000010000000000010100010001001111000001110101 ，即对应着问题描述，数值为1的物品放入背包，可得到最大的价值为2426，该问题的理论最优值是2460，与理论最优值相近，且背包重量小于1000，解题速度够快，该代码可行。该实例对应的代码程序为GAK2.M。专心-专注-专业
