董　輝，陳建軍

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

改進(jìn)粒子群算法在二維排樣中的研究與應(yīng)用

董輝，陳建軍

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

摘要：針對服裝行業(yè)二維不規(guī)則樣片優(yōu)化排樣問題，提出了一種改進(jìn)的粒子群優(yōu)化排樣方法.該算法在傳統(tǒng)的粒子群優(yōu)化算法中先引入小生境的思想，將種群劃分成多個子群，各子群運用粒子群算法單獨進(jìn)化，取出各子群進(jìn)化后的最好粒子，又可形成新群體，新群體運用混合蛙跳算法進(jìn)化，使子群的最好粒子進(jìn)一步更新，種群的多樣性進(jìn)一步增強，全局尋優(yōu)的能力進(jìn)一步提升.該算法概念簡單，易于實現(xiàn)，具有較好的能力去搜索全局最優(yōu)解和較快的收斂速度.實驗結(jié)果表明該算法是有效的.

關(guān)鍵詞：小生境；粒子群；混合蛙跳；排樣

服裝行業(yè)二維不規(guī)則樣片的優(yōu)化排樣問題就是在指定大小區(qū)域的材料上，尋找一種將很多不規(guī)則形狀的樣片最優(yōu)的排布方案，所有樣片排放位置都互不重疊，樣片排放組合緊湊、密集，剩余有效材料越多，材料利用率就越高，排樣方案則越優(yōu).二維不規(guī)則件優(yōu)化排樣問題在服裝制造行業(yè)中長期存在，也頻繁的出現(xiàn)在如機器人、金屬、玻璃、木材和船舶等行業(yè)中.由于服裝總是大批量的生產(chǎn)，特別是服裝材料成本價格越來越高，提高一點點材料利用率就可以節(jié)省大量材料，產(chǎn)生龐大的經(jīng)濟(jì)價值，具有長遠(yuǎn)的現(xiàn)實意義[1].粒子群算法(Particle swarm optimization，PSO)簡單易實現(xiàn)，它所具備得參數(shù)個數(shù)少、收斂速度快等優(yōu)點，使得它頻繁的應(yīng)用于模糊系統(tǒng)控制、組合優(yōu)化、復(fù)雜函數(shù)求解及機器人路徑規(guī)劃等相關(guān)領(lǐng)域.可是，粒子群算法同樣也存在不少問題，如對解的搜索精度不高；容易過早收斂和對參數(shù)值的影響大.為了解決這些問題，很多學(xué)者改進(jìn)了經(jīng)典的PSO方法.有些是對粒子群的一些依賴參數(shù)做出優(yōu)化[2-5]，如對慣性權(quán)重w和學(xué)習(xí)因子c1，c2進(jìn)行調(diào)節(jié)[6]；還有引入其他算法的思想和粒子群算法相融合[7-9]，比如量子粒子群融合算法[7]、免疫粒子群融合算法[8]及遺傳粒子群融合算法[9]等.這些改進(jìn)的PSO算法雖然具有一定的效果，但使算法概念更加復(fù)雜，實現(xiàn)困然，而且仍然克服不了在求解優(yōu)化排樣問題時搜索精度不高和易陷入局部最優(yōu)解的缺陷.為此提出了一種改進(jìn)的粒子群優(yōu)化算法——基于小生境粒子群和混合蛙跳的融合算法(NPSO-SFLA).

新算法中，在傳統(tǒng)的粒子群優(yōu)化算法中先引入小生境[10]的思想，為了解決粒子群算法容易過早收斂、陷入局部最優(yōu)的問題，將種群劃分成多個子群，各子群運用粒子群算法單獨進(jìn)化，使種群多樣性增多以避免局部最優(yōu).然后，取出各子群進(jìn)化后的最好粒子，又可形成新群體，新群體運用混合蛙跳算法進(jìn)化，使子群的最好粒子進(jìn)一步更新，種群的多樣性進(jìn)一步增強，全局尋優(yōu)的能力進(jìn)一步提升.兩種算法的結(jié)合相得益彰，有效的解決粒子群算法容易陷入局部最優(yōu)和混合蛙跳算法收斂速度慢也易陷入局部最優(yōu)的問題.排樣實例表明了該方法的有效性.

1排樣技術(shù)

1.1排樣方法

提出了一種改進(jìn)的粒子群算法來搜索最佳的排樣組合，采用文獻(xiàn)[11-12]提出的BL(Bottom left)算法進(jìn)行樣片的底層排樣.

BL算法基本排樣策略：每一個待排樣片都先放置在材料的右上角，以材料的右上角為基準(zhǔn)點向材料的左下角移動，最初一直向下移動樣片，然后一直向左移動樣片，直到待排樣片向下或向左都不能移動時停止即兩個方向都接觸到其它已排樣片或材料邊界，記錄下當(dāng)前的排樣高度；重復(fù)以上過程，當(dāng)所有的待排樣片都排入時停止，最后所得的最大高度即排樣高度記為H.

1.2樣片的幾何表達(dá)

樣片的幾何形狀同排樣的利用率密切相關(guān)，由于服裝行業(yè)的樣片形狀各異而且復(fù)雜，若將此樣片直接作為排樣對象，會使排樣問題更加復(fù)雜，從而直接影響排樣的效果.通常將不規(guī)則件排樣近似為矩形件來處理，但是未能充分考慮二維不規(guī)則樣片形狀的各異，導(dǎo)致不能充分的利用材料.本方法采用文獻(xiàn)[13]提出的一種離散的幾何處理方法，能夠完全克服二維不規(guī)則樣片形狀高度復(fù)雜性的影響，簡化排樣復(fù)雜度從而得到更好的排樣效果.二維不規(guī)則樣片和指定大小的材料區(qū)間可以看成由很多坐標(biāo)形成的直線區(qū)域所組成，所以就可以將它們的幾何區(qū)域轉(zhuǎn)化為一系列坐標(biāo)區(qū)間，從而簡化排樣的復(fù)雜度.

基本思想：每個待排樣片所形成的輪廓都是一個不規(guī)則的多邊形，從該多邊形的最低點開始，以某種等距離的水平線去掃描該多邊形，水平線與多邊形會形成兩個或兩個以上的交點(頂點時記為兩個)，記錄下這些交點，一直向上掃描，直到該多邊形的最高點結(jié)束.這些交點按大小順序排列，同一水平線上的點兩兩可組成很多線段區(qū)間，所有水平線段區(qū)間所形成的區(qū)域可看作該樣片的區(qū)域，掃描距離越小，所形成的離散的幾何區(qū)間精度越高.此處掃描距離取1 mm，即精度值為1 mm.

1.3個體適應(yīng)度評價

對于排樣問題，本方法取排樣圖的高度的倒數(shù)作為適應(yīng)度的評價，即適應(yīng)度函數(shù)為F=1/H，其中H是排樣圖的高度，故H越小，F(xiàn)越大，排樣效率越佳.

2粒子群算法和蛙跳算法

2.1經(jīng)典粒子群算法

PSO算法是1995年由Eberhart和Kennedy[14]提出的一種種群優(yōu)化算法，該算法可描述如下：D維的搜索空間(即D個待排樣片)，種群的大小N(即粒子個數(shù))，種群中第i個粒子的位置xi=，速度vi=，某個粒子的迄今最好位置pi=，目前整個種群的最好位置gbest=.每個粒子速度、位置的更新公式為

vin(d+1)=w×vin(d)+c1×r1×[pin-xin(d)]+

c2×r2×[gn-xin(d)]

(1)

xin(d+1)=xin(d)+vin(d+1)

(2)

式中：i=(1,2,…,N)；n=(1,2,…,D)；d為迭代次數(shù)；c1，c2分別為各項的學(xué)習(xí)因子；r1，r2都是在0到1之間隨機取值；慣性權(quán)重w隨迭代次數(shù)線性遞減：w=wmax-wmind/T,wmax，wmin分別為設(shè)置的最大值和最小值；xin(d)和vin(d)分別為粒子i當(dāng)前的位置和速度；xin(d+1)和vin(d+1)分別為粒子i更新后的位置和速度；T為最大迭代次數(shù).

2.2混合蛙跳算法

混合蛙跳算法(SFLA)是2003年由Eusuff和Lanset[15]提出的一種群體進(jìn)化算法.其基本思想為：青蛙群體被劃分為若干個子群，各子群以自己的意識各自單獨進(jìn)化，此時種群進(jìn)化基于各子群的局部搜索，當(dāng)子群達(dá)到迭代次數(shù)以后，各子群再進(jìn)行混合運算以達(dá)到進(jìn)行全局交流的目的，這個過程一直進(jìn)行，直至達(dá)到退出條件，則停止.各子群先局部搜索，再全局混合信息交流的策略能夠有效地跳出局部極值，去尋找到全局最優(yōu).

該算法數(shù)學(xué)模型可描述如下：D維搜索空間中，初始群體P只青蛙，P只青蛙表示有P個解，則第i個解xi=，將青蛙分成M個族群，N只青蛙為一個族群，即P=M·N.族群的分類方法[16]：計算所有青蛙即P個解的適應(yīng)度值，將P個適應(yīng)度值進(jìn)行升序或降序，將排序后的青蛙(P個解)按順序分配給M個族群，分配N次后分配完畢.xb和xw分別表示當(dāng)前族群中適應(yīng)度最好和最差的解，xg表示整個群體適應(yīng)度最好的解，對族群中適應(yīng)度最差的解xw迭代進(jìn)化如下：

dj=r×(xb-xw)

(3)

xw,new=xw,old+dj(dmin≤dj≤dmax)

(4)

式中：dj為最差青蛙在第i維移動的距離；r在0到1之間隨機取值；xw,new和xw,old分別為族群中最差解的新值和舊值；dmin和dmax分別為移動距離的最小值和最大值.更新過后，比較新解和舊解的適應(yīng)度值，如果有改進(jìn)，則用新解代替舊解，并更新族群內(nèi)xb，xw，xg；如果沒有改進(jìn)，則用xg代替式(3)中的xb，再次執(zhí)行式(3，4)，如果仍無改進(jìn)，則隨機用一個新解去代替舊解xw,old.重復(fù)執(zhí)行，達(dá)到最大迭代次數(shù)時結(jié)束.當(dāng)各個族群的都執(zhí)行完局部搜索，再將所有族群重新混合，并重新劃分族群，各個族群重新執(zhí)行局部搜索，反復(fù)迭代，直到滿足條件結(jié)束.

3改進(jìn)粒子群算法(NPSO-SFLA)

3.1算法實現(xiàn)

首先在PSO中引入小生境的思想，將粒子初始種群分成Cnum組大小相等的子群(即小生境)，計算種群所有粒子的歐式幾何距離[17]，并按從小到大的順序排列，依序逐一分成Cnum組子群，各子群運用粒子群算法單獨進(jìn)化，取出各子群進(jìn)化后的最好粒子，形成新群體，新群體運用混合蛙跳算法進(jìn)化，進(jìn)一步尋找最好粒子.混合蛙跳模式的進(jìn)化，使得各子群最好粒子能有機會進(jìn)一步更新自己，不僅能提高種群多樣性，而且能進(jìn)一步尋優(yōu).混合蛙跳算法的引入，增強了全局尋優(yōu)的能力，把它在子群進(jìn)化后得到的最好粒子反饋到粒子群的速度更新公式中，從而克服PSO容易過早收斂、陷入局部最優(yōu)的問題.

新算法的速度和位置更新公式分別為

vin(d+1)=w×vin(d)+c1×r1×[pin-xin(d)]+

c2×r2[gin-xin(d)]+c3×

r3[xb,sfla-xin(d)]

(5)

xin(d+1)=xin(d)+vin(d+1)

(6)

式中：gin為粒子群第i組的全局最優(yōu)值；r3為0～1之間的隨機數(shù)；c3為第四項的學(xué)習(xí)因子；xb,sfla為蛙跳算法得到的最好粒子.相比于式(1)，式(5)中右邊第三項改為了子群的最優(yōu)解，增加了右邊第4項，蛙跳算法得到的全局最優(yōu)粒子的反饋.新公式保留了粒子個體的自身速度、歷史最優(yōu)位置的影響，變化為各子群局部最優(yōu)粒子的作用，加入了全局最優(yōu)粒子的反饋，使得局部和全局的信息得到充分的交流，能有力的跳出局部最優(yōu)解，使全局尋優(yōu)的能力進(jìn)一步提升.

3.2算法流程

改進(jìn)粒子群算法(NPSO-SFLA)具體流程如下：

1) 初始化整個粒子群的初始位置與速度，設(shè)置相關(guān)參數(shù).

2) 根據(jù)粒子的歐式幾何距離將粒子分成Cnum組，每組P個粒子.

3) 使用式(5，6)更新每個粒子的速度與位置.

4) 使用BL算法進(jìn)行排樣，計算粒子適應(yīng)度值F.

5) 根據(jù)F更新粒子的個體最優(yōu)解pin，各組的全局最優(yōu)解gin.

6) 將各組的全局最優(yōu)解gin組成蛙群，計算適應(yīng)度值并進(jìn)行排序分族，分為M族，每族N個.

7) 蛙群按照式(3，4)更新粒子，找出最優(yōu)解xb,sfla.

8) 比較子群在連續(xù)n代內(nèi)的最優(yōu)解是否有更好，若有，則跳到步驟10)；否則執(zhí)行步驟9).

9) 重置該子群的位置與速度.

10) 迭代次數(shù)n=n+1，若n等于最大迭代次數(shù)T，則執(zhí)行結(jié)束；否則轉(zhuǎn)到步驟3)繼續(xù)執(zhí)行.

4實驗結(jié)果及分析

實驗環(huán)境：硬件配置為Intel酷睿i3 370 M，主頻2.40 GHz，內(nèi)存為5 GB；軟件配置為Windows7 64位操作系統(tǒng)，VC 2008軟件開發(fā)平臺.本方法選擇了一個寬1 200 mm，長度不限的矩形材料作為排樣的底板，排放20個任意形狀的服裝樣片.采取與經(jīng)典PSO算法進(jìn)行實驗結(jié)果比較，對NPSO-SFLA算法的性能進(jìn)行測試，兩者采用一樣的參數(shù)設(shè)置.算法參數(shù)設(shè)置如下：最大迭代次數(shù)為500次，慣性因子wmax，wmin分別設(shè)為0.9，0.5，學(xué)習(xí)因子c1，c2，c3都取值為2，種群大小為30個粒子，NPSO-SFLA算法分6個子群，每個子群由5個粒子組成，蛙跳分為2組，每組3個粒子，蛙跳族內(nèi)迭代10次，樣片的旋轉(zhuǎn)角度以90度為基本單位.同樣環(huán)境下，兩種算法各自運行100次，兩者的結(jié)果對比如表1所示.

表1　PSO與NPSO-SFLA的實驗結(jié)果對比

表1中，比較兩者平均排樣高度可得出NPSO-SFLA收斂精度更優(yōu)；新算法的H標(biāo)準(zhǔn)偏差也較小，說明NPSO-SFLA算法的穩(wěn)定性好，新算法的平均收斂代數(shù)較低，說明NPSO-SFLA算法的收斂速度更快；比較平均收斂代數(shù)和標(biāo)準(zhǔn)偏差可得出NPSO-SFLA具有更強的全局搜索能力；從兩者的最差和最好排樣高度比較可知新提出的NPSO-SFLA都明顯要優(yōu)于PSO；比較兩者的排樣時間，NPSO-SFLA的耗時比經(jīng)典的PSO多，這是由于加入蛙跳的進(jìn)化而增加的運行時間.

圖1(a)中，NPSO-SFLA排樣高度為947 mm，圖1(b)中，PSO排樣高度為955 mm，新算法排樣效果更好，材料利用率更高.圖2中，NPSO-SFLA在380代收斂于排樣高度947 mm，PSO在421代收斂于排樣高度955 mm，新算法更快的找到最優(yōu)解，從表1中兩中算法的平均收斂代數(shù)比較可知：新算法收斂更快，體現(xiàn)出NPSO-SFLA更佳的收斂性能.

圖1　兩種排樣算法最佳效果圖Fig.1　The best layout chart by two algorithm

圖2　兩種排樣算法收斂性能比較Fig.2　Convergence performance comparison by two algorithms

5結(jié)論

新提出的NPSO-SFLA算法概念簡單，易于實現(xiàn)，粒子群算法與蛙跳算法的結(jié)合，取長補短，具有較強的搜索最優(yōu)解的能力.實驗結(jié)果顯示新算法的排樣高度明顯優(yōu)于標(biāo)準(zhǔn)的PSO算法，實驗數(shù)據(jù)分析得出NPSO-SFLA具有較好的搜索全局最優(yōu)解的能力和較快的收斂速度.結(jié)果表明：新提出的改進(jìn)粒子群算法能有效解決服裝行業(yè)的二維不規(guī)則樣片排樣問題，該算法能夠有效地提高材料的利用率，給服裝行業(yè)的二維不規(guī)則件優(yōu)化排樣問題帶來新的解決方案.

參考文獻(xiàn)：

[1]童科.群智能算法的研究與應(yīng)用——基于求解矩形優(yōu)化排樣問題[D]. 無錫：江南大學(xué)，2011.

[2]ZHANG Y N, TENG H F. Detecting particle swarm optimization[J]. Concurrency and computation practice and experience，2009，21(4)：449-473.

[3]SOUDAN B, SAAD M. An evolutionary dynamic population size PSO implementation[C]//3rd Information and Communication Technologies: From Theory to Applications. Damascus: IEEE，2008:1-5.

[4]韓冬梅，王麗萍，吳秋花.基于模糊偏好的多目標(biāo)粒子群算法在庫存控制中的應(yīng)用[J].浙江工業(yè)大學(xué)學(xué)報，2012，40(3)：348-351.

[5]黃太安，生佳根，徐紅洋，等.一種改進(jìn)的簡化粒子群算法[J].計算機仿真，2013，30(2)：327-330，335.

[6]韓毅，蔡建湖，周根貴，等.線型結(jié)構(gòu)批量計劃問題的粒子群算法參數(shù)方案設(shè)定[J].浙江工業(yè)大學(xué)學(xué)報，2010，38(6)：683-692.

[7]黃建江，須文波，孫俊，等.量子行為粒子群優(yōu)化算法的布局問題研究[J].計算機應(yīng)用，2006，26(12)：3015-3018.

[8]段富，蘇同芬.免疫粒子群算法的改進(jìn)及應(yīng)用[J].計算機應(yīng)用，2010，30(7)：1883-1884，1888.

[9]SETTLES M, SOULE T. Breeding swarms: a GA /PSO hybrid[C]//GECCO 2005-Genetic and Evolutionary Computation Conference. Washington: Assoc Computing Machinery，2005：161-168.

[10]章軍.小生境粒子群優(yōu)化算法及其在分類器集成中的應(yīng)用研究[D].合肥：中國科學(xué)技術(shù)大學(xué)，2007.

[11]SHI Yuhui, EBERHART R C. A modified particle swarm optimizer[C]//Proc IEEE World Congress on Computational Intelligence. Piscataway: IEEE Press，1998：69-73.

[12]CHAZELLE B. The bottom-left bin-packing heuristic: an efficient implementation[J]. IEEE transactions on computers，1983，32(8)：697-707.

[13]陳勇，唐敏，童若鋒，等.基于遺傳模擬退火算法的不規(guī)則多邊形排樣[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2003，15(5)：598-603.

[14]KENNEDY J, EBERHART R C. Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks. Piscataway: IEEE，1995：1942-1948.

[15]EUSUFF M M, LANSEY K E. Optimization of water distribution network design using shuffled frog leaping algorithm[J]. Journal of water resources planning and management，2003，129 (3)：210-225.

[16]李俊，孫輝，史小露.多種群粒子群算法與混合蛙跳算法融合的研究[J].小型微型計算機系統(tǒng)，2013，34(9)：2164-2168.

[17]董輝，黃勝.二維排樣中小生境粒子群算法的研究與應(yīng)用[J].浙江工業(yè)大學(xué)學(xué)報，2014，42(3)：257-268.

(責(zé)任編輯：陳石平)

Research and application of an improved particle swarm algorithm in two-dimensional layout

DONG Hui, CHEN Jianjun

(College of Information Engineering, Zhejiang University of Technology, Hangzhou 310023, China)

Abstract:An improved particle swarm algorithm is proposed to solve the optimization of two-dimensional irregular layout problem in the garment industry. In this algorithm, the niche technology is introduced to the traditional particle swarm optimization algorithm while the population is divided into multiple sub-swarms and each sub-swarm is evolved by particle swarm algorithm independently. Then the best particles in the sub-swarms are reformed into a new group and the new group can be evolved by shuffled frog leaping algorithm. This algorithm can update the best particles of sub-swarms, enhance the diversity of the population and promote the global optimization capability further. The algorithm is simple in concept and is easy to be implemented. It has better ability to search the global optimal solution and faster convergence speed. Experimental results show that the algorithm is effective.

Keywords:niche; particle swarm; shuffled frog leaping algorithm; nesting

收稿日期：2015-12-15

作者簡介：董輝(1979—)，男，浙江永康人，副教授，研究方向為嵌入式系統(tǒng)技術(shù)及應(yīng)用，E-mail：hdong@zjut.edu.cn.

中圖分類號：TP391

文獻(xiàn)標(biāo)志碼：A

文章編號：1006-4303(2016)04-0388-04