改進粒子群算法在二維排樣中的研究與應用

董　輝，陳建軍

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

改進粒子群算法在二維排樣中的研究與應用

董輝，陳建軍

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

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

關鍵詞：小生境；粒子群；混合蛙跳；排樣

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

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

1排樣技術

1.1排樣方法

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

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

1.2樣片的幾何表達

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

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

1.3個體適應度評價

對于排樣問題，本方法取排樣圖的高度的倒數(shù)作為適應度的評價，即適應度函數(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分別為各項的學習因子；r1，r2都是在0到1之間隨機取值；慣性權重w隨迭代次數(shù)線性遞減：w=wmax-wmind/T,wmax，wmin分別為設置的最大值和最小值；xin(d)和vin(d)分別為粒子i當前的位置和速度；xin(d+1)和vin(d+1)分別為粒子i更新后的位置和速度；T為最大迭代次數(shù).

2.2混合蛙跳算法

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

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

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分別為移動距離的最小值和最大值.更新過后，比較新解和舊解的適應度值，如果有改進，則用新解代替舊解，并更新族群內(nèi)xb，xw，xg；如果沒有改進，則用xg代替式(3)中的xb，再次執(zhí)行式(3，4)，如果仍無改進，則隨機用一個新解去代替舊解xw,old.重復執(zhí)行，達到最大迭代次數(shù)時結束.當各個族群的都執(zhí)行完局部搜索，再將所有族群重新混合，并重新劃分族群，各個族群重新執(zhí)行局部搜索，反復迭代，直到滿足條件結束.

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

3.1算法實現(xiàn)

首先在PSO中引入小生境的思想，將粒子初始種群分成Cnum組大小相等的子群(即小生境)，計算種群所有粒子的歐式幾何距離[17]，并按從小到大的順序排列，依序逐一分成Cnum組子群，各子群運用粒子群算法單獨進化，取出各子群進化后的最好粒子，形成新群體，新群體運用混合蛙跳算法進化，進一步尋找最好粒子.混合蛙跳模式的進化，使得各子群最好粒子能有機會進一步更新自己，不僅能提高種群多樣性，而且能進一步尋優(yōu).混合蛙跳算法的引入，增強了全局尋優(yōu)的能力，把它在子群進化后得到的最好粒子反饋到粒子群的速度更新公式中，從而克服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為第四項的學習因子；xb,sfla為蛙跳算法得到的最好粒子.相比于式(1)，式(5)中右邊第三項改為了子群的最優(yōu)解，增加了右邊第4項，蛙跳算法得到的全局最優(yōu)粒子的反饋.新公式保留了粒子個體的自身速度、歷史最優(yōu)位置的影響，變化為各子群局部最優(yōu)粒子的作用，加入了全局最優(yōu)粒子的反饋，使得局部和全局的信息得到充分的交流，能有力的跳出局部最優(yōu)解，使全局尋優(yōu)的能力進一步提升.

3.2算法流程

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

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

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

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

4) 使用BL算法進行排樣，計算粒子適應度值F.

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

6) 將各組的全局最優(yōu)解gin組成蛙群，計算適應度值并進行排序分族，分為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í)行結束；否則轉到步驟3)繼續(xù)執(zhí)行.

4實驗結果及分析

實驗環(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算法進行實驗結果比較，對NPSO-SFLA算法的性能進行測試，兩者采用一樣的參數(shù)設置.算法參數(shù)設置如下：最大迭代次數(shù)為500次，慣性因子wmax，wmin分別設為0.9，0.5，學習因子c1，c2，c3都取值為2，種群大小為30個粒子，NPSO-SFLA算法分6個子群，每個子群由5個粒子組成，蛙跳分為2組，每組3個粒子，蛙跳族內(nèi)迭代10次，樣片的旋轉角度以90度為基本單位.同樣環(huán)境下，兩種算法各自運行100次，兩者的結果對比如表1所示.

表1　PSO與NPSO-SFLA的實驗結果對比

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

圖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結論

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

參考文獻：

[1]童科.群智能算法的研究與應用——基于求解矩形優(yōu)化排樣問題[D]. 無錫：江南大學，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]韓冬梅，王麗萍，吳秋花.基于模糊偏好的多目標粒子群算法在庫存控制中的應用[J].浙江工業(yè)大學學報，2012，40(3)：348-351.

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

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

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

[8]段富，蘇同芬.免疫粒子群算法的改進及應用[J].計算機應用，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)化算法及其在分類器集成中的應用研究[D].合肥：中國科學技術大學，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].計算機輔助設計與圖形學學報，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]董輝，黃勝.二維排樣中小生境粒子群算法的研究與應用[J].浙江工業(yè)大學學報，2014，42(3)：257-268.

(責任編輯：陳石平)

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)技術及應用，E-mail：hdong@zjut.edu.cn.

中圖分類號：TP391

文獻標志碼：A

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