馬嘉呈，姚登凱，趙顧顥

(空軍工程大學(xué) 空管領(lǐng)航學(xué)院，西安 710051)

三維戰(zhàn)術(shù)訓(xùn)練空域規(guī)劃方法研究

馬嘉呈，姚登凱，趙顧顥

(空軍工程大學(xué) 空管領(lǐng)航學(xué)院，西安 710051)

三維戰(zhàn)術(shù)訓(xùn)練空域規(guī)劃是對空域的合理規(guī)劃利用，人工排樣已經(jīng)無法保證空域的安全有效利用,尋找高效快速的算法對于提高空域利用率和訓(xùn)練效率具有重要意義。通過對空域規(guī)劃的理論研究，結(jié)合空域特性，將整個(gè)空域劃分為立方體單元，構(gòu)建相應(yīng)的訓(xùn)練空域規(guī)劃模型；在此基礎(chǔ)之上，利用改進(jìn)的遺傳算法來尋求最優(yōu)方案，剔除了大量不可行解；通過實(shí)例仿真驗(yàn)證該空域規(guī)劃模型的合理性和有效性。結(jié)果表明：該空域模型是合理和有效的，提高了空域規(guī)劃的速度和準(zhǔn)確度。

三維戰(zhàn)術(shù)訓(xùn)練；空域安全；空域規(guī)劃；遺傳算法；排樣優(yōu)化

0 引 言

隨著我國空軍軍事訓(xùn)練轉(zhuǎn)型的推進(jìn)，軍事訓(xùn)練時(shí)間、戰(zhàn)術(shù)訓(xùn)練比重不斷提高，多兵機(jī)種合練、體系對抗已成常態(tài)，對空域等資源需求逐年增加。同時(shí)我國民用航空運(yùn)輸業(yè)進(jìn)入持續(xù)快速發(fā)展的新階段，對空域的需求也日益迫切。因此，合理安全利用航空兵戰(zhàn)術(shù)訓(xùn)練空域，既有利于充分發(fā)揮我軍主戰(zhàn)裝備的優(yōu)勢，又有利于空域結(jié)構(gòu)的合理優(yōu)化，有效緩解軍民航空域需求矛盾問題。

三維戰(zhàn)術(shù)訓(xùn)練空域規(guī)劃是對航空兵戰(zhàn)術(shù)訓(xùn)練所需空域的集中規(guī)劃，是指根據(jù)訓(xùn)練科目的不同要求，將一系列大小各異的空域塊在作戰(zhàn)責(zé)任區(qū)內(nèi)進(jìn)行排放，各個(gè)空域塊之間互不重疊，尋求能使空域利用率最大的規(guī)劃方案。從理論上看，此問題類似于三維排樣問題，是典型的NP-Hard問題[1]。目前，對于二維排樣問題，已有許多方法解決該問題，例如人工神經(jīng)網(wǎng)絡(luò)算法[2-3]、遺傳算法[4-5]、蟻群算法[6-7]等。利用啟發(fā)式排樣算法和人工智能算法的組合算法已成為解決此類問題的重點(diǎn)研究方向。但三維排樣問題由于復(fù)雜性和高難度，研究較少[8-9]。國外，一般采用物體組合的啟發(fā)式算法[10]，但其無法處理多約束問題。并且在解決大規(guī)模的規(guī)劃問題時(shí)，會(huì)導(dǎo)致爆炸組合，出現(xiàn)時(shí)間災(zāi)難問題，無法對其進(jìn)行合理的規(guī)劃。同時(shí)，由于空域自身的獨(dú)特性，其規(guī)劃問題也不同于排樣問題。規(guī)劃時(shí)需要考慮維數(shù)、形狀等因素，計(jì)算復(fù)雜度極高。目前，訓(xùn)練空域的規(guī)劃主要是依靠參謀人員的經(jīng)驗(yàn)進(jìn)行人為地規(guī)劃，從而導(dǎo)致空域的利用率較低，且無法保證空域的安全運(yùn)行。

在解決此類問題的過程中，主要存在以下困難：利用窮舉法在空域塊較多時(shí)出現(xiàn)“組合爆炸”，無法準(zhǔn)確地找出最佳方案；啟發(fā)式搜索法引入的啟發(fā)信息主要依靠人為經(jīng)驗(yàn)，故存在“組合爆炸”；神經(jīng)網(wǎng)絡(luò)在解決此問題時(shí)，雖效果明顯，但易于陷入局部最優(yōu)，當(dāng)空域塊種類較多時(shí)，無法尋找出全局最優(yōu)的解決方案。

本文將空域劃分為立方體單元，并依此構(gòu)建空域離散化模型，通過改進(jìn)的遺傳算法來不斷尋優(yōu)，找出最佳的規(guī)劃方案。

1 訓(xùn)練空域規(guī)劃的數(shù)學(xué)模型

戰(zhàn)術(shù)訓(xùn)練空域的規(guī)劃是指根據(jù)訓(xùn)練科目的不同，在某機(jī)場作戰(zhàn)責(zé)任區(qū)內(nèi)對各個(gè)訓(xùn)練科目所需空域的合理規(guī)劃，從而使得整個(gè)空域的利用率最大。本文將整個(gè)空域以及各個(gè)訓(xùn)練科目所需空域抽象為單位立方體的集合。受到區(qū)域地形、空中禁飛區(qū)、軍民航線等多方面的影響，某機(jī)場作戰(zhàn)責(zé)任區(qū)通常是不規(guī)則形狀的，故需先將作戰(zhàn)責(zé)任區(qū)進(jìn)行離散化處理。對于訓(xùn)練空域規(guī)劃問題，將其置于三維直角坐標(biāo)系中解決。其約束條件為

①空間約束：各個(gè)訓(xùn)練空域塊均需安排在機(jī)場作戰(zhàn)責(zé)任區(qū)內(nèi)，且所需的空域總體積不得大于機(jī)場總空域體積。

②位置約束：各個(gè)訓(xùn)練空域塊之間不得重疊。

③方向約束：鑒于實(shí)際情況，各訓(xùn)練空域塊放置時(shí)，需要與坐標(biāo)軸平行，但可以水平90°旋轉(zhuǎn)。

1.1 符號(hào)說明

本文采用的坐標(biāo)系為三維笛卡爾直角坐標(biāo)系，將離散化后的空域范圍置于三維坐標(biāo)系中，并使其一邊與坐標(biāo)軸的橫軸相重合；對于訓(xùn)練科目所需的空域塊，取其左后下的頂點(diǎn)作為參考點(diǎn)。本文中所需的參數(shù)和變量的具體說明如下：

①n：總的訓(xùn)練空域塊個(gè)數(shù)；

②m：最后排入的訓(xùn)練空域塊個(gè)數(shù)；

③xi,yi,zi：訓(xùn)練空域塊參考點(diǎn)的坐標(biāo)，i=1,2,…,n；

④li,wi,hi：訓(xùn)練空域塊的長度、寬度、高度(默認(rèn)長度大于寬度)，i=1,2,…,n；

⑤Vi：訓(xùn)練空域塊的體積，Vi=li×wi×hi，i=1,2,…,n；

⑥V：離散化后整個(gè)空域的體積；

⑦ai：取值為0或1的變量，若訓(xùn)練空域塊被安排在空域內(nèi)，則ai=1，否則ai=1，i=1,2,…,n；

⑧Exyz：取值為0或1的變量，表示空間點(diǎn)(x,y,z)是否被占用。若被占用則Exyz=1，否則Exyz=0；

⑩lxi,lyi,lzi：取值為0或1的變量，表示訓(xùn)練空域塊i的長是否平行于x軸，y軸或z軸的某個(gè)軸，若平行于x軸，則lxi=1，i=1,2,…,n；

1.2 目標(biāo)函數(shù)及約束條件

本文中的優(yōu)化目標(biāo)是使得整個(gè)空域的利用率最大化，即在該機(jī)場作戰(zhàn)責(zé)任區(qū)內(nèi)安排的訓(xùn)練空域塊最多，故目標(biāo)函數(shù)可表示為

(1)

在規(guī)劃過程中由于受到空間約束，各個(gè)訓(xùn)練空域必須被包含在作戰(zhàn)責(zé)任區(qū)內(nèi)，故各個(gè)空域點(diǎn)與各個(gè)訓(xùn)練空域塊的代表值之和必定小于或者等于1，且排入的空域塊體積之和必小于作戰(zhàn)責(zé)任區(qū)的范圍。具體公式如下：

(2)

(3)

式(3)表示各個(gè)空域塊不能重疊，即需要滿足位置約束：

(4)

在規(guī)劃過程中，由于各個(gè)空域塊需要與坐標(biāo)軸平行放置，故需要滿足下述的約束條件：

(5)

2 遺傳算法求解空域規(guī)劃的主要方法

遺傳算法主要通過處理參數(shù)形成的編碼集來進(jìn)行全局尋優(yōu)，并利用評(píng)估函數(shù)來找出該問題的最佳解，不需要其他的先決條件，這也給問題的實(shí)現(xiàn)帶來了極大的便利[11-12]。針對訓(xùn)練空域規(guī)劃的特點(diǎn)，本文將空域進(jìn)行離散化處理，編寫相應(yīng)的編碼和解碼方式，并通過懲罰技術(shù)來解決約束問題。

2.1 訓(xùn)練空域的預(yù)處理

軍用機(jī)場的作戰(zhàn)責(zé)任區(qū)，由于地形對航路航線的影響，通常是不規(guī)則的。為了更加合理地利用空域，本文首先對空域邊界進(jìn)行離散化處理。具體步驟如下：

步驟1 將整個(gè)訓(xùn)練空域以圖像的形式存儲(chǔ)在內(nèi)存當(dāng)中；

步驟2 將圖像轉(zhuǎn)化為位圖(0/1形式)進(jìn)行存儲(chǔ)；

步驟3 人為劃分區(qū)間，并取置信度為0.75，將位圖轉(zhuǎn)化為矩陣V。

通過上述操作，將各個(gè)訓(xùn)練空域轉(zhuǎn)化為矩陣的形式存儲(chǔ)，以便進(jìn)行后續(xù)的操作。

2.2 編碼及解碼方式

編碼是將問題的可行解轉(zhuǎn)化為遺傳算法能處理的搜索空間來進(jìn)行操作。本文編碼主要是考慮空域的放置方向。鑒于實(shí)際情況，本文中空域塊只作水平90°旋轉(zhuǎn)。每一種方案都對應(yīng)于一個(gè)編碼長度為2n的字符串S={S1,S2,…,Sn,Sn+1,…，S2n}。其中，S1～Sn是空域塊的編號(hào)，由[1,n]間的非重復(fù)正整數(shù)組成；Sn+1～S2n則是相應(yīng)的空域塊的放置方向，是由{0，1}組成的字符串，0表示長與x軸平行，1則表示長與y軸平齊，即水平旋轉(zhuǎn)90°。

解碼是指按照一定的規(guī)則得出每個(gè)字符串相應(yīng)的適應(yīng)度函數(shù)值，以便進(jìn)一步處理。本文采用的原則是：根據(jù)字符串中的順序及相應(yīng)的放置方向依次在空域內(nèi)尋找相應(yīng)的空間；對于空域塊的放置，采用逐層遞加的方式；對于每層則采用左下優(yōu)先的策略。

2.3 評(píng)估函數(shù)

空域規(guī)劃的主要目標(biāo)是提高空域利用率，故將目標(biāo)函數(shù)作為適應(yīng)度函數(shù)(S表示某一染色體)。即

Fitness(S)

(6)

但在對染色體作遺傳運(yùn)算的過程中需要考慮約束條件，故利用懲罰函數(shù)來將有約束問題轉(zhuǎn)化為無約束問題。針對空域規(guī)劃問題，本文主要考慮以下三個(gè)懲罰項(xiàng)：

(1) 空域塊必須放置在作戰(zhàn)責(zé)任區(qū)內(nèi)，即滿足約束條件(2)和條件(3)；

(7)

(2) 空域塊之間不能重疊，即滿足約束條件(4)；

(8)

(3) 空域塊需要平行于坐標(biāo)軸放置，即滿足約束條件(5)；

(9)

對于三個(gè)約束條件而言，任何一項(xiàng)不滿足，該解均為不可行解，故本文將評(píng)估函數(shù)定義為

(10)

2.4 遺傳操作過程

針對某一染色體，本文對其上基因進(jìn)行遺傳操作，主要包括：選擇操作、交叉操作和變異操作。通過上述操作來模擬自然界中的物種進(jìn)化過程，不斷尋求問題的最優(yōu)解。

(1) 選擇操作

選擇操作的目的是從當(dāng)前群體中選出優(yōu)良個(gè)體來作為下一代繁殖的父本，它是通過適應(yīng)度函數(shù)選擇優(yōu)勝的個(gè)體來遺傳到下一代。本文綜合采用輪盤賭法和最優(yōu)個(gè)體保存的方法。輪盤賭選擇的思路是：先計(jì)算每個(gè)個(gè)體的適應(yīng)度函數(shù)值并求和，再根據(jù)每個(gè)個(gè)體所占據(jù)的比例選擇遺傳到下一代的個(gè)體。為了保證種群的最優(yōu)進(jìn)化，本文還利用最優(yōu)個(gè)體保存法(即，將父代中適應(yīng)度值最高的個(gè)體遺傳到下一代)，從而可以保證遺傳算法以1的概率收斂。

(2) 交叉操作

交叉是指對兩個(gè)相互配對的個(gè)體以某種方式交換部分基因來形成兩個(gè)新的個(gè)體。本文綜合采用順序交叉和兩點(diǎn)交叉。在交叉過程中隨機(jī)生成兩個(gè)[1，2n]間的整數(shù)a1和a2(a1lt;a2)作為交叉位。若a2≤n,則對a1～a2之間的基因采用順序交叉的方法；若a1gt;n,則對a1～a2之間的基因采用兩點(diǎn)交叉的方法，即，直接交換交叉位之間的基因，其他基因保持不變；若a1≤n且a2gt;n,則對a1～an之間的個(gè)體采用順序交叉，而an+1～a2之間的個(gè)體采用兩點(diǎn)交叉的方法。

(3) 變異操作

為了保證遺傳過程中種群的多樣性，避免算法過早收斂導(dǎo)致無法找到全局最優(yōu)個(gè)體，對個(gè)體以一定的概率來進(jìn)行變異操作。本文中變異操作只針對個(gè)體的后半部分基因(n+1～2n)，具體操作為：在[n+1,2n]間的每個(gè)基因位隨機(jī)生成一個(gè)隨機(jī)數(shù)，若其小于變異率則將此基因位的基因換為其他的等位基因。

(4) 交叉、變異的自適應(yīng)性

交叉率、變異率的選擇會(huì)影響到遺傳算法的運(yùn)行結(jié)果，通常它們的值都是人工設(shè)定且不隨迭代代數(shù)變化的。但是在自然界中，當(dāng)生態(tài)穩(wěn)定的時(shí)候，很多生物會(huì)采用無性繁殖，而當(dāng)環(huán)境惡化的時(shí)候，這些生物會(huì)采用有性繁殖來大量繁殖以增加個(gè)體的適應(yīng)性及多樣性，這也使得交叉率和變異率都有提高。

為了使遺傳算法更加貼合實(shí)際，本文利用兩個(gè)函數(shù)來模擬上述過程。當(dāng)種群后代沒有進(jìn)化時(shí)，增加交叉率和變異率，到1時(shí)停止；當(dāng)種群進(jìn)化時(shí)，會(huì)相應(yīng)地減小交叉率和變異率。本文以f(x)=(1-cp)e-1/cf作為交叉率的增量值，其中cp是指當(dāng)前的交叉率，cf是未進(jìn)化的迭代次數(shù)。由于變異率比交叉率小，以f(x)=(1-mp)e-1/cf/10作為變異率的增量值；當(dāng)后代進(jìn)化了，將p=bi·p/3的值作為交叉率和變異率的減量值，其中bi為當(dāng)前最優(yōu)的空域利用率值，p為當(dāng)前的變異率和交叉率。

3 三維訓(xùn)練空域規(guī)劃實(shí)例仿真

為了測試該方法對訓(xùn)練空域規(guī)劃問題的合理性和有效性，進(jìn)行下述的實(shí)例仿真。

(1) 多科目訓(xùn)練空域規(guī)劃實(shí)例

某機(jī)場航空兵不同戰(zhàn)術(shù)訓(xùn)練科目所需的空域大小如下表1所示。

表1 不同訓(xùn)練科目所需空域大小

該機(jī)場作戰(zhàn)責(zé)任區(qū)如下圖1所示。首先，需對該不規(guī)則的訓(xùn)練空域進(jìn)行離散化處理，并轉(zhuǎn)化為相應(yīng)的矩陣。其離散化后的空域圖如圖2所示。

應(yīng)用改進(jìn)的遺傳算法來進(jìn)行計(jì)算，各項(xiàng)的初始參數(shù)取值分別為：種群規(guī)模m=20,迭代代數(shù)n=100，初始交叉率cp=0.9，初始變異率mp=0.1。通過計(jì)算得到的最大適應(yīng)度值為1.655 5。其數(shù)值變化如圖3所示。

交叉率和變化率隨著迭代次數(shù)的變化如圖4所示。

從圖4可以看出：交叉率和變異率隨著空間利用率的上升而下降，當(dāng)最優(yōu)空間利用率不變時(shí)，交叉率和變異率會(huì)上升來增加種群多樣性。

最后得到的戰(zhàn)術(shù)訓(xùn)練空域規(guī)劃和底面分布如圖5～圖6所示。

(2) 含時(shí)間因素的空域規(guī)劃實(shí)例

假定該機(jī)場某時(shí)段內(nèi)訓(xùn)練科目只有3種，且每種訓(xùn)練科目均需完成6次，各科目所需空域大小為(4，14，3)、(8，8，2)、(10，5，3)，而各科目的訓(xùn)練時(shí)間依次為30、40、50 min。利用上述方法，同樣可以得出其最優(yōu)規(guī)劃。由于訓(xùn)練科目較多，無法一次性完成所有科目，故需要分批次進(jìn)行訓(xùn)練。通過仿真可知，上述科目需分兩個(gè)階段進(jìn)行，各階段的底層排樣圖和訓(xùn)練空域圖如圖7～圖8所示。

從圖7～圖8可以看出：按照目前的以科目分批次訓(xùn)練，由于科目二和科目三無法同時(shí)在空域內(nèi)完成，需分兩批進(jìn)行，故需要210 min。利用本文算法可將訓(xùn)練時(shí)間由210 min縮短為100 min；而從圖7可以看出：利用此方法在實(shí)現(xiàn)動(dòng)態(tài)任務(wù)規(guī)劃的同時(shí)也能夠保證空域利用率和用空安全，為空域的靈活使用提供一定的借鑒意義；利用計(jì)算機(jī)進(jìn)行輔助設(shè)計(jì)，大大縮短了空域規(guī)劃所需時(shí)間，提高了規(guī)劃效率。

4 結(jié) 論

本文提出了一種對訓(xùn)練空域的規(guī)劃方法。其先將三維空域進(jìn)行離散化處理，根據(jù)空域規(guī)劃的特點(diǎn)構(gòu)建了相應(yīng)的規(guī)劃模型，再利用改進(jìn)的遺傳算法來找出最優(yōu)的規(guī)劃方案，最后通過實(shí)例驗(yàn)證了方法的合理性和有效性。與人為劃分訓(xùn)練區(qū)域相比，利用計(jì)算機(jī)來輔助處理，不僅大大縮短了工作時(shí)間，還在一定程度上可以提高空域的利用率。對未來空域的靈活使用具有一定的參考價(jià)值，但該算法的穩(wěn)定性和求解效率還有待進(jìn)一步的研究和改進(jìn)。

[1] Pisinger D. Heuristics for the container loading problem[J]. European Journal of Operational Research, 2002, 141(2): 382-392.

[2] Jolal F, Ghanbari A. Integrating data transformation techniques with hopfield neural networks for solving traveling salesman problem[J]. Expert Systems with Application, 2010, 37(7): 5331-5335.

[3] 郭中華, 金靈, 鄭彩英. 人工神經(jīng)網(wǎng)絡(luò)求解TSP問題的改進(jìn)算法研究[J]. 計(jì)算機(jī)仿真， 2014， 31(4): 355-358.

Guo Zhonghua, Jin Ling, Zheng Caiying. Study on improved method of neural network to solve TSP[J]. Computer Simulation, 2014, 31(4): 355-358.(in Chinese)

[4] Katayama K, Sakamoto H. The efficiency of hybrid mutation genetic algorithm for the traveling salesman problem[J]. Mathematical and Computer Modeling, 2000, 31: 197-203.

[5] 蔣興波, 呂肖慶, 劉成誠. 一種用于矩形排樣優(yōu)化的改進(jìn)遺傳算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2008, 44(22): 244-248.

Jiang Xingbo, Lü Xiaoqing, Liu Chengcheng. Improved genetic for packing problem of rectangles[J]. Computer Engineering and Applications, 2008, 44(22): 244-248.(in Chinese)

[6] Dorigo M, Bonabeau E. Ant algorithms and stigmergy[J]. Future Generation Computer System Journal, 2000, 16: 851-857.

[7] 郭怡, 李輝. 基于蟻群算法的矩形排樣問題研究[J]. 中國農(nóng)機(jī)化學(xué)報(bào), 2014, 35(4): 250-254.

Guo Yi, Li Hui. Research on rectangular packing based on ant colony algorithm[J]. Journal of Chinese Agricultural Mechanization, 2014, 35(4): 250-254.(in Chinese)

[8] Fuellerer U, Doemer K F, Hartl R F, et al. Metaheuristicsfor vehicle routing problems with three-dimensional loading constraints[J]. European Journal of Operational Research, 2010, 201(3): 751-759.

[9] 張德富, 魏麗軍, 陳青山, 等. 三維裝箱間題的組合啟發(fā)式算法[J]. 軟件學(xué)報(bào), 2007, 18(9): 2083-2089.

Zhang Defu, Wei Lijun, Chen Qingshan, et al. A combinational heuristic algorithm for the three dimensional packing problem[J]. Journal of Software, 2007, 8(9): 2083-2089.(in Chinese)

[10] Lim A, Rodrigues B, Yang Y. 3-D container packing heuristics[J]. Applied Intelligence, 2005, 22(2): 125-134.

[11] Stefanj. On genetic algorithms for the packing of polygons[J]. European Journal of Operations. 1996, 88: 165-181.

[12] Leng T W, Yung C H, Troutt M D. Applications of genetic search and simulated annealing to the two-dimensional non-guillotine cutting stock problem[J]. Computers amp; Industrial Engineering, 2001(40): 201-214.

馬嘉呈(1992-)，男，碩士研究生。主要研究方向：空域與流量管理。姚登凱(1966-)，男，博士，教授。主要研究方向：空域管理。趙顧顥(1986-)，男，博士研究生，講師。主要研究方向：空域管理和量子密匙等。

(編輯：趙毓梅)

ResearchonPlanningMethodsof3DTacticalTrainingAirspace

Ma Jiacheng, Yao Dengkai, Zhao Guhao

(College of Air Traffic Control and Navigation, Air Force Engineering University, Xi’an 710051, China)

The planning of 3D tactical training airspace is to make good use of airspace. Artificial nesting cannot guarantee the efficient and safe use of airspace, so it is of important significance to find an efficient and fast algorithm to improve the efficiency of airspace utilization and training. Through the theoretical research of airspace planning and considering the attributes of airspace, the airspace is divided into several cubical units, based on which the training airspace planning model is constructed. An improved genetic algorithm is applied to find the optimal solution, while a lot of infeasible solutions are discarded. In the end, a simulation is performed to test the feasibility and effectiveness of the model proposed. Results show that the airspace model can improve the efficiency and accuracy of airspace planning, and it is reasonable and effective.

3D tactical training; airspace safety; airspace planning; genetic algorithm; layout optimization

2017-04-28；

2017-06-15

國家社會(huì)科學(xué)基金軍事學(xué)項(xiàng)目(16GJ004-264)國家空管科研課題(KGKT05140501)

馬嘉呈,727032612@qq.com

1674-8190(2017)04-375-06

V328.1

A

10.16615/j.cnki.1674-8190.2017.04.002