基于改進(jìn)遺傳算法的瀝青路面再生工廠布局優(yōu)化

肖子豪,郭小宏

(重慶交通大學(xué)經(jīng)濟(jì)與管理學(xué)院,重慶 400074)

在瀝青路面再生工廠規(guī)劃建設(shè)過程中,車間布局是一個(gè)重要卻又復(fù)雜的部分。不僅各功能單元的相互關(guān)系、物料搬運(yùn)距離會(huì)對(duì)布局規(guī)劃產(chǎn)生影響,而且各功能單元的布置方式也會(huì)對(duì)布局產(chǎn)生制約。僅使用傳統(tǒng)的方法,比如分支定界法[1]、割平面法[2]和系統(tǒng)布局規(guī)劃法[3](system layout planning, SLP),解決多個(gè)功能單元的布局規(guī)劃問題時(shí)效率很低[4],只能完成規(guī)模較小的布置組合內(nèi)容。車間布局優(yōu)化在降低車間物料搬運(yùn)成本及提高生產(chǎn)效率方面起到了重要的作用[5]。近年來,智能算法作為主要研究手段被廣泛應(yīng)用于車間布局優(yōu)化的研究中。周潤博[6]、謝暉[7]利用遺傳算法結(jié)合SLP法,以物流成本最小和功能區(qū)相關(guān)性最大為目標(biāo)對(duì)公司生產(chǎn)車間進(jìn)行布局優(yōu)化,有效縮短了物料搬運(yùn)距離,提高了企業(yè)的生產(chǎn)效率。張廣泰等[8]融合熵權(quán)-逼近理想解排序法,基于遺傳算法對(duì)SLP法進(jìn)行了改進(jìn),提高了車間布局的非物流關(guān)系強(qiáng)度。趙歡[9]采用剩余矩形排樣算法和遺傳算法,考慮設(shè)備布局與總體布局的耦合得到二次優(yōu)化布局,減少了廠區(qū)總體布局費(fèi)用。盧義楨等[10]引入自適應(yīng)遺傳算子策略,提出改進(jìn)的遺傳模擬退火算法求解模型,有效降低了物流成本和縮短了搬運(yùn)時(shí)間。董舒豪等[11]采用遺傳模擬退火算法,針對(duì)多行設(shè)施布局優(yōu)化模型,進(jìn)行分段編碼并以實(shí)例驗(yàn)證了其優(yōu)越性。伍義[12]、李孟雪[13]、楊雅楠[14]采用遺傳算法及遺傳模擬退火算法,以非物流相關(guān)性最大、物流成本最小、碳排放最少為目標(biāo)得到了布局優(yōu)化方案。但是,目前針對(duì)再生工廠車間布局優(yōu)化問題所采用的遺傳算法仍存在一些不足:1)再生工廠的各個(gè)功能單元并非成行布置,其放置位置受到車間邊界、功能單元間距約束的影響。現(xiàn)有算法采用間接編碼方式,各功能單元的布置位置信息表達(dá)不直觀,編碼解碼復(fù)雜度高,影響了算法的效率;2)現(xiàn)有遺傳算法針對(duì)初始種群的設(shè)定方法并不明確,對(duì)于種群的優(yōu)化方法欠佳使得算法的全局搜索能力不強(qiáng),易陷入局部最優(yōu)。

基于此,筆者采用實(shí)數(shù)分層編碼,分為坐標(biāo)層和放置方式層,分別對(duì)應(yīng)各車間的坐標(biāo)及放置狀態(tài),使信息表達(dá)更加直觀,降低編碼難度,減少求解時(shí)間;并針對(duì)初始布局進(jìn)行排列組合得到初始種群,提高設(shè)定效率,增加其多樣性。坐標(biāo)層采用多點(diǎn)變異,放置方式層采用單點(diǎn)變異,引入模擬退火算子,增加了繁殖更優(yōu)個(gè)體的概率,提高了算法的局部搜索性能。

1 工廠布局相關(guān)概念和數(shù)學(xué)模型

1.1 功能單元?jiǎng)澐峙c聯(lián)系

瀝青路面再生工廠的工藝流程為將回收的RAP料進(jìn)行破碎篩分,得到不同粒徑的基準(zhǔn)料,烘干后按一定的比例與新集料、粉料、瀝青和再生劑進(jìn)行混合攪拌,最終得到再生成品料。按加工對(duì)象,對(duì)生產(chǎn)設(shè)備進(jìn)行分類組合實(shí)現(xiàn)功能單元的劃分,如表1所示,再根據(jù)工藝關(guān)系梳理各功能單元之間的聯(lián)系,如圖1所示。

圖1 功能單元聯(lián)系圖Fig.1 Contact diagram of functional unit

表1 瀝青路面再生工廠的功能單元?jiǎng)澐?/p>

1.2 功能單元位置信息表示

再生工廠車間布局是指按照一定約束,在給定的布局范圍內(nèi)對(duì)各個(gè)功能單元進(jìn)行合理布置,從而達(dá)成多目標(biāo)的協(xié)調(diào)。需布局的車間范圍在一個(gè)長為L,寬為W的矩形內(nèi)部,車間左下角為坐標(biāo)原點(diǎn)。各功能單元的形狀假定為矩形,均平行于X軸或Y軸放置,功能單元之間保持一定的活動(dòng)距離,其位置信息指矩形中心的橫、縱坐標(biāo),放置方式是指其平行于X軸或Y軸放置,表示為

(x1,x2,…,xj,…,xn-1,xn),

(1)

(y1,y2,…,yj,…,yn-1,yn),

(2)

(z1,z2,…,zj,…,zn-1,zn)。

(3)

式(1)—式(3)中:xn表示第n個(gè)功能單元的橫坐標(biāo);yn表示第n個(gè)功能單元的縱坐標(biāo);zn表示第n個(gè)功能單元的放置方式;xj,yj,zj分別表示第j個(gè)功能單元的橫坐標(biāo)、縱坐標(biāo)、放置方式。

車間和功能單元的布局模型如圖2所示,其中:Fi,Fj,Fk為功能單元代號(hào);lj為某功能單元的長度;wj為某功能單元的寬度;sx,sy為功能單元在X軸、Y軸方向上與車間邊界的活動(dòng)間距;sxf,syf為2個(gè)功能單元之間在X軸、Y軸方向上的安全間距;L為車間長度;W為車間寬度。

圖2 車間和功能單元布局模型圖Fig.2 Layout model of workshop and functional units

1.3 方向約束

當(dāng)功能單元的長邊平行于X軸時(shí),將其視為橫向放置;當(dāng)功能單元的長邊平行于Y軸時(shí),將其視為豎向放置。

(4)

功能單元的放置方式如圖3所示。

圖3 功能單元的放置方式示例Fig.3 Example of how functional units are placed

1.4 邊界約束

功能單元的布置位置應(yīng)落在車間范圍內(nèi),且與車間邊界保持一定的間距。

(5)

1.5 間距約束

車間內(nèi)部的任意功能單元之間互不重合,在X軸或Y軸方向上至少保留大小為sxf或syf的間距,且每個(gè)功能單元只能被布置1次。

Ujk×Vjk=0,

(6)

(7)

(8)

式(6)—式(8)中:Ujk表示判斷j功能單元和k功能單元在X軸方向上是否重疊;Vjk表示判斷j功能單元和k功能單元在Y軸方向上是否重疊。

1.6 目標(biāo)函數(shù)

車間布局優(yōu)化以非物流關(guān)系強(qiáng)度最大、物流成本最小及碳排放最少為目標(biāo),其具體計(jì)算方式參考文獻(xiàn)[15],目標(biāo)函數(shù)設(shè)定如下:

(9)

式中:D表示目標(biāo)函數(shù)值;a1表示非物流關(guān)系強(qiáng)度權(quán)重;D1表示非物流關(guān)系強(qiáng)度值;D1max表示非物流關(guān)系強(qiáng)度最大值;a2表示物料搬運(yùn)成本權(quán)重;D2表示物流成本值;D2max表示物料搬運(yùn)成本最大值;a3表示碳排放權(quán)重;D3表示碳排放值;D3max表示碳排放最大值。

2 改進(jìn)遺傳算法

2.1 實(shí)數(shù)分層編碼

遺傳算法的編碼和解碼方法很大程度上決定了算法的可行性和效率,因此設(shè)計(jì)適宜的編碼和解碼方法極為重要。針對(duì)再生工廠車間布局問題,采用傳統(tǒng)的二進(jìn)制編碼會(huì)使種群個(gè)體過于冗長,且不同位置的個(gè)體在十進(jìn)制編碼轉(zhuǎn)換為二進(jìn)制編碼時(shí)長度可能不一致,導(dǎo)致編碼過于復(fù)雜。為解決傳統(tǒng)遺傳算法在布置位置和放置方式表示問題上的不足,提出實(shí)數(shù)分層編碼方法,在降低編碼難度的同時(shí),能夠直觀表示各功能單元的布置位置和放置方式。用分層編碼的方式映射3個(gè)決策層(橫坐標(biāo)層、縱坐標(biāo)層以及放置方式層)共同對(duì)目標(biāo)函數(shù)產(chǎn)生的影響。

圖4所示為實(shí)數(shù)分層編碼示例。第1層為橫坐標(biāo)層,實(shí)數(shù)表示功能單元在車間布局范圍內(nèi)的橫坐標(biāo);第2層為縱坐標(biāo)層,實(shí)數(shù)表示功能單元在車間布局范圍內(nèi)的縱坐標(biāo);第3層為放置方式層,反映各功能單元的放置方式:數(shù)字1表示該功能單元橫向放置,數(shù)字0表示豎向放置。

圖4 實(shí)數(shù)分層編碼示例Fig.4 Example of real number layered coding

實(shí)數(shù)分層編碼的解碼方式相對(duì)簡便,只需將橫坐標(biāo)層、縱坐標(biāo)層以及放置方式層中的數(shù)字按編碼順序列出。圖4所示的再生工廠車間布局方案解碼輸出結(jié)果如表2所示。

表2 布局方案解碼輸出結(jié)果

2.2 初始種群設(shè)定

由于再生工廠車間布局的范圍偏大、功能單元數(shù)量偏多,采用車間邊界內(nèi)隨機(jī)生成功能單元布置位置的方法效率低下。提出基于初始方案的排列組合方法,將初始方案作為初始種群之一,其余種群個(gè)體采用各功能單元橫、縱坐標(biāo)和放置方式交換的方法得到。由于生成1～12的全排列數(shù)組數(shù)量超出MATLAB軟件行數(shù)范圍,遂生成1～6和7～12的2個(gè)全排列數(shù)組,對(duì)其進(jìn)行排列組合并將順序與初始布局方案相同的數(shù)組剔除,從而得到1～12的排列數(shù)組。將初始方案按該數(shù)組排列放置,通過判斷得到的方案是否符合約束條件,并計(jì)算符合約束條件方案的目標(biāo)函數(shù)值,從中篩選出剩余的種群個(gè)體,保證初始種群個(gè)體的有效性,增加初始種群個(gè)體的多樣性。

2.3 交叉算子

交叉算子是產(chǎn)生新個(gè)體的主要方式,在算法中起核心作用,決定了算法的性能優(yōu)劣。在交叉操作中,染色體的前2行作為交換的基本單元,即橫坐標(biāo)層和縱坐標(biāo)層進(jìn)行算術(shù)交叉,放置方式層不進(jìn)行交叉,這能夠保證子代與父代的放置方式一致。編碼交叉操作示例如圖5所示,圖中α=0.2,具體步驟如下。

圖5 編碼交叉操作示例圖Fig.5 Example diagram of coding cross operation

步驟1 從種群中選擇相鄰的2條染色體,提取其橫坐標(biāo)層和縱坐標(biāo)層作為父代基因P1和P2。

步驟2 將父代基因P1和P2進(jìn)行算術(shù)交叉,生成2個(gè)子代基因O1和O2。算術(shù)表達(dá)式為

O1=α×P1+(1-α)×P2,

(10)

O2=(1-α)×P1+α×P2,

(11)

式中:α表示(-0.5,1.5)內(nèi)的隨機(jī)數(shù)。

步驟3 將生成的子代基因O1和O2分別與父代染色體P1和P2的放置方式層基因結(jié)合,得到2個(gè)新的種群個(gè)體。

2.4 變異算子

變異算子任意改變所選染色體的一個(gè)或多個(gè)基因,以增加種群的結(jié)構(gòu)可變性,能防止算法過早收斂。針對(duì)坐標(biāo)層,引入模擬退火算子,在迭代初期,于全局范圍內(nèi)搜索最優(yōu)值。隨著迭代次數(shù)的增加,搜索范圍逐漸減小,便于尋找近似最優(yōu)解的精確解,提高算法的搜索效率。對(duì)于放置方式層,采用單點(diǎn)變異的方式。

1)橫坐標(biāo)層、縱坐標(biāo)層的變異

示例如圖6所示,具體步驟如下。

圖6 橫坐標(biāo)層和縱坐標(biāo)層變異示例圖Fig.6 Example diagram of horizontal and vertical coordinate layer variation

步驟1 生成2個(gè)(0,1)范圍內(nèi)的1×12隨機(jī)數(shù)列矩陣,找出數(shù)值小于變異概率的位置下標(biāo)并標(biāo)記。

步驟2 對(duì)橫坐標(biāo)層和縱坐標(biāo)層標(biāo)記位置的數(shù)據(jù)進(jìn)行變異,變異公式如下:

a=a+a×b×0.95gen,

(12)

式中:a表示橫坐標(biāo)層和縱坐標(biāo)層標(biāo)記位置的數(shù)據(jù);b表示(-1,1)內(nèi)的一個(gè)隨機(jī)數(shù);gen表示迭代次數(shù)。圖中b取-0.5,gen取1。

步驟3 將變異后的數(shù)據(jù)作為基因?qū)?yīng)標(biāo)記位置放回染色體內(nèi)。

2)放置方式層的變異

放置方式層采用單點(diǎn)變異,示例如圖7所示,具體步驟如下。

圖7 放置方式層變異示例圖Fig.7 Example diagram of placement method layer variation

步驟1 生成[1,12]范圍內(nèi)的一個(gè)隨機(jī)整數(shù),找出該整數(shù)對(duì)應(yīng)放置方式層的位置下標(biāo)并標(biāo)記。

步驟2 對(duì)放置方式層標(biāo)記位置的數(shù)據(jù)進(jìn)行變異,變異公式如下:

(13)

式中:c表示放置方式層標(biāo)記位置的數(shù)據(jù)。

步驟3 將變異后的數(shù)據(jù)作為基因?qū)?yīng)標(biāo)記位置放回染色體內(nèi)。

將變異后的橫坐標(biāo)層、縱坐標(biāo)層和放置方式層基因組合,得到新的種群個(gè)體。

2.5 改進(jìn)遺傳算法實(shí)現(xiàn)步驟

傳統(tǒng)的車間布局遺傳算法編碼復(fù)雜,增加了解碼的難度和時(shí)間,布局位置和放置方式信息表達(dá)不夠直觀,且搜索算子設(shè)置單一,導(dǎo)致算法的尋優(yōu)能力不足。本文針對(duì)傳統(tǒng)遺傳算法進(jìn)行改進(jìn),提出實(shí)數(shù)分層編碼方法,引入模擬退火算子,清晰表達(dá)功能單元的布局位置和放置方式信息,增強(qiáng)算法尋求最優(yōu)解的能力,具體步驟如下。

步驟1 根據(jù)再生工廠車間布局的約束,基于初始布局方案得到滿足約束條件的初始種群個(gè)體。

步驟2 計(jì)算種群個(gè)體的適應(yīng)度函數(shù)值,采用輪盤賭方法進(jìn)行種群個(gè)體的選擇。

步驟3 依次選擇相鄰的2個(gè)種群個(gè)體,將其橫坐標(biāo)層、縱坐標(biāo)層作為父代基因進(jìn)行交叉,之后與父代的放置方式層基因結(jié)合,得到新的種群個(gè)體。

步驟4 根據(jù)變異概率,對(duì)種群個(gè)體依次進(jìn)行橫坐標(biāo)層、縱坐標(biāo)層和放置方式層變異,得到新的種群個(gè)體。

步驟5 計(jì)算新種群中個(gè)體的目標(biāo)函數(shù)值,對(duì)目標(biāo)函數(shù)值進(jìn)行排序。保留部分優(yōu)秀個(gè)體,并將其與父代染色體中優(yōu)秀的個(gè)體結(jié)合,形成新的種群。

步驟6 判斷迭代次數(shù)是否滿足算法終止條件。是則輸出計(jì)算結(jié)果,否則返回步驟2。

3 實(shí)例驗(yàn)證

為驗(yàn)證改進(jìn)算法的有效性,以某瀝青路面再生工廠為研究對(duì)象。該再生工廠車間的長L=180 m,寬W=150 m,生產(chǎn)大門位于(0,118),各功能單元均位于布局范圍內(nèi),且與車間邊界的間距sx,sy均大于或等于5 m。各功能單元尺寸、布局位置與車間邊界的間距如表3所示,初始布局方案如圖8所示。

圖8 初始布局方案圖Fig.8 Plan of initial layout

表3 功能單元信息

利用MATLAB 2016a完成改進(jìn)遺傳算法的編寫。設(shè)置初始種群規(guī)模大小NIND=200、變異概率Pm=0.2、最大迭代次數(shù)MAXGEN=200。通過算法進(jìn)行求解,得到如下結(jié)果:優(yōu)化后的目標(biāo)函數(shù)值為0.423 3,優(yōu)化后的布局位置和放置方式如表4所示。

表4 優(yōu)化后功能單元布局位置和放置方式表

將原始布局方案與優(yōu)化布局方案數(shù)據(jù)依照優(yōu)化目標(biāo)計(jì)算,得到相應(yīng)結(jié)果,其對(duì)比如表5所示。

表5 方案優(yōu)化前后效果對(duì)比

根據(jù)表5對(duì)比結(jié)果可知,優(yōu)化后的布局方案中各功能單元的非物流關(guān)系強(qiáng)度提高7.96,每日物料搬運(yùn)成本減少14 468.85元,每日碳排放減少30.59 kg。

為驗(yàn)證文中算法的有效性,將傳統(tǒng)遺傳算法、文獻(xiàn)[14]中的遺傳算法應(yīng)用于該實(shí)例并進(jìn)行比較,迭代過程如圖9所示,3種算法得到的目標(biāo)函數(shù)值與迭代次數(shù)的對(duì)比如表6所示。

圖9 算法迭代過程Fig.9 Process of algorithm iteration

表6 迭代結(jié)果對(duì)比

從表6對(duì)比3種算法迭代結(jié)果可知,改進(jìn)后的遺傳算法較傳統(tǒng)遺傳算法迭代次數(shù)減少34次,目標(biāo)函數(shù)值減少0.012 8,較文獻(xiàn)[14]中遺傳算法迭代次數(shù)相近,目標(biāo)函數(shù)值減少0.009 9。

4 結(jié) 語

筆者針對(duì)瀝青路面再生工廠布局優(yōu)化,采用遺傳算法對(duì)其初始種群設(shè)定方式、編碼方式與交叉和變異方式進(jìn)行明確及改進(jìn),得到如下結(jié)論。

1)采用實(shí)數(shù)分層編碼,以功能單元布局位置的橫、縱坐標(biāo)和放置方式代替?zhèn)鹘y(tǒng)的二進(jìn)制編碼,增強(qiáng)了布局位置信息表示的直觀性,降低了解碼復(fù)雜度,減少了算法求解時(shí)間,提高了運(yùn)行效率。

2)基于初始布局方案,采用排列組合得到初始種群,增加了初始種群的多樣性。

3)針對(duì)算法的變異引入模擬退火算子,使得尋優(yōu)能力提升,從而可以高效地對(duì)布局方案進(jìn)行優(yōu)化。

4)實(shí)例表明,改進(jìn)后的遺傳算法較傳統(tǒng)遺傳算法迭代次數(shù)減少34次,目標(biāo)函數(shù)值減少0.012 8,較文獻(xiàn)[14]中目標(biāo)函數(shù)值減少0.009 9。優(yōu)化后的布局方案中,每日物料搬運(yùn)成本減少14 468.85元,碳排放減少30.59 kg。改進(jìn)后的方法可為瀝青路面再生工廠布局優(yōu)化提供參考與技術(shù)支持。

本文利用MATLAB僅生成了1～12全排列的部分?jǐn)?shù)組,未生成全部數(shù)組,今后可完善全部數(shù)組以豐富初始種群,增加其多樣性,并利用約束條件篩選出更為優(yōu)秀的種群個(gè)體,從而提高算法的尋優(yōu)能力。此外,本文的研究僅引入模擬退火算子,后續(xù)可引入其他算子,并針對(duì)再生工廠布局優(yōu)化算法進(jìn)行改進(jìn)。