改進粒子群搜索的二維皮革排樣優化算法
2016-01-22 01:05:10陳志楊,劉妍
浙江工業大學學報 2015年5期
改進粒子群搜索的二維皮革排樣優化算法
陳志楊，劉妍
(浙江工業大學 計算機科學與技術學院，浙江 杭州 310023)
摘要：針對傳統的排樣方法普遍利用率不高且母版多為矩形的問題，提出了一種在不規則皮革母版上提高排樣利用率的方法，在排樣策略與組合優化上同時進行改進，減少母版的浪費區域.在皮革樣片分塊排放原則的基礎上利用最優匹配原則將不同級別的待排樣片排入質量分級區域，然后結合改進粒子群搜索算法來優化預排樣中原始樣片排布不夠緊湊的問題，實現皮革的優化排樣.實驗結果表明：所提方法在滿足工藝要求的基礎上可以提高皮革的利用率，得到較好的排樣效果.
關鍵詞：分塊排樣；最優匹配；改進粒子群搜索
收稿日期：2015-03-05
基金項目：國家自然科學基金資助項目(61303138)
作者簡介：陳志楊(1971—)，男，河北秦皇島人，教授，研究方向為計算機輔助設計(CAD)、幾何造型和圖形處理，E-mail：czy@zjut.edu.cn.
中圖分類號：TP391
文獻標志碼：A
文章編號：1006-4303(2015)05-0492-05
Abstract:Focusing on the the problem of low utilization and restricted rectangle shape in the traditional nesting way, a method that can improve the utilization of irregular-shape sheets is proposed in this paper. The method improves nesting strategies and combinatorial optimization so that can reduce the waste region on the master. The best-matching rules are used to pack the different levels samples to quality staging area. Then the modified particle swarm optimization search algorithm is used to deal with the problem that the original sample arrangement is not compact enough. It will optimize the leather nesting algorithm. The result show that this method not only meet the technological requirements, but also improve utilization and get the good nesting result.
Keywords:partition nesting; best-matching; improved PSO search
Optimization algorithm of two-dimensional leather nesting
based on improved PSO search
CHEN Zhiyang, LIU Yan
(College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)
工業生產中，排樣問題有著廣泛的應用，如在服裝制造業，木材、皮革等領域的下料問題[1].在皮革加過程中，皮革的裁剪工藝直接影響到皮革制品的優劣，因此對皮革加工質量，效率的要求也越來越高[2].因為皮革材料邊緣不規則，質量分布不均勻，母版的重復加工率低，所以提高皮革排樣的利用率是一個重要問題[3].對于二維排樣問題，不少學者進行過研究.矩形件排樣按照排入策略可分為BL算法[4-5]、改進BL算法[6-7]、填充算法[8]等，按組合優化算法可分為遺傳算法[9]、蟻群算法[10]、粒子群算法[11]等.曹炬[12]提出的背包算法可以快速找到近似最優解，但是計算復雜度較高.黃少麗等[13]提出了組塊策略.劉瑞杰等[14]使用蟻群算法來求解矩形件優化排料問題，將排樣問題用樹來描述，將問題轉變成求取面積最大的二叉樹.梁利東等[15]提出矩形動態匹配算法，能較好的解決矩形板材的排樣問題.目前，針對矩形件的排樣問題主要是將定位求解與定序求解相結合來獲得最優解.
本算法的研究目標是實現皮革母版上的分塊排樣，提高利用率.之前的許多排樣辦法都是在規則的矩形母版上排樣，這種方法不適合皮革不規則的輪廓，同時沒有考慮到工藝要求.通過在皮革母版上進行質量分塊，采用不同的排樣規則，滿足分割要求，同時各部分分別采用粒子群改進算法，豐富了粒子種群的多樣性.在最優匹配原則排樣情況下，使用改進的粒子群算法能更好的尋找樣片的排樣位置，使各個樣片更緊湊的排布在一起，提高排樣的利用率.
1排樣要求與問題描述
1.1排樣要求
在皮革加工行業，因為皮革材料的特殊性以及生產工藝的要求，常常需要在不規則母版上劃分出質量優劣區域，同時將待排樣片劃定級別.在質量較好，瑕疵較少的區域排放一級樣片，瑕疵較多的區域排放二級樣片.一級母版劃定為一個寬為W，高為L的矩形區域，其中排放N個矩形樣片R；每個矩形樣片R的高和寬為hi，wi；二級母版是不規則母版除去一級母版之外的區域.皮革排樣的約束條件是將一級樣片放置在一級母版上，二級樣片放置在二級母版上，Ri，Rj(0 1.2排樣問題描述 初始排樣采用最優匹配算法.最優匹配算法是一種邊長匹配算法，利用邊長與待排母版的剩余長度相似度進行選擇排樣，使母版的利用率達到最大.該算法是先將一級樣片與二級樣片分別按寬度大小進行排序，寬度大的排在存儲數組的前面，相同寬度的樣片按高度遞減的順序依次存儲，然后選擇其中面積最大的開始排樣，先排放面積大的樣片，再排放面積小的樣片. 優化排樣算法的方法是首先按最優匹配原則將所有的原始樣片排入指定區域，求出此時的母版利用率，然后用改進粒子群算法搜索每個樣片的最優排放位置，橫放或者豎放，更新粒子群的粒子值，按最優匹配將樣片排入.如果經過粒子群搜索之后，求得最大的母版利用率，則此時粒子代表的各個樣片排放位置認定為最優排樣方案.如果搜索算法求得的利用率小于第一次的母版利用率，則認定初始排樣位置是最優方案. 2算法描述 為了提高皮革的排樣利用率，在滿足工藝要求的基礎上，采用分塊排樣與最優匹配相結合的方法對待排樣片進行預排樣，求得預排樣的利用率.在此基礎上，用改進的粒子群算法搜索原始樣片是否有更合適的位置放置，從而使排樣的效果更加緊湊. 2.1一級母版放置 一級母版區域的排放步驟為：1) 將一級母版最下面的邊設置為初始最高輪廓線，一級母版的寬設置為初始剩余寬度，記錄此時的最大高度為零；2) 當按面積大小依次排入零件Ri時，在最高輪廓線選擇最低的一段，如果同時存在幾段，選擇最左邊的一段，測試該段的寬度是否大于或者等于Ri的寬度. 如果Ri寬度小于該線段寬度，將樣片排入；如果Ri寬度大于該線段寬度，從剩余樣片中選擇樣片寬度最接近剩余寬度的樣片排入.排入后更新剩余寬度，判斷此時的高度是否大于原來最高輪廓線的高度.如果超過，則更新此時最大的高度為最高輪廓線，即Ri所處位置的高度.重復步驟2，直到所有樣片都排入一級區域. 如圖1所示，4個矩形按面積大小排列.當1，2確定位置后，一級母版剩余的寬度不能放置第3塊矩形，則從剩余的矩形中選擇寬度小于或等于剩余寬度的矩形放置.1，2，4放置好之后，此時最高輪廓線為2的高度，則將第3塊矩形放在第2塊矩形的上面，同時更新最高輪廓線的高度. 圖1 一級邊長匹配過程 Fig.1 The matching process of the first-level side length 如果第一塊一級母版排完規定的一級樣片后還有剩余，即最大高度小于劃定的高度L，可將第二塊中一級樣片放置在第一塊一級母版中，提高板材的利用率. 2.2二級母版放置 二級區域是不規則母版除去一級區域外的不規則圖形，一級區域一般位于母版中間位置，因此二級樣片是向中間一級母版靠攏.二級樣片放置采用邊長匹配融合原則. 首先將一級母版區域定為原始融合圖形，原融合圖形的邊長分為豎直于水平線與平行于水平線兩種，稱為豎界邊與橫界邊，分別將原融合圖形橫界邊與待排樣片的寬度進行相似性匹配.相似度由兩邊的長度比例表示，越接近1，表明相似度越好.找到相似度最高的樣片之后，同時比較豎界邊與待排樣片的高度是否相似度更好.如果相似度更好，則將該待排樣片定位在原融合樣片橫界邊的位置.選定在各個邊長上定位的待排樣片后，與母版邊界進行檢測碰撞.如果沒有重疊，則將這些待排樣片與原融合圖形進行融合，刪除重復的點，形成一個新的融合圖形進行下一輪的排樣篩選. 依次比較原始融合圖形與該二級樣片的各個邊長，設定s為兩個寬度之比，t為兩個高度之比，v為標記位.s，t，v各位的取值如表1所示.標志位v=0，表示樣片進入下一次篩選；v=1時，表示樣片可放置在原融合樣片的豎界邊位置上；v=2時，表示樣片可放置在原融合樣片的橫界邊位置上；v=3時，表示樣片有兩個位置可以選擇，在豎界邊和橫界邊上都能進行定位. 表1 母版與樣片邊長比例情況 原始融合圖形中橫界邊和豎界邊的個數分別為n1，n2，每次定位選擇n1個標志位為2和n2個標志位為1的二級樣片分別放置在原始融合圖形的各個邊上，將這些二級樣片與原始融合圖形進行融合，把重合的點去掉，形成一個新的融合圖形.融合過程就是將新加入進來的點集重新排序，同時刪除多余的點.標志位為3的圖形可以替代任一標志位為1和2的樣片.這個過程不斷重復，直到所有的樣片都放置完畢. 圖2中矩形0為一級母版，1，2，3，4，5分別為按面積排序的5個矩形樣片，依次與一級母版的各個邊長比較相似度.按照相似度由低到高將樣片定位在圖3中的各個位置，圖4為融合之后形成的新融合圖形. 圖2 樣片與融合圖形 Fig.2 The samples and the fused images 圖3 最優匹配定位 Fig.3 The best-matching location 圖4 融合成新的融合圖形 Fig.4 The new fused images 2.3基于改進離散粒子群算法的優化 單純使用最優匹配方法排樣會導致某些樣片寬高比過大，排樣結果不緊湊導致利用率降低.利用粒子群算法可全局搜索排樣位置的最優解，在最優匹配的基礎上對排樣的結果進行優化.之前的研究大多使用標準粒子群算法進行優化，但是標準粒子群算法在求解非線性問題上容易陷入局部最優解[16-17]，因此采用改進的粒子群算法對排樣結果進行優化，更適合求解排樣這種離散問題. 2.3.1標準粒子群算法 粒子群優化算法PSO(Particle swarm optimization)是在1995年由Kennedy等[18]提出，特征是簡單，易操作，具有全局搜索能力.基本粒子群算法的數學描述是：粒子群優化算法中粒子的位置維度代表了該問題的一組解[19].粒子群算法初始為一群隨機粒子，通過不斷迭代找到最優解[20].每次迭代中，粒子按照一定的速度與位置的變化公式更新粒子位置以便搜索新解.用N維向量Xi來表示粒子的位置，Vi表示粒子的速度.假設個體極值Pbi代表當前粒子Pi的最優值，全局極值gbi表示整個種群目前找到的最優解. vin(m+1)=wvin(m)+c1r1[Pbin(m)-xin(m)]+ c2r2[gbin(m)-xin(m)] (1) xin(m+1)=xin(m)+vin(m+1) (2) 公式中第i個樣片的排樣方法為Xi= 2.3.2慣性權重分析與優化 許多研究表明慣性權值w對優化粒子群性能有著重大影響[21-23]，w較小時有利于算法的局部搜索，w較大時在全局的搜索能力較強.在之前的研究中，大多數粒子群算法將w定義為一個小于1的常量.這樣的結果是粒子的速度會越來越小，容易陷入局部最優解.針對這個問題，筆者所提方法采用改進慣性權重w的算法，使w隨著迭代次數不斷變化，在速度更新過程中快速找到最優解，從而改進了算法的性能.所提方法中w定義為 (3) 其中：N為總迭代次數；n為當前的迭代次數.采用這種定義的點是最開始的時候保持w為最大，在開始搜索的時候加快收斂速度.隨著迭代次數的增加，w逐漸減小，可以防止錯過最優解.在速度更新的過程中，自適應地改變慣性權重w，使粒子的收斂速度和收斂精度達到平衡狀態. 2.3.3慣性權重分析與優化 矩形樣片有橫放，豎放兩種放置方法，因此X的取值定義為1，0來表示當前樣片為橫放還是豎放.例如(000110000)表示將第4、第5個樣片豎放，交換第4、第5個樣片的寬和高進行排樣，這樣可以解決樣片如果高度遠大于寬度時，則在排樣過程中會提高最高輪廓線的高度，導致利用率下降的問題.在優化算法中，第i個樣片的X取值為1還是0采用隨機生成的方法，在(0～1)中隨機生成數字，同時設定中間值，小于中間值的保存為0，大于等于中間值的保存為1.經過多次測試，筆者認為中間值選擇0.4可以得到較好的結果. 2.3.4兩種粒子的適應度函數 一級母版區域是已知寬度W的矩形，全部排入一級樣片時的最小高度Lm，第i個一級樣片的面積為ai，定義適應度函數為 (4) 二級區域采用對最后的融合圖形求取凸包面積aG.凸包面積包含了其中的一級母版的面積，假定一級母版的利用率為100%，即剔除一級母版后，求M2個二級樣片的面積與凸包面積的比值.所以二級母版上的適應度函數為 (5) 兩種適應度函數數值越接近1，解的質量越好.對不同區域采用不同的適應度函數來選擇最優解，增加了粒子的位置多樣性，更適用于分塊排樣. 2.3.5粒子群優化算法步驟 Step 1初始化粒子群，在(vmin，vmax)中隨機生成每個粒子的速度，設定最大迭代次數N，隨機生成粒子的位置，學習因子c1，c2，確定適應度函數F. Step 2計算每個粒子的適應度，將所有粒子中適應度數值最大的賦值給gb，對應將粒子Pi的適應度值賦值給Pbi. Step 3開始迭代計算.按式(1)更新粒子的速度，并限制在(vmin，vmax)中，按式(2)更新粒子當前的位置，更新粒子i的當前最優值Pbi以及全局最優值gb. Step 4若達到最大迭代次數，則結束；否則轉Step 3. 3實驗結果與分析 筆者在VC++環境下實現了不規則皮革母版的分區排樣，表2中是排樣的數據結果，母版的整體排樣效果圖如圖5～7所示.圖5中間區域為一級母版的初始排樣情況，無色方塊代表一級樣片的排放位置，黑色方塊為一級母版上的剩余面積.一級母版在初始排樣后經過粒子群搜索優化，得到一級區域的排樣優化圖，如圖6所示.圖7為二級區域的優化排樣結果，黑色陰影位置是圖6中優化排樣后的一級區域，虛線代表整體區域的凸包形狀. 圖5 一級區域初始排樣圖 Fig.5 The original layout of the first-level area 圖6 一級區域優化排樣圖 Fig.6 The optimized layout of the first-level are a 圖7 二級區域優化排樣圖 Fig.7 The optimized layout of the second-level area 由表2數據結果表明：經過優化算法之后，各級母版的利用率都得到了提高.根據初始排樣圖與優化圖的比較，初始排樣時各個樣片按照邊長匹配原則在各個區域中進行放置，母版的浪費區域較多，原因是有些初始樣片的長寬比過大，按原始樣片排放會產生最高輪廓線升高或者放置不下的問題，各個樣片之間不夠緊湊.經過粒子群優化算法得到適應度函數值最大的一組結果，使各個樣片找到最優的排放方式，然后再按照邊長匹配原則將各個處理后的樣片排入，可以得到較優的排樣結果. 4結論 通過分塊排樣，最優匹配原則，結合改進粒子群搜索算法，實現了皮革母版排樣問題的優化，改進后的粒子群算法對慣性權重進行自適應設置，擴展了粒子種群的范圍，一定程度上避免了算法“早熟”，從而在搜索最優位置上比基本的粒子群算法有更大的優勢.此方法在滿足工藝要求的同時，相比單純使用最優匹配原則的排樣辦法增加了樣片在母版上排樣的聚合程度，提高了母版的排樣利用率. 參考文獻： [1]張玉萍，張春麗，蔣壽偉.皮料優化排樣的有效算法[J].軟件學報，2005，16(2):319-323. [2]易秋菊，曾睿，余洋，等.中國皮革行業面臨的嚴峻形勢和機遇[J].西部皮革，2009，31(5):13-17. [3]林智慧，史偉民，楊亮亮.電腦皮革切割機控制系統的研究[J].機電工程，2012，29(8):937-940. [4]BAKER B S, COFFMAN E G, RIVEST R L. Orthogonal packings in two dimensions[J]. SIAM Journal on Computing，1980，9(4)：846-855. [5]CHAZELLE B. The bottom-left bin-packing heuristic:an efficient implementation[J]. IEEE Transactions on Computers，1983，32(8):697-707. [6]劉德全，滕弘飛.矩形件排樣問題的遺傳算法求解[J].小型微型計算機系統，1988，19(12):20-25. [7]董德威，顏云輝，王展.存在表面缺陷原材料的矩形件優化排樣問題研究[J].東北大學學報，2012，9(9):661-664. [8]陶獻偉，王華昌，李志剛.基于填充算法的矩形件排樣優化求解[J].中國機械工程，2003，14(13):1104-1107. [9]張玉萍，宋健，蔣壽偉.基于離散化和遺傳算法的皮革制造中的排樣問題[J].計算機工程，2004，30(23):143-145. [10]劉瑞杰，王麗娟，史原.多種群蟻群算法在矩形件優化排料中的應用[J].江南大學學報：自然科學版，2013，12(13):287-291. [11]董輝，黃勝.二維排樣中小生境粒子群算法的研究與應用[J].浙江工業大學學報，2014，42(3):257-268 [12]曹炬.二維異形切割件優化排樣的擬合算法[J].中國機械工程，2000，11(4):438-441. [13]黃少麗，楊劍，侯桂玉，等.解決二維下料問題的順序啟發式算法[J].計算機工程與應用，2011，47(13):234-237. [14]劉瑞杰，須文波.求解矩形件優化排料蟻群算法[J].江南大學學報：自然科學版，2005，4(1):23-26. [15]梁利東，鐘相強.基于矩形化動態匹配的船體零件排樣算法研究[J].船舶工程，2013，35(1):68-71. [16]溫濤，盛國華，郭權，等.基于改進粒子群算法的Web服務組合[J].計算機學報，2013，36(5):1031-1046. [17]盛煜翔，潘海天，夏陸兵，等.混合混沌粒子群算法在苯與甲苯閃蒸過程優化中的應用[J].浙江工業大學學報，2010，38(3)：318-321． [18]KENNEDY J. Particle swarm optimization[J]. Proceedings of IEEE the International Conference on Neural Networks,1995(4):1942-1948. [19]黃太安，生佳根，徐紅洋.一種改進的簡化粒子群算法[J].計算機仿真，2013，30(2):327-330. [20]隨聰慧，唐慧佳.改進公式的核心主子群粒子群算法[J].計算機應用，2011，31(5):1324-1327. [21]李欣然.粒子群優化算法研究[J].計算機與現代化，2010(6):6-8. [22]王延梁，王理，夏國平．基于混合粒子群算法的裝運機械組合優化問題[J].系統工程理論與實踐，2012，32(10)：2262-2269． [23]韓冬梅，王麗萍，吳秋花.基于模糊偏好的多目標粒子群算法在庫存控制中的應用[J].浙江工業大學學報，2012，40(3)：348-351． (責任編輯：劉巖)
