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

管賢平

（江蘇大學 現代農業裝備與技術省部共建教育部重點實驗室，鎮江 212013）

0 引言

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

1 布局設計問題模型

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

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

布局設計問題的目標是最小化包括物流路程和工作站重構成本在內的總物流成本J：

其中Δw為工作站w是否重構的指示變量：

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

位置約束：

流量約束：

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

2 變鄰域遺傳算法

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

1） 染色體編碼

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

2） 適應度值計算

根據個體染色體編碼計算其對應的總物流成本，將總成本的倒數作為個體的適應度值。

3） 交叉操作

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

4） 變異操作

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

5） 選擇操作

根據適應度值按輪盤賭的方式選擇個體。

6） 小生境淘汰運算

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

7） 變鄰域搜索

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

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

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

（1）初始化： 根據海明距離定義鄰域結構Nk，k＝1， ，kmax，設置局部搜索次數LSIt為停止條件。

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

（3）令k＝1。

（6）ifk≤kmax轉 Step 4。

（7）ifl＜LSIt,l＝l＋1，轉Step 3。

（8）Setπi＝π；

返回πi。

8） 停止條件

完成一定進化代數Ng后停止。

9） 參數設置

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

3 計算實例

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

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

1） 實例 1

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

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

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

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

2） 實例 2

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

表3 實例1兩種方法的結果

表 4 實例2 GA方法的結果

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

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

4 結論

本文根據基于AGV的RMS布局設計特點，提出了變鄰域遺傳算法的布局設計方法，設計了兩個計算實例進行計算分析。計算結果表明：在問題規模較小時，GA方法都能得到最優結果，在問題規模較大時，GA方法能在有限時間內完成計算，這說明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] 周明, 孫樹棟, 遺傳算法原理及應用[M].北京: 國防工業出版社, 1999.

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