资源描述：
《利用遗传算法求解装箱问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第24卷 第4期延安大学学报(自然科学版)Vol.24No.42005年12月JournalofYananUniversity(NaturalScienceEdition)Dec.2005a利用遗传算法求解装箱问题12李大可,杨花娥(1.西安建筑科技大学理学院,陕西西安710054;2.西安文理学院数学系,陕西西安710063)摘 要:遗传算法通过编码技术,运用繁殖、杂交和突变等遗传算子,对染色体组成的初始种群,进行适应度分析,构成优胜劣汰、适者生存的自然环境,产生出新的更加优良的种群.经过若干代的进化,最终求得适合问题的最优解.关键词:遗传算法;装箱
2、问题;遗传算子中图分类号:TP301.6文献标识码:A文章编号:10042602X(2005)04200322021 遗传算法子总容积条件下,如何使装入装子物体的总价值最大.这里wi、pi和W都是正整数,i=1,2,⋯,n.遗传算法是一种模仿生物遗传与进化过程而得问题的一个可行解可以用如下二进制字符串表出的一种随机优化方法,它是“仿生学”在数学领域示:X=(x1,x2,⋯,xn),xi为如下021变量:xi=1,中的直接引用.它利用简单的编码技术和进化繁殖表示物品i被装箱;xi=0表示物品i未被装箱,i=机制来表现复杂的现象,进而提供了一种求解复杂1,
3、2,⋯,n.从而向量X就是一个装箱方案.系统优化问题的通用框架.由于它不依赖问题的具装箱问题可以用如下数学模型表述:n体领域,不受搜索空间的限制性假设的约束,不要求max∑pi×xi一定具有目标函数的解析表达式,因此,遗传算法应i=1n用的领域十分广泛.遗传算法的主要过程如下.s.t.∑wixi≤W,xi∈{0,1},i=1,2,⋯,n.i=11)对研究的变量或对象进行编码形成染色体,并随机地建立一个初始群体.2 应用举例2)计算群体中诸染色体的适应度.3)执行遗传算子操作.包括:繁殖,将适应度高下面我们通过一个经济活动中常见的实际问的染色体进行繁殖,
4、添入到群体中,删除适应度低的题,介绍如何利用遗传算法解决装箱问题,这是遗传染色体;杂交,随机选出染色体对,基基因进行片段算法最简单、最基本的应用模式.交叉换位,产生新的染色体对;突变,随机改变某染例 现有100万元资金打算在5个不同的地方色体的某个基因,得到新染色体.修建某种工厂,由于条件不同,所需投资分别为:w14)根据某种条件判断计算过程是否可以结束,=56,w2=20,w3=54,w4=42,w5=15(单位:万如果不满足结束条件,则返回到步骤2,直到满足结元),工厂建成后,每年能得到的利润分别为:p1=束条件为止.7,p2=5,p3=9,p4=
5、6,p5=3(单元:万元).问如装箱问题也称背包问题,它可以表述为一个单何确定投资地点,使总投资不超过100万元,且使建约束的纯整数规划问题.设有一个箱子的总容积为成后每年所获总利润最多?W,另有n个不同的物品,其体积分别w1,w2,⋯,此问题可以看成是一种装箱问题.其中装箱数wn,其价值分别为p1,p2,⋯,pn,问题是在不超过箱学模型中的参数分别为:xi表示在第i个地方是否a 收稿日期:20050710作者简介:李大可(1958),男,陕西西安市人,西安建筑科技大学副教授.©1994-2007ChinaAcademicJournalElectron
6、icPublishingHouse.Allrightsreserved.http://www.cnki.net第4期 李大可,杨花娥:利用遗传算法求解装箱问题 33修建工厂(i=1,2,⋯,5),W=100,n=5,w1=56,代X.(1)w2=20,w3=54,w4=42,w5=15,p1=7,p2=5,利用解码法对第一代染色体中的不可行解x1(2)p3=9,p4=6,p5=3,目标函数:maxf(X)=7x1进行改造,使其转化成可行解x1=[1;0;0;0;0],(1)(1)+5x2+9x3+6x4
7、+3x5,约束条件:g(X)=56x1f(x1=7,而g(x1)=56.(其中[1;0;1;0;0]还是+20x2+54x3+42x4+42x4+15x5≤100.不可行解)编码是应用遗传算法首先要解决的问题,在遗需要说明的是对种群实施各种遗传运算后,都传算法的实际应用中,根据所研究对象的不同性质,要检验解X的可行性,凡是不可行的,都可按上述将问题的可行解设计成染色体.遗传基因也可以取解码法转化成可行解.不同的表示形式,在下面的讨论中,遗传基因用0ö1在对染色体进行繁殖运算时,首先计算各个染(m)(m)(m)码表示,这是一种最常用的编码形式.遗传算法操
8、作色体的生存概率.对于给定群体x1,x2,⋯,xn,(m)的对象是用遗传基因表示的染色体,每个
