三维战术训练空域规划方法研究

马嘉呈，姚登凯，赵顾颢

(空军工程大学 空管领航学院，西安 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