基于改進遺傳算法的裝備保障效能評估指標約簡

潘成勝，周 敏，杜秀麗，呂亞娜

(大連大學通信與網絡重點實驗室，遼寧 大連 116622)

1 引言

裝備保障系統效能評估以裝備保障理論與系統評估理論為基礎，通過多種技術對裝備保障系統指揮、維修、供應等效能進行綜合評價，是對裝備保障系統效能的計算度量[1]，不僅可以綜合反映裝備保障系統的組成要素、運行機制等情況[2]，而且對保障資源合理配置、保障系統優化設計等具有重要指導作用，已成為一項重要而緊迫的任務[3]。

裝備保障系統組織規模龐大、結構復雜，其效能評估指標繁多且相互聯系、相互冗余[4]，直接使用這些評估指標會導致評估模型維數較高、求解困難、評估效率低等問題。因此，研究裝備保障系統效能評估指標約簡意義重大。

楊志遠等[5]以主動雷達導引頭干擾效能評估指標體系為研究對象，采用粗糙集理論對指標體系進行屬性約簡。杜鋒等[6]通過驗證各評價指標相對于決策屬性是否必要以及各子集組合相對于決策屬性是否獨立，對裝備保障指揮系統效能評估指標體系進行約簡。Wang等[7]利用粗糙集理論與灰色關聯分析法對評估指標進行篩選，不僅保留了關鍵指標，而且允許指標相互獨立。Xu等[8]應用粗糙集屬性約簡算法對雷達干擾效能評估指標體系進行約簡，刪除了冗余屬性。上述方法主要基于粗糙集理論進行指標約簡，但是該方法屬于NP完全問題，其分明矩陣的構建過程復雜度較高，無法適應大數據量下的指標約簡工作。宋佳成等[9]針對反導預警雷達效能評估指標體系中存在信息重疊問題，采用灰色關聯分析理論對指標體系進行約簡。該方法需要對各項指標的最優值進行現行確定，主觀性過強，同時部分指標最優值難以確定，收斂性較差。

遺傳算法[10]是一類可以用于復雜系統優化的搜索算法，魯棒性較強且收斂性好。然而，傳統的遺傳算法(Standard Genetic Algorithm， SGA)在交叉和變異時采用固定概率進行求解，當選取的概率較大時，會破壞種群穩定性，使算法淪為隨機搜索，較小時算法容易陷入局部極值，降低優化效率[11]。針對傳統遺傳算法存在的問題，較多學者提出了自適應機制，在算法搜索過程中動態調整交叉概率與變異概率。Sriniva等[12]提出了自適應遺傳算法(Adaptive Genetic Algorithm， AGA)，該算法中交叉概率與變異概率隨著種群適應度進行線性調整，但該算法在初期易陷入局部極值，難以找到全局最優解。楊從銳等[13]提出了一種非線性自適應調節交叉概率與變異概率的自適應遺傳算法(Improve Adaptive Genetic Algorithm， IAGA)，但是該算法沒有考慮種群大部分的個體適應度較小而只有少數個體適應度大的情況。金立兵等[14]提出了一種基于Sigmoid函數曲線的非線性自適應遺傳算法，但該算法在進化初期變異概率過大，可能會使得算法收斂性能降低。

基于以上分析，本文提出一種基于改進遺傳算法的裝備保障系統效能評估指標約簡方法。該方法首先對遺傳算法進行改進，以強精英參與、完備交叉、預變異策略完成遺傳算法的選擇、交叉與變異操作；然后將改進后的遺傳算法用于裝備保障系統效能評估指標約簡，以利用更少指標得到更高的評估精度。

2 裝備保障系統效能評估指標體系構建

本文遵循完備性、目的性、客觀性、層次性等指標體系設計原則[15]，結合裝備保障自身特性，建立裝備保障系統效能評估指標體系，其構建步驟如圖1所示。

圖1 裝備保障系統指標體系構建流程示意圖

1)分析裝備保障系統，得到效能指標構成體系；

2)分析裝備保障影響因素，從中篩選出影響裝備保障效能的主要因素；

3)以效能指標為源頭，對各效能指標進行層次分解，構造評估指標體系的遞階層次結構，即樹型結構；

4)選取與裝備保障效能評估的相關屬性指標，描述裝備保障效能評估指標體系中個指標的含義，建立能夠全面衡量裝備保障系統效能的評估指標體系。

基于上述分析，構建的效能評估指標體系如圖2所示。

圖2 裝備保障系統效能評估指標體系

3 基于改進遺傳算法的裝備保障系統效能評估指標約簡

3.1 完備交叉與預變異

遺傳算法模擬自然界優勝劣汰的進化現象，將待優化問題解集的搜索空間映射為遺傳空間，根據適應度值進行選擇、交叉與變異操作，完成種群進化過程，最終獲取最優解。其中，交叉操作主要對遺傳空間進行探索，通過對父代個體進行交叉操作以產生新個體；變異操作是遺傳算法中的輔助性搜索操作，其主要目的是通過變異算子找到新基因，以維持種群多樣性，使算法跳出局部最優解。上述操作是遺傳算法的關鍵所在，直接影響算法性能。

1)交叉、變異問題分析

SGA算法采用固定值的交叉概率與變異概率，該方法雖然使得算法簡單易行，但是容易陷入局部最優解，且算法收斂性較差。針對上述問題，較多學者提出了各種自適應遺傳算法。在算法初期，使用較大的交叉概率與較小的變異概率，促進種群進化，加快算法收斂速度；算法運行到后期，使用較小的交叉概率與較大的變異概率，以維持種群多樣性，跳出局部最優解，其交叉概率與變異概率按式(1)[16]進行自適應調整

(1)

其中，fmax表示種群最大適應度值，favg表示種群平均適應度值，f表示交叉個體中較大的適應度值，f′表示變異個體適應度值。

雖然現有自適應遺傳算法在收斂速度與精度方面有了一定提高，但是多數自適應算法根據適應度值動態調整交叉與變異概率，難以控制這兩個概率的平衡點，且當個體適應度值高于種群平均適應度值時，自適應遺傳算法處理方式較為單一，算法后期存在收斂速度慢等缺點。基于上述分析，本文通過完備交叉與預變異操作來避免以上問題。

2)完備交叉操作

完備交叉操作的基本思想：在遺傳算法種群中，不論是“優良”個體還是“劣質”個體，其附近都可能存在優質解，因此，本文認為在當前代種群中，所有的個體都應該進行交叉操作，以保證新產生的個體不會遺漏優質解。因此將父代個體通過均勻交叉算法進行兩兩交叉，得到備選子代個體。

3)預變異操作

預變異操作的基本思想：將父代個體與備選子代分別通過單點變異算法進行預變異，得到預變異個體，對父代個體與預變異個體的適應度值以及備選子代個體與預變異個體的適應度值進行求解，當預變異個體的適應度值大于其自身適應度值時，則意味著該個體的變異操作是有效的，產生變異個體，否則該個體的變異操作是無效的，不產生變異個體。最后，將通過完備交叉與預變異操作后的個體進行適應度值排序，得到下一代個體。

基于上述思想，本文提出一種基于預變異與完備交叉的遺傳算法(Genetic algorithm based on pre-mutation and complete crossover， PMCCGA)。

3.2 基于遺傳算法的裝備保障系統效能評估指標約簡算法

裝備保障系統指標繁多，直接通過這些指標進行效能評估求解復雜度高且求解誤差較大，通過指標約簡可以有效提高效能評估的速度與精度。本文首先采用完備交叉與預變異策略對遺傳算法中的交叉與變異操作進行改進，通過綜合互信息與選擇比例構造算法適應度函數，然后將改進后的遺傳算法用于裝備保障系統效能評估指標約簡，提高裝備保障系統效能評估精確度。

基于改進遺傳算法的裝備保障系統效能評估指標約簡算法步驟如下：

1)裝備保障系統效能評估指標編碼

本文采用二進制編碼方式，用0和1表示未選中指標和選中指標。假設某裝備保障系統效能評估數據集Ω中，有n個樣本，每個樣本有m個效能評估指標和1個評估等級標簽，將評估等級劃分為k級，則每個樣本可以表示為Xi={xi1，xi2，…，xim，labeli}，i=1，2，…，n，其中xij表示第i個樣本第j個效能評估指標值，labeli表示第i個樣本的效能評估等級，則用一個長度為m的0和1字符串來表示效能評估指標組合G=(g1，g2，…，gm)，其中gi=0表示該效能評估指標被丟棄，gi=1表示該效能評估指標被選中。

2)遺傳算法初始化

設置種群規模、最大迭代次數以及產生初始種群。

3)計算適應度函數

本文將綜合互信息以及選擇比例作為遺傳算法適應度函數，要求綜合互信息值盡可能大，選擇比例盡可能小。根據以上分析，可知在進行裝備保障系統效能評估指標系統約簡時有兩個優化目標：1)最大化綜合互信息值；2)最小化選擇比例。

優化第一個目標，可以建立如式(2)的目標函數

(2)

式中，n表示已選裝備保障系統效能評估指標個數，Xi、Xk表示n個評估指標中的第i和第k個(i≠k)指標，Y表示裝備保障系統效能評估等級，參數α、β為調節參數，α，β∈[0，1]。上式第1項為所有已選效能評估指標與效能評估等級之間的互信息和，第2項為已選效能評估指標之間的互信息，第3項為在評估等級已知的條件下，已選效能評估指標之間的條件互信息。

優化第二個目標，可以建立如式(3)所示的目標函數，該式表示已選效能評估指標個數占總效能評估指標個數的比例值。

(3)

其中，k表示裝備保障系統效能評估指標體系中已選指標個數，m表示總指標個數。

將式(2)、(3)結合，建立式如式(4)所示的綜合目標函數，通過優化綜合目標函數能夠同時優化兩個目標。

F=α1f1-α2f2，α1+α2=1

(4)

α1、α2是調節參數，用來調整互信息與所選指標個數的相對重要程度。由于F函數的取值范圍較小，不同個體對應的目標函數值差異可能很小，遺傳算法在進行選擇操作時不能有效的將適應度值高的個體選擇出來，從而影響遺傳算法的收斂速度與尋優結果。因此需要對F函數進行放大處理，本文采用指數函數的方法。

(5)

其中，λ為放大差異參數，是一個隨進化代數增加而逐漸增加的動態變化的數，t為當前的進化代數，T為最大迭代次數，Favg是當前種群平均適應度值，ξ是一個足夠小的數，防止分母為0。

4)判斷是否達到最大迭代次數，若是，則輸出當前的最優效能評估指標子集，否則執行以下步驟。

5)執行選擇操作

將父代個體與子代個體按照適應度值大小進行排序，選擇適應度值大的個體進入下一次迭代運算。

6)執行交叉操作

將所有的父代個體進行均勻交叉產生備選子代個體，并計算備選子代個體適應度值。

7)執行預變異操作

將所有父代個體與備選子代個體通過單點變異操作進行預變異，然后計算預變異個體適應度值，若預變異個體適應度值大于當前個體適應度值，則產生變異，否則不進行變異操作。

8)返回步驟4)。

4 仿真分析

為了驗證本文所提算法的有效性，按照圖3所示的仿真方案流程進行仿真。仿真中用到的Wine、Parkinsons和BreastCancer數據集為UCI公開數據集，裝備保障效能評估指標數據集(Equipment Support System Effectiveness Evaluation Index data set，ESSEEI)則是通過相關調研獲得，實驗數據集如表1所示。

圖3 仿真方案流程示意圖

表1 實驗數據集

在本文算法中，不同參數的選取會影響算法的收斂性能與尋優精度。因此，本文將通過實驗一確定參數的合理取值。實驗一通過控制變量法對α、β、α1、α2的取值進行仿真，仿真結果如圖4所示。

圖4 α、β、α1、α2取值仿真曲線

從圖4的仿真結果可以得到，當α=0.9、β=0.1、α1=0.7、α2=0.3時，SVM分類準確率最高。

實驗二主要用來驗證改進后遺傳算法的性能，選取5個復雜函數作為測試工具，將改進后的遺傳算法與AGA、IAGA進行比較驗證。

f1=xsin(10πx)+2.0，x∈[-1，2]

(6)

式(6)函數是一元多峰值函數，其函數圖像如圖5所示，在函數定義域內，該函數存在多個極大值，其全局最大值為3.8503，通過該函數可以測試算法在存在多個極值時的全局尋優能力。

圖5 函數f1圖像

函數(7)圖像如圖6所示，在該函數定義域內存在多個局部最優點，其全局最大值為11.7525。當算法全局尋優能力較差時，算法易收斂于局部最大值10.8221。

圖6 函數f2圖像

x1，x2∈[-10，10]

(8)

式(8)函數是二元多峰函數，其函數圖像如圖7所示。在該函數中，每個峰頂都存在一個局部最大值，但該函數只有一個全局最大值1.0000。

圖7 函數f3圖像

x1，x2∈[-10，10]

(9)

式(9)函數是二維復雜函數，其函數圖像如圖8所示。在函數定義域內，該函數具有無窮多個極值點，在(0，0)處取得全局最大值1.0000。由于該函數具有強烈震蕩的性態，如果算法全局搜索能力較弱，則很容易陷入局部最優值。通過該函數可以測試算法跳出局部最優的能力。

圖8 函數f4圖像

(10)

圖9 函數f5圖像

對上述5個函數進行500次尋優計算，其實驗結果如表2所示。

由表2的實驗結果可以看出，在5組測試函數中，AGA的平均收斂代數分別是本文算法的9.5倍、6.43倍、5.71倍、9.33倍、2.8倍；IAGA的平均收斂代數分別是本文算法的6.75倍、4.29倍、3.71倍、5.67倍、2.1倍。同時，在5組測試函數進行500次尋優計算時，AGA分別未收斂43次、47次、54次、51次、47次；IAGA分別未收斂37次、20次、17次、14次、21次，而本文算法不存在未收斂情況。由上述分析可知，本文算法無論在算法收斂性方面還是算法穩定上均優于其它兩種算法。在平均收斂值方面，本文所提算法在測試函數1、2、3、5中，與AGA、IAGA相比，平均收斂值較大，與函數理論值的誤差最小，更加接近函數理論上的最大值，且在函數1中，本文所提算法找到了函數理論上的最大值；在函數2中，本文所提算法的平均收斂值雖然比IGAG略低，但收斂次數與收斂代數比IGAG好。由平均收斂值可知，本文所提算法具有較好的全局尋優能力。

表2 3種算法在5個函數驗證時的對比結果

實驗三將本文算法與灰色關聯分析法、粗糙集屬性約簡算法進行對比，通過ESSEEI數據集驗證了本文算法在裝備保障系統效能評估指標約簡中的有效性，實驗結果如圖10、11所示。

圖10 不同算法在SVM分類器中的分類準確率

圖10為不同算法下約簡的裝備保障系統效能評估指標在SVM分類器上學習所得到的分類準確率。由圖10可知，本文算法在ESSEEI數據集上具有更好的評估準確率，最高評估準確率為90.7%，而層次分析法與灰色關聯分析法的最高評估準確率分別為87.8%和88.6%。同時本文算法能夠選擇更少的關鍵效能評估指標，所選效能評估指標個數為29個，粗糙集屬性約簡算法與灰色關聯分析法所選效能評估指標個數分別為50個和43個。因此，本文算法能夠在得到更高評估準確率的同時選擇更少的效能評估指標個數。

圖11為不同算法下SVM分類器ROC (Receiver Operating Characteristic)曲線圖與AUC(Area Under roc Curve)值。ROC曲線將真正例率和假正例率結合，能夠準確反映某種分類器真正例率和假正例率的關系。ROC曲線越靠近左上角，模型的準確性就越高。AUC值為ROC曲線所覆蓋的區域面積，AUC值越大，其分類效果越好。由圖11可知，使用本文算法約簡后的裝備保障系統效能評估指標作為SVM分類器的輸入，其ROC曲線最靠近左上角，且本文算法的AUC值最大。

圖11 不同算法下SVM分類器ROC曲線

5 結束語

裝備保障系統效能評估過程中存在大量相互聯系、相互冗余的效能評估指標，通過原有指標進行裝備保障效能評估復雜度高且精度較低，因此，本文提出了基于改進遺傳算法的裝備保障系統效能評估指標約簡算法。通過算法性能測試函數仿真結果表明，本文所提算法具有較好的收斂性能與全局尋優能力，將其用于裝備保障系統效能評估指標約簡，能夠建立合理的裝備保障效能評估指標體系，對裝備保障系統進行準確評估。