基于改進遺傳算法的航天大型零件車間布局優(yōu)化

何 坤，沈 斌，彭劼?lián)P，王家海，Juergen Fleisher

(同濟大學(xué) a.中德學(xué)院；b.機械與能源工程學(xué)院；c.先進制造技術(shù)中心，上海 201804)

0 引言

設(shè)備布局問題是設(shè)施規(guī)劃中一個重要方面。在提高生產(chǎn)效率的方面，設(shè)施布置設(shè)計被視為提高車間生產(chǎn)力的關(guān)鍵[1]。它對于提高車間生產(chǎn)能力、傳遞信息流和物料流以及降低生產(chǎn)成本和保證生產(chǎn)安全具有十分重要的意義。設(shè)備布局根據(jù)物流設(shè)備的不同，可以分為線性單行布局、線性多行布局、U 型布局、環(huán)型布局。傳統(tǒng)對于設(shè)備的布局一般是：圖論方法、數(shù)學(xué)方法等。但是70年代末，關(guān)于NP問題的理論研究，一些學(xué)者開始轉(zhuǎn)向啟發(fā)式算法用于對NP問題的求解。José Fernando Gon?alves和Mauricio G. C. Resende[2]采用一種偏見隨機密匙遺傳算法進行不等面積布局，目標(biāo)時間少物流量和運輸成本，該混合算法分為有條件版本和無條件版本，因此，在進行計算過程中需要甄別，運算過程復(fù)雜，且只適用于塊狀布局，有一定局限性。Rajesh Matai等[3]使用改進的模擬退火算法來解決多目標(biāo)設(shè)施布局問題，將溫度變化與目標(biāo)值的最大值、最小值和平均值的數(shù)值聯(lián)系起來，但是該改進使過程計算量大，這種方法難以使目標(biāo)正?；土炕繕?biāo)權(quán)重。AkashTayal和Surya PrakashSingh[4]通過大數(shù)據(jù)手段對數(shù)據(jù)進行收集，得到Multi-objective Stochastic Dynamic Facility Layout Problem模型，之后用FA和CSA的混合算法進行對該問題解析，但是，采集的數(shù)據(jù)是否準(zhǔn)確，和對數(shù)據(jù)的處理是否合適，對結(jié)果影響較大。焦曉璇等[5]利用了SA的突跳能力和克服PSO的容易局部最優(yōu)問題，在該基礎(chǔ)上對算法的結(jié)構(gòu)進行優(yōu)化。重慶大學(xué)葉連發(fā)[6]將SLP和PGA算法相結(jié)合用于處理多品種小批量車間布局問題，但是對數(shù)據(jù)分析不夠細(xì)致，容易出現(xiàn)計算過程混亂。關(guān)健和林耿[7]針對單行布局將蟻群算法和爬山法等算法結(jié)合起來，但是其中對蟻群算法適用性分析不夠。

隨著我國對航天事業(yè)的投資力度，產(chǎn)品產(chǎn)量越來越大，原有的車間生產(chǎn)難以滿足日益增多的訂單需求，因此對車間的改造升級越來越重要[8]。本文以某航天所某零件的加工車間為例，使用模擬退火遺傳算法對該車間進行布局評價。首先對該車間特點進行分析，以搬運成本減少和面積利用率最小為目的，轉(zhuǎn)化為布局模型；然后使用改進算法進行優(yōu)化，包含與SA、GA和初始布局的結(jié)果進行比對，驗證該組合算法的優(yōu)勢。

1 方法介紹

1.1 布置方案

本文研究的是給定的車間(長×寬)基礎(chǔ)上，對塊狀設(shè)備區(qū)進行多行布置。其中每一行的寬度由每行中最大寬度設(shè)備塊決定，每一行的長度不能超過車間的總長，當(dāng)布置的一行的總長度超過規(guī)定最長L時就要將設(shè)備放置到另一行。布置過程為從左下角開始，依次向右布置，直到布置完成。如圖1所示。

圖1 設(shè)備布置過程

1.2 多行布局問題的數(shù)學(xué)模型

多行布局是在給定的空間中對于長、寬不同的設(shè)備布局，目的是達到總物料搬運成本最小和面積利用最小。這樣，目標(biāo)函數(shù)模型表達為：

(1)

dij=|xi-xj|+|yi-yj|,ij=1 ,…,n;

(2)

(3)

∑k=1mzik=1,i=1 ,…,n;

(4)

∑i=1nzik≤n,k=1,…,m;

(5)

(6)

yi=max(yk1,yk2,…,yka),a為一行中設(shè)備數(shù)。

(7)

模型中，w和l是設(shè)備空間的寬度和長度，ij表示的是其中的兩個設(shè)備，式(1)中F表示所要求的目標(biāo)函數(shù)值，即是搬運距離(dij)和相應(yīng)的搬運量(fij)以及搬運所需費用(cij)之間的乘積與面積利用率的加權(quán)和，其中c1、c2為權(quán)重因子，并有c1+c2= 1，目的就是求得最小值，St是它的面積利用率；式(2)是兩個工位之間距離計算公式；式(4)表示的是任意一個設(shè)備只能布置在其中的一行中；式(5)表示當(dāng)設(shè)備布置時設(shè)備數(shù)量不能比已經(jīng)布局的設(shè)備數(shù)多；式(6)表示在其中布置的一行當(dāng)中，兩個相鄰的設(shè)備橫坐標(biāo)之間的關(guān)系，式(7)表示在一行中縱坐標(biāo)是在本行中的所有設(shè)備的最大寬度的一半的值。

1.3 SA-GA混合算法

SA-GA算法通過SA和GA的交替使用，即先由SA對初始種群進行處理，然后使用GA進行交叉變異，之后往復(fù)使用兩種算法直到滿足迭代結(jié)束條件。算法利用SA的高效性、魯棒性強的特點[9]和GA的種群特點[10]，克服了遺傳算法過早收斂、局部最優(yōu)，使其收斂速度更快，結(jié)果更好。

流程設(shè)計如圖2所示。

圖2 SA-GA混合算法流程

對算法的改進，初始解對于算法的收斂速度具有重要影響，因此本文采用效率較高的2-opt，3-opt方法進行初始處理。交叉采用經(jīng)典的部分交叉映射(PMX)，采用兩點交叉變異原則，能夠在保證收斂速度的情況下得到較好結(jié)果。

1.4 GA-SA算法對于航天大型零件車間設(shè)計

(1)編碼原則。采用數(shù)字編碼規(guī)則，直接將工位以數(shù)字的格式進行編碼{m1，m2，m3，m4，…，mn}，mi表示第i個工站。

本文對于多行布局進行自動換行，布置完一個設(shè)備即對布置過的長度計算判斷，判斷是否超出車間總長度，若沒有，則計算該行工站坐標(biāo)，否則換行，并將該行最后一個設(shè)備排布到下一行，以此類推。

(2)初始化。采用2-opt，3-opt的方法進行初始化，生成初代種群。

(3)模擬退化過程。在模擬退火算法中產(chǎn)生的新個體采用Metropolis接受準(zhǔn)則來確定，將種群中每個個體進行模擬退火操作，然后生成一個新的種群。

(4)選擇規(guī)則。采用輪盤賭的選擇原則選取下一代種群。

(5)交叉原則。采用部分交叉映射(PMX)的方法處理排序交叉。

(6)變異原則。采用兩點變異原則實施。

(7)適應(yīng)度函數(shù)。以物流總費用(Handling Cost)和面積利用率作為組合優(yōu)化目標(biāo)。

2 實例驗證和結(jié)果分析

對該航天大型零件車間，一共有16個工位。車間大小為120m×40m，工位面積、頻率如表1、表2所示。

表1 工位區(qū)域面積m×m

表2 工件搬運頻率

圖3 各工站輸出物流量

對于該航天大型零件車間布局過程中，工位1、2、3是有約束關(guān)系，因此是固定的。以Visual Studio 2012為編程環(huán)境，使用C#語言，選定如下算法參數(shù)，模擬退化操作：溫度T=200，衰減參數(shù)0.95，馬可夫鏈長度1000，步長為1；遺傳算法：總運行次數(shù)MaxTime=100，種群數(shù)量popsize=10，交叉率CrossRate= 0.8，變異率MutateRate-0.2，c1=0.6，c2=0.4分別使用模擬退化算法、遺傳算法、模擬退火遺傳算法得出如圖4所示。

圖4 SA-GA與SA、GA 收斂對比圖

由圖可知，混合算法在大約85代獲得最優(yōu)值，同時可以到出SA初始收斂較快，但是整體較慢。在收斂速度還是在結(jié)果上面都優(yōu)于單獨使用的算法。初始布局是(1，2，3；11，13，7，6，10，5；16，14，15，8，4，9，12)得到的物流量結(jié)果是29440，而優(yōu)化后的布局是(1，2，3；5，16，4，9，13，7，15，12；14，10，8，11，6)，相應(yīng)的物流量結(jié)果為17324，效率提高了41%，因此該算法能夠很好的解決此問題。

3 結(jié)束語

本文中針對設(shè)備布局問題建立數(shù)學(xué)模型，針對單一算法的缺點引入模擬退火遺傳算法(SA-GA)對遺傳算法進行改進，利用該混合算法對一個實際規(guī)劃問題進行優(yōu)化，明顯提高了企業(yè)生產(chǎn)效率，因此，在NP問題上對啟發(fā)式算法的研究和改進方式提供了參考思路，特別是對遺傳算法進行改進，將非種群算法與種群算法的結(jié)合，文中的混合算法在85代左右得出最優(yōu)結(jié)果，而另兩個算法的結(jié)果較混合算法較差，因此，擴展了改進思路，同時在非種群算法(如模擬退火算法)的研究上，可以進行種群化分析，以此提高收斂速率和最優(yōu)結(jié)果。

[1] Tarkesh H, Atighehchian A, Nookabadi A S. Facility layout design using virtual multi-agent system[J]. Journal of Intelligent Manufacturing, 2009, 20(4): 347.

[2] Gon?alves J F,Resende M G C. A biased random-key genetic algorithm for the unequal area facility layout problem[J].European Journal of Operational Research, 2015, 246(1): 86-107.

[3] Matai R, Singh S P, Mittal M L. Modified simulated annealing based approach for multi objective facility layout problem[J].International Journal of Production Research, 2013, 51(14): 4273-4288.

[4] Tayal A, Singh S P. Integrating big data analytic and hybrid firefly-chaotic simulated annealing approach for facility layout problem[J]. Annals of Operations Research, 2016:1-26.

[5] 焦曉璇, 景博, 黃以鋒, 等. 基于模擬退火離散粒子群算法的測試點優(yōu)化[J]. 計算機應(yīng)用, 2014, 34(6): 1649-1652.

[6] 葉連發(fā). 基于 SLP 與 PGA 的多品種小批量生產(chǎn)車間設(shè)施布局優(yōu)化研究[D]. 重慶:重慶大學(xué), 2012.

[7] 關(guān)健, 林耿. 改進蟻群算法求解單行設(shè)施布局問題[J]. 吉林大學(xué)學(xué)報 (信息科學(xué)版), 2016,34 (4): 528-535.

[8] 郭具濤, 楊長祺, 李中權(quán), 等. 航天大型薄壁結(jié)構(gòu)件智能生產(chǎn)系統(tǒng)研究[J]. 航天制造技術(shù), 2015(5):11-14,22.

[9] 宛劍業(yè), 張飛超, 高麗媛,等. 基于遺傳模擬退火算法的車間布局規(guī)劃研究[J]. 遼寧工業(yè)大學(xué)學(xué)報: 自然科學(xué)版, 2016, 36(1): 35-39.

[10] 羅宜美, 黃小榮. 基于遺傳算法的連續(xù)型設(shè)備布置優(yōu)化[J].工業(yè)工程, 2007, 10(6): 131-134.