基于自適應(yīng)遺傳模擬退火算法的多目標(biāo)車間布局優(yōu)化*

盧義楨 李西興 朱傳軍 吳 銳

（①?gòu)V東工業(yè)大學(xué)管理學(xué)院，廣東 廣州 510000；②湖北工業(yè)大學(xué)現(xiàn)代制造質(zhì)量工程湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430068）

車間設(shè)施布局問(wèn)題是智能制造精益生產(chǎn)中面臨復(fù)雜問(wèn)題之一，其實(shí)質(zhì)是一種非線性組合優(yōu)化問(wèn)題，需要尋求合理高效的車間設(shè)施布局方案來(lái)提高車間空間利用率，降低車間物流成本，提高生產(chǎn)效率。車間設(shè)施布局是否合理對(duì)整個(gè)生產(chǎn)系統(tǒng)的總體性能有著重要的影響。

當(dāng)前車間布局優(yōu)化問(wèn)題主要利用智能優(yōu)化算法進(jìn)行求解。國(guó)內(nèi)研究中，謝潔明等[1]提出了基于仿真的遺傳網(wǎng)格自適應(yīng)直接搜索算法（GMADS）用于求解具有單向?qū)蚵窂骄W(wǎng)絡(luò)、多重嵌套封閉環(huán)形物料儲(chǔ)運(yùn)系統(tǒng)的布局優(yōu)化問(wèn)題。郭源源等[2]采用粒子群算法求解二維設(shè)施布局問(wèn)題并將粒子群算法與SLP法進(jìn)行結(jié)合，提高了初始解的合理性和尋優(yōu)過(guò)程的高效性。陳勇等[3]為滿足低成本、高穩(wěn)健性的車間布局要求，設(shè)計(jì)了以單位面積布置成本、單位產(chǎn)品物流成本和布局熵為優(yōu)化目標(biāo)的車間布局優(yōu)化模型，提出了基于Pareto優(yōu)化的聚類并行多目標(biāo)遺傳算法。國(guó)外學(xué)者對(duì)應(yīng)用智能算法求解布局問(wèn)題也有諸多研究，F(xiàn)rederico Galaxe Paes等[4]通過(guò)引入經(jīng)分解策略改進(jìn)后的遺傳算法解決不平等區(qū)域設(shè)施布局問(wèn)題（UA-FLP）時(shí)，尋優(yōu)表現(xiàn)優(yōu)于普通遺傳算法。Jose Fernando Goncalves等[5]針對(duì)不平等區(qū)域設(shè)施布局問(wèn)題提出了偏向性的隨機(jī)關(guān)鍵遺傳算法（BRKGA）確定設(shè)施布局方案。

在車間設(shè)施布局優(yōu)化研究中，多將車間不同作業(yè)單元間搬運(yùn)距離總和作為優(yōu)化目標(biāo)[6?7]，而沒(méi)有考慮到實(shí)際生產(chǎn)中不同作業(yè)單元之間物料搬運(yùn)方式可能存在差異的情況針對(duì)該問(wèn)題，本文考慮不同作業(yè)單元之間物料搬運(yùn)方式不同的情況，以最小車間物流成本與最短車間搬運(yùn)時(shí)間為優(yōu)化目標(biāo)，采用自適應(yīng)遺傳模擬退火算法對(duì)車間設(shè)施布局問(wèn)題進(jìn)行求解，并通過(guò)實(shí)例分析驗(yàn)證了模型和算法的有效性。

1 問(wèn)題描述

在制造車間中，零件按各自批量和工藝流程依次經(jīng)過(guò)不同的作業(yè)單元完成加工過(guò)程。在這個(gè)過(guò)程中，不同的車間設(shè)施布局方案會(huì)對(duì)物料搬運(yùn)過(guò)程的時(shí)間、成本等指標(biāo)產(chǎn)生影響，需要建立數(shù)學(xué)模型，通過(guò)運(yùn)算求解出一套較優(yōu)的布局方案以滿足降低生產(chǎn)成本、提高生產(chǎn)效率的要求。

1.1 問(wèn)題假設(shè)

（1）假設(shè)各作業(yè)單元形狀均為標(biāo)準(zhǔn)矩形，長(zhǎng)和寬均已知。

（2）假設(shè)各作業(yè)單元均為橫平豎直，作業(yè)單元的邊界分別平行于車間四周邊界。

（3）假設(shè)物料是從一個(gè)作業(yè)單元的幾何中心搬運(yùn)到下一個(gè)作業(yè)單元的幾何中心。

（4）假設(shè)物料搬運(yùn)的路徑平行于車間邊界的直線。

（5）假設(shè)不同作業(yè)單元之間物料搬運(yùn)速度不同且均已知。

基于以上假設(shè)，建立車間設(shè)施布局示意圖如圖1所示。

圖1 車間設(shè)施布局

在圖1中，X軸為車間的長(zhǎng)度方向；Y軸為作業(yè)車間的寬度方向；mi為車間第i個(gè)作業(yè)單元，i=1,2,···,N（N為車間作業(yè)單元總數(shù)）；L為作業(yè)車間總長(zhǎng)度；W為作業(yè)車間總寬度；li、wi分別為車間i作業(yè)單元的長(zhǎng)度、寬度；xi、yi分別為i作業(yè)單元幾何中心點(diǎn)的橫坐標(biāo)、縱坐標(biāo)；sij為i作業(yè)單元與j作業(yè)單元邊界之間的凈間距[8]。

1.2 數(shù)學(xué)模型

本文同時(shí)考慮車間物流成本最小與車間搬運(yùn)時(shí)間最短兩個(gè)目標(biāo)進(jìn)行建模，目標(biāo)函數(shù)表達(dá)式如下所示。

式中：G1為第一個(gè)優(yōu)化目標(biāo)車間物流成本；G2為第二個(gè)優(yōu)化目標(biāo)車間搬運(yùn)時(shí)間；Pij為i作業(yè)單元與j作業(yè)單元之間單次物料搬運(yùn)單位距離的費(fèi)用；Dij為i作業(yè)單元與j作業(yè)單元幾何中心點(diǎn)之間的曼哈頓距離；Fij為i作業(yè)單元與j作業(yè)單元之間物料搬運(yùn)頻率；Vij為i作業(yè)單元與j作業(yè)單元之間物料搬運(yùn)速度。當(dāng)i=j時(shí)，Pij、Fij、Vij=0。

采用歸一化因子u1、u2來(lái)統(tǒng)一量綱[9]，u1、u2的計(jì)算如式（3）、式（4）所示?？紤]到實(shí)際生產(chǎn)中對(duì)多個(gè)優(yōu)化目標(biāo)的側(cè)重不同，加入加權(quán)因子w1、w2，且滿足w1+w2=1(w1、w2∈(0,1))，最終得到目標(biāo)函數(shù)表達(dá)式如式（5）所示。

式中：G為加權(quán)后的目標(biāo)函數(shù)值；Dmax為兩作業(yè)單元間可能存在的最大曼哈頓距離，近似為車間的長(zhǎng)和寬之和；v′ij為車間所有路徑上物料搬運(yùn)速度的平均值。

1.3 約束條件

在對(duì)車間不同作業(yè)單元的布局進(jìn)行建模優(yōu)化時(shí)，還需要結(jié)合實(shí)際情況建立約束條件，主要包括以下內(nèi)容。

（1）間距約束。不同作業(yè)單元之間需要保持一定的距離，即

（2）通道約束。各作業(yè)單元之間與車間墻壁之間需要保留一定的距離，即

（3）尺寸約束。同一行或同一列的所有作業(yè)單元在在X軸或Y軸方向上的布局不得超過(guò)車間的長(zhǎng)度或?qū)挾龋?/p>

式中：s為 最小間距。

2 自適應(yīng)遺傳模擬退火算法

為了對(duì)上述模型進(jìn)行求解，提出一種自適應(yīng)遺傳模擬退火算法，即在傳統(tǒng)遺傳算法上對(duì)交叉變異算子采用自適應(yīng)調(diào)整策略；同時(shí)利用模擬退火算法的概率突跳性來(lái)降低過(guò)早收斂的可能性，進(jìn)一步增強(qiáng)算法求解性能并基于Metropolis準(zhǔn)則判斷是否接受新個(gè)體。算法流程如圖2所示。

圖2 算法計(jì)算流程

2.1 種群初始化

本文采用實(shí)數(shù)編碼的方式構(gòu)建個(gè)體的基因序列，編碼樣式為[m1,m2,m3,m4,···,mN]，代表的含義是自車間區(qū)域自左下角依次沿X軸正方向布置作業(yè)單元，當(dāng)布置的作業(yè)單元總長(zhǎng)度超出車間長(zhǎng)度時(shí)，沿Y軸正方向另起一行，從最左端繼續(xù)向右依次布置，例如個(gè)體編碼[2,7,3,10,1,4,5,···]的布局即圖3所示。

圖3 編碼示例對(duì)應(yīng)的車間布局圖

2.2 適應(yīng)度函數(shù)

本文中綜合優(yōu)化目標(biāo)是求最小值，設(shè)置適應(yīng)度函數(shù)fi為

式中：G為目標(biāo)函數(shù)；P為懲罰函數(shù)。懲罰函數(shù)定義為

2.3 選擇算子

為保證種群基因多樣性并且同時(shí)提高算法的收斂效率，本文選擇輪盤(pán)賭加部分精英保留的策略進(jìn)行選擇操作。輪盤(pán)賭策略中，個(gè)體i被選中的概率Pi為

式中：popsize為種群大??；fi為第i個(gè)個(gè)體的適應(yīng)度值。

采用輪盤(pán)賭的方式選出下一代種群中一半的個(gè)體后，采用部分精英保留策略選出另一半的個(gè)體，選出的所有個(gè)體組合成子代種群。

2.4 交叉算子

由于車間布局問(wèn)題中個(gè)體基因型的代碼具有特殊含義，因此本文采用基于位置的交叉算子，其具體操作如圖4所示。

圖4 交叉過(guò)程

2.5 變異操作

在實(shí)數(shù)編碼下，基因序列上的每一個(gè)數(shù)字都具有特殊的含義，無(wú)法采用二進(jìn)制編碼下的各種變異方法。針對(duì)本問(wèn)題，為了保證變異之后的個(gè)體仍具有意義，采用互換變異的方式進(jìn)行操作，如圖5所示。

圖5 變異過(guò)程

2.6 自適應(yīng)交叉、變異策略

遺傳算法中，交叉概率Pc和變異概率Pm是影響算法尋優(yōu)能力的重要參數(shù)，由于自適應(yīng)取值法對(duì)交叉、變異算子進(jìn)行非線性設(shè)計(jì)，使得交叉概率與變異概率隨種群中個(gè)體的適應(yīng)度值的變化而變化，能夠防止算法陷入過(guò)早收斂[10]，因此本文對(duì)Pc、Pm的取值采用自適應(yīng)取值法，取值計(jì)算過(guò)程如式（15）、式（16）所示。

式中：Pcmax與Pcmin分別為遺傳操作過(guò)程中交叉概率取值區(qū)間的上、下限，f′為進(jìn)行交叉操作兩個(gè)個(gè)體中較大者的適應(yīng)度值，favg為每代種群的平均適應(yīng)度值，fmax為當(dāng)前種群中的最大適應(yīng)度值，λ為常數(shù)。

式中：Pmmax、Pmmin為變異概率取值區(qū)間的上、下限，f為變異個(gè)體的適應(yīng)度值，favg為每代種群的平均適應(yīng)度值，fmax為當(dāng)前種群中的最大適應(yīng)度值。

2.7 嵌入模擬退火算法

在遺傳算法中嵌入模擬退火算法，借用模擬退火算法的概率突跳性增強(qiáng)算法全局尋優(yōu)的能力。設(shè)定初始溫度t作為模擬退火尋優(yōu)的起始點(diǎn)，設(shè)定終止溫度Tend作為模擬退火尋優(yōu)的終止點(diǎn)，在等溫狀態(tài)下交換個(gè)體前后一半基因并依據(jù)Metropolis準(zhǔn)則計(jì)算新個(gè)體被接受的概率，其計(jì)算公式如下

式中：Ps為新個(gè)體接受的概率；fi(t)為個(gè)體變換前的適應(yīng)度值；fj(t)為個(gè)體變化后的適應(yīng)度值；t為當(dāng)前溫度。依據(jù)式（14）更新當(dāng)前溫度，即

式中：λ為溫度衰減參數(shù)，用于控制退火速度，且取值大小滿足λ∈(0，1)。

3 計(jì)算實(shí)例

3.1 車間概述

FK公司是一家主要從事汽車零部件設(shè)計(jì)和制造的公司，該公司生產(chǎn)車間為30 m×25 m的矩形，車間內(nèi)有11套各式加工機(jī)床以及原材料、成品存放區(qū)。為方便描述，用序號(hào)表示各作業(yè)單元，各作業(yè)單元的尺寸數(shù)據(jù)見(jiàn)表1，車間的原始布局如圖6所示。

圖6 車間原始布局

根據(jù)產(chǎn)品的工藝流程以及不同作業(yè)單元間物料搬運(yùn)方式的差異，作業(yè)單元間的單位費(fèi)用如表2所示，作業(yè)單元間的搬運(yùn)頻率如表3所示，作業(yè)單元間的搬運(yùn)速度如表4所示。

3.2 優(yōu)化過(guò)程及相關(guān)參數(shù)設(shè)定

設(shè)定最小間隔參數(shù)s為1 m。由表2、表3、表4的數(shù)據(jù)，計(jì)算出歸一化因子u1=4.905×10?6、u2=5.646×10?5。根據(jù)對(duì)優(yōu)化目標(biāo)的側(cè)重不同，設(shè)定權(quán)重因子w1=0.6，w2=0.4。種群數(shù)量設(shè)定為50，迭代次數(shù)gen為500代，保證算法充分進(jìn)行尋優(yōu)搜索。為驗(yàn)證不同算法的設(shè)計(jì)以及不同參數(shù)的選取對(duì)算法尋優(yōu)的影響，引入4種不同的方案進(jìn)行對(duì)比，具體如表5所示。

表2 作業(yè)單元間的單位費(fèi)用 元/m

表3 作業(yè)單元間的搬運(yùn)頻率 次/天

表4 作業(yè)單元間的搬運(yùn)速度 m/s

表5 算法參數(shù)設(shè)定對(duì)比

3.3 優(yōu)化結(jié)果及分析

在MATLAB軟件上運(yùn)行各套算法對(duì)車間布局問(wèn)題進(jìn)行求解，運(yùn)行結(jié)果如圖7所示。從圖7可以看出，各算法在迭代一定代數(shù)之后停止了波動(dòng)，達(dá)到收斂。經(jīng)計(jì)算，方案1至方案3求解得到的最優(yōu)目標(biāo)函數(shù)值分別為0.180、0.175、0.169，本文提出的自適應(yīng)的遺傳模擬退火算法求解得到的最優(yōu)目標(biāo)函數(shù)值為0.158，比普通遺傳算法尋優(yōu)結(jié)果更優(yōu)秀，由本文算法求解得到的最優(yōu)個(gè)體為[5,13,10,1,11,4,3,6,2,8,9,7,12]，其車間作業(yè)單元布局如圖8所示，各作業(yè)單元的位置坐標(biāo)如表6所示。

表6 優(yōu)化后作業(yè)單元位置坐標(biāo)

圖7 算法優(yōu)化過(guò)程迭代圖

圖8 優(yōu)化后車間作業(yè)單元布局

為了評(píng)估優(yōu)化效果，將原布局與優(yōu)化后的布局下的搬運(yùn)費(fèi)用及搬運(yùn)時(shí)間進(jìn)行對(duì)比，如表7所示，對(duì)比發(fā)現(xiàn)優(yōu)化效果顯著。

表7 優(yōu)化前后對(duì)比

4 結(jié)語(yǔ)

針對(duì)車間設(shè)施布局優(yōu)化問(wèn)題，本文以最低車間物流成本與最短車間搬運(yùn)時(shí)間為優(yōu)化目標(biāo)建立數(shù)學(xué)模型，采用自適應(yīng)遺傳模擬退火算法對(duì)問(wèn)題進(jìn)行求解，并通過(guò)4種參數(shù)設(shè)定方案對(duì)比驗(yàn)證了自適應(yīng)策略的算法的優(yōu)越性。給出了FK公司的車間設(shè)施布局優(yōu)化案例，結(jié)果表明，經(jīng)遺傳模擬退火算法優(yōu)化后得到的車間布局方案，相較于原始布局方案，其車間物流成本降低了9.98%，車間搬運(yùn)時(shí)間縮短了20.8%，證明該算法有較強(qiáng)的尋優(yōu)能力，可以為企業(yè)車間生產(chǎn)制造減少浪費(fèi)，提高效率。

在后續(xù)工作中，還需要繼續(xù)結(jié)合其他算法的思路對(duì)算法進(jìn)行改進(jìn)，同時(shí)車間布局?jǐn)?shù)學(xué)模型的復(fù)雜度需結(jié)合實(shí)際情況作進(jìn)一步的完善。