盧齊飛，唐 平，張光富，包夢華

（廣東工業(yè)大學 自動化學院，廣東 廣州 510006）

0 引 言

二維不規(guī)則排樣問題是指將一系列二維平面圖形（或零件）互不交疊地放置在某一板材上，使得未被覆蓋的面板面積最小，并且使零件在板材上的排布最優(yōu)，使得板材的利用率最大。相比于矩形件排樣，不規(guī)則排樣的零件和板材為任意多邊形，板材還可能包含內部孔洞，并且增加了排樣角度。從計算復雜性理論來看，二維不規(guī)則排料問題屬于具有高計算復雜性的NPC問題。

為此，國內外眾學者提出了很多不同的排樣優(yōu)化算法。文獻［1］提出了一種分層雙螺旋染色體結構的遺傳算法來解決排樣問題。在排樣策略上對種群重組和保持種群的多樣性提供了新思路，但是文中并沒有考慮多邊形旋轉的問題。文獻［2］提出了一種基于離散差分進化算法的新方法，它將板材排樣問題分解成多個單層的排樣問題，再將單層堆疊組合成包，能夠很好地解決板材中產生的空隙問題，但是該方法還處于實驗階段。文獻［3］設計了基于鄰域搜索和遺傳算法的混合算法，這種算法既發(fā)揮了遺傳算法的全局搜索能力，又體現(xiàn)了鄰域搜索算法的局部搜索能力，但是文獻中只做了矩形件的實驗，對于不規(guī)則圖形的排樣，算法效率不得而知。文獻［4］提出了一種基于重心NFP的二維不規(guī)則多邊形排樣算法，該算法可以處理板材和零件均為不規(guī)則形狀的排樣問題，但是算法時間復雜度太高。文獻［5］利用圖形間的相似度對待排樣的圖形進行分類，從而達到降低算法時間復雜度的目的，但是文獻中對相似度的計算規(guī)則比較模糊，很難判定兩個圖形怎樣才算相似以及相似程度多少等問題。上述工作主要從改進算法和改進排樣策略這兩個方面著手，以期達到提高排樣效率的目的。但是對于問題規(guī)模較大時，零件的形狀并不規(guī)則時，計算時間較長，排樣的利用率不高。

因為石材大板具有不規(guī)則廓形和各種表面缺陷，所以石材的排樣是二維不規(guī)則排樣問題。本文針對石材排樣的特點對它進行了算法設計。首先在算法步驟上進行改進，在編碼方式上采用二進制與十進制編碼相結合的方法，編碼串太長問題和有些相近編碼方案獲得的材料利用率相去甚遠問題得到了一定程度上的解決。然后在排樣策略上，提出了基于圖形矢量信息的相似度的明確計算方法，降低了算法的時間復雜度。并利用該算法，對算例進行測試。從實驗數(shù)據結果來看，排樣質量和排放速度都有提高。

1 問題描述

多邊形的排樣問題就是將n個大小不一的多邊形放在一塊寬為W，長為L的板材中，并尋求一種最佳的排放次序使得該板材的利用率最大。因為多邊形各個頂點的位置關系我們已經知道，所以只需已知它其中一個頂點的坐標（x，y）和旋轉角度α，那么就可以對它進行定位。設Zi（i∈I，I為多邊形集合）為第i個多邊形，Si為第i個多邊形的面積，H為所有多邊形排放后總的結果高度，Emax為最大板材利用率，Zig為圖形i的第g個頂點的坐標，α為圖形i的旋轉角度，Zjg為圖形j的第g個頂點的坐標，β為圖形j的旋轉角度，其中g 表示兩個圖形中的任意一個頂點。為了達到板材利用率最大的目標Emax，其中Emax可以用式（1）表示

必須滿足下列約束條件：

（1）Zi和Zj不能重疊，即當i≠j時，滿足式（2）的條件

（2）Zi必須在板材內，而且必須有一部分圖形與板材的邊界接觸，則肯定要滿足條件：

k為有k個圖形，m為第k個圖形的第m個頂點。

（3）多邊形的最初排放符合BLF原則。

（4）按面積從大到小的順序排放，并且同種多邊形盡量排布在一起。

（5）先把有瑕疵的石材區(qū)域包絡成最接近區(qū)域大小的矩形，并把此區(qū)域記作Bi，i∈（1，2，…，m），m為有m個瑕疵區(qū)域。要求待排樣的多邊形與包絡區(qū)域不相交，即要求滿足式（4）

2 改進的優(yōu)化排樣智能算法

經典的遺傳算法優(yōu)化排樣問題是一個多參數(shù)優(yōu)化問題，它對圖形進行編碼排序產生初始種群，然后通過交叉，變異等一系列遺傳操作，得到不同的排列順序，并挑選出這一代中最優(yōu)的，能夠使板材利用率最大的排列序列，把它保存起來，隨后進行迭代比較，直至經過一定的迭代次數(shù)得到最優(yōu)或次優(yōu)解。而本文提出的算法為了解決隨著種群規(guī)模的增大，傳統(tǒng)算法的復雜度也相應呈指數(shù)增大的問題，對經典方法進行了改進。本文算法優(yōu)化排樣的主要操作有：

2.1 圖形預處理

因為要排樣的圖形包括了矩形，三角形，梯形，平行四邊形和不規(guī)則圖形，所以我們可以先把前面幾種規(guī)則圖形排在一起。例如，可以把三角形對排在一起，變成平行四邊形之后，再進行排放；兩個梯形也可以按照上述方法組合成一個平行四邊形，然后把組合后的平行四邊形與原有的平行四邊形聯(lián)排。對于不規(guī)則件，先獲取不規(guī)則零件內、外輪廓信息，板材信息，先設定一個最小矩形包絡率，判斷零件是否大于最小矩形包絡率，如果是的話，則對零件進行包絡；如果否，則判斷零件是否大于相似度閾值。如果大于則進行相似度計算，如果都不滿足，則進行后續(xù)操作。

圖形的拼接與碰靠如圖1所示。

圖1 圖形的拼接與碰靠

2.2 混合編碼表示

編碼是應用遺傳算法時要解決的首要問題，也是設計遺傳算法時的一個關鍵步驟，它除了決定了個體的染色體排列形式之外，還決定了個體從搜索空間的基因型變換到解空間的表現(xiàn)型的解碼方法。一般編碼表示有二進制編碼，十進制編碼和格雷碼，但是格雷碼并不適用于排樣問題，而經典的遺傳算法通常采用二進制編碼或者十進制編碼。然而Holland證明：當使用二進制編碼時，個體中包含的模式數(shù)目最多，所以他建議使用二進制串來表示個體。但是最大的內在并行性并不能保證提供最優(yōu)的性能，二值串的使用并沒有得到普遍贊同。實際上，對于特定的問題使用相應的編碼方式可以得到更高的性能。本文采用二進制與十進制相結合的編碼策略，使得遺傳算法的搜索范圍和搜索效率都提高了。

表1中前面四項是用十進制編碼，后面四項是用二進制編碼。幾何圖形數(shù)量，幾何元素邊長，幾何元素類型和何種圖形是構成圖形相似性特征的信息。

表1 零件編碼信息

每個零件都有一個零件編號，以便于標識。旋轉角度可以取0°到360°，但是為了搜索速度的加快，可以取10度的倍數(shù)進行搜索。幾何元素的數(shù)量相等或相近是區(qū)分圖形十分相近的重要前提。幾何元素邊長是為利用相似度計算公式所需要的必要條件。何種圖形用4個二進制位用來表示，其中首位的0，1分別表示規(guī)則圖形和不規(guī)則圖形，如三角形為0000，矩形為0010，梯形為0100。幾何元素類型包括直線段00，圓弧10和曲線01。最后兩位用二進制判斷是否需要填充和靠接。

2.3 排樣原則

在板材上排樣時，要盡量選擇一個最佳匹配方案，由于本文需要處理的是規(guī)模較大的規(guī)則圖形和大量的不規(guī)則多邊形，如果采用經典的遺傳算法收斂到最優(yōu)解或者接近最優(yōu)解的次優(yōu)解的時間都是令人難以接受的，因此必須改進算法來提高收斂速度。從而本文提出了通過計算兩個或者多個圖形的相似度，進而對一部分圖形進行歸類，達到簡化計算，加快搜索速度的目的。

2.4 相似度計算

2.4.1 拓撲結構和幾何形狀相似性

定義1 如果兩個圖形構成的幾何元素的數(shù)量相似以及其連接順序也一一對應，則稱這兩個圖形的拓撲結構相似。

定義2 如果兩個圖形滿足拓撲結構相似，且其幾何元素的連接方式也一樣（指的是垂直連接、銳角連接、鈍角連接、相切連接）則稱這兩個圖形幾何形狀相似。

為了比較圖形的幾何相似性，除了采取上述定義下的幾何相似判斷方法，本文還通過畫圓形區(qū)域來達到計算頂點重合程度作用，拓展了幾何相似性的定義。

2.4.2 相似度計算方法

本文通過采取圖形間部分頂點重合后再計算圖形的幾何相似性的方法，并且采取軸對稱兼容與線序倒轉兼容的方式，從而進行兩個多邊形的相似性比較。

幾何相似性的計算既為在相同拓撲結構下，幾何元素相同的數(shù)目的多少決定相似程度的大小。由此，本文得出圖形A和B的相似度為Qs（AB），Qs（AB）可以用式（5）表示

圖2 相似度計算示例

相似度計算具體操作如下：

（1）從磁盤中讀取圖形文件，并得到矢量信息。

（2）將兩個圖形進行消除毛刺工作。

（3）將右邊輸入的圖形通過拉伸變換，旋轉，軸對稱翻轉等操作，使其能夠消除干擾因素，與左邊輸入的圖形處在各自坐標軸上相應的位置，從而方便下一步的操作。

（4）取左邊圖形的某個頂點，設定一個合適的圓形區(qū)域半徑，然后進行頂點重合操作。即如果右邊圖形在這一范圍內有一個或者多個頂點，則認為這一個或者多個頂點視作與左邊圖形對應的一個頂點。采用相似度計算公式，則可以計算出相似度。

圓形區(qū)域選取如下：以一個頂點為圓心，以很小的距離作半徑，畫一個小圓，只要另外一個或幾個頂點在圓內或圓上，即視為重合，如圖3所示。

圖3 圓形區(qū)域的選取

2.5 適應度函數(shù)設計

在優(yōu)化排樣問題中，傳統(tǒng)方法往往只把排樣布局的結果高度作為適應度函數(shù)的唯一參數(shù)。但是排樣優(yōu)化的目標是提高材料利用率，而且排布最高點的位置也會影響適應度函數(shù)。所以綜合考慮以上三點因素我們定義適應度函數(shù)為f（x），可以用式（6）表示

式中：g（χ）——材料利用率，h（χ）——排樣圖的高度，l（χ）——排布最高點中最左邊頂點的x坐標。α，β，γ為權重，取α＝0.5，β＝0.3，γ＝0.2。

2.6 碰撞算法

在不規(guī)則排樣過程中，臨界多邊形（NFP）被廣泛用于計算兩個多邊形之間相互接觸的靠接位置，并求出可能的靠接位置，使排樣過程成為多邊形靠接時零件排放位置的定位優(yōu)化問題。臨界多邊形NFP是這樣得到的：先把其中一個多邊形A 固定，另一個多邊形B 上有一點P，B 在A的輪廓周圍沿A的輪廓線滑動，由P點形成的多邊形就是NFP，NFP有這樣的性質：如果上述多邊形B 擺放時，若P處于NFP內，則A 與B相交；若P處于NFP邊界上，則A 與B剛好接觸；若P處于NFP外，則A 與B 之間存在間隙。所以，NFP法可用于求解新擺放零件相對于己經擺好零件的可行定位。

臨界多邊形法如圖4所示。

圖4 臨界多邊形法

2.7 算法描述

（1）輸入起始的幾何圖形，讀取幾何圖形的矢量信息。

（2）對幾何圖形進行編碼操作。

（3）判斷輸入的圖形是否是規(guī)則圖形，如果是，則對規(guī)則圖形進行隊排，拼接操作，否則，再判斷它是否大于最小矩形包絡率。如果是，則進行矩形包絡，否則，再進行不規(guī)則圖形的相似度計算，并判斷是否大與閾值。如果是，則歸類，否則，等待后續(xù)操作。

（4）利用圖形序列構成一個按面積從大到小排列的染色體，然后根據現(xiàn)有的圖形信息隨機生成10個初始種群。

（5）計算適應度值f，并判斷f是否滿足終止條件，以及迭代次數(shù)是否達到100代。如果是，則跳到（9），否則，進行交叉操作。

（6）采用OX 順序交叉算子進行交叉，并且編碼過程中，當零件編號發(fā)生變化時，幾何元素數(shù)量，幾何元素邊長，幾何元素類型和何種圖形都要隨之變化。并且只能夠序號與序號進行互換，旋轉角度與旋轉角度互換，它們之間不可以進行交叉變換，交換之后根據多邊形的信息得出是否需要填充，并進行相應操作。

（7）然后進行變異，在變異算子選擇上，選取了互換變異。互換變異就是隨機的選擇兩個位置，并將這兩個位置上的零件相互交換，變異概率取0.1。

（8）再進行個體選擇，復制組成新一代種群，并且第一個染色體為適應度值最高的染色體。在選擇過程中，搜索歷史，如果產生的染色體沒有出現(xiàn)過，則加入新一代種群，否則不加入。

（9）最后經過100代迭代之后，得到最優(yōu)解，通過解碼便可以得到排樣結果圖。

算法流程如圖5所示。

圖5 排樣算法流程

3 仿真與結果分析

為了驗證本算法的優(yōu)越性，在VS2010.net系統(tǒng)下，電腦配置為CPU：Intel Core i3 M350＠2.27GHZ，內存：2GB，操作系統(tǒng)：Windows7的PC機下實驗。

（1）輸入給定的圖形，在一塊足夠大的板材上進行排樣。在驗證過程中取種群規(guī)模為N＝10，交叉概率為0.5，變異概率為0.1，設定進化代數(shù)為100?？偣策M行3次實驗，分別排入30個零件，50個零件和80個零件，如圖6、圖7和圖8所示。

由圖6，圖7和圖8可知，隨著圖形數(shù)量的不斷增大，改進的遺傳算法能夠使圖形的占有率顯著增加，但是運行時間也急劇增加。

（3）運用本文算法在MATLAB7.1平臺下進行仿真實驗，用本文算法與遺傳算法GA 對25個矩形件進行排樣，結果如表2和圖9所示。圖9中左圖為本文算法的排樣結果圖，右圖為GA的排樣結果圖。

表2 本文算法與GA 對25個矩形件排樣結果

4 結束語

本文通過對大規(guī)模零件和不規(guī)則石材下料優(yōu)化排樣進行研究，提出了一種改進的遺傳算法來求解此問題。針對遺傳算法排樣占有率低，處理時間長的缺點，在排樣過程中首先對圖形進行預處理，從而方便后續(xù)的排樣操作。然后采取了混合編碼方式，對于本文特定的石材下料問題得到了比單獨使用一種編碼方式的更好的排樣效果。隨后在排樣原則上，提出了基于矢量圖形信息的相似度計算方法，對不規(guī)則圖形進行歸類，并采用臨界多邊形方法進行碰靠，確定零件的位置，提高了排放的速度。通過實驗，本文算法在處理大規(guī)模零件和不規(guī)則石材下料優(yōu)化排樣問題上能夠得到不錯的占有率，并且在占有率和時間復雜度上均優(yōu)于傳統(tǒng)的遺傳算法。但是由于本文算法比較復雜，對于時間復雜度的研究還有待于進一步提高。

［1］Mitsukuni，Matayoshi.Two dimensional rectilinear polygon packing using genetic algorithm with a hierarchical chromosome［C］／／Anchorage，Alaska，USA：IEEE International Conference on Systems，Man，and Cybernetics，2011：989－996.

［2］YAO Fang，LUO Jiaxiang，HU Yueming.Solving two dimensional rectangular boards packing and stacking problems with discrete differential evolution algorithm［J］.Journal of Computer－Aided Design ＆ Computer Graphics，2012，24（3）：406－413（in Chinese）.［姚芳，羅家祥，胡躍明.二維板材組包排樣問題的離散差分進化算法求解［J］.計算機輔助設計與圖形學學報，2012，24（3）：406－413.］

［3］SONG Yanan，XU Ronghua，YANG Yimin，et al.Study on application of hybrid algorithm on parking［J］.Computer Engineering and Applications，2009，45（34）：17－20（in Chinese）.［宋亞男，徐榮華，楊宜民，等.混合算法在排樣問題上的應用研究［J］.計算機工程與應用，2009，45（34）：17－20.］

［4］LIU Huyao，HE Yuanjun.2D irregular nesting algorithm based on gravity center NFP［J］.Chinese Mechanical Engineering，2007，18（6）：723－731（in Chinese）.［劉胡瑤，何援軍.基于重心NFP的不規(guī)則形狀排樣算法［J］.中國機械工程，2007，18（6）：723－731.］

［5］TANG Jiangang，LIU Cong，ZHANG Lihong.Irregular graph stock layout based on improved genetic algorithm［J］.Computer Engineering，2010，36（21）：185－187（in Chinese）.［唐堅剛，劉從，張麗紅.基于改進遺傳算法的不規(guī)則圖形排樣［J］.計算機工程，2010，36（21）：185－187.］

［6］CHEN Duanbing，HUANG Wengqi.Greedy algorithm for rectangle－packing problem［J］.Computer Engineering，2007，35（4）：160－162（in Chinese）.［陳端兵，黃文奇.求解矩形Packing問題的貪心算法［J］.計算機工程，2007，35（4）：160－162.］

［7］ZHANG Pengcheng，ZHANG Rongjie.Solved rectangle’s NFP by polygon segmentation［C］／／CangZhou，China：IEEE International Conference on Power Eng，Hebei Eng ＆Tech Coll，2011：1625－1628.

［8］LIANG Lidong，YE Jiawei.Research of irregular parts packing with genetic algorithm［J］.Computer Engineering and Applications，2009，24（2）：223－228.［梁利東，葉家偉.基于遺傳算法的不規(guī)則件優(yōu)化排樣研究［J］.計算機工程與應用.2009，24（2）：223－228.］

［9］SONG Xiaoxia.Improvement and implementation of technology of initial population in genetic algorithm［J］.Computer Engineering and Design，2007，28（22）：5484－5487（in Chinese）.［宋曉霞.遺傳算法中初始群體技術的改進與實現(xiàn)［J］.計算機工程與設計，2007，28（22）：5484－5487.］

［10］CHEN Shijin，CAO Ju.Heuristic algorithm for rectangular cutting stock problem［J］.Computer Engineering and Applications，2010，46（12）：230－232（in Chinese）.［陳仕軍，曹炬.矩形件優(yōu)化排樣的一種啟發(fā)式算法［J］.計算機工程與應用，2010，46（12）：230－232.］