，，

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

0 引言

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

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

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

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

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

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

(1)

約束條件為：

(2)

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

A=Pb×Cnt

(3)

ε=A-D

(4)

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

2 SAPSO算法的設(shè)計(jì)與實(shí)現(xiàn)

2.1 算法選擇

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

2.1.1 PSO算法

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

(5)

(6)

2.1.2 SAPSO算法

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

(7)

(8)

自適應(yīng)加速因子為：

(9)

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

2.2 裁剪分床方案設(shè)計(jì)

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

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

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

2.3 SAPSO算法實(shí)現(xiàn)

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

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

(10)

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

(11)

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

(12)

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

(13)

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

(14)

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

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

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

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

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

圖3 配比粒子搜索流程圖

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

(15)

(16)

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

(17)

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

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

(18)

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

(19)

8)然后計(jì)算所有粒子的適應(yīng)值Fvaluei：

(20)

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

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

3 實(shí)驗(yàn)結(jié)果與性能分析

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

圖4 訂單一兩種方法的分床結(jié)果

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

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

圖5 訂單二兩種方法的分床結(jié)果

圖6 PSO與SAPSO算法適應(yīng)度曲線(實(shí)線—SAPSO，虛線—PSO)

4 結(jié)論

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

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

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

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

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

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

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

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

[10] 潘 峰. 粒子群優(yōu)化算法與多目標(biāo)優(yōu)化[M]. 北京：北京理工大學(xué)出版社, 2013.

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

[12] 程 躍, 程文明, 鄭 嚴(yán). 基于改進(jìn)粒子群算法的中藥提取過(guò)程PID優(yōu)化控制[J]. 計(jì)算機(jī)測(cè)量與控制, 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ìn)粒子群算法的小波神經(jīng)網(wǎng)絡(luò)語(yǔ)音去噪[J]. 計(jì)算機(jī)測(cè)量與控制, 2013,21(10):2799-2800.