基于遺傳光學(xué)算法的鏡片加工車間布局優(yōu)化*

馬玉瑩，張家驊

(無錫工藝職業(yè)技術(shù)學(xué)院機(jī)電與信息工程學(xué)院，江蘇 宜興 214206)

0 引言

車間設(shè)備布局優(yōu)化是指在滿足約束的條件下，在已知的工作區(qū)域?qū)υO(shè)備進(jìn)行布局來實(shí)現(xiàn)某些生產(chǎn)目標(biāo)。設(shè)備布局對于企業(yè)提高生產(chǎn)效率，降低生產(chǎn)成本有著重要意義[1]。由于車間設(shè)備布局問題被證明是NP-hard問題，采用確定性優(yōu)化方法求解效果不理想，智能優(yōu)化算法是解決此類問題的主要方法[2]。遺傳算法、粒子群算法、蟻群算法等已經(jīng)被成功用來解決設(shè)備布局問題[3-5]，其中遺傳算法是主流算法[6]。肖國紅等采用遺傳算法求解了以最小化物料搬運(yùn)費(fèi)用為目標(biāo)的鏡片加工車間布局優(yōu)化問題[7]。但是實(shí)際生產(chǎn)中往往存在多個(gè)優(yōu)化目標(biāo)；而且傳統(tǒng)遺傳算法存在容易陷入局部最優(yōu)等缺點(diǎn)[8]。通過不同算法的混合，能夠提高單一算法的搜索性能；光學(xué)優(yōu)化算法是一種新的群體智能算法，并在連續(xù)問題上被證明優(yōu)于粒子群算法[9]。因此本文根據(jù)企業(yè)實(shí)際情況，以最小化鏡片車間設(shè)備間物流搬運(yùn)費(fèi)用和設(shè)備包絡(luò)面積為優(yōu)化目標(biāo)建立多目標(biāo)模型，并開發(fā)了一種遺傳光學(xué)算法，來求解設(shè)備布局方案。

1 問題描述及數(shù)學(xué)模型

在矩形布局的車間內(nèi)，確定形狀和尺寸已知的磨削機(jī)等設(shè)備位置；出于物料要求，設(shè)備分行排列，設(shè)備間存在間距要求。圖1是車間設(shè)備布置示意圖。

圖1 車間設(shè)備布置示意圖

該問題的目標(biāo)函數(shù)如下：

minF=ω1f1+ω2f2

(1)

(2)

f2=Sl/β

(3)

Dij=|xi-xj|+|yi-yj|

(4)

xi=xk+(li+lk)/2+hik+Δi=
hk0+Δk+(li+2lk)/2+hik+Δi

(5)

yi=(t-1)d+d0

(6)

Sl=H×[(m-1)d+d0+
0.5max(wi)-(d0-0.5max(wj)]

(7)

式(1)是目標(biāo)函數(shù)，同時(shí)最優(yōu)化目標(biāo)f1和f2，采用加權(quán)法將雙目標(biāo)優(yōu)化問題轉(zhuǎn)換為單目標(biāo)，ω1和ω2是加權(quán)系數(shù)，由企業(yè)專家給出，ω1+ω2=1；式(2)和式(3)分別是目標(biāo)函數(shù)物料搬運(yùn)成本和布局結(jié)果所包絡(luò)面積，式中Pij為設(shè)備i和j之間的搬運(yùn)費(fèi)用，Qij為設(shè)備i和j間物料搬運(yùn)頻率，m為車間總行數(shù)，n為設(shè)備數(shù)量，Sl為車間布局包絡(luò)總面積，式中α和β由預(yù)先調(diào)試給出，對目標(biāo)函數(shù)進(jìn)行歸一化處理；式(4)中Dij為設(shè)備i和j之間距離；式(5)為第i臺設(shè)備橫坐標(biāo)，li為設(shè)備長度，hij為設(shè)備i和j間的橫向最小間距，hi0為設(shè)備i和車間邊界間的橫向最小間距，Δi為設(shè)備i和i-1或邊界間凈間距；式(6)為第k行的第i臺設(shè)備的縱坐標(biāo)，d為設(shè)備行間距，d0為第一行設(shè)備到車間邊界的距離; 式(7)中H為車間寬度中wi為最后一行上的設(shè)備的寬度，wj為第一行上的設(shè)備的寬度。

該問題的需要滿足的約束是：

xi,yi≥0,Δi>0,

(8)

|xi-xj|≥[(li+lj)/2+hij]λikλjk

(9)

λik={0,1}

(10)

(11)

i，j，k=1,…,n；t=1,…,m

式(8)是設(shè)備坐標(biāo)和設(shè)備間凈間距非負(fù)要求，式(9)要求同一行設(shè)備不能重疊。式(10)表示當(dāng)設(shè)備i布置在第k行，決策變量λik=1，否則為0；式(11)要求一臺設(shè)備只能出現(xiàn)一次。

2 遺傳光學(xué)算法

本文通過將光學(xué)算法混合到遺傳算法中，設(shè)計(jì)一種遺傳光學(xué)算法來求解鏡片加工設(shè)備布局問題。

2.1 光學(xué)算法

光學(xué)優(yōu)化算法是Kashan在2015年設(shè)計(jì)的一種新型群體算法，并已在連續(xù)問題上證明該算法要優(yōu)于粒子群等算法[9]。該算法將被優(yōu)化函數(shù)曲面的局部凹凸性質(zhì)比擬成凹、凸鏡，將可行解比作光源，光源經(jīng)凹、凸鏡成像后的點(diǎn)為更新后的解。因?yàn)楣庠吹奈恢貌煌瑥亩尸F(xiàn)大小不同的像，實(shí)現(xiàn)算法的探索與利用。該算法的原理如圖2所示，焦距f，球面半徑r(r=2f)，物距p，像距q，球面鏡物像公式：

2/r=1/p+1/q?q=rp/(2p-r)

(12)

球面鏡放大率公式：

m=-q/p=HI/HO?HI=-HO·q/p

(13)

在光學(xué)優(yōu)化算法中，將問題的初始解表示為一系列初始光源的位置，光線在已知光學(xué)參數(shù)的鏡面上不斷反射成像，即通過式(12)、式(13)，可將光源點(diǎn)位置p和HO，換算得到像點(diǎn)的位置q和HI，從而實(shí)現(xiàn)解的更新。

王金葉等[10]對光學(xué)優(yōu)化問題進(jìn)行了進(jìn)一步研究，提高了算法性能。但目前主要光學(xué)優(yōu)化算法研究的是連續(xù)性問題，還沒有研究設(shè)備布局這類離散問題。

圖2 光學(xué)優(yōu)化算法原理圖

2.2 遺傳光學(xué)算法流程

遺傳算法是通過模擬生物進(jìn)化過程實(shí)現(xiàn)優(yōu)化目標(biāo)，包括選擇、交叉、變異操作；其中變異算子存在盲目變異的缺陷，使算法易陷入局部最優(yōu)。本文將光學(xué)算法取代遺傳算法的變異算子，來提高算法的尋優(yōu)能力。圖3是整個(gè)遺傳光學(xué)算法的流程圖。

圖3 遺傳光學(xué)算法流程圖

2.3 染色體的編碼和解碼

由于光學(xué)算法解的更新函數(shù)是連續(xù)型，要使該算法適合離散問題，編碼和解碼很重要。本文采用連續(xù)性編碼，染色體長度2n，基因值取值范圍[0,Δ]，其中Δ為設(shè)備之間的最大凈間距。例如有3臺設(shè)備，設(shè)備之間的凈間距[0,2]，可如圖4進(jìn)行編碼，保證了染色體可以使用連續(xù)函數(shù)的更新方法。

采用面向設(shè)備的原理進(jìn)行解碼，如圖4編碼段進(jìn)行解碼的時(shí)候，基于部分優(yōu)先權(quán)解碼策略，對前半段的染色體按照基于優(yōu)先權(quán)位置排列，后面的基因值不變。這樣設(shè)備布置順序是1-3-2，這個(gè)順序下的設(shè)備間的凈間距是1.4、1.1、1.7。

圖4 染色體編碼與解碼

2.4 選擇算子和交叉算子

在求解最小化問題時(shí)，采用競標(biāo)賽選擇，可以避免采用輪盤賭算子時(shí)需要適應(yīng)度值轉(zhuǎn)換問題，并獲得更好性能[11]。因此，采用競標(biāo)賽選擇，隨機(jī)選中兩個(gè)個(gè)體，適應(yīng)度值好的個(gè)體，進(jìn)入到進(jìn)化過程中。交叉算子采用均勻交叉，因?yàn)檫@種方式能夠產(chǎn)生較好的個(gè)體后代，破壞能力較小[12]。

2.5 光學(xué)優(yōu)化

(14)

最后，將光學(xué)優(yōu)化后的種群與原種群進(jìn)行比較，將目標(biāo)函數(shù)值好的染色體保留形成新的種群，進(jìn)行下一次進(jìn)化，直到滿足迭代要求。

3 實(shí)例研究

光學(xué)鏡片加工車間120 m2(12 m×10 m)，需布置10臺設(shè)備(4臺磨削機(jī)，4臺拋光機(jī)，2臺清洗機(jī))，具體尺寸如表1所示，表2是設(shè)備間的物料搬運(yùn)費(fèi)用Pij，表3是設(shè)備間物料搬運(yùn)頻率Qij，設(shè)備間橫向最小距離hij=2 m，設(shè)備與車間邊界的最小間距hi0=1.5 m，兩設(shè)備間的凈間距Δ的取值范圍為[0，1.5]m。第一行設(shè)備與車間上邊界之間的距離d0為1.5 m，車間行間距d為2 m。

表1 待布局設(shè)備尺寸 (m)

表2 單位物料搬運(yùn)費(fèi)用Pij

分別采用文獻(xiàn)中的遺傳算法(GA)[3]，自適應(yīng)遺傳算法(AGA)[13]與本文遺傳光學(xué)算法(GOA)的結(jié)果進(jìn)行對比。優(yōu)化過程中算法的參數(shù)如下：ω1=0.5，ω2=0.5；由企業(yè)現(xiàn)場工程師給定；目標(biāo)函數(shù)標(biāo)準(zhǔn)化系數(shù)α=6742，β=68；種群數(shù)量100；最大遺傳代數(shù)為600；GA中交叉率pc=0.8；變異率pm=0.2；AGA中自適應(yīng)參數(shù)與文獻(xiàn)[13]設(shè)置一致；GOA中，光學(xué)更新系數(shù)Pc=0.7。由于GA和AGA中用的是輪盤賭算子，因此目標(biāo)是最大化適應(yīng)度值，為了對比，對適應(yīng)度值進(jìn)行了轉(zhuǎn)化，結(jié)果給出了最小化目標(biāo)值。

表3 設(shè)備間物料搬運(yùn)頻率Qij

圖5是每個(gè)算法執(zhí)行5次后的最優(yōu)的目標(biāo)函數(shù)值的收斂曲線。可以看到三種算法中，GOA的效果最好，GA的效果最差。這是由于普通GA容易陷入局部最優(yōu)，而變異算子變異盲目。AGA算法雖然比GA算法得到了好的效果，但是從整個(gè)過程上看，AGA算法只是在算法后半段才開始發(fā)揮最用，在算法前半段，由于種群差異大，自適應(yīng)參數(shù)并不發(fā)揮很大作用。從GOA算法的進(jìn)化過程中可以看到，GOA算法整體趨勢就表明該算法可以跳出局部最優(yōu)解，往全局最優(yōu)解的方向發(fā)展。

圖5 不同算法適應(yīng)度值收斂曲線

表4是最終獲得的搬運(yùn)費(fèi)用值和設(shè)備包絡(luò)面積，三種算法都可以得到相同的包絡(luò)面積，但是GOA在搬運(yùn)費(fèi)用上，比GA的結(jié)果可以節(jié)約10%的費(fèi)用。

表4 搬運(yùn)費(fèi)用和設(shè)備包絡(luò)面積

4 結(jié)論

(1)根據(jù)鏡片車間設(shè)備布局問題，建立了具有搬運(yùn)成本和設(shè)備包絡(luò)面積指標(biāo)的多目標(biāo)設(shè)備布局模型。

(2)針對傳統(tǒng)遺傳算法，采用競標(biāo)賽選擇算子替換輪盤賭選擇算子，光學(xué)優(yōu)化算法取代變異算子，構(gòu)造了一種遺傳光學(xué)算法。

(3)實(shí)際案例計(jì)算結(jié)果表明，遺傳光學(xué)算法通過將光學(xué)優(yōu)化引入到種群進(jìn)化環(huán)節(jié)，引導(dǎo)種群趨向最優(yōu)方向收斂，避免傳統(tǒng)遺傳算法陷入局部最優(yōu)，能得到比遺傳算法質(zhì)量更好的方案。