一種基于遺傳算法的NIC-SoS發(fā)展路線圖優(yōu)選方法

禹明剛 牟楊城 康凱

網(wǎng)絡(luò)信息體系(Networking Information-Centric System of Systems,NIC-SoS)[1-3]是近年來我軍在網(wǎng)絡(luò)化和體系化作戰(zhàn)背景下提出的新概念,這一體系是一個由跨接多個“域”(Field) 的軍事信息裝備,以及由多種信息裝備鉸鏈而成的網(wǎng)絡(luò)共同構(gòu)成的復(fù)雜巨系統(tǒng),其實體關(guān)系概念圖如圖1所示.

不同種類、規(guī)模的信息裝備,及裝備間的組網(wǎng)關(guān)系形成不同的網(wǎng)絡(luò)信息體系方案,具備不同的作戰(zhàn)能力.隨時間推進(jìn),各體系方案由于自身結(jié)構(gòu)調(diào)整(裝備增減、更替、連接關(guān)系重構(gòu)等) 引發(fā)能力的演化(提升、削弱、消退等).前期,我們對網(wǎng)絡(luò)信息體系的演化機(jī)理及規(guī)律進(jìn)行了初步探索,相關(guān)成果見文獻(xiàn)[4-7].如何尋找一種科學(xué)方法來評估體系方案在演化各時間剖面上的能力,且綜合各階段評估結(jié)果選擇最優(yōu)體系發(fā)展路線圖,具有重要科學(xué)意義和應(yīng)用價值.

1 NIC-SoS 發(fā)展路線圖優(yōu)選問題建模

設(shè)網(wǎng)絡(luò)信息體系發(fā)展過程分L(L∈Z) 個階段,每個階段存在wl(wl∈Z,l∈Z,l∈[1,L])個可行方案,第l階段的方案表示為Swll,則網(wǎng)絡(luò)信息體系發(fā)展路線圖如圖2所示.

由圖2可知,網(wǎng)絡(luò)信息體系發(fā)展路線圖的優(yōu)選問題是一個復(fù)雜的多階段、多屬性決策問題,本質(zhì)上是從眾多可行的體系發(fā)展路線中,搜索最優(yōu)體系發(fā)展路線的問題.

前期,我們曾經(jīng)從能力視角對某時間階段內(nèi)體系方案的效用值進(jìn)行瞬態(tài)評估[8],進(jìn)而可以得出該時間段最優(yōu)的體系方案.然而,相鄰階段的體系方案演化過程需要承擔(dān)必要的演化代價(時間、費用、風(fēng)險等),每個時間階段的“局部最優(yōu)”體系方案構(gòu)成的發(fā)展路線不必然是“整體最優(yōu)”[9-11].因此,需要設(shè)計一種路線圖優(yōu)選方法,綜合評估體系發(fā)展各階段效用值,并基于評估結(jié)果,在眾多體系發(fā)展路線圖中尋找最優(yōu)解.

網(wǎng)絡(luò)信息體系發(fā)展路線圖優(yōu)選問題數(shù)學(xué)模型的優(yōu)化目標(biāo),是極大化網(wǎng)絡(luò)信息體系發(fā)展路線圖的綜合效用值.我們擬從3 個方面考察網(wǎng)絡(luò)信息體系發(fā)展路線圖的綜合效用(Utility): 周期內(nèi)各階段能力需求滿足度均值E(C)、周期內(nèi)能力需求滿足度震蕩程度σ2(C)、周期內(nèi)方案演化總代價Cost_all.

圖1 網(wǎng)絡(luò)信息體系實體關(guān)系概念圖

圖2 網(wǎng)絡(luò)信息體系發(fā)展路線圖示意圖

設(shè)網(wǎng)絡(luò)信息體系發(fā)展路線圖為體系方案的序列:

其中,Swtll(wtl∈[1,wl],l∈[1,L])表示體系發(fā)展路線圖在第l階段所有可行的wl個體系方案中選擇了第wt-l個.

網(wǎng)絡(luò)信息體系是一種“以能力為牽引”的建設(shè)思路,建設(shè)目的是保證體系能夠滿足遂行特定使命任務(wù)的能力需求[12-14].因此,定義體系方案在演化各階段的瞬態(tài)能力滿足度為S(Swtll),則整個演化周期內(nèi)體系能力滿足度均值為:

網(wǎng)絡(luò)信息體系發(fā)展路線圖的效用評價是一個動態(tài)過程,既需要考慮路線圖在整個演化周期內(nèi)的平均能力滿足度,又要考慮滿足度的穩(wěn)定性.一條穩(wěn)定性較差的體系發(fā)展路線圖意味著體系能力建設(shè)的不均衡不穩(wěn)定,能力建設(shè)的隨意性較大.用方差表征路線圖在周期內(nèi)能力需求滿足度震蕩程度:

設(shè)相鄰階段體系方案能力演化代價為Cost(Swtll→Swtl+1l+1),則整個路線圖中體系方案能力演化總代價為:

其中,cl,l+1為Cost(Swtll→Swtl+1l+1)的權(quán)重,表明評價過程中對不同演化時刻的重視程度.

設(shè)上述3 類指標(biāo)權(quán)重為αi(i= 1,2,3),且將能力滿足度方差σ2(C)、能力演化總代價Cost_all兩類成本型指標(biāo)歸一化為效益型指標(biāo)σ2(C)?、Cost_all?.

綜上所述,網(wǎng)絡(luò)信息體系發(fā)展路線圖最優(yōu)選擇問題,以體系方案發(fā)展路線Rmap為決策變量,其數(shù)學(xué)模型為:

2 基于遺傳算法的最優(yōu)發(fā)展路線圖搜索

智能搜索算法為自然啟發(fā)式搜索方法,不需要描述優(yōu)化問題的整個解空間,利用種群對解空間進(jìn)行抽樣篩選,并通過各種算子操作使種群在迭代過程中逐漸聚集到產(chǎn)生高質(zhì)量解的區(qū)域.本文采用遺傳算法(Genetic Algorithm,GA) 來搜索網(wǎng)絡(luò)信息體系發(fā)展的最優(yōu)路線圖.

2.1 染色體編碼及適應(yīng)度函數(shù)

一條網(wǎng)絡(luò)信息體系發(fā)展路線即為一個長度為L的體系方案序列組合.本研究采用整數(shù)型編碼方式對發(fā)展路線進(jìn)行染色體編碼: 一條染色體就是一條體系發(fā)展路線,它由L個整數(shù)構(gòu)成有序序列:

其中→[1,wl],l→[1,L].序列中的wtl表示體系發(fā)展路線在第l階段所有可行的wl個體系方案中選擇了第個.

根據(jù)式(4),一條染色體性能優(yōu)劣的評判標(biāo)準(zhǔn)是該染色體對應(yīng)的體系發(fā)展路線圖的綜合效用值.路線圖的綜合效用值越大,其對應(yīng)的染色體性能越優(yōu).因此,設(shè)置染色體的綜合效用值F為GA 的適應(yīng)度函數(shù):

2.2 遺傳算子

1)交叉算子

隨機(jī)產(chǎn)生初始種群ΔI,|ΔI| =N,計算ΔI中各染色體適配值.設(shè)置適配值較差的染色體交叉概率為Pc1,適配值較優(yōu)的染色體交叉概率為Pc2,且滿足Pc1＞Pc2.計算染色體發(fā)生交叉操作的概率Pc為:

其中,f為交叉操作中適配值較大的染色體的適配值,為ΔI的平均適配值,fmax為ΔI中最大的適配值.

采用輪盤賭選擇法進(jìn)行M(M∈[1,N]) 輪選擇,選中的染色體對參與交叉操作.設(shè)參與交叉操作的兩條染色體分別為和令x=Random[2,L],基于以下原則產(chǎn)生新的染色體和J′=

設(shè)未參與交叉的染色體共N0個,保留該N0個未參與交叉的染色體,并從交叉產(chǎn)生的新染色體中隨機(jī)選擇N-N0,產(chǎn)生交叉種群ΔC.

2)變異算子

設(shè)適配值較差的染色體變異概率為Pm1,適配值較優(yōu)的染色體變異概率為Pm2,且滿足Pm1＞Pm2.計算染色體發(fā)生變異操作的概率Pm為:

其中,f為待變異染色體的適配值,為ΔI的平均適配值,fmax為ΔI中最大的適配值.

采用輪盤賭選擇法進(jìn)行M(M∈[1,N]) 輪選擇,選中的染色體參與變異操作.對于染色體I=基于以下原則進(jìn)行變異產(chǎn)生新的染色體

設(shè)未參與變異的染色體共N0′個,保留該N0′個未變異的染色體,并與M個新變異產(chǎn)生的染色體共同產(chǎn)生變異種群ΔM.

3)選擇算子

選擇操作是依據(jù)適配值函數(shù)為每一條染色體計算適配值,從而使較優(yōu)的染色體保留下來.然而,在生物界遺傳過程中,最優(yōu)染色體并不總是被保留,因此,不能完全按適配值大小的順序進(jìn)行優(yōu)選.在具體的操作中,為每條染色體設(shè)定選擇概率,保證每條染色體存在被保留的可能性.同時,設(shè)定適配值越大的染色體保留概率越大,實現(xiàn)優(yōu)化遺傳的目的.

將ΔI、ΔC和ΔM合并為一個種群,計算合并種群中每個染色體的適應(yīng)度值fn,其中h∈[1,3N].則保留概率

使用精英保留策略和輪盤賭選擇相結(jié)合的方法進(jìn)行選擇操作,保留pn值最高的前M(M∈[1,N])條染色體,對合并種群中剩余染色體進(jìn)行N-M輪輪盤賭選擇,生成新一代種群ΔN.

2.3 算法步驟

基于GA 的網(wǎng)絡(luò)信息體系發(fā)展路線圖優(yōu)選方法流程如圖3所示.

3 建模方法比較

基于GA 的網(wǎng)絡(luò)信息體系發(fā)展路線圖優(yōu)選算法如下:

Step 1設(shè)置種群規(guī)模N,采用整數(shù)型編碼方式對染色體進(jìn)行編碼,隨機(jī)產(chǎn)生初始種群ΔI;

Step 2依據(jù)交叉概率Pc,對ΔI進(jìn)行交叉操作,產(chǎn)生交叉種群ΔC;

Step 3依據(jù)變異概率Pm,對ΔI進(jìn)行變異操作,產(chǎn)生變異種群ΔM;

Step 4將種群ΔI、ΔC和ΔM并為一個種群,進(jìn)行選擇操作,產(chǎn)生新一代種群ΔN,并替代ΔI;

Step 5重復(fù)Step2 至Step4 直至達(dá)到算法終止條件.

圖3 基于GA 的體系發(fā)展路線圖優(yōu)選流程

4 算例仿真

網(wǎng)絡(luò)信息體系4 階段動態(tài)演化路線中,第1 階段可選的體系方案分別為S11-S31,第2 階段為S12-S62,第3 階段為S13-S53,第4 階段為S14-S44.采用文獻(xiàn)[15] 提供的方法,計算各階段方案的能力需求滿足度如表1所示.

在網(wǎng)絡(luò)信息體系演化過程中,相鄰階段之間會產(chǎn)生包括經(jīng)費投入等在內(nèi)的演化代價,以前兩階段為例,給出方案間演化代價如表2所示.

表1 各階段方案的能力需求滿足度

表2 第1 階段與第2 階段間體系演化代價

根據(jù)式(4)建立的數(shù)學(xué)模型,利用GA 對4 個階段的演化路線進(jìn)行最優(yōu)化選擇.取α1= 0.30、α2=0.35、α3= 0.35,設(shè)GA 算法種群規(guī)模N= 100,交叉概率Pc1= 0.75、Pc2= 0.60,變異概率Pm1=0.80、Pm2= 0.70,輪盤選擇輪數(shù)及保留算子中M= 30,算法終止條件為適配值最大的染色體連續(xù)50 代適配值不變.

圖4 遺傳算法解的收斂情況

隨著迭代次數(shù)增加,GA 收斂情況如圖4所示,遺傳算法在第43 代收斂到最優(yōu)解,其適應(yīng)度值為0.73,即綜合效用值為0.73.其最優(yōu)解為S21→S42→S13→S34.

5 結(jié)論

本文針對網(wǎng)絡(luò)信息體系發(fā)展路線圖優(yōu)選問題,建立了網(wǎng)絡(luò)信息體系發(fā)展路線圖優(yōu)選問題模型,設(shè)計了基于遺傳算法的最優(yōu)發(fā)展路線圖搜索策略.算例仿真表明,遺傳算法能夠有效實現(xiàn)網(wǎng)絡(luò)信息體系發(fā)展路線圖的優(yōu)選.

網(wǎng)絡(luò)信息體系對我軍聯(lián)合作戰(zhàn)體系的形成和效能的發(fā)揮起著全局性、基礎(chǔ)性的支撐,如何尋找一種科學(xué)方法對網(wǎng)絡(luò)信息體系進(jìn)行方案評估、優(yōu)選及發(fā)展路線設(shè)計,具有重要科學(xué)意義和應(yīng)用價值.下一步筆者擬結(jié)合網(wǎng)絡(luò)信息體系的軍事領(lǐng)域特點,考慮體系優(yōu)選中的敵我對抗因素,引入博弈理論[16],實現(xiàn)對抗環(huán)境下的網(wǎng)絡(luò)信息體系方案評估及優(yōu)選,為我軍科學(xué)合理地進(jìn)行網(wǎng)絡(luò)信息體系頂層設(shè)計提供決策支持.