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

　在服裝行業(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)，會使問題更加復(fù)雜化,。本文提出一種啟發(fā)式算法,，同時(shí)將遺傳模擬退火算法相結(jié)合，并應(yīng)用到服裝行業(yè)的服裝樣件的排樣,，以解決服裝樣件的混合排樣問題,。
1 基于BL策略的啟發(fā)式排樣算法
　本文采用遺傳模擬退火算法，通過全局優(yōu)化概率搜索來產(chǎn)生最佳的排樣次序和每個(gè)排樣件的旋轉(zhuǎn)角度,，然后用啟發(fā)式排樣算法進(jìn)行定位,，實(shí)現(xiàn)自動排樣。啟發(fā)式算法采用眾所周知的左下角（BL）策略[1],，每一個(gè)排樣件從板料的右上角開始向板料的左下角平移,，重復(fù)水平和垂直方向的移動直至無法再向左或者向下移動,。啟發(fā)式思想的本質(zhì)是模擬人的智能行為，而排樣對象的幾何表達(dá)方式則是算法實(shí)現(xiàn)的關(guān)鍵,。
1.1 排樣對象的幾何表達(dá)
　不規(guī)則形狀的排樣件及樣板的幾何輪廓由直線段和曲線段組成,，因?yàn)榍€段可以按一定的精度離散成直線段，所以排樣對象最終為可能帶有內(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ū)間,，對于一條掃描線,，可以分為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è)。
?。?）排序,。把所有交點(diǎn)按遞增順序進(jìn)行排序。
?。?）交點(diǎn)配對,。第1個(gè)與第2個(gè)，第3個(gè)與第4個(gè)……每對交點(diǎn)代表掃描線與多邊形區(qū)域的一個(gè)相交區(qū)間,。這樣,，排樣件可以看作是由一系列水平線段區(qū)間組成，如圖1所示,。

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

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

　考慮到以上的情況,，本文對上述的算法進(jìn)行了改進(jìn)，增加了一個(gè)回測的環(huán)節(jié),，也就是從掃描線k=0開始重復(fù)掃描,。一個(gè)簡單的方法就是當(dāng)一條掃面線i完成后，對它之前的0~i-1條掃描線進(jìn)行重復(fù)掃描操作,。但這種方法隨著實(shí)際運(yùn)用中排樣件的數(shù)量的增加,，重復(fù)操作的次數(shù)將會呈指數(shù)上升，大大延長了排樣時(shí)間,，影響效率,。鑒于以上的不足之處，改進(jìn)的部分將利用掃描線值i及排樣件上移量n這兩個(gè)量來簡化這一個(gè)過程,。
　改進(jìn)的算法為：步驟（5）中有交點(diǎn)的兩種處理方法后,，排樣件或是在x軸方向被移動,，或是在y軸方向被移動,，此時(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ú)立地對所產(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)度評價(jià)
　在服裝行業(yè)中，衣片總是放在一整塊原料上進(jìn)行排放,，本文已經(jīng)定義原料為指定寬度,，但高度（長度）不限的情況。假設(shè)h為個(gè)體對應(yīng)的排樣結(jié)果的高度,，待排任意多邊形排樣件從原料的最左最下方開始排放（這里采用h作為評價(jià)標(biāo)準(zhǔn)）,，高度越小，原料利用率最高，并且考慮到不同的排樣結(jié)果有時(shí)會有相同的高度h,，同時(shí),，為了區(qū)別兩種高度相同的排樣結(jié)果，這里需要再定義一個(gè)寬度d,，寬度越小,，原料利用率越高。定義遺傳算法的目標(biāo)函數(shù)為f（x）=h（x）+d（x）,。
　這里將遺傳算法的適應(yīng)度函數(shù)定義為1/f（x）,，則目標(biāo)函數(shù)值將會轉(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ù)編號i,。I=[i1，i2,，…,，in]是這n個(gè)待排樣件的一個(gè)排列，ij是排列中第j個(gè)排樣件的編號,。在排列I中為每個(gè)排樣件增加一個(gè)角度屬性α,，那么遺傳個(gè)體的染色體編碼為：
X=[（i1，α1,，flag1）,，…，（in,，αn,，flagn）]
　式中,，ij是排列中第j個(gè)排樣件的編號，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位置處開始?。╭-p+1）個(gè)基因，構(gòu)成新染色體的前半部分,，再從Xj中取出其余未包含的基因構(gòu)成后半部分[5],。
2.5 變異操作
　以上分析的染色體基因位（ij，αj,，flagj）中包含兩部分內(nèi)容：排樣件序號的屬性,、排樣件旋轉(zhuǎn)角度的屬性，這里將變異過程也分成次序變異和角度變異兩個(gè)部分來進(jìn)行,。次序變異改變排樣序列,，從而形成一個(gè)新的個(gè)體。在[1,，n]范圍內(nèi)生成兩個(gè)不相等隨機(jī)數(shù)p和q,，并令p<q，然后將兩個(gè)位置上的基因?qū)φ{(diào),。
角度變異是對基因位中的αj和flagj分別用各自的等位數(shù)值來替換,。αj的變異用[0°，89°]范圍內(nèi)的一個(gè)隨機(jī)數(shù)去替換原值,；同樣,，flagj的變異用[1，8]范圍內(nèi)的一個(gè)隨機(jī)整數(shù)去替換原值,。
2.6 遺傳參數(shù)
　為了提高求解效率,、改善求解結(jié)果，本文對群體大小,、交叉概率和變異概率這三個(gè)參數(shù)的選擇使用了浮動數(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為：

　其次,，對一件西褲的樣板圖進(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é)果可以看出，本文的算法對于服裝樣板具有良好的排樣效果,，有一定的應(yīng)用性,。

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