基于改進粒子群算法的船舶排樣問題研究

杜浩楠，黃澤峰，袁 雁，黃泰安

(1.江蘇科技大學南徐學院，江蘇 鎮江 212003;2.江蘇科技大學計算機科學與工程學院，江蘇 鎮江 212003)

0 引言

在船舶行業逐漸蕭條的形勢下，最大限度的降低生產成本是提高船廠效益的有力途徑。造船材料占據了生產成本的很大部分，因此提高船舶板材的利用率是關鍵。然而，船舶零件多為不規則形狀，給計算機自動排樣程序的實現增加了困難。一些學者就通過矩形包絡的方法，將不規則圖形排樣轉化為矩形件排樣，這樣更利于問題的解決。矩形件排樣問題在理論上屬于具有最高復雜性的NP完全問題，隨著矩形零件的增多，很難用傳統算法得到最優解。因此，不管是從理論研究還是從實際應用上講，對二維矩形件排樣問題的研究都具有重要的意義。

粒子群優化算法［1］(Particle Swarm Optimization，簡稱PSO)是由Kennedy和 Eberhart首先提出的一種全局隨機搜索算法。它模擬鳥群覓食過程中的遷徙和群聚行為，利用群體智能搜索出較好的解。該算法有著收斂速度快、設置參數少、算法簡單易實現等優點，所以一經提出就受到了學術界的廣泛重視，并被廣泛應用于函數優化、模式分類、模糊系統控制、神經網絡訓練以及其他工程領域中［2，3］。因此近年來許多國內外學者研究粒子群算法，并提出了很多改進的算法［4～8］。

要使矩形件優化排樣獲得更好的效果，可考慮從2方面入手:一是用更好的方法確定矩形件排放的先后順序和排放方式，二是設計出更好的矩形件排放算法［9］。國內外不少學者已經做了很多研究工作，提出了一些近似算法和啟發式算法［10～13］。本文從第一方面入手，應用改進的粒子群算法——蛙跳簡化粒子群算法進行矩形件優化排樣。排樣實例表明了該方法的有效性。

1 剩余矩形法簡介

對于矩形件排樣問題，常見的啟發式算法有左底算法(BL算法)、左底填充算法(BLF算法)、下臺階法、最低水平線法、剩余矩形法［14，15］。本文是將改進的粒子群算法同剩余矩形法相結合用于排樣問題，剩余矩形法可做如下闡述:

參照圖1，寬W、高H的矩形(0，0，W，H)。一個矩形件i(寬wi、高hi)加入后，原來的大矩形減去加入矩形件的位置。設矩形件的左下角坐標為(xi，yi)，則大矩形減掉與矩形件(xi，yi，xi+wi，yi+hi)相交的部分后，得到的4個新的矩形:(0，0，xi，H)、(0，0，W，yi)、(0，yi+hi，W，H)、(xi+wi，0，W，H)。相鄰矩形件的重疊部分如何處理將在后文中給出。

剩余矩形法包含剩余矩形集、待排矩形集、已排矩形集等3個矩形集。剩余矩形集包含任何沒有被排樣的空間，待排矩形集和已排矩形集分別包含待排、已排的矩形件信息。剩余矩形法可作如下描述:

(1)初始時，剩余矩形集為母板(0，0，W，H)。

(2)當1個矩形件排入時，3個集都要進行更新。待排矩形集要刪除代表該矩形件的結點。在剩余矩形集中找到一個能放下該矩形件的最小剩余矩形，將該矩形件放置在此剩余矩形的左下角(滿足BL條件)，刪除此剩余矩形，得到了2個新的剩余矩形R1和R2，如圖2所示。對于R1和R2的重合部分(圖中虛線部分)，將在第3步進行調整。對于已排矩形集，則記錄排入矩形的位置。

圖1 剩余矩形法示意圖

(3)更新剩余矩形集。新的剩余矩形的產生會引起剩余矩形集發生變化，這時就要對剩余矩形集作如下調整:對于有完全包含關系的剩余矩形，刪除被包含的矩形，僅保留較大面積矩形;對于有相交關系的剩余矩形，全部保留;對于與已排入矩形有相交關系的剩余矩形，全部刪除;對于面積為零或已放不下剩下任一矩形的剩余矩形，全部刪除。按此規則更新的剩余矩形集用于下一次排樣。

(4)重復第2、第3步，直至所有矩形排完，即待排矩形集為零，輸出板材利用率。

從上面的描述可以看出，剩余矩形法既滿足BL條件又符合BLF算法的思想，這樣就能夠對排樣過程中產生的空白間隙進行填充，保證了板材較高的利用率，有利于找到較優解。

圖2 剩余矩形法切割示意圖

2 粒子群算法的改進

蛙跳簡化粒子群算法(SFLA-SPSO)就是將混合蛙跳算法的分組思想引入到文獻［8］給出的簡化粒子群算法中。由于多了一個分組操作，將原來簡化的粒子群算法的位置更新公式改寫如下:

式中:x(t)、x(t+1)分別表示粒子當前位置和迭代后的位置。符號右邊的第1項為“歷史”部分，表示過去對現在的影響，通過慣性因子w來調節影響程度;第2項為“認知”部分，表示粒子對自身的思考，c1為自身學習因子，Pbest表示粒子自身最優位置;第3項為“社會”部分，表示粒子與組內最優粒子gbest的比較和模仿，c2為組內學習因子;第4項為“超社會”部分，表示粒子與總的粒子群體最優粒子g′best的比較和模仿，c3為全局學習因子;r1、r2、r3均為［0，1］之間的隨機數，由計算機分別隨機生成。這樣粒子就獲得了更為豐富的信息來更新自身位置，局部信息和全局信息能夠得到充分利用，粒子間的信息共享和合作也更加充分。

蛙跳簡化粒子群算法的具體流程如下:

Step 1選定粒子群規模(m組，每組n個粒子)，對粒子群的初始位置進行初始化;

Step 2計算每個粒子的適應度;將粒子按照適應度函數值由小到大的順序進行排序，得到全局最優值;

Step 3對粒子進行分組，第 i組粒子為{xi，xm+i，x2m+i，…，x(j－1)m+i}，i∈［1，m］，j∈［1，n］;

Step 4對于每個粒子，將其適應度與所經歷過的最好位置的適應度進行比較，如果更好，則將其作為粒子的個體歷史最優值，用當前位置更新個體歷史最好位置pbest;

Step 5選出組內最優位置gbest，對于第i組粒子，有gbest=xi;

Step 6每個小組中n個粒子按照公式(1)更新自身位置，迭代完成后對每個粒子按適應度由小到大的順序進行排序，排序后的粒子進入下一次組內迭代，轉到Step 5;

Step 7達到組內迭代次數后，各組更新后的粒子進入下一次分組，轉到Step 3;

Step 8達到分組次數后，退出。

蛙跳簡化粒子群算法的流程圖如圖3所示。

3 改進粒子群算法在船舶排樣中的應用

蛙跳簡化粒子群算法定義于連續的函數空間，要將其應用到組合優化問題中，必須將其改造為離散的算法。參照文獻［16］，本文求解矩形件排樣問題的蛙跳簡化粒子群算法作如下定義:

3.1 基本概念

(1)粒子群

粒子群表示待排矩形件部分排樣序列(包含是否翻轉的信息)的集合。

(2)粒子位置

一個排樣序列 X=(r1N1，r2N2，…，rnNn)代表了一個粒子的位置，即排樣問題的一個解。其中，Ni為矩形件的序號;ri為翻轉因子，只取1或－1，ri=1表示矩形件Ni橫放，ri=－1表示矩形件Ni豎放。粒子的位置隨著搜索的進行而不斷改變，即排樣序列在不斷發生變化。

圖3 蛙跳簡化粒子群算法流程圖

例如 X=(1，2，－5，3，－4)就是一個位置，表示先橫放1號矩形件，接著橫放2號矩形件，豎放5號矩形件，橫放3號矩形件，最后豎放4號矩形件。

(3)置換子

假設某個粒子k的位置為Xk，置換子(riik，rjjk)的操作定義為交換Xk中序號為ik和jk的矩形件位置，并繼承置換子中的翻轉因子。即 X′k=Xk+(riik，rjjk)，其中X′k為粒子 k經過置換操作后的新位置。

例如:Xk=(3，2，－1，5，4)，(ik，jk)=(1，－2)，表示先將排樣序列(3，2，－1，5，4)中1號矩形件橫放，2號矩形件豎放，再調換兩者的位置，則X′k=(3，2，－1，5，4)+(1，－2)=(3，1，－2，5，4)。

(4)置換序列

一個或多個置換子組成的隊列即為置換序列，它表示置換子按隊列順序依次作用在粒子位置上。((4，－1)，(2，－3))就是一個置換序列，它由置換子(4，－1)、(2，－3)組成，表示先把矩形件4橫放，矩形件1豎放，然后交換位置，再將矩形件2橫放，矩形件3豎放，再將位置進行互換。

例如:粒子位置(4，－2，－5，1，3)與置換序列((4，－1)，(2，－3))的操作

(4，－2，－5，1，3)+((4，－1)，(2，－ 3))=((4，－2，－5，1，3)+(4，－1))+(2，－3)=(－1，－2，－5，4，3)+(2，－3)=(－1，－3，－5，4，2)。

(5)粒子間距

粒子間距(粒子間的距離)就是一個置換序列，它表示粒子從一個位置更新到另一個位置需要的置換子的隊列。用D表示間距，|D|表示間距長度即間距所含置換子的數目。間距D可以表示為:

3.2 基本操作

(1)+(位置，間距)

粒子位置與粒子間距相加，表示一組置換子序列依次作用于粒子位置上，粒子到達一個新的位置。

例如:A=(－2，－3，1，4，5)+(－1，4)=(－2，－3，4，－1，5)。

(2)－(位置，位置)

粒子的位置與位置相減，即得到粒子間距(置換序列)。

例如:A=(1，4，5，2，3)，B=(1，4，－2，－3，5)，分別比較A(i)和B(i)，找到第一個A(i)≠B(i)的位置，即A(3)=5，B(3)=－2，則第一個置換子為(A(3)，B(3))即(5，－2)，更新 B=B+(5，－2)=(1，4，5，－3，－2);同理，A(4)≠B(4)，第二個置換子為(2，－3)，更新 B=B+(2，－3)=(1，4，5，2，－3);A(5)≠B(5)，第三個置換子為(3，－3)，更新 B=B+(3，－3)=(1，4，5，2，3)，此時 A=B。最后得到 A－B的置換序列為((5，－2)，(2，－3)，(3，－3))。即A－B=D，則 A=B+D。

設定i=1，j=0，n為 A、B兩個序列的長度，即待排矩形件的個數。Dj表示A－B得到的置換序列中第j個置換子。A－B具體過程如下:①若A(i)=B(i)，則 i=i+1;否則 j=j+1，Dj=(A(i)，B(i))，i=i+1，同時更新B=B+Dj;②重復執行①，直到i＞n時退出。A －B={Dj，j=1，2，…}。

(3)⊕(間距，間距)

粒子間距與間距相加，表示把一個間距加到另一個間距末尾。如:((5，－2)，(3，－3))+((4，－1)，(2，－3)，(3，5))=((5，－2)，(3，－3)，(4，－1)，(2，－3)，(3，5))。

(4)×(實數，間距)

間距與實數相乘，例如:cD，c為實數，D為間距。假設間距D的長度為k，乘法操作其實就是截取間距列表，使得新的間距的長度等于［ck］。例如c=0.8，k=6，則運算的結果是截取間距的前4個置換子;若c≥1，則取全部(即8個)置換子。

3.3 粒子更新公式定義

算法的粒子更新公式為:

3.4 適應度函數

本文在定寬無限長的板材上進行排樣。設板材寬度為W，第i(共有n個矩形件，i=1，2，…，n)個矩形件的長為li，寬為wi。矩形件沿板材長度方向進行排放，則優化排樣的適應度函數為:

式中:h為零件排樣后在板材上所達到的最大高度，則理論最優高度為Hbest=max∑ni=1liwi/W，適應度函數可更新為E=Hbest/h。

3.5 終止條件

算法在達到最大迭代次數時停止。

3.6 算法步驟

算法步驟同蛙跳簡化粒子群算法的步驟，只是在計算適應度函數時要調用剩余矩形法的程序。

4 排樣實例測試及結果分析

本文分別對2組矩形件進行測試，測試數據見表1。實驗中c1=c3=2，c2=0.8;第1組粒子群分為5組，每組5個，第2組粒子群分為5組，每組10個;組內迭代次數為1，分組次數為30;程序獨立運行50次，取最高利用率對應的排樣序列進行作圖。因矩形件參數均為整數，故理論最低高度H′best=(Hbest)+1，此時理論最高利用率為 E′best=Hbest/H′best。2組矩形件用本文算法得到的最優排樣圖分別如圖4、圖5所示。

表1 測試數據

由圖4、圖5可以看出，在板材寬帶為15的情況下，12塊矩形件排樣計算出的最低高度為20，此時板材利用率為98%，排樣圖已達到最優結果;66塊矩形件排樣計算出的最低高度為318，此時板材利用率為90.61%，優于文獻［9］的排樣結果(利用率88.12%)。總體來看，基于蛙跳簡化粒子群算法的矩形件排樣效果較好，也證明了該算法的有效性。

圖4 12塊矩形件排樣結果

圖5 66塊矩形件排樣結果

5 結論

船舶零件屬于不規則形狀物體，可用組合、矩形包絡等方式將其轉化為矩形件再進行排樣［17］。本文將蛙跳簡化粒子群算法經離散化后，結合剩余矩形法來求解定寬無限長板材上的矩形件排樣優化問題。文中將矩形件的翻轉信息加入到排樣序列中，降低了程序的復雜度，提高了運行效率。2個測試實例表明，此種求解的算法能找到比較滿意的排樣方案，說明了此種排樣方法的有效性。然而，由于剩余矩形法是將矩形件一塊一塊排入板材中，這樣得到的排樣圖形有些雜亂，不方便切割，給實際的工程應用帶來了困難。如何實現同規格矩形件組合后按塊排入是本文下一步研究的重點。

［l］Kennedy J，Eberhart R C.Particle swarm optimization［C］//Proc.IEEE Int＇I Conf.on Neural Networks.NJ Piscataway，IEEE Press，1995:1942－1948.

［2］Eberhart R C，Shi Y.Particle Swam Optimization:Development，Applications and Resources［C］//Proc.Congress on Evolutionary Com-putation.Korea:IEEE Serrice center，2001:8l－86.

［3］柯晶，錢積新.應用粒子群優化的非線性系統辨識［J］.電路與系統學報，2003，8(4):12－15.

［4］孫湘，周大為，張希望.慣性權重粒子群算法模型收斂性分析及參數選擇［J］.計算機工程與設計，2010，31(18):4068－4071.

［5］石永生，陳家琪.基于高斯變異的量子粒子群算法［J］.電腦與信息技術，2010，18(6):9－12.

［6］王華秋，曹長修.基于模擬退火的并行粒子群優化研究［J］.控制與決策，2005，20(5):500－504.

［7］徐志烽.一種多粒子群的協同優化算法［J］.現代電子技術，2007，(1):131 －133.

［8］胡旺，李志蜀.一種更簡化而高效的粒子群優化算法［J］.軟件學報，2007，18(4):861－868.

［9］黃紅兵.矩形件排樣問題的粒子群算法求解［J］.機械工程師，2007，(12):60－61.

［10］楊傳華，等.定序列矩形件優化排樣的二維搜索算法［J］.佳木斯大學學報:自然科學版，2010，28(3):354－356.

［11］陶獻偉，王華昌，李志剛.基于填充算法的矩形件排樣優化求解［J］.中國機械工程，2003，14(13):1104－1107.

［12］李明，周澤槐.基于粒子群算法的矩形件優化排樣［J］.電路與系統學報，2007，12(2):39－42.

［13］李妮.基于遺傳算法的矩形件排樣問題研究［D］.太原:山西大學，2010.

［14］陳釗.求解矩形排樣問題的離散粒子群算法［D］.合肥:合肥工業大學，2009.

［15］李滿江，孟祥旭，王志強.矩形件和任意多邊形排樣問題的算法及應用［J］.貴州工業大學學報:自然科學版，2002，31(4):126－130.

［16］宋佩華.基于離散粒子群優化算法求解矩形件排樣問題［D］.桂林:廣西師范大學，2007.

［17］賈志欣，殷國富，羅陽，等.二維不規則零件排樣問題的遺傳算法求解［J］.計算機輔助設計與圖形學學報，2002，14(5):467－470.