基于遺傳算法的航空兵出動(dòng)架次計(jì)算方法

張迎新，徐元子，殷 軍，吉 寧，郭 棟

（1.解放軍31002 部隊(duì)，北京 100094；2.空軍指揮學(xué)院，北京 100097）

0 引言

制空權(quán)是現(xiàn)代戰(zhàn)爭(zhēng)戰(zhàn)場(chǎng)控制權(quán)的關(guān)鍵，航空兵戰(zhàn)時(shí)出動(dòng)能力是評(píng)估奪取制空權(quán)能力的重要方面。航空兵出動(dòng)架次計(jì)算，以給定兵力在一定時(shí)間內(nèi)對(duì)目標(biāo)任務(wù)的出動(dòng)架次為評(píng)估指標(biāo)，計(jì)算給定約束條件下的最大出動(dòng)架次，具有重要的理論價(jià)值和現(xiàn)實(shí)意義。影響給定兵力出動(dòng)架次的因素主要包括機(jī)場(chǎng)保障和目標(biāo)任務(wù)的位置距離。

近年來，國(guó)內(nèi)外關(guān)于航空兵出動(dòng)架次的研究主要集中于機(jī)場(chǎng)保障要素對(duì)出動(dòng)架次的影響。文獻(xiàn)［1］針對(duì)航母作戰(zhàn)部署進(jìn)程中因艦載機(jī)發(fā)射回收而產(chǎn)生的航行偏差問題，構(gòu)建了艦載機(jī)出動(dòng)架次規(guī)劃模型。文獻(xiàn)［2］針對(duì)航母艦載機(jī)的出動(dòng)回收調(diào)度策略問題，建立了基于馬爾科夫決策過程的仿真模型，提出了基于學(xué)徒學(xué)習(xí)理論的調(diào)度方法。文獻(xiàn)［3］針對(duì)航母作戰(zhàn)部署進(jìn)程中的艦載機(jī)出動(dòng)規(guī)劃問題，建立了基于多目標(biāo)規(guī)劃的問題模型。文獻(xiàn)［4］針對(duì)航母艦載機(jī)出動(dòng)能力評(píng)估指標(biāo)體系量化問題，提出了主成分約簡(jiǎn)方法與突變級(jí)數(shù)方法相結(jié)合的指標(biāo)量化方法。文獻(xiàn)［5］針對(duì)維修保障模式對(duì)飛機(jī)出動(dòng)架次率的影響，構(gòu)建了基于蒙特卡洛和排隊(duì)論方法仿真模型。文獻(xiàn)［6］針對(duì)戰(zhàn)時(shí)飛機(jī)出動(dòng)保障設(shè)備優(yōu)化配置問題，建立了蒙特卡洛排隊(duì)過程模型，分析了保障設(shè)備配備比對(duì)出動(dòng)架次的影響。

以上文獻(xiàn)在計(jì)算飛機(jī)出動(dòng)架次時(shí)，并沒有考慮目標(biāo)任務(wù)的位置距離因素的影響。然而，受飛機(jī)續(xù)航能力限制，任何飛機(jī)執(zhí)行戰(zhàn)斗任務(wù)的航程距離都是非常有限的，在飛機(jī)部署位置給定的條件下，任務(wù)距離是影響出動(dòng)架次的重要因素［7］。為此，本文提出了一種面向目標(biāo)任務(wù)的航空兵出動(dòng)架次評(píng)估方法，計(jì)算部署在指定地點(diǎn)的一定數(shù)量的飛機(jī)在一定時(shí)間內(nèi)對(duì)給定目標(biāo)任務(wù)的最大持續(xù)出動(dòng)架次。通過對(duì)比相同兵力對(duì)不同位置目標(biāo)任務(wù)的出動(dòng)架次，可直觀比較任務(wù)距離對(duì)航空兵出動(dòng)架次的影響。

1 問題描述與建模

典型的航空兵出動(dòng)架次評(píng)估問題可以這樣描述：給定可投入兵力集合F 和目標(biāo)任務(wù)集合T，計(jì)算一定時(shí)間內(nèi)的最大持續(xù)出動(dòng)架次。出動(dòng)兵力給定了投入作戰(zhàn)的航空兵飛機(jī)型號(hào)、數(shù)量和部署地點(diǎn)，以及各型號(hào)飛機(jī)的戰(zhàn)斗巡航速度、作戰(zhàn)半徑等屬性；目標(biāo)任務(wù)給定了待執(zhí)行空中戰(zhàn)斗巡邏任務(wù)的位置、執(zhí)行優(yōu)先級(jí)和兵力需求等屬性。受飛機(jī)數(shù)量和機(jī)場(chǎng)最大容量限制，任何空軍基地在一定時(shí)間內(nèi)的出動(dòng)架次都是有限的；同時(shí)，受飛機(jī)續(xù)航能力限制，不考慮空中加油情況下，每架次飛機(jī)執(zhí)行任務(wù)的航程距離不能超過其作戰(zhàn)半徑，其中，飛機(jī)作戰(zhàn)半徑定義為遂行戰(zhàn)斗任務(wù)時(shí)，不經(jīng)空中加油在同一機(jī)場(chǎng)做一次往返飛行所能達(dá)到最遠(yuǎn)作戰(zhàn)點(diǎn)的距離。航空兵出動(dòng)架次評(píng)估需要在滿足所有的約束條件下，通過任務(wù)—資源優(yōu)化調(diào)度，合理安排出動(dòng)架次，計(jì)算給定兵力在一定時(shí)間內(nèi)支撐目標(biāo)任務(wù)的最大持續(xù)出動(dòng)架次。

1.1 模型參數(shù)

f∈F 為兵力集合，f 為部署在同一地點(diǎn)且飛機(jī)型號(hào)相同的兵力；t∈T 為目標(biāo)任務(wù)集合；locf=（latf，lonf）為兵力位置的緯度值和經(jīng)度值；loct=（latt，lont）為目標(biāo)任務(wù)位置的緯度值和經(jīng)度值；speedf為飛機(jī)巡航速度，單位：km/h；rangef為飛機(jī)作戰(zhàn)半徑，即遂行任務(wù)時(shí)不經(jīng)空中加油在同一機(jī)場(chǎng)往返飛行所能到達(dá)的最遠(yuǎn)作戰(zhàn)距離，單位：km；numf為飛機(jī)數(shù)量；flightt為同時(shí)執(zhí)行每個(gè)任務(wù)的飛機(jī)數(shù)量；distt，f為f 距離t 的大圓圈航線距離，也是兩點(diǎn)間最短距離；exect，f為f 分配執(zhí)行t 的每架次執(zhí)行任務(wù)時(shí)間；sortiet，f為f分配執(zhí)行t 的出動(dòng)架次。

1.2 模型描述

1.2.1 目標(biāo)函數(shù)

選擇出動(dòng)架次為效能指標(biāo)，以最大化同時(shí)執(zhí)行任務(wù)t∈T 的飛機(jī)數(shù)量flightt為目標(biāo)函數(shù)。

1.2.2 出動(dòng)架次兵力約束

受飛機(jī)數(shù)量和機(jī)場(chǎng)最大容量限制，在一定時(shí)間內(nèi)任何兵力的出動(dòng)架次都是有限的，分配給兵力f的出動(dòng)架次不能超過其最大出動(dòng)能力。

給定時(shí)間dura 內(nèi)兵力f 的最大出動(dòng)架次capf主要由飛機(jī)數(shù)量numf和平均出動(dòng)周期cyclef決定。

出動(dòng)周期包括地面準(zhǔn)備時(shí)間groundf和空中飛行時(shí)間airf。

地面準(zhǔn)備時(shí)間是考慮再次出動(dòng)，飛機(jī)從返航著陸到再次起飛的總時(shí)間，包括著陸滑行、安全檢查、裝填、加油、滑行起飛等相對(duì)固定的準(zhǔn)備活動(dòng)時(shí)間prepf，以及隨機(jī)性較大的飛機(jī)維修保障時(shí)間mainf。

美蘭德公司在評(píng)估美軍戰(zhàn)斗機(jī)出動(dòng)架次時(shí)，通過分析飛機(jī)維護(hù)保障數(shù)據(jù)，并借鑒波音公司對(duì)飛機(jī)飛行時(shí)間與維修保障時(shí)間影響關(guān)系的研究成果，提出了美軍F-15、F-16 兩型戰(zhàn)斗機(jī)大規(guī)模出動(dòng)時(shí)的地面準(zhǔn)備時(shí)間經(jīng)驗(yàn)公式，認(rèn)為大規(guī)模連續(xù)出動(dòng)時(shí)準(zhǔn)備活動(dòng)標(biāo)準(zhǔn)時(shí)間為180 min，維修保障時(shí)間等于3.4 h加上每1 個(gè)飛行小時(shí)需要的0.68 h 維護(hù)時(shí)間［6］。

由于本文研究大規(guī)模出動(dòng)架次評(píng)估問題，為簡(jiǎn)化問題研究，借鑒文獻(xiàn)［6］中方法對(duì)飛機(jī)出動(dòng)地面準(zhǔn)備時(shí)間進(jìn)行簡(jiǎn)化計(jì)算。需要注意的是，飛機(jī)出動(dòng)地面準(zhǔn)備時(shí)間是維修保障人員素質(zhì)、裝備性能和管理能力的集中體現(xiàn)，根據(jù)飛機(jī)型號(hào)和部署機(jī)場(chǎng)的不同而不同。

空中飛行時(shí)間airf是飛機(jī)遂行戰(zhàn)斗任務(wù)，從起飛到著陸的總時(shí)間，包括從機(jī)場(chǎng)往返于目標(biāo)任務(wù)區(qū)的巡航時(shí)間pathf，以及到達(dá)目標(biāo)任務(wù)t 位置的執(zhí)行任務(wù)時(shí)間exect，f。

受飛機(jī)續(xù)航能力限制，每架次作戰(zhàn)距離最大不能超過其作戰(zhàn)半徑rangef，為簡(jiǎn)化問題研究，令每架次空中飛行時(shí)間airf都等于其最大作戰(zhàn)續(xù)航時(shí)間，即往返作戰(zhàn)半徑距離作戰(zhàn)的巡航時(shí)間。

1.2.3 出動(dòng)架次任務(wù)約束

根據(jù)任務(wù)要求，給定時(shí)間dura 內(nèi)，分配執(zhí)行任務(wù)t 的總架次，必須足夠保持flightf架飛機(jī)持續(xù)執(zhí)行任務(wù)。

其中，exect，f是f 分配執(zhí)行任務(wù)t 的每架次任務(wù)t 執(zhí)行時(shí)間，sortiet，f是f 分配執(zhí)行t 的架次數(shù)，Dura 是給定任務(wù)時(shí)間，flightf是同時(shí)執(zhí)行每個(gè)任務(wù)的飛機(jī)數(shù)量。

1.2.4 出動(dòng)架次分配約束

根據(jù)大地主題解算知識(shí)，球面上兩點(diǎn)間的大圓圈航線距離是兩點(diǎn)間的最短距離。已知兩點(diǎn)的經(jīng)度和緯度坐標(biāo)locf=（latf，lonf）、loct=（latt，lont），可計(jì)算兩點(diǎn)間大圓圈航線距離distt，f，采用如下經(jīng)典計(jì)算公式：

其中，Rearth=6 378 km 為地球半徑。

受飛機(jī)續(xù)航能力限制，不考慮空中加油，如果分配f 執(zhí)行任務(wù)t，則f 與t 之間距離不能大于f 的作戰(zhàn)半徑。

其中，xt，f是決策變量，如果sortiet，f>0，則xt，f=1，否則xt，f=0。

2 求解算法

遺傳算法借鑒基因理論，模擬生物種群的“適者生存”進(jìn)化機(jī)制，是一種適用于快速求解復(fù)雜問題的啟發(fā)式方法。引入遺傳算法對(duì)航空兵出動(dòng)架次評(píng)估模型進(jìn)行求解，算法主要包括3 部分：1）問題編碼，將問題解編碼為染色體是遺傳算法設(shè)計(jì)的基礎(chǔ)，結(jié)合問題特點(diǎn)，提出了一種擴(kuò)展的任務(wù)列表編碼方法；2）計(jì)算初始解集，是算法優(yōu)化的起點(diǎn)，設(shè)計(jì)了一種基于優(yōu)先序的初始解生成算法；3）遺傳算子，通過交叉、變異和選擇算子對(duì)解集進(jìn)行迭代優(yōu)化，根據(jù)問題特點(diǎn)和編碼方式分別采用優(yōu)先序交叉法、兩點(diǎn)變異法和概率選擇法進(jìn)行遺傳操作。

2.1 問題編碼

航空兵出動(dòng)架次評(píng)估就是在給定約束條件下，通過優(yōu)化調(diào)度有限的出動(dòng)架次，計(jì)算滿足任務(wù)要求的航空兵最大出動(dòng)架次。求解過程需要確定任務(wù)調(diào)度優(yōu)先序和資源分配優(yōu)先序，任務(wù)列表編碼方法將問題解編碼為一個(gè)任務(wù)列表，由于其內(nèi)嵌了任務(wù)之間的時(shí)序關(guān)系，是求解任務(wù)調(diào)度問題時(shí)廣泛使用的一種問題編碼方法。針對(duì)問題特點(diǎn)，對(duì)任務(wù)列表編碼進(jìn)行擴(kuò)展，設(shè)計(jì)了一種雙列表染色體編碼方法，采用兩個(gè)列表分別描述t∈T 的任務(wù)調(diào)度優(yōu)先序和兵力f∈F 的資源分配優(yōu)先序。染色體采用實(shí)數(shù)編碼，一個(gè)完整的染色體編碼方案可表示為：

2.2 初始解集

采用串行調(diào)度機(jī)制，對(duì)任務(wù)優(yōu)先權(quán)進(jìn)行隨機(jī)賦值，生成初始解集的染色體編碼。對(duì)于每一個(gè)染色體編碼，根據(jù)任務(wù)優(yōu)先權(quán)依次分配出動(dòng)架次，直至生成一個(gè)完整的航空兵出動(dòng)計(jì)劃。對(duì)于任務(wù)t∈T 的兵力分配，依據(jù)每架次的執(zhí)行任務(wù)時(shí)間exect，f，由大到小依次選擇。算法流程如下：

Step1：初始化每個(gè)任務(wù)的巡邏飛機(jī)數(shù)量flightt=1。

Step 2：對(duì)任務(wù)優(yōu)先權(quán)進(jìn)行隨機(jī)賦值，依據(jù)每架次執(zhí)行任務(wù)時(shí)間exect，f由大到小對(duì)資源優(yōu)先權(quán)進(jìn)行賦值，生成初始解集的染色體編碼。

Step 3：采用串行調(diào)度機(jī)制，對(duì)染色體進(jìn)行解碼，生成出動(dòng)架次計(jì)劃。根據(jù)任務(wù)優(yōu)先權(quán)依次調(diào)度任務(wù)，根據(jù)資源優(yōu)先權(quán)依次安排出動(dòng)兵力，直至生成完整的航空兵出動(dòng)計(jì)劃。

Step 4：判斷終止條件。如果給定兵力滿足所有目標(biāo)任務(wù)，則flightt=flightt+1，轉(zhuǎn)Step 3繼續(xù)迭代，否則轉(zhuǎn)Step 5；

Step 5：輸出最大出動(dòng)架次flightt=flightt-1。

2.3 遺傳算子

遺傳算法通過對(duì)初始解集的交叉、變異和選擇操作，對(duì)解集進(jìn)行優(yōu)化迭代。

根據(jù)問題編碼特點(diǎn)，采用優(yōu)先權(quán)交叉方法進(jìn)行交叉操作，主要步驟是：1）選擇一定數(shù)量的優(yōu)先基因；2）確定優(yōu)先基因在父代染色體中的任務(wù)優(yōu)先序；3）保持選定優(yōu)先基因在原父代染色體中任務(wù)優(yōu)先序的前提下，按照另一父代染色體的優(yōu)先序生成子代染色體。一個(gè)完整的交叉操作示例如圖1 所示：首先確定優(yōu)先基因{2，3，6}，保持任務(wù)優(yōu)先權(quán)在父代染色體中的相對(duì)次序{6，3，2}、{3，2，6}不變，按照另一染色體的任務(wù)優(yōu)先權(quán)進(jìn)行排序，生成兩個(gè)新的子代染色體。需要注意的是，交叉操作只改變?nèi)蝿?wù)優(yōu)先權(quán)，不改變資源優(yōu)先權(quán)。

表2 投入戰(zhàn)斗兵力

圖1 遺傳交叉操作示例

采用兩點(diǎn)變異方法進(jìn)行變異操作。變異操作只改變?nèi)蝿?wù)優(yōu)先序，不改變資源優(yōu)先序，主要步驟是：選擇兩個(gè)突變基因，交換突變基因的任務(wù)優(yōu)先序，生成新的染色體。一個(gè)完整的變異操作示例如圖2所示：

圖2 遺傳變異操作示例

采用概率選擇法進(jìn)行選擇操作。根據(jù)目標(biāo)函數(shù)定義，將同時(shí)執(zhí)行任務(wù)t∈T 的飛機(jī)數(shù)量作為解的適應(yīng)度值，采用概率法選擇下一代進(jìn)化的解集。為防止進(jìn)化過程中最優(yōu)解丟失，采用精英保留策略，每次迭代產(chǎn)生的最優(yōu)解，直接進(jìn)入下一代迭代。

3 仿真實(shí)例

3.1 實(shí)驗(yàn)想定

表1 目標(biāo)任務(wù)

表3 飛機(jī)性能數(shù)據(jù)

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

為便于比較驗(yàn)證，飛機(jī)出動(dòng)周期時(shí)間采用文獻(xiàn)［7］中數(shù)據(jù)，假設(shè)F-15、F-16 飛機(jī)的出動(dòng)準(zhǔn)備地面活動(dòng)時(shí)間為3 h，維修保障時(shí)間為3.4 h 平均維護(hù)加每1 個(gè)飛行小時(shí)產(chǎn)生的0.68 h 額外維護(hù)時(shí)間。根據(jù)飛機(jī)性能和目標(biāo)任務(wù)距離，可計(jì)算給定兵力對(duì)目標(biāo)任務(wù)的每架次戰(zhàn)斗活動(dòng)時(shí)間（單位：h），如表4 所示。根據(jù)飛機(jī)出動(dòng)周期可計(jì)算，24 h 內(nèi)給定兵力對(duì)每個(gè)目標(biāo)任務(wù)的最大出動(dòng)架次，如表4 中最后一行所示。

表5 航空兵最優(yōu)出動(dòng)計(jì)劃

4 結(jié)論

本文提出了一種面向目標(biāo)任務(wù)的航空兵出動(dòng)架次計(jì)算方法。首先，分析問題特點(diǎn)，基于資源受限項(xiàng)目調(diào)度理論，建立了航空兵出動(dòng)架次計(jì)算數(shù)學(xué)模型。然后，設(shè)計(jì)了一種航空兵出動(dòng)架次評(píng)估遺傳算法，算法構(gòu)建了一種擴(kuò)展任務(wù)列表染色體編碼方法對(duì)問題進(jìn)行遺傳編碼，提出了一種基于優(yōu)先規(guī)則出動(dòng)架次分配算法進(jìn)行初始解計(jì)算。最后，構(gòu)建了航空兵出動(dòng)架次計(jì)算仿真算例，對(duì)本文提出的模型和算法進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，所提模型和算法能夠有效求解航空兵大規(guī)模出動(dòng)架次計(jì)算問題。研究中很多因素進(jìn)行了簡(jiǎn)化處理，后續(xù)將分析空中加油、交戰(zhàn)損失對(duì)出動(dòng)架次的影響，進(jìn)一步拓展模型。