本文選題：不規(guī)則零件　切入點(diǎn)：三角組矩法　出處：《吉林大學(xué)》2012年碩士論文

【摘要】：二維不規(guī)則零件排樣問(wèn)題，是NP類(lèi)問(wèn)題中非常重要的一類(lèi)，這類(lèi)問(wèn)題很難進(jìn)行求解。然而，由于該問(wèn)題理論意義和實(shí)際意義的重要性，使得該問(wèn)題成為了最優(yōu)化問(wèn)題中一個(gè)極其重要的分支。到目前為止，對(duì)于這類(lèi)問(wèn)題的求解主要基于兩種思路：一種是對(duì)這類(lèi)零件直接在原材料上進(jìn)行排放；另一種則是將不規(guī)則零件轉(zhuǎn)化為規(guī)則矩形件，然后按照矩形件進(jìn)行排樣優(yōu)化。本文采用第二種方法，所做的具體工作如下： 由于本文的主要研究對(duì)象是二維不規(guī)則零件，因此，首先要將二維不規(guī)則零件轉(zhuǎn)化為規(guī)則零件（即矩形零件）。本文在采用矩形包絡(luò)法的基礎(chǔ)上，提出了另外兩種將其規(guī)則化的方法：“三角組矩法”和“梯形組矩法”�！叭墙M矩法”的主要思想是將兩個(gè)或多個(gè)相同的三角形零件組合成平行四邊形，然后再進(jìn)一步轉(zhuǎn)化為矩形；而“梯形組矩法”的研究對(duì)象則比較寬泛，四邊形、五邊形及多邊形都可以；這種方法是先將這些不規(guī)則零件轉(zhuǎn)化為包絡(luò)這些不規(guī)則零件的最小梯形，然后將兩個(gè)或多個(gè)相同的梯形進(jìn)行平行排列，最終同樣轉(zhuǎn)化為矩形進(jìn)行排列。這樣使得所有的零件都可以按照矩形的排樣方式進(jìn)行排放，極大的縮短了排放的時(shí)間，提高了排樣的效率。 在將不規(guī)則零件規(guī)則化后，本文對(duì)矩形件進(jìn)行排樣的各種排樣算法進(jìn)行了分析和研究，這些算法主要包括：BL算法、基于最低水平線(xiàn)的搜索算法和剩余矩形匹配算法等；對(duì)這些算法進(jìn)行綜合比較后，本文選擇了剩余矩形匹配算法來(lái)對(duì)規(guī)則化后的矩形件進(jìn)行排樣。 由于以上各種排樣算法都是定序列的排樣算法，很難直接得到最優(yōu)或滿(mǎn)意的排樣效果圖；因此該算法必須和某種具備全局搜索能力的算法結(jié)合起來(lái)使用，才能達(dá)到我們想要得到的結(jié)果。遺傳算法以達(dá)爾文的生物進(jìn)化論為基礎(chǔ)而創(chuàng)建，通過(guò)選擇、交叉和變異等操作來(lái)逼近最優(yōu)解。本文采用輪盤(pán)賭策略來(lái)進(jìn)行選擇，通過(guò)雙點(diǎn)交叉算子來(lái)進(jìn)行交叉操作，，并應(yīng)用交換變異、旋轉(zhuǎn)變異和位置變異三種變異算子來(lái)進(jìn)行變異操作，最后得到問(wèn)題的最優(yōu)解或滿(mǎn)意解，并通過(guò)例子來(lái)驗(yàn)證可行性。
[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.

【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2012
【分類(lèi)號(hào)】：TH162

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 王少純;王仲仁;康達(dá)昌;錢(qián)衛(wèi);許瑞林;董力臣;;交互式微機(jī)輔助沖件排樣法[J];鍛壓技術(shù);1990年05期

2 夏萼輝;卡銘甲;李紹成;;單雙排沖裁件的最佳排樣法——計(jì)算機(jī)輔助設(shè)計(jì)[J];鍛壓機(jī)械;1984年02期

3 曹炬,胡修彪;大規(guī)模矩形件優(yōu)化排樣的遺傳算法[J];鍛壓機(jī)械;1999年04期

4 戴曉明,鄒潤(rùn)民,馮瑞,張洪源,邵惠鶴;混合并行遺傳算法求解TSP問(wèn)題[J];電子與信息學(xué)報(bào);2002年10期

5 龔志輝,黃星梅;二維矩形件優(yōu)化排樣算法的改進(jìn)研究[J];湖南大學(xué)學(xué)報(bào)(自然科學(xué)版);2003年S1期

6 黃繼進(jìn);帶預(yù)選搜索步深的二維一刀切矩形優(yōu)化排料[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);1994年04期

7 曹炬，周濟(jì);矩形件排樣優(yōu)化的一種近似算法[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);1995年03期

8 劉弘,曾廣周,林宗楷;具有類(lèi)比學(xué)習(xí)機(jī)制的優(yōu)化排料系統(tǒng)[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);1997年05期

9 龔邦明;周汝忠;;計(jì)算機(jī)優(yōu)化排樣[J];機(jī)械工業(yè)自動(dòng)化;1989年02期

10 李建勇,鄂明成,曹月東;利用混沌人工神經(jīng)元網(wǎng)絡(luò)進(jìn)行布局優(yōu)化計(jì)算[J];制造業(yè)自動(dòng)化;2000年01期

相關(guān)博士學(xué)位論文 前1條

1 賈志欣;面向發(fā)電設(shè)備制造的下料優(yōu)化排樣原理與關(guān)鍵技術(shù)[D];四川大學(xué);2002年

相關(guān)碩士學(xué)位論文 前6條

1 宋開(kāi)勝;基于遺傳算法的二維排樣研究[D];哈爾濱工程大學(xué);2010年

2 楊威;板材排樣優(yōu)化的計(jì)算智能方法研究[D];四川大學(xué);2002年

3 黃紅兵;矩形件下料優(yōu)化排樣的遺傳算法[D];廣西師范大學(xué);2005年

4 張克;二維矩形件優(yōu)化排樣問(wèn)題研究[D];山東大學(xué);2006年

5 趙曉東;矩形件優(yōu)化排樣算法的研究與實(shí)現(xiàn)[D];大連交通大學(xué);2008年

6 李青;二維不規(guī)則零件排樣問(wèn)題的研究[D];合肥工業(yè)大學(xué);2009年

本文編號(hào)：1660149