成果介紹: 基于遺傳禁忌搜索混合算法的修理級別問題研究
相關(guān)鏈接： 中國安全網(wǎng) 中國質(zhì)量網(wǎng) 中國論文網(wǎng) 中國資訊網(wǎng)
作者：鄭曉敏
現(xiàn)有文獻中討論了不同的多層、多級的LORA模型[1-9]，這些模型無不涉及大量的決策變量，因此，通過傳統(tǒng)優(yōu)化方法如整數(shù)規(guī)劃和分支定界等很難對LORA問題進行優(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í)行這些活動，從而確定部件進行修理或報廢的位置，并以最低成本滿足維修要求。
1.2 建立數(shù)學(xué)模型
本文研究中，設(shè)i為所研究系統(tǒng)的部件，i=1，2，…，n，n為部件總數(shù)；r為修理選項，包括修理、報廢、移動；e為維修級別。本文參考文獻[1，3，4]所描述的模型，對LORA問題進行建模，通過最小化維修成本獲得最優(yōu)修理決策。
建立的數(shù)學(xué)模型如下：
式(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問題進行求解。
本文的GATS算法首先生成N個初始可能解；然后利用禁忌搜索的迭代過程進行鄰域搜索，對這些解進行更新；之后，流程返回遺傳算法，再進行一個迭代過程；通過遺傳算子產(chǎn)生新的后代，并根據(jù)新的后代的適應(yīng)值對最佳解的禁忌表進行更新。GATS算法的終止準(zhǔn)則是達到了預(yù)定義的連續(xù)迭代次數(shù)，迭代過程獲得的最佳解相同。
GATS算法流程如圖1所示。
GATS算法的具體步驟如下：
(1)隨機產(chǎn)生一個解集（20個解），驗證式(2)、式(3)、式(4)、式(5)。
(2)通過鄰域搜索改進解的適應(yīng)度值。鄰域解僅通過修改解的值為1或o獲得。另外，直到驗證了式(2)～式(5)，才接受鄰域解。然后，更新禁忌表，其中包含所有已探索過的解的適應(yīng)度值。接著，僅當(dāng)適應(yīng)度值不出現(xiàn)于禁忌表中時，探索一個新的鄰域。
(3)重復(fù)步驟(2)，直到最佳適應(yīng)度值沒有改進。
(4)用最佳鄰域替換該解。
(5)基于遺傳算法的選擇算子和交叉算子，選擇兩個解來產(chǎn)生新的染色體。當(dāng)驗證了式(2)～式(5)時，接受這些新的解。
(6)利用變異算子，生成新的染色體。
(7)更新最佳染色體的禁忌表。
(8)重復(fù)以上步驟，直到最佳染色體沒有改進。
2.2 GATS算法設(shè)計
2.2.1編碼方式
用遺傳算法求解特定問題時，首先要確定編碼方式。本文采用的編碼方式是一個二進制矩陣（n×d），其中n為所有部件（即項目）的數(shù)量，d為所有修理決策的數(shù)量。該編碼方式中，xij=1意味著部件i和級別j選擇了修理、報廢或者移動決策。圖2是染色體或解的二進制編碼方式，其中“項目”表示待分析產(chǎn)品，可以是部件或子部件。
另外，任何技術(shù)系統(tǒng)都可視為裝配的集合，這些裝配又可視為一些子裝配的集合。出于建模的考慮，系統(tǒng)分解結(jié)構(gòu)用一個矩陣來表示，稱為共性矩陣，如圖3所示。其中列代表父部件，行表示子部件，子部件4、5、6屬于父部件3，或者說父部件3包含了子部件4、5、6。根據(jù)式(4)，無論何時父部件3采取報廢或移動決策，子部件4、5、6都將采取同樣的決策。
2.2.2適應(yīng)度函數(shù)
本文的目標(biāo)函數(shù)是求解最小值問題，算法的選擇過程采用輪盤選擇法，因此本文采用的適應(yīng)度函數(shù)為：
2.2.3遺傳算法算子
GATS算法使用適應(yīng)度值比例選擇的輪盤賭抽樣作為交叉算子。每一代采用最優(yōu)保存策略，用滿足式(1)的最好的解替換最差的。選擇一對父代進行交叉運算產(chǎn)生兩個新的子代。交叉算子通過交換信息作用于這兩個父染色體。由于每一對父代染色體的基因密碼有著相同的結(jié)構(gòu)，因此隨機選擇交叉點進行單點交叉，接著根據(jù)式(4)調(diào)整子代修理決策。
變異運算是遺傳算法的另一重要特點，是產(chǎn)生新個體的輔助方法，變異運算的目的是維持群體的多樣性，防止解陷入局部最優(yōu)。本文中變異算子從最優(yōu)解列表中隨機選出一個染色體，并用一個同樣是隨機產(chǎn)生的新的染色體替換；另外，選擇一個最優(yōu)解，并隨機為部件產(chǎn)生一個修理決策；然后再根據(jù)式(4)調(diào)整修理決策。
2.2.4鄰域結(jié)構(gòu)
TS的框架由產(chǎn)生自初始解的一些鄰域解組成，通過目標(biāo)函數(shù)對這些解進行評估并分類。禁忌表通過最優(yōu)解的適應(yīng)度進行更新，然后確定一個新的解并從中產(chǎn)生額外的鄰域搜索。當(dāng)一系列迭代之后最佳解保持不變時，便求得了最優(yōu)解。本文采用互換的方法產(chǎn)生鄰域結(jié)構(gòu)。
2.2.5禁忌對象和禁忌表的確定
本文將禁忌對象設(shè)定為狀態(tài)本身，將每次迭代最終接受的解作為禁忌對象放入禁忌表中。禁忌表是禁忌對象的集合。
3實例分析
本節(jié)將根據(jù)數(shù)值實驗的結(jié)果測試GATS算法的有效性。為了比較起見，對文獻[3]執(zhí)行過的案例進行研究。文獻[3]中給出了航空發(fā)動機的三層結(jié)構(gòu)和兩轟修理網(wǎng)絡(luò)，以及所有項目在不同級別上不同修理選項的固定成本和可變成本。另外，圖4給出共性矩陣，顯示父部件（項目1到項目10）與子部件（項目11到項目32）之間的關(guān)系。用MATLAB語言對GATS算法進行編譯，并在電腦上實施該算法。表1為本文GATS算法獲得的最優(yōu)解，與文獻[3]的修理決策相同。另外，文獻[7]中也對文獻[3]執(zhí)行過的案例進行了研究，其中所使用的免疫粒子群算法(IA-PSO)和本文GATS算法得出相應(yīng)的總維修成本分別是4 277. 27美元和4 216. 27美元，計算時間分別為32 s和21 s，如表2所示。
4結(jié)論
(1)在現(xiàn)有LORA研究的基礎(chǔ)上，對LORA問題進行了建模，以最小化維修成本為目標(biāo)，獲得最佳修理級別決策。
(2)利用遺傳-禁忌搜索混合算法，對LORA問題進行了優(yōu)化求解，并給出了算法的求解步驟。利用文獻[3]中的數(shù)據(jù)，通過算例的比較分析，對三級修理網(wǎng)絡(luò)和多級系統(tǒng)結(jié)構(gòu)的修理決策進行了優(yōu)化，結(jié)果表明在合理的時間內(nèi)可獲得LORA問題的最優(yōu)解，證明該算法是切實可行的。與免疫粒子群算法的比較結(jié)果表明了本文算法的有效性。
(3)與相關(guān)文獻研究結(jié)果相比，本文提出的算法更適于求解涉及大量決策變量的LORA問題。結(jié)合工程實際對LORA模型進行改進后，可以用本文提出的算法對LORA問題進行優(yōu)化求解，為維修決策的制定提供參考。
5摘要：
修理級別分析(LORA)是維修決策制定的一個重要工具。由于已有的修理級別分析整數(shù)規(guī)劃模型涉 及大量的決策變量，用傳統(tǒng)的優(yōu)化方法很難對其進行優(yōu)化求解，故提出了一種遺傳禁忌搜索混合算法，以最小化維修成本為目標(biāo)，對LORA問題進行求解，確定最佳修理決策組合。最后通過算例的比較分析，表明了本算法的有效性。
