賈寶惠，周 帆

(中國民航大學(xué) 航空工程學(xué)院，天津 300300)

基于遺傳禁忌搜索混合算法的修理級別問題研究

賈寶惠，周 帆

(中國民航大學(xué) 航空工程學(xué)院，天津 300300)

修理級別分析(LORA)是維修決策制定的一個重要工具。由于已有的修理級別分析整數(shù)規(guī)劃模型涉及大量的決策變量，用傳統(tǒng)的優(yōu)化方法很難對其進(jìn)行優(yōu)化求解，故提出了一種遺傳禁忌搜索混合算法，以最小化維修成本為目標(biāo)，對LORA問題進(jìn)行求解，確定最佳修理決策組合。最后通過算例的比較分析，表明了本算法的有效性。

修理級別分析；維修成本；遺傳算法；禁忌搜索

中國民航大學(xué)預(yù)研重大項目(3122014P002)

0 引言

修理級別分析(Level of Repair Analysis, LORA)用來評估綜合后勤保障中系統(tǒng)全壽命成本的影響要素，以實現(xiàn)最低全壽命維修成本的系統(tǒng)設(shè)計。LORA是一個確定失效部件應(yīng)報廢還是修理，以及在修理網(wǎng)絡(luò)中什么位置執(zhí)行這些活動的過程。

現(xiàn)有文獻(xiàn)中討論了不同的多層、多級的LORA模型[1-9]，這些模型無不涉及大量的決策變量，因此，通過傳統(tǒng)優(yōu)化方法如整數(shù)規(guī)劃和分支定界等很難對LORA問題進(jìn)行優(yōu)化求解，而遺傳算法及其混合策略在求解非常耗時的大規(guī)模組合問題時顯示出了極高的效力。鑒于此，本文提出一種遺傳禁忌搜索混合算法，將其應(yīng)用于LORA問題求解，并利用算例的比較分析，表明該算法能在可接受計算時間內(nèi)求得最優(yōu)解。

1 LORA問題模型的建立

1.1 航空裝備維修級別和層次劃分

LORA分析是以維修級別與裝備修理的約定層次的劃分為基礎(chǔ)的。維修級別根據(jù)裝備的范圍和深度區(qū)分任務(wù)，并按維修時所處場所劃分等級。航空裝備維修級別分為三級，即基層級(O)、中繼級(I)和基地級(D)。裝備修理約定層次一般劃分為外場可更換件(LRU)、車間可更換件(SRU)、車間可更換件子部件(SSRU)三個層次。對于一個給定的設(shè)計，修理級別分析師必須決定哪些部件要修理、哪些部件要報廢、在修理網(wǎng)絡(luò)中何處執(zhí)行這些活動，從而確定部件進(jìn)行修理或報廢的位置，并以最低成本滿足維修要求。1.2 建立數(shù)學(xué)模型

本文研究中，設(shè)i為所研究系統(tǒng)的部件,i=1,2,…，n，n為部件總數(shù)；r為修理選項，包括修理、報廢、移動；e為維修級別。本文參考文獻(xiàn)[1,3,4]所描述的模型，對LORA問題進(jìn)行建模，通過最小化維修成本獲得最優(yōu)修理決策。

建立的數(shù)學(xué)模型如下：

(1)

其中：VCr,e,i為部件i在維修級別e上執(zhí)行修理選項r的可變成本；λi為部件i全壽命周期內(nèi)所需維修任務(wù)的總次數(shù)；FCr,e,i為部件i在維修級別e上執(zhí)行修理選項r的固定成本；Xr,e,i為決策變量，Xr,e,i=1,表示部件i在維修級別e上選擇了修理選項r，否則Xr,e,i=0。

式(1)是目標(biāo)函數(shù)，對執(zhí)行修理和報廢活動的固定和可變成本求和，并使其最小。約束條件如下：

(2)

(3)

Xr,e,j=Xr,e,i,?e,其中r=報廢或者移動.

(4)

(5)

式(2)確保在基層級(e=1)選擇一個修理選項。式(3)表示如果在e級上采取移動決策，在e+1級上應(yīng)只采取修理決策，否則，在e+1級上不選擇任何修理選項。式(4)表示子部件與父部件在各維修級別上采取相同的報廢或者移動決策；j表示部件i的子部件。式(5)表示在最高級維修級別上(e=3)僅有兩種修理決策(修理或報廢)可供選擇。

2 求解算法設(shè)計

2.1 算法思路

遺傳算法和禁忌搜索(Tabu Search，TS)都是求解組合優(yōu)化問題的常用算法[10]。遺傳算法及其混合策略在求解非常耗時的大規(guī)模組合問題時顯示出了極高的效力，缺點是當(dāng)種群規(guī)模較大時求解速度較慢，而禁忌搜索又較依賴于初始解。因此，提出兩者混合算法即GATS算法，克服兩種算法的缺點并保留各自的優(yōu)勢，對NP-hard和組合優(yōu)化的LORA問題進(jìn)行求解。

本文的GATS算法首先生成N個初始可能解；然后利用禁忌搜索的迭代過程進(jìn)行鄰域搜索，對這些解進(jìn)行更新；之后，流程返回遺傳算法，再進(jìn)行一個迭代過程；通過遺傳算子產(chǎn)生新的后代，并根據(jù)新的后代的適應(yīng)值對最佳解的禁忌表進(jìn)行更新。GATS算法的終止準(zhǔn)則是達(dá)到了預(yù)定義的連續(xù)迭代次數(shù)，迭代過程獲得的最佳解相同。

GATS算法流程如圖1所示。

圖1 GATS算法的流程

GATS算法的具體步驟如下：

(1) 隨機(jī)產(chǎn)生一個解集(20個解)，驗證式(2)、式(3)、式(4)、式(5)。

(2) 通過鄰域搜索改進(jìn)解的適應(yīng)度值。鄰域解僅通過修改解的值為1或0獲得。另外，直到驗證了式(2)～式(5)，才接受鄰域解。然后，更新禁忌表，其中包含所有已探索過的解的適應(yīng)度值。接著，僅當(dāng)適應(yīng)度值不出現(xiàn)于禁忌表中時，探索一個新的鄰域。

(3) 重復(fù)步驟(2)，直到最佳適應(yīng)度值沒有改進(jìn)。

(4) 用最佳鄰域替換該解。

(5) 基于遺傳算法的選擇算子和交叉算子，選擇兩個解來產(chǎn)生新的染色體。當(dāng)驗證了式(2)～式(5)時，接受這些新的解。

(6) 利用變異算子，生成新的染色體。

(7) 更新最佳染色體的禁忌表。

(8) 重復(fù)以上步驟，直到最佳染色體沒有改進(jìn)。

2.2 GATS算法設(shè)計

2.2.1 編碼方式

用遺傳算法求解特定問題時，首先要確定編碼方式。本文采用的編碼方式是一個二進(jìn)制矩陣(n×d)，其中n為所有部件(即項目)的數(shù)量，d為所有修理決策的數(shù)量。該編碼方式中，xij=1意味著部件i和級別j選擇了修理、報廢或者移動決策。圖2是染色體或解的二進(jìn)制編碼方式，其中“項目”表示待分析產(chǎn)品，可以是部件或子部件。

圖2 染色體(修理決策)的二進(jìn)制編碼示例

另外，任何技術(shù)系統(tǒng)都可視為裝配的集合，這些裝配又可視為一些子裝配的集合。出于建模的考慮，系統(tǒng)分解結(jié)構(gòu)用一個矩陣來表示，稱為共性矩陣，如圖3所示。其中列代表父部件，行表示子部件，子部件4、5、6屬于父部件3，或者說父部件3包含了子部件4、5、6。根據(jù)式(4)，無論何時父部件3采取報廢或移動決策，子部件4、5、6都將采取同樣的決策。

圖3 系統(tǒng)結(jié)構(gòu)的矩陣表述

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

本文的目標(biāo)函數(shù)是求解最小值問題，算法的選擇過程采用輪盤選擇法，因此本文采用的適應(yīng)度函數(shù)為：

F(f(x))=Cmax-f(x).

(6)

2.2.3 遺傳算法算子

GATS算法使用適應(yīng)度值比例選擇的輪盤賭抽樣作為交叉算子。每一代采用最優(yōu)保存策略，用滿足式(1)的最好的解替換最差的。選擇一對父代進(jìn)行交叉運算產(chǎn)生兩個新的子代。交叉算子通過交換信息作用于這兩個父染色體。由于每一對父代染色體的基因密碼有著相同的結(jié)構(gòu)，因此隨機(jī)選擇交叉點進(jìn)行單點交叉，接著根據(jù)式(4)調(diào)整子代修理決策。

變異運算是遺傳算法的另一重要特點，是產(chǎn)生新個體的輔助方法，變異運算的目的是維持群體的多樣性，防止解陷入局部最優(yōu)。本文中變異算子從最優(yōu)解列表中隨機(jī)選出一個染色體，并用一個同樣是隨機(jī)產(chǎn)生的新的染色體替換；另外，選擇一個最優(yōu)解，并隨機(jī)為部件產(chǎn)生一個修理決策；然后再根據(jù)式(4)調(diào)整修理決策。

2.2.4 鄰域結(jié)構(gòu)

TS的框架由產(chǎn)生自初始解的一些鄰域解組成，通過目標(biāo)函數(shù)對這些解進(jìn)行評估并分類。禁忌表通過最優(yōu)解的適應(yīng)度進(jìn)行更新，然后確定一個新的解并從中產(chǎn)生額外的鄰域搜索。當(dāng)一系列迭代之后最佳解保持不變時，便求得了最優(yōu)解。本文采用互換的方法產(chǎn)生鄰域結(jié)構(gòu)。

2.2.5 禁忌對象和禁忌表的確定

本文將禁忌對象設(shè)定為狀態(tài)本身，將每次迭代最終接受的解作為禁忌對象放入禁忌表中。禁忌表是禁忌對象的集合。

3 實例分析

本節(jié)將根據(jù)數(shù)值實驗的結(jié)果測試GATS算法的有效性。為了比較起見，對文獻(xiàn)[3]執(zhí)行過的案例進(jìn)行研究。文獻(xiàn)[3]中給出了航空發(fā)動機(jī)的三層結(jié)構(gòu)和兩級修理網(wǎng)絡(luò)，以及所有項目在不同級別上不同修理選項的固定成本和可變成本。另外，圖4給出共性矩陣，顯示父部件(項目1到項目10)與子部件(項目11到項目32)之間的關(guān)系。用MATLAB語言對GATS算法進(jìn)行編譯，并在電腦上實施該算法。表1為本文GATS算法獲得的最優(yōu)解，與文獻(xiàn)[3]的修理決策相同。另外，文獻(xiàn)[7]中也對文獻(xiàn)[3]執(zhí)行過的案例進(jìn)行了研究，其中所使用的免疫粒子群算法(IA-PSO)和本文GATS算法得出相應(yīng)的總維修成本分別是4 277.27美元和4 216.27美元，計算時間分別為32 s和21 s，如表2所示。

圖4 共性矩陣

項目級別2級別3修理報廢移動修理報廢項目110000項目200101項目301000項目401000??????項目3100101項目3201000

表2 IA-PSO與GATS算法比較

4 結(jié)論

(1) 在現(xiàn)有LORA研究的基礎(chǔ)上，對LORA問題進(jìn)行了建模，以最小化維修成本為目標(biāo)，獲得最佳修理級別決策。

(2) 利用遺傳-禁忌搜索混合算法，對LORA問題進(jìn)行了優(yōu)化求解，并給出了算法的求解步驟。利用文獻(xiàn)[3]中的數(shù)據(jù)，通過算例的比較分析，對三級修理網(wǎng)絡(luò)和多級系統(tǒng)結(jié)構(gòu)的修理決策進(jìn)行了優(yōu)化，結(jié)果表明在合理的時間內(nèi)可獲得LORA問題的最優(yōu)解，證明該算法是切實可行的。與免疫粒子群算法的比較結(jié)果表明了本文算法的有效性。

(3) 與相關(guān)文獻(xiàn)研究結(jié)果相比，本文提出的算法更適于求解涉及大量決策變量的LORA問題。結(jié)合工程實際對LORA模型進(jìn)行改進(jìn)后，可以用本文提出的算法對LORA問題進(jìn)行優(yōu)化求解，為維修決策的制定提供參考。

[1] Barros L,Riley M.A combinatorial approach to level of repair analysis[J].European Journal of Operational Research,2001,129(2):242-251.

[2] Gutin G,Rafiey A,Yeo A,et al.Level of repair analysis and minimum cost homomorphisms of graphs[J].Discrete Applied Mathematics,2006,154(6):881-889.

[3] Saranga H,Dinesh Kumar U.Optimization of aircraft maintenance/support infrastructure using genetic algorithms-level of repair analysis[J].Annals of Operations Research,2006,143(1):91-106.

[4] Basten R J I,Schutten J M J,van der Heijden M C.An efficient model formulation for level of repair analysis[J].Annals of Operations Research,2009,172(1):119-142.

[5] Brick E D, Uchoa E. A facility location and installation of resources model for lever of repair analysis[J].European Journal of Operational Research,2009,192：479-486.

[6] Basten R J I,van der Heijden M C,Schutten J M J.A minimum cost flow model for level of repair analysis[J].International Journal of Production Economics,2011,133(1)：233-242.

[7] 吳昊,左洪福,孫偉.一種新的民用飛機(jī)修理級別優(yōu)化模型[J].航空學(xué)報,2009(2):247-253.

[8] 薛陶,馮蘊雯,薛小鋒,等.一種飛機(jī)修理級別經(jīng)濟(jì)性分析模型[J].航空學(xué)報,2013(1):97-103.

[9] 薛陶,馮蘊雯,代曉明.基于改進(jìn)AHP方法的飛機(jī)修理級別經(jīng)濟(jì)性分析[J].火力與指揮控制,2013(3):58-61.

[10]王超.基于混合遺傳禁忌搜索算法的多目標(biāo)柔性作業(yè)車間調(diào)度問題研究[D].重慶：重慶大學(xué),2012:31-44.

(英文摘要Study on Level of Repair Analysis Based on Hybrid Genetic-Tabu Search Algorithm

JIA Bao-hui, ZHOU Fan

(College of Aeronautical Engineering, Civil Aviation University of China, Tianjin 300300, China)

Level of repair analysis (LORA) is considered as an important tool for maintenance decision making. It is very difficult to solve the LORA integer programming model, which involves a large number of decision variables, using traditional optimization techniques. In this paper, a hybrid algorithm, combining genetic algorithm and tabu search, is presented. The LORA problem is solved based on the proposed algorithm to minimize the maintenance cost, thus determining the best repair decisions combinations. Finally, the algorithm is proved to be effective through a comparison study of numerical examples.

level of repair analysis; maintenance cost; genetic algorithm; tabu search

1672- 6413(2015)06- 0011- 03

2015- 01- 28；

2015- 09- 13

賈寶惠(1971-)，女，山西運城人，教授，碩士，研究方向為航空機(jī)電技術(shù)及維修工程。

TP391.7

A