基于遺傳光學算法的鏡片加工車間布局優化*

馬玉瑩，張家驊

(無錫工藝職業技術學院機電與信息工程學院，江蘇 宜興 214206)

0 引言

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

1 問題描述及數學模型

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

圖1 車間設備布置示意圖

該問題的目標函數如下：

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

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

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)是設備坐標和設備間凈間距非負要求，式(9)要求同一行設備不能重疊。式(10)表示當設備i布置在第k行，決策變量λik=1，否則為0；式(11)要求一臺設備只能出現一次。

2 遺傳光學算法

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

2.1 光學算法

光學優化算法是Kashan在2015年設計的一種新型群體算法，并已在連續問題上證明該算法要優于粒子群等算法[9]。該算法將被優化函數曲面的局部凹凸性質比擬成凹、凸鏡，將可行解比作光源，光源經凹、凸鏡成像后的點為更新后的解。因為光源的位置不同，從而呈現大小不同的像，實現算法的探索與利用。該算法的原理如圖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)

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

王金葉等[10]對光學優化問題進行了進一步研究，提高了算法性能。但目前主要光學優化算法研究的是連續性問題，還沒有研究設備布局這類離散問題。

圖2 光學優化算法原理圖

2.2 遺傳光學算法流程

遺傳算法是通過模擬生物進化過程實現優化目標，包括選擇、交叉、變異操作；其中變異算子存在盲目變異的缺陷，使算法易陷入局部最優。本文將光學算法取代遺傳算法的變異算子，來提高算法的尋優能力。圖3是整個遺傳光學算法的流程圖。

圖3 遺傳光學算法流程圖

2.3 染色體的編碼和解碼

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

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

圖4 染色體編碼與解碼

2.4 選擇算子和交叉算子

在求解最小化問題時，采用競標賽選擇，可以避免采用輪盤賭算子時需要適應度值轉換問題，并獲得更好性能[11]。因此，采用競標賽選擇，隨機選中兩個個體，適應度值好的個體，進入到進化過程中。交叉算子采用均勻交叉，因為這種方式能夠產生較好的個體后代，破壞能力較小[12]。

2.5 光學優化

(14)

最后，將光學優化后的種群與原種群進行比較，將目標函數值好的染色體保留形成新的種群，進行下一次進化，直到滿足迭代要求。

3 實例研究

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

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

表2 單位物料搬運費用Pij

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

表3 設備間物料搬運頻率Qij

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

圖5 不同算法適應度值收斂曲線

表4是最終獲得的搬運費用值和設備包絡面積，三種算法都可以得到相同的包絡面積，但是GOA在搬運費用上，比GA的結果可以節約10%的費用。

表4 搬運費用和設備包絡面積

4 結論

(1)根據鏡片車間設備布局問題，建立了具有搬運成本和設備包絡面積指標的多目標設備布局模型。

(2)針對傳統遺傳算法，采用競標賽選擇算子替換輪盤賭選擇算子，光學優化算法取代變異算子，構造了一種遺傳光學算法。

(3)實際案例計算結果表明，遺傳光學算法通過將光學優化引入到種群進化環節，引導種群趨向最優方向收斂，避免傳統遺傳算法陷入局部最優，能得到比遺傳算法質量更好的方案。