遗传算法求解0-1背包问题

《遗传算法求解0-1背包问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、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);holdon;（5）用轮盘赌进行选择操作，用选择出的个体构成的种群替代旧的种群better1=1;ip=1;updatef=-1

3、0;%betterl为当前算出的总价值，ip为代数whileip<=dsfori=1:ZQfi(i)=syd(i)-min(syd)+1;end9fori=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,:);end（1）设置的交叉概率pc为90%，产生要配对的父代的序

4、号，经过50次顺序调换，将原有顺序打乱，使相邻两个个体作为交叉的父代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);9if(p

5、i+1),j);So(weiindex(i+1),j)=ch;endendend（1）设置变异的概率为5%，产生50*10的0-1矩阵，对1的位置进行变异M=rand(ZQ,Y)<=pm;So=So-2.*(So.*M)+M;（2）产生精英染色体，you1是适应度最大的染色体，you2为适应度最小的染色体，最优解为不超过背包容量的适应度最大的syd2数组，better3即为每代的最优值，并用粉色星号画出来。syd=So*val'-pu*So*val'./(So*wei').*((So*wei'-w)>0).*(So*wei'-w);[better1,you1]=ma

6、x(syd);ifupdatef>=better1better1=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]=m

7、ax(syd2);9plot(ip,better3,'-*m');end;（1）将最优值和参数显示出来。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));1.结果