用於矩形件的智能排樣方法
2023-05-04 04:43:16
用於矩形件的智能排樣方法
【專利摘要】本發明公開了一種用於矩形件的智能排樣方法,包括下列步驟:S1:初始化遺傳算法的相關參數;S2:從待排樣矩形件庫中提取矩形件的相關信息;S3:從板材庫中提取原料板的相關信息;S4:對所獲得信息進行編碼,並隨機生成初始種群;S5:利用最低水平線搜索算法對上述初始種群進行逐一解碼,以獲得解的利用率;S6:遺傳算法選擇、交叉、變異操作,直到迭代結束,並輸出最優排樣方案。按照本發明的智能排樣方法,可以很好地滿足矩形件的工藝要求,並且採用了智能算法和啟發式算法相結合,能快速高效尋找到一種優化方案,由此大大提高了企業的材料利用率且能顯著縮短排樣時間,提高排樣效率。
【專利說明】用於矩形件的智能排樣方法
【技術領域】
[0001]本發明屬於加工件排樣領域,尤其涉及一種用於矩形件的智能排樣方法。
【背景技術】
[0002]排樣問題是一個在金屬製造業、造紙業、玻璃製造、家具製造業、汽車製造業等製造領域生產實踐中普遍遇到的問題,有效的排樣方法可以使企業按照最優的方式對所需求的零件進行切割,從而可以極大地提高原材料的利用率以及切割效率,進而提升企業的經濟效益。
[0003]傳統的排樣方式多採用人工排樣下料,由操作工人按照零件尺寸和數量在原料板上簡單排列切割下料。這種傳統的手工排樣下料生產方式容易造成大量邊角餘料,且企業不能做到排樣預算。
[0004]對於矩形件的排樣優化而言,現有的優化排樣方法往往沒有考慮矩形件的特殊工藝、具有纖維方向、「一刀切」(所謂一刀切,就是指矩形件的下料設備如鋸床和剪床機等在加工時只能沿著某一方向進行切割,直至此次切割完成),因此不能適用於矩形件「一刀切」的排樣優化。採用人工對矩形件進行排樣,效率低下且排樣效果不理想,因此如何根據矩形的特定工藝要求及其自身的特性,來定製符合矩形件的加工要求,能夠更有效的利用原材料、大幅度降低生產成本並且效率更高的排樣方法,已經成為業內迫切的技術要求。
[0005]因此,亟需研發出解決上述問題的有效措施。
【發明內容】
[0006]為解決上述技術問題,本發明的目的在於提供一種能夠更有效地利用原材料、排樣結果符合的用於矩形件的智能排樣方法。
[0007]本發明提供了一種用於矩形件的智能排樣方法,包括下列步驟:
[0008]S1:設定遺傳算法中包括種群population、迭代次數T、交叉概率Pc以及變異概率Pm在內的參數;
[0009]S2:從矩形零件庫選擇待排樣的矩形件,並提取包括矩形種類K、各種類矩形的數量叫、各種類矩形的尺寸即纖維方向的長Ii和非纖維向的寬Wi,以及矩形排樣時是否存在纖維方向要求在內的矩形相關信息,並對每一個矩形進行十進位整數編碼,由此形成一個矩形序列;
[0010]S3:從原料庫選擇符合上述矩形件排樣要求的矩形板材,並提取包括板材序號、數量、各序號板材的尺寸即纖維方向的長和非纖維方向的寬在內的板材相關信息;
[0011]S4:根據上述矩形件信息隨機生成遺傳算法的初始種群population,其中每個染色體(染色體為矩形件排樣的一個序列也即矩形排樣的一個解)就是矩形件的一個排樣序列,矩形件的排樣序列就是根據矩形個數編碼號構成的不重複的隨機序列。
[0012]S5:利用最低水平線搜索算法對所獲得初始種群進行解碼,其中對每條染色體的解碼具體步驟如下:[0013]S201:設置初始最高輪廓線為板材底邊;
[0014]S202:每當要排入一個矩形Ri,就在最高輪廓線集中選取最低的一段水平線,如果有數段,則選擇最左邊的一段,測試該段最低水平線的寬度是否大於等於要排矩形的寬度;
[0015]①如果該最低水平線的寬度大於等於要排矩形Ri的寬度,並且排入高度不超出原料板的邊界,則將該矩形排在此位置,同時更新最高輪廓線集。否則,從矩形Ri所在的位置開始向後搜索可以放進最低水平線的矩形,即從{Ri+1...Rj...RJ中搜索比較與最低水平線寬度最吻合的矩形排入;如果矩形&的寬度與最低水平線最相近且不超出原料板高度,則將矩形Rj排入,同時交換矩形Ri與Rj的位置,{R1; R2,...Rj,...Ri,...RJ ,更新最高輪廓線集;
[0016]②否則,從該矩形所在的位置開始向後搜索可以放進最低水平線且不超出原料板高度的矩形,比較與最低水平線寬度最吻合矩形件排入,並交換這兩個矩形的位置,同時更新最聞輪廊線集;
[0017]③如果沒有可以排進最低水平線的矩形,則將最低水平線提高至與高度較低的一段齊平,更新最高輪廓線集。當抬高最低水平線不能排進任何矩形時,重新加一塊原料板;
[0018]S203:重複步驟S202,直到排下該矩形件;
[0019]S204:重複S202、S203直到所有矩形件排放完成;
[0020]S6:利用上述步驟S5獲得的解碼結果生成排樣方案圖,並可以計算得到每個解對應的排樣利用率,並保留最大利用率gbest (全局最優解即全局最大利用率)以及對應的染色體序列;利用遺傳算法中輪盤賭選擇算子從中選出數量為population個數的個體進入下一步;
[0021]S7:對上述步驟S6篩選出的population中的每相鄰的兩個染色體都隨機產生一個處於O?I之間數值r。,若r。小於遺傳算法的交叉概率Pc,則對這兩條染色體進行部分匹配交叉運算,若r。大於等於遺傳算法的交叉概率Pc,則對這兩條染色序列體保持不變;
[0022]S8:對上述步驟S7所得到的population中的每一條染色體都隨機產生一個處於O?I之間的數值rm,若rm小於遺傳算法的變異概率Pm,則對該染色體執行變異運算,若rm大於等於遺傳算法的變異概率Pm,則該染色體序列保持不變;
[0023]S9:對上述步驟S8所得到的population中的每一個染色體用最低水平線搜索算法進行解碼,得到對應的排樣圖及板材利用率,同時記錄這個population中的最高利用率Ibest (局部最優解即局部最大利用率)以及對應的染色體,並比較Ibest與gbest的大小,若Ibest大於gbest,則將Ibest賦值給gbest,同時將Ibest對應的染色體序列賦給gbest ;
[0024]SlO:重複以上S6-S9,直到迭代次數達到設定的迭代次數T為止;
[0025]上述優化步驟S7中執行部分匹配交叉運算的具體子步驟包括:
[0026]S301:分別隨機選擇出相鄰兩個染色體序列中處於相同位置上的一部分連續數字,同時交換Al與A2的這兩個部分的連續數字;
[0027]S302:對於所獲得的2組連續數字中相同的數,按照第一組數字位置保持不變、第二組數字調換位置以使該相同數字處於與第一組相同位置,然後在兩組數字中共同約掉相同數字的原則來執行操作,由此獲得新的對應關係;[0028]S303:將上述2個染色體序列中處於相同位置上的所述那部分連續數字予以交換;
[0029]S304:將上述2個染色體序列中除去所述部分連續數字之外的其他部分數字,用上述約掉相同的數所獲得的對應關係進行替換,由此完成部分匹配交叉操作過程並獲得新的2個染色體序列。
[0030]上述優化步驟S8中執行變異運算的具體子步驟包括:
[0031]S401:隨機生成一個處於O~1之間數值r,如果r大於0.5,則對該染色體進行位置變異,否則進行旋轉變異;
[0032]S402:位置變異:隨機選出2個進行位置變異的數字,交換這兩個數字的位置;
[0033]S403:旋轉變異:隨機選出1個進行旋轉變異的數字,將該數字變為其相反數。
[0034]本發明的有益效果為:按照本發明的智能排樣方法,可以很好地滿足矩形件的工藝要求,並且採用了智能算法和啟發式算法相結合,能快速高效尋找到一種優化方案,由此大大提高了企業的材料利用率且能顯著縮短排樣時間,提高排樣效率。
【專利附圖】
【附圖說明】
[0035]圖1是矩形件「一刀切」排樣方法流程圖;
[0036]圖2是最低水平線搜索算法排樣的流程方框圖;
[0037]圖3是排樣結果示意圖;
[0038]圖4是自動排樣方法的收斂速度圖。
【具體實施方式】
[0039]為了使本發明的目的、技術方案及優點更加清楚明白,以下結合附圖及實例,對本發明進行進一步詳細說明。應當理解,此處所描述的具體實例僅僅用於解釋本發明,並不用於限定本發明。
[0040]作為本領域的技術人員所理解的,表現為矩形件的排樣方法存在自身的工藝要求及約束,具體來說,譬如包括:
[0041](1)任意兩個矩形件不重疊且矩形件均不能超出矩形板材的邊界;
[0042](2)被排放矩形件的邊要平行於矩形板材的邊;
[0043](3)原料板本身具有纖維方向,而待排矩形件中的部分矩形存在纖維方向要求,部分矩形不存在纖維方向,故單種矩形能否豎排(本文規定矩形編碼為正數表示矩形橫排,編碼為負數則表示矩形豎排)要根據矩形自身屬性而定;
[0044](4)矩形排樣後要滿足「一刀切」的下料工藝;
[0045]本發明首先對上述工藝要求及約束可建立相應的矩形件排樣數學模型,例如取水平方向的軸為X軸且向右的方向為正,取豎直方向的軸且向上的方向為正,由此建立一個坐標系。在該坐標系中,取矩形板材的左下角為坐標系零點,矩形板材的長與X軸重合,矩形板材的寬與Y軸重合,現在將K種矩形件排放在P張板材上,,其中第i(I <i<k)種零件的數量為Iii,它的纖維方向的長和非纖維方向的寬分別為Ii和Wi,排樣時矩形是否存在纖維方向要求為= I表示存在纖維方向要求,r1 = O表示不存在纖維方向要求);第j(j = 1,2,…,P)張板材纖維方向上的長和非纖維方向上的寬分別為Lj和Wj,則矩形件排樣的數學模型如下:
[0046]
【權利要求】
1.一種用於矩形件的智能排樣方法,包括下列步驟: 51:設定遺傳算法中包括種群population、迭代次數T、交叉概率Pc以及變異概率Pm在內的參數; 52:從矩形零件庫選擇待排樣的矩形件,並提取包括矩形種類K、各種類矩形的數量n1、各種類矩形的尺寸即纖維方向的長Ii和非纖維向的寬Wi,以及矩形排樣時是否存在纖維方向要求在內的矩形相關信息,並對每一個矩形進行十進位整數編碼,由此形成一個矩形序列; 53:從原料庫選擇符合上述矩形件排樣要求的矩形板材,並提取包括板材序號、數量、各序號板材的尺寸即纖維方向的長和非纖維方向的寬在內的板材相關信息; 54:根據上述矩形件信息隨機生成遺傳算法的初始種群population,其中每個染色體就是矩形件的一個排樣序列,矩形件的排樣序列就是根據矩形個數編碼號構成的不重複的隨機序列; 55:利用最低水平線搜索算法對所獲得初始種群進行解碼; 56:利用上述步驟S5獲得的解碼結果生成排樣方案圖,計算得到每個解對應的排樣利用率,並保留最大利用率gbest,全局最優解即全局最大利用率以及對應的染色體序列;利用選擇算子從中選出數量為population個數的個體進入下一步; 57:對上述步驟S6篩選出的population中的每相鄰的兩個染色體都隨機產生一個處於O~I之間數值r。,若r。小於交叉概率Pc,則對這兩條染色體進行部分匹配交叉運算,若rc大於等於交叉概率Pc,則對這兩條染色序列體保持不變; 58:對上述步驟S7所得到的population中的每一條染色體都隨機產生一個處於O~I之間的數值rm,若rm小於變異概率Pm,`則對該染色體執行變異運算,若rm大於等於變異概率Pm,則該染色體序列保持不變; 59:對上述步驟S8所得到的population中的每一個染色體用最低水平線搜索算法進行解碼,得到對應的排樣圖及板材利用率,同時記錄這個population中的最高利用率Ibest以及對應的染色體,並比較Ibest與gbest的大小,若Ibest大於gbest,則將Ibest賦值給gbest,同時將Ibest對應的染色體序列賦給gbest ; SlO:重複以上S6-S9步驟,直到迭代次數達到設定的迭代次數T為止。
2.如權利要求1所述的一種用於矩形件的智能排樣方法,其特徵在於:採用一種最低水平線搜索算法進行解碼,包括以下步驟: 5201:設置初始最高輪廓線為板材底邊; 5202:每當要排入一個矩形Ri,就在最高輪廓線集中選取最低的一段水平線,如果有數段,則選擇最左邊的一段,測試該段最低水平線的寬度是否大於等於要排矩形的寬度; ①如果該最低水平線的寬度大於等於要排矩形Ri的寬度,並且排入高度不超出原料板的邊界,則將該矩形排在此位置,同時更新最高輪廓線集。否則,從矩形Ri所在的位置開始向後搜索可以放進最低水平線的矩形,即從{Ri+1...Rj...RJ中搜索比較與最低水平線寬度最吻合的矩形排入;如果矩形&的寬度與最低水平線最相近且不超出原料板高度,則將矩形Rj排入,同時交換矩形Ri與Rj的位置,(R1, R2,...Rj,...Ri,...Rj,更新最高輪廓線集; ②否則,從該矩形所在的位置開始向後搜索可以放進最低水平線且不超出原料板高度的矩形,比較與最低水平線寬度最吻合矩形件排入,並交換這兩個矩形的位置,同時更新最高輪廓線集; ③如果沒有可以排進最低水平線的矩形,則將最低水平線提高至與高度較低的一段齊平,更新最高輪廓線集。當抬高最低水平線不能排進任何矩形時,重新加一塊原料板; 5203:重複步驟S202,直到排下該矩形件; 5204:重複S202、S203,直到所有矩形件排放完成。
3.如權利要求1所述的一種用於矩形件的智能排樣方法,其特徵在於:採用匹配交叉運算,包括以下步驟: S301:分別隨機選擇出相鄰兩個染色體序列中處於相同位置上的一部分連續數字,同時交換這兩個部分的連續數字; S302:對於所獲得的兩組連續數字中相同的數,按照第一組數字位置保持不變、第二組數字調換位置以使該相同數字處於與第一組相同位置,然後在兩組數字中共同約掉相同數字的原則來執行操作,由此獲得新的對應關係; S303:將上述兩個染色體序列中處於相同位置上的所述那部分連續數字予以交換; S304:將上述兩個染色體序列中除去所述部分連續數字之外的其他部分數字,用上述約掉相同的數所獲得的對應關係進行替換,由此完成部分匹配交叉操作過程並獲得新的2個染色體序列。
4.如權利要求1所述的一種用於矩形件的智能排樣方法,其特徵在於:採用變異運算,包括以下步驟: 5401:隨機生成一個處於O~I之間數值r,如果r大於0.5,則對該染色體進行位置變異,否則進行旋轉變異; 5402:位置變異:隨機選出2個進行位置變異的數字,交換這兩個數字的位置; 5403:旋轉變異:隨機選出I個進行旋轉變異的數字,將該數字變為其相反數。
5.如權利要求1所述的一種用於矩形件的智能排樣方法,其特徵在於:其交叉概率在0.6~0.95的範圍內。
6.如權利要求1所述的一種用於矩形件的智能排樣方法,其特徵在於:其變異概率在0.05~0.2的範圍內。
7.如權利要求1所述的一種用於矩形件的智能排樣方法,其特徵在於:其選擇算子採用輪盤賭方法。
【文檔編號】G06F17/50GK103500255SQ201310483406
【公開日】2014年1月8日 申請日期:2013年10月16日 優先權日:2013年10月16日
【發明者】朱志松, 王桂蘭, 朱龍彪, 陳陽陽, 徐海黎, 王恆, 嚴曉照 申請人:南通大學