基于自適應遺傳算法的大型關重件車間布局優化

張青雷 ，黨文君 ，段建國

（1.上海理工大學機械工程學院，上海 200093；2.上海海事大學，中國（上海）自貿區供應鏈研究院，上海 201306）

1 引言

設備布局問題是現代制造業面臨的一個非常重要的問題，為了全面的提高現代機械制造技術水平，提高機械產業的整體競爭力，降低車間內生產制造的生產成本，就需要合理的利用車間內的生產資源。而一個科學、合理的車間布置方案，就可以有效的利用車間內的生產資源，提高生產效率，還可以減少車間內的勞動及運輸成本[1]。因此，科學合理的設備布局有著很重要的意義。

近年來，已經有不少學者[2-5]對車間布局問題有了比較深入的研究；文獻[6]針對多零件族變批量的生產需求，分析了系統重用和加工任務重現的必要性，以重組成本、追加投資、空閑時間、加工任務重現度、系統重用度等指標為線性組合建立了目標函數，建立面向多零件族變批量需求模式的布局重組規劃模型，用遺傳算法進行求解；文獻[7]分析了多品種小批量連桿類零件的生產特點及加工工藝，提出了一種柔性制造車間布局方法，通過選擇柔性制造的加工設備及輔助設備，得出合適的車間布局方案；文獻[8]針對面積不定、形狀固定的多行布局問題，提出自由換行布局策略和凈間距的概念，構建了帶逆向物流的多目標組合優化數學模型，使用自適應遺傳算法對模型進行求解；文獻[9]以車間內物流搬運費用最小與空間利用率最大為目標建立多目標優化車間布局模型，并且提出一種差分元胞多目標遺傳算法對車間內模型進行求解；文獻[10]采用遺傳算法針對某廠曲軸生產車間設備局部問題進行了優化研究，并提出了搬運矩概念，得到了較為優化的設計結果。但目前對于大型關重件生產車間的布局優化問題研究相對較少，關重件通常包括關鍵件和重要件，關鍵件是指具備產品關鍵特性的單元件，重要件是指不包含關鍵特性但是具有重要特性的單元件。一般大型關重件都是單件小批量生產，工件的體積較大且每道工序加工的時間較長。以大型船用曲軸這一關重件的加工車間為例，同時考慮物料搬運成本及搬運時間兩個因素建立車間布局模型。對于標準遺傳算法存在早熟收斂和后期進化緩慢的問題，使用一種改進的自適應遺傳算法進行求解，有效的提高了整體尋優能力。

2 車間設備布局問題描述

2.1 問題描述及假設

對于大型關重件的生產車間，由于其單件小批量的生產特性，可將車間內的設備根據需要加工的零件的工藝計劃將具有相似工藝特征的零件合并為一個零件族，然后將具有密切加工工藝關系的機器構建成生產單元，使單元零件的全部加工工序所包含的設備都在一個單元內，再對車間內各個生產單元進行多行布局[11]。假設車間內的生產單元的形狀均為矩形塊狀結構，相互兩個單元之間的物流運輸方向只能平行于相應的參考線。設車間有n 個設備單元M=｛m1，m2，…，mn｝，布置為 r 行，引入一決策變量 Zik：

i=1，2，…，n；k=1，2，…，r；車間的長度為 L，寬為 H，車間內單元的長為S，寬為Q；將整個車間置入一直角坐標系中，行方向為x 軸正方向，列方向為y 軸正方向，生產單元的位置由其中心的坐標（xi，yi）確定。

圖1 車間設備布局示意圖Fig.1 Sketch Map of Workshop Equipment

2.2 確立目標函數

（1）車間布局的目標就是合理的提高資源的利用率，使得各設備單元間的總物料搬運成本最小化。因此，車間布局問題的數學模型可表達為：

式中：Q—物流成本；cij—單位距離的運輸成本；fij—單元間的物流頻率；dij—單元間的距離單元間運輸物料的重量。

（2）車間內的搬運時間主要有搬運距離、搬運頻率與搬運速度有關，為優化車間布局，應使車間內搬運時間最短，其數學模型為：

式中：T—車間內總搬運時間；V—零件的搬運速度，取決于搬運設備。

（3）車間布局的總和目標函數為

式中：ωi—權重值，且 ω1+ω2=1 。

2.3 約束條件

2.3.1 行方向的約束

（1）每個生產單元只能布置在一個位置上且每行最多布置n個單元。

（2）同一行內任意兩個生產單元之間的距離需大于基本間距Δx。

（3）同一行中單元布置不能超出車間范圍

2.3.2 列方向的約束

（1）為使車間內生產單元布置較為整齊，同一行中單元的y坐標相同。

（2）在不同行中的任意兩個生產單元在y 軸方向上的間距需大于基本間距Δy。

（3）在不同行中的生產單元在y 軸方向不能超出車間范圍。

2.3.3 其它約束

影響車間布局設計的因素也有很多，除了上述設備尺寸與車間大小方面的約束條件及外，還包括其它很多特殊的要求約束。比如設備的搬運通道、人員的安全通道、參觀通道等，或者車間內某些特殊位置的放置，這些約束具有一定的不確定性，為了簡化工作，忽略這些特殊約束條件，建立了上述的優化模型。設計者可通過優化的布局并結合車間的實際情況得到最終的優化方案[12]。

3 基于改進自適應遺傳算法的目標函數求解

標準遺傳算法的基本思想起源于Darwin 的進化論和Mendel的遺傳學說，是一種借鑒了“優勝劣汰”的生物進化法則和遺傳思想提出的一種全局隨機搜索算法。這種算法是將相關問題編碼成為染色體，大量的染色體組成種群，通過不同的操作如選擇、復制、交叉和變異等使得其初始種群不斷進化，淘汰掉適應度值較低的方案，向著最優解接近。在標準遺傳算法中，交叉率和變異率是影響遺傳算法進化的關鍵，但是交叉算子和變異算子的數值是固定的，Pc和Pm數值的大小都會影響算法的收斂速度，可能會使算法的收斂緩慢或者是過早的收斂導致陷入局部最優。針對此問題，Srinvivas 等提出一種自適應遺傳算法，根據個體適應度值的大小實時調整交叉、變異的概率，保持進化的優勝劣汰。

3.1 確定染色體編碼方案

遺傳算法通常都采用二進制編碼方式，但二進制編碼方式占用的存儲空間比較大且需要較長的編碼和解碼時間，對于多行布局的車間問題，采用實數編碼的方式。編碼包括表示不同設備序列的符號和設備凈間距兩部分，采用如下的編碼方式：

式中：｛m1，m2，…，mn｝—設備的排列順序；｛Δ1，Δ2，…，Δn｝—第 i臺設備與前一臺設備的凈間距。同時，采用自動換行的策略，即布置在同一行的設備的長度之和大于車間的長度，那么本行的最后一臺設備將自動布置到下一行，繼續新一行的布置。

3.2 適應度函數

種群的適應度是判斷種群的個體優劣的依據，決定著種群中的個體繁殖或淘汰，算法在搜索過程中就是以適應度為判斷的依據，車間布局的適應度函數可以采取目標函數值的倒數的策略實現，即。

3.3 產生初始種群

一般是由計算機隨機產生N 個初設設備的排列序列及凈間距組成初始種群，但為了加快遺傳算法的收斂過程，使用目前車間真實的設備排列方式為初始種群中第一個染色體設備排列序號。

3.4 遺傳操作

（1）選擇運算。采用輪盤賭選擇法，群體中的每個個體出現的概率都于個體的適應度值有關，其概率與適應度值的大小成正比，從而構成子代種群。（2）交叉運算。對于設備排列順序采用部分匹配交叉算法（PMX）；對于凈間距，采用算數交叉的方法。（3）變異運算。采用互換變異法對凈間距進行變異操作。

3.5 自適應交叉、變異概率

遺傳算法的交叉概率和變異概率能夠對遺傳算法的性能產生極大的影響，將會直接影響算法的收斂性。雖然M.Srinvivas 提出的自適應遺傳算法的交叉率Pc和變異率Pm可以隨適應度自動改變，但是當個體適應度等于或者接近最大適應度時，Pc和Pm等于或者接近于零，這對與算法的進化是不利的，使得變化初期種群內的優良個體基本不會發生變化，整個種群進化結果成為局部最優解的可能性增加[13]。因此，做出了一些改進：

式中：fmax—群體中最大的適應度值；favg—每代群體的平均適應度值；f′—需要交叉的兩個個體中較大的適應度值；f—將要變異的個體的適應度值。算法改進后，當種群中的個體適應度值為最大時，其交叉率和變異率將不會變為零，其最優個體依然有概率繼續進化，使得算法能夠跳出局部最優解。

3.6 精英保留策略

為了避免交叉操作和變異操作破壞種群中的精英個體，保留每一代種群中的優良個體，采用了精英保留策略，精英保留策略的基本思想是種群進化過程中每一代適應度最大的精英個體直接復制到下一代，保證最優的個體不被交叉、變異等遺傳運算破壞，精英保留策略也有效的提高了算法的收斂能力[14]。

4 應用實例

4.1 實例描述

應用上述的算法對某大型船用曲軸生產車間進行優化布局，車間長為264m，寬為72m。根據產品的工藝性，現將車間劃分成的11 個區域，區域名稱及面積，如表1 所示。車間的初始布局，如圖2 所示。

表1 車間區域編號及面積（m＊m）Tab.1 Workshop Area Number and Area

圖2 車間初始布局圖Fig.2 Initial Layout of Workshop

一段時間內工件在各區域間的物流頻率和物料運輸的重量，如表2、表3 所示。由于船用曲軸各部分零件重量較大，車間內運輸設備主要是使用天車和一種搬運平板小車進行運輸。

表2 零件在各區域間的物流頻率Tab.2 Logistics Frequency of Parts Between Regions

表3 區域間物料運輸的重量Tab.3 Weight of Interregional Material Transportation

4.2 結果分析與比較

運用matlab 軟件編寫相應程序，對自適應遺傳算法以及標準遺傳算法進行運算。選取算法的參數，群體容量N=50，最大遺傳代數為300，自適應遺傳算法中Pc1=0.9，Pc2=0.6，Pm1=0.1，Pm2=0.01；標準遺傳算法中Pc=0.6，Pm=0.1；以上述參數運用兩種算法對問題進行計算。算法進化的過程，如圖3 所示。對比兩種算法的最優目標函數值，自適應遺傳算法的優化程度明顯高于標準遺傳算法，達到最優解的進化代數也小于遺傳算法，其收斂速度更快，克服了遺傳算法收斂慢的弱點。

圖3 遺傳進化過程對比Fig.3 Comparison of Genetic Evolution Process

基于自適應遺傳算法得出的車間布局的最優解為［10，9，7，3，4，8，1，2，5，6］，車間布局，如圖4 所示。優化后的函數值由最初的10.1×106減小為6.2×106，優化后車間內的物料搬運成本與搬運時間比最初的布局減少35%，對車間內的生產效率有一定的提升。

圖4 優化后的車間布局圖Fig.4 Optimized Layout of Workshop

5 結論

（1）分析了大型關重件車間的生產特點，基于其單件小批量的生產特性，將有密切加工工藝關系的機器構建成生產單元，對各個生產單元建立了同時考慮物流費用與物流時間的多目標優化數學模型。（2）對于標準遺傳算法存在早熟收斂和后期進化緩慢的問題，使用了一種交叉率和變異率可以隨適應度自動改變的自適應遺傳算法，采用自動換行的編碼方式，并且加入了精英保留策略以提高算法的收斂能力。（3）通過實例驗證了數學模型及自適應算法的可行性，車間內的物流搬運成本及物流時間節省35%左右，優化后的布局可以有效的提高生產效率，較好的實現了優化布局的目標。