作者：鄭曉敏

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

1  LORA問題模型的建立

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

    LORA分析是以維修級別與裝備修理的約定層次的劃分為基礎的。維修級別根據裝備的范圍和深度區分任務，并按維修時所處場所劃分等級。航空裝備維修級別分為三級，即基層級(O)、中繼級(I)和基地級(D)。裝備修理約定層次一般劃分為外場可更換件(LRU)、車間可更換件(SRU)、車間可更換件子部件( SSRU)三個層次。對于一個給定的設計，修理級別分析師必須決定哪些部件要修理、哪些部件要報廢、在慘理網絡中何處執行這些活動，從而確定部件進行修理或報廢的位置，并以最低成本滿足維修要求。

1.2 建立數學模型

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

建立的數學模型如下：

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

2.1  算法思路

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

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

GATS算法流程如圖1所示。

    GATS算法的具體步驟如下：

    (1)隨機產生一個解集（20個解），驗證式(2)、式(3)、式(4)、式(5)。

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

    (3)重復步驟(2)，直到最佳適應度值沒有改進。

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

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

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

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

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

2.2   GATS算法設計

2.2.1編碼方式

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

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

2.2.2適應度函數

    本文的目標函數是求解最小值問題，算法的選擇過程采用輪盤選擇法，因此本文采用的適應度函數為：

2.2.3遺傳算法算子

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

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

2.2.4鄰域結構

    TS的框架由產生自初始解的一些鄰域解組成，通過目標函數對這些解進行評估并分類。禁忌表通過最優解的適應度進行更新，然后確定一個新的解并從中產生額外的鄰域搜索。當一系列迭代之后最佳解保持不變時，便求得了最優解。本文采用互換的方法產生鄰域結構。

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

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

3實例分析

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

4結論

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

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

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

5摘要：

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