基于分布估计算法的矩形件排样优化问题研究

《基于分布估计算法的矩形件排样优化问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学校代码：10289分类号：TP311密级：公开学号：132070027江苏科技大学硕士学位论文基于分布估计算法的矩形件排样优化问题研究研究生姓名马康导师姓名高尚申请学位类别工学硕士学位授予单位江苏科技大学学科专业软件工程论文提交日期2015年12月31日研究方向智能计算论文答辩日期2016年03月26日答辩委员会主席李永忠评阅人盲审盲审2016年3月20日分类号：TP311密级：公开学号：132070027工学硕士学位论文基于分布估计算法的矩形件排样优化问题研究学生姓名马康指导教师高尚教授江苏科技

2、大学二〇一六年三月AThesisSubmittedinFulfillmentoftheRequirementsfortheDegreeofMasterofEngineeringResearchofRectangularPackingMethodsBasedonEstimationofDistributionAlgorithmsSubmittedbyMaKangSupervisedbyProfessorGaoShangJiangsuUniversityofScienceandTechnologyMar

3、ch,2016江苏科技大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：年月日摘要摘要本文主要研究矩形件排样优化的问题。矩形件排样优化问题是指一些相同或不同规格的矩形件按照某种策略排布到矩形板材上，使得按照此排样图切割时，产生最少的下料。

4、矩形件排样优化的问题广泛存在于众多生产制造领域中，像机械制造、家具生产、造纸、服装、皮革等。研究矩形件排样优化问题有着极大的现实意义。基于一个好的排样策略生成的排样图，可以提高原材料的利用率，降低企业的生产成本，提高企业的经济效益。矩形件排样优化问题这种组合优化问题在数学上属于NP完全问题。由于其求解的复杂性，在确定的时间内求得最优解很困难。目前，人们通常采用智能优化算法和启发式规则求解矩形件优化排样的问题。例如遗传算法，蚁群算法，粒子群算法，模拟退火算法，BL算法（Bottom-Left），DP算

5、法（DifferenceProcess）等。然而，单纯的智能算法和启发式规则在求解矩形件排样的问题中表现出来的效果有限且算法性能提升困难。本文在研究了国内外众多学者的求解算法之后，提出了一种分布估计算法结合改进的最低水平线算法的混合算法求解矩形件排样问题。分布估计算法是一种新兴的基于概率模型的智能优化算法，它采用了一种全新的进化模式，在很多领域都有着成功的应用。本文详细介绍了分布估计算法的思想和特点，对分布估计算法的应用做了新的尝试，将其应用于求解矩形件排样问题。接着，在对比了BL算法，最低水平线算

6、法和最低水平线搜索算法的基础上提出了一种改进的最低水平线搜索算法。改进之处在于：记录矩形件排样过程中产生的空闲区域，并判断空闲区域之间的位置关系，对于相邻接的空闲区域进行合并。用能够排入空闲区域的矩形件填充空闲区域，实现了空闲区域再利用，提高了板材的利用率。克服了最低水平线搜索算法无法回收利用矩形件排样过程中产生的空闲区域的弊端。分布估计算法和改进的最低水平线搜索算法结合求解矩形件排样问题的过程中，首先，运用分布估计算法求得较优的排样顺序，然后按照改进的最低水平线搜索算法排放矩形件，生成排样图。通过

7、算法在实际应用中的测试结果表明，改进算法有着较好的性能，对提高板材利用率和经济效益有着重要的作用。关键字矩形件；优化排样；下料问题；分布估计算法；启发式算法IAbstractAbstractThispapermainlystudiestheoptimizationofrectangularstrippacking.TheproblemoftheRectangularstrippackingcanbedescribedasputtingtheneededtheRectangularofsameorva

8、rioussizesontheRectangularsheetbasedonthegivenpackingalgorithm,whichaimatminimizingsheet’sunusedareaaftercutting.TheproblemsoftheRectangularpackingoptimizationarewidelyexistedinmanymanufacturingfields,suchasmachinerymanufacturing,furnit