遺傳算法在車間設(shè)施布局優(yōu)化中的應(yīng)用

孫檜茹 馮國紅

（東北林業(yè)大學(xué)，黑龍江 哈爾濱 150000）

0 引言

車間設(shè)施布局是制造系統(tǒng)的重要組成，對(duì)生產(chǎn)系統(tǒng)的運(yùn)行質(zhì)量產(chǎn)生直接影響[1]。合理的車間設(shè)施布局可以降低物流成本，對(duì)提高企業(yè)生產(chǎn)效率和企業(yè)綜合競爭力有積極作用?；诩扔醒芯拷Y(jié)果表明，車間設(shè)施布局欠佳產(chǎn)生的費(fèi)用占總運(yùn)行費(fèi)用的30%~48%，通過車間設(shè)施布局優(yōu)化可以降低10%~25%，有必要深入研究車間的設(shè)施布局優(yōu)化。該文以實(shí)踐應(yīng)用為視角，闡述了車間設(shè)備布局原理，分析了存在的問題并使用遺傳算法優(yōu)化車間設(shè)施布局，使用Flexsim軟件進(jìn)行仿真評(píng)價(jià)，希望為企業(yè)的車間設(shè)施布局優(yōu)化提供參考。

1 車間設(shè)備布局理論

車間設(shè)施布局是企業(yè)對(duì)生產(chǎn)車間內(nèi)部各個(gè)主要生產(chǎn)設(shè)備、輔助設(shè)備進(jìn)行統(tǒng)籌規(guī)劃并合理安排其相應(yīng)位置與面積等，進(jìn)而實(shí)現(xiàn)信息流、物流等生產(chǎn)系統(tǒng)各工作車間通暢的實(shí)踐方式[2]。設(shè)施布局指的是對(duì)車間的空間進(jìn)行重新布局，可以實(shí)現(xiàn)車間設(shè)備的有效組合，提高生產(chǎn)效率，實(shí)現(xiàn)經(jīng)濟(jì)效益最大化。車間設(shè)施布局應(yīng)該與生產(chǎn)制造系統(tǒng)整體及工作緊密聯(lián)系、相輔相成，應(yīng)該充分考慮工藝設(shè)計(jì)、產(chǎn)品設(shè)計(jì)和物流系統(tǒng)設(shè)計(jì)，物流系統(tǒng)會(huì)對(duì)布局形式產(chǎn)生影響，當(dāng)設(shè)計(jì)時(shí)應(yīng)以最大限度減少物流環(huán)節(jié)為主要原則，確保設(shè)計(jì)的物流系統(tǒng)的合理性，減少搬運(yùn)成本，增加物料處理時(shí)間。

2 車間設(shè)備布局問題概述

以某公司的連桿生產(chǎn)線布局圖35 m×20 m的車間為例，其間共分布不同面積的工作區(qū)共16個(gè)，工作區(qū)大小、在制品搬運(yùn)頻率與搬運(yùn)距離見表1。由此可知，各個(gè)工作區(qū)在制品的搬運(yùn)頻率與搬運(yùn)距離具有顯著的不均衡性，形成時(shí)間和成本的巨大浪費(fèi)，該公司生產(chǎn)綱領(lǐng)為月產(chǎn)量1.2萬件，工作日日平產(chǎn)552件，當(dāng)前該車間最大日產(chǎn)量是350件，遠(yuǎn)不能滿足生產(chǎn)綱領(lǐng)要求，須優(yōu)化配置車間布局，實(shí)現(xiàn)生產(chǎn)效率提高并節(jié)約物流成本。

表1 工作區(qū)大小及在制品搬運(yùn)頻率與搬運(yùn)距離表

3 遺傳算法原理及基本流程

遺傳算法模擬了生物遺傳進(jìn)化論，堅(jiān)持優(yōu)勝劣汰的原則，即在遺傳過程中，能夠適應(yīng)遺傳環(huán)境的個(gè)體得以保留并繼續(xù)進(jìn)行遺傳操作，淘汰無法適應(yīng)遺傳環(huán)境的個(gè)體[3]。經(jīng)過層層篩選，最優(yōu)個(gè)體陸續(xù)得到繁殖，下一代繼續(xù)重復(fù)上述步驟，當(dāng)滿足終止條件后，遺傳過程將停止，所得結(jié)果即為最優(yōu)[4]。其工序如下。

明確問題展現(xiàn)方案：確定優(yōu)化對(duì)象有助于解決求助問題，即確定相關(guān)變量、約束條件和目標(biāo)函數(shù)等參數(shù)，奠定編碼基礎(chǔ)。

編碼：將待求解問題解空間向遺傳算法的搜索空間轉(zhuǎn)換的過程即為編碼，便于求解。編碼的常見方式有一般數(shù)據(jù)結(jié)構(gòu)編碼、實(shí)數(shù)編碼、二進(jìn)制編碼及格雷碼編碼等[5]。遺傳算法最關(guān)鍵的一步是編碼，其決定了遺傳算法的搜索結(jié)果和速度。應(yīng)該根據(jù)具體問題選擇編碼方式，這對(duì)該算法具有重要意義。

初始物種產(chǎn)生：其問題的最初解即結(jié)束編碼，產(chǎn)生初始種群。影響其規(guī)模求解速度的是隨機(jī)產(chǎn)生的初級(jí)種群。最優(yōu)解無法主導(dǎo)全體進(jìn)化方向的原因往往是種族規(guī)模過大；遺傳算法過早是因?yàn)榉N群過小，這會(huì)影響到求解結(jié)果的準(zhǔn)確度。適種族規(guī)模的妥當(dāng)選擇十分重要，通常選取30~100為宜。

計(jì)算適應(yīng)度：即為相對(duì)應(yīng)值某染色體相較的種群優(yōu)劣，可用適應(yīng)度函數(shù)來計(jì)算個(gè)人適應(yīng)度值，如果進(jìn)行下一步遺傳操作，需要較高適應(yīng)度。

操作選擇：該步驟是優(yōu)勝劣汰群體中的個(gè)體頭的過程，高適應(yīng)度個(gè)體繼續(xù)遺傳至下一代群體的概率遠(yuǎn)高于低適應(yīng)度個(gè)體。進(jìn)行選擇通常是為了將高適應(yīng)度個(gè)體選擇出來，參與進(jìn)一步操作。

交叉操作：產(chǎn)生新個(gè)體的主要方法是遺傳算法中的交叉，根據(jù)上一步交叉概率任意選出的兩個(gè)個(gè)體中相同基因位置進(jìn)行交叉操作。交叉概率為0.4~0.99[6]，根據(jù)待求解問題選擇合適參數(shù)。

變異操作：變異是當(dāng)進(jìn)化時(shí)輔助新個(gè)體產(chǎn)生的方式，發(fā)生率雖低卻必須存在，新個(gè)體微調(diào)通過交叉算子的方式產(chǎn)生，提高種群多樣性，遺傳算法中交叉算子的全局搜索能力起決定作用，同時(shí)使其具備部分搜索功能，防止部分最優(yōu)情況的出現(xiàn)。將0.0001~0.1設(shè)置為變異概率，防止變異概率較大而產(chǎn)生遺傳算法運(yùn)算量壓力[7]。在實(shí)際遺傳中，后續(xù)應(yīng)設(shè)置恰當(dāng)?shù)淖儺惛怕蕘碓O(shè)置遺傳算法參數(shù)，防止遺傳基因的變異概率較低，經(jīng)過遺傳算子操作可以得到新種群，然后返回至選擇操作。

4 車間設(shè)施布局?jǐn)?shù)學(xué)模型

考慮設(shè)施實(shí)際布局的復(fù)雜性，假定車間和各個(gè)機(jī)床為長方形，數(shù)據(jù)收集均按照長方形的長和寬量取；機(jī)床位置與廠房呈平行位置；連桿在制品在兩個(gè)設(shè)備之間的流動(dòng)只能按照水平和豎直方向；設(shè)施間物流方向不與物流搬運(yùn)費(fèi)發(fā)生關(guān)系[8]。將生產(chǎn)車間左下角設(shè)置為坐標(biāo)原點(diǎn)，結(jié)合模型約束條件來建立數(shù)學(xué)模型，如圖1所示。

圖1 車間設(shè)施布局?jǐn)?shù)學(xué)模型

圖1中，mi為機(jī)床；Li和Wi為機(jī)床的長度與寬度；Dxij和Dyij為機(jī)床在X軸方向和Y軸方向上的最小間距；xi、xj、yi和yj為工作區(qū)的中心坐標(biāo)。

當(dāng)進(jìn)行生產(chǎn)線布局時(shí)，物流費(fèi)用作為目標(biāo)函數(shù)來評(píng)價(jià)布局效果，目標(biāo)值越小表明布局效果越好，可行性越高，如公式（1）和公式（2）所示。

式中：C為總物流費(fèi)用；Pij為單位距離物流搬運(yùn)費(fèi)用；Qij為工作區(qū)i和j間物料搬運(yùn)頻率；Dij為工作區(qū)i和j間的搬運(yùn)距離。

5 遺傳算法求解

車間的設(shè)施數(shù)量直接影響布置方案數(shù)量，設(shè)施多則布置方案復(fù)雜程度高，由于一般線性算法難以對(duì)車間內(nèi)設(shè)施布置優(yōu)化問題求解，因此使用遺傳算法計(jì)算。

5.1 編碼

首先將編碼問題解決在進(jìn)行遺傳算法的運(yùn)用，決定編碼方式的是問題類型，在遺傳算法中對(duì)遺傳算子操作方式產(chǎn)生直接影響的是編碼的質(zhì)量。會(huì)降低群體的穩(wěn)定性及其精準(zhǔn)度低是因運(yùn)用傳統(tǒng)的編碼方式進(jìn)行遺傳計(jì)算。該文包括為目標(biāo)組合優(yōu)化問題使車間設(shè)備的問題，屬非線性規(guī)劃問題，其目標(biāo)函數(shù)具有非連續(xù)性，解空間離散，應(yīng)該結(jié)合實(shí)際情況選擇編碼方式[9]。該文選擇等間距實(shí)數(shù)編碼方式，將設(shè)備最間距設(shè)定為1 m，根據(jù)車間需要布置設(shè)備，兩者相結(jié)合即為該文所使用的編碼方式，即混合編碼方式，如公式（3）所示。

式中：mn為第n臺(tái)機(jī)床；s=1為設(shè)備間距為1m。

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

在具體應(yīng)用遺傳算法的過程中，一個(gè)個(gè)體的優(yōu)良須靠個(gè)體適應(yīng)度值的大小來評(píng)價(jià)。在計(jì)算過程中，適應(yīng)度值大的個(gè)體被遺傳到下一代的可能性較大；適應(yīng)度值越小，個(gè)體被遺傳到下一代的概率越小。遺傳算法優(yōu)化進(jìn)程的重要依據(jù)是適應(yīng)度函數(shù)。例如在存在約束條件下的求解優(yōu)化進(jìn)程中，須先建一個(gè)無限制的函數(shù)，再將該函數(shù)轉(zhuǎn)變成適應(yīng)度函數(shù)，方便用于遺傳算法。

該文設(shè)置適應(yīng)度函數(shù)公式如公式（4）所示。

式中：T為不合理懲罰函數(shù)。

根據(jù)公式計(jì)算，可知各個(gè)工作區(qū)中心點(diǎn)的位置坐標(biāo)，見表2。

表2 各個(gè)工作區(qū)中心點(diǎn)位置坐標(biāo)

該布局結(jié)果最終計(jì)算所得搬運(yùn)費(fèi)為4505.26元，相比優(yōu)化前降低了3434.56元。

6 遺傳算子操作

6.1 選擇

判斷種群的進(jìn)化方向是遺傳算子的操作目標(biāo)。完成遺傳的方式是在父代種群中選擇優(yōu)秀的個(gè)體，在下一代群體中進(jìn)行復(fù)制，淘汰適應(yīng)度較低的父體中的算子。根據(jù)算子的計(jì)劃進(jìn)程選擇遺傳算法操作，能保證遺傳基因的優(yōu)良是需進(jìn)行多次積累和選擇的。不同問題選擇的操作方法、性質(zhì)及功能均不相同，為了解決該文存在的問題，可以采取精英保留法、輪盤賭法及確定式采樣選擇等方法。最終，該文確定使用輪盤賭法操作，假定個(gè)體適應(yīng)度值為fi，某群體大小為能n，則遺傳至子代與被選擇的個(gè)體概率如公式（5）所示。

分析公式（5）可知，較高概率遺傳到下一代的個(gè)體是種群中適應(yīng)度值較高的，這一特征與遺傳算法特點(diǎn)相吻合。

6.2 交叉算子

使用部分匹配交叉方法（PMX）應(yīng)確認(rèn)父體中的兩交叉點(diǎn)，并交換交叉點(diǎn)中部基因順序，父體繼承的選定部分則存自個(gè)體中未確定的基因，通過基因遺傳計(jì)算，可得出個(gè)體與整體之間的關(guān)系。

6.3 變異算子

變異算子是指將某一片段中的某些基因座的遺傳值替換為一個(gè)區(qū)域中的其他等位基因，并通過編碼染色體的方式創(chuàng)建出一個(gè)新的個(gè)體。變異算子采用的是基該位變異。

6.4 算法的具體設(shè)計(jì)

算法的具體設(shè)計(jì)內(nèi)容有以下6點(diǎn)：第一，設(shè)置種群規(guī)模，初始化設(shè)計(jì)參數(shù)，選擇最大值來得到變異和交叉概率；第二，涉及生成已經(jīng)設(shè)定種群規(guī)模數(shù)量的初始解，構(gòu)成初始種群；第三，將初始種群根據(jù)一定順序進(jìn)行排序，選取當(dāng)前解并隨機(jī)生成交叉概率，判斷其是否能夠滿足＜0.4的要求。如果能夠滿足，則選擇其應(yīng)用于交叉解；如果不滿足，直接進(jìn)入下一步；第四，剖析上述產(chǎn)生的新個(gè)體的任意變異概率，判定是否符合＜0.1的規(guī)定。如果符合，則處理單點(diǎn)變異，在這時(shí)產(chǎn)生新個(gè)體，使其加入種群。如果不滿足，則不需要進(jìn)行較差，可以支架加入新種群；第五，合并新舊種群，產(chǎn)生一個(gè)種群集合，集合內(nèi)各個(gè)個(gè)體以由大到小的順序排列，同時(shí)融合種群，輸出最小解作為最優(yōu)解并回到第二步驟；第六，當(dāng)?shù)螖?shù)滿足設(shè)定次數(shù)時(shí)，結(jié)束迭代操作并輸出最小解，獲得唯一的排序。

7 算例仿真

7.1 算例描述

某企業(yè)的螺桿車間生產(chǎn)設(shè)施位置按照公益配置原則進(jìn)行排列。已知螺桿車間的總布局為長21.0m、寬16.0m，車間內(nèi)共有8處設(shè)施。根據(jù)螺桿制造工藝分析，應(yīng)用SLP方法對(duì)車間進(jìn)行布局。但是在實(shí)際運(yùn)行過程中，存在物流運(yùn)輸頻繁、效率偏低和物流搬運(yùn)成本較高等問題?？梢娪斜匾獌?yōu)化車間布局。

7.2 計(jì)算要點(diǎn)與結(jié)果

首先，變換各個(gè)設(shè)施的坐標(biāo)，每次變換可以得到一個(gè)解，作為種群的一個(gè)個(gè)體，5個(gè)個(gè)體為一個(gè)種群，重復(fù)這一運(yùn)算，產(chǎn)生了125個(gè)群體，將其作為初始群體。

其次，對(duì)每個(gè)群體的適應(yīng)度函數(shù)進(jìn)行計(jì)算，計(jì)算其交叉變異和迭代。同時(shí)，獲取個(gè)體的適度值。結(jié)合實(shí)際情況來說，物流成本越高，個(gè)體的適度值越低。需要選擇物流成本較低的個(gè)體適應(yīng)度。

再次，評(píng)價(jià)算法得到的解，判斷其是否是最小解，將各解連接后判斷其是否為收斂。

最后，對(duì)解進(jìn)行迭代計(jì)算，最終得出最優(yōu)布局，如圖2所示。

圖2 優(yōu)化后的車間設(shè)施布局

8 結(jié)語

該文以實(shí)踐發(fā)展為視角、以遺傳算法為理論基礎(chǔ)，結(jié)合車間設(shè)施布局理論來分析布局存在的問題，構(gòu)建車間設(shè)施布局模型。使用遺傳算法得到優(yōu)化后結(jié)果，使用Flexsim軟件對(duì)該結(jié)果做仿真分析，可知在車間設(shè)施布局優(yōu)化后，企業(yè)生產(chǎn)效率提高，運(yùn)輸成本降低，對(duì)企業(yè)可持續(xù)發(fā)展具有現(xiàn)實(shí)意義。但是整體來說，該研究簡化了模型的實(shí)際效果，且虛擬仿真設(shè)計(jì)在求解復(fù)雜不規(guī)則設(shè)備方面的能力存在不足，會(huì)對(duì)車間設(shè)施布局優(yōu)化方案的最優(yōu)性產(chǎn)生影響，需要在后續(xù)研究中進(jìn)行完善。