《矩形三阶段带排样问题的遗传算法研究》由会员分享，可在线阅读，更多相关《矩形三阶段带排样问题的遗传算法研究（39页珍藏版）》请在金锄头文库上搜索。
1、.广西师范大学硕士研究生学位论文矩形三阶段带排样问题的遗传算法的研究39 / 39.学生：严玄指导崔耀东.专业：计算机应用技术研究方向：计算机辅助设计与优化计算技术年级：2006 级.中文摘要计算机辅助排样CAN是计算机辅助技术最具体的应用之一,是计算机技术与现代经济快速发展的必然产物。它广泛存在于机械加工、家电制造、服装裁剪、国防科技等国民经济行业中,解决好这类问题可以节省原材料,简化生产工艺,降低生产成本,增加企业效益。矩形件带排样问题RSPP是矩形排样问题中的一个重要分支,它是指给定 n 个不同的矩形零件集合 R1 , R2 , , Rn ,将其全部置于定宽无限高的矩形条带 Q 上,使得
2、所占据条带的高度最小。RSFP 在理论上是属于高计算复杂性的 NP 完全问题,求解这类问题所需要的计算量随着问题规模的增加呈指数级增长,而不是线性增长。因此,研究 RSPP具有重要的实用和理论价值。遗传算法是借鉴生物的自然选择和遗传进化机制而开发出来的一种自适应全局优化概率搜索算法,它模拟生物进化的基本过程,通过对群体施加选择、交叉、变异等遗传算子来仿真生物的基本进化过程,逐步使群体进化到所求得的解包含全局最优解或近似最优解。它对于非常复杂、高度非线性的组合优化问题表现出比传统优化方法更加独特和优越的性能。排样问题是一个多目标规划问题,在考虑材料利用率的同时,还需要考虑到生产工艺的要求。为了适
3、应特殊的领域,排样过程中需要满足特定的生产工艺要求,往往会对得到的排样方式加以限制,生成适合的下料方案。基于上述考虑,本文使用一种基于遗传算法求解 RSPP 的启发式遗传算法,同时要求得到的排样方式为一个三阶段排样方案。本文的主要工作如下：首先,本文使用一种基于递归方法的启发式解码方式,通过对染色体序列进行解码,得到对应的三阶段排样方式。将分段切割的思想引入到解码过程中。在解码过程中根据毛坯的序列将排样方案划分为层,将层划分为堆,层和堆上毛坯的排放遵循贪婪的原则,若当前堆上方不可以继续排放任何毛坯时则产生一个新堆,当前层上不能再产生新堆时划分一个新的层,依循这样的排放规则直到所有的毛坯排放完成
4、。这样所得到的排样方式为一个可剪切下料的方式,即可沿层的方向先把矩形条带切割成比较小的段,然后沿堆的方向再将层切割成若干个小堆,最后将堆切割成所需要的毛坯。其次,依据特定的分层思想,设计交叉算子和变异算子。在进行交叉操作时,交叉的对象设计成以层为单位进行,在对染色体解码以后,通过比较各层的废料率,将废料率较小的层遗传到子代,这样既保留了父代染色体的优良基因片段,又提高了交叉的效率；同样的,变异操作也以层为单位进行,先找出当前个体所对应的排样方式中那些排放不合理I.广西师范大学硕士研究生学位论文的毛坯,先从当前位置删除,将其放在基因队列的最后,然后选择部分待变异的层并拆分这些层,最后将这些毛坯依
5、次插入到未被拆分的层上的合适位置。经过交叉和变异操作后,引入一个新的操作调整操作,该操作在不改变带的利用率的条件下,用来调整层和堆的相对位置,简化得到的排样方案。然后,规划和设计了排样系统的基本功能模块,开发了一个基于遗传算法的矩形带排样系统。通过大量实验测试,并将实验结果与同类算法的实验结果进行比较和分析,验证了该系统的算法的有效性。最后,论文对己完成的工作进行了总结,指出进一步的研究工作。关键词：矩形带排样,遗传算法,三阶段,切割下料,优化II.广西师范大学硕士研究生学位论文Research on the three-stage rectangle strip packing proble
6、msgenetic algorithm.Student: Yan XuanTutor: Cui YaodongMajor: Computer Application and Technique.Research Area: Optimization and Computation Technology; Computer added designGrade: 2006AbstractCAN is one special application in computer assistant technologies. It is the result ofcomputer technologies
7、 and economys development. It widely exists in country economicindustry such as machining process, electrical furniture producing, costume industries and thescience of national defense and so on. Solving these problems can save raw materials, streamlineproduction processes, reduce production cost an
8、d increase the efficiency of industry. Therectangle strip packing problem is an importance branch of rectangle packing problem. Itcan be stated as putting some quantified rectangles R1 , R2 , , Rn on the given sheet, which isfixed with width and isnt fixed with height, with an aim to minimizing shee
9、ts unused area. Butit is a high computational complexity NP-complete problem in theory. So when the scale of theproblem is large, we can not use exact algorithm to acquire the optimal solution. Therefore, thestudy on RSPP has important practical and theoretical value.The genetic algorithm is a proba
10、bility of global search optimization algorithm based onbiologys natural selection and the mechanism of genetic anagenesis. It simulates biologyanagenesis basal progress, uses the Digital gene string to analyse the chromosome, and imitatesthe basal biology evolution progress through selection, crosso
11、ver, mutation and so forth geneticoperation. The problem solution represented by the most excellent chromosome is the ultimatelyoptimization solution or close to the optimization solution. Genetic algorithm has special andoutstanding performance in very complex and high nonlinear grouping optimize p
12、roblems.Packing problems is about multiple objectives programming problems. When consider thematerials using rate, we should need to take care to the demands of producing technologies atthe same time. When applying in special area and satisfy the specific needs, we should meet theproducing technolog
13、ys need in the packing process, and give limits to the packing way andmake sure the stuffs-arranging manners. Based on the above considerations, in this paper, wepropose a heuristic genetic algorithm which is about solving RSPP based on the geneticalgorithm. At the same time, the packing pattern sho
14、uld be the three-stage packing pattern. Thepapers main work and the novelty of this research are as follows:First, the paper uses a heuristic decode manner which is based on recursion. ThroughIII.广西师范大学硕士研究生学位论文decoding the chromosome sequence, we get the responding three-stage patterns. We use theg
15、rading cutting idea in the decode process. In decode process we divide the patterns into layersby the rough sequence, and then divide the layer into stacks. How to place the roughs on layersand stacks is decided by the Greedy ruler. If the current stack cant stand one more rough, make anew stack. If the current layer cant stand one more stack, make a new layer too. Following thisruler we place all the roughs. So the packing manner we get can be a feasible cutting stockmanner. In this way, the edge can divide the rectangle strips into small segments along the layer
