基于UG二次開發(fā)技術(shù)的計算機輔助夾具定位系統(tǒng)的研究和開發(fā)

1、二維零件排樣算法的研究李凌輝，謝友寶，蔡洪偉，吳娟（南昌航空大學，江西南昌，330063）摘 要：本文首先用數(shù)據(jù)庫保存待排零件的數(shù)據(jù)信息，然后提取零件的最小包絡矩形并編碼，再使用最低水平線法將零件排樣轉(zhuǎn)化成矩形件的正交排樣圖，最后結(jié)合遺傳算法實現(xiàn)二維零件排樣，此算法具有自動化程度高，優(yōu)化性能好，快速高效等特點。關(guān)鍵詞：二維排樣，最低水平線法，最小包絡矩形，編碼，遺傳算法The reaserch on algorithm of two-dimensional parts layoutLi Linghui,Xie Youbao, Cai Hongwei ,Wu Juan(Nangchang Han

2、gkong University, Nanchang, 330063)Abstract:This article first uses the database to preserve the data infromation of the nesting parts, then extracts the minimum enclosure rectangle and codes, and applies the Lowest Horizontal Line algorithm to transform parts layout into the rectangular orthogonal

3、parts blank layout graphics ,finally unifies the genetic algorithm to realize two-dimensional parts layout, this algorithm has high automation, good optimized performance , fast and efficient and so on .Keywords: two-dimensional layout，the Lowest Horizontal Line algorithm，the minimum enclosure recta

4、ngle，code，the genetic algorithm1引言企業(yè)的生產(chǎn)效率，產(chǎn)品的質(zhì)量與成本，是一個企業(yè)生存和發(fā)展的關(guān)鍵，因此材料成本在工業(yè)生產(chǎn)中顯得尤其重要。板類零件性能優(yōu)越，制造工藝簡單，成本低廉，被廣泛應用于汽車,飛機,造船,電器等行業(yè)中，而板類零件都存在一個共同的排樣問題，能否研究出一套優(yōu)化的排樣方案，對于降低材料浪費，提高企業(yè)的經(jīng)濟效率有著重要的理論意義和現(xiàn)實意義。 二維排樣在排樣問題中應用最廣泛，航空企業(yè)中飛機的幾千個薄板零件需要下料，造船業(yè)中鈑金件的裁切，服裝業(yè)中布料的裁剪均屬于此類問題。有關(guān)零件排樣算法，目前已經(jīng)有很多較好的方案，如模擬退火算法，矩形包絡算法，啟發(fā)算法,

5、神經(jīng)網(wǎng)絡算法等，但是每種方法都有自己的優(yōu)點和不足之處，其排樣技術(shù)還是不夠成熟。筆者綜合了幾種零件排樣算法的思想，提出了另外一種排樣算法可以較好的解決此問題。2排樣問題介紹二維零件的排樣問題是指將一系列形狀各異的零件在矩形板材中按最優(yōu)方式進行排布, 使其板材的利用率最高。排樣問題可以從兩個方面加以說明，一是排樣零件的調(diào)度，即從零件庫中選出零件,為零件排樣做準備；另一個是如何確定零件的最佳排放位置, 編寫相關(guān)算法并檢測算法優(yōu)化性能。3二維零件排樣方法3.1零件圖形數(shù)據(jù)的提取和保存排料過程中，通過與AutoCAD的接口提取各零件實體的數(shù)據(jù)信息，它以DXF文件格式記錄，零件實體中具體的數(shù)據(jù)信息包括直線

6、（LINE），圓（CIRCRE），圓?。ˋRC），樣條（SPLINE）等。獲得零件實體的信息之后，找出實體間的拓撲關(guān)系，對零件實體段點進行排序處理，使其成為一個封閉的輪廓，滿足零件表達的要求。得到零件的圖形數(shù)據(jù)以后，根據(jù)零件的不同規(guī)格分類編號，放入數(shù)據(jù)庫中保存，數(shù)據(jù)庫保存零件數(shù)據(jù)應遵循以下原則：（1）科學全面性：盡量多的反應零件主要特征，如：長度，寬度，弧度，面積，凹凸性等；（2）代碼唯一性：同一類型零件應該具備相同的編碼，不同類型的零件編碼不同；（3）易擴展性：為以后新加入的零件類型提供友好的數(shù)據(jù)庫接口程序。3.2零件預處理排樣的零件對于任意形狀規(guī)則,按類型可分為凸多邊形、凹多邊形或為兩者的

7、混合體。分別求出它們的最小包絡矩形面積（零件的最小包絡矩形是指外切零件的矩形中面積最小的那一個）。對凹多邊形,可能存在較大的空白區(qū)域,可采用人機交互的方法用小零件（由小到大的順序）盡量添滿空白區(qū)域。現(xiàn)在對零件的排樣問題轉(zhuǎn)變成了零件矩形件在板材上的排樣問題了。3.3排樣零件數(shù)學模型在寬度確定，高度(或長度)不限的板材上排放給定的矩形件。設板材寬度為W,待排零件種類數(shù)為N，第i個零件的長度為，寬度為，數(shù)量為,，零件沿板材寬度方向進行排放，零件排樣后在板材上所達到的最大高度為H,則優(yōu)化排樣的目標函數(shù)為: 當排樣零件較多時，計算量將變得很大，計算時間也將變長。為了加速搜索，減少計算量，本文采用一些約束

8、條件來簡化尋優(yōu)過程：（1）同種零件盡量排布在一起;（2）零件沿板材寬度方向排放，可以水平排放，也可以旋轉(zhuǎn)90度之后再排放;（3）零件相互靠近，但不能相互重疊，也不能超出板材邊界之外;（4）零件矩形件排樣方式遵行最底水平線法和遺傳算法規(guī)則的要求。設在坐標系統(tǒng)上，板材最左下角的坐標為(0，0)。矩形件i排放在板材上，其左下角和右上角坐標分別以，表示，則有：當矩形件橫排時： 當矩形件豎排時：設任意兩個排樣的矩形件a和b的左下角和右上角的坐標分別為：，和,則滿足下面任意一個條件，矩形件不會相互重疊：(1)； (2)； (3)； (4) ；對于任意的矩形件i，為了不超出板材之外，必須滿足下列條件:(1)

9、 (2)； (3)；3.4排樣解碼方法遺傳算法是一種把問題的可行解作為種群,把每一個可能的解看作種群的個體,算法運行時在整個解空間內(nèi)隨機搜索,按一定的評估策略對每一個個體作出評價,不斷地使用選擇、交叉、變異這三種遺傳算子,直至產(chǎn)生最優(yōu)解。（1）確定編碼方法用遺傳算法求解問題，必須先確定編碼方法。不同的編碼方法,遺傳算子實現(xiàn)的方式也不同。本文采用了十進制編碼方式,將每一矩形進行編號（i=1,2,n），零件編號構(gòu)成一個整數(shù)串，1n,表示了一種排樣圖的一個解。其中,每一位整數(shù)代表一個矩形,并且每一位整數(shù)可以有正負之分,正號表示零件不發(fā)生旋轉(zhuǎn),負號表示將零件旋轉(zhuǎn)90度。這樣一個整數(shù)串就是一個個體,每一

10、個體對應一種排樣圖，m個個體構(gòu)成一個群體。（2）算法的選擇基于“最左最下”原則的BL算法如下：第一步：將放在板材的左下角,若為負值,則將其旋轉(zhuǎn)90后再排放,求出排放后所占板材的最大高度；第二步：將 (i=2,3,n)置于板材右邊最大高度處,交替向下向左移動.。首先盡可能地向下移動,然后再盡可能地向左移動,直至無法再向下向左移動為止(即接觸到其它零件或板材邊界),并求出此時的最大高度;重復上述過程,直至所有零件排放完畢,最后所得的最大高度即為所需板材的高度。現(xiàn)使用“下臺階”算法對第二步進行了改進。在向下向左移動時,采用了向下優(yōu)先的原則,克服了BL算法對某些最優(yōu)排樣圖排列的缺點。對于編碼1,-2,

11、3,-4, BL算法與“下臺階”算法的排放過程分別如圖1和2所示： 1234 圖（1）“BL”算法 1234圖（2）“下臺階”算法分析BL算法和“下臺階”算法可以發(fā)現(xiàn),BL算法并非最優(yōu)排樣,容易發(fā)生板材左側(cè)排放偏高的情況，而“下臺階”算法則易發(fā)生右側(cè)偏高的情況。本文提出一種基于零件最高輪廓線的解碼算法最底水平線算法,具體過程如下：第一步：設置初始最高輪廓線為板材的最下面的邊；第二步：每當要排入一個零件時,就在最高輪廓線集中選取最低的一段水平線,如有數(shù)段,則選取最左邊的一段,測試該段線的寬度是否大于或等于要排入零件的寬度。如果該段線的寬度大于要排入零件的寬度,則將該零件在此位置排放,更新零件最高

12、廓線;否則,查詢與最低水平線段相鄰的左、右兩段水平線,將最低水平線提升至與高度較低的一段平齊,更新零件最高輪廓線。重復第二步,直至能排入該零件。重復上述過程,直至所有零件排放完畢。對于編碼1,-2,3,-4,采用最底水平線法方法的排樣過程如圖3所示。在排放1,2矩形后,最右端排放矩形3，如果最低水平線的寬度小于矩形3的寬度,則提升該與相鄰的左段水平線平齊,這時最低水平線變成了靠左邊一段,將矩形3排放,照此方法放入矩形4。121321（a） （b） （c）144444444411234432121（d） （e） （f）圖（3）“最底水平線法”排放零件3.5適應度函數(shù)遺傳算法中利用適應度函數(shù)評價解

13、的好壞,適應度函數(shù)值越優(yōu),解的質(zhì)量就越高，對排樣問題,取排樣圖的最大高度的倒數(shù)為適應度函數(shù)值。若兩個排樣圖具有相同的高度,適應度值仍有好壞之分。從余料再利用的角度看,本文采用如下的適應度函數(shù)；f(P)=B/B1,其中B是排入矩形件的面積,B1是排樣圖整體高度輪廓線以下的板材面積。4遺傳算法求解過程4.1初始種群給定n個零件,隨機產(chǎn)生由m個編碼構(gòu)成的初始種群,用“最低水平線法”計算每一個體的適應度。4.2遺傳算子(1)交叉算子將父輩群體中的個體隨機兩兩配對,進行交叉操作,產(chǎn)生m個個體構(gòu)成子輩群體。本文采用了兩種交叉算子:單點交叉和雙點交叉。設兩個進行交叉的個體為和。單點交叉是在1n范圍內(nèi)隨機生成

14、一個交叉位b1,從P中將位于b1之前的元素拷貝至子輩個體new Individual1中作為前面的元素,剩余元素按Q中出現(xiàn)的先后順序拷貝至new Individual1;同樣的方法可以產(chǎn)生另一新個體new Individual2。雙點交叉是在1n范圍內(nèi)隨機生成兩個交叉位b1,b2,從P中將位于b1,b2之間的元素拷貝至子輩個體new Individual1中作為前面的元素,剩余元素按Q中出現(xiàn)的先后順序拷貝至new Individual1,從而得到新個體new Individual1;同樣的方法可以產(chǎn)生另一新個體new Individual2.(2)變異算子對進行了交叉操作的子輩個體,采用兩種變

15、異算子進行變異。第一種是旋轉(zhuǎn)變異,隨機產(chǎn)生一個旋轉(zhuǎn)位bit,以概率對子輩個體中位于bit之后的矩形進行旋轉(zhuǎn);第二種是位置變異,以較小的概率,在1n范圍內(nèi)隨機產(chǎn)生兩個整數(shù)bit1,bit2,對子輩的個體中的位于bit1,bit2的兩個零件對調(diào)。(3)選擇算子用“最低水平線法”求變異后的m個子輩個體的適應度。將父輩個體與子輩個體的適應度函數(shù)值由大到小排序,取排在前面的m個個體作為下一代的父輩個體。5結(jié)束語算法的優(yōu)化性是相對的，本文的算法還可以繼續(xù)研究下去，在使用最底水平線法和遺傳算法排放完矩形件后，矩形件或板料中還有很多小空白域區(qū)，我們可以根據(jù)經(jīng)驗采用人機交互方式在這些小空域區(qū)中合理放置更多更小的

16、零件，也可以根據(jù)這些小空域區(qū)和零件的特征屬性，再尋找一種優(yōu)化的小零件排樣算法。參考文獻1 Liu Jiamin,Zhang Shengnan.Research and imlementation of two dimensional irregular of Computer Aided Design And Computer Graphics,2000,12(7): 488491(in Chinese).2劉聰,吳兵銳.淺談AutoCAD的接口DXF文件J.山東煤炭科技.2002(1)：38-39.3Jia Zhi xin,Yin Guofu,Luo Yang,etal application of smiulated annealing to the rectangular packing