您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 质量控制/管理 > 遗传算法求解0-1背包问题
遗传算法——解决0-1背包问题北京科技大学物流工程系2013.6.112一、实例一:1.问题描述假设:背包最大重量为300,物品的数量为10,物品的价值:[9575237350226578998],物品的重量:[89591943100724416764]2.Matlab代码(1)参数初始化,导入本问题的物品的价值和重量数据,并设定背包最大重量。wei=[9575237350226578998];val=[89591943100724416764];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);holdon;(5)用轮盘赌进行选择操作,用选择出的个体构成的种群替代旧的种群better1=1;ip=1;updatef=-10;%betterl为当前算出的总价值,ip为代数whileip=dsfori=1:ZQfi(i)=syd(i)-min(syd)+1;endfori=1:ZQ3sp(i)=fi(i)/sum(fi);endfori=2:ZQsp(i)=sp(i-1)+sp(i);endfori=1:ZQp=rand(1);sindex=1;whilepsp(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);weiindex(i+point-1)=temp;endfori=1:2:ZQp=rand(1);if(ppc)4point=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;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=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]=max(syd2);plot(ip,better3,'-*m');5end;(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.结果6如图所示,横坐标是迭代次数,纵坐标是每代的最优解。最优染色体解是:[1010111001],即对应着问题描述,数值为1的物品放入背包,可得到最大的价值为388,跟该问题的最优值一样,且背包重量为294,不超过最大限重300,且解题速度够快,该代码可行。该实例对应的matlab文件名为GAK.M。二、实例二1.问题描述假设:背包的最大重量为1000,物品的数量为100,物品价值:[756468188355601018835387801492186722641580337981439374487472709498577598446980189678962414375052666327305088631006850615563479552406543693446264518949367334796067486549281049779847561123470289521]物品重量:[2721148236948871866975607416384924688785327037366529916541378709523884304485753924427615536878752453843499322258039923459174117192857311214447712891571362436813340696568734191115013789334604135]2.Matlab代码(1)参数初始化,导入本问题的物品的价值和重量数据,并设定背包最大重量。wei=[7564681883556010188353878014921867226415803379814393744874727094985775984469801896789624143750526663273050886310068506155634795524065436934462645189493673347960674865492810497798475611234707289521];val=[2721148236948871866975607416384924688785327037366529916541378709523884304485753924427615536878752453843499322258039923459174117192857311214447712891571362436813340696568734191115013789334604135];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);holdon;其他代码与上述实例一样,在此不做赘述。3.结果8如图所示,横坐标是迭代次数,纵坐标是每代的最优解。最优染色体解是:[0001011110100101011101001000000000001010100001011001110000010000000000010100010001001111000001110101],即对应着问题描述,数值为1的物品放入背包,可得到最大的价值为2426,该问题的理论最优值是2460,与理论最优值相近,且背包重量小于1000,解题速度够快,该代码可行。该实例对应的代码程序为GAK2.M。
本文标题:遗传算法求解0-1背包问题
链接地址:https://www.777doc.com/doc-6319822 .html