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

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

维普资讯 doc.guandang.net

华南理工大学学报 (自然科学版 ) 第3 1卷第 6期 20 0 3年 6月 J u n lo o t i a Un v r i f Te h o o y o r a f S u h Ch n i e st o c n l g y V0 . 131 No 6 .

( trl ce c d t n Naua in eE io ) S i

Jn 2 o u e O3

文章编号: 0055 (0 3 0 - 2 - 10 - X 20 )6 0 6 5 6 0 0

一

维下料问题的改进自适应遗传算法 魏凉良叶家玮 (南理工大学交通学院,广东广州 5 0 4 )华 160

摘

要:提出采用改进的自适应遗传算法与求解此类问题的一般算法—— B D算法相 F

混合,成一种改进的自适应混合遗传算法 ( HG .将其与另一种新的求解此类问构 MA A)并 题的 E F P F算法进行了精度、度等方面的比较 .果表明,文方法可以取得较为满意速结本 的效果 .章最后给出了一个实例 .文

关键词:一维下料;改进自适应遗传算法;E F P F算法

中图分类号: 7 . U6 12

文献标识码: A

在某些以条状型材为原材料的生产部门,常经遇到如下形式的下料问题:有原材料根,料长现原度为,求截成 m种长度不同并满足需求量的零 要件;件长度为 Z,,,;求量为/,:…,零 Z… Z需: 1/, , 1 ,

需零件即物品.从计算复杂性来讲,这是一个 NP No d tr nsi P ln mi1题,难精确求 ( n eemiit oy o a)难 c很

解.常的算法有 3种¨: ) F Frt i通 J1 F ( i t s F )近似算法,/个物品,,,顺次装箱,箱的次序将 1, …设为 B,:…,对某一物品/, B, B,,它总是被装到第一 个能装下它的箱子中;) F B s Ft 2 B ( et i )近似算法,将物品顺次装箱,要求每个物品装进箱子后留下的空 隙最小; ) F FrtFtD ces g 3 F D( i i erai )或 B D( et s n F B s

/. 1问应采取什么样的下料方案,, 使得材料利用率最大,而达到减少材料损失,低成本,从降提高经济效

益的目的,就是所谓一维最优下料问题 .这 以往有不少人研究过这个问题 .当下料的成品

品种数较少时,问题不难解决;当原料品种数和成品品种数均较大时,问题则相当复杂,工建模也很困人难 .文先列出求解这类问题的一般算法和 E F 本 PF算法,然后提出一种改进的混合遗传算法,进行计并算比较.结果表明,本文提出的算法是解决该类问题 的又一较好的方法 .

Fr eraig近似算法, i t ces ) sD n如果在装箱之前先把他们按体积大小降次排列,再利用 F或 B )近似算 F( F法就得到 F D ( B D F或 F )近似算法.似算法的求近解结果与给定数据有很大关系,果往往不太理想.效

2求解下料问题的 E F P F算法 EF P F算法【是求解装箱问题的一种较新的算 2 法.它将所有的箱子分成 8,组将实数列中的元素分

1求解下料问题的一般算法 一

维下料问题可建模为装箱问题 .箱问题的装

一

般提法如下:有 n物品/,,,,,要装箱发设个//…/,/ :/

成 8类, (/,] (/ 2,/] (/,/ 2,称 2 3 1, 7 1 2 3, 12 7 1] (/ 2,/] 1 3,/ 2, (/,/] (/, 5 1 12,(/ 5 1] 14 13, 15 1] (,/]上的元素分别为 a,:a,l: 4/, 0 15 a,,卢,,卢 卢,,卢,元素, a,,称为 a类元素,类 a,:a统同时用 a a,2a,lb,3b,,la,3b,2b,4r分别表示 a a,2a,, la,3卢,:,,元素的个数,卢, y类因此有 a= a+a :+ a EF, P F算法步骤如下: I ( )从卢,。 :卢,类元素中卢 取出口个元素与 a类元素放在一起 ( a,,或,> b :+

送,已知每个物品的体积为 () () t (,)i= , E O1, .

1 2…,,,, n现规定每个箱子的容量为 1问如何确,定装箱方案可使得装完这 n个物品所需要用的箱子 数目为最小?本问题中,材料即可看做箱子,在原所

收稿日期: 0 2 1 -3 2 0 -02

b+b,, 则取完所有的卢,, :卢,类元素

为止 )再从卢,卢,类元素中取出 a个元素与 a类元素放在一。 ::

作者简介:凉良 (99一)女,士研究生,要从事计魏 17,硕主 算机辅助船舶设计、造及人工智能技术应用研究制

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

第1页

你可能喜欢

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

热门文档

相关文档

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