【作者】 曾窕俊；

【导师】 崔耀东；

【作者基本信息】 广西师范大学 ， 计算机软件与理论， 2006， 硕士

【摘要】 优化排样问题是指寻求二维图形在特定长度,宽度区域内的摆放尽可能多,以使区域的利用率达到最优。它在服装、皮革制品、体育用品、机械等制造行业中都有应用。国内有成千上万家这样的企业,大部分企业仍处于手工排样下料阶段,下料利用率较低,造成原材料的浪费。因此有效提高原材料的利用率,降低生产成本,是增加企业效益的有效途径之一。二维不规则图形的优化排样问题是一个在许多生产实践中有关键应用的重要问题,也是一个计算机科学和运筹学中的基本问题。在理论上属于NP--完全(困难)问题,因为存在实际形状的复杂性和计算上的复杂性,求解十分困难。目前研究较多的是规则零件(如矩形)的排样问题,对不规则件的研究较少。对不规则件的处理基本上是基于规则零件排样处理的矩形近似方法和对不规则零件直接处理两种方法。本文应用一种名为挤压算法的近优算法。它是一种基于对不规则零件直接处理的方法。使用该算法能提高材料的利用效率,它通过在排样过程中对相邻的两个和两排的图形进行向左,向下的移动,通过减少它们之间的空隙来实现此目的。在排样计算的过程中,如何找到零件之间在什么位置靠接紧密并且不重叠是一个关键的问题。此外,它会利用到一些与图形学相关算法。以下为它的基本步骤:1、通过预处理,将所有的待摆放的多边形分别绕它们的重心旋转一个角度,从而可以得到它们最佳包络矩形。2、计算相邻的两个和两排的图形的最小距离。3、根据这个最小距离,移动它们,从而减少它们之间的空隙。但仅有此算法不能对整个排样问题进行优化处理。因为它要求在实际的摆放前必须得到一个多边形的摆放序列。它必须和某种具有全局搜索能力能提供这种摆放序列的算法相结合运用,才能达到我们所需的效果。遗传算法是一种很好的全局优化算法。它以达尔文的生物进化论为启发而创建,借助选择、交叉、变异等操作逐步逼近最优解。具有隐含并行机制和自适应性。本文对遗传算法的发展现状进行分析。在对基本遗传算法的优缺点进行分析后,主要针对它的局部搜索能力差,全局搜索速度较慢和早熟现象提出改进。主要是针对遗传算法进行遗传算子(选择算子、交叉算子和变异算子)的改进。通过以上分析,将两种算法混合更多还原

【Abstract】 Optimizing nesting generally refers to arranging as many as possible needed geometrical graphic in some plane regions with constrained length and width.,which appears in many industries, such as the industries of rag trade, leather, sports goods, mechanical manufacturing, and so on. There are thousands of enterprises ,which have Optimizing nesting problems in our country, but the majority of them use hand-generated cutting patterns in the nesting process. As a result, the material usage is low and the amount of waste is large. Improving material usage may reduce the costs of production and it is an efficient way to increase the profits of the enterprises. The optimization of two-dimensional irregular graphic layout is a basic problem in computer science and operational research, and has root key applications in many industries. But the current results from traditional methods do not satisfy real applications. In theory, the nesting problem of two-dimensional irregular shapes belongs to the NP-hard problems. It is very difficult to find the optimal solution for such a problem because of the complexity of shapes and computation.Currently, most of the papers published in the area are concerned with the cutting problem of regular shapes (such as rectangular), only few is about the irregular shapes. One method about irregular shapes nesting is approximately rectangle solution method based on regular shapes, the other method is to deal with the irregular shapes directly. This paper presents a new approximation optimal method, named collision algorithm, about the packing space based on the latter method. Using this algorithm, we can improve the efficiency of cutting through colliding left and down in the processing of placement. So it undoubtedly decrease interspaces between two neighbor graphics and two chains of graphics. How to find the positions where shapes are not overlapping and are contacted is one of crucial technologies of optimization problem in the courses. It involves with some graphic algorithms . Following is its更多还原