三維戰術訓練空域規劃方法研究

馬嘉呈，姚登凱，趙顧顥

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

三維戰術訓練空域規劃方法研究

馬嘉呈，姚登凱，趙顧顥

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

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

三維戰術訓練；空域安全；空域規劃；遺傳算法；排樣優化

0 引 言

隨著我國空軍軍事訓練轉型的推進，軍事訓練時間、戰術訓練比重不斷提高，多兵機種合練、體系對抗已成常態，對空域等資源需求逐年增加。同時我國民用航空運輸業進入持續快速發展的新階段，對空域的需求也日益迫切。因此，合理安全利用航空兵戰術訓練空域，既有利于充分發揮我軍主戰裝備的優勢，又有利于空域結構的合理優化，有效緩解軍民航空域需求矛盾問題。

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

在解決此類問題的過程中，主要存在以下困難：利用窮舉法在空域塊較多時出現“組合爆炸”，無法準確地找出最佳方案；啟發式搜索法引入的啟發信息主要依靠人為經驗，故存在“組合爆炸”；神經網絡在解決此問題時，雖效果明顯，但易于陷入局部最優，當空域塊種類較多時，無法尋找出全局最優的解決方案。

本文將空域劃分為立方體單元，并依此構建空域離散化模型，通過改進的遺傳算法來不斷尋優，找出最佳的規劃方案。

1 訓練空域規劃的數學模型

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

①空間約束：各個訓練空域塊均需安排在機場作戰責任區內，且所需的空域總體積不得大于機場總空域體積。

②位置約束：各個訓練空域塊之間不得重疊。

③方向約束：鑒于實際情況，各訓練空域塊放置時，需要與坐標軸平行，但可以水平90°旋轉。

1.1 符號說明

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

①n：總的訓練空域塊個數；

②m：最后排入的訓練空域塊個數；

③xi,yi,zi：訓練空域塊參考點的坐標，i=1,2,…,n；

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

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

⑥V：離散化后整個空域的體積；

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

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

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

1.2 目標函數及約束條件

本文中的優化目標是使得整個空域的利用率最大化，即在該機場作戰責任區內安排的訓練空域塊最多，故目標函數可表示為

(1)

在規劃過程中由于受到空間約束，各個訓練空域必須被包含在作戰責任區內，故各個空域點與各個訓練空域塊的代表值之和必定小于或者等于1，且排入的空域塊體積之和必小于作戰責任區的范圍。具體公式如下：

(2)

(3)

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

(4)

在規劃過程中，由于各個空域塊需要與坐標軸平行放置，故需要滿足下述的約束條件：

(5)

2 遺傳算法求解空域規劃的主要方法

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

2.1 訓練空域的預處理

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

步驟1 將整個訓練空域以圖像的形式存儲在內存當中；

步驟2 將圖像轉化為位圖(0/1形式)進行存儲；

步驟3 人為劃分區間，并取置信度為0.75，將位圖轉化為矩陣V。

通過上述操作，將各個訓練空域轉化為矩陣的形式存儲，以便進行后續的操作。

2.2 編碼及解碼方式

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

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

2.3 評估函數

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

Fitness(S)

(6)

但在對染色體作遺傳運算的過程中需要考慮約束條件，故利用懲罰函數來將有約束問題轉化為無約束問題。針對空域規劃問題，本文主要考慮以下三個懲罰項：

(1) 空域塊必須放置在作戰責任區內，即滿足約束條件(2)和條件(3)；

(7)

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

(8)

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

(9)

對于三個約束條件而言，任何一項不滿足，該解均為不可行解，故本文將評估函數定義為

(10)

2.4 遺傳操作過程

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

(1) 選擇操作

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

(2) 交叉操作

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

(3) 變異操作

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

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

交叉率、變異率的選擇會影響到遺傳算法的運行結果，通常它們的值都是人工設定且不隨迭代代數變化的。但是在自然界中，當生態穩定的時候，很多生物會采用無性繁殖，而當環境惡化的時候，這些生物會采用有性繁殖來大量繁殖以增加個體的適應性及多樣性，這也使得交叉率和變異率都有提高。

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

3 三維訓練空域規劃實例仿真

為了測試該方法對訓練空域規劃問題的合理性和有效性，進行下述的實例仿真。

(1) 多科目訓練空域規劃實例

某機場航空兵不同戰術訓練科目所需的空域大小如下表1所示。

表1 不同訓練科目所需空域大小

該機場作戰責任區如下圖1所示。首先，需對該不規則的訓練空域進行離散化處理，并轉化為相應的矩陣。其離散化后的空域圖如圖2所示。

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

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

從圖4可以看出：交叉率和變異率隨著空間利用率的上升而下降，當最優空間利用率不變時，交叉率和變異率會上升來增加種群多樣性。

最后得到的戰術訓練空域規劃和底面分布如圖5～圖6所示。

(2) 含時間因素的空域規劃實例

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

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

4 結 論

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

[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] 郭中華, 金靈, 鄭彩英. 人工神經網絡求解TSP問題的改進算法研究[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] 蔣興波, 呂肖慶, 劉成誠. 一種用于矩形排樣優化的改進遺傳算法[J]. 計算機工程與應用, 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]. 中國農機化學報, 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] 張德富, 魏麗軍, 陳青山, 等. 三維裝箱間題的組合啟發式算法[J]. 軟件學報, 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

國家社會科學基金軍事學項目(16GJ004-264)國家空管科研課題(KGKT05140501)

馬嘉呈,727032612@qq.com

1674-8190(2017)04-375-06

V328.1

A

10.16615/j.cnki.1674-8190.2017.04.002