文档介绍：第31卷第6期 2003年6月华南理工大学学报(自然科学版) JournalofSouthChinaUniversityofTechnology (NaturalScienceEdition) June 2Oo3 文章编号:1000-565X(2003)06-0026-05 维下料问题的改进自适应遗传算法魏凉良叶家玮(华南理工大学交通学院,广东广州510640) 摘要:提出采用改进的自适应遗传算法与求解此类问题的一般算法——BFD算法相混合,构成一种改进的自适应混合遗传算法(MAHGA).并将其与另一种新的求解此类问题的EPFF算法进行了精度、,. 关键词:一维下料;改进自适应遗传算法;EPFF算法中图分类号: 文献标识码:A 在某些以条状型材为原材料的生产部门,经常遇到如下形式的下料问题:现有原材料根,原料长度为,要求截成m种长度不同并满足需求量的零件;零件长度为Z,Z:,?,Z;需求量为/1,,/1,:,?, /1,.问应采取什么样的下料方案,使得材料利用率最大,从而达到减少材料损失,降低成本,提高经济效益的目的,这就是所谓一维最优下料问题. ,问题不难解决;当原料品种数和成品品种数均较大时,问题则相当复杂, 算法,然后提出一种改进的混合遗传算法,,本文提出的算法是解决该类问题的又一较好的方法. 1 :设有n个物品//,,//,:,?,//,要装箱发送,已知每个物品的体积为(),()t. E(O,1),i= 1,2,?,n,现规定每个箱子的容量为1,问如何确定装箱方案可使得装完这n个物品所需要用的箱子数目为最小?在本问题中,原材料即可看做箱子,所收稿日期:2002-10-23 作者简介:魏凉良(1979一),女,硕士研究生,主要从事计算机辅助船舶设计、,这是一个 NP(NondeterministicPolynomia1)难题,¨J:1)FF(FirstFit)近似算法,将/1,个物品,,?,顺次装箱,设箱的次序为B,B:,?,B,对某一物品//,,它总是被装到第一个能装下它的箱子中;2)BF(BestFit)近似算法,将物品顺次装箱,要求每个物品装进箱子后留下的空隙最小;3)FFD(FirstFitDecreasing)或BFD(Best FirstDecreasing)近似算法,如果在装箱之前先把他们按体积大小降次排列,再利用FF(或BF)近似算法就得到FFD(或BFD),效果往往不太理想. 2 求解下料问题的EPFF算法 EPFF算法【,将实数列中的元素分成8类,称(2/3,1],(7/12,2/3],(1/2,7/12], (5/12,1/2],(1/3,5/12],(1/4,1/3],(1/5, 1/4],(0,1/5]上的元素分别为