李怡敏，王宝珠，刘翠响，高 妍
（河北工业大学 信息工程学院，天津 300401）
0 引 言
低空空域是一种重要的空中资源，既是国家空域体系的重要组成部分，也是各类通用航空器的活动区域，蕴藏着极大的经济价值和社会价值[1]。根据国务院中央军委空中交通管制委员会在 2014年颁布《低空空域使用管理规定（试行）》的规定，我国的低空空域一般是指全国范围内真高1 000 m（含）以下区域，山区和高原地区可经批准后根据实际需求，适当调整高度范围[2]。我国航空航天较美国等发达国家起步较晚[3]，早在1993年，美国联邦航空管理局（Federal Aviation Administration，FAA）为了在美国建立更为简单、有效的国家空域体系，根据美国的地理自然条件和航空发展现状，有选择地引入了国际民航组织（ICAO）制定的空域分类标准[4]，将其国家空域的80%划设为民用空域，而这其中绝大部分的空域活动是低空空域的通用航空。由此可见，我国的航空航天事业取得了一定发展，但在低空空域的开放和利用方面距离美国等发达国家还存在一定的差距。目前，我国已经在逐步开放低空空域，这一资源在不久的将来一定能够得到更加充分的使用。
随着我国的信息技术和自动化技术的迅速发展，航空航天领域也得到了发展和变革，飞行器的种类和功能层出不穷，航迹规划技术也应运而生。航迹规划，就是在一定约束条件下，寻求从起始点到目标点满足特定目标的最优飞行航迹[5]。在低空空域，由于地形的复杂以及各类雷达障碍物的阻碍，低空航迹规划成为现代化战场上克敌制胜的关键。
1 算法与改进
1.1 头脑风暴算法的基本原理
头脑风暴算法（Brain Storm Optimization）是一种新的群体智能优化算法[6-7]，是史玉回教授在2011年的第二次群体智能国际会议上提出的。该算法模拟了人类集思广益求解问题的行为，即头脑风暴的过程[8]，基本思想是通过聚类/分类的方法分析解集合的构成，基于解的分布生成新的解，并经过迭代求解。该算法将群体智能优化算法与数据分析方法相结合[9]，具有求解过程不依赖数学模型的特点，在处理多目标优化问题等方面具有较好效果。
头脑风暴算法的实现过程是：
1）产生n（种群大小）个潜在的问题的解（个体），然后用聚类算法将这n个个体分为m（预先设定的参数）类，通过评估这n个个体，将每一类中的个体进行排序，选出每一类内最优的个体作为该类的中心个体；
2）随机选中一个类的中心个体，按概率大小确定它是否被一个随机产生的个体所替代；
3）进行个体的更新过程，通过某一种方式产生新个体。BSO 算法中存在三类算子，它们分别是解聚合类算子、新解生成算子以及新解选择算子[10]。
BSO 算法的基本流程如图1所示。
其中，在进行解集合聚合类时，传统BSO 算法采用了k-means 聚类，这一方法建立在已知数据有多少类的基础上，首先给定聚类中心a，求取各个点和聚类中心的欧氏距离，取数值较小的距离作为当前距离，并将该点归入中心点；然后将归入中心点的各个点的平均值作为新的聚类中心，重复上边的步骤，直到达到阈值或者规定迭代次数。可以看出，这一方法的优点是计算速度快，运算简单，但是初始聚类中心的选择对于聚类影响很大，对于一些特殊情况，k-means 算法无法做出正确聚类。
算法随机选择一至两个类别生成新解，在生成新解的过程中，由Pg来确定新解的生成方式。如果随机生成的数值比Pg小，那么生成的新解是由一个聚类簇生成的；如果随机数值比Pg大，则由两个聚类簇生成新解。Pg取 0.3～0.8 之间，函数收敛效果最好[11]。新解由选择的解加上一个高斯随机值来得到。
1.2 算法的改进
传统BSO 算法采用的k-means 聚类方法具有计算简单、运算速度快的优点。但是该算法也存在一定的缺点，首先，算法运行时需要人为给定一个聚类数，而聚类数对聚类结果具有很大影响；其次，初始聚类中心选择不好，很有可能难以得到理想的聚类效果；最后，聚类中心是类信息的平均值，故对“噪声”和孤立点数据敏感，少量的该类数据能够对平均值产生极大的影响[12]。而k-means 聚类方法的这些缺点难免会影响BSO 算法的性能。
由于k-means 聚类方法存在以上缺点，本文采用基于密度的DBscan 算法。在DBscan 算法中将数据点分为以下三类：核心点（在半径内含有超过领域密度阈值数目的点）、边界点（在半径内点的数量小于领域密度阈值数目，但是落在核心点的邻域内）、噪音点（既不是核心点也不是边界点的点）。
算法的基本步骤如下：
1）首先确定半径r和邻域密度阈值minPoints。从一个没有被访问过的任意数据点开始，以这个点为中心，r为半径的圆内包含的点的数量是否大于或等于minPoints，如果大于或等于minPoints，则该点被标记为核心点，反之则会被标记为噪音点。
2）重复步骤1），如果一个噪音点存在于某个核心点为半径的圆内，则这个点被标记为边缘点，反之仍为噪音点。重复步骤1），直到所有的点都被访问过。
DBscan 算法较k-means 算法来说，不需要输入聚类数k，就可以发现任意形状的数据集，对于实际的低空航线规划问题具有更好的适应性。这里将采用DBscan算法聚类的BSO 算法简称为DBBSO 算法。
2 低空航线规划的数学建模
考虑到低空空域高度变化不大的特点，为了方便计算，将三维空间简化为二维平面，同时，对坐标系进行转换。由于航线规划主要思考了从初始点s到目标点e的路径选择问题，初始点和目标点都是已知的，因此，在这里将方向作为新坐标系的x轴方向，与垂直方向作为新坐标系的y轴方向，并将s点作为坐标原点。如图2所示，转换后的新坐标系的坐标为：
式中，θ为原始坐标系到新坐标系逆时针旋转的角度。
图2 坐标系转换Fig.2 Transformation of coordinate system
2.1 目标函数
低空范围内的航线规划受到多个条件的制约，一般要满足多个条件，如安全性、实时性、协作性以及飞行约束，在这里主要讨论最小航迹段长度和安全性这两点条件约束下的目标函数。
2.1.1 最小航迹段长度
由于受到燃油及其他条件的限制，战斗机无法做到无限制的航行，因此，飞行距离就成为了一个限制条件。对于航迹规划，规划结果常常不是唯一的，存在许多可行航迹，但是最终实行的航迹的长度都必须是满足同等约束条件下最小的航迹段。由于已知初始点s和终点e，将整个se段分为n个相等的段，设li(i=0,2,…,n)为无人机的各段的航迹长度，假设整个航迹长度为L，那么L就可以表示为：
2.1.2 安全性
在低空空域飞行时，战斗机既需要躲避雷达的探测，也需要避过各种地形障碍物，如建筑物、高山、高压电线等，因此低空航线规划的首要原则是需要避开地形、雷达、高炮等各种威胁，确保飞行物的安全。假设敌方威胁位置坐标为W（a，b），通常威胁存在一定的作用范围，低空航迹规划应尽可能规避威胁，即绕过这些区域，不同的威胁具备不同的威胁等级，即它们的威胁程度不同，按照威胁程度的大小，共有5 个等级[13]，如表1所示。
表1 威胁环境Table 1 Threat environment
雷达威胁主要来源于雷达等探测设备。雷达的种类众多且各类雷达的用途与特性各不相同，以对空监视雷达为例建立雷达威胁模型。监视雷达的主要探测目标是飞机，也包含巡航导弹、无人战斗机等目标。监视雷达一般在方位上做360°均匀旋转。雷达具有远距离探测、识别和跟踪目标的功能，它通过接收自身发射的电磁波回波，并进行分析，从而得到有关被探测目标的位置及方向等信息[14]。根据雷达方程可以得到雷达最远作用距离Rmax：
式中：PT为雷达发射机的功率；GR为雷达接收天线增益；GT为雷达发射天线增益；σ为被探测目标的有效雷达散射截面积；λ为雷达信号的工作波长；Smin为最小可检测信号[15]。
由于雷达探测发现目标的概率直接与目标到雷达的距离R有关，所以，可以将发现概率简化为：
由此可以看出，不论是障碍物还是雷达，在进行低空航迹规划时都要满足一定的距离，且战斗机受到的威胁程度与距离的4 次方成反比，因此，可以将安全性的目标函数表示如下：
式中：T表示战斗机受到的总威胁；ti表示第i个威胁的威胁等级；Ri表示目标与威胁物之间的距离。由此，可以确定在最小航迹段长度和目标安全性两个约束条件下的目标函数为：
式中，λ是权重系数。
3 仿真实验
为了验证算法有效性，在Intel Core i5-2450M CPU 2.5 GHz 的PC 机上设计实现了同样威胁环境下的BSO算法和DBBSO 算法的仿真实验，运行环境为Windows 7，实验平台为Matlab，起始点坐标为（0，0），目标点坐标为（20，25），最大迭代次数均为1 000，威胁环境如图3所示，算法运行结果如图4所示，运算时间和航迹长度如表2所示。
图3 威胁环境Fig.3 Threat environment
图4 航迹仿真结果Fig.4 Simulation results of flight paths of different algorithms
由图3和表2可以看出，DBBSO 算法的运行速度慢于BSO 算法，但其规划结果要好，得到的航迹长度也更短，这是因为DBBSO 算法采用基于密度的DBscan 聚类算法，在解决高维函数问题时，寻优能力更强，但是DB-scan 聚类运算过程要比k-means 算法复杂，所以运算时间更长。由于航线规划的目标函数质是一个四维函数，所以DBBSO 算法较BSO 算法解决航线规划问题得到的结果更好。
表2 算法比较Table 2 Comparison of BSO algorithm with DBBSO algorithm
4 结 论
本文针对战斗机低空路径规划问题，调整了传统的头脑风暴优化算法。在转换坐标系的基础上，综合考虑最小航迹段长度和安全性两个因素，建立了数学模型，从而确立了BSO 算法的目标函数。并对传统BSO 算法做出了改进，将传统算法中的k-means 算法替换为基于密度的DBscan 算法。通过在同一威胁环境下的仿真实验结果，可以得出结论，改进后的DBBSO 算法规划效果优于传统BSO 算法，但由于聚类过程花费的时间更长，DBBSO 算法运算时间要比传统BSO 算法更长。作为一种新兴的群体智能优化算法，头脑风暴算法具备很大的潜力，考虑到其独特的聚类结果的特点，不仅仅是航线规划，可以在将来解决更复杂的多目标优化的路径规划问题。
