基于离散粒子群算法的战术训练空域规划问题*

马嘉呈，姚登凯，赵顾颢，孙天驰

（空军工程大学空管领航学院，西安 710051）

0 引言

随着我国空军军事训练转型的推进，军事训练时间、战术训练比重不断提高，多兵机种合练、体系对抗已成常态，对空域资源的需求逐年增加。而由于民航业的持续快速发展，其对空域的需求也日益迫切。因此，合理安全地利用航空兵战术训练空域，既有利于充分发挥我军主战装备的优势，又有利于空域结构的合理优化，从而实现军民航的协调可持续发展。

航空兵战术训练空域规划是指在某作战责任区内，对各个训练科目所需空域的合理规划和安排。而对于训练空域的规划问题，目前国内没有成熟的计算方法和理论体系，大多是根据参谋人员的经验人为划设，故无法保证空域的利用率和灵活性。根据计算复杂理论可知，该问题类似于NP完全问题。近年来，不少学者应用人工神经网络算法[1-2]、遗传算法[3-4]、蚁群算法[5-6]等智能算法来解决该问题。随着智能算法的发展和人们对排样问题的深入理解，利用启发式排样算法和人工智能算法的组合算法已成为解决此类的重点研究方向。但训练空域规划问题有其自身的独特性，目前的几种排样算法均不适用于解决该问题。其次，作战责任区通常是不规则形的，而排样问题大都是解决在矩形区域内的，对于不规则区域内的排放问题研究较少。而且，由于空域的有限性，无法保证所有的训练科目均被安排。这些都给训练空域的规划增加了难度。本文首先将空域进行离散化处理，并构建空域规划模型；根据空域规划的特点，将离散粒子群算法[7-8]与改进的最低水平线算法相结合来获得最佳的规划方案，并与传统的遗传算法进行比较来验证该方法的高效性。

1 训练空域规划模型

战术训练空域规划问题是指在指定的作战责任区内，对各个训练科目所需空域的合理安排，从而使整个空域的利用率达到最大。即在指定的作战责任区S内，排放N个作战科目，每个作战科目所需空域的长为li（1≤i≤N），宽为wi（1≤i≤N）。在排放过程中，使整个空域的利用率E最大。

式中，m为排入的训练科目个数。由于受到区域地形、空中禁飞区、军民航线等多方面的影响，某机场所辖的空域范围通常是不规则形状的。故在解决空域规划的问题时，需将其离散化处理，抽象为单元格的集合并置于二维坐标系中。其约束条件为：

1）范围约束：各个训练空域均需安排在所辖的作战责任区以内，所需的总面积不能大于作战责任区的面积。

2）位置约束：各个科目的训练空域之间不能重叠。

3）方向约束：考虑到实际情况，为使空域的利用率最大化，各个训练科目在排放时需要与坐标轴平行，且可以水平旋转90°。具体如下所示

式中，n 为总的训练科目数；x，y 为空域的坐标；l，w为各个科目训练空域所需的长度和宽度；Exy为取值为0或1的变量，表示（x，y）处的空域是否被占用。若被占用则Exy=1，否则为取值为0或1的变量，表示第i个训练科目所需空域是否占用（x，y）处的空域，若被占用则，否则：取值为0或1的变量，表示训练科目i的长是否平行于X轴或Y轴某个轴，若平行于X轴，则lxi=1；Wxi，Wyi，Wzi：取值为0或1的变量，表示训练科目i的宽是否平行于X轴或Y轴某个轴，若平行于Y轴，则Wyi=1，i=1，2，…，n；S 为作战责任区的总面积。

上式中，式（2）、式（5）是保证各个训练科目均被放置在所辖的作战责任区内，即范围约束；式（3）是保证各个训练空域之间不会重叠，即位置约束；式（4）是保证各个训练科目之间均沿坐标轴方向放置，即方向约束。

2 改进的最低水平线算法

最低水平线算法是以BL算法为基础的一种排样搜索算法。它是利用最高轮廓线和最低水平线来完成搜索寻优的。最高轮廓线是当前排样过程中各排样件最大高度的集合，而最低水平线是指最高轮廓线中最低的一段。但传统的最低水平线法只是利用了各个矩形件的上边缘，对于之下的空隙则无法利用。这在一定程度上也会造成资源的浪费。而对于训练空域规划问题，由于作战责任区是不规则的，利用传统的方法也无法充分利用作战责任区的边缘空域。当前的最低水平线无法容纳当前矩形的时候，采用的办法是向后搜索一个可容纳的矩形，如若没有则提升最低水平线。但由于其在搜索时只考虑离当前排样矩形最近的一个矩形，这将不能保证资源利用率的最大化。本文对传统的最低水平线的改进如下：不再设置最高轮廓线，而是建立一个最低水平线库，即搜索当前空域内所能利用的所有位置。这将保证边缘空域的合理利用；在向后搜索的过程中，若对于当前最低水平线，有一个以上的可容纳的训练科目时，选择与其宽度最接近的排放，这能保证空域利用的最大化。具体步骤如下：

1）从作战责任区的下边缘开始，依次向上搜索所有可利用的空域段，并记录它的起点位置及其长度。

2）从第一个空域段开始，根据所给的训练科目的宽度，依次寻找该空域段可容纳的训练科目：

a）如果该空域段的长度大于训练科目的宽度，且排入后不会占用已利用的空域，则将该训练科目安排在该位置，并更新最低水平线库。

b）否则，向后搜索选择与之宽度最接近的训练科目排入，若没可容纳的训练科目，则从下一个空域段继续搜索。

3）重复步骤2）至该作战责任区内无法再安排其他训练科目为止。

3 粒子群优化算法

粒子群优化算法是Kennedy博士和Eberhart博士受自然界中鸟群运动模型的启发提出的一种基于种群的搜索算法。该算法建模简单，且所需的参数较少。相较于其他进化算法，该算法实现时比较简单并且具有更强大的全局优化能力。目前在人工智能、认知科学等多个领域均得到了广泛的应用。而且，大量的实验结果表明：对于遗传算法解决的各类优化问题，PSO算法能更加高效地解决此类问题。

3.1 离散粒子群优化算法

PSO算法的应用大多数注重连续、无约束的确定性优化问题，在离散、约束等优化问题上研究较少。目前，已经提出了多种离散粒子群算法，并且在解决旅行商（TSP）问题上取得了不错的效果。本文利用置换子和置换序列来解决空域规划问题。

1）置换子：假设某个序列位置为Xk，置换子为（ik，jk）。则置换操作为交换位置 Xk中值为 ik，jk的位置来得到新的位置 X′。例如 Xk=（1，2，3，4，5），（ik，jk）=（2，3），则 X′=（1，3，2，4，5）。

2）置换序列：由单个或多个置换子构成的有序列就是置换序列。通常情况下，两个位置作差就会得到一个置换序列。例如：置换序列={（1，2），（2，3）}，序列位置为（1，2，3，4，5），通过置换得到的新位置为（3，1，2，4，5）。注意置换序列是按照置换子的位置依次作用在位置序列上的。

3）加法操作：对于位置和速度之间的加法是指将置换序列中的置换子依次作用于该位置从而得到新的位置。

4）速度的数乘：将数乘运算定义为：

其中，Rand（）为一个0～1之间的随机数。而数乘操作的含义是以一定的概率（1/C）来保留对速度的操作。如当C=4时，保留概率为25%。

5）粒子的更新

在离散粒子群中，速度和位置的更新如下所示：

其中，w，C1，C2为速度保留概率，以及全局最优值和个体最优值对进化的影响因数。

3.2 应用离散粒子群算法解决训练空域规划问题

针对战术训练空域规划问题的离散性的特点，本文利用离散粒子群算法来解决此问题。具体算法介绍如下：

3.2.1 编码与解码

针对训练空域规划问题的离散性，本文采用整数编码的方式来进行编码。首先对各个训练科目进行编号，再根据训练科目数n，生成一个1～n的整数排列，即为一个排放序列。每个排放序列根据改进的最低水平线算法都能生成一个规划方案，从而确定该方案的适应度值。

3.2.2 适应度函数

对于训练空域规划问题，由于空域范围限制无法同时容纳所有的训练科目，故在考虑空域利用率的同时还需要兼顾所能容纳的训练科目数。故目标函数为

其中，S为任一规划方案，E为空域的利用率，m为被安排的训练科目数，N为总的训练科目数。由于在解决训练空域规划问题时，需要考虑其约束条件，故本文利用惩罚函数来将其转化为无约束问题，对于上文中的3个约束条件，违反任一条此排样方案均被视为无效方案，故引入参数q来代表惩罚项。q的取值为0或1，当满足约束时q=1，反之为0。故最后的适应度函数应为：

3.2.3 算法具体步骤

假定种群的粒子数为m，最大的迭代次数为N，个体最优位置为Pid，全局最优位置为Pgd。

1）产生初始粒子种群。针对战术训练空域规划问题的离散性，本文选取m个1～n的整数排列（n为训练科目数）作为初始粒子群的位置，并且每个位置均赋予一个初始的速度，同时给定参数W，C1，C2的值。

2）利用改进的最低水平线法来计算每个粒子的适应度值F，并将其作为每个粒子的初始个体最优位置Pid，选取其中适应度最大的位置作为全局最优位置Pgd。

3）按照上文中粒子更新的方法更新粒子的位置，并同时求出每个新位置的适应度值。如果新位置的函数值大于原函数值，则更新该粒子的个体最优位置。而对于整个粒子群，每更新一代就选取其中最大的适应度值与上一代的进行比较，若大于，则将此位置作为新的全局最优位置。

4）当迭代次数达到设定的最大迭代次数或者适应度不再发生变化时，终止该算法，并根据最优的规划方案画出空域规划图。

算法的流程如图1所示。

图1 训练空域规划流程图

4 算例分析

为了测试该算法的性能，本文以MATLAB R2014为平台进行了下述的实例仿真。

某机场不同机型的不同训练科目所需空域大小如表1所示。

而该机场的作战责任区如图2所示。

根据上述方法，首先需要对该机场的作战责任区进行离散化处理，以便利用离散粒子群算法来求解战术训练空域规划问题。其离散化后的图形如图2所示。

表1 各训练科目所需空域大小

图2 作战责任区

图3 作战责任区离散图

根据上述方法，首先需要对该机场的作战责任区进行离散化处理，以便利用离散粒子群算法来求解战术训练空域规划问题。其离散化后的图形如图3所示。

在离散化处理完成后，利用离散粒子群算法结合改进的最低水平线法来对问题进行求解。在求解过程中，假定粒子群的种群个数为20，迭代次数为100代，个体经验保留概率C1=0.85，全局经验保留概率C2=0.85。通过仿真，发现当迭代到第73代时已经趋于稳定，而此时的适应度值为11.855 3。最后生成的空域训练图以及在迭代过程中每代的最优适应度值和平均适应度值的变化过程如图4和图5所示。

图4 适应度值变化曲线图

图5 战术训练空域规划图

为确定该算法的高效性，本文与解决排样问题中常用的智能算法（遗传算法）来进行比较，同样，在利用遗传算法求解过程中，设定种群大小为20，迭代次数为100代，选择和变异概率均为0.8。通过仿真发现：当迭代到第90代的时候，基本趋于稳定，而此时的适应度值为10.789 9。最后生成的空域训练图以及在迭代过程中每代的最优适应度值和平均适应度值的变化过程如图6和图7所示。

图6 适应度值变化曲线图

图7 战术训练空域规划图

通过对比两组数据，不难看出：本文算法对于战术训练空域规划问题的求解要明显优于传统的遗传算法。利用本文算法得到的训练空域规划方案对空域的利用率要更大，且在作战责任区内安排的训练科目数也更多；通过比较两组数据趋于稳定时的代数，发现遗传算法的搜索性能要明显弱于离散粒子群算法；而从程序运行的时间上看，利用离散粒子群算法所用的求解时间要明显小于人工排样的时间，且短于遗传算法所需要的时间。由此可见，本文提出的离散粒子群算法结合改进最低水平线算法在解决战术训练空域规划问题上具有良好的性能，并且要优于传统的遗传算法求解。

5 结论

随着我国军民航持续稳定高效地发展，对空域资源的需求日益迫切。因此，合理高效地利用空域对于缓解军民航用空冲突具有重大意义。本文将战术训练空域规划问题通过离散化处理将其抽象为数学问题来进行求解，通过利用离散粒子群算法结合改进的最低水平算法来寻找最优的规划方案。最后与传统遗传算法的比较来验证算法的合理性。相比于人为排样规划，该算法在进行战术训练空域规划时要更为高效，同时也为以后空域的灵活使用提供了一定的参考价值。但是对于求解过程中参数的设定以及求解的精度上还有待一步的讨论和研究。