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

　在服裝行業制衣過程中，要想降低產品成本，提高原材料的利用率是一個非常重要的手段。服裝排樣就是按照某種算法合理地在原料上排放要切割的衣服樣件，從而達到節約原材料的目的。傳統的排樣方法是由排樣者憑借經驗采用模板試切的方式進行的，一方面效率低下，而且排樣方案的優劣完全取決于排樣者的經驗程度，這樣就造成了很大的局限性。
　在現代工業生產實際中，排樣一般為不同形狀樣件的混合排樣，這個屬于NP完全問題，隨著樣件數量的增加，并將樣件形狀、角度等因素考慮在內，會使問題更加復雜化。本文提出一種啟發式算法，同時將遺傳模擬退火算法相結合，并應用到服裝行業的服裝樣件的排樣，以解決服裝樣件的混合排樣問題。
1 基于BL策略的啟發式排樣算法
　本文采用遺傳模擬退火算法，通過全局優化概率搜索來產生最佳的排樣次序和每個排樣件的旋轉角度，然后用啟發式排樣算法進行定位，實現自動排樣。啟發式算法采用眾所周知的左下角（BL）策略[1]，每一個排樣件從板料的右上角開始向板料的左下角平移，重復水平和垂直方向的移動直至無法再向左或者向下移動。啟發式思想的本質是模擬人的智能行為，而排樣對象的幾何表達方式則是算法實現的關鍵。
1.1 排樣對象的幾何表達
　不規則形狀的排樣件及樣板的幾何輪廓由直線段和曲線段組成，因為曲線段可以按一定的精度離散成直線段，所以排樣對象最終為可能帶有內孔特征或者無效區域的多邊形。設G（α）為排樣件G旋轉α角度后的圖形，G（α）最大和最小的x、y坐標值分別為Xmax、Xmin、Ymax、Ymin。以間距為0.25個單位的水平掃描線順序掃描G（α）的多邊形區域，經過G（α）的掃描線條數N=int[（Ymax-Ymin）/4]，計算掃描線與多邊形的相交區間，對于一條掃描線，可以分為4個步驟實現：
?。?）求交。計算掃描線與多邊形各邊的交點。
　（2）交點取舍。交點中，如果是多邊形的局部最高點或者局部最低點的頂點（極值點），交點算作零個或者兩個交點；如果是頂點但不是極值點，交點只算一個。
?。?）排序。把所有交點按遞增順序進行排序。
　（4）交點配對。第1個與第2個，第3個與第4個……每對交點代表掃描線與多邊形區域的一個相交區間。這樣，排樣件可以看作是由一系列水平線段區間組成，如圖1所示。

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

　矩陣中的“×”可以是實際操作中任意一個用不到的數字，例如100，甚至更大。
　本文中就是通過這樣的方式來表示原料上已經排好的樣件所占的區域用矩陣martx表示，待排的樣件用同樣的表示方法用矩陣martx1表示。布局過程中通過比較兩者相同掃描線的區間來判斷要做怎樣的操作。
1.2 基于BL策略的啟發式算法
　啟發式算法實現了排樣件在原料上的緊密排列。假設排樣件的排樣次序和各自的旋轉角度已經確定，并且也已對各排樣件做好預處理，同時令排樣件的最左最下處為移動基準點。排樣的原料范圍這里假設為寬度一定、高度不限的區域，具體可以根據實際需要進行修改。則基于BL策略的啟發式算法對排樣件隊列按以下步驟進行操作：
?。?）取第一個排樣件G（1），將它的基準點放在原料的坐標原點處，同時分別取掃描線0至G（1）的y軸方向上的最大值（間隔0.25）進行掃描，并且將各掃描線得到的掃面區間以y軸、x軸升序（y軸優先）為原則進行存儲，這樣得到已排好的樣件所占的區域用矩陣martx表示。
?。?）按順序依次取排樣件G（α）（α=2，3，…，N），將排樣件的基準點放在坐標原點。初始化x、y方向上的移動距離，m=0，n=0。取掃描線0到G（α）的y方向上的最大值（間隔0.25）進行掃描，得到各掃面區間進行存儲，得到矩陣martx1。
　（3）依次取k=i，i=0至martx、martxt1中y方向上的最大值。
?。?）當k=i時，按順序，martx中得到第一個區間（sx1，sx2），martx1中得到區間（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中得到下一個掃描區間（px1，px2），轉步驟（5）；若沒有下一個掃描區間，轉步驟（6）。
　②無交點時，martx中若有下一個掃描區間（px1，px2），轉步驟（5）；沒有，轉步驟（6）。
?。?）當martx中同一掃描線的所有區間都掃描過后，k=i+1，進行下一條掃描線的掃描，轉步驟（4）。
?。?）當所有掃描線完成后，可以得到x、y軸方向上最終的平移量m、n，將martx1中的x值加m，y值加n，得到新的martx1′。對，martx′、martx1′按照同一掃描線的掃面區間從小到大原則進行合并，得到新的martx。
　將圖形的基準點放在坐標原點，若圖形之間的重疊部分較多時，用以上的啟發式算法排除出來的結果較為理想。但如果出現類似圖2的情況時，結果就會出現排樣件之間的重疊。原因在于掃描線k=0~0.55之間兩者沒有重疊的地方，真正需要移動的掃描線是從k=0.55開始。當k=0.55掃描完后，兩個排樣件在k=0.55之上的部分都已分開，沒有重疊部分；但此時可以看到k=0.55以下的部分卻出現了重疊，這是由于掃描線是以y軸正方向順序掃描的，所以k=0.55以下的部分將不會再予以考慮。

　考慮到以上的情況，本文對上述的算法進行了改進，增加了一個回測的環節，也就是從掃描線k=0開始重復掃描。一個簡單的方法就是當一條掃面線i完成后，對它之前的0~i-1條掃描線進行重復掃描操作。但這種方法隨著實際運用中排樣件的數量的增加，重復操作的次數將會呈指數上升，大大延長了排樣時間，影響效率。鑒于以上的不足之處，改進的部分將利用掃描線值i及排樣件上移量n這兩個量來簡化這一個過程。
　改進的算法為：步驟（5）中有交點的兩種處理方法后，排樣件或是在x軸方向被移動，或是在y軸方向被移動，此時計算掃描線i值與排樣件上移量n，如果n<i，則進行i-n+1條掃描線掃描（k=n，n+1，…i），并且重復4×i+1-4×n次操作。通過以上的改進，排樣的結果將如圖3所示，是理想中的效果。

2 模擬退火算法
2.1 遺傳模擬退火混合算法
　遺傳模擬退火混合算法是將遺傳算法和模擬退火算法相結合而構成的一種優化算法[2]。雖然遺傳算法有較強的全局搜索性能，但它的爬山能力弱，在實際應用中容易產生早熟收斂的問題，并且在進化后期搜索效率低。而模擬退火算法卻具有擺脫局部最優點的能力，能抑制遺傳算法的早熟現象。因此，考慮將模擬退火的思想引入遺傳算法，有效解決遺傳算法的選擇壓力。
　與基本遺傳算法的總體運行過程相類似，遺傳模擬退火算法也是從一組隨機產生的初始解（初始群體）開始全局最優解的搜索過程，它先通過選擇、交叉、變異等遺傳操作來產生一組新的個體，然后再獨立地對所產生出的各個個體進行模擬退火過程，以其結果作為下一代群體中的個體。這個運行過程反復迭代地進行，直到滿足某個終止條件為止。具體算法流程可以參考文獻[3]，算法能夠在起始溫度與結束溫度之間充分地實現退火過程，且各溫度呈線性變化。
2.2 個體適應度評價
　在服裝行業中，衣片總是放在一整塊原料上進行排放，本文已經定義原料為指定寬度，但高度（長度）不限的情況。假設h為個體對應的排樣結果的高度，待排任意多邊形排樣件從原料的最左最下方開始排放（這里采用h作為評價標準），高度越小，原料利用率最高，并且考慮到不同的排樣結果有時會有相同的高度h，同時，為了區別兩種高度相同的排樣結果，這里需要再定義一個寬度d，寬度越小，原料利用率越高。定義遺傳算法的目標函數為f（x）=h（x）+d（x）。
　這里將遺傳算法的適應度函數定義為1/f（x），則目標函數值將會轉化成[0，1]中的一個數，且目標函數越大，適應度越小，這樣有利于后面的選擇操作，可以將較為理想的個體保留下來。
2.3 染色體編碼
　編碼是應用遺傳算法時首要解決的問題，也是設計遺傳算法時的一個關鍵步驟。編碼方法除了決定個體的染色體排列形式之外，還決定了個體從搜索空間的基因型變換到解空間的表現型的解碼方法。這里的解空間的表現型即排樣件的排樣次序和各自的旋轉角度。
　由于衣片排樣件沒有任何角度限制，因此不但要考慮0～360°范圍之間的所有可能角度值，而且還包括排樣件關于x軸或者y軸可能的鏡像。參考文獻[4]把幾何形體的角度歸納為0~89°范圍內的基本角度和8個不同鏡像之一的聯合表示，8個鏡像如圖4所示。

　假設有n個待排樣件，第i個排樣件帶有整數編號i。I=[i1，i2，…，in]是這n個待排樣件的一個排列，ij是排列中第j個排樣件的編號。在排列I中為每個排樣件增加一個角度屬性α，那么遺傳個體的染色體編碼為：
X=[（i1，α1，flag1），…，（in，αn，flagn）]
　式中，ij是排列中第j個排樣件的編號，1≤ij≤n；αj是第j個排樣件的基本旋轉角度，0°≤αj≤89°；flagj是第j個排樣件的角度鏡像，1≤flagj≤8。
2.4 交叉操作
　有兩個個體Xi、Xj在[1，n]范圍內生成兩個不相等的隨機數p和q，并且p＜q，從Xi中的p位置處開始取（q-p+1）個基因，構成新染色體的前半部分，再從Xj中取出其余未包含的基因構成后半部分[5]。
2.5 變異操作
　以上分析的染色體基因位（ij，αj，flagj）中包含兩部分內容：排樣件序號的屬性、排樣件旋轉角度的屬性，這里將變異過程也分成次序變異和角度變異兩個部分來進行。次序變異改變排樣序列，從而形成一個新的個體。在[1，n]范圍內生成兩個不相等隨機數p和q，并令p<q，然后將兩個位置上的基因對調。
角度變異是對基因位中的αj和flagj分別用各自的等位數值來替換。αj的變異用[0°，89°]范圍內的一個隨機數去替換原值；同樣，flagj的變異用[1，8]范圍內的一個隨機整數去替換原值。
2.6 遺傳參數
　為了提高求解效率、改善求解結果，本文對群體大小、交叉概率和變異概率這三個參數的選擇使用了浮動數值。群體大小M隨著待排樣件數的多少而變化，這里取染色體的長度作為M值。若有n個待排樣件，染色體的每一個基因位（ij，αj，flagj）長度為3，則M=3n。為了保證“優秀”的個體得以保存而遺傳到下一代，而“失敗”的個體得以改善，個體的交叉概率和變異概率與個體適應度成反比。在每一代個體中，若最“優秀”的個體的適應度為Fbest（X），最“失敗”的個體的適應度為Fworst（X），個體Xi的適應度為F（Xi），那么個體Xi的交叉概率Pc和變異概率Pm為：

　其次，對一件西褲的樣板圖進行實例排樣。樣板如圖7所示，圖中為兩條西褲的所有部分，共28個，選擇寬度為15個單位，高度為20個單位的區域作為原料范圍。
　因為待排樣部分的數量為28，可以得到種群的大小M=3n=84，經過100次的迭代后，其結果如圖8所示，高度為9.2個單位；經過200次迭代結果如圖9所示，高度為8個單位。從結果可以看出，本文的算法對于服裝樣板具有良好的排樣效果，有一定的應用性。

　本文將人工智能研究領域中的遺傳模擬退火算法運用到服裝行業的計算機排樣領域中，通過在遺傳算法的搜索過程中結合退火算法的思想，將與領域知識相關的局部搜索策略運用于單純的全局優化概率搜索來提高衍化效率。利用遺傳模擬退火算法的全局優化搜索能力，尋找出排樣件最優（排列最緊密）的排樣次序及各自的旋轉角度，再結合啟發式排樣算法，得到了一種實用高效的排樣算法。
參考文獻
[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].四川大學學報（工程科學版），2001（5）.
[3] 康立山，謝云.非數值并行算法-模擬退火算法[M]. 北京：科學出版社，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] 劉勇，康立山，陳毓屏.非數值并行算法-遺傳算法[M]. 北京：科學出版社，2007.