程 暉，唐明浩

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

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

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

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

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

1.1 排樣對象的幾何表達

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

（1）求交。計算掃描線與多邊形各邊的交點。

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

（3）排序。把所有交點按遞增順序進行排序。

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

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

表1 排樣圖形矩陣表示

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 模擬退火算法

2.1 遺傳模擬退火混合算法

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

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

2.2 個體適應(yīng)度評價

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

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

2.3 染色體編碼

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

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

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

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

2.4 交叉操作

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

2.5 變異操作

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

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

2.6 遺傳參數(shù)

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

2.7 模擬退火

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

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

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

3 排樣實例及分析

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

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

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

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

[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é)報（工程科學(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.