基于變鄰域遺傳算法的RMS布局設(shè)計方法

管賢平

（江蘇大學 現(xiàn)代農(nóng)業(yè)裝備與技術(shù)省部共建教育部重點實驗室，鎮(zhèn)江 212013）

0 引言

隨著市場需求的多樣化和個性化，能以較低成本快速響應(yīng)市場需求的可重構(gòu)制造系統(tǒng)（RMS）得到廣泛關(guān)注[1]。布局設(shè)計問題是已知負載流量，根據(jù)給定系統(tǒng)可能的分布位置，確定各個工作站在車間的位置分布，以使得總物流成本最小化[2]。在可重構(gòu)制造環(huán)境下，需要快速改變系統(tǒng)的構(gòu)形，以適應(yīng)不斷變化的生產(chǎn)需求，對布局問題的求解時間和求解質(zhì)量提出很高的要求。Meng等[3]提出可重構(gòu)布局問題。本文針對基于AGV的RMS的布局設(shè)計要求，綜合考慮AGV空載和負載路程，提出高效、求解質(zhì)量高的變鄰域遺傳算法。

1 布局設(shè)計問題模型

本文作如下假設(shè)：每個工作站s有一個加載點Ps和一個卸載點Ds；車間中可分配的位置數(shù)量與待分配的工作站數(shù)量相等，每個位置只能分配一個工作站。AGV在工作站之間的路徑段可雙向行走。工作站w到工作站u之間的負載流量fwu給定，Ps、Dt之間的最短路徑長度為LPsDt，工作站的單位重構(gòu)成本為CR，系統(tǒng)上一生產(chǎn)周期的初始布局為工作站w到工作站u之間的空載流量為

決策變量為Hws。假如工作站w分配到位置s，則Hws＝1，否則為0。

布局設(shè)計問題的目標是最小化包括物流路程和工作站重構(gòu)成本在內(nèi)的總物流成本J：

其中Δw為工作站w是否重構(gòu)的指示變量：

需要滿足以下的約束條件：

位置約束：

流量約束：

布局設(shè)計問題是一個復雜的非線性規(guī)劃問題，最優(yōu)化方法難以求解大規(guī)模的問題，這里采用啟發(fā)式方法：遺傳算法（GA）。針對一般GA局部搜索能力的不足，提出變鄰域遺傳算法（VNS/GA）。

2 變鄰域遺傳算法

GA是一種有效的啟發(fā)式方法，得到廣泛應(yīng)用[4,5]。GA方法是并行搜索，可以得到多個不同的較高質(zhì)量的解，但是局部搜索能力較差，為此借鑒文獻[5]的方法，在局部搜索中增加變鄰域（VNS）搜索策略。根據(jù)GA的一般設(shè)計步驟，設(shè)計如圖1所示的處理過程。

1） 染色體編碼

GA的個體編碼采用工作站排序編碼的方法，編碼長度等于工作站的數(shù)量NW。某個編碼為：π＝(Wi1，Wi2， ，WiNW)，表示在位置Sk上分布的工作站為Wik。假設(shè)種群數(shù)量為Np，則種群可以表示為 Π ＝ (π1，π2， ，πNp)。

2） 適應(yīng)度值計算

根據(jù)個體染色體編碼計算其對應(yīng)的總物流成本，將總成本的倒數(shù)作為個體的適應(yīng)度值。

3） 交叉操作

染色體的交叉采用部分映射交叉的方法。在選定的兩個位置中間的基因，其排序按照另一個體中的基因排序。

4） 變異操作

變異采用隨機選擇染色體的兩個位置，交換這兩個位置上的基因。

5） 選擇操作

根據(jù)適應(yīng)度值按輪盤賭的方式選擇個體。

6） 小生境淘汰運算

比較個體編碼之間的相似度，對編碼距離較小的個體，其中適應(yīng)度值更小的個體進行一定的排擠，即小生境淘汰運算。這為了產(chǎn)生較多的相異個體，避免種群過早收斂。

7） 變鄰域搜索

由于GA的局部搜索能力較差，采用VNS局部搜索策略對產(chǎn)生的個體進行局部搜索，以提高解的質(zhì)量。為了降低搜索時間，以一個較小的概率pv對個體進行搜索。

編碼πi與πj之間的海明距離H π(πi，πj)定義為不同放置不同工作站的位置數(shù)量。對于一個編碼π，其鄰域定義為：

對某編碼πi的VNS搜索過程如下：

（1）初始化： 根據(jù)海明距離定義鄰域結(jié)構(gòu)Nk，k＝1， ，kmax，設(shè)置局部搜索次數(shù)LSIt為停止條件。

（2）設(shè)置初始解為π＝πi,令l＝0。

（3）令k＝1。

（6）ifk≤kmax轉(zhuǎn) Step 4。

（7）ifl＜LSIt,l＝l＋1，轉(zhuǎn)Step 3。

（8）Setπi＝π；

返回πi。

8） 停止條件

完成一定進化代數(shù)Ng后停止。

9） 參數(shù)設(shè)置

GAL算法的主要參數(shù)有：進化代數(shù)Ng，種群數(shù)量Np，交叉概率pc，變異概率pm，小生境參數(shù)h，變鄰域搜索參數(shù)kmax，pv。經(jīng)過一定嘗試，將各個參數(shù)設(shè)置為：Ng＝150，Np＝20，pc＝0.8，pm＝ 0.2，h＝ max ([1，NW/8])，kmax＝ [NW/3]，pv＝ 0.1。

3 計算實例

為了驗證所提出方法的效果，設(shè)計了工作站數(shù)量分別為9和15的兩個計算實例。實例1采用窮舉方法得到最優(yōu)解。而實例2由于規(guī)模較大，不能得到最優(yōu)解，只給出GA方法的運行結(jié)果。

對每個實例，首先假設(shè)在初始生產(chǎn)周期，在給定的初始負載流量表（稱為流量表1）情況下，不考慮工作站重構(gòu)成本，進行初始布局設(shè)計。然后假設(shè)系統(tǒng)在初始布局情況下，在新的生產(chǎn)周期，根據(jù)新的生產(chǎn)任務(wù)得到新的負載流量表（稱為流量表2），進行新的生產(chǎn)周期的布局設(shè)計，這時需要考慮工作站的重構(gòu)成本，針對不同重構(gòu)成本進行算例的比較分析。

1） 實例 1

本實例的工作站數(shù)量為9，各位置布局如圖2所示，流量表1如表1所示，流量表2如表2所示。首先采用窮舉法，得到各種設(shè)置情況下的最優(yōu)解，然后GA方法分別10次，以得到平均物流成本和平均計算時間。本實例兩種方法的計算結(jié)果如表3所示。

計算結(jié)果分析：窮舉法的計算時間明顯比GA方法更長。在不同的工作站單位重構(gòu)成本條件下，有不同的最優(yōu)布局。GA方法在各種設(shè)置下都能得到最優(yōu)解。

表1 實例1的初始負載流量表

表2 實例1新的負載流量表

2） 實例 2

本實例的工作站數(shù)量為15，系統(tǒng)位置布局為3行5列的格子布局，同樣根據(jù)不同流量表進行布局求解。由于本實例的工作站數(shù)量較多，無法用窮舉法求得最優(yōu)結(jié)果，所以只給出GA方法的結(jié)果，如表4所示。

表3 實例1兩種方法的結(jié)果

表 4 實例2 GA方法的結(jié)果

計算結(jié)果分析：在問題規(guī)模較大的情況下，窮舉法不能在有限時間內(nèi)完成，所以只能采用啟發(fā)式方法。GAL方法的運行效果較好。

通過由以上計算實例說明， GA方法比窮舉時間更短，在問題規(guī)模較大的情況下，GA方法能在有限時間內(nèi)完成計算，得到較好結(jié)果，這說明GA方法是一種快速高效的求解方法。

4 結(jié)論

本文根據(jù)基于AGV的RMS布局設(shè)計特點，提出了變鄰域遺傳算法的布局設(shè)計方法，設(shè)計了兩個計算實例進行計算分析。計算結(jié)果表明：在問題規(guī)模較小時，GA方法都能得到最優(yōu)結(jié)果，在問題規(guī)模較大時，GA方法能在有限時間內(nèi)完成計算，這說明GA方法是一種快速高效的求解方法。

[1] Z.M.Bi, et al., Reconfigurable manufacturing systems:the state of the art.International Journal of Production Research, 2008, 46(4): 967-992.

[2] A.Drira, H.Pierreval, and S.Hajri-Gabouj, Facility layout problems: A survey.Annual Reviews in Control,2007, 31(2): 255-267.

[3] G.Meng, S.S.Heragu, and H.Zijm, Reconfigurable layout problem.International Journal of Production Research, 42:22, 4709-4729.

[4] 周明, 孫樹棟, 遺傳算法原理及應(yīng)用[M].北京: 國防工業(yè)出版社, 1999.

[5] 管賢平, 戴先中, 李俊, 基于變鄰域小生境遺傳算法的AGV路徑網(wǎng)絡(luò)設(shè)計方法[J].中國機械工程, 2009, 20(21):2581-2586.