基于自適應(yīng)遺傳算法的大型關(guān)重件車(chē)間布局優(yōu)化

張青雷 ，黨文君 ，段建國(guó)

（1.上海理工大學(xué)機(jī)械工程學(xué)院，上海 200093；2.上海海事大學(xué)，中國(guó)（上海）自貿(mào)區(qū)供應(yīng)鏈研究院，上海 201306）

1 引言

設(shè)備布局問(wèn)題是現(xiàn)代制造業(yè)面臨的一個(gè)非常重要的問(wèn)題，為了全面的提高現(xiàn)代機(jī)械制造技術(shù)水平，提高機(jī)械產(chǎn)業(yè)的整體競(jìng)爭(zhēng)力，降低車(chē)間內(nèi)生產(chǎn)制造的生產(chǎn)成本，就需要合理的利用車(chē)間內(nèi)的生產(chǎn)資源。而一個(gè)科學(xué)、合理的車(chē)間布置方案，就可以有效的利用車(chē)間內(nèi)的生產(chǎn)資源，提高生產(chǎn)效率，還可以減少車(chē)間內(nèi)的勞動(dòng)及運(yùn)輸成本[1]。因此，科學(xué)合理的設(shè)備布局有著很重要的意義。

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

2 車(chē)間設(shè)備布局問(wèn)題描述

2.1 問(wèn)題描述及假設(shè)

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

i=1，2，…，n；k=1，2，…，r；車(chē)間的長(zhǎng)度為 L，寬為 H，車(chē)間內(nèi)單元的長(zhǎng)為S，寬為Q；將整個(gè)車(chē)間置入一直角坐標(biāo)系中，行方向?yàn)閤 軸正方向，列方向?yàn)閥 軸正方向，生產(chǎn)單元的位置由其中心的坐標(biāo)（xi，yi）確定。

圖1 車(chē)間設(shè)備布局示意圖Fig.1 Sketch Map of Workshop Equipment

2.2 確立目標(biāo)函數(shù)

（1）車(chē)間布局的目標(biāo)就是合理的提高資源的利用率，使得各設(shè)備單元間的總物料搬運(yùn)成本最小化。因此，車(chē)間布局問(wèn)題的數(shù)學(xué)模型可表達(dá)為：

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

（2）車(chē)間內(nèi)的搬運(yùn)時(shí)間主要有搬運(yùn)距離、搬運(yùn)頻率與搬運(yùn)速度有關(guān)，為優(yōu)化車(chē)間布局，應(yīng)使車(chē)間內(nèi)搬運(yùn)時(shí)間最短，其數(shù)學(xué)模型為：

式中：T—車(chē)間內(nèi)總搬運(yùn)時(shí)間；V—零件的搬運(yùn)速度，取決于搬運(yùn)設(shè)備。

（3）車(chē)間布局的總和目標(biāo)函數(shù)為

式中：ωi—權(quán)重值，且 ω1+ω2=1 。

2.3 約束條件

2.3.1 行方向的約束

（1）每個(gè)生產(chǎn)單元只能布置在一個(gè)位置上且每行最多布置n個(gè)單元。

（2）同一行內(nèi)任意兩個(gè)生產(chǎn)單元之間的距離需大于基本間距Δx。

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

2.3.2 列方向的約束

（1）為使車(chē)間內(nèi)生產(chǎn)單元布置較為整齊，同一行中單元的y坐標(biāo)相同。

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

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

2.3.3 其它約束

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

3 基于改進(jìn)自適應(yīng)遺傳算法的目標(biāo)函數(shù)求解

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

3.1 確定染色體編碼方案

遺傳算法通常都采用二進(jìn)制編碼方式，但二進(jìn)制編碼方式占用的存儲(chǔ)空間比較大且需要較長(zhǎng)的編碼和解碼時(shí)間，對(duì)于多行布局的車(chē)間問(wèn)題，采用實(shí)數(shù)編碼的方式。編碼包括表示不同設(shè)備序列的符號(hào)和設(shè)備凈間距兩部分，采用如下的編碼方式：

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

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

種群的適應(yīng)度是判斷種群的個(gè)體優(yōu)劣的依據(jù)，決定著種群中的個(gè)體繁殖或淘汰，算法在搜索過(guò)程中就是以適應(yīng)度為判斷的依據(jù)，車(chē)間布局的適應(yīng)度函數(shù)可以采取目標(biāo)函數(shù)值的倒數(shù)的策略實(shí)現(xiàn)，即。

3.3 產(chǎn)生初始種群

一般是由計(jì)算機(jī)隨機(jī)產(chǎn)生N 個(gè)初設(shè)設(shè)備的排列序列及凈間距組成初始種群，但為了加快遺傳算法的收斂過(guò)程，使用目前車(chē)間真實(shí)的設(shè)備排列方式為初始種群中第一個(gè)染色體設(shè)備排列序號(hào)。

3.4 遺傳操作

（1）選擇運(yùn)算。采用輪盤(pán)賭選擇法，群體中的每個(gè)個(gè)體出現(xiàn)的概率都于個(gè)體的適應(yīng)度值有關(guān)，其概率與適應(yīng)度值的大小成正比，從而構(gòu)成子代種群。（2）交叉運(yùn)算。對(duì)于設(shè)備排列順序采用部分匹配交叉算法（PMX）；對(duì)于凈間距，采用算數(shù)交叉的方法。（3）變異運(yùn)算。采用互換變異法對(duì)凈間距進(jìn)行變異操作。

3.5 自適應(yīng)交叉、變異概率

遺傳算法的交叉概率和變異概率能夠?qū)z傳算法的性能產(chǎn)生極大的影響，將會(huì)直接影響算法的收斂性。雖然M.Srinvivas 提出的自適應(yīng)遺傳算法的交叉率Pc和變異率Pm可以隨適應(yīng)度自動(dòng)改變，但是當(dāng)個(gè)體適應(yīng)度等于或者接近最大適應(yīng)度時(shí)，Pc和Pm等于或者接近于零，這對(duì)與算法的進(jìn)化是不利的，使得變化初期種群內(nèi)的優(yōu)良個(gè)體基本不會(huì)發(fā)生變化，整個(gè)種群進(jìn)化結(jié)果成為局部最優(yōu)解的可能性增加[13]。因此，做出了一些改進(jìn)：

式中：fmax—群體中最大的適應(yīng)度值；favg—每代群體的平均適應(yīng)度值；f′—需要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值；f—將要變異的個(gè)體的適應(yīng)度值。算法改進(jìn)后，當(dāng)種群中的個(gè)體適應(yīng)度值為最大時(shí)，其交叉率和變異率將不會(huì)變?yōu)榱悖渥顑?yōu)個(gè)體依然有概率繼續(xù)進(jìn)化，使得算法能夠跳出局部最優(yōu)解。

3.6 精英保留策略

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

4 應(yīng)用實(shí)例

4.1 實(shí)例描述

應(yīng)用上述的算法對(duì)某大型船用曲軸生產(chǎn)車(chē)間進(jìn)行優(yōu)化布局，車(chē)間長(zhǎng)為264m，寬為72m。根據(jù)產(chǎn)品的工藝性，現(xiàn)將車(chē)間劃分成的11 個(gè)區(qū)域，區(qū)域名稱(chēng)及面積，如表1 所示。車(chē)間的初始布局，如圖2 所示。

表1 車(chē)間區(qū)域編號(hào)及面積（m＊m）Tab.1 Workshop Area Number and Area

圖2 車(chē)間初始布局圖Fig.2 Initial Layout of Workshop

一段時(shí)間內(nèi)工件在各區(qū)域間的物流頻率和物料運(yùn)輸?shù)闹亓浚绫?、表3 所示。由于船用曲軸各部分零件重量較大，車(chē)間內(nèi)運(yùn)輸設(shè)備主要是使用天車(chē)和一種搬運(yùn)平板小車(chē)進(jìn)行運(yùn)輸。

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

表3 區(qū)域間物料運(yùn)輸?shù)闹亓縏ab.3 Weight of Interregional Material Transportation

4.2 結(jié)果分析與比較

運(yùn)用matlab 軟件編寫(xiě)相應(yīng)程序，對(duì)自適應(yīng)遺傳算法以及標(biāo)準(zhǔn)遺傳算法進(jìn)行運(yùn)算。選取算法的參數(shù)，群體容量N=50，最大遺傳代數(shù)為300，自適應(yīng)遺傳算法中Pc1=0.9，Pc2=0.6，Pm1=0.1，Pm2=0.01；標(biāo)準(zhǔn)遺傳算法中Pc=0.6，Pm=0.1；以上述參數(shù)運(yùn)用兩種算法對(duì)問(wèn)題進(jìn)行計(jì)算。算法進(jìn)化的過(guò)程，如圖3 所示。對(duì)比兩種算法的最優(yōu)目標(biāo)函數(shù)值，自適應(yīng)遺傳算法的優(yōu)化程度明顯高于標(biāo)準(zhǔn)遺傳算法，達(dá)到最優(yōu)解的進(jìn)化代數(shù)也小于遺傳算法，其收斂速度更快，克服了遺傳算法收斂慢的弱點(diǎn)。

圖3 遺傳進(jìn)化過(guò)程對(duì)比Fig.3 Comparison of Genetic Evolution Process

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

圖4 優(yōu)化后的車(chē)間布局圖Fig.4 Optimized Layout of Workshop

5 結(jié)論

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