采用遗传算法的矩形件优化下料模型

　制造技术/工艺装备现代制造工程2009年第1期采用遗传算法的矩形件优化下料模型陈勇,王玫,熊艳(四川大学制造科学与工程学院,成都610065)摘要:矩形优化排样问题是典型的组合优化问题,具有NPC(NonpolynomialComplete)难度。针对此类问题的复杂性,提出一个实用的遗传算法模型,该模型在选择算子中,提出新的适值函数,采用无回放随机联赛选择,同时引入精英保护策略;在解码中,提出以边和面积匹配同时达到较优的原则,对剩余矩形匹配算法进行改进。最后通过测试,证明此模型能较好地解决下料问题。关键词:遗传算法;优化下料;匹配原则中图分类号:TP391;TH16　文献标识码:A　文章编号:1671—3133(2009)01—0063—04AgeneticalgorithmforthemodernofrectangularpackingproblemCHENYong,WANGMei,XIONGYan(SchoolofManufacturingScience&Engineering,SichuanUniversity,Chengdu610065,CHN)Abstract:Theoptimallayoutofrectangularpartsisatypicalcombinationaloptimizationproblem,andalsoaNPC(NonpolynomialComplete)problem.Accordingtothecomplexityofthisproblem,anutilitarianmodelwasputforward.Fortheselectionopera2tor,thismodelhaspresentedanewfitnessfunction,adoptingstochastictournamentselectionwithoutputtingback,andtheelitismschemewasintroducedinit.Inordertoimprovetheremainingrectangularmatchingalgorithm,anewmatchingprinciplewhichmakestheareaandedgematchingachieveoptimizationhasbeenpresentedinthedecoder.Finallythroughexperimentaltest,andtheresultsconfirmthatthismodelcanresolverectanglecuttingproblembetter.Keywords:geneticalgorithm;optimalcutting;matchingprinciple0　引言“下料问题”又称为“排样问题”或者“切割问题”,是指把需要的多种规格、多种类型的零件排放在规定尺寸的多张矩形板材上,如何确定下料,以使板材的耗用量最低或者利用率最大[123]。这类问题属于NPC难题,至今尚未找到多项式时间算法。针对此类问题的复杂性,国内外许多学者从各个方面做了大量深入的研究,相继提出了一些近似算法[4]。到20世纪末期,随着遗传算法、模拟退火算法和神经网络算法等现代智能优化算法的成熟,一些研究者开始将它们应用于零件排样中,取得了一定成果[5]。遗传算法属于一种全局优化算法,具有解决非线性问题、鲁棒性强、全局最优性不依赖于问题模型、可并行性、高效率及全局搜索能力强等特点[6],但具体运用还存在一些不足,例如文献[1]、文献[3]中用的都是随机性较强的“轮盘赌”选择方法。针对遗传算法在下料问题中的运用不足,本文设计一个实用的遗传算法模型来解决矩形件优化下料问题。此模型在已有遗传算法模型的基础上改进:在交叉运算后采用一个简单的修复策略修复非法染色体;为增加种群的多样性、防止早熟,本文以耗用板材的前n-1块板材的利用率作为适值函数,评价染色体的优劣;采用无回放随机联赛法进行选择,同时引入精英保护策略保护优秀染色体;在解码时,对剩余矩形匹配算法[7]的匹配原则进行改进,使矩形件的排样更快、更优。最后通过测试,证明此模型能较好地解决下料问题。1　排样问题描述矩形件排样问题是排样问题中研究最多、应用最广的一类问题,其实质是通过设计一种合适的排样方法和一个合理的排样顺序,使零件在板材上的排样能够达到较优。其数学描述如下[7]。设有各种大小同质矩形零件集合{Pi},i∈[1,n],其面积集合为{bi};另有原材料板材集合{Aj},j∈[1,m],其面积集合为{aj};排样工作就是选出适当的36　现代制造工程2009年第1期制造技术/工艺装备板材集合{Aj′},j′∈[1,k],其面积集合为{aj′},将零件集合中的所有零件合适地安排在此板材集合中的某个板材上,并确定零件在该板材上的位置和方向。优化排样即是寻找合理的板材集合{Aj′},以及其上零件的合理放置布局,在满足以下两个条件时:1)所有零件必须在矩形板材以内;2)零件之间不得交叉重叠,使目标函数F达到最大:F=max(∑ni=1bi/∑kj′=1aj′)2　遗传算法遗传算法是一种全局数值优化方法,与传统搜索方法不同,它是从一组随机产生的初始解开始搜索,经过交叉、变异和选择,反复迭代,最后收敛于最好的染色体,也就是问题的最优解或次优解[8]。遗传算法的基本步骤、流程[7]如图1所示。图1　遗传算法基本流程211　编码编码是把一个问题的可行解从解空间转换到遗传算法能够处理的搜索空间的转换方法。常用的编码方法有二进制编码、实数编码和符号编码。本文采用整数编码:以输入的矩形零件的总数为依据对每一块零件编号,每一个编号就是这块零件在板材上的排列顺序,所有零件的编号结合在一起就是一个染色体,即一个染色体就是从0到n-1(n表示零件的总数)的一列不重复的随机数,例如一共有五个零件,则编码可能为(2,0,1,4,3),其意义就是首先排2号零件,其次排0号,再排1号、4号和3号。212　交叉和变异交叉是获得新染色体的直接而有效的方法,它可以改善遗传算法的全局搜索能力,维持群体的多样性。然而在无重复的整数编码的染色体中,通过交叉,往往会使某些染色体变得不合法,例如:交叉前染色体:P1:(5370|2164)P2:(2057|6413)交叉后染色体:R1:(5370|6413)R2:(2057|2164)交叉后的两个染色体中都出现了重复的数字(R1中为3,R2中为2),这样的染色体显然不合法,需要修复。已有的文献中大都采用文献[7]中用到的交叉方法,这种方法是先交换部分基因,再进行交叉。本文所用的方法是:先让染色体进行单点交叉,然后从染色体的交叉点出发,分别找出两个染色体交叉点前/后相同的基因,把它们记录下来,然后再把配对染色体交叉点后记录下来的基因进行交换。上例中,R1中交叉点前/后相同的基因是3,R2中是2,把交叉点以后的3和2交换,其结果为:R1:(5370|6412)R2:(2057|3164)显然,通过修复,两个染色体都合法。交叉运算决定了遗传算法的全局搜索能力,变异运算决定了遗传算法的局部搜索能力。将两者有机地结合,能够使遗传算法以良好的搜索性能完成最优化问题的寻优过程[9]。本文介绍两种常用的变异方法[10]。1)变换变异:(53|706412)](57|306412)2)反转变异:(53|7064|12)](53|1064|72)213　适值计算及选择在板材排样中,大都以板材的总体利用率作为遗传算法的适应值,然而,在排样过程中有两种情况:一是种群中各个染色体使用的板材的数量不同;二是种群中各个染色体所用板材的数量相同,而最后一块板材的利用率不同。排样过程中最后一块板材上排样的零件数目和面积大都不相同,如果以所有板材的利用率作为衡量染色体优劣的,则在板材耗用量相同的情况下是无法体现出优劣的。当零件个数确定以后,如果最后一块板材上排样的零件面积不同,则前n-1块板材上排样零件的面积也不相同,如果以前n-1块板材的利用率作为适值函数则可较好地表示出排样的优劣情况,如图2所示的排样方案。图2　零件排样示意图板材面积为S,第i个零件的面积为si,则其适值函数F(x)为:F(x)=∑n-2i=1si/[(K-1)S]46　制造技术/工艺装备现代制造工程2009年第1期式中:K为板材集合。已有的文献中大都采用比例选择,也称为“轮盘赌”选择。这种方法有如下几点不足。1)随机性较强,有时适应值大的染色体也可能选择不上,导致种群退化。2)某些适应值大的个体迅速繁殖,导致算法早熟,收敛到局部最优解。3)当各个染色体的适应值接近时,选择的误差可能增大。针对以上不足,笔者采用随机联赛选择方法,并对其进行改进,然后应用于选择,同时还引入精英保护策略将最好的染色体直接复制到下一代。在随机联赛中,适应值大的染色体一旦被选择进行联赛,则一定会选上。如果限定每个染色体至多有一次机会参加竞争,则可避免重复选择的问题。将经过交叉和变异的子代与父代种群合并在一起,组成一个新的种群参加竞争选择,如图3所示,每次将选择上的染色体放入新种群中参加下一次的交叉和变异,同时将此染色体从竞争种群中去除。为了减少精英流失,采用精英保护策略,即将当前种群中最好的染色体保护起来,不让其参与交叉和变异,直接复制到下一代种群中,具体操作如图4所示。经过改进,既保证了种群的多样性,又不会早熟,同时防止了精英的丢失。图3　联赛选择示意图图4　精英保护策略214　解码排样问题中的解码操作是实现排样的关键技术。在板材上排样时,要尽量选择一个最佳匹配方案,而剩余矩形匹配算法,就是在充分利用零件与剩余矩形板材之间的匹配关系的条件下进行的排样操作。剩余矩形匹配算法中的核心是匹配原则,而实际应用时,往往都是希望在保证排样原则的条件下用来排样的板材的面积要尽量小,最好是刚好排下矩形零件,没有一点废料。文献[7]中使用的匹配原则是使零件的长度尽量接近板材的长度或者宽度,即零件的长度与板材的长度或者宽度的比值要大,这种匹配原则简单实用,但还可以改进。本文改进的原则是:在矩形零件能够排下的前提下,使零件和板材的长度和面积同时达到一个较优的匹配。笔者认为面积匹配也可以作为匹配原则,当边长匹配值在某一邻域内变化时,可以根据面积匹配值确定选材优劣;也就是使零件和板材在边长比值较大的情况下,面积比值也要达到较大。如何将边长匹配和面积匹配有机地结合是一个具有两个目标的多目标优化问题。本文使用一种简单的方法———权重法,即给边长和面积的匹配值分别分配一个权重值w1、w2,w1+w2=1,使{w1(li/L)+w2(si/S)}最大,其中li和si为第i个零件的边长和面积,L和S为用来排样第i个零件的板材的边长和面积。如图5所示,当有一系列板材都适合排下零件而边长比值又相近时,面积匹配则非常必要。图5　匹配选材示意图综上所述,得出本文的遗传算法模型,如图6所示。图6　遗传算法流程模型3　计算实例此实例采用文献[3]算例1中的数据,取种群大小为80,交叉概率为0195,变异概率为0105,板材长为600mm,宽为400mm,其余参数见表1。311　权重判定实验是通过测试在同一条件下匹配的权重值不同时其算法的收敛情况,实验总共分五组,每组测试30次,迭代次数为35,分别记录其收敛次数,最后计算56　现代制造工程2009年第1期制造技术/工艺装备平均收敛次数,结果见表2。表1　矩形零件数据序　号数　量长/mm宽/mm131307023140803114010041220210532409062300707312080833509091310130103130110表2　权重实验数据序号权重参数w1w2收敛次数1组2组3组4组5组平均收敛次数11　0　1114101514121820190111619111513141830170131716191515161440150151713151915151850130171416161319151660110191917191014151870　1　15161817151612　　从以上数据可以看出,当w1=1,w2=0,即只以边作为匹配条件计算时,相对其他收敛较慢,如果以边和面积同时作为匹配条件,可以加速收敛,提高效率。312　排样测试通过以上判定,文中以w1=017,w2=013进行测试,迭代次数为100,其他参数不变,得出的排样结果如图7所示。图7　零件排样此算例若用一般方法排样需用三块板材。利用此法则仅需两块板材。4　结语本文研究了遗传算法在矩形板材下料中的应用,在交叉算子中应用修复策略,使染色体变得合法;通过使用改进后的选择算子,既能够保证种群的多样性,防止早熟,又能够减少精英的流失,防止退化;遗传算法和剩余矩形匹配算法都能够使矩形排样达到优化,将具有局部优化特性的剩余矩形匹配算法作为具有全局优化特性的遗传算法的解码方法,可以有效地减少算法时间,提高板材利用率。另外,在剩余矩形匹配算法中,除了边匹配外,面积匹配也非常重要,怎样将两者有机地结合可进一步研究。参考文献:[1]　曹炬,胡修彪.大规模矩形件优化排样的遗传算法[J].成形技术,1999(4).[2]　岳琪.基于遗传退火算法板式家具大规模矩形件优化下料研究[D].哈尔滨:东北林业大学,2005.[3]　马炫,张亚龙.基于遗传算法的大规模矩形件优化排样[J].智能系统学报,2007,2(5).[4]　FarleyAA.Mathematicalprogrammingmodelsforcut2ting2stockproblemsintheclothingindustry[J].Journaloftheoperationalresearchsociety,1988,39(1).[5]　张克.二维矩形件优化排样问题研究[D].济南:山东大学,2006.[6]　陈永光.遗传算法及模糊控制理论在木板优化下料系统中的应用[D].北京:北京林业大学,2003.[7]　杨威.板材排样优化的计算智能方法研究[D].成都:四川大学,2002.[8]　玄光男,程润伟.遗传算法与工程设计[M].北京:科学出版社,2000.[9]　周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1999.[10]　黄红兵,矩形件下料优化排样的遗传算法[D].南宁:广西师范大学,2005.作者简介:陈勇,硕士研究生,研究方向:计算机辅助设计与制造。作者通讯地址:四川大学望江校区制造科学与工程学院07研(成都610065)E2mail:firtish@126.com收稿日期:200820720366