基于遺傳禁忌搜索混合算法的修理級(jí)別問(wèn)題研究

賈寶惠，周 帆

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

基于遺傳禁忌搜索混合算法的修理級(jí)別問(wèn)題研究

賈寶惠，周 帆

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

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

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

中國(guó)民航大學(xué)預(yù)研重大項(xiàng)目(3122014P002)

0 引言

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

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

1 LORA問(wèn)題模型的建立

1.1 航空裝備維修級(jí)別和層次劃分

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

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

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

(1)

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

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

(2)

(3)

Xr,e,j=Xr,e,i,?e,其中r=報(bào)廢或者移動(dòng).

(4)

(5)

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

2 求解算法設(shè)計(jì)

2.1 算法思路

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

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

GATS算法流程如圖1所示。

圖1 GATS算法的流程

GATS算法的具體步驟如下：

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

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

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

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

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

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

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

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

2.2 GATS算法設(shè)計(jì)

2.2.1 編碼方式

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

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

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

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

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

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

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

(6)

2.2.3 遺傳算法算子

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

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

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

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

2.2.5 禁忌對(duì)象和禁忌表的確定

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

3 實(shí)例分析

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

圖4 共性矩陣

項(xiàng)目級(jí)別2級(jí)別3修理報(bào)廢移動(dòng)修理報(bào)廢項(xiàng)目110000項(xiàng)目200101項(xiàng)目301000項(xiàng)目401000??????項(xiàng)目3100101項(xiàng)目3201000

表2 IA-PSO與GATS算法比較

4 結(jié)論

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

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

(3) 與相關(guān)文獻(xiàn)研究結(jié)果相比，本文提出的算法更適于求解涉及大量決策變量的LORA問(wèn)題。結(jié)合工程實(shí)際對(duì)LORA模型進(jìn)行改進(jìn)后，可以用本文提出的算法對(duì)LORA問(wèn)題進(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ī)修理級(jí)別優(yōu)化模型[J].航空學(xué)報(bào),2009(2):247-253.

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

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

[10]王超.基于混合遺傳禁忌搜索算法的多目標(biāo)柔性作業(yè)車間調(diào)度問(wèn)題研究[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-)，女，山西運(yùn)城人，教授，碩士，研究方向?yàn)楹娇諜C(jī)電技術(shù)及維修工程。

TP391.7

A