，

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

排樣是指將多片不規(guī)則形狀的零件在某個(gè)規(guī)定大小的區(qū)域中按最佳的方式進(jìn)行排放的過(guò)程，并要求各個(gè)零件互不重疊.排樣在造船、布匹和皮革加工業(yè)中有著廣泛應(yīng)用.排樣效率的微小提升可帶來(lái)巨大的經(jīng)濟(jì)效益[1].

粒子群算法(PSO,全名Particle swarm optimization)是一個(gè)在連續(xù)的定義域內(nèi)搜索函數(shù)極值的有效方法[2].PSO算法具有操作簡(jiǎn)單、收斂速度快的特點(diǎn)，但也容易陷入局部極值，搜索結(jié)果不夠理想.因此許多學(xué)者提出改進(jìn)型的PSO算法[3-4].小生境技術(shù)起源于遺傳算法，這種方法能使基于群體的隨機(jī)優(yōu)化算法形成物種，從而使相應(yīng)的優(yōu)化算法具有發(fā)現(xiàn)多個(gè)最優(yōu)解的能力[5].針對(duì)排樣問(wèn)題，提出了一種基于小生境的粒子群算法，利用其保持物種進(jìn)化過(guò)程中的多樣性的特點(diǎn)彌補(bǔ)了粒子群算法容易陷入局部最優(yōu)的缺陷，一定程度上改善了搜索效果，在實(shí)際排樣中提高了材料利用率.

1 零件輪廓預(yù)處理與排樣過(guò)程

1.1 零件輪廓預(yù)處理

由于二維不規(guī)則零件的輪廓的復(fù)雜性，可以通過(guò)將零件的不規(guī)則輪廓轉(zhuǎn)化為一系列坐標(biāo)區(qū)間從而脫離不規(guī)則幾何輪廓的復(fù)雜性進(jìn)行排樣預(yù)處理[6].不規(guī)則零件的離散化幾何表達(dá)即圖形的掃描轉(zhuǎn)換方法，其思想是:用等間距的水平掃描線與不規(guī)則多邊形相交，從而得到由交點(diǎn)坐標(biāo)組成的多邊形幾何輪廓上的水平線段區(qū)間，因此可以把不規(guī)則多邊形看作是由一系列的水平線段區(qū)間構(gòu)成[7]，如圖1所示.此處確定水平線間距為1 mm，即精度為1 mm.

圖1 幾何離散化

預(yù)處理基本步驟如下：

1) 將輪廓各點(diǎn)按順序依次排列，形成封閉區(qū)間(如圖1中順序：a-b,b-c,c-d,d-e,e-f,f-g,g-h,h-i,i-a).

2) 對(duì)各區(qū)間線段離散化，記錄離散化后各點(diǎn)的二維坐標(biāo)(x，y)，輪廓線段交點(diǎn)記兩次.

3) 遍歷輪廓最低點(diǎn)至最高點(diǎn)的所有水平線，從最左端沿水平線向右查找，第2n-1個(gè)點(diǎn)為區(qū)間線段起點(diǎn)，第2n個(gè)點(diǎn)為區(qū)間線段終點(diǎn)(n=1,2,3,…)，如圖1中區(qū)間m-n，o-p,q-r.

1.2 基本排樣過(guò)程

采用文獻(xiàn)[8]提出的BL(Bottom left)算法進(jìn)行零件的底層排樣.

BL算法的基本思想：零件先從材料的左下角排入，后面的零件往右依次排入，當(dāng)零件超出材料的右側(cè)時(shí)，將零件相對(duì)于材料上移，并從左邊開(kāi)始重新搜索材料的剩余空間，如此循環(huán)往復(fù)，直至樣片全部排入或樣片溢出材料頂部時(shí)停止，即排樣高度記為H.

2 基于小生境的粒子群算法

在粒子群算法中，所有材料樣片的某個(gè)狀態(tài)的集合被視為一個(gè)個(gè)體(粒子)，狀態(tài)包括三種：排入次序(order,1—n，n為樣片總數(shù))、旋轉(zhuǎn)角度(angle，0°～360°)、鏡像(mirror，關(guān)于y軸對(duì)稱，0～1).那么某片材料的位置、速度信息可分別表示為x=,v=.記某個(gè)粒子的適應(yīng)度值F=1/H.

2.1 經(jīng)典PSO算法

假定種群粒子個(gè)數(shù)為R，材料樣片數(shù)位N，那么粒子數(shù)第i個(gè)粒子的位置可記為Xi=，速度則記為Vi=，粒子的歷史最佳位置記為Bi=，整個(gè)粒子群的歷史最佳位置記為Gbest=.對(duì)于第i的底n塊材料，其速度、位置的更新公式為

(1)

式中：d為迭代次數(shù)；c1，c2分別為學(xué)習(xí)因子；rand1，rand2分別為0～1之間的隨機(jī)數(shù)；慣性權(quán)值w(d)隨迭代次數(shù)線性遞減：w(d)=wmax-wmin·d/D,其中wmax，wmin分別為最大和最小設(shè)定值，D為最大迭代次數(shù).

2.2 基于小生境的粒子群算法

2.2.1 小生境思想的引入

在經(jīng)典PSO的基礎(chǔ)上引入小生境的思想，假定初始種群粒子個(gè)數(shù)R=P·Q，P和Q均為正整數(shù)，將初始種群均分為P個(gè)子群(即小生境)，通過(guò)計(jì)算每個(gè)粒子的歐式幾何距離，將粒子按歐式幾何距離從小到大的順序排列，依次取出粒子，每Q個(gè)組成一個(gè)子群.

因此，相比于經(jīng)典PSO算法，新算法需增加變量：子群的歷史最佳位置，記為GSp=(p為子群序號(hào)，P>p>0).此變量的作用類似于整個(gè)粒子群的歷史最佳位置記為Gbest，作為粒子飛行的一個(gè)參考因素.

若在式(1)中將Gbest項(xiàng)完全由Bsj替代，那么屬于不同子群的粒子趨向性會(huì)有所不同，從而避免整個(gè)種群趨向于同一目標(biāo)以致種群過(guò)早收斂、陷入局部極值的問(wèn)題；但同時(shí)種群的收斂速度將變慢，時(shí)間效率大大降低.考慮上述問(wèn)題，本方法提出的新算法將式(1)改造為

(2)

(3)

式中:p為子群序號(hào)；q為子群中某粒子的序號(hào).因此，p·Q+q等效于式(1)中的i，下標(biāo)pqn等效于式(1)中的in.根據(jù)式(3)易得：當(dāng)d>2D/3或d為偶數(shù)時(shí)，式(2)等同于式(1)；否則式(1)中的種群歷史最佳位置項(xiàng)gi(d)變?yōu)樽尤簹v史最佳位置gspn(d).

由上所述可知：新的算法在前2D/3的迭代次數(shù)內(nèi)時(shí)，趨向種群歷史最佳位置與趨向子群歷史最佳位置的操作交叉進(jìn)行，這使得粒子能夠在更大范圍內(nèi)，搜索更優(yōu)解，且此操作可在一定程度上防止粒子的進(jìn)化停滯(粒子信息保持不變).同時(shí)，由于種群最優(yōu)解的作用，算法的收斂作用也不至于被減弱許多.在迭代的后期(后D/3)，我們認(rèn)為，算法已接近全局極值點(diǎn)，因此進(jìn)行全速搜索，即不再考慮子群最優(yōu)解的影響，在種群最優(yōu)解的周圍進(jìn)行細(xì)致搜索，以期得到更優(yōu)解.

2.2.2 加入小生境的重置機(jī)制

針對(duì)PSO算法容易陷入局部最優(yōu)解的問(wèn)題，新算法中加入了子群的淘汰與重置機(jī)制，當(dāng)某個(gè)子群在連續(xù)n次迭代過(guò)程中都未找到更優(yōu)解時(shí)，那么，認(rèn)為該子群陷入了局部極值解，此時(shí)通過(guò)對(duì)子群的隨機(jī)重置，可使該子群有機(jī)會(huì)跳出局部極值解，從而進(jìn)一步增強(qiáng)了算法的全局搜索能力.

2.2.3 算法流程

基于小生境的粒子群算法(NPSO)流程如下：

1) 隨機(jī)初始化整個(gè)粒子群的初始位置與速度.

2) 根據(jù)粒子的歐式幾何距離將種群分成多個(gè)子群.

3) 使用公式(2)更新每個(gè)粒子的速度與位置.

4) 根據(jù)粒子位置使用BL算法進(jìn)行排樣，計(jì)算適應(yīng)度值F=1/排樣高度.

5) 根據(jù)F的值更新粒子，子群以及整個(gè)種群的當(dāng)前最優(yōu)解.

6) 判斷子群在連續(xù)n代內(nèi)的最優(yōu)解是否有更新，若有，則跳到步驟8)；否則執(zhí)行步驟7).

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

8) 迭代次數(shù)n=n+1，判斷n是否為最大迭代次數(shù)，如是，則跳出迭代過(guò)程，執(zhí)行結(jié)束；否則轉(zhuǎn)到步驟3)繼續(xù)執(zhí)行.

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

仿真環(huán)境：硬件配置為Core 2雙核，主頻2.93 GHz，內(nèi)存為1.96 GB；軟件配置為Windows XP系統(tǒng)，VC 2008軟件開(kāi)發(fā)平臺(tái).

本方法以22塊不規(guī)則服裝樣片作為測(cè)試對(duì)象，采用寬1 200 mm,長(zhǎng)度沒(méi)有限制的長(zhǎng)方形作為排樣底板.為了測(cè)試算法的性能，使用新提出的NPSO算法與標(biāo)準(zhǔn)PSO算法[9]分別進(jìn)行排樣，取相同的實(shí)驗(yàn)參數(shù)，兩種算法的最大迭代次數(shù)為500次，慣性因子w(d)=0.9-0.5d/500，種群的粒子個(gè)數(shù)為30，NPSO算法分5個(gè)子群，每個(gè)子群擁有6個(gè)粒子.本實(shí)驗(yàn)中樣片的旋轉(zhuǎn)角度以90°為基本單位.兩種算法的排樣過(guò)程各重復(fù)30次，實(shí)驗(yàn)結(jié)果如表1所示.

表1 實(shí)驗(yàn)數(shù)據(jù)對(duì)照表

從表1可知：兩種算法在運(yùn)行時(shí)間和標(biāo)準(zhǔn)偏差上幾乎相同；但從排樣高度來(lái)看，NPSO要大大好于PSO.

圖2給出了兩種算法的最佳排樣方案的效果圖.對(duì)比圖2(a，b)可看出：使用新提出的NPSO算法比PSO算法排列的更緊湊，效果更優(yōu).

圖2 兩種算法最佳排樣效果圖

4 結(jié)束語(yǔ)

粒子群算法思路簡(jiǎn)單，易于實(shí)現(xiàn)，通過(guò)對(duì)兩種粒子群算法步驟的介紹和仿真實(shí)例的數(shù)據(jù)結(jié)果分析，新提出的基于小生境的粒子群算法的性能明顯好于未經(jīng)過(guò)改良的粒子群算法，前者在未改變時(shí)間復(fù)雜度的前提下，其全局搜索能力比后者有較大提升，彌補(bǔ)了粒子群算法的最大不足.通過(guò)上述仿真可知：將基于小生境的粒子群算法應(yīng)用到解決二維不規(guī)則排樣的問(wèn)題中是可行的，而且它在實(shí)際應(yīng)用中，可以有效提高材料利用率.

參考文獻(xiàn)：

[1] 劉虓，葉家瑋，胡金鵬．基于最小使能原理的不規(guī)則零件排樣算法[J]．華南理工大學(xué)學(xué)報(bào)，2011，39(8)：26-41．

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

[3] 盛煜翔，潘海天，夏陸岳，等．混合混沌粒子群算法在苯與甲苯閃蒸過(guò)程優(yōu)化中的應(yīng)用[J]．浙江工業(yè)大學(xué)學(xué)報(bào)，2010，38(3)：318-321．

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

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

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

[7] 黃建江．智能數(shù)控裁床的研究與開(kāi)發(fā)——二維不規(guī)則零件排樣算法的設(shè)計(jì)與應(yīng)用[D]．無(wú)錫：江南大學(xué)，2007．

[8] STEFAN J. On genetic algorithms for the packing of polygons[J]．European Journal of Operational Research,1996,88:165-181．

[9] SHI Yu-hui, EBERHART R C.A modified particle swarm optimizer[C]//Proc IEEE World Congress on Computational Intelligence. New York: IEEE Press,1998:69-73．