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

，，

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

0 引言

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

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

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

1 裁剪分床的數(shù)學模型

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

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

(1)

約束條件為：

(2)

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

A=Pb×Cnt

(3)

ε=A-D

(4)

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

2 SAPSO算法的設計與實現(xiàn)

2.1 算法選擇

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

2.1.1 PSO算法

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

(5)

(6)

2.1.2 SAPSO算法

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

(7)

(8)

自適應加速因子為：

(9)

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

2.2 裁剪分床方案設計

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

圖1 裁剪分床實現(xiàn)流程圖

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

2.3 SAPSO算法實現(xiàn)

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

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

(10)

平均每床鋪布層數(shù)：

(11)

平均每層布裁剪的件數(shù)：

(12)

根據(jù)以上結果計算出所需分床數(shù)量Bedi的上限：

(13)

所需的分床數(shù)量下限：

(14)

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

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

圖2 鋪布層數(shù)粒子搜索流程圖

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

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

圖3 配比粒子搜索流程圖

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

(15)

(16)

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

(17)

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

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

(18)

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

(19)

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

(20)

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

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

3 實驗結果與性能分析

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

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

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

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

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

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

4 結論

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

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

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

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

[4] 師 華, 戴 鴻. 服裝企業(yè)裁剪分床案例分析與探討[J]. 山東紡織經(jīng)濟, 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] 姜 蕾. 服裝生產(chǎn)工藝與設備[M]. 北京：中國紡織出版社, 2004.

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

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

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

[10] 潘 峰. 粒子群優(yōu)化算法與多目標優(yōu)化[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優(yōu)化控制[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īng)網(wǎng)絡語音去噪[J]. 計算機測量與控制, 2013,21(10):2799-2800.