二维不规则零件排样问题优化研究

发布时间：2018-03-24 21:36

本文选题：不规则零件　切入点：三角组矩法　出处：《吉林大学》2012年硕士论文

【摘要】：二维不规则零件排样问题，是NP类问题中非常重要的一类，这类问题很难进行求解。然而，由于该问题理论意义和实际意义的重要性，使得该问题成为了最优化问题中一个极其重要的分支。到目前为止，对于这类问题的求解主要基于两种思路：一种是对这类零件直接在原材料上进行排放；另一种则是将不规则零件转化为规则矩形件，然后按照矩形件进行排样优化。本文采用第二种方法，所做的具体工作如下：由于本文的主要研究对象是二维不规则零件，因此，首先要将二维不规则零件转化为规则零件（即矩形零件）。本文在采用矩形包络法的基础上，提出了另外两种将其规则化的方法：“三角组矩法”和“梯形组矩法”。“三角组矩法”的主要思想是将两个或多个相同的三角形零件组合成平行四边形，然后再进一步转化为矩形；而“梯形组矩法”的研究对象则比较宽泛，四边形、五边形及多边形都可以；这种方法是先将这些不规则零件转化为包络这些不规则零件的最小梯形，然后将两个或多个相同的梯形进行平行排列，最终同样转化为矩形进行排列。这样使得所有的零件都可以按照矩形的排样方式进行排放，极大的缩短了排放的时间，提高了排样的效率。在将不规则零件规则化后，本文对矩形件进行排样的各种排样算法进行了分析和研究，这些算法主要包括：BL算法、基于最低水平线的搜索算法和剩余矩形匹配算法等；对这些算法进行综合比较后，本文选择了剩余矩形匹配算法来对规则化后的矩形件进行排样。由于以上各种排样算法都是定序列的排样算法，很难直接得到最优或满意的排样效果图；因此该算法必须和某种具备全局搜索能力的算法结合起来使用，才能达到我们想要得到的结果。遗传算法以达尔文的生物进化论为基础而创建，通过选择、交叉和变异等操作来逼近最优解。本文采用轮盘赌策略来进行选择，通过双点交叉算子来进行交叉操作，，并应用交换变异、旋转变异和位置变异三种变异算子来进行变异操作，最后得到问题的最优解或满意解，并通过例子来验证可行性。
[Abstract]:The two-dimensional irregular nesting problem is a very important problem in NP, this kind of problem is difficult to solve. However, because of the importance of theoretical and practical significance, the problem has become an extremely important branch of optimization problems. So far, for solving this problem mainly based on two ways: one is on this kind of parts directly discharged in raw materials; the other is the irregular parts into the regular rectangular layout optimization, then in accordance with the rectangular parts. This paper adopts second kinds of methods, the specific work done as follows:
As the main research object is the two-dimensional irregular parts, therefore, first of all to the two-dimensional irregular parts into regular shapes (i.e. rectangular parts). Based on the rectangular envelope method, puts forward the two methods to the rule: "triangle moment method" and "ladder group moment the" method ". The main idea of triangle group moment method" is to combine two or more identical triangular parts combined into a parallelogram, and then further into the rectangle; and "the object of study group trapezoidal moment method" is broad, quadrilateral, Pentagon and polygon; this method is the first these irregular parts into the smallest trapezoidal envelope of these irregular parts, then two or more identical trapezium is arranged in parallel, also eventually transformed into rectangular arrangement. This makes all parts in The discharge of rectangle pattern is greatly shortened, and the efficiency of layout is improved.
In the irregular parts of the rules, the rectangular various layout layout algorithm is analyzed and studied, these algorithms include: BL algorithm, the lowest horizontal line search algorithm and matching algorithm based on rectangle; comparison of these algorithms, this paper chooses the rectangle matching algorithm to the layout of rectangle rule after.
The above algorithm of layout of all kinds of algorithms are set sequence, map layout is difficult to directly get the optimal or satisfactory; therefore the algorithm must have a global search ability of the algorithm used in combination, in order to achieve our desired results. Genetic algorithm with Darwin's theory of evolution is created based on the selection, crossover and mutation to approximate the optimal solution. In this paper, using the roulette strategy to choose, to cross through the double point crossover operator, and the application of exchange variation, rotation variation and position variation of the three mutation operators for mutation operation, finally get the optimal solution or satisfactory solution, and verify the feasibility by examples.

【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TH162

【参考文献】