改進(jìn)的遺傳算法優(yōu)化二維不規(guī)則圖形排樣

盧齊飛，唐 平，張光富，包夢(mèng)華

（廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院，廣東 廣州 510006）

0 引 言

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

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

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

1 問題描述

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

必須滿足下列約束條件：

（1）Zi和Zj不能重疊，即當(dāng)i≠j時(shí)，滿足式（2）的條件

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

k為有k個(gè)圖形，m為第k個(gè)圖形的第m個(gè)頂點(diǎn)。

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

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

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

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

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

2.1 圖形預(yù)處理

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

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

圖1 圖形的拼接與碰靠

2.2 混合編碼表示

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

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

表1 零件編碼信息

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

2.3 排樣原則

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

2.4 相似度計(jì)算

2.4.1 拓?fù)浣Y(jié)構(gòu)和幾何形狀相似性

定義1 如果兩個(gè)圖形構(gòu)成的幾何元素的數(shù)量相似以及其連接順序也一一對(duì)應(yīng)，則稱這兩個(gè)圖形的拓?fù)浣Y(jié)構(gòu)相似。

定義2 如果兩個(gè)圖形滿足拓?fù)浣Y(jié)構(gòu)相似，且其幾何元素的連接方式也一樣（指的是垂直連接、銳角連接、鈍角連接、相切連接）則稱這兩個(gè)圖形幾何形狀相似。

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

2.4.2 相似度計(jì)算方法

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

幾何相似性的計(jì)算既為在相同拓?fù)浣Y(jié)構(gòu)下，幾何元素相同的數(shù)目的多少?zèng)Q定相似程度的大小。由此，本文得出圖形A和B的相似度為Qs（AB），Qs（AB）可以用式（5）表示

圖2 相似度計(jì)算示例

相似度計(jì)算具體操作如下：

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

（2）將兩個(gè)圖形進(jìn)行消除毛刺工作。

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

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

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

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

2.5 適應(yīng)度函數(shù)設(shè)計(jì)

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

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

2.6 碰撞算法

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

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

圖4 臨界多邊形法

2.7 算法描述

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

（2）對(duì)幾何圖形進(jìn)行編碼操作。

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

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

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

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

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

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

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

算法流程如圖5所示。

圖5 排樣算法流程

3 仿真與結(jié)果分析

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

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

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

（3）運(yùn)用本文算法在MATLAB7.1平臺(tái)下進(jìn)行仿真實(shí)驗(yàn)，用本文算法與遺傳算法GA 對(duì)25個(gè)矩形件進(jìn)行排樣，結(jié)果如表2和圖9所示。圖9中左圖為本文算法的排樣結(jié)果圖，右圖為GA的排樣結(jié)果圖。

表2 本文算法與GA 對(duì)25個(gè)矩形件排樣結(jié)果

4 結(jié)束語

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

［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ìn)化算法求解［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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）.［宋亞男，徐榮華，楊宜民，等.混合算法在排樣問題上的應(yīng)用研究［J］.計(jì)算機(jī)工程與應(yīng)用，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］.中國機(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）.［唐堅(jiān)剛，劉從，張麗紅.基于改進(jìn)遺傳算法的不規(guī)則圖形排樣［J］.計(jì)算機(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］.計(jì)算機(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］.計(jì)算機(jī)工程與應(yīng)用.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）.［宋曉霞.遺傳算法中初始群體技術(shù)的改進(jìn)與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與設(shè)計(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］.計(jì)算機(jī)工程與應(yīng)用，2010，46（12）：230－232.］