雙種群混合遺傳算法的裁剪分床應用研究

杜守信，毋 濤

西安工程大學 計算機科學學院，西安710048

裁剪分床計劃（Cut Order Planning，COP）的制定是服裝企業生產過程中難以避免的問題。該問題旨在尋找多尺碼、不規則數量的生產訂單在多個裁床上排布的最佳搭配，來滿足服裝企業低成本、高效率的生產需求。當下的服裝企業訂單大多以短交期、多款式多尺碼、中小批量為主，在客戶的生產訂單到達后，迅速制定裁剪方案并投入生產，能提高企業的生產效率，帶來利潤的顯著提升。COP 的制定是整個生產過程中重要的一環，對生產效率和生產成本都有著關鍵的影響。COP制定過程又受到企業生產環境中眾多因素的影響，在實際生產中可以使用層次分析法[1]來對影響裁剪分床的因素進行分類，并確定影響重大的因素作為裁剪分床數學模型的約束條件。COP 制定時綜合考慮企業的生產環境，將生產需求訂單分到多個裁床，確定裁床鋪布層數，并對每個裁床中的尺碼進行合理搭配，在較短的時間內尋找最優方案并完成裁剪，達到原材料的最大利用和生產成本的最小化，對當下服裝生產企業的競爭與生存有著重要意義。

傳統的裁剪分床方法要求生產訂單不同尺碼之間的數量配比具有一定的規律性，或者人為地增減需求數量而產生一定的規律，這種以經驗為主的分床方法需要進行大量的計算，并且結果有著較大的誤差，造成了很多不必要的浪費。隨著市場需求不斷改變，生產訂單的尺寸、風格、面料和顏色等越來越多樣化，導致COP 問題愈加復雜[2]。為了有效地解決該問題，國內外學者進行了眾多理論研究，其中ünal等為獲取最佳解決方案，使用了混合整數非線性規劃的方法來建立模型，并使用計算機求解[3]。在智能算法的使用方面，Nascimento 和Casali等提出了一種基于狀態空間的啟發式搜索算法來解決裁剪分床問題[4]。M’Hallah 和Bouziri 對裁剪分床中的COP 和TDL（Two-Dimensional Layout）問題進行了整體考慮，使用構造啟發式和元啟發式方法實現最小化織物長度的目的[5]。國內學者王學驥等[6]、江麗林等[7]分別在不同的方向上改進了粒子群優化算法，并用來解決裁剪分床實際問題。實際應用過程中，單一的啟發式算法往往會存在一定的問題，使得結果不總是優秀的，為此一些學者開始考慮結合多種算法來彌補單一算法的缺陷。劉艷梅等提出一種針對大批量定制服裝裁剪分床計劃的兩階段優化算法，分階段尋優得到符合要求的最優解[8]。Xu 和Thomassey 等在遺傳算法尋優的基礎上提出一種基于整數編程的裁剪訂單模型來完成訂單的裁剪計劃[9]。Abeysooriya 和Fernando 則將傳統的啟發式算法與遺傳算法相結合來優化裁剪分床計劃，并提升算法的執行效率[10]。而Tsao 和Liao 等在混合算法的基礎上，結合基于退火的遺傳算法和基于禁忌搜索的遺傳算法，并以降低總成本為目的來進一步解決COP問題[11]。

綜合上述情況，在現有理論中一些單一算法改進的方式已經被混合算法所替代，而在混合算法研究中部分算法沒有從實際生產環境的整體情況來考慮，只在相應的具體情境下進行算法的改進來提升效率，并不能適用于大多數生產過程，還有部分在改進算法的同時增加了算法復雜度，增大了時間成本。

本文對實際服裝生產過程進行綜合、全面的考慮，由于不同類型的生產訂單需求迥異，提出了圍繞多個目標建立的優化數學模型，企業可以通過調整權重參數選擇最符合生產的模型。模型求解利用遺傳算法和粒子群算法兩者的優勢，將算法優化過程分為兩個種群進行，遺傳算法帶來群體多樣性的同時，將優秀的個體組成精英群體再使用粒子群算法優化求解，以較快的速度篩選出最優方案。混合算法在提升搜索效率的同時又減小了陷入局部最優的可能。

1 裁剪分床問題模型

1.1 問題描述

假設某服裝生產企業現接收到一批訂單需要生產，已知該訂單共有n個尺碼，且每個尺碼的需求數量為A={a1,a2,…,an}，考慮企業生產情況，需要制定一個裁剪分床計劃方案，使得生產時間較小，面料利用率較高，裁剪時不可少裁，超出數量也要在一定范圍內，設置各尺碼最大超裁數量為G={g1,g2,…,gn} 。為了更好地進行套排分布，裁床上各尺碼最大鋪設數量設置為S={s1,s2,…,sn} 。

1.2 多維度數學模型的建立

裁剪分床計劃的數學模型，要以生產訂單的尺碼和需求數量為基準，裁床的長度、裁刀的長度、訂單織物的幅寬和厚度、訂單的需求款式等為約束條件，企業實際需求為目標來建立。為了充分利用原材料，減少生產成本和裁剪時間，裁剪分床計劃制定時會盡可能選擇大小尺碼套排的方式。

參照如圖1所示的實際生產裁剪分床流程，從企業的需求出發，分別在超裁數量、裁剪時間、面料利用率三個維度上建立數學模型。

圖1 裁剪分床流程圖Fig.1 Flow chart of cut order planning

在裁剪分床計劃制定時，同一個裁床上不同的套排配比會產生不同的面料使用長度，鋪設尺碼時要在面料的長寬方向進行取整，則第i個裁床面料使用長度的計算公式為：

式中，Cij是裁床i上尺碼j的鋪設數量；w1是待裁剪面料的幅寬；w2是產生裁片的標準寬度；L是最大鋪布長度。

1.2.1 超裁目標函數

超裁數量是制定裁剪分床計劃時的一個必要參數，也是大多數企業生產中主要參考的目標。超裁數量過大會使生產成本上升，整體效率下降，還有可能導致庫存堆積引起大量浪費。但是由于尺碼數量不一致，難免會造成裁剪誤差，在實際裁剪中要使得各尺碼裁片裁剪的誤差盡量小。設進行裁剪時需要的裁床數量為m，為減少整體誤差使用了方差作為目標值，則訂單的裁剪數量誤差目標函數可表示為：

式（3）作為尺碼j裁剪誤差的一個條件函數，生產中裁剪數量不可小于需求數量，因此添加約束來避免少裁。其中，Hi是裁床i的鋪布層數，其數值在裁床鋪布層數最大值Hmax和最小值Hmin之間。

1.2.2 裁剪時間

裁剪時間目標函數主要分為裁剪時間和拉布時間。裁剪時間與裁床臺數、鋪布長度有關，拉布時間受拉布機速度和用布總長度影響。目標函數公式為：

式中，v1是裁床上裁刀的行進速度；v2是拉布機拉布速度。

1.2.3 面料利用率

面料利用率考慮的是在每個裁床上盡可能地實現多尺碼套排分布，并最大地占用鋪設面料長度。目標函數公式為：

2 混合的多種群粒子群-遺傳算法

2.1 算法選擇

根據所建模型的非線性特點，引入了現代智能算法進行模型求解。現代智能算法種類豐富，不同算法又有著不同的適應能力，從模型與算法的相關特性考慮，選擇了粒子群優化算法混合遺傳算法的方式來求解問題模型。

遺傳算法是一種模擬自然進化中的自然選擇和遺傳學機理來搜索最優解的方法[12]，具有較強的全局搜索優化能力，但常規的遺傳算法在求解復雜模型時存在收斂速度慢、優化精度低的缺點。粒子群算法（Particle Swarm Optimization，PSO）是1995 年由Eberhart 博士和Kennedy 博士共同提出的一種模擬鳥類捕食行為的群智能算法，與其他算法相比有著參數少、易實現、收斂速度快的特點[13]。

為了能夠提高算法的全局搜索能力，降低陷入局部最優的可能，并適當提升算法的收斂速度，提出使用多種群的粒子群-遺傳混合算法，將粒子群算法快速收斂能力與遺傳算法的全局多樣性優勢結合起來，并對內部進化機制做出一定的改進。

2.2 多目標數學模型的處理

對于多個目標函數的處理，一般是使用線性組合將多個不同的目標函數按照一定的權重疊加，得到一個最終的函數進行求解。

由于多目標函數尺度不同，要先進行歸一化處理，其中超裁數量目標函數使用訂單尺碼設定的最大超裁數量平方和進行歸一化處理，時間目標中使用了當前情況下的最大裁剪時間進行歸一化處理。

對處理后的目標函數進行線性組合為：

式中α,β,γ≥0 且α ＋β ＋γ=1,是不同目標函數在實際生產中的權重參數。

在模型求解時，算法需要解決的關鍵問題是尋找最優的鋪布層數配比Hi和各尺碼鋪布數量配比Cij，目標函數的尋找過程中使用以下公式：

2.3 混合的雙種群算法設計

采用混合的雙種群粒子群-遺傳算法來解決裁剪分床問題的主要步驟可描述為：第一步，企業根據生產訂單、設備等信息初始化參數，結合生產現狀設定需求模型；第二步，根據已有條件計算合適的分床數量區間并確定算法目標函數；第三步，取可用分床數量M進行算法種群初始化，設定算法最大進化世代數；第四步，使用遺傳算法進化普通群體，進化過程每一代取兩個最優個體加入到精英種群，對種群進行交叉和變異；第五步，等到精英種群數量滿足時，暫停遺傳算法，使用粒子群算法對精英種群進行進化；第六步，記錄粒子群算法進化過程中的局部和全局最優并更新粒子；第七步，粒子群算法進化結束，記錄最優個體，排序并選擇優秀個體替換到普通種群，開始新一輪的混合算法迭代；第八步，算法達到最大迭代次數后比較算法進化結果，取最優個體作為當前分床數M下的最優方案；第九步，當前分床數M=M ＋1，如果仍在可用區間內，轉到第三步繼續使用算法求解，否則比較不同分床數下的最優方案，選擇最符合目標需求的即為最終方案。具體的混合雙種群算法設計流程如圖2。

圖2 混合的雙種群算法設計流程圖Fig.2 Flow chart of double population hybrid genetic algorithm

2.4 算法的實現

2.4.1 編碼方案

算法中個體方案包括各裁床鋪布層數與各裁床各尺碼的數量配比，由于裁床鋪布層數是比較大的實數，使用二進制編碼會導致編碼過長過大，不利于計算，而實數編碼意義明確，且減少了編碼和解碼的步驟，提高了算法效率[14]，為此混合算法編碼時使用了實際數值作為編碼。而算法的求解過程是對裁床鋪布層數矩陣和裁床各尺碼數量配比矩陣同時尋優，會導致嵌套過深而丟失性能，混合算法中考慮兩矩陣的相同維度，尋優過程中將兩者編碼在同一矩陣中，計算時再將結果解碼成兩個獨立矩陣，有效降低了算法的時間復雜度。編碼形式為：

2.4.2 適應度函數

適應度函數通常是根據目標函數進行設計的，混合算法進化時使用目標函數作為個體適應度進行計算，滿足約束條件時，適應度越小代表當前方案越優秀。模型的適應度函數為：

2.4.3 選擇機制

算法進化過程涉及三處選擇，即普通種群進化時選取精英個體更新精英種群，遺傳算法進化中進行交叉個體的選擇，精英群體進化完成后選擇個體替換普通種群。從普通種群中選擇更新精英群體時，在普通種群按照適應度排序，選擇最優的兩個加入到精英種群；遺傳算法進化時和精英種群反向優化普通種群時，均使用輪盤賭的機制選擇個體；保證優秀個體有更大概率選中的同時又保存了個體多樣性。輪盤賭選擇時被選中的概率使用其適應度占比：

式中，fiti為個體適應度，pop代表混合算法的種群大小。

2.4.4 交叉

算法的交叉操作是選擇兩個染色體進行配對，配對染色體的基因片段相互交換形成新的個體，增加種群多樣性。為了在進化時有更好的全局搜索能力，算法中的交叉機制采用隨機交叉的方式進行，在個體矩陣的全索引區間內隨機生成一個整數r，針對選擇的配對個體，交換r后的基因片段。對于選擇機制產生的新種群，令其奇數位置個體與偶數位置個體進行配對交叉，最終獲得一個新的基因種群。具體交叉流程如圖3。

圖3 混合算法交叉機制流程圖Fig.3 Flow chart of hybrid algorithm crossover mechanism

當交叉位置r=n時，如下所示為選擇個體s1、s2進行配對交叉，產生兩個新的子代s3、s4的過程：

2.4.5 變異

變異操作是對種群中一些個體產生隨機的變化來使個體能夠更加適應進化的需求。算法進化的前期過程主要靠交叉操作來產生多樣性，后期則依賴于變異操作，因此算法中采用一種隨進化次數增多而逐漸增加的自適應變異概率，并對選擇的個體生成一個（0，1）內分布的概率矩陣P，所有概率元素與p相比較，如果該基因片段對應的概率大于變異概率不發生變異，小于則發生變異。自適應的變異概率公式為：

式中，p0是初始設定的變異概率；μ是自適應概率的最大尺度；maxIter是算法最大進化代數。

變異算子選取時，在文獻[15]中的變異算子基礎上，結合粒子群算法進化機制，提出了一種基因片段近優趨勢的變異方式。對于個體xk的變異過程公式如下：

式中，ρ是慣性系數；P是變異概率矩陣；σ和θ是兩個學習率。

圖4為算法具體變異流程。

圖4 混合算法變異機制流程圖Fig.4 Flow chart of hybrid algorithm mutation mechanism

2.4.6 粒子群優化算法

精英種群進化時使用一種改進的慣性權重自適應的粒子群優化算法來快速收斂找到最優解，對于精英種群的個體粒子，初始位置已經確定，初始化粒子的速度，并根據速度和位置公式不斷更新粒子狀態，直至達到最大迭代次數或者最優解不再發生變化。進化時更新公式為：

式中，c1、c2是學習因子；r1、r2是隨機數值。

參數對算法的優化性能影響很大，因此在使用中要選擇合適的參數值[16]。慣性權重ω較大時有利于算法跳出局部最優，較小時有利于局部尋優，結合文獻[17]中慣性權重的改進思想，設置一個在進化過程中自適應的慣性權重因子：

式中，ω0是初始設定的慣性因子；ω1是進化過程減小的最大尺度。

2.4.7 混合算法的交叉影響機制

在文獻[18]算法的基礎上，調整種群結構，將改進的遺傳算法和粒子群優化算法結合，提出了交叉影響雙種群的混合算法。將個體分為普通種群和精英種群，普通種群使用遺傳算法進化保留種群的多樣性，精英群體使用粒子群優化算法進化提高收斂速度，在進化過程中雙種群之間交叉影響，相互促進。雙種群影響關系如圖5。

圖5 混合算法進化兩種群交叉影響關系圖Fig.5 Relationship graph of hybrid algorithm evolution of two groups

算法交叉進化時具體流程如圖6。

圖6 混合算法種群交叉進化流程圖Fig.6 Flow chart of hybrid algorithm population cross evolution

3 實驗結果

根據某服裝生產企業的實際需求訂單以及企業生產條件，進行了算法的實用性測試。實驗環境為英特爾Core i5-9300H，2.4 GHz 主頻，16 GB 內存，GTX 1660 Ti 6 GB 顯卡；算法運行環境為PyCharm2017.1。實驗過程選擇了手工計算方法、遺傳算法、粒子群算法與本文算法進行對比。

根據訂單信息表1可知，該訂單所有尺碼總的需求數量為5 016 件，由企業生產條件及生產設備參數可以得到裁床適宜鋪布層數范圍為[50，250]，每層面料最大可以裁剪各尺碼總數量為15，計算出裁床數量的適用區間是[4，8]，設定尺碼套排時每種尺碼數量不超過3 件，尺碼最大允許超裁比例為2%，結合生產需求建立模型并使用混合算法求解。

表1 生產訂單詳情Table 1 Production order details

由圖7 中三種算法的進化曲線可以看出：（1）粒子群算法在進化過程中種群收斂速度較快，卻容易陷入局部最優而停止搜索。（2）遺傳算法更為穩定，在進化過程中能保證種群多樣性，但是算法進化緩慢，需要進行較多的進化世代才能尋找到最優解。（3）混合算法進化速度有顯著提升，圖中混合算法在200代以內便已經尋得最優解并停止了搜索，且最優解也與遺傳算法最優解相當。

圖7 多種算法的適應度和迭代次數的關系曲線圖Fig.7 Relationship graph between fitness and number of iterations of multiple algorithms

使用雙種群粒子群-遺傳混合算法最終獲取最優裁剪分床方案為：

使用人工經驗計算的方式得到一組裁剪分床方案為：

對比算法和人工計算裁剪方案可以得到：智能算法遍歷尋找最優解，滿足裁剪要求的同時會盡可能地套排尺碼來減少裁床的使用數量并降低目標函數值。而人工計算由于不能進行所有可能的枚舉，只能根據經驗及需求數量的規律性來進行分床和排布，套排情況較差且增加1個裁床的成本。

表2 是使用四種不同算法求解同一訂單模型時的結果比較。人工計算的方法多使用1個裁床，超裁數量為59 件，且個別尺碼超裁數量超過了2%，由于裁床數量多，裁剪時間也最長。智能算法結果比人工計算要提高很多，PSO 算法收斂速度快，遺傳算法進化比較穩定。混合算法在各方面數據均優于其他算法，且裁剪超出數量比人工計算減少50%以上，時間縮短了5 min；與單個改進遺傳算法相比，裁剪超出數量少了6 件，裁剪時間提升了0.24 min，算法執行時間加快了16.2%，面料的利用率也保持在較高水平。

表2 多種算法的裁剪分床方案最優結果Table 2 Results of cut order planning schemes based on multiple algorithms

從表3中比較結果可以看出，在使用不同維度的目標函數模型時，算法優化的方向是不同的。與考慮三種目標的結果相比，不考慮裁剪時間和面料利用率得到了超出數量為18 的結果，而裁剪時間增加了7.96 min，面料利用率則下降了3 個百分點；考慮其中兩個目標時，則剩余目標會造成較大的浪費。

表3 不同維度目標函數情況下的結果Table 3 Results under different dimensional objective functions

4 結束語

本文針對服裝生產企業的裁剪分床問題，充分考慮生產條件，提供了一個動態的多維目標函數模型，使企業可以根據自身生產需求調整裁剪方案，提出了使用一種基于雙種群的混合粒子群-遺傳算法來求解多目標模型的流程方法。使用混合算法對企業生產的一個具體訂單信息進行了裁剪分床計劃的制定，并與當下的人工計算方法、粒子群優化算法、遺傳算法進行了對比。

結果表明，雙種群粒子群混合遺傳算法進化過程結合了粒子群和遺傳算法的優勢，提升了算法執行效率的同時能穩定尋優。與手工計算結果相比，裁床數量減少1個，超出裁剪數量降低了60%左右，實際裁剪時間減少5 min。同時分析了實際生產中需求目標不同對裁剪方案的影響，針對不同的目標模型尋求最適宜的裁剪分床方案。證明了本文混合算法有著優秀的尋優能力，且表現穩定，能夠適應不同的生產環境，滿足多種生產需求。

后續研究可以將進化種群進行更系統的分類，突出層次結構，深度結合兩種優化算法，進一步提升裁剪分床過程中的效率和生產利潤。