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

1、遗传算法2013.6.11一、 实例一：1. 问题描述假设：背包最大重量为300,物品的数量为10,物品的价值：9575 23 7350 22 657 89 98,物品的重量：8959 19 43100 72 4416 7 642. 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=ha

2、rdlim(So); %S。为随机产生的矩阵，值为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

3、 = 1; updatef=-10; %betterl 为当前算出的总价值，ip 为代数 whileip<= dsfori=1:ZQfi(i)=syd(i)-min(syd)+1;endfori=1:ZQ/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%，产生要配对的父代的序号，经

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);if(p<pc)r 一一 -匚一 _ _point=unidrnd(Y-1)+1;for j=point:(Y-1)ch=So(weiindex(i),j);So(weiindex(i),j)=So(weiindex(

5、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) 产生精英染色体，youl是适应度最大的染色体，you2为适应度最小的染色体，最优解为不超过背包容量的适应度最大的syd2数组，better3即为每代的最优值，并用粉色星号画出来。syd =So*val'-pu*So*val'./(So*wei').*(So*wei'-w)>0).*(So*wei'-w);bet

6、ter1,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

7、*val'.*(So*wei'-w)>0);better3,you3 = max(syd2);plot(ip,better3,'-*m');一匚 一 _r .一i 3end;(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(sprin

8、tf('交义概率:%.3f,pc);disp(sprintf('变异概率:%.3f,pm);disp(sprintf('最优解:%.2f',best);3.结果代孰50种群大小十30奴蹄:0.900变异概率:0. 050最伽解；009如图所示，横坐标是迭代次数，纵坐标是每代的最优解。最优染色体解是：10 101110 01,即对应着问题描述，数值为1的物品放入背包，可得到最大的价值为 388,跟该问题的最优 值一样，且背包重量为294,不超过最大限重300,且解题速度够快，该代码可 行。该实例对应的matlab文件名为GAK.M。实例二1.问题描述假设：背包的最

9、大重量为1000,物品的数量为100,物品价值：7564 68188355 601018835387801492186722 641580 33798143 9374487472709498577598 446 98018 96789624 1437505266632730508863100 685061 55634795 524065436934462645189493 67334 79606748 6549281049779847561123 47028 9521物品重量：2721 14823694 887186697560741638492468 878532 70373665 2991

10、654137870952388430 448575 39244276 155368787524538434993222 58039 92345917 41171928573112144477128 91571 36243681 3340696568734191115013 789334 6041352. Matlab 代码(1)参数初始化，导入本问题的物品的价值和重量数据， 并设定背包最大重量wei=75 64681883556010188353878014921867226415803379814393744874727094985775984469801896789624143750526

11、6632730508863100 6850615563479552406543693446264518949367334796067486549281049779847561123470- .a,工工f J'i 二一-一-r理 顿628 95 21;val=27211482369488718669756074163849246887853270373665299165413787095238843044857539244276155368787524538434993222580399234591741171928573112144477128915713624368133406965

12、687341911150137893 34 60 41 35;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.结果代数；500种群大小：驴交叉概率：0- 900变异概率；0. 030最优解：12426.00】> Figure 1口叵区如图所示，横坐标是迭代次数，纵坐标是每代的最优解。最优染，色体解是:00010111