基于改進(jìn)遺傳算法的裝備保障效能評估指標(biāo)約簡

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

(大連大學(xué)通信與網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室，遼寧 大連 116622)

1 引言

裝備保障系統(tǒng)效能評估以裝備保障理論與系統(tǒng)評估理論為基礎(chǔ)，通過多種技術(shù)對裝備保障系統(tǒng)指揮、維修、供應(yīng)等效能進(jìn)行綜合評價(jià)，是對裝備保障系統(tǒng)效能的計(jì)算度量[1]，不僅可以綜合反映裝備保障系統(tǒng)的組成要素、運(yùn)行機(jī)制等情況[2]，而且對保障資源合理配置、保障系統(tǒng)優(yōu)化設(shè)計(jì)等具有重要指導(dǎo)作用，已成為一項(xiàng)重要而緊迫的任務(wù)[3]。

裝備保障系統(tǒng)組織規(guī)模龐大、結(jié)構(gòu)復(fù)雜，其效能評估指標(biāo)繁多且相互聯(lián)系、相互冗余[4]，直接使用這些評估指標(biāo)會(huì)導(dǎo)致評估模型維數(shù)較高、求解困難、評估效率低等問題。因此，研究裝備保障系統(tǒng)效能評估指標(biāo)約簡意義重大。

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

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

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

2 裝備保障系統(tǒng)效能評估指標(biāo)體系構(gòu)建

本文遵循完備性、目的性、客觀性、層次性等指標(biāo)體系設(shè)計(jì)原則[15]，結(jié)合裝備保障自身特性，建立裝備保障系統(tǒng)效能評估指標(biāo)體系，其構(gòu)建步驟如圖1所示。

圖1 裝備保障系統(tǒng)指標(biāo)體系構(gòu)建流程示意圖

1)分析裝備保障系統(tǒng)，得到效能指標(biāo)構(gòu)成體系；

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

3)以效能指標(biāo)為源頭，對各效能指標(biāo)進(jìn)行層次分解，構(gòu)造評估指標(biāo)體系的遞階層次結(jié)構(gòu)，即樹型結(jié)構(gòu)；

4)選取與裝備保障效能評估的相關(guān)屬性指標(biāo)，描述裝備保障效能評估指標(biāo)體系中個(gè)指標(biāo)的含義，建立能夠全面衡量裝備保障系統(tǒng)效能的評估指標(biāo)體系。

基于上述分析，構(gòu)建的效能評估指標(biāo)體系如圖2所示。

圖2 裝備保障系統(tǒng)效能評估指標(biāo)體系

3 基于改進(jìn)遺傳算法的裝備保障系統(tǒng)效能評估指標(biāo)約簡

3.1 完備交叉與預(yù)變異

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

1)交叉、變異問題分析

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

(1)

其中，fmax表示種群最大適應(yīng)度值，favg表示種群平均適應(yīng)度值，f表示交叉?zhèn)€體中較大的適應(yīng)度值，f′表示變異個(gè)體適應(yīng)度值。

雖然現(xiàn)有自適應(yīng)遺傳算法在收斂速度與精度方面有了一定提高，但是多數(shù)自適應(yīng)算法根據(jù)適應(yīng)度值動(dòng)態(tài)調(diào)整交叉與變異概率，難以控制這兩個(gè)概率的平衡點(diǎn)，且當(dāng)個(gè)體適應(yīng)度值高于種群平均適應(yīng)度值時(shí)，自適應(yīng)遺傳算法處理方式較為單一，算法后期存在收斂速度慢等缺點(diǎn)?；谏鲜龇治?，本文通過完備交叉與預(yù)變異操作來避免以上問題。

2)完備交叉操作

完備交叉操作的基本思想：在遺傳算法種群中，不論是“優(yōu)良”個(gè)體還是“劣質(zhì)”個(gè)體，其附近都可能存在優(yōu)質(zhì)解，因此，本文認(rèn)為在當(dāng)前代種群中，所有的個(gè)體都應(yīng)該進(jìn)行交叉操作，以保證新產(chǎn)生的個(gè)體不會(huì)遺漏優(yōu)質(zhì)解。因此將父代個(gè)體通過均勻交叉算法進(jìn)行兩兩交叉，得到備選子代個(gè)體。

3)預(yù)變異操作

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

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

3.2 基于遺傳算法的裝備保障系統(tǒng)效能評估指標(biāo)約簡算法

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

基于改進(jìn)遺傳算法的裝備保障系統(tǒng)效能評估指標(biāo)約簡算法步驟如下：

1)裝備保障系統(tǒng)效能評估指標(biāo)編碼

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

2)遺傳算法初始化

設(shè)置種群規(guī)模、最大迭代次數(shù)以及產(chǎn)生初始種群。

3)計(jì)算適應(yīng)度函數(shù)

本文將綜合互信息以及選擇比例作為遺傳算法適應(yīng)度函數(shù)，要求綜合互信息值盡可能大，選擇比例盡可能小。根據(jù)以上分析，可知在進(jìn)行裝備保障系統(tǒng)效能評估指標(biāo)系統(tǒng)約簡時(shí)有兩個(gè)優(yōu)化目標(biāo)：1)最大化綜合互信息值；2)最小化選擇比例。

優(yōu)化第一個(gè)目標(biāo)，可以建立如式(2)的目標(biāo)函數(shù)

(2)

式中，n表示已選裝備保障系統(tǒng)效能評估指標(biāo)個(gè)數(shù)，Xi、Xk表示n個(gè)評估指標(biāo)中的第i和第k個(gè)(i≠k)指標(biāo)，Y表示裝備保障系統(tǒng)效能評估等級(jí)，參數(shù)α、β為調(diào)節(jié)參數(shù)，α，β∈[0，1]。上式第1項(xiàng)為所有已選效能評估指標(biāo)與效能評估等級(jí)之間的互信息和，第2項(xiàng)為已選效能評估指標(biāo)之間的互信息，第3項(xiàng)為在評估等級(jí)已知的條件下，已選效能評估指標(biāo)之間的條件互信息。

優(yōu)化第二個(gè)目標(biāo)，可以建立如式(3)所示的目標(biāo)函數(shù)，該式表示已選效能評估指標(biāo)個(gè)數(shù)占總效能評估指標(biāo)個(gè)數(shù)的比例值。

(3)

其中，k表示裝備保障系統(tǒng)效能評估指標(biāo)體系中已選指標(biāo)個(gè)數(shù)，m表示總指標(biāo)個(gè)數(shù)。

將式(2)、(3)結(jié)合，建立式如式(4)所示的綜合目標(biāo)函數(shù)，通過優(yōu)化綜合目標(biāo)函數(shù)能夠同時(shí)優(yōu)化兩個(gè)目標(biāo)。

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

(4)

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

(5)

其中，λ為放大差異參數(shù)，是一個(gè)隨進(jìn)化代數(shù)增加而逐漸增加的動(dòng)態(tài)變化的數(shù)，t為當(dāng)前的進(jìn)化代數(shù)，T為最大迭代次數(shù)，F(xiàn)avg是當(dāng)前種群平均適應(yīng)度值，ξ是一個(gè)足夠小的數(shù)，防止分母為0。

4)判斷是否達(dá)到最大迭代次數(shù)，若是，則輸出當(dāng)前的最優(yōu)效能評估指標(biāo)子集，否則執(zhí)行以下步驟。

5)執(zhí)行選擇操作

將父代個(gè)體與子代個(gè)體按照適應(yīng)度值大小進(jìn)行排序，選擇適應(yīng)度值大的個(gè)體進(jìn)入下一次迭代運(yùn)算。

6)執(zhí)行交叉操作

將所有的父代個(gè)體進(jìn)行均勻交叉產(chǎn)生備選子代個(gè)體，并計(jì)算備選子代個(gè)體適應(yīng)度值。

7)執(zhí)行預(yù)變異操作

將所有父代個(gè)體與備選子代個(gè)體通過單點(diǎn)變異操作進(jìn)行預(yù)變異，然后計(jì)算預(yù)變異個(gè)體適應(yīng)度值，若預(yù)變異個(gè)體適應(yīng)度值大于當(dāng)前個(gè)體適應(yīng)度值，則產(chǎn)生變異，否則不進(jìn)行變異操作。

8)返回步驟4)。

4 仿真分析

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

圖3 仿真方案流程示意圖

表1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

從圖4的仿真結(jié)果可以得到，當(dāng)α=0.9、β=0.1、α1=0.7、α2=0.3時(shí)，SVM分類準(zhǔn)確率最高。

實(shí)驗(yàn)二主要用來驗(yàn)證改進(jìn)后遺傳算法的性能，選取5個(gè)復(fù)雜函數(shù)作為測試工具，將改進(jìn)后的遺傳算法與AGA、IAGA進(jìn)行比較驗(yàn)證。

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

(6)

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

圖5 函數(shù)f1圖像

函數(shù)(7)圖像如圖6所示，在該函數(shù)定義域內(nèi)存在多個(gè)局部最優(yōu)點(diǎn)，其全局最大值為11.7525。當(dāng)算法全局尋優(yōu)能力較差時(shí)，算法易收斂于局部最大值10.8221。

圖6 函數(shù)f2圖像

x1，x2∈[-10，10]

(8)

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

圖7 函數(shù)f3圖像

x1，x2∈[-10，10]

(9)

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

圖8 函數(shù)f4圖像

(10)

圖9 函數(shù)f5圖像

對上述5個(gè)函數(shù)進(jìn)行500次尋優(yōu)計(jì)算，其實(shí)驗(yàn)結(jié)果如表2所示。

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

表2 3種算法在5個(gè)函數(shù)驗(yàn)證時(shí)的對比結(jié)果

實(shí)驗(yàn)三將本文算法與灰色關(guān)聯(lián)分析法、粗糙集屬性約簡算法進(jìn)行對比，通過ESSEEI數(shù)據(jù)集驗(yàn)證了本文算法在裝備保障系統(tǒng)效能評估指標(biāo)約簡中的有效性，實(shí)驗(yàn)結(jié)果如圖10、11所示。

圖10 不同算法在SVM分類器中的分類準(zhǔn)確率

圖10為不同算法下約簡的裝備保障系統(tǒng)效能評估指標(biāo)在SVM分類器上學(xué)習(xí)所得到的分類準(zhǔn)確率。由圖10可知，本文算法在ESSEEI數(shù)據(jù)集上具有更好的評估準(zhǔn)確率，最高評估準(zhǔn)確率為90.7%，而層次分析法與灰色關(guān)聯(lián)分析法的最高評估準(zhǔn)確率分別為87.8%和88.6%。同時(shí)本文算法能夠選擇更少的關(guān)鍵效能評估指標(biāo)，所選效能評估指標(biāo)個(gè)數(shù)為29個(gè)，粗糙集屬性約簡算法與灰色關(guān)聯(lián)分析法所選效能評估指標(biāo)個(gè)數(shù)分別為50個(gè)和43個(gè)。因此，本文算法能夠在得到更高評估準(zhǔn)確率的同時(shí)選擇更少的效能評估指標(biāo)個(gè)數(shù)。

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

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

5 結(jié)束語

裝備保障系統(tǒng)效能評估過程中存在大量相互聯(lián)系、相互冗余的效能評估指標(biāo)，通過原有指標(biāo)進(jìn)行裝備保障效能評估復(fù)雜度高且精度較低，因此，本文提出了基于改進(jìn)遺傳算法的裝備保障系統(tǒng)效能評估指標(biāo)約簡算法。通過算法性能測試函數(shù)仿真結(jié)果表明，本文所提算法具有較好的收斂性能與全局尋優(yōu)能力，將其用于裝備保障系統(tǒng)效能評估指標(biāo)約簡，能夠建立合理的裝備保障效能評估指標(biāo)體系，對裝備保障系統(tǒng)進(jìn)行準(zhǔn)確評估。