遗传算法求解01背包问题.docVIP

PAGE PAGE 2 遗传算法 ——解决0-1背包问题 北京科技大学物流工程系 2013.6.11 实例一： 问题描述 假设：背包最大重量为300，物品的数量为10， 物品的价值：[95 75 23 73 50 22 6 57 89 98]， 物品的重量：[89 59 19 43 100 72 44 16 7 64] Matlab代码 参数初始化，导入本问题的物品的价值和重量数据，并设定背包最大重量。 wei=[9575 23 73 50 22 6 57 89 98]; val=[89 59 19 43 100 72 44 16 7 64]; w=300; %总重量约束值 随机产生数量为30的种群。生成30*10的0-1矩阵。 So =round(rand(30,10)); So=hardlim(So); %So为随机产生的矩阵,值为0或1 [ZQ,Y] = size(So); 迭代次数为50代，交叉概率为90%，变异概率为5%. ds = 50; pc = 0.9; pm = 0.05; 设置适应度函数，利用惩罚函数降低不合格解的适应度，惩罚因子设为1.5. pu=1.5; syd =So*val-pu*So*val./(So*wei).*((So*wei-w)0).*(So*wei-w); figure(1); hold on; 用轮盘赌进行选择操作，用选择出的个体构成的种群替代旧的种群 better1=1; ip = 1; updatef=-10; %betterl为当前算出的总价值，ip为代数 whileip= ds fori=1:ZQ fi(i)=syd(i)-min(syd)+1; end fori=1:ZQ sp(i)=fi(i)/sum(fi); end fori=2:ZQ sp(i)=sp(i-1)+sp(i); end fori=1:ZQ p=rand(1); sindex=1; while p sp(sindex) sindex=sindex+1; end newSo(i,:)=So(sindex,:); end fori=1:ZQ So(i,:)=newSo(i,:); end 设置的交叉概率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 设置变异的概率为5%，产生50*10的0-1矩阵，对1的位置进行变异 M=rand(ZQ,Y)=pm; So=So-2.*(So.*M)+M; 产生精英染色体，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; 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; 将最优值和参数显示出来。 syd2 =So*val-So*v