基于改進(jìn)粒子群算法的船舶排樣問(wèn)題研究

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

(1.江蘇科技大學(xué)南徐學(xué)院，江蘇 鎮(zhèn)江 212003;2.江蘇科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 鎮(zhèn)江 212003)

0 引言

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

粒子群優(yōu)化算法［1］(Particle Swarm Optimization，簡(jiǎn)稱(chēng)PSO)是由Kennedy和 Eberhart首先提出的一種全局隨機(jī)搜索算法。它模擬鳥(niǎo)群覓食過(guò)程中的遷徙和群聚行為，利用群體智能搜索出較好的解。該算法有著收斂速度快、設(shè)置參數(shù)少、算法簡(jiǎn)單易實(shí)現(xiàn)等優(yōu)點(diǎn)，所以一經(jīng)提出就受到了學(xué)術(shù)界的廣泛重視，并被廣泛應(yīng)用于函數(shù)優(yōu)化、模式分類(lèi)、模糊系統(tǒng)控制、神經(jīng)網(wǎng)絡(luò)訓(xùn)練以及其他工程領(lǐng)域中［2，3］。因此近年來(lái)許多國(guó)內(nèi)外學(xué)者研究粒子群算法，并提出了很多改進(jìn)的算法［4～8］。

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

1 剩余矩形法簡(jiǎn)介

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

參照?qǐng)D1，寬W、高H的矩形(0，0，W，H)。一個(gè)矩形件i(寬wi、高h(yuǎn)i)加入后，原來(lái)的大矩形減去加入矩形件的位置。設(shè)矩形件的左下角坐標(biāo)為(xi，yi)，則大矩形減掉與矩形件(xi，yi，xi+wi，yi+hi)相交的部分后，得到的4個(gè)新的矩形:(0，0，xi，H)、(0，0，W，yi)、(0，yi+hi，W，H)、(xi+wi，0，W，H)。相鄰矩形件的重疊部分如何處理將在后文中給出。

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

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

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

圖1 剩余矩形法示意圖

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

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

從上面的描述可以看出，剩余矩形法既滿足BL條件又符合BLF算法的思想，這樣就能夠?qū)ε艠舆^(guò)程中產(chǎn)生的空白間隙進(jìn)行填充，保證了板材較高的利用率，有利于找到較優(yōu)解。

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

2 粒子群算法的改進(jìn)

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

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

蛙跳簡(jiǎn)化粒子群算法的具體流程如下:

Step 1選定粒子群規(guī)模(m組，每組n個(gè)粒子)，對(duì)粒子群的初始位置進(jìn)行初始化;

Step 2計(jì)算每個(gè)粒子的適應(yīng)度;將粒子按照適應(yīng)度函數(shù)值由小到大的順序進(jìn)行排序，得到全局最優(yōu)值;

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

Step 4對(duì)于每個(gè)粒子，將其適應(yīng)度與所經(jīng)歷過(guò)的最好位置的適應(yīng)度進(jìn)行比較，如果更好，則將其作為粒子的個(gè)體歷史最優(yōu)值，用當(dāng)前位置更新個(gè)體歷史最好位置pbest;

Step 5選出組內(nèi)最優(yōu)位置gbest，對(duì)于第i組粒子，有g(shù)best=xi;

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

Step 7達(dá)到組內(nèi)迭代次數(shù)后，各組更新后的粒子進(jìn)入下一次分組，轉(zhuǎn)到Step 3;

Step 8達(dá)到分組次數(shù)后，退出。

蛙跳簡(jiǎn)化粒子群算法的流程圖如圖3所示。

3 改進(jìn)粒子群算法在船舶排樣中的應(yīng)用

蛙跳簡(jiǎn)化粒子群算法定義于連續(xù)的函數(shù)空間，要將其應(yīng)用到組合優(yōu)化問(wèn)題中，必須將其改造為離散的算法。參照文獻(xiàn)［16］，本文求解矩形件排樣問(wèn)題的蛙跳簡(jiǎn)化粒子群算法作如下定義:

3.1 基本概念

(1)粒子群

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

(2)粒子位置

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

圖3 蛙跳簡(jiǎn)化粒子群算法流程圖

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

(3)置換子

假設(shè)某個(gè)粒子k的位置為Xk，置換子(riik，rjjk)的操作定義為交換Xk中序號(hào)為ik和jk的矩形件位置，并繼承置換子中的翻轉(zhuǎn)因子。即 X′k=Xk+(riik，rjjk)，其中X′k為粒子 k經(jīng)過(guò)置換操作后的新位置。

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

(4)置換序列

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

例如:粒子位置(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)粒子間距

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

3.2 基本操作

(1)+(位置，間距)

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

例如: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)，找到第一個(gè)A(i)≠B(i)的位置，即A(3)=5，B(3)=－2，則第一個(gè)置換子為(A(3)，B(3))即(5，－2)，更新 B=B+(5，－2)=(1，4，5，－3，－2);同理，A(4)≠B(4)，第二個(gè)置換子為(2，－3)，更新 B=B+(2，－3)=(1，4，5，2，－3);A(5)≠B(5)，第三個(gè)置換子為(3，－3)，更新 B=B+(3，－3)=(1，4，5，2，3)，此時(shí) A=B。最后得到 A－B的置換序列為((5，－2)，(2，－3)，(3，－3))。即A－B=D，則 A=B+D。

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

(3)⊕(間距，間距)

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

(4)×(實(shí)數(shù)，間距)

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

3.3 粒子更新公式定義

算法的粒子更新公式為:

3.4 適應(yīng)度函數(shù)

本文在定寬無(wú)限長(zhǎng)的板材上進(jìn)行排樣。設(shè)板材寬度為W，第i(共有n個(gè)矩形件，i=1，2，…，n)個(gè)矩形件的長(zhǎng)為li，寬為wi。矩形件沿板材長(zhǎng)度方向進(jìn)行排放，則優(yōu)化排樣的適應(yīng)度函數(shù)為:

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

3.5 終止條件

算法在達(dá)到最大迭代次數(shù)時(shí)停止。

3.6 算法步驟

算法步驟同蛙跳簡(jiǎn)化粒子群算法的步驟，只是在計(jì)算適應(yīng)度函數(shù)時(shí)要調(diào)用剩余矩形法的程序。

4 排樣實(shí)例測(cè)試及結(jié)果分析

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

表1 測(cè)試數(shù)據(jù)

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

圖4 12塊矩形件排樣結(jié)果

圖5 66塊矩形件排樣結(jié)果

5 結(jié)論

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

［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］柯晶，錢(qián)積新.應(yīng)用粒子群優(yōu)化的非線性系統(tǒng)辨識(shí)［J］.電路與系統(tǒng)學(xué)報(bào)，2003，8(4):12－15.

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

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

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

［7］徐志烽.一種多粒子群的協(xié)同優(yōu)化算法［J］.現(xiàn)代電子技術(shù)，2007，(1):131 －133.

［8］胡旺，李志蜀.一種更簡(jiǎn)化而高效的粒子群優(yōu)化算法［J］.軟件學(xué)報(bào)，2007，18(4):861－868.

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

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

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

［12］李明，周澤槐.基于粒子群算法的矩形件優(yōu)化排樣［J］.電路與系統(tǒng)學(xué)報(bào)，2007，12(2):39－42.

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

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

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

［16］宋佩華.基于離散粒子群優(yōu)化算法求解矩形件排樣問(wèn)題［D］.桂林:廣西師范大學(xué)，2007.

［17］賈志欣，殷國(guó)富，羅陽(yáng)，等.二維不規(guī)則零件排樣問(wèn)題的遺傳算法求解［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2002，14(5):467－470.