基于遺傳K均值算法的軍事裝備試驗(yàn)數(shù)據(jù)分組模型

馬晨光，劉慶國，李亞雄

(火箭軍工程大學(xué)， 西安 710025)

裝備試驗(yàn)與評(píng)價(jià)是按照規(guī)定的程序、條件和方法獲取裝備的特性數(shù)據(jù)，并通過數(shù)據(jù)處理分析，考核驗(yàn)證裝備的特性是否滿足要求的活動(dòng)[1]。隨著信息化進(jìn)程的不斷深入，現(xiàn)代戰(zhàn)爭對(duì)于軍事裝備維修保養(yǎng)的要求也不斷提高[2]。現(xiàn)有的軍事裝備維修保養(yǎng)引入了一些高科技手段，但如何在軍事裝備數(shù)量繁多，標(biāo)準(zhǔn)要求高的軍事裝備維修保養(yǎng)中，科學(xué)合理地安排維修保養(yǎng)計(jì)劃仍是各級(jí)指揮員的當(dāng)務(wù)之急。

K均值算法是一種無監(jiān)督的聚類分析方法，但其分組數(shù)目需要事先指定，容易陷入局部最優(yōu)，不具有客觀性，而采用具有全局搜索能力的遺傳算法則能夠?qū)崿F(xiàn)分組數(shù)目的自動(dòng)學(xué)習(xí)。本研究以軍事裝備為研究對(duì)象，建立了基于遺傳K均值算法的聚類分組模型，將不同的軍事裝備劃分到不同的組。基于此，指揮員可以按照不同組別指定不同的維修保養(yǎng)計(jì)劃，使得軍事裝備的維修保養(yǎng)更加科學(xué)化，更有利于長期戰(zhàn)斗力生成。

1 相似性度量

相似性度量是進(jìn)行聚類分組的依據(jù)，本文將不同軍事裝備試驗(yàn)數(shù)據(jù)進(jìn)行歸一化處理，采用歐氏距離作為相似性度量。在此之前需要進(jìn)行數(shù)據(jù)清理、數(shù)據(jù)集成、數(shù)據(jù)裝換和數(shù)據(jù)消減的數(shù)據(jù)預(yù)處理，詳見文獻(xiàn)[3]。由于各項(xiàng)軍事裝備試驗(yàn)數(shù)據(jù)采取的分制不同，需歸一化后才能進(jìn)行聚類分組。假設(shè)m=[ma,mb,…,mNN]和n=[na,nb,…,nNN]為兩個(gè)軍事裝備，其中NN為軍事裝備試驗(yàn)數(shù)據(jù)項(xiàng)目的總數(shù)。歸一化處理公式為

(1)

其中amax和amin為軍事裝備試驗(yàn)數(shù)據(jù)a項(xiàng)的最大最小值，在歸一化處理后，采用加權(quán)系數(shù)的歐式距離作為相似性度量

(2)

其中ωkk為權(quán)系數(shù)。

2 K均值算法

K均值算法是一種使用最廣泛的聚類算法[4-5]。算法以K為參數(shù)，把軍事裝備分為K個(gè)簇，使組內(nèi)具有較高的相似度，而組間相似度較低。算法首先隨機(jī)選擇K個(gè)軍事裝備，每個(gè)軍事裝備初始代表了一個(gè)簇的平均值或中心，對(duì)剩余的每個(gè)軍事裝備根據(jù)其與各個(gè)簇中心的距離，將它賦給最近的簇，然后重新計(jì)算每個(gè)簇的平均值，不斷重復(fù)該過程，直到準(zhǔn)則函數(shù)收斂。準(zhǔn)則函數(shù)為

(3)

式中：p表示軍事裝備試驗(yàn)數(shù)據(jù)；Ci表示第i個(gè)分組；mi表示組Ci的聚類中心。

K均值算法的描述如下：

1) 任意選擇K個(gè)軍事裝備的試驗(yàn)數(shù)據(jù)作為初始的聚類中心。

2) 計(jì)算每個(gè)軍事裝備的試驗(yàn)數(shù)據(jù)與K個(gè)聚類中心的距離，并將距離聚類中心最近的其他軍事裝備試驗(yàn)數(shù)據(jù)劃分到一組。

3) 計(jì)算每個(gè)組的質(zhì)心(聚集點(diǎn)的均值)并重新計(jì)算每個(gè)軍事裝備的試驗(yàn)數(shù)據(jù)到質(zhì)心的距離，并根據(jù)最小距離重新對(duì)相應(yīng)的對(duì)象進(jìn)行劃分。重復(fù)該步驟，直到式1)不再明顯發(fā)生變化。

3 基于遺傳K均值算法的聚類分組模型

由于K均值算法對(duì)初始聚類中心比較敏感，容易陷入局部最優(yōu)，加入具有全局搜索能力的遺傳算法[6-7]則能夠有效地解決該問題。

1) 染色體編碼

本研究采用實(shí)數(shù)編碼方式進(jìn)行編碼。圖1中G1，G2，…，Gk為初始聚類中心點(diǎn)。

G1G2…Gk

圖1 編碼示意圖

2) 初始種群的生成

為了獲得全局最優(yōu)解，初始種群完全隨機(jī)生成。先將每個(gè)樣本隨機(jī)指派為某一類作為最初的聚類劃分，并計(jì)算各類的聚類中心作為初始個(gè)體的染色體編碼，共生成K個(gè)初始種群個(gè)體，由此產(chǎn)生第一代種群。

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

本文的適應(yīng)度函數(shù)計(jì)算式為

(4)

其中：a和b為正的常系數(shù)；E為準(zhǔn)則函數(shù)，描述分組的緊密性；Gb描述的是組間的離散性，式(4)的含義為組間距離越大，組內(nèi)距離越小，適應(yīng)度函數(shù)值越大

(5)

式(5)中ci,cj分別為第i,j個(gè)聚類中心。

4) 遺傳算子

選擇：采用適應(yīng)度比例法，根據(jù)各個(gè)體的適應(yīng)度計(jì)算個(gè)體被選中的概率，用輪盤賭方法進(jìn)行個(gè)體的選擇。

交叉：本研究采用單點(diǎn)交叉：在兩條需要交叉的染色體上，隨機(jī)選取交叉點(diǎn)，然后交換交叉點(diǎn)右側(cè)的基因，得到兩個(gè)新的染色體。

變異：其具體操作過程是：對(duì)于每個(gè)變異點(diǎn)，從對(duì)應(yīng)基因位的取值范圍內(nèi)取一隨機(jī)數(shù)代替原有基因值。

結(jié)合K均值算法和遺傳算法，得到遺傳K均值算法流程(見圖2)：

① 設(shè)置參數(shù)，包括初始分組數(shù)目K，種群的規(guī)模Mt，遺傳終止代數(shù)hf，交叉概率Pc和變異概率Pm；

② 隨機(jī)產(chǎn)生初始種群；

③ 以種群個(gè)體為聚類中心，采用K均值算法進(jìn)行聚類分組，計(jì)算個(gè)體的適應(yīng)度值；

④ 按照上文的遺傳算子設(shè)計(jì)方法，得到新的后代；

⑤ 反復(fù)執(zhí)行③到④，直到算法收斂或達(dá)到遺傳終止代數(shù)，將得到適度值最優(yōu)的個(gè)體作為結(jié)果。

4 實(shí)驗(yàn)結(jié)果及分析

本文以假設(shè)的200臺(tái)某型軍事裝備的訓(xùn)練數(shù)據(jù)作為研究對(duì)象，數(shù)據(jù)結(jié)構(gòu)包含：編號(hào)(S1-S400)，機(jī)動(dòng)能力(A,100分制)、抗干擾能力(B,100分制)，打擊能力(C,20分制)、打擊精度(D,20分制)、運(yùn)載能力(E,20分制)和生存能力(F,20分制)等各項(xiàng)軍事裝備試驗(yàn)數(shù)據(jù)(見表1)。設(shè)定初始K值為3，終止迭代次數(shù)為60，Pc和Pm分別為0.7和0.1。本文設(shè)置A,B,F 3個(gè)項(xiàng)目的權(quán)重為0.25,0.25,0.2，其他3項(xiàng)分別為0.1。

姓名ABCDEFS1808120201598S2896814151796S31009717161889S46985121720100S5827420141494S687781991893S7958615181696S88891614884S9789013161592S10924513201390S11917810121783S12847719191277…………………

經(jīng)計(jì)算后，得到分組結(jié)果如表2所示。分組數(shù)目由最初的3變?yōu)?，實(shí)現(xiàn)了自動(dòng)學(xué)習(xí)，說明遺傳算法在K均值聚類分組中發(fā)揮了作用。第1、2、3、4、5組軍事裝備的數(shù)量分別為48，24，70，28和30，為指揮員按照組別制定維修保養(yǎng)計(jì)劃打下了基礎(chǔ)。

表2 分組結(jié)果

5 結(jié)論

本文給出了軍事裝備試驗(yàn)數(shù)據(jù)的相似性度量，采用遺傳K均值算法對(duì)軍事裝備的試驗(yàn)訓(xùn)練數(shù)據(jù)進(jìn)行了聚類分組，實(shí)驗(yàn)結(jié)果證明該方法實(shí)現(xiàn)了分組數(shù)目的自動(dòng)學(xué)習(xí)，為指揮員按照組別指定維修保養(yǎng)計(jì)劃打下了基礎(chǔ)。

聚類分組仍有一部分內(nèi)容需要進(jìn)一步討論和研究，如：聚類分組的有效性評(píng)價(jià)，依據(jù)分組結(jié)果制定科學(xué)合理的維修保養(yǎng)計(jì)劃等。

參考文獻(xiàn)：

[1] 廖興禾，白洪波，丁建琪.基于系統(tǒng)工程的裝備試驗(yàn)與評(píng)價(jià)需求研究[J].裝備學(xué)院學(xué)報(bào)，2017，28(1)：118-123.

[2] 王志航.RFID技術(shù)在軍事裝備維修保養(yǎng)中的應(yīng)用[D].濟(jì)南:山東大學(xué)，2008.

[3] 李健平.決策樹技術(shù)在軍事訓(xùn)練成績中的分析研究[D].昆明:昆明理工大學(xué)，2010.

[4] 鄧敏，劉啟亮，李光強(qiáng)，等.空間聚類分析及應(yīng)用[M].北京：科學(xué)出版社，2011.

[5] 呂可,鄭威,趙嚴(yán)冰.雷達(dá)對(duì)抗偵察裝備作戰(zhàn)能力的ANP冪指數(shù)評(píng)估方法[J].火力與指揮控制,2016(12)：59-63.

[6] 賴玉霞，劉建平，楊國興.基于遺傳算法的K均值聚類分析[J].計(jì)算機(jī)工程，2008，34(20)：200-202.

[7] 王玉斌.數(shù)據(jù)挖掘技術(shù)在輔助決策中的應(yīng)用研究[D].重慶:重慶大學(xué)，2008.