2022年遗传算法求解-背包问题 .pdf

《2022年遗传算法求解-背包问题 .pdf》由会员分享，可在线阅读，更多相关《2022年遗传算法求解-背包问题 .pdf（8页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、遗传算法解决 0-1 背包问题北京科技大学物流工程系2013.6.11 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 2 一、实例一：1.问题描述假设：背包最大重量为300，物品的数量为 10，物品的价值： 95 75 23 73 50 22 6 57 89 98，物品的重量： 89 59 19 43 100 72 44 16 7 64 2.Matlab 代码（1） 参数初始化，导入本问题的物品的价值和重量数据，并设定背包最大

2、重量。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=hardlim(So); %So为随机产生的矩阵 ,值为 0 或 1 ZQ,Y = size(So); （3） 迭代次数为 50代，交叉概率为90%，变异概率为 5%. ds = 50; pc = 0.9; pm = 0.05; （4） 设置适应度函数， 利用惩罚函数降低不合格解的适应度，惩罚因子设为

3、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 为代数whileipsp(sindex) sindex=sindex+1; end newSo(i,:)=So(sindex,:); end fori=1:ZQ So(i,:)=newSo(i,:); end （6） 设置的交叉概率pc为

4、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) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -

5、 第 3 页，共 8 页 - - - - - - - - - 4 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 （7） 设置变异的概率为5%，产生 50*10 的 0-1 矩阵，对 1 的位置进行变异M=rand(ZQ,Y)0).*(So*wei-w); better1,you1 = max(syd); ifupdatef=better1 better1=updatef;

6、 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); 名师资料总结 - - -精品

7、资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - 5 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(变异

8、概率 : %.3f,pm); disp(sprintf(最优解 : %.2f,best); 3.结果名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - 6 如图所示，横坐标是迭代次数，纵坐标是每代的最优解。最优染色体解是： 1 0 1 0 1 1 1 0 0 1，即对应着问题描述，数值为1 的物品放入背包，可得到最大的价值为388，跟该问题的最优值一样，且背包重量为294，不超过最大限重 300，且解题速度够快，该代码可行。该实例对

9、应的 matlab 文件名为 GAK.M。二、实例二1.问题描述假设：背包的最大重量为1000，物品的数量为100，物品价值： 75 64 68 18 83 55 60 10 18 83 53 87 80 14 92 18 6722 64 15 80 33 79 81 43 93 74 48 74 72 70 94 98 57 75 98 446 9 80 18 96 78 96 24 14 37 50 52 66 63 27 30 50 88 63100 68 50 61 55 63 47 95 52 40 65 43 69 34 46 26 45 18 9493 67 3 34 79 60

10、 67 48 65 4 9 28 10 49 77 98 47 56 1123 4 70 28 95 21 物品重量： 27 21 14 82 36 94 88 71 86 69 75 60 74 16 38 49 2468 87 85 32 70 37 36 65 29 91 6 54 13 78 70 95 2 38 8430 44 85 75 39 24 42 76 15 53 68 78 75 24 53 84 34 99 3222 5 80 39 92 34 59 17 41 17 19 28 57 31 1 21 44 47 7128 9 15 71 36 24 36 81 33

11、40 69 65 68 73 4 19 1 11 5013 78 93 34 60 41 35 2.Matlab 代码（1） 参数初始化，导入本问题的物品的价值和重量数据，并设定背包最大重量。wei=75 64 68 18 83 55 60 10 18 83 53 87 80 14 92 18 67 22 6415 80 33 79 81 43 93 74 48 74 72 70 94 98 57 75 98 4 46 980 18 96 78 96 24 14 37 50 52 66 63 27 30 50 88 63 100 6850 61 55 63 47 95 52 40 65 43

12、69 34 46 26 45 18 94 93 67 334 79 60 67 48 65 4 9 28 10 49 77 98 47 56 11 23 4 70名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - 7 28 95 21; val=27 21 14 82 36 94 88 71 86 69 75 60 74 16 38 49 24 68 8785 32 70 37 36 65 29 91 6 54 13 78 70 9

13、5 2 38 84 30 4485 75 39 24 42 76 15 53 68 78 75 24 53 84 34 99 32 22 580 39 92 34 59 17 41 17 19 28 57 31 1 21 44 47 71 28 915 71 36 24 36 81 33 40 69 65 68 73 4 19 1 11 50 13 7893 34 60 41 35; w=1000; %总重量约束值（2） 随机产生数量为 50 的种群。生成 50*100 的 0-1 矩阵。So =round(rand(50,100); So=hardlim(So); %So为随机产生的矩阵 ,

14、值为 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); hold on; 其他代码与上述实例一样，在此不做赘述。3.结果名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -

15、 - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - 8 如图所示，横坐标是迭代次数，纵坐标是每代的最优解。最优染色体解是 :0 0 0 1 0 1 1 1 1 0 1 0 0 1 0 1 01 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 10 1 0 1 0 0 0 0 1 0 1 1 0 0 1 1 1 0 0 00 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 01 0 0 0 1 0 0 1 1 1 1 0 0 0 0 0 1 1 1 01 0 1，即对应着问题描述，数值为1 的物品放入背包，可得到最大的价值为 2426， 该问题的理论最优值是2460， 与理论最优值相近， 且背包重量小于 1000，解题速度够快，该代码可行。该实例对应的代码程序为GAK2.M 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -