基于改進蟻群優化算法的車間布局優化

葛安華，姚向楠，張玉巧

(東北林業大學 工程技術學院，哈爾濱 150040)

隨著市場競爭的加劇和生產方式的變革，原有的設施布局漸漸不適應要求，迫使企業對已有系統、人員和設施進行重新評估和認識，這使得布局的問題逐漸顯現出來，人們也越來越重視如何設計出更高效的布局。但布局問題是一個及其復雜且矛盾的優化問題，目前一些學者提出的布置模型還不夠完善，其求解算法也有許多不足。改進的蟻群優化算法是在克服蟻群優化算法缺點的基礎上發展而來，應用范圍幾乎遍及各個領域[1]。鑒于此，本文將采用一種改進的蟻群算法來求解車間布局的優化問題。

1 車間布局問題的二次分配建模

1957年Koopamans和Beckmann為彼此間有物料流動的設施的位置問題提出了二次分配問題(QAP)[2]。為簡化該模型做如下假設：

(1)確定數量的需要布置在矩形區域中的矩形設施。

(2)設施的位置相互之間不能重疊，且不能超出矩形區域。

(3)設施間的距離度采用直角距離進行計量。

(4)不同設施間單位物流量搬運單位距離所需費用相同，且為1。

以總搬運成本Z最小為目標，現有n個設施和n個位置，每個設施要求布置在一個不同位置上，假如設施i被布置在位置點k上，設施j被布置在位置點h上，設施i與j之間流量用fij來表示，位置點k與h之間的距離用dkh來表示。

那么QAP的數學模型可表示為

(1)

式中：xik、xih為決策變量，如果設施i布置在位置點k上，則xik取值為1，否則xik取值為0。公式(2)為其約束條件。

。(2)

2 改進蟻群優化算法的求解

蟻群優化算法(ACO)已成為解決各種組合優化問題的最有效的算法之一[3-12]，根據二次分配的特點，蟻群優化算法適用于解決二分配問題。但傳統的螞蟻算法采用固定的信息素增減來進行信息素更新，使得這種算法容易出現收斂速度慢、陷入局部最優、運算時間長等現象[13]。為了解決這個問題，Stutzle和Hoos對此提出了兩點改進，一是把路徑上的信息素濃度的大小限制在[τmin,τmax]范圍之內，二是對信息素強度更新提出了新的更新規則，這就是最大最小螞蟻系統(MAX-MIN Ant System，MMAS)。本文將運用最大最小螞蟻系統來求解車間布局QAP模型。

2.1 問題圖形表示

根據目標函數和約束條件，車間布局問題的構件圖設計如圖1所示。從而構成了n個設施選擇n個位置的決策問題。每個節點{rij|i=1,2,…n;j=1,2…n}表示設施i選擇布局的位置j。這樣共有nn向量將節點從第1個位置連接到第n位置。

圖1 車間布局的構建圖

2.2 螞蟻的路徑選擇

螞蟻在各個節點上游走，并留下不同的信息素的濃度，以此來影響下一批螞蟻選擇的移動方向。令τij(t)為t時刻各個節點上信息素的濃度大小，初始時刻節點上的信息素濃度為τ0。生成的Nant只螞蟻被放在圖1第一個位置的各個節點上，然后每一只螞蟻根據信息素和啟發式信息獨立的選擇下一位置的某個節點，t時刻，處于節點rij時的螞蟻k選擇下一位置節點rz(j+1)的概率公式為：

(3)

3 車間布局的蟻群算法

3.1 車間布局蟻群算法的描述

在初始化數據、參數和信息素之后，設NCmax為最大迭代次數，ACO算法反復在主循環中迭代，當Nant只螞蟻都迭代完成，得到了Nant組解初始解，然后，通過局部搜索法對初始解進行優化，最后更新信息素矩陣。總共分為三大步驟，具體運行如下。

3.1.1 初始解

(1)把初始化禁忌表的值設為零。

(2)fork=1toNant，按照公式3概率公式計算選擇下一個位置的節點，如螞蟻沒走到最后一個位置，將其所選擇的節點加入螞蟻k的禁忌表，結束。

(3)當螞蟻第k=Nant時，每一只螞蟻都已經建立了初始解。否則返回(2)。

3.1.2 局部搜索優化

本文運用的局部搜索方法是運用傳統的2-選擇交換和一種新的交換方法相結合的形式來計算的，結果表明其改善方法更優一些。運用局部搜索法對初始解優化的步驟為：

(1)fork=1，局部搜索次數設定為1。

(2)隨機產生兩個要交換元素的位置，對其進行交換。

(3)交換后目標函數值的新解小于初始解時，實施交換，否則不進行交換。

(4)當局部搜索次數為n次，fork=Nant時，完成了對所有初始解的局部搜索。

3.1.3 信息素更新

MMAS對信息素的大小值施加限制，控制在范圍[τmin,τmax]，如果更新后的信息素大于τmax或者小于τmin，強令其值τmax或者為τmin。當所有螞蟻都完成局部搜索后，將進行信息素更新。信息素更新分為信息素的揮發和信息素的釋放，具體規則為：

τij(t+1)=(1-ρ)τij(t)+Δτij(t)。

(4)

(5)

(6)

式中：ρ表示揮發因子；1-ρ則為殘留因子；Cbest為當前迭代最優解或者是至今最優解。信息素的釋放只對系統產生的最優解和當前最優解，其他解Δτij(t)=0。

具體步驟為：

(1)產生隨機數，判斷其解是否為至今最優還是當代最優，計算信息素相應的釋放量Δτij(t)。

(2)對信息素矩陣進行信息素進行揮發，然后計算更新之后的信息素τij(t+1)。

(3)判斷信息更新之后的量是否在[τmin,τmax]之內，若不在則按信息素更新規則更改。

根據上面三大步驟的不斷循環和分析，最終將獲得車間的最優布局方案。下面給出一個簡單的應用范例。

3.2 實例應用

一個總面積為35 m×20 m的生產車間，車間有12個生產單元，現以最小化物料運輸成本為目標函數，建立該車間的QAP模型，對該車間的布局進行優化。現根據QAP模型要求把車間區域重新劃分，由于有12個生產車間，則劃分為12個面積相等的區域，按照三行進行布置。現有各個生產單元之間的物流流量表1。區域之間的距離運用距心之間的直角距離來計算，相鄰之間為一個單位，這樣就構造了一個距離矩陣見表2。車間的原來的布局方案為R=(D，H，C，I，F，A，L，J，G，B，E，K)，如圖2所示。

該布局方案的物料的搬運成本為

(7)

圖2原始布置方案

Fig.2 The original layout plan

表1 各單元之間的物流量矩陣 kg

表2 各區域間的距離矩陣表 m

運行環境：PC機，內存為2G，操作環境為win7，開發VC++6.0實現，程序中用到的參數設置為Nant=12，NCmax=12，α=1，β=2，ρ=0.05，τmax=2，τmin=0.4，Q=1000，Cbest=5，τ0=2，n=30。運行結果，得出最優的布置方案為R=(E，B，I，C，G，K，J，H，D，F，A，L)。相應的布置如圖3所示。該布置方案的物料的搬運成本為3680。

圖3最優布置方案

Fig.3 Optimal layout scheme

顯然，和原布局方案進行比較，新方案高潛在物流量的生產單位分配到具有低潛在距離的位置上，所以在物料搬運的成本上更低。

4 結論和討論

本文根據車間布局優化的最小物流費用原則，建立了布局優化的QAP數學模型，針對QAP的特點，提出了一種改進的蟻群優化算法來對其進行求解，該算法強調對最優路徑的開發，并且對路徑上信息素濃度的大小進行了限制，避免了搜索的停滯；同時對信息素強度更新提出了新的更新規則，并且融合局部搜索的方法，使得改進后的蟻群算法解的性能得到較大提高。結合具體實例，并通過VC++6.0編程來實現求解，結果表明，新布局方案物料搬運成本要比原布局方案節約10%，驗證了改進的蟻群優化算法對布局優化的QAP數學模型的求解是可行且有效的。

不可否認的是蟻群優化算法是一個復雜的系統，它的行為受到參數、宏觀算法部件和問題特性等多方面影響，本文使用的改進的蟻群優化算法一定程度上克服了它的一些缺陷，但如何最有效的發揮算法的性能還需做進一步研究；另外，本文求解的車間布局問題是靜態的車間設施平面布局，對于更復雜的車間布局問題也還需做進一步研究和探討。

【參 考 文 獻】

[1]桑國珍，李智勇.蟻群算法研究與應用[J].內江科技，2009(8)：33-34.

[2]Lari M B.Layout designs in cellular manufacturing[J].European Journal of Operational Research，1999，112：258-272.

[3]張利城，吳金卓，何 榮.基于循環取貨模式的車輛路徑優化研究[J].森林工程，2013，29(4)：87-89.

[4]魯 強，陳 明.平面布局的蟻群算法[J].計算機應用，2005，25(5)：1119-1121.

[5]范 文，余隋懷.蟻群算法求解人及布局優化問題[J].機械科學與技術，2004，14(4)：423-427.

[6]魯 強，陳 明.平面布局的蟻群算法[J].計算機應用，2005，25(5)：1019-1021.

[7]Al-Attar A.A hybrid GA-heuristic search strategy[J].Al Expert USA，1994，9(9)：34-37.

[8]Komarudin K.Applying ant system for solving unequal area facility layout problems[J].European Journal of Operational Research，2010，202：730-746.

[9]王家善.設施規劃與設計[J].工業工程，1998，1(1)：11-14.

[10]吳永忠.面向大規模定制的生產線優化設計系統的研究與開發[D].廣州：廣東工業大學，2004.

[11]葛安華，周晏明，李權章.改進遺傳算法求解作業車間提前/托期調度問題[J].森林工程，2013，29(3)：138-141.

[12]詹玉洪.求解車輛路徑問題的混合螞蟻系統[J].計算技術與自動化，29(1)：138-141.

[13]倪慶劍，邢漢承.蟻群算法及其應用研究[J].計算機應用與軟件，2008，25(8)：12-15.