遺傳模擬退火算法在服裝排料中的研究

程 暉，唐明浩

（東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院，上海 201620）

在服裝行業(yè)制衣過程中，要想降低產(chǎn)品成本，提高原材料的利用率是一個(gè)非常重要的手段。服裝排樣就是按照某種算法合理地在原料上排放要切割的衣服樣件，從而達(dá)到節(jié)約原材料的目的。傳統(tǒng)的排樣方法是由排樣者憑借經(jīng)驗(yàn)采用模板試切的方式進(jìn)行的，一方面效率低下，而且排樣方案的優(yōu)劣完全取決于排樣者的經(jīng)驗(yàn)程度，這樣就造成了很大的局限性。

在現(xiàn)代工業(yè)生產(chǎn)實(shí)際中，排樣一般為不同形狀樣件的混合排樣，這個(gè)屬于NP完全問題，隨著樣件數(shù)量的增加，并將樣件形狀、角度等因素考慮在內(nèi)，會(huì)使問題更加復(fù)雜化。本文提出一種啟發(fā)式算法，同時(shí)將遺傳模擬退火算法相結(jié)合，并應(yīng)用到服裝行業(yè)的服裝樣件的排樣，以解決服裝樣件的混合排樣問題。

1 基于BL策略的啟發(fā)式排樣算法

本文采用遺傳模擬退火算法，通過全局優(yōu)化概率搜索來產(chǎn)生最佳的排樣次序和每個(gè)排樣件的旋轉(zhuǎn)角度，然后用啟發(fā)式排樣算法進(jìn)行定位，實(shí)現(xiàn)自動(dòng)排樣。啟發(fā)式算法采用眾所周知的左下角（BL）策略[1]，每一個(gè)排樣件從板料的右上角開始向板料的左下角平移，重復(fù)水平和垂直方向的移動(dòng)直至無法再向左或者向下移動(dòng)。啟發(fā)式思想的本質(zhì)是模擬人的智能行為，而排樣對(duì)象的幾何表達(dá)方式則是算法實(shí)現(xiàn)的關(guān)鍵。

1.1 排樣對(duì)象的幾何表達(dá)

不規(guī)則形狀的排樣件及樣板的幾何輪廓由直線段和曲線段組成，因?yàn)榍€段可以按一定的精度離散成直線段，所以排樣對(duì)象最終為可能帶有內(nèi)孔特征或者無效區(qū)域的多邊形。設(shè)G（α）為排樣件G旋轉(zhuǎn)α角度后的圖形，G（α）最大和最小的 x、y 坐標(biāo)值分別為 Xmax、Xmin、Ymax、Ymin。以間距為0.25個(gè)單位的水平掃描線順序掃描G（α）的多邊形區(qū)域，經(jīng)過 G（α）的掃描線條數(shù) N=int[（Ymax-Ymin）/4]，計(jì)算掃描線與多邊形的相交區(qū)間，對(duì)于一條掃描線，可以分為4個(gè)步驟實(shí)現(xiàn)：

（1）求交。計(jì)算掃描線與多邊形各邊的交點(diǎn)。

（2）交點(diǎn)取舍。交點(diǎn)中，如果是多邊形的局部最高點(diǎn)或者局部最低點(diǎn)的頂點(diǎn)（極值點(diǎn)），交點(diǎn)算作零個(gè)或者兩個(gè)交點(diǎn)；如果是頂點(diǎn)但不是極值點(diǎn)，交點(diǎn)只算一個(gè)。

（3）排序。把所有交點(diǎn)按遞增順序進(jìn)行排序。

（4）交點(diǎn)配對(duì)。第 1個(gè)與第 2個(gè)，第 3個(gè)與第 4個(gè)……每對(duì)交點(diǎn)代表掃描線與多邊形區(qū)域的一個(gè)相交區(qū)間。這樣，排樣件可以看作是由一系列水平線段區(qū)間組成，如圖1所示。

考慮到平面坐標(biāo)中任何圖形都只有x、y兩個(gè)方向，所以實(shí)際操作中可以用2×n形式的矩陣來表示，如表1所示。這樣既簡潔，使用起來也方便。

表1 排樣圖形矩陣表示

矩陣中的“×”可以是實(shí)際操作中任意一個(gè)用不到的數(shù)字，例如 100，甚至更大。

本文中就是通過這樣的方式來表示原料上已經(jīng)排好的樣件所占的區(qū)域用矩陣martx表示，待排的樣件用同樣的表示方法用矩陣martx1表示。布局過程中通過比較兩者相同掃描線的區(qū)間來判斷要做怎樣的操作。

1.2 基于BL策略的啟發(fā)式算法

啟發(fā)式算法實(shí)現(xiàn)了排樣件在原料上的緊密排列。假設(shè)排樣件的排樣次序和各自的旋轉(zhuǎn)角度已經(jīng)確定，并且也已對(duì)各排樣件做好預(yù)處理，同時(shí)令排樣件的最左最下處為移動(dòng)基準(zhǔn)點(diǎn)。排樣的原料范圍這里假設(shè)為寬度一定、高度不限的區(qū)域，具體可以根據(jù)實(shí)際需要進(jìn)行修改。則基于BL策略的啟發(fā)式算法對(duì)排樣件隊(duì)列按以下步驟進(jìn)行操作：

（1）取第一個(gè)排樣件 G（1），將它的基準(zhǔn)點(diǎn)放在原料的坐標(biāo)原點(diǎn)處，同時(shí)分別取掃描線 0至 G（1）的 y軸方向上的最大值（間隔0.25）進(jìn)行掃描，并且將各掃描線得到的掃面區(qū)間以y軸、x軸升序（y軸優(yōu)先）為原則進(jìn)行存儲(chǔ)，這樣得到已排好的樣件所占的區(qū)域用矩陣martx表示。

（2）按順序依次取排樣件 G（α）（α=2，3，…，N），將排樣件的基準(zhǔn)點(diǎn)放在坐標(biāo)原點(diǎn)。初始化x、y方向上的移動(dòng)距離，m=0，n=0。取掃描線 0到 G（α）的 y方向上的最大值（間隔0.25）進(jìn)行掃描，得到各掃面區(qū)間進(jìn)行存儲(chǔ)，得到矩陣martx1。

（3）依次取 k=i，i=0 至 martx、martxt1 中 y方向上的最大值。

（4）當(dāng) k=i時(shí)，按順序，martx中得到第一個(gè)區(qū)間（sx1，sx2），martx1 中得到區(qū)間（px1，px2）。

（5）判斷（sx1，sx2）與（px1，px2）是否有交點(diǎn)：①有交點(diǎn)時(shí)，令 x=px2-sx1，將 G（α）整體向右平移 x個(gè)單位，判斷平移后的 G（α）是否超出 x方向上的限制，即原料的最大寬度。若超出，將x方向上的平移量清零，即m=0；y方向上的平移量增加 0.25個(gè)單位，即 n=n+0.25；不超出，m=m+x，從 martx中得到下一個(gè)掃描區(qū)間（px1，px2），轉(zhuǎn)步驟（5）；若沒有下一個(gè)掃描區(qū)間，轉(zhuǎn)步驟（6）。

②無交點(diǎn)時(shí)，martx中若有下一個(gè)掃描區(qū)間（px1，px2），轉(zhuǎn)步驟（5）；沒有，轉(zhuǎn)步驟（6）。

（6）當(dāng)martx中同一掃描線的所有區(qū)間都掃描過后，k=i+1，進(jìn)行下一條掃描線的掃描，轉(zhuǎn)步驟（4）。

（7）當(dāng)所有掃描線完成后，可以得到 x、y軸方向上最終的平移量 m、n，將 martx1中的 x值加 m，y值加 n，得到新的 martx1′。對(duì)，martx′、martx1′按照同一掃描線的掃面區(qū)間從小到大原則進(jìn)行合并，得到新的martx。

將圖形的基準(zhǔn)點(diǎn)放在坐標(biāo)原點(diǎn)，若圖形之間的重疊部分較多時(shí)，用以上的啟發(fā)式算法排除出來的結(jié)果較為理想。但如果出現(xiàn)類似圖2的情況時(shí)，結(jié)果就會(huì)出現(xiàn)排樣件之間的重疊。原因在于掃描線k=0～0.55之間兩者沒有重疊的地方，真正需要移動(dòng)的掃描線是從k=0.55開始。當(dāng)k=0.55掃描完后，兩個(gè)排樣件在k=0.55之上的部分都已分開，沒有重疊部分；但此時(shí)可以看到k=0.55以下的部分卻出現(xiàn)了重疊，這是由于掃描線是以y軸正方向順序掃描的，所以k=0.55以下的部分將不會(huì)再予以考慮。

考慮到以上的情況，本文對(duì)上述的算法進(jìn)行了改進(jìn)，增加了一個(gè)回測(cè)的環(huán)節(jié)，也就是從掃描線k=0開始重復(fù)掃描。一個(gè)簡單的方法就是當(dāng)一條掃面線i完成后，對(duì)它之前的0～i-1條掃描線進(jìn)行重復(fù)掃描操作。但這種方法隨著實(shí)際運(yùn)用中排樣件的數(shù)量的增加，重復(fù)操作的次數(shù)將會(huì)呈指數(shù)上升，大大延長了排樣時(shí)間，影響效率。鑒于以上的不足之處，改進(jìn)的部分將利用掃描線值i及排樣件上移量n這兩個(gè)量來簡化這一個(gè)過程。

改進(jìn)的算法為：步驟（5）中有交點(diǎn)的兩種處理方法后，排樣件或是在x軸方向被移動(dòng)，或是在y軸方向被移動(dòng)，此時(shí)計(jì)算掃描線i值與排樣件上移量 n，如果 n＜i，則進(jìn)行 i-n+1 條掃描線掃描（k=n，n+1，…i），并且重復(fù)4×i+1-4×n次操作。通過以上的改進(jìn)，排樣的結(jié)果將如圖3所示，是理想中的效果。

2 模擬退火算法

2.1 遺傳模擬退火混合算法

遺傳模擬退火混合算法是將遺傳算法和模擬退火算法相結(jié)合而構(gòu)成的一種優(yōu)化算法[2]。雖然遺傳算法有較強(qiáng)的全局搜索性能，但它的爬山能力弱，在實(shí)際應(yīng)用中容易產(chǎn)生早熟收斂的問題，并且在進(jìn)化后期搜索效率低。而模擬退火算法卻具有擺脫局部最優(yōu)點(diǎn)的能力，能抑制遺傳算法的早熟現(xiàn)象。因此，考慮將模擬退火的思想引入遺傳算法，有效解決遺傳算法的選擇壓力。

與基本遺傳算法的總體運(yùn)行過程相類似，遺傳模擬退火算法也是從一組隨機(jī)產(chǎn)生的初始解 （初始群體）開始全局最優(yōu)解的搜索過程，它先通過選擇、交叉、變異等遺傳操作來產(chǎn)生一組新的個(gè)體，然后再獨(dú)立地對(duì)所產(chǎn)生出的各個(gè)個(gè)體進(jìn)行模擬退火過程，以其結(jié)果作為下一代群體中的個(gè)體。這個(gè)運(yùn)行過程反復(fù)迭代地進(jìn)行，直到滿足某個(gè)終止條件為止。具體算法流程可以參考文獻(xiàn)[3]，算法能夠在起始溫度與結(jié)束溫度之間充分地實(shí)現(xiàn)退火過程，且各溫度呈線性變化。

2.2 個(gè)體適應(yīng)度評(píng)價(jià)

在服裝行業(yè)中，衣片總是放在一整塊原料上進(jìn)行排放，本文已經(jīng)定義原料為指定寬度，但高度（長度）不限的情況。假設(shè)h為個(gè)體對(duì)應(yīng)的排樣結(jié)果的高度，待排任意多邊形排樣件從原料的最左最下方開始排放（這里采用h作為評(píng)價(jià)標(biāo)準(zhǔn)），高度越小，原料利用率最高，并且考慮到不同的排樣結(jié)果有時(shí)會(huì)有相同的高度h，同時(shí)，為了區(qū)別兩種高度相同的排樣結(jié)果，這里需要再定義一個(gè)寬度d，寬度越小，原料利用率越高。定義遺傳算法的目標(biāo)函數(shù)為 f（x）=h（x）+d（x）。

這里將遺傳算法的適應(yīng)度函數(shù)定義為 1/f（x），則目標(biāo)函數(shù)值將會(huì)轉(zhuǎn)化成[0，1]中的一個(gè)數(shù)，且目標(biāo)函數(shù)越大，適應(yīng)度越小，這樣有利于后面的選擇操作，可以將較為理想的個(gè)體保留下來。

2.3 染色體編碼

編碼是應(yīng)用遺傳算法時(shí)首要解決的問題，也是設(shè)計(jì)遺傳算法時(shí)的一個(gè)關(guān)鍵步驟。編碼方法除了決定個(gè)體的染色體排列形式之外，還決定了個(gè)體從搜索空間的基因型變換到解空間的表現(xiàn)型的解碼方法。這里的解空間的表現(xiàn)型即排樣件的排樣次序和各自的旋轉(zhuǎn)角度。

由于衣片排樣件沒有任何角度限制，因此不但要考慮 0～360°范圍之間 的所有可能角度值，而且還包括排樣件關(guān)于x軸或者y軸可能的鏡像。參考文獻(xiàn)[4]把幾何形體的角度歸納為 0～89°范圍內(nèi)的基本角度和8個(gè)不同鏡像之一的聯(lián)合表示，8個(gè)鏡像如圖4所示。

假設(shè)有n個(gè)待排樣件，第i個(gè)排樣件帶有整數(shù)編號(hào)i。 I=[i1，i2，…，in]是這 n 個(gè)待排樣件的一個(gè)排列，ij是排列中第j個(gè)排樣件的編號(hào)。在排列I中為每個(gè)排樣件增加一個(gè)角度屬性α，那么遺傳個(gè)體的染色體編碼為：

式中，ij是排列中第 j個(gè)排樣件的編號(hào)，1≤ij≤n；αj是第 j個(gè)排樣件的基本旋轉(zhuǎn)角度，0°≤αj≤89°；flagj是第 j個(gè)排樣件的角度鏡像，1≤flagj≤8。

2.4 交叉操作

有兩個(gè)個(gè)體 Xi、Xj在 [1，n]范圍內(nèi)生成兩個(gè)不相等的隨機(jī)數(shù) p和 q，并且 p＜q，從 Xi中的 p位置處開始取（q-p+1）個(gè)基因，構(gòu)成新染色體的前半部分，再從 Xj中取出其余未包含的基因構(gòu)成后半部分[5]。

2.5 變異操作

以上分析的染色體基因位 （ij，αj，flagj）中包含兩部分內(nèi)容：排樣件序號(hào)的屬性、排樣件旋轉(zhuǎn)角度的屬性，這里將變異過程也分成次序變異和角度變異兩個(gè)部分來進(jìn)行。次序變異改變排樣序列，從而形成一個(gè)新的個(gè)體。在[1，n]范圍內(nèi)生成兩個(gè)不相等隨機(jī)數(shù) p和 q，并令 p＜q，然后將兩個(gè)位置上的基因?qū)φ{(diào)。

角度變異是對(duì)基因位中的αj和 flagj分別用各自的等位數(shù)值來替換。αj的變異用[0°，89°]范圍內(nèi)的一個(gè)隨機(jī)數(shù)去替換原值；同樣，flagj的變異用[1，8]范圍內(nèi)的一個(gè)隨機(jī)整數(shù)去替換原值。

2.6 遺傳參數(shù)

為了提高求解效率、改善求解結(jié)果，本文對(duì)群體大小、交叉概率和變異概率這三個(gè)參數(shù)的選擇使用了浮動(dòng)數(shù)值。群體大小M隨著待排樣件數(shù)的多少而變化，這里取染色體的長度作為M值。若有n個(gè)待排樣件，染色體的每一個(gè)基因位（ij，αj，flagj）長度為 3，則 M=3n。 為了保證“優(yōu)秀”的個(gè)體得以保存而遺傳到下一代，而“失敗”的個(gè)體得以改善，個(gè)體的交叉概率和變異概率與個(gè)體適應(yīng)度成反比。在每一代個(gè)體中，若最“優(yōu)秀”的個(gè)體的適應(yīng)度為 Fbest（X），最“失敗”的個(gè)體的適應(yīng)度為 Fworst（X），個(gè)體 Xi的適應(yīng)度為 F（Xi），那么個(gè)體 Xi的交叉概率 Pc和變異概率Pm為：

2.7 模擬退火

經(jīng)過交叉和變異運(yùn)算后，由兩個(gè)父代個(gè)體p1、p2生成兩個(gè)子代個(gè)體c1和c2。對(duì)由父代個(gè)體和子代個(gè)體所組成的兩個(gè)個(gè)體組 p1和c1、p2和 c2，以概率 p接受父代個(gè)體為下一代群體中的個(gè)體，以概率（1-p）接受子代個(gè)體為下一代群體中的個(gè)體，其中：

式中，fp和 fc分別為父代個(gè)體和子代個(gè)體所對(duì)應(yīng)的目標(biāo)函數(shù)值，T為溫度參數(shù)。

本文的遺傳模擬退火算法流程圖可簡單用圖5來描述。

3 排樣實(shí)例及分析

為了實(shí)例說明本文研究的排樣算法的排樣效果，在Matlab 7.6環(huán)境下對(duì)算法進(jìn)行仿真。首先進(jìn)行單一圖形的排樣，排樣件的形狀如圖6所示，數(shù)量為16個(gè)，范圍界定為15×8個(gè)單位。結(jié)果如圖6所示，可以看到，單一排樣件排樣的結(jié)果還是令人滿意的。

其次，對(duì)一件西褲的樣板圖進(jìn)行實(shí)例排樣。樣板如圖7所示，圖中為兩條西褲的所有部分，共28個(gè)，選擇寬度為15個(gè)單位，高度為20個(gè)單位的區(qū)域作為原料范圍。

因?yàn)榇艠硬糠值臄?shù)量為28，可以得到種群的大小M=3n=84，經(jīng)過100次的迭代后，其結(jié)果如圖 8所示，高度為9.2個(gè)單位；經(jīng)過200次迭代結(jié)果如圖9所示，高度為8個(gè)單位。從結(jié)果可以看出，本文的算法對(duì)于服裝樣板具有良好的排樣效果，有一定的應(yīng)用性。

本文將人工智能研究領(lǐng)域中的遺傳模擬退火算法運(yùn)用到服裝行業(yè)的計(jì)算機(jī)排樣領(lǐng)域中，通過在遺傳算法的搜索過程中結(jié)合退火算法的思想，將與領(lǐng)域知識(shí)相關(guān)的局部搜索策略運(yùn)用于單純的全局優(yōu)化概率搜索來提高衍化效率。利用遺傳模擬退火算法的全局優(yōu)化搜索能力，尋找出排樣件最優(yōu)（排列最緊密）的排樣次序及各自的旋轉(zhuǎn)角度，再結(jié)合啟發(fā)式排樣算法，得到了一種實(shí)用高效的排樣算法。

[1]BAKER B S， COFFMAN E G， RIVEST R L.Orthogonal packing in two dimensions[J].SIAM Journal on Computing，1980， 9（4）：846-855.

[2]賈志欣，殷國富，羅陽，等.矩形件排樣問題的模擬退火算法求解[J].四川大學(xué)學(xué)報(bào)（工程科學(xué)版），2001（5）.

[3]康立山，謝云.非數(shù)值并行算法-模擬退火算法[M].北京：科學(xué)出版社，2008.

[4]BABU A R，BABU N R.A generic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms[J].Computer-Aided Design， 2001， 33（12）： 879-891.

[5]劉勇，康立山，陳毓屏.非數(shù)值并行算法-遺傳算法[M].北京：科學(xué)出版社，2007.