基于遺傳算法的虛擬維修環(huán)境布局規(guī)劃研究

張忠華，耿 宏

（1.中國東方航空股份有限公司機(jī)務(wù)培訓(xùn)中心，上海 200335；2.中國民航大學(xué)航空自動化學(xué)院，天津 300300）

目前關(guān)于虛擬維修的研究主要集中在虛擬維修過程建模和虛擬維修場景管理兩個方面。在場景管理中，當(dāng)部件進(jìn)行拆裝時，特別是對于航空發(fā)動機(jī)這類復(fù)雜部件的拆裝，必須考慮拆裝后大量零部件的擺放問題，即零部件在場景中的布局問題。為提高虛擬維修環(huán)境管理效率，對拆裝后產(chǎn)生的大量零部件做合理的布局規(guī)劃非常必要。文獻(xiàn)[1]中提出了一種遺傳算法和人機(jī)交互結(jié)合的方法解決布局問題[1]，從三維空間到二維平面的簡化中使用人機(jī)交互的方法來確定各個二維面；然而人機(jī)互動需要很高的硬件支持，在簡單虛擬維修條件下實(shí)用性不強(qiáng)。文獻(xiàn)[2]直接進(jìn)行三維空間的布局[2]，從隨機(jī)布局開始，利用改進(jìn)編碼的遺傳算法得到布局，由于布局是基于三維的，需要考慮空間中3個面的情況，處理過程更加復(fù)雜。

基于此，文中將零部件模型化處理，為其包絡(luò)外接圓柱體，同時應(yīng)用層次劃分將復(fù)雜的三維空間布局問題轉(zhuǎn)化為多個二維平面布局處理。二維布局應(yīng)盡可能減少拆裝后組件的移動距離，縮短維修培訓(xùn)時間，提高效率，此處采用基于遺傳算法的布局優(yōu)化。

1 虛擬維修環(huán)境整體布局規(guī)劃

維修環(huán)境中的零部件總體布局規(guī)劃如圖1所示。首先將不規(guī)則、復(fù)雜的待布局零部件模型化為簡單的外包圓柱體；為了簡化復(fù)雜的三維布局問題，此處建立一個部件信息庫，存儲各零部件的屬性特征。層次劃分利用其中的一些顯性屬性將各組件分配到不同的二維平面，處理流程如圖2所示。三維空間布局問題隨即轉(zhuǎn)化為多個二維平面的布局問題；最后對二維布局采用遺傳算法進(jìn)行優(yōu)化，得到虛擬拆裝環(huán)境布局結(jié)果。

圖1 虛擬維修環(huán)境布局規(guī)劃整體框架Fig.1 Virtual maintenance environment overall layout planning framework

圖2 虛擬環(huán)境空間規(guī)劃Fig.2 Virtual environment spatial planning

部件信息庫包含物理層和幾何層兩部分。物理層主要描述零部件的物理屬性，如部件名稱、拆裝層次、與其他部件的結(jié)合關(guān)系等物理信息。幾何層主要描述零部件的具體幾何參數(shù)，如體積、質(zhì)量、質(zhì)心等幾何信息。

三維布局轉(zhuǎn)化為多個二維布局是通過層次劃分完成的。層次劃分主要利用拆裝順序、安裝平面以及部件相似屬性來進(jìn)行二維平面的劃分。拆裝順序在信息庫的物理層中可以找到。結(jié)合組件的性能約束條件、拆裝層次、部件屬性關(guān)系，對拆裝后的組件進(jìn)行合理分類，給每個安裝面或?qū)傩韵嗨频牧悴考峙湟粋€二維平面，如 P1，P2，…，Pn，使得組件布局更具層次感；以組件拆裝過程中的先后順序?yàn)橐罁?jù)，平面在部件的上下排列（最先拆裝的零部件組成的平面距待拆裝部件最遠(yuǎn)），同時規(guī)定平面上布局物排列形狀接近圓形，可最大化地減少零部件的移動距離，提高虛擬維修效率。

2 二維布局?jǐn)?shù)學(xué)模型

將組件模型簡化為大小不一的圓柱體，規(guī)劃到各平面后，以圓柱體高為平面距上一級高度，在平面Pj上（j=1，2，…，n）對 n 個圓形作布局。

在n個圓形中，第i個圓形Ri的半徑為ri，質(zhì)量為mi（從部件信息庫中獲?。?，i∈I={1，2，…，n}。假定模型中圓形的質(zhì)心與重心重合。平面Pj的圓心為坐標(biāo)原點(diǎn)O=（0，0），圓形Ri的位置用（xi，yi）表示，其中xi、yi分別表示第i個圓的圓心在軸x、y方向的坐標(biāo)值，如圖3所示。

圖3 最大距離圓形布局圖Fig.3 Maximum distance planning

針對平面上的布局優(yōu)化問題建立如下約束條件：

1）幾何約束

布局問題中最基本的約束條件，要求布局物在幾何上沒有相互覆蓋（嵌入）[3]，在這里即是圓形間不發(fā)生干涉，約束為

其中：（xi，yi）、ri分別為圓形Ri的圓心位置及半徑。

2）平衡性能約束

為使虛擬效果更有真實(shí)感，引入平衡約束，嚴(yán)格要求每個平面上的平衡量δ為0，即將平面Pj上所有布局物構(gòu)成的系統(tǒng)質(zhì)心移動到待拆裝部件的中心線上即可。平移后的質(zhì)心為

3）優(yōu)化目標(biāo)——包絡(luò)半徑最小

布局優(yōu)化要求該平面上所有布局物組成的包絡(luò)圓最小[4]。由平衡性能約束條件可知，最小包絡(luò)半徑r可定義為n個圓形的最遠(yuǎn)點(diǎn)到達(dá)平面中心的最長距離。此處包絡(luò)半徑函數(shù)用D（，R）表示

3 基于遺傳算法的布局優(yōu)化

遺傳算法由Holland于1975年首次提出，是一種模擬生物界自然選擇和遺傳變異的機(jī)制來求解復(fù)雜問題的隨機(jī)搜索和優(yōu)化方法，通過選擇、交叉、變異等操作來實(shí)現(xiàn)[5]。實(shí)踐表明，遺傳算法易產(chǎn)生早熟現(xiàn)象、計算時間較長，此處在基本遺傳算法的基礎(chǔ)上對初始解和控制參數(shù)進(jìn)行了調(diào)整，應(yīng)用于布局優(yōu)化中[6]。

3.1 初始解的產(chǎn)生

假定布局物的集合為Ii（i=0，1，…，n），則I0表示還未開始布局的集合。通過布局集合中的任意圓形Ri（i=0，1，…，n）確定其所屬集合的有效布局空間。每次待布物的布置選擇，只在其有效解空間中選擇隨機(jī)解[7]。

1）取待布物 Ri；

2）確定Ri的有效解空間：

a.在平面Pj中任意選擇xi；

b.做直線 X=xi；

c.判斷當(dāng)前解是否與現(xiàn)有解沖突，處理流程如圖4所示。其中ri為圓形Ri的半徑，xi-1、ri-1為Ri前一個布局圓形的參數(shù)；

d.對于沖突解，將其存儲至禁止區(qū)域集合中，避免多次沖突。同時為Ri重新選擇適用區(qū)域；

e.同樣的方法選擇yi坐標(biāo)。

3）隨機(jī)選擇個體解，直至完成該平面上所有圓形的布局。

3.2 算法中基本參數(shù)的選擇

3.2.1 編碼策略

遺傳算法的傳統(tǒng)編碼最初均采用二進(jìn)制，后來又有整形、實(shí)數(shù)等編碼形式。一般求解中會使用二進(jìn)制符號串來表示群體中的個體。在布局問題中，為了更方便適應(yīng)度函數(shù)的表示及求解，此處使用基于實(shí)際位置坐標(biāo)形式的實(shí)數(shù)編碼，即染色體表示為：{（x1，y1），（x2，y2），…，（xn，yn）}。其中，xn和 yn分別表示第 n 個布置圓形Rn的實(shí)際位置。

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

圖4 確定沖突解流程圖Fig.4 Definite conflict solution flow chart

此處采用實(shí)數(shù)編碼，可直接將目標(biāo)函數(shù)作為適應(yīng)度函數(shù)，從而大大降低個體適應(yīng)度評價的復(fù)雜度。這樣就可直接用個體的解作為評價個體適應(yīng)度的度量指標(biāo)，保證適應(yīng)度值較低的個體也會以概率遺傳。從而在適應(yīng)度值低的情況下保證群體的多樣性，在一定程度上避免局部收斂。當(dāng)群體的適應(yīng)值較高時，又有利于種群的整體收斂。

3.2.3 控制參數(shù)

控制參數(shù)包括變異概率和交叉概率，與迭代次數(shù)有關(guān)。同時，與當(dāng)前代的分布狀態(tài)有關(guān)，與個體的表現(xiàn)也有關(guān)，每一層的二維布局優(yōu)化中參數(shù)值的選取將視情況選擇。

3.2.4 選擇算子

本文采用轉(zhuǎn)輪盤方式進(jìn)行個體選擇[8]。首先計算個體的相對適應(yīng)值其中xi表示Ri確定位置時的圓心橫坐標(biāo)，Σxi表示所有可能橫坐標(biāo)值的和。再根據(jù)選擇概率隨機(jī)選擇個體，從而得到父本。此處通過一個隨機(jī)數(shù)δ完成，δ∈[0，1]。若q0+q1+… +qi-1＜δ≤q0+q1+…+qi，則第i個個體被選擇到下父本中。

3.2.5 交叉算子和變異

交叉和變異可保證遺傳算法在進(jìn)化過程中樣本的多樣性，從而使問題具有全局尋優(yōu)的意義[9]。本文算法中，當(dāng)被布置個體的適應(yīng)度較低時，以滿足轉(zhuǎn)動慣量最小的原則，對原布置微調(diào)，此操作視為交叉。反之，對布置物重新布置，這種大范圍的調(diào)動視為變異，從而使其作為一種搜索算子進(jìn)行全局的解搜索。

3.2.6 算法步驟

1）設(shè)置群體代數(shù)t=0，按照初始解規(guī)則生成規(guī)模為N的初始群體；

2）對初始種群進(jìn)行適應(yīng)度評價；

3）進(jìn)行復(fù)制、交叉和變異操作，生成新的子代群體；

4）評價新一代群體的適應(yīng)度，并記錄該代群體中的最優(yōu)個體；

5）按照收斂準(zhǔn)則檢驗(yàn)，若滿足，則轉(zhuǎn)6）；否則，令t=t+1，轉(zhuǎn)至步驟 3）；

6）結(jié)束迭代，輸出最優(yōu)個體，并解碼出最終結(jié)果。

4 實(shí)例分析

航空發(fā)動機(jī)內(nèi)的組件拆裝一直是飛機(jī)維修過程中的復(fù)雜對象之一，其拆裝后包含的零部件多達(dá)上千個。下面對某航空發(fā)動機(jī)高壓壓氣機(jī)裝配零部件做層次劃分，在前機(jī)匣裝配層、輪盤轉(zhuǎn)子裝配層、高壓壓氣機(jī)裝配層、輪盤裝配層這4個二維層上進(jìn)行布局。運(yùn)用基于遺傳算法的布局方法對某個二維層作零部件布局優(yōu)化，模型簡化后的圓形參數(shù)如表1所示。遺傳算法的參數(shù)取值如下：編碼串長度15，群體大小200；終止代數(shù)100，交叉概率0.6，變異概率0.3。最終布局如圖5所示。

表1 二維層上圓形模型參數(shù)Tab.1 Circular model parameter of two-dimensional layout

5 結(jié)語

本文針對虛擬維修環(huán)境的三維布局，利用層次劃分簡化為多個二維平面布局問題，同時在二維布局中采用遺傳算法進(jìn)行優(yōu)化，提出了一種虛擬維修零部件布局的可行性方法。本文將組件均簡化為其包絡(luò)圓柱體，然而組件形狀其實(shí)是各異的，設(shè)計針對任意形狀的布局方法，更精確地達(dá)到布局最優(yōu)化是需要進(jìn)一步研究的內(nèi)容，同時，采用的遺傳算法在參數(shù)選擇上可以加入自適應(yīng)算法，提高算法的有效性。

圖5 二維層上圓形模型布局優(yōu)化結(jié)果Fig.5 Circular model layout optimization results two-dimensional layout

[1]何良莉，魏發(fā)遠(yuǎn)，王峰軍.虛擬布局/裝配環(huán)境下的人機(jī)交互技術(shù)研究[J].機(jī)械設(shè)計，2010（5）：86-89.

[2]張 剛，鄧克文，李火生，等.復(fù)雜結(jié)構(gòu)產(chǎn)品虛擬布局與裝配設(shè)計系統(tǒng)研究[J].計算機(jī)集成制造系統(tǒng)，2008，14（2）：209-214.

[3]錢志勤，滕弘飛.人機(jī)交互的遺傳算法及其在約束布局優(yōu)化中的應(yīng)用[J].計算機(jī)學(xué)報，2001，24（5）：553-559.

[4]季 關(guān)，肖人彬.基于蟻群算法的帶平衡約束矩形布局問題的啟發(fā)式求解[J].計算機(jī)應(yīng)用，2010，30（11）：2898-2901.

[5]HOLLAND J H.Adaptation in natural and artificial systems：An Introductory Analysis with Applications to Biology，Control，and Artificial Intelligence[M].Oxford：U Michigan Press，1975.

[6]SCHNECKE V，VORNBERGER O.Hybrid genetic algorithms for constrained placement problems[J].IEEE Transactions on Evolutionary Computation，1997，1（4）：266-277.

[7]李亞洲，鄭曉軍，張 強(qiáng)，等.基于改進(jìn)初始解的遺傳算法的布局設(shè)計方法[J].計算機(jī)工程與應(yīng)用，2013，49（8）：245-248.

[8]于 洋，查建中.基于學(xué)習(xí)的遺傳算法及其在布局中的應(yīng)用[J].計算機(jī)學(xué)報，2001，24（12）：1242-1249.

[9]張 剛，殷國富，鄧克文，等.解空間編碼遺傳算法在三維布局中的應(yīng)用[J].中國機(jī)械工程，2006，17（1）：79-83.