矩形三阶段带排样问题的遗传算法研究

《矩形三阶段带排样问题的遗传算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、广西师范大学硕士研究生学位论文矩形三阶段带排样问题的遗传算法的研究学生：严玄指导老师：崔耀东专业：计算机应用技术研究方向：计算机辅助设计与优化计算技术年级：2006级中文摘要计算机辅助排样（CAN）是计算机辅助技术最具体的应用之一，是计算机技术与现代经济快速发展的必然产物。它广泛存在于机械加工、家电制造、服装裁剪、国防科技等国民经济行业中，解决好这类问题可以节省原材料，简化生产工艺，降低生产成本，增加企业效益。矩形件带排样问题（RSPP）是矩形排样问题中的一个重要分支，它是指给定n个不同的矩形零件集合R1,R2,Ë,Rn，将其全部置于定宽无限高的矩形条带Q上，使得所占据条带的

2、高度最小。RSFP在理论上是属于高计算复杂性的NP完全问题，求解这类问题所需要的计算量随着问题规模的增加呈指数级增长，而不是线性增长。因此，研究RSPP具有重要的实用和理论价值。遗传算法是借鉴生物的自然选择和遗传进化机制而开发出来的一种自适应全局优化概率搜索算法，它模拟生物进化的基本过程，通过对群体施加选择、交叉、变异等遗传算子来仿真生物的基本进化过程，逐步使群体进化到所求得的解包含全局最优解或近似最优解。它对于非常复杂、高度非线性的组合优化问题表现出比传统优化方法更加独特和优越的性能。排样问题是一个多目标规划问题，在考虑材料利用率的同时，还需要考虑到生产工艺的要求。为了适应特殊的

3、领域，排样过程中需要满足特定的生产工艺要求，往往会对得到的排样方式加以限制，生成适合的下料方案。基于上述考虑，本文使用一种基于遗传算法求解RSPP的启发式遗传算法，同时要求得到的排样方式为一个三阶段排样方案。本文的主要工作如下：首先，本文使用一种基于递归方法的启发式解码方式，通过对染色体序列进行解码，得到对应的三阶段排样方式。将分段切割的思想引入到解码过程中。在解码过程中根据毛坯的序列将排样方案划分为层，将层划分为堆，层和堆上毛坯的排放遵循贪婪的原则，若当前堆上方不可以继续排放任何毛坯时则产生一个新堆，当前层上不能再产生新堆时划分一个新的层，依循这样的排放规则直到所有的毛坯排放完成

4、。这样所得到的排样方式为一个可剪切下料的方式，即可沿层的方向先把矩形条带切割成比较小的段，然后沿堆的方向再将层切割成若干个小堆，最后将堆切割成所需要的毛坯。其次，依据特定的分层思想，设计交叉算子和变异算子。在进行交叉操作时，交叉的对象设计成以层为单位进行，在对染色体解码以后，通过比较各层的废料率，将废料率较小的层遗传到子代，这样既保留了父代染色体的优良基因片段，又提高了交叉的效率；同样的，变异操作也以层为单位进行，先找出当前个体所对应的排样方式中那些排放不合理I广西师范大学硕士研究生学位论文的毛坯，先从当前位置删除，将其放在基因队列的最后，然后选择部分待变异的层并拆分这些层，最后将

5、这些毛坯依次插入到未被拆分的层上的合适位置。经过交叉和变异操作后，引入一个新的操作——调整操作，该操作在不改变带的利用率的条件下，用来调整层和堆的相对位置，简化得到的排样方案。然后，规划和设计了排样系统的基本功能模块，开发了一个基于遗传算法的矩形带排样系统。通过大量实验测试，并将实验结果与同类算法的实验结果进行比较和分析，验证了该系统的算法的有效性。最后，论文对己完成的工作进行了总结，指出进一步的研究工作。关键词：矩形带排样，遗传算法，三阶段，切割下料，优化II广西师范大学硕士研究生学位论文Researchonthethree-stagerectanglestrippackingp

6、roblem’sgeneticalgorithmStudent:YanXuanTutor:CuiYaodongMajor:ComputerApplicationandTechniqueResearchArea:OptimizationandComputationTechnology;ComputeraddeddesignGrade:2006AbstractCANisonespecialapplicationincomputerassistanttechnologies.Itistheresultofcomputertechnologiesandeconomy’sdevelopm

7、ent.Itwidelyexistsincountryeconomicindustrysuchasmachiningprocess,electricalfurnitureproducing,costumeindustriesandthescienceofnationaldefenseandsoon.Solvingtheseproblemscansaverawmaterials,streamlineproductionprocesses,reduceproduction