基于遗传算法的一刀切矩形排料求解

《基于遗传算法的一刀切矩形排料求解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据第26卷第3期2008年6月江西科学JIANGXISCIENCEV01．26No．3Jun．2008文章编号：1001—3679(2008)03一0406—04基于遗传算法的一刀切矩形排料求解徐新爱1，刘翌2，王洪发3(1．江西教育学院，江西南昌330029；2．江西旅游商贸职业学院，江西南昌330100；3．浙江水利水电专科学校，浙江杭州310018)摘要：采用遗传算法对一刀切矩形排料问题进行求解，在排料过程中引入了启发式思想。并针对这个具体问题设计了新的交叉算子和变异算子，新的遗传算子更适合求解一刀切矩形排料问题。关键词：一刀切；矩形排料；遗传算法中图分类号：022

2、文献标识码：ASolutiononRectangularStockCuttingof。GuillotineBasedonGeneticAlgorithmXUXin—ai1，LIUYi2，WANGHong—fa3(1．JiangxiInstituteofEducation，JiangxiNanchang330029PRC；2．jiangxiTourism＆CommerceCollege。JiangxiNanchang330100PRC；3·ZhejiangWaterConservancyandHydropowerCollege，ZhejiangHangzhou310018PRC)

3、Abstract：Thisarticleadoptsgeneticalgorithmtosolvetheproblemofguillotinerectangularstockcutting。introducingexploringthinkingtotheprocedureofstockcuttingaswell∞designingthenewcrossoverandmutafioninrespectofthespecificalproblemscorrespondingly．Thisnewgeneticalgo-rithmwillbebetterinthesolutionof

4、theguillotinerectangularcuttingproblem．Keywords：Guillotine，Rectangularstockcutting，Geneticalgorithm0引言许多传统的工业问题，如钢板、圆木、玻璃、卷纸等的切割、服装裁剪、货物装箱等，表面上看不同，然而它们之间存在着紧密的联系。它们均属排料和切割问题，简称排料问题。排料是组合优化问题的一类典型问题，其实质是对定量资源进行合理分配，使剩余量最小。本文讨论了在定宽无限长的矩形材料上(如一捆卷材)，裁剪出若干个大小不同小矩形，在加工工艺上，要求切割的每一刀均从板材的一端沿一直线切到另一端，

5、而不能挖裁，这就是所谓的“一刀切”问题。对于这个问题，目前尚未见成熟的算法，人们只能凭借经验。Gilmore与Gomory【l-3]用线性规划建立了一刀切问题的数学模型，把线性规划的求解转化为一个背包子问题，然后构造求解背包问题的有效方法，用的数学工具主要是线性规划、动态规划与背包函数。黄继进结合动态规划和人工智能启发式搜索的思想，提出带预选搜索步深的二维一刀切矩形优化排料算法H1。本文采用遗传算法对一刀切矩形排料问题进行求解，在排料过程中引入了启发式思想。并针对这个具体问题设计了新的交叉算子和变异算收稿日期：2008一03—24；修订日期：2008—04—08作者简介：徐新爱

6、(1973一)。女，江西丰城人，讲师，主要研究方向：智能计算。万方数据第3期徐新爱等：基于遗传算法的一刀切矩形排料求解子，新的遗传算子更适合求解一刀切矩形排料问题。试验表明该算法的效果理想，有实用价值。1一刀切矩形排料1．1排列方式设小矩形长宽分别为c、d，在模板或切割的余料上的排列方式有2种，即横排和竖排，如图l、图2所示。令dl=rain(dxl，dyl)，d2=min(dx2，dy2)，若dl

7、切下，切割顺序有2种。例如对于图2的排列，切割顺序有图3或图4的2种方式，用哪种切割顺序比较合理?本文的原则是，第1次下刀的刀口以短为好。所以选取图4的切割顺序。1．3启发式排料设rg个小矩形足(i=l，2，⋯，几)，依次将它们布局在模板上。对于R。按照上述的排列方式和切割顺序布局在模板上，得到2块余料，记为肘。和M2；对于R2按照1．1所述的排列方式从余料肘，和JIIf：中选择l块，切割后又得到2块余料(若选择M，，余料记为M，和坞；若选择幔，余料记为肘：和肘，)，这样切割尺。和尺：后得到