基于自適應加速因子粒子群優化算法的裁剪分床研究

，，

(浙江工業大學 信息工程學院，杭州 310000)

0 引言

服裝行業的裁剪優化分床問題是根據企業的生產條件和相應訂單情況，將訂單中的號型種類、數量和顏色進行合理搭配，科學的安排裁剪床數、鋪布層數和套排規格件數[1]，使得分床床數達到最少、布料消耗達到最低、生產效率達到最高、裁剪數量誤差最小的優化組合問題[2]。裁剪優化分床一直是制約服裝行業提高生產效率、節約布料的難題，同樣也出現在箱包、家居、鞋帽等行業中。同時，勞動力成本的提升以及服裝材料價格提高，使得服裝生產成本越來越高。因此，通過優化分配以減少分床數量和裁剪誤差，從而減少人工工作量，提高原材料的利用率，降低生產成本，能夠產生巨大的經濟效益，具有重大的現實意義[3]。

傳統的數學思維分床方法具有一定的規范性，但是效率比較低，分床結果誤差比較大，仍然得不到比較理想的分床方案。但相比于人工分床的效率有顯著提高，且分床結果誤差可顯著減少。傳統的數學思維分床方法主要有分組法、加減法、并床法、比例法[4-5]、取半法[6]、等量優化分床法[7]、試湊法等。這些方法對生產訂單的數據要求較高，各號型樣片數量之間必須具備某種特定的關系，具有一定的局限性，只適用于一些特定的訂單，并不適用于實際的分床訂單[7-8]。

因此，為了解決目前在裁剪分床領域遇到的這一難題，本文引入現代智能優化算法，在經典粒子群優化算法(particle swarm optimization，PSO)的基礎上，設計一種基于自適應加速因子粒子群優化算法(SAPSO)的裁剪分床方法。利用SAPSO算法的簡單易實現、參數個數少、收斂速度快等特點，以各號型樣片裁剪數量誤差平方和為目標，建立裁剪優化分配求解的數學模型。最后，通過分床實例驗證了該方法的有效性。

1 裁剪分床的數學模型

服裝裁剪分床是根據生產訂單要求和企業生產條件，將生產訂單中各號型樣片件數、顏色進行合理的組合搭配，科學地制定出裁剪分床床數、各床鋪布層數、各號型套排的配比，并降低布料損耗、減少工時消耗、提高生產效率的工藝設計過程，俗稱分床。裁剪分床主要包括以下幾個方面：(1)生產訂單裁剪分床床數。裁剪分床床數決定了裁剪工時的消耗；(2)每床需要鋪的號型種類，每個號型鋪布的件數。在生產條件允許的范圍內，套排號型種類越多越節約原材料；(3)每床需要鋪布料的層數。在生產條件允許的鋪布層數范圍內，鋪布層數越大，裁剪的效率就會越高。由于在同一床里具有不同號型，不同號型套排的件數也不一樣，因此需要進行合理的優化搭配。

設某服裝生產訂單有m種號型，每種號型的裁剪數量為Di(i=1,2,...,m)、每種號型允許的最大裁剪誤差數量ρ，裁床的鋪布層數Cnt的上限Cntmax和下限Cntmin，各號型樣片在每床上配比Pb的上限Pbmax，最佳的分床床數t。因此，裁剪分床求解的數學模型為：

(1)

約束條件為：

(2)

其中:Ai表示第i種號型樣片實際裁剪的件數，Pbij表示第i種號型樣片在第j床上套排的件數，Cntj表示第j床上的鋪布層數，εi表示第i種號型的裁剪誤差件數，Fvalue表示各號型樣片實際裁剪件數與目標裁剪件數之差的平方和。裁剪分床是在滿足約束條件的前提下，求解使目標Fvalue最小的鋪布層數Cntj和對應的配比Pbij。將上式表示成矩陣的形式：

A=Pb×Cnt

(3)

ε=A-D

(4)

A是各號型樣片實際裁剪數量矩陣；Pb是各號型樣片在各床上套排的件數組成的矩陣，也稱配比矩陣，其中每一行表示某種號型樣片在各床上套排的件數；Cnt是各床鋪布層數的矩陣；ε是各號型樣片裁剪數量的誤差矩陣。

2 SAPSO算法的設計與實現

2.1 算法選擇

由于本模型是非線性的，采用常規的解析法無法進行求解，因此引入現代智能優化算法?，F代智能優化算法很多，但是其中很多算法參數比較多，復雜度較大，實現起來比較難。而粒子群優化算法比較簡單，參數較少，收斂速度快，實現起來比較容易，再結合本模型及裁剪分床的實際情況，優先選擇粒子群優化算法進行求解。

2.1.1 PSO算法

經典粒子群優化算法(PSO)是由Kennedy和Eberhart于1995年提出的一種種群優化算法[9-11]，PSO算法具有概念簡單、實現容易、精度高、收斂速度快和需要調整的參數少等優點，是一種啟發式算法[12-13]。該算法可表述如下：在K維的搜索空間ΩK內，種群的大小M(即粒子的數量)，種群中第i個粒子的位置值αi={α1,α2,…,αM}，速度向量值vi={v1,v2,…,vM}，其中粒子的歷史最好位置Pbesti={Pbest1,Pbest2,…,PbestM}，當前整個種群的全局最好位置Gbest。每個粒子的速度向量值和位置向量值的更新公式分別為：

(5)

(6)

2.1.2 SAPSO算法

針對經典粒子群優化算法求解離散優化問題容易陷入局部最優的問題[14]，在經典粒子群優化算法中引入自適應加速因子，設計了一種基于自適應加速因子粒子群優化算法。其中自適應加速因子與算法迭代次數成反比關系，迭代次數越大，自適應加速因子越小。因此在算法搜索的前期，自適應加速因子較大，算法的全局搜索能力較強，在算法搜索的后期，自適應加速因子較小，算法的局部搜索能力較強，收斂速度更快，搜索效率更高。自適應加速因子粒子群優化算法(SAPSO)的速度和位置更新公式分別為：

(7)

(8)

自適應加速因子為：

(9)

其中:γ為正整數，n為當前迭代次數，N為最大迭代次數。

2.2 裁剪分床方案設計

本文采用SAPSO算法進行裁剪分床方案的設計，其實現過程如圖1裁剪分床實現流程圖所示。

圖1 裁剪分床實現流程圖

第一步，設定裁剪分床過程中的初始條件，其中包括裁剪分床限制條件和SAPSO算法參數；第二步，根據各號型所要裁剪的總件數、每床鋪布層數的上限和下限、每層布可裁剪服裝號型樣片件數上限和下限來計算可能的分床床數；第三步，采用SAPSO算法搜索各床上的鋪布層數：以各床上的鋪布層數作為粒子的位置，給各床在搜索空間內隨機初始化一個層數，同理初始化速度值，將第一個粒子的位置當做局部最優和全局最優的初始值，并且將初始適應值設置為正無窮大；第四步，再采用SAPSO算法搜索在對應鋪布層數下，使配比粒子適應值最小的配比；第五步，根據當前鋪布層數及對應的局部最優值和全局最優值，更新鋪布層數粒子的速度值和位置值，再計算鋪布層數更新后的適應值，以更新鋪布層數粒子的局部最優值和全局最優值；第六步，若迭代次數達到設定值，則以最終搜索的各床鋪布層數和各號型在各床上最優配比作為分床方案，否則轉到第四步繼續搜索。

2.3 SAPSO算法實現

1)首先由用戶根據實際的生產條件設定每床鋪布層數Cnt的上限Cntmax和下限Cntmin，每層布可裁剪樣片總件數T的上限Tmax和下限Tmin，每種號型樣片每床排的件數Pb的上限Pbmax，各號型樣片所需裁剪的件數Si；自適應加速因子正整數參數γ，認知因子c1，社會因子c2，算法迭代過程中層數粒子速度向量的最大限幅Vcmax、配比粒子速度向量的最大限幅Vbmax。

2)然后根據各號型樣片所需裁剪的件數計算出各號型樣片所需裁剪的數量總和：

(10)

平均每床鋪布層數：

(11)

平均每層布裁剪的件數：

(12)

根據以上結果計算出所需分床數量Bedi的上限：

(13)

所需的分床數量下限：

(14)

其中:ceil和floor分別表示向上取整和向下取整。

3)由于計算出來的分床床數Bed是在一個有限的范圍內，所以先搜索床數小的分床方案，如果床數小的方案不符合要求，再去搜索床數大的分床方案。在某一分床床數情況下，采用SAPSO算法搜索鋪布層數，其算法搜索過程如圖2所示。

圖2 鋪布層數粒子搜索流程圖

4)以各床上的鋪布層數作為粒子的位置，給各床在搜索空間ΩK(鋪布層數限制范圍)內隨機初始化一個層數，同理初始化M個粒子{Cnt1,Cnt2,…,CntM}，以及速度向量值{v1,v2,…,vM}，以各號型樣片誤差平方和為適應值Fvalue。令各個粒子的初始個體歷史最優Pbesti=Cnti，粒子的全局最優Gbest=Cnt1。

5)再采用SAPSO算法搜索在對應鋪布層數下，使Fvalue最小的配比Pb：其搜索過程如圖3所示。

圖3 配比粒子搜索流程圖

(1)將第j種號型樣片在各床上的配比作為粒子的位置Pbi，在搜索空間ΨK(配比的限制范圍)內，給該號型樣片在各床上的配比隨機初始化一個值，同理初始化M個粒子{Pb1,Pb2,…,PbM}，速度向量值{vb1,vb2,…,vbM}。令各個粒子的個體歷史最優Pbest1i=Pbi，粒子的全局最優Gbest1i=ceil(Pb1)。(2)根據配比粒子速度更新公式：

(15)

(16)

Fvalue1i=[ceil(Pbi)×Cnti-Dj]2

(17)

通過比較前后兩次適應值的大小來更新粒子的歷史最優配比Pbest1i，以及全局最優配比Gbest1j。(5)迭代次數n1=n1+1，若迭代次數達到設定值N1，給出所有號型樣片對應鋪布層數下的最優配比Gbest1j，結束搜索；否則轉到步驟(2)繼續搜索。同理搜索其他號型樣片在各床上的配比。

6)再根據鋪布層數粒子的速度更新公式：

(18)

7)再根據位置更新公式：

(19)

8)然后計算所有粒子的適應值Fvaluei：

(20)

通過比較前后兩次適應值的大小來更新局部最優Pbesti和全局最優Gbest。

9)迭代次數n=n+1，若迭代次數達到設定值N，則輸出所有號型樣片最優的鋪布層數Gbest和對應的所有號型樣片的最優配比Gbest1，結束搜索；否則轉到步驟5)繼續搜索。

3 實驗結果與性能分析

本實驗的配置環境：硬件配置為Intel Core i3-2310M，CPU主頻為2.40 GHz，4 GB內存；軟件環境：64位Windows7操作系統，安裝Microsoft Visual C++ 2013軟件開發平臺。本方法選擇一個包含6種號型和一個包含5種號型的實際生產訂單進行實驗分析。通過與等量優化分床法分床結果進行對比分析，在分床結果誤差和用料預算上進行比較，對SAPSO算法的性能進行測試，兩者分別針對相同的生產訂單進行分床實驗；與經典PSO算法進行分床效率的比較。SAPSO算法分床過程中兩次的設置參數相同，算法參數設置如下：最大迭代次數N=N1=100，自適應加速因子中正整數參數γ=100，認知因子c1和社會因子c2都取值2，種群大小為M=20。算法迭代過程中層數粒子速度向量的最大限度Vcmax=20、配比粒子速度向量的最大限幅Vbmax=2。分別對兩個訂單進行分床，兩種方法的分床結果如圖4和圖5所示。

圖4 訂單一兩種方法的分床結果

圖4為6種號型訂單兩種方法的分床結果，其中(a)為等量優化分床法結果，(b)為SAPSO算法分床結果；圖5為5種號型訂單兩種方法的分床結果，其中(a)為等量優化分床法結果，(b)為SAPSO算法分床結果。對比兩種分床方法的結果，在相同的約束條件與相同的生產訂單情況下，采用SAPSO算法進行分床的結果明顯比等量優化分床法分床結果誤差??；在用料預算上，SAPSO算法分床結果比等量優化分床法用料預算更少，更節省原材料。雖然在用料預算上提高的不多，但對于訂單量上億的大型企業來說帶來的經濟效益也是不容忽視的。

圖6為經典PSO算法與SAPSO算法的適應度曲線，從兩者的適應度曲線可以看出，SAPSO算法分床在迭代23次左右搜索到最優解，PSO算法分床在迭代52次左右搜索到最優解，從圖6中可以看出SAPSO算法收斂性比PSO算法更快，分床效率更高。

圖5 訂單二兩種方法的分床結果

圖6 PSO與SAPSO算法適應度曲線(實線—SAPSO，虛線—PSO)

4 結論

本文設計的基于SAPSO算法裁剪分床的方法，通過將裁剪分床的鋪布層數和各號型在各床上的配比抽象成SAPSO算法中的粒子進行搜索，有效地減小裁剪誤差，從而提高原材料的利用率，給服裝行業的裁剪分床問題提供了一種新的解決方法。該方法簡單易行，需要調整的參數少，且收斂速度快。實驗結果表明SAPSO算法分床的誤差比等量優化分床法小，并且在用料預算上SAPSO算法分床更少，更節約原材料。SAPSO算法收斂速度比PSO算法快、耗費時間短，效率更高。

[1] 劉艷梅, 顏少聰, 紀楊建,等. 大批量定制服裝裁剪分床計劃的兩階段優化方法[J]. 計算機集成制造系統, 2012,18(3):479-485.

[2] 劉吉慶. 制訂裁剪分配方案的研究[J]. 包裝世界, 2009(4):108-110.

[3] 庹 武, 鄭 攀, 常亭亭, 等. 基于層次分析法的服裝裁剪分床影響因素[J]. 紡織學報, 2013,34(4):148-152.

[4] 師 華, 戴 鴻. 服裝企業裁剪分床案例分析與探討[J]. 山東紡織經濟, 2008(5):117-118.

[5] Degraeve Z, Gochet W, Jans R. Alternative formulations for a layout problem in the fashion industry[J]. European Journal of Operational Research, 2002,143(1):80-93.

[6] 姜 蕾. 服裝生產工藝與設備[M]. 北京：中國紡織出版社, 2004.

[7] 鄭 攀, 庹 武. 服裝裁剪自動分床系統的研究與開發[J]. 山東紡織經濟, 2013,(11):76-79.

[8] 王曉云, 黃珍珍, 張洪志, 等. 服裝裁剪工藝計劃優化系統的開發研究[J]. 價值工程, 2010,29(5):187-188.

[9] 李明陽, 嚴 華. 改進粒子群算法在云計算負載均衡中的應用研究[J]. 計算機測量與控制, 2016,24(10):219-221.

[10] 潘 峰. 粒子群優化算法與多目標優化[M]. 北京：北京理工大學出版社, 2013.

[11] Kennedy J, Eberhart R. Particle swarm optimization[A]. IEEE International Conference on Neural Networks, Proceedings[C]. IEEE, 1995(4):1942-1948.

[12] 程 躍, 程文明, 鄭 嚴. 基于改進粒子群算法的中藥提取過程PID優化控制[J]. 計算機測量與控制, 2010,18(3):533-534.

[13] Ma L, Forouraghi B. A Modified Particle Swarm Optimizer. Advances in Natural Computation[M]. Springer Berlin Heidelberg, 2012.

[14] 趙鴻圖, 劉 云. 改進粒子群算法的小波神經網絡語音去噪[J]. 計算機測量與控制, 2013,21(10):2799-2800.