陳 釗
(安徽職業(yè)技術(shù)學(xué)院 實(shí)訓(xùn)中心,安徽 合肥 230011)
關(guān)鍵字: 離散粒子群算法;矩形排樣;組合優(yōu)化;
矩形件優(yōu)化排樣是在給定的板材上將待排矩形件按照最優(yōu)方式進(jìn)行排布, 以便最大限度地利用材料, 其實(shí)質(zhì)就是一個組合優(yōu)化的二維布局問題, 但至今仍無法找到解決該問題的有效多項式時間算法。對于矩形優(yōu)化排樣問題的研究,主要有啟發(fā)式算法的研究、基于人工智能算法的研究以及基于運(yùn)籌學(xué)方法的研究,都取得了很多成果。近年來,基于人工智能算法對于排樣問題的研究是現(xiàn)在和未來研究的重點(diǎn)。
粒子群優(yōu)化算法( Particle Swarm Optimization) 是由Kennedy 和Eberhart[1,2]于1995 年在鳥群、魚群和人類社會行為規(guī)律的啟發(fā)下提出的一種基于群智能的演化計算技術(shù)。他們提出了PSO算法的離散二進(jìn)制版,但這只是在對經(jīng)典連續(xù)性PSO問題的針對性修改,并沒有考慮到離散型問題組合優(yōu)化的特點(diǎn)。Clerc[3]提出的DPSO算法,說明了解決離散型問題的關(guān)鍵在于對于問題域的定義及其對于PSO算法相關(guān)的數(shù)學(xué)對象和運(yùn)算規(guī)則的定義。鐘一文等[4]利用DPSO很好的解決了TSP問題。針對矩形優(yōu)化排樣問題,由于排樣序列不是連續(xù)的序列而是一串不重復(fù)且屬于一定范圍內(nèi)的離散型序列,因此屬于離散型組合優(yōu)化問題。本文通過固定的排樣規(guī)則(剩余矩形排樣法)將原本復(fù)雜的二維排樣問題轉(zhuǎn)換成為可以求解組合優(yōu)化的問題,對離散粒子群算法進(jìn)行了改進(jìn),根據(jù)所求解問題及離散量運(yùn)算的特點(diǎn),對粒子的位置、速度等量及其運(yùn)算規(guī)則進(jìn)行了重新定義,取得了很好的結(jié)果。
本文采用的是剩余矩形排樣法,構(gòu)造了三個矩形鏈表,分別為剩余矩形鏈表、待排矩形鏈表、已排矩形鏈表。任何沒有被排樣的空間,都在矩形鏈表中表示。形成方法如下:
(1)初始剩余矩形鏈表中僅有一個矩形,即母板(0,Height,Width,0)。
(2)從待排矩形鏈表中取出一個矩形,同時刪除該結(jié)點(diǎn)。在剩余矩形集合中找到一個能放下該矩形件的剩余矩形,將該矩形件放置在剩余矩形的左下角(滿足BL條件),將位置記錄并加入已排矩形鏈表,同時剩余矩形鏈表中每個剩余矩形都減去該矩形所占的位置,形成新的剩余矩形,如下圖所示,切割后形成兩個剩余矩形R1和R2,它們有共同的重合部分(虛線部分)。
剩余矩形排樣法排樣示意圖
(3)由于新的剩余矩形的產(chǎn)生,會引起原剩余矩形鏈表的改變,因此對其(虛線部分)進(jìn)行調(diào)整:去掉面積為零的或已無法排下的所剩的任何一個矩形件的剩余矩形;去掉和已排矩形有相交關(guān)系的剩余矩形;把具有完全包含關(guān)系的剩余矩形中面積小的矩形去除、有相交關(guān)系的矩形全部保留。得到新的剩余矩形集合,為下一次排樣使用。
(4)當(dāng)待排鏈表非空時,轉(zhuǎn)到第2步繼續(xù)進(jìn)行排樣。如空則結(jié)束排樣,計算出板材利用率。
根據(jù)上述排樣規(guī)則,可以總結(jié)本文研究的矩形排樣問題的目標(biāo)函數(shù)和約束條件為:
(1)
(2)
Clerc說明了解決離散型問題的關(guān)鍵在于對問題域的定義及PSO算法相關(guān)的數(shù)學(xué)對象和運(yùn)算規(guī)則的定義,包括:粒子的位置表示;粒子的速度表示;位置與速度的加法運(yùn)算規(guī)則;位置的減法運(yùn)算規(guī)則;速度的加法和乘法運(yùn)算規(guī)則。本文對于離散粒子群算法進(jìn)行重新定義,如下:
(1)粒子的位置表示。粒子的位置X定義為一個整數(shù)序列X =(x1,x2, x3,……,xn),1≤i≤n,1≤Xi≤n。并且序列中所有成員不能重復(fù)并且屬于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。同樣序列中所有成員不能重復(fù)并且屬于1-n,表示為一個交換序列。Vi 的值為該位置Xi交換對象的坐標(biāo)。例如:V = (2,3,1,4,5)就是一個速度,v1= 2表示為x1的交換對象為x2。
(3)位置與速度的加法運(yùn)算規(guī)則。位置與速度相加得到一個新的位置,X’= X + V ,即:
(3)
式(3)說明,如果Vi=i的話Xi不變,否則,Xi 與Xvi 交換。該交換序列從第1位到第n位依次進(jì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)位置的減法運(yùn)算規(guī)則。倆個位置相減得到一個速度,V=X′-X,即:
X′i-Xi=j;X'j=Xi
(4)
式(4)說明,X′-X得到為Xi在X’中的下標(biāo)。例如:X =(3,2,1,4,5),V = (2,
3,1,4,5)則X - V = (2,1,3,4,5)。
(5)速度的加法和乘法運(yùn)算規(guī)則。兩個速度的相加即為兩個交換序列的相加,相加的規(guī)則和X + V類似。其中,Rand()為一個在0和1范圍之內(nèi)的隨機(jī)數(shù);V為以一定概率保留。
(5)
速度的乘法運(yùn)算為
(6)
(6)粒子的運(yùn)動方程。通過以上的定義,可以將經(jīng)典的PSO算法的公式改為:
V’ =V+C1*(Xpbest-X) +C2*(Xgbest-X);
(7)
X’=X+V;
(8)
其中,慣性權(quán)值W=1,C1和C2為學(xué)習(xí)因子設(shè)為2。
(1)實(shí)驗數(shù)據(jù)。該算法采用C++編寫,經(jīng)算法仿真數(shù)據(jù)的經(jīng)典算例,算例一為25個矩形的排樣問題:將15*40的矩形分成25個小矩形進(jìn)行排樣。算例二為50個矩形的排樣問題:將15*40的矩形分成50個小矩形進(jìn)行排樣。
(2)參數(shù)設(shè)置。兩個算例的參數(shù)設(shè)置均為:W=1,C1=C2=2,初始種群的粒子數(shù)為100個,迭代終止條件為運(yùn)行100代。
(3)實(shí)驗結(jié)果。算例一的實(shí)驗結(jié)果為高度15,寬度42,板材利用率為95.24%,對比結(jié)果如表1所示;算例二的實(shí)驗結(jié)果為高度15,寬度42,板材利用率為95.24%,對比結(jié)果如表2所示。
表1 25矩形排樣問題
表2 50矩形排樣問題
實(shí)驗結(jié)果對比顯示本文提出的算法所求得的最優(yōu)解要優(yōu)于宋佩華等人[5]的離散粒子群算法,李滿江等人[6]與王竹婷[7]提出的遺傳算法所求得的最優(yōu)解,材料利用率更是達(dá)到了95%以上,說明了本文提出的改進(jìn)離散粒子群算法的有效性和先進(jìn)性。