摘  要： 提出了一種基于遺傳模擬退火算法的啟發(fā)式排樣算法，并將這種算法應(yīng)用于服裝排樣領(lǐng)域以減少原料的浪費。該算法通過基于遺傳模擬退火算法的全局優(yōu)化概率搜索，尋找排樣件在排樣時的最優(yōu)次序及各自的旋轉(zhuǎn)角度，然后采用基于左下角（BL）策略的啟發(fā)式排樣算法實現(xiàn)自動排樣。
    關(guān)鍵詞： 服裝排樣；啟發(fā)式算法；遺傳模擬退火算法

　在服裝行業(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)：
?。?）求交。計算掃描線與多邊形各邊的交點。
　（2）交點取舍。交點中，如果是多邊形的局部最高點或者局部最低點的頂點（極值點），交點算作零個或者兩個交點；如果是頂點但不是極值點，交點只算一個。
?。?）排序。把所有交點按遞增順序進行排序。
?。?）交點配對。第1個與第2個，第3個與第4個……每對交點代表掃描線與多邊形區(qū)域的一個相交區(qū)間。這樣，排樣件可以看作是由一系列水平線段區(qū)間組成，如圖1所示。

　考慮到平面坐標(biāo)中任何圖形都只有x、y兩個方向，所以實際操作中可以用2×n形式的矩陣來表示，如表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ā)式算法對排樣件隊列按以下步驟進行操作：
?。?）取第一個排樣件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方向上的最大值。
?。?）當(dāng)k=i時，按順序，martx中得到第一個區(qū)間（sx1，sx2），martx1中得到區(qū)間（px1，px2）。
?。?）判斷（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）。
?、跓o交點時，martx中若有下一個掃描區(qū)間（px1，px2），轉(zhuǎn)步驟（5）；沒有，轉(zhuǎn)步驟（6）。
?。?）當(dāng)martx中同一掃描線的所有區(qū)間都掃描過后，k=i+1，進行下一條掃描線的掃描，轉(zhuǎn)步驟（4）。
?。?）當(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中為每個排樣件增加一個角度屬性α，那么遺傳個體的染色體編碼為：
X=[（i1，α1，flag1），…，（in，αn，flagn）]
　式中，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為：

　其次，對一件西褲的樣板圖進行實例排樣。樣板如圖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.