，

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

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

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

1 零件輪廓預處理與排樣過程

1.1 零件輪廓預處理

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

圖1 幾何離散化

預處理基本步驟如下：

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

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

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

1.2 基本排樣過程

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

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

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

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

2.1 經典PSO算法

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

(1)

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

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

2.2.1 小生境思想的引入

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

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

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

(2)

(3)

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

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

2.2.2 加入小生境的重置機制

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

2.2.3 算法流程

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

1) 隨機初始化整個粒子群的初始位置與速度.

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

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

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

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

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

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

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

3 仿真實驗與結果分析

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

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

表1 實驗數(shù)據(jù)對照表

從表1可知：兩種算法在運行時間和標準偏差上幾乎相同；但從排樣高度來看，NPSO要大大好于PSO.

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

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

4 結束語

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

參考文獻：

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

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

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

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

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

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

[7] 黃建江．智能數(shù)控裁床的研究與開發(fā)——二維不規(guī)則零件排樣算法的設計與應用[D]．無錫：江南大學，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．