基于遺傳算法的啤酒灌裝生產(chǎn)線布局設計研究

賈瑞 李光

摘要：為了體現(xiàn)啤酒灌裝生產(chǎn)線布局設計的多樣性，通過對傳統(tǒng)的遺傳算法進行改進，設計了用于啤酒灌裝生產(chǎn)線布局設計的編碼方式與雙目標函數(shù)，驗證了改進后遺傳算法的可行性。

關鍵詞：啤酒灌裝生產(chǎn)線;設施布局;遺傳算法

0? ? 引言

啤酒灌裝生產(chǎn)線布局問題實質(zhì)上是確定設備在車間中的位置，目前通過智能算法對啤酒灌裝生產(chǎn)線進行布局設計的論文較為少見。遺傳算法作為一種自適應的優(yōu)化算法，搜索過程靈活性強，且具有強大的全局尋優(yōu)能力。本文采用遺傳算法對啤酒灌裝生產(chǎn)線進行布局設計，提出面向啤酒灌裝生產(chǎn)線的布局設計方法。

1? ? 啤酒灌裝生產(chǎn)線的組成與說明

啤酒灌裝生產(chǎn)線主要包含卸箱機、洗瓶機、驗瓶機、灌裝壓蓋機、殺菌機、貼標機、裝箱機等。由于啤酒灌裝生產(chǎn)線布局形式多樣，求解非常困難，本文在進行啤酒灌裝生產(chǎn)線布局設計之前做如下假設與定義：

（1）在布局過程中，忽略每臺設備的形狀和大小，將其視為一個點，重點考慮設備在車間中的位置。本文中用M表示各種設備的集合，M={M1，M2，…，MN}，其中N為設備的數(shù)量;（xi，yi）與（xi+1，yi+1）分別表示兩個相鄰設備的位置坐標。

（2）不同設備間的輸送系統(tǒng)用直線表示，忽略其寬度;相鄰兩個設備間的距離大于0即認為屬于可行解。

（3）為便于計算，規(guī)定平面布局空間解分別用一維空間解和二維空間解表示。

（4）車間的長、寬，設備的首、末位置分別用L、W、S、E表示。

2? ? 基于啤酒灌裝生產(chǎn)線布局設計問題對傳統(tǒng)遺傳算法進行改進

2.1? ? 確定初始參數(shù)與染色體的編碼、解碼方式

由于本文所研究問題可能存在布局形式多樣的情況，因此將相鄰設備間輸送系統(tǒng)的連接情況分為直道相連和轉(zhuǎn)彎道相連兩大類。

本文為解決啤酒灌裝生產(chǎn)線布局設計問題，提出的編碼與解碼方式如圖1所示。

圖1中，M1～M5表示不同工藝設備;虛線框內(nèi)M0表示輸送系統(tǒng)的轉(zhuǎn)彎點，虛線框內(nèi)數(shù)字表示輸送系統(tǒng)間的轉(zhuǎn)彎位置，在編碼時可將染色體分為定長與不定長兩種情況;后兩行分別表示設備在一維空間解中和設備在二維空間解中的位置，其中灰色數(shù)字表示設備的首末位置，黑色數(shù)字表示其他設備在空間解中的位置。染色體在一維空間解中進行編碼，計算適應度值時需要解碼，在二維空間解中進行計算，解碼公式為：

式中：X為設備在一維空間解中的位置;W為車間的寬度;int（）為取整函數(shù);%為取余運算;x與y分別表示設備在二維空間解中的橫縱坐標。

2.2? ? 初始化種群

為避免在計算過程中陷入局部最優(yōu)解，本文提出初始化兩個種群的方法。在種群A中，染色體的長度等于設備的個數(shù)，即兩兩設備間均以直道連接。在種群B中，染色體的長度大于設備的個數(shù)，即相鄰設備間可能存在一個或多個轉(zhuǎn)彎道。在初始化種群B時，可以初始化一個或多個種群，不同種群分別進化，從而保證布局結(jié)果的多樣性。

2.3? ? 個體適應度函數(shù)值的計算

本文在啤酒灌裝生產(chǎn)線布局設計時考慮兩個目標。第一個目標的計算式如下：

其中，D為兩個相鄰設備間的距離之和，期望D最小。為了保證布局結(jié)果的多樣性，本文中兩個相鄰設備間的距離用歐式距離計算，w1為該目標的影響權(quán)重。

第二個目標的計算式如下：

其中，θi，i+1為任意兩個相鄰設備間的角度;ai，i+1為兩個相鄰設備間角度關系的適應度值，一般兩個相鄰設備間的角度為0、90°、180°、270°，如果ai，i+1不滿足角度關系，則對其懲罰;A為兩個相鄰設備之間角度關系的適應度值之和，A的理想值為0;w2為該目標的影響權(quán)重。

綜上，個體的最終適應度值可用公式（4）計算：

2.4? ? 選擇、交叉、變異操作

本文采用輪盤賭選擇法進行選擇。交叉操作可讓部分優(yōu)秀基因保留下來產(chǎn)生新的個體，本文選擇單點交叉的方式進行交叉操作。變異也是產(chǎn)生新個體的一種方式，在研究過程中發(fā)現(xiàn)空間解比較大，因此提出讓每一個基因都具備變異能力的策略。

2.5? ? 選擇最優(yōu)結(jié)果

經(jīng)過選擇、交叉、變異操作后，會得到多個布局方案。此時，選擇比較滿意的一個作為參考方案。

3? ? 算法測試與案例

為了測試該算法的可行性，本文在一個10 m×10 m大小的空間內(nèi)對5臺設備進行布局設計。在一維空間解中給定S=23，E=88，初始化1個種群，每個種群中有40個染色體，迭代500次。以目標一進行測試，染色體的適應度函數(shù)變化曲線如圖2所示。

由圖2可知，隨著迭代次數(shù)的增加，染色體的適應度值越來越大，當?shù)?60次左右時趨于穩(wěn)定，說明在當前初始條件下適應度函數(shù)在逐步收斂。布局方案如圖3黑線所示，顯然兩個相鄰設備間的距離之和已接近最短。再以目標一和目標二同時進行測試，得到的布局方案如圖3灰線所示。綜上可知，該算法能快速得到比較滿意的布局設計方案。

在一個50 m×40 m大小的空間內(nèi)對7臺設備進行布局設計。假設S=123，E=1 588，w1=0.5，w2=10。初始化2個種群，每個種群中包含100個染色體，迭代5 000次。對目標一和目標二同時進行優(yōu)化，得到的啤酒灌裝生產(chǎn)線布局設計方案如圖4所示，設計用時146.385 s。

4? ? 結(jié)語

本文通過對遺傳算法進行改進，提出了啤酒灌裝生產(chǎn)線智能布局設計方法，然后對算法進行了驗證，說明了算法的有效性。但是影響啤酒灌裝生產(chǎn)線布局設計的影響因素有很多，文中只考慮了兩個方面。由于在真正對啤酒灌裝生產(chǎn)線進行布局設計時，還需要結(jié)合客戶的需求，所以在布局設計過程中還有很多參數(shù)需要不斷調(diào)整，這些參數(shù)的不同取值都可能會對布局結(jié)果產(chǎn)生很大的影響，因此，本文所提方法還需要進一步進行更深層次的研究。

收稿日期：2020-05-27

作者簡介：賈瑞（1993—），男，山西人，碩士碩士生，研究方向：包裝生產(chǎn)線布局優(yōu)化。

通信作者：李光（1975—），男，山東人，副教授，研究方向：包裝機械、包裝虛擬仿真以及包裝動力學。