基于改進(jìn)蟻群優(yōu)化算法的車間布局優(yōu)化

葛安華，姚向楠，張玉巧

(東北林業(yè)大學(xué) 工程技術(shù)學(xué)院，哈爾濱 150040)

隨著市場(chǎng)競(jìng)爭(zhēng)的加劇和生產(chǎn)方式的變革，原有的設(shè)施布局漸漸不適應(yīng)要求，迫使企業(yè)對(duì)已有系統(tǒng)、人員和設(shè)施進(jìn)行重新評(píng)估和認(rèn)識(shí)，這使得布局的問(wèn)題逐漸顯現(xiàn)出來(lái)，人們也越來(lái)越重視如何設(shè)計(jì)出更高效的布局。但布局問(wèn)題是一個(gè)及其復(fù)雜且矛盾的優(yōu)化問(wèn)題，目前一些學(xué)者提出的布置模型還不夠完善，其求解算法也有許多不足。改進(jìn)的蟻群優(yōu)化算法是在克服蟻群優(yōu)化算法缺點(diǎn)的基礎(chǔ)上發(fā)展而來(lái)，應(yīng)用范圍幾乎遍及各個(gè)領(lǐng)域[1]。鑒于此，本文將采用一種改進(jìn)的蟻群算法來(lái)求解車間布局的優(yōu)化問(wèn)題。

1 車間布局問(wèn)題的二次分配建模

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

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

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

(3)設(shè)施間的距離度采用直角距離進(jìn)行計(jì)量。

(4)不同設(shè)施間單位物流量搬運(yùn)單位距離所需費(fèi)用相同，且為1。

以總搬運(yùn)成本Z最小為目標(biāo)，現(xiàn)有n個(gè)設(shè)施和n個(gè)位置，每個(gè)設(shè)施要求布置在一個(gè)不同位置上，假如設(shè)施i被布置在位置點(diǎn)k上，設(shè)施j被布置在位置點(diǎn)h上，設(shè)施i與j之間流量用fij來(lái)表示，位置點(diǎn)k與h之間的距離用dkh來(lái)表示。

那么QAP的數(shù)學(xué)模型可表示為

(1)

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

。(2)

2 改進(jìn)蟻群優(yōu)化算法的求解

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

2.1 問(wèn)題圖形表示

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

圖1 車間布局的構(gòu)建圖

2.2 螞蟻的路徑選擇

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

(3)

3 車間布局的蟻群算法

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

在初始化數(shù)據(jù)、參數(shù)和信息素之后，設(shè)NCmax為最大迭代次數(shù)，ACO算法反復(fù)在主循環(huán)中迭代，當(dāng)Nant只螞蟻都迭代完成，得到了Nant組解初始解，然后，通過(guò)局部搜索法對(duì)初始解進(jìn)行優(yōu)化，最后更新信息素矩陣?？偣卜譃槿蟛襟E，具體運(yùn)行如下。

3.1.1 初始解

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

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

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

3.1.2 局部搜索優(yōu)化

本文運(yùn)用的局部搜索方法是運(yùn)用傳統(tǒng)的2-選擇交換和一種新的交換方法相結(jié)合的形式來(lái)計(jì)算的，結(jié)果表明其改善方法更優(yōu)一些。運(yùn)用局部搜索法對(duì)初始解優(yōu)化的步驟為：

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

(2)隨機(jī)產(chǎn)生兩個(gè)要交換元素的位置，對(duì)其進(jìn)行交換。

(3)交換后目標(biāo)函數(shù)值的新解小于初始解時(shí)，實(shí)施交換，否則不進(jìn)行交換。

(4)當(dāng)局部搜索次數(shù)為n次，fork=Nant時(shí)，完成了對(duì)所有初始解的局部搜索。

3.1.3 信息素更新

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

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

(4)

(5)

(6)

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

具體步驟為：

(1)產(chǎn)生隨機(jī)數(shù)，判斷其解是否為至今最優(yōu)還是當(dāng)代最優(yōu)，計(jì)算信息素相應(yīng)的釋放量Δτij(t)。

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

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

根據(jù)上面三大步驟的不斷循環(huán)和分析，最終將獲得車間的最優(yōu)布局方案。下面給出一個(gè)簡(jiǎn)單的應(yīng)用范例。

3.2 實(shí)例應(yīng)用

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

該布局方案的物料的搬運(yùn)成本為

(7)

圖2原始布置方案

Fig.2 The original layout plan

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

表2 各區(qū)域間的距離矩陣表 m

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

圖3最優(yōu)布置方案

Fig.3 Optimal layout scheme

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

4 結(jié)論和討論

本文根據(jù)車間布局優(yōu)化的最小物流費(fèi)用原則，建立了布局優(yōu)化的QAP數(shù)學(xué)模型，針對(duì)QAP的特點(diǎn)，提出了一種改進(jìn)的蟻群優(yōu)化算法來(lái)對(duì)其進(jìn)行求解，該算法強(qiáng)調(diào)對(duì)最優(yōu)路徑的開(kāi)發(fā)，并且對(duì)路徑上信息素濃度的大小進(jìn)行了限制，避免了搜索的停滯；同時(shí)對(duì)信息素強(qiáng)度更新提出了新的更新規(guī)則，并且融合局部搜索的方法，使得改進(jìn)后的蟻群算法解的性能得到較大提高。結(jié)合具體實(shí)例，并通過(guò)VC++6.0編程來(lái)實(shí)現(xiàn)求解，結(jié)果表明，新布局方案物料搬運(yùn)成本要比原布局方案節(jié)約10%，驗(yàn)證了改進(jìn)的蟻群優(yōu)化算法對(duì)布局優(yōu)化的QAP數(shù)學(xué)模型的求解是可行且有效的。

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

【參 考 文 獻(xiàn)】

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

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

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

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

[5]范 文，余隋懷.蟻群算法求解人及布局優(yōu)化問(wèn)題[J].機(jī)械科學(xué)與技術(shù)，2004，14(4)：423-427.

[6]魯 強(qiáng)，陳 明.平面布局的蟻群算法[J].計(jì)算機(jī)應(yīng)用，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]王家善.設(shè)施規(guī)劃與設(shè)計(jì)[J].工業(yè)工程，1998，1(1)：11-14.

[10]吳永忠.面向大規(guī)模定制的生產(chǎn)線優(yōu)化設(shè)計(jì)系統(tǒng)的研究與開(kāi)發(fā)[D].廣州：廣東工業(yè)大學(xué)，2004.

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

[12]詹玉洪.求解車輛路徑問(wèn)題的混合螞蟻系統(tǒng)[J].計(jì)算技術(shù)與自動(dòng)化，29(1)：138-141.

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