文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 一维下料问题的改进自适应遗传算法
侵权投诉

一维下料问题的改进自适应遗传算法

维普资讯 doc.guandang.net

第 6期

魏凉良等:一维下料问题的改进自适应遗传算法

起;2将。 ()类元素装人第 1组箱子中,每个箱子中 装人 1个元素; 3将:元素及取出的岛,类元 ()类 素装人第 2组箱子中,每个箱子最多装一个:元类素和一个或类元素;4将, ()类元素及取出的 ,,,

3 2遗传算法的基本构成 . 遗传算法的形式化定义为】: G=( A C,E, o P,M,,,, F )

式中: c为个体的编码方法; E为个体适应度评价函数;o P为初始群体;为群体大小;为选择算 子; f为交叉算子;为变异算子;为遗传运算终止 T条件 .

类元素装人第 3组箱子中,个箱子最多每

装一个类元素和一个或岛或类元素;5将, ()卢类元素及剩余的,,类元素分别装入第 4—。卢, 7组箱子中,各组箱子分别装 2 2 34个卢,,,,,, 岛 类元素;6将 y元素按 F算法装人第 8 ()类 F组箱 子中.

3 3求解一维下料问题的 MA G . H A 3 3 1染色体编码方法 . .

假设原材料编号依次是 A,:…,各个零件 A, A,编号依次是 u,:…,其中零件。尺寸为 Z,。u, u,的。

3求解下料问题的改进自适应遗传 算法 3 1算法思想 . 遗传算法是一种基于自然选择和群体遗传机理的搜索算法,模拟了自然选择和自然遗传过程中它 发生的繁殖、交和突变现象.杂在利用遗传算法求解问题时,问题的每个可能的解都被编码成一个“染色体”即个体,干个个体构成了群体 (有可能,若所解 )在遗传算法开始时, .总是随机地产生一些个体 (即初始解 )根据预定的目标函数对每个个体进行, 评价,出一个适应度值.于此适应度值,择个给基选

u的尺寸为 z,::其余依次类推可得其它尺寸的零件编号,各个零件所在原材料的编号依次排列就

构将 成该问题的染色体编码 .

本文的编码使用的是等长度的字符代码编码方法,符号集为数字序号表,{,,,}初始群体如 12… k .由 l2…,,, k的随机排列产生.由个体的染色体码串 即可统计出下料方案.例如[,,,…,,]就 6 3 2 3 8代表一种下料方案 (体中的一个个体 )表示从 6群, 号原料中截取第 1零件, 3原料中截取第 2个 个从号零件等等. 3 3 2目标函数和适应度函数 ..

体用来复制下一代.选择操作体现了“适者生存”原理,好”的个体被选择用来复制,坏”的个体则被““淘汰.然后选择出来的个体经过交叉和变异算子进行再组合生成新的一代.这一群新个体由于继承了 上一代的一些优良性状,而在性能上要优于上一 因

按照本问题的目标要求应使材料利用率最大, 工程上通常希望的结果是:于一批给定的原料和对待下料对象,料后的材料中除一根材料具备最长下

余料外 (于随后的进一步利用 )其它被下料材料便,的余料总长度最小,且完全未使用的原料尽可能多. 换言之,即将一已用材料剩余量的最大值,同完全连未使用材料的长度总和相加作为优化目标函数. 由此可表达为下述目标函数 J:厂 ( )=m x L一 l+k ) ( ≤后 . a( i a 1≤ L ) 式中:完全未使用的原料数量;为第根原材 k为口料上第 _零件的数量;『种 L为原材料长 . 为满足适应度函数的非负性,用如下方法:采

代,这样逐步朝着更优解的方向进化.因此,传算遗 法可以看做是一个由可行解组成的群体逐代进化的 过程.

遗传算法由于其运算简单和解决问题的有效能力而被广泛应用到众多的领域 .论上已经证明,理遗传算法能从概率的意义上以随机的方式寻求到问题的最优解 .另一方面,但实践表明遗传算法的应用也会出现一些不尽人意的问题,些问题中最主要的这是它容易产生早熟现象及局部搜索能力差等.要解决这些问题,就要对基本的遗传算法本身进行调整改进.此外,将遗传算法与问题的特有知识集成到一起所构成的混合遗传算法,有可能

产生求解性能较 佳的方法 .求解一维下料问题时,文采用一种基在本

F X ): (

)厂 )>0, ( X)≤ 0

【 0,

对给定原料数量 k的取值,若过大将直接导致搜索空间的扩大,不利于搜索效率的提高; k过小但又易导致运算错误.先估计一个有富余的原料数应量,可根据 E F P F算法的思想进行估计 .公式如下: r= al+后 +a 3+ bl 2+ 6/2+ 6/3+ b/4+ r / 2 3 4/x

于个体适应度值交叉率和变异率自适应调整的遗传算法,同时,人 B D算法的思想,正无效的染色引 F修体,提高了算法的运行效率和解的质量.

I :

一

式中:一为类元素中的最大长度. L将公式中所有

一维下料问题的改进自适应遗传算法

上一页第2页

你可能喜欢

  • 普通遗传学试题答案
  • 算法语句
  • 算法分析期末试题
  • 算法试卷
  • 算法程序框图试题

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email