免费预览已结束,剩余4页可下载查看
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
遗传算法解决0-1背包问题北京科技大学物流工程系2013.6.11一、 实例一:1. 问题描述假设:背包最大重量为300,物品的数量为10,物品的价值:9575237350226578998,物品的重量:895919431007244167642. Matlab代码(1) 参数初始化,导入本问题的物品的价值和重量数据,并设定背包最大重量。wei=9575237350226578998;val=89591943100724416764;w=300; %总重量约束值(2) 随机产生数量为30的种群。生成30*10的0-1矩阵。So =round(rand(30,10);So=hardlim(So); %So为随机产生的矩阵,值为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 = 1; updatef=-10; %betterl为当前算出的总价值,ip为代数whileipsp(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:ZQ point=unidrnd(ZQ-i+1);temp=weiindex(i);weiindex(i)=weiindex(i+point-1);weiindex(i+point-1)=temp;endfori=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;endendend(7) 设置变异的概率为5%,产生50*10的0-1矩阵,对1的位置进行变异 M=rand(ZQ,Y)0).*(So*wei-w); better1,you1 = max(syd); ifupdatef=better1 better1=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);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(变异概率: %.3f,pm);disp(sprintf(最优解: %.2f,best);3. 结果如图所示,横坐标是迭代次数,纵坐标是每代的最优解。最优染色体解是:1010111001,即对应着问题描述,数值为1的物品放入背包,可得到最大的价值为388,跟该问题的最优值一样,且背包重量为294,不超过最大限重300,且解题速度够快,该代码可行。该实例对应的matlab文件名为GAK.M。二、 实例二1. 问题描述假设:背包的最大重量为1000,物品的数量为100,物品价值:756468188355601018835387801492186722641580337981439374487472709498577598446980189678962414375052666327305088631006850615563479552406543693446264518949367334796067486549281049779847561123470289521物品重量:27211482369488718669756074163849246887853270373665299165413787095238843044857539244276155368787524538434993222580399234591741171928573112144477128915713624368133406965687341911150137893346041352. Matlab代码(1) 参数初始化,导入本问题的物品的价值和重量数据,并设定背包最大重量。wei=756468188355601018835387801492186722641580337981439374487472709498577598446980189678962414375052666327305088631006850615563479552406543693446264518949367334796067486549281049779847561123470289521;val=2721148236948871866975607416384924688785327037366529916541378709523884304485753924427615536878752453843499322258039923459174117192857311214447712891571362436813340696568734191115013789334604135;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. 结果如图所示,横坐标是迭代次数,纵坐标是每代的最优解。最优染色体解是:0001011110100101011101001000000000001010
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 关于2026年销售数据对接时间协调函4篇范本
- 电力系统继电保护装置故障分析指导
- 事业单位计算机岗2026面试结构化问答强化训练试卷及解析
- 小学教资面试语文结构化高频考题题库参考答案
- 事业单位文秘岗2026面试经典考题结构化问答试卷及答案
- 事业单位计算机岗面试高频考题2026试卷及答案
- 初中化学教资面试答辩题库及参考答案
- 2026高中教资面试数学试讲全真模拟试卷参考答案
- 通知项目完成的正式通知(6篇)
- 2026高中教资面试生物试讲历年真题题库试卷及参考答案
- 大学篮球说课稿课件
- (2025年)零售药店医保培训试题(+答案)
- 初中语文《春》课件
- 4.1 多变的天气 课件2026-2027学年人教版初中地理七年级上册
- 高三英语核心高频词汇语境化教学设计
- 期中复习(1-3单元)分层作业2025-2026学年四年级数学上册新人教版(含答案)
- 2026年其他知识竞赛-国家电网规划发展策划知识竞赛历年参考题库含答案解析
- 面向人工智能的光计算与光互连技术发展路径
- 2026年护士长竞聘质量控制测试题含答案
- 建筑边坡工程验收规范
- 2026中国光纤配线设备智能化管理需求增长研究报告
评论
0/150
提交评论