離散粒子群算法在矩形排樣問題上的應用研究

陳 釗

(安徽職業(yè)技術(shù)學院 實訓中心，安徽 合肥 230011)

關鍵字： 離散粒子群算法；矩形排樣；組合優(yōu)化；

矩形件優(yōu)化排樣是在給定的板材上將待排矩形件按照最優(yōu)方式進行排布, 以便最大限度地利用材料, 其實質(zhì)就是一個組合優(yōu)化的二維布局問題, 但至今仍無法找到解決該問題的有效多項式時間算法。對于矩形優(yōu)化排樣問題的研究，主要有啟發(fā)式算法的研究、基于人工智能算法的研究以及基于運籌學方法的研究，都取得了很多成果。近年來，基于人工智能算法對于排樣問題的研究是現(xiàn)在和未來研究的重點。

1 問題描述

粒子群優(yōu)化算法( Particle Swarm Optimization) 是由Kennedy 和Eberhart[1，2]于1995 年在鳥群、魚群和人類社會行為規(guī)律的啟發(fā)下提出的一種基于群智能的演化計算技術(shù)。他們提出了PSO算法的離散二進制版，但這只是在對經(jīng)典連續(xù)性PSO問題的針對性修改，并沒有考慮到離散型問題組合優(yōu)化的特點。Clerc[3]提出的DPSO算法，說明了解決離散型問題的關鍵在于對于問題域的定義及其對于PSO算法相關的數(shù)學對象和運算規(guī)則的定義。鐘一文等[4]利用DPSO很好的解決了TSP問題。針對矩形優(yōu)化排樣問題，由于排樣序列不是連續(xù)的序列而是一串不重復且屬于一定范圍內(nèi)的離散型序列，因此屬于離散型組合優(yōu)化問題。本文通過固定的排樣規(guī)則(剩余矩形排樣法)將原本復雜的二維排樣問題轉(zhuǎn)換成為可以求解組合優(yōu)化的問題，對離散粒子群算法進行了改進，根據(jù)所求解問題及離散量運算的特點，對粒子的位置、速度等量及其運算規(guī)則進行了重新定義，取得了很好的結(jié)果。

2 建立解決問題模型

2.1 下料規(guī)則(剩余矩形排樣法)

本文采用的是剩余矩形排樣法，構(gòu)造了三個矩形鏈表，分別為剩余矩形鏈表、待排矩形鏈表、已排矩形鏈表。任何沒有被排樣的空間，都在矩形鏈表中表示。形成方法如下：

(1)初始剩余矩形鏈表中僅有一個矩形，即母板(0，Height，Width，0)。

(2)從待排矩形鏈表中取出一個矩形，同時刪除該結(jié)點。在剩余矩形集合中找到一個能放下該矩形件的剩余矩形，將該矩形件放置在剩余矩形的左下角(滿足BL條件)，將位置記錄并加入已排矩形鏈表，同時剩余矩形鏈表中每個剩余矩形都減去該矩形所占的位置，形成新的剩余矩形，如下圖所示，切割后形成兩個剩余矩形R1和R2，它們有共同的重合部分(虛線部分)。

剩余矩形排樣法排樣示意圖

(3)由于新的剩余矩形的產(chǎn)生，會引起原剩余矩形鏈表的改變，因此對其(虛線部分)進行調(diào)整：去掉面積為零的或已無法排下的所剩的任何一個矩形件的剩余矩形；去掉和已排矩形有相交關系的剩余矩形；把具有完全包含關系的剩余矩形中面積小的矩形去除、有相交關系的矩形全部保留。得到新的剩余矩形集合，為下一次排樣使用。

(4)當待排鏈表非空時，轉(zhuǎn)到第2步繼續(xù)進行排樣。如空則結(jié)束排樣，計算出板材利用率。

2.2 矩形排樣問題的數(shù)學模型

根據(jù)上述排樣規(guī)則，可以總結(jié)本文研究的矩形排樣問題的目標函數(shù)和約束條件為：

(1)

(2)

3 改進離散粒子群算法

Clerc說明了解決離散型問題的關鍵在于對問題域的定義及PSO算法相關的數(shù)學對象和運算規(guī)則的定義，包括：粒子的位置表示；粒子的速度表示；位置與速度的加法運算規(guī)則；位置的減法運算規(guī)則；速度的加法和乘法運算規(guī)則。本文對于離散粒子群算法進行重新定義，如下：

(1)粒子的位置表示。粒子的位置X定義為一個整數(shù)序列X =(x1，x2, x3,……,xn)，1≤i≤n,1≤Xi≤n。并且序列中所有成員不能重復并且屬于1-n(n為待排矩形件零件的個數(shù)),表示為待排矩形零件的排樣順序。Xi的值為待排矩形零件的編號，表示為編號為Xi的零件的排樣順序為i。例如：X = (3，2，1，4，5)就是一個位置，x1= 3表示編號為3的零件的排樣順序為1即第一個排。

(2)粒子的速度表示。粒子的速度定義為一個整數(shù)序列V = (v1,v2,v3,……，vn)，1≤i≤n,1≤Vi≤n。同樣序列中所有成員不能重復并且屬于1-n,表示為一個交換序列。Vi 的值為該位置Xi交換對象的坐標。例如：V = (2，3，1，4，5)就是一個速度，v1= 2表示為x1的交換對象為x2。

(3)位置與速度的加法運算規(guī)則。位置與速度相加得到一個新的位置，X’= X + V ，即：

(3)

式(3)說明，如果Vi=i的話Xi不變，否則，Xi 與Xvi 交換。該交換序列從第1位到第n位依次進行交換，循環(huán)執(zhí)行，交換的次數(shù)為vi≠i的個數(shù)。例如：X =(3，2，1，4，5),V = (2，3，1，4，5)則X + V = (3，1，2，4，5)。

(4)位置的減法運算規(guī)則。倆個位置相減得到一個速度，V=X′-X，即:

X′i-Xi=j;X'j=Xi

(4)

式(4)說明，X′-X得到為Xi在X’中的下標。例如：X =(3，2，1，4，5),V = (2，

3，1，4，5)則X - V = (2，1，3，4，5)。

(5)速度的加法和乘法運算規(guī)則。兩個速度的相加即為兩個交換序列的相加，相加的規(guī)則和X + V類似。其中，Rand()為一個在0和1范圍之內(nèi)的隨機數(shù)；V為以一定概率保留。

(5)

速度的乘法運算為

(6)

(6)粒子的運動方程。通過以上的定義，可以將經(jīng)典的PSO算法的公式改為：

V’ =V+C1*(Xpbest-X) +C2*(Xgbest-X)；

(7)

X’=X+V；

(8)

其中，慣性權(quán)值W=1，C1和C2為學習因子設為2。

4 實驗及結(jié)果分析

(1)實驗數(shù)據(jù)。該算法采用C++編寫，經(jīng)算法仿真數(shù)據(jù)的經(jīng)典算例，算例一為25個矩形的排樣問題：將15*40的矩形分成25個小矩形進行排樣。算例二為50個矩形的排樣問題：將15*40的矩形分成50個小矩形進行排樣。

(2)參數(shù)設置。兩個算例的參數(shù)設置均為：W=1，C1=C2=2，初始種群的粒子數(shù)為100個，迭代終止條件為運行100代。

(3)實驗結(jié)果。算例一的實驗結(jié)果為高度15，寬度42，板材利用率為95.24%，對比結(jié)果如表1所示；算例二的實驗結(jié)果為高度15，寬度42，板材利用率為95.24%，對比結(jié)果如表2所示。

表1 25矩形排樣問題

表2 50矩形排樣問題

實驗結(jié)果對比顯示本文提出的算法所求得的最優(yōu)解要優(yōu)于宋佩華等人[5]的離散粒子群算法，李滿江等人[6]與王竹婷[7]提出的遺傳算法所求得的最優(yōu)解，材料利用率更是達到了95%以上，說明了本文提出的改進離散粒子群算法的有效性和先進性。