基于啟發式遺傳算法的近距空中支援超網絡結構優化

張 澤，王 瑛，閆孟達，岳龍飛，胡東愿

(空軍工程大學空管領航學院， 西安 710051)

1 引言

近距空中支援(close air support,CAS)是一種典型的聯合作戰行動，指航空兵在與己方部隊距離較近、可以直接影響己方部隊行動的情況下對目標實施空中突擊，以支援陸上和海上作戰部隊。近距空中支援包括預先計劃的近距空中支援和即時性近距空中支援，預先計劃的近距空中支援(preplanned close air support,PCAS)指陸軍和空軍根據預先制定的作戰計劃和攻擊目標申請火力打擊，PCAS計劃的有效制定有利于把握戰場的主動權，因此本文主要對PCAS網絡進行優化。優化網絡結構對于預警探測、打擊引導等作戰行動具有重要影響，對網絡效率和網絡效能的高低起到決定作用。

目前，國內外關于作戰信息網絡結構優化的研究，主要集中在理論分析、模型構建和算法改進等方面。文獻[3]把作戰網絡信息流運用到遺傳算法中，建立信息流算法與模型，對于優化作戰網絡體系效能具有重要意義；文獻[4]通過復雜網絡提出作戰體系網絡連接優化控制方法，仿真分析網絡結構對網絡效能的影響，結果驗證了網絡模型的有效性。

已有研究主要集中在對作戰網絡結構優化方面，但仍存在以下不足：沒有根據實際作戰特點建立網絡模型，僅停留在理想作戰層面；僅考慮單個優化目標，沒有針對不同層級和整體網絡進行優化。本文有兩點創新，一是構建CAS超網絡基本模型，將基本模型中的鄰接矩陣作為啟發式信息，對其初始化生成遺傳算法的初始種群；第二根據關鍵節點設置變異概率，提高種群尋優精度和速度。

本文依據超網絡理論，以提高網絡抗毀性、網絡流轉效率和全網效能為優化目標，使用遺傳算法進行求解，構建CAS信息流轉超網絡優化模型，對優化后的網絡進行仿真分析。

2 CAS超網絡

美國科學家Sheffi首次提出超網絡(Super-network)的概念，通常指規模巨大、連接復雜、節點具有異質性的網絡，或網絡中嵌套網絡，且存在虛擬節點的邊和流等的大型網絡。超網絡的特征為多層、多級、多維、多流量、多屬性等，用于描述“高于而又超于現存網絡”的網絡。

CAS超網絡是指在CAS作戰中，作戰信息在作戰節點之間交互流通的過程，CAS超網絡由五層網絡組成，包括申請網、情報網、指控網、協調網和火力網，CAS超網絡鄰接矩陣可記為。

CAS超網絡結構是集申請網()、情報網()、指控網()、協調網()和火力網()為一體的作戰網絡()。作戰網絡由作戰節點()和作戰信息()構成，記為=(,)，作戰節點分為申請節點()、情報節點()、指控節點()、協調節點()和火力節點()，有=∪∪∪∪。以現代近距空中支援作戰為背景，根據節點類型，對CAS作戰力量進行分類，作戰力量具體情況如表1所示；作戰信息分為申請信息()、情報信息()、指控信息()、協調信息()和火力信息()，有=∪∪∪∪。五層網絡通過一定的映射規則相互聯系，相互作用，得到CAS超網絡基本模型如圖1所示。

表1 作戰力量具體情況Table 1 Specific situation of operational power

續表(表1)

圖1 CAS超網絡基本模型示意圖Fig.1 CAS super-network basic model

3 CAS超網絡結構優化模型

CAS超網絡結構優化是在初始網絡模型的基礎上，根據CAS作戰目的，以提高CAS作戰的靈活性和穩定性為目標，選取優化目標，建立多目標優化函數，通過遺傳算法進行尋優，得出最優矩陣。由于現代戰場具有極端的動態性，要求CAS作戰靈活，能夠迅速變更打擊目標、戰術和調整使用合適的武器彈藥，CAS必須響應迅捷，因此以提高網絡的抗毀性和網絡效率為優化目標。

3.1 抗毀性

網絡的抗毀性是指當遭受破壞時，網絡維持或恢復其性能到一個可接受程度的能力。這種破壞可以是確定性故障，也可以是隨機性故障。抗毀性可用來衡量網絡的可靠性。

1) 等效最短路徑數

衡量網絡的抗毀性，通常選取連通性作為測量指標。全連通網絡是抗毀性最強的網絡，網絡結構十分穩固。比較與全連通網絡的結構差異，差異越小說明網絡結構越緊湊，抗毀性越強。節點間的等效最短路徑數可以計算與全連通網絡的結構差異，等效最短路徑數可以表示為

(1)

其中，表示網絡中節點與之間最短路徑的長度，指節點與之間長度為的最短路徑條數，()為與具有相同節點數||的全連通網絡′中，節點與之間長度不大于的路徑條數。當與兩節點之間有直接連邊時，=1，否則=0，對于全部節點對(,)，如果=1，那么該網絡是全連通網絡。

根據等效最短路徑數，可以將抗毀性表示為

(2)

當(′)=1時，表示全連通網絡′中任意2個節點之間等效最短路徑數為1，抗毀性最強；非全連通網絡的抗毀性(′)∈(0,1)，(′)越大，抗毀性越強。

以抗毀性最強作為網絡的優化目標，有

(3)

2) 約束條件

網絡連邊的增加可以為信息流轉提供更多路徑，避免節點遭損毀后信息傳輸中斷，但連邊過多會導致信息擁堵，降低信息傳輸效率，因此應該對網絡連邊總數進行限制。網絡各節點在網絡層級、系統功能等因素影響下，具有一定的連接容量值和節點飽和度。

節點飽和度()是節點連接容量值和連接度值()的分段函數。在時刻，節點的飽和度函數為

()=-()

(4)

其中，()∈[0,]。當()=0時，()=，說明節點處于飽和狀態，不會與其他節點相連；當()>0時，()<，說明節點可以增加連邊。

因此，節點的飽和度約束可以表示為

()>0

(5)

網絡總連邊飽和度約束為

||≤80

(6)

3.2 網絡效率

網絡效率表示信息在網絡上傳輸的有效程度，通常用平均最短路徑作為優化目標。

1) 平均最短路徑

平均最短路徑指任意2個節點之間最短路徑的平均值，用來衡量網絡中信息的流轉效率。平均最短路徑越長，節點之間交流所需成本越高，效率越低；反之，成本越低，效率越高。可表示為

(7)

其中，||表示網絡中節點總數，, 指節點與之間的最短路徑數。

以平均最短路徑最短作為優化目標，有

(8)

CAS作戰中，作戰單元之間相互聯系，作戰信息在作戰單元之間流轉交互，在申請網、情報網、指控網、協調網和火力網之間建立交互關系，CAS超網絡結構的改變會影響平均最短路徑的長度。

2) 約束條件

平均最短路徑取決于CAS超網絡結構中對網絡效率影響重大的網絡。其中，情報網、指控網和火力網是負責情報傳輸、指揮控制和火力打擊功能，是決定網絡效率高低的關鍵，有

∈{,,}

其中，表示矩陣中的元素。

4 啟發式遺傳算法求解CAS優化問題

4.1 遺傳算法簡介

遺傳算法是根據自然界中生物進化規律提出的，是一種通過模擬自然進化過程搜索最優解的方法。該算法利用計算機仿真運算，將問題的求解轉換成染色體基因的交叉、變異等過程。傳統遺傳算法存在一些缺陷，本文在遺傳算法的基礎上，根據網絡的鄰接矩陣和關鍵節點設計改進遺傳算法求解CAS優化問題。

4.2 CAS超網絡的啟發式遺傳算法設計

1) 啟發式信息初始化生成初始種群

根據CAS超網絡，構建鄰接矩陣。若兩節點之間有連邊，用1表示；若兩節點之間沒有連邊，用0表示。這樣生成網絡的鄰接矩陣為，將作為啟發式信息，對每一位以5的概率隨機進行取反操作，生成至共99個初始網絡，最終得到初始種群包含個體至。

2) 適應度函數

適應度是用來度量種群中個體優劣的指標，適應度函數的設定決定算法的收斂程度和目標函數最優解。本文適應度函數由抗毀性和網絡效率兩部分組成，將網絡效率目標函數轉換為求最大值問題，可以得到適應度函數：

(9)

其中為常數，為保證適應度函數為正，取=4，越大，說明個體越好。

3) 選擇機制

選擇是從當前種群中選擇優秀的個體，作為父代參與下一代繁衍，從而迭代出最優秀的個體。一般遺傳算法采用輪盤法居多，但會導致高適應度個體過多，導致過早收斂。

為克服過早收斂問題，本文采用精英選擇法和比例選擇法選擇進入下一代中的個體，首先使用精英選擇法選擇適應度排名前30的個體不經選擇直接進入下一代，其余個體使用比例選擇法選擇30%的個體進入下一代。將2種方法結合可提高種群優化的開拓能力，避免過早收斂。

4) 關鍵節點變異機制

變異是指在群體中隨機選擇一部分個體，改變其基因型。為提高算法的尋優精度，給關鍵節點和其余節點設置不同的變異概率。由多屬性決策的節點重要性綜合評價方法得出CAS超網絡中節點的重要程度，其中，重要性排名前6的節點分別為地面情報中心()、控制中心()、空中聯絡官()、作戰參謀官()和援機中的2個長機(()、())。本文給關鍵節點設置2的變異概率，其余節點設置1的變異概率，以增大對關鍵節點連邊的探索。

4.3 遺傳算法求解CAS問題步驟

首先生成初始種群，在CAS超網絡鄰接矩陣的基礎上，進行種群初始化；然后評估個體適應度，將適應度按從大到小排序，根據精英選擇法和比例選擇法選擇個體；對選擇出的個體進行交叉變異操作，變異完成后，計算新一代種群的適應度，比較個體適應度大小，依次迭代，當連續5代內最優值不變或迭代500次時算法終止，迭代結束。本文遺傳算法流程如圖2所示。

圖2 遺傳算法流程框圖Fig.2 Genetic algorithm flow chart

5 仿真實驗

5.1 仿真設置

由CAS超網絡模型，設置參數||=28，邊長度設為1，連邊總數||不大于80，網絡節點的連接度容量如表2所示。抽象CAS超網絡的層級網絡拓撲結構，如圖3所示。

表2 CAS超網絡節點連接度容量Table 2 CAS超網絡 node connectivity capacity

圖3 CAS超網絡拓撲結構示意圖Fig.3 CAS super-network topology structure

5.2 優化結果

根據設置的參數值，采用遺傳算法，運用Matlab軟件求解，得到優化后的鄰接矩陣，將鄰接矩陣轉化為CAS超網絡網絡拓撲結構，如圖4所示。

圖4 CAS超網絡優化拓撲結構示意圖Fig.4 CAS super-network optimized topology structure

相較于圖3，優化后的網絡拓撲結構更為復雜，網絡連邊增多，個別節點之間信息交互關系發生改變。優化前后CAS超網絡拓撲結構性能如表3所示。

表3 CAS超網絡優化前后拓撲結構性能Table 3 Comparison of topology performance before and after CAS super-network optimization

由表3可知，在CAS超網絡優化過程中，網絡連邊較優化前有了顯著增加，抗毀性增強，網絡效率提高，整體網絡的可靠性和信息交互的靈活性有很大提高。

5.3 實驗結果分析

為了評價啟發式遺傳算法的有效性，采用Matlab軟件仿真得到適應度值作為測試結果。

圖5將平均適應度與最大適應度收斂情況進行對比，結果顯示當適應度值為2.8左右時，適應度趨于收斂。

圖5 遺傳算法適應度函數值曲線Fig.5 Genetic algorithm fitness function value

圖6將啟發式遺傳算法和隨機種群遺傳算法的平均適應度函數進行對比。圖6中，隨機種群生成大部分無效種群，不滿足約束條件，其平均適應度函數值收斂性較差，尋優精度低，啟發式遺傳算法收斂速度快，尋優精度更高。

圖6 遺傳算法平均適應度函數值曲線Fig.6 Average fitness function value of genetic algorithm

對優化前后的CAS超網絡拓撲結構特性進行對比分析，進一步驗證優化后CAS超網絡的有效性，選取節點的超度分布、介數、聚類系數3個拓撲指標仿真分析網絡的特性。

1) 超度分布

節點的超度可以表示為與該節點直接相連的其他所有節點的總數，記為，節點的度為的概率可用超度分布()來表示，描述了整個網絡中所有節點度的分布情況，可以有效反映戰場中信息流轉動態變化的過程，表示為

(10)

其中：為超度值為的節點個數，表示超網絡中節點的總數。在CAS作戰中，超度值較高的節點處于各自子網的核心，作戰信息在此處交互流通，信息關系復雜性高。計算超度有利于識別出CAS中重要的作戰單元，對保護關鍵作戰單元和優化戰術具有重要意義。

優化前后CAS超網絡拓撲結構的超度分布如圖7所示。

圖7 優化前后CAS超網絡拓撲結構的超度分布曲線Fig.7 The super distribution curve of CAS super-network topology structure before and after optimization

由圖7可知，優化前后節點分布趨勢大致相似，均由大變小，當度值分別為3和5時，節點超度分布達到最大，表明CAS超網絡拓撲結構整體呈現不均勻分布。優化后的網絡節點度值數量明顯增多，說明信息交互更加豐富，網絡拓撲結構復雜度提高。

2) 介數

節點的介數是指經過該節點的最短路徑的數量占整個網絡中所有最短路徑的數量的比例，超邊的介數反映了經過該邊的所有最短路徑的比例。介數體現了節點和邊在整個網絡交互傳輸中的重要程度，反映了節點在信息流動中的作用，表示為

(11)

優化前后CAS超網絡拓撲結構的介數分布如圖8所示。由Matlab計算可知，優化前后節點的介數平均值分別為97.929和31.929，表明優化后節點對信息流動的影響力較優化前小。由圖8可知，優化后的介數分布較優化前更加集中，優化前介數波動幅度較大，優化后介數分布較平穩。這說明優化后網絡中經過每個節點的個數占最短路徑的比例減小，節點對戰場信息流轉的影響基本一致。

圖8 優化前后CAS超網絡拓撲結構的超度分布曲線Fig.8 The betweenness curve of CAS super-network topology structure before and after optimization

3) 聚類系數

聚類系數是指節點所有鄰居節點之間的實際連邊條數與理論連邊總條數的比例，集聚系數可以描述網絡中節點的集聚情況，反映網絡的緊密程度，表示為

(12)

式(12)中：表示超三角形的數目，表示長度為2的路徑數目。1個超三角形指的是由3個不同的頂點和3個不同的超邊構成的序列，3個頂點是相鄰的，2路指的是步長為2的路，在路中頂點和超邊是相異的。對CAS作戰而言，聚類系數高說明作戰節點之間連接緊密，內部作戰信息關系復雜性高于其他節點，作戰中雙方對抗激烈、作戰節奏快，整個CAS作戰體系連接緊密度高。

優化前后CAS超網絡拓撲結構的聚類系數分布如圖9所示。

優化前后，網絡平均聚類系數分別為0.086和0.192，優化后網絡聚類系數更高，說明優化后網絡的節點分布較為集中，網絡更為緊密。由圖9可知，優化后網絡的聚類系數值都集中在0～0.4，較優化前分布均勻。這說明優化后的網絡不僅信息連邊大幅增加，節點之間信息交互更加頻繁、聯系更加緊密。

圖9 優化前后CAS超網絡拓撲結構的超度分布曲線Fig.9 The clustering curve of CAS super-network topology structure before and after optimization

6 結論

基于超網絡理論，構建CAS超網絡結構，提高了CAS作戰網絡的穩定性和靈活性，選擇抗毀性和網絡效率作為優化目標，通過啟發式遺傳算法求解運算，建立優化后的CAS超網絡拓撲結構，仿真分析優化前后網絡的超度分布、介數和聚類系數，結果表明優化后的網絡具有更高的抗毀性和更快的網絡效率。下一步將考慮節點和信息連邊的多樣性，研究節點和連邊類型發生變化對CAS超網絡的抗毀性和網絡效率產生的影響。