一种改进遗传算法在UCAV快速航迹规划中的应用*

顾潮琪，周德云

（西北工业大学电子信息学院，西安710129）

一种改进遗传算法在UCAV快速航迹规划中的应用*

顾潮琪，周德云

（西北工业大学电子信息学院，西安710129）

针对无人作战飞机（Unmanned Combat Aerial Vehicle，UCAV）航迹规划约束条件复杂、不确定因素多、实时性要求高的特点，提出了一种基于Voronoi图和改进遗传算法的快速航迹规划方法。该方法采取分层航迹规划的思想，首先根据Voronoi图生成初始航迹，并综合考虑约束条件，赋予各条航迹相应的权值；然后应用改进的遗传算法在生成的航迹空间中寻优，最终得到满意的航迹。该算法利用多处理机并行计算技术对传统遗传算法进行改进，大大缩短寻优时间。仿真结果表明基于Voronoi图和改进遗传算法的航迹规划提高了实时性，增强了UCAV的动态战场适应能力和突发威胁应对能力。

无人作战飞机，改进遗传算法，Voronoi图，航迹规划，实时性

0 引言

在防空技术日益先进且防空体系日益完善的现代战争环境中，航迹规划是提高UCAV作战效能、实施远程精确打击的有效手段［1］。其核心内容就是在任务空间内找到一条能够到达指定区域的飞行航线，在满足相关约束前提下使某种性能指标最优［2］。当UCAV在作战过程中遇到突发威胁，或需要攻击时间敏感性目标时，时间作为一个不可忽视的因素越来越受到人们的关注和重视，快速航迹规划已成为提高飞行器环境适应性和生存能力的重要方法。传统求解方法如动态规划法、Dijkstra算法、A*算法等需要对规划空间进行全面搜索，并行计算效果差，存在组合爆炸的问题；而智能规划算法如模拟退火算法［3］、遗传算法（Genetic Algorithm，GA）［4］、神经网络［5］以及群智能算法中的蚁群算法［6］、粒子群算法［7］等无法适应优化目标的动态变化，并且计算时间长，多用于离线寻优。

因此，本文提出了一种能进行动态决策的改进遗传算法（Improved Genetic Algorithm，IGA），该算法是在传统遗传算法的基础上，借助于并行计算技术，在确定优化目标（决策）期间对可能的多个优化目标函数的优良个体进行培养，一旦优化目标确定后就能根据预先培养的优良个体进行快速寻优，使遗传算法具有动态性能，能够适应优化目标的动态变化，提高寻优的实时性。

1 基于Voronoi图的战场空间构建

1.1 初始航迹集合

Voronoi图是计算几何学中的一种重要几何结构，它应用在航迹规划中的最大特点是能够根据已知战场威胁源分布情况建立规划空间模型并生成初始可选航迹集合［8］。根据Voronoi图的性质，UCAV沿着Voronoi边进行飞行将获得最大的安全性。如果任意加入一个威胁点，也只影响该点邻近威胁点所组成的多边形内Voronoi图的构造，不影响该多边形以外Voronoi图的重新构造。因此，Voronoi图适用于战场环境变化情况下UCAV局部航迹重规划，如突发威胁体下航迹重规划的情况。

基于构建的战场环境Voronoi图，UCAV的初始航迹集合可以表示为：Voronoi图的顶点为航迹中途点，边为航迹段，从UCAV起始点到目标点的Voronoi图边的组合构成许多条航迹。从这些组合中选择从UCAV起始点到目标点的n条航迹，构成UCAV的初始航迹集合。

1.2 航迹代价计算

UCAV航迹规划通常考虑的约束条件有［9］：①威胁因素；②航迹长度约束；③UCAV的机动能力；④最小航迹段长度；⑤飞行高度限制。因此，本文UCAV的航迹代价包括威胁代价Jthreat、燃油代价Jfuel、最大拐弯角代价Jangle和最小航迹段代价Jlength。各种代价的计算公式如下：

综合考虑上述威胁代价、燃油代价、最大拐弯角代价和最小航迹段代价之后，可以得到UCAV航迹规划的最小性能指标为：

其中k1、k2、k3和k4为权衡系数且k1+k2+k3+k4=1，取4个代价之间一个折衷的数，加权的大小取决于权项的重要性和可行性的综合指标，本文采用层次分析法确定航迹代价函数中的权系数。

2 基于改进遗传算法的航迹规划

2.1 改进遗传算法

改进遗传算法的设计思想借鉴了多处理机并行处理技术［10-11］，在一台处理机做决策时，用另外一台处理机对所有可能的目标进行预先进化，培养每一个可能的优化目标函数的优良个体。一旦决策做出，种群内部就已经包含着对所有目标函数（决策）的，非常接近于最优解的优良个体。在此基础上进行具体目标函数的寻优，则可以大大缩短寻优时间，提高实时性，并且可以使遗传算法能够适应优化目标的动态变化。

根据上述设计思想，改进遗传算法的关键在于进化过程中对各个目标的优良个体进行保留，如果有n个可能的目标函数，则只要一个个体对某一个函数较优，就可保留。假定有n个候选的目标函数，可以根据先验知识选择一个作为主目标函数，例如f1，而f2……fn作为隐含目标函数。当前种群中的个体对每一个目标函数都有目标函数值，在f1进化时，通过正常的选择、交叉和变异操作形成新个体集合。新个体对每一个目标函数也有不同的适应度和函数值，在用新个体替换原来种群中的部分个体时，就不能仅仅按照对f1的适应度来考虑，还要考虑其对所有目标函数的适应度。因此，需要替换掉那些对所有函数都不优的个体，而不仅仅是替换掉所有对f1不优的个体。对此，设置一个综合适应度，它是个体对各个目标函数适应度的加权。

2.2 适应度函数设计

基于改进遗传算法航迹规划的关键在于适应度函数的设计，通过对约束条件的处理即进化过称中采用并行计算技术对UCAV航迹规划的各种代价函数进行计算以形成综合适应度，一旦战场环境发生变化，可以通过调整代价函数而形成新的综合适应度来满足需求。

对于单条UCAV航迹，可将式（5）作为其适应度函数，并且假定威胁代价值最小、燃油代价值最小、最大拐弯角代价最小和最小航迹段代价最小为4个可能的目标函数，即：

根据作战经验，规避威胁是UCAV对地打击过程中需要首先考虑的，因此，将f1作为主目标函数，f2，f3和f4作为隐含目标函数。进化过程中，在f1寻优时保留对f2，f3和f4较优的个体于种群之中，培养每一个可能寻优的目标函数的优良个体，这样一旦优化目标发生变化，如出现突发威胁时，通过调整加权系数使综合适应度发生变化，在此种群基础上对新的综合适应度的寻优能够很快收敛。

2.3 基于改进遗传算法的航迹搜索流程

同传统遗传算法的航迹搜索流程一样，只是改进的遗传算法在进化过程中对适应度函数的确定是一个动态变化的过程，因此，基于Voronoi图模型与改进遗传算法的UCAV快速航迹搜索流程图如图1所示。

图1 基于改进遗传算法的航迹搜索流程

3 仿真实验及结果分析

仿真采用双线程方式，第1个线程实时地接受战场环境信息，确定综合适应度函数；第2个线程则进行预先进化操作，对航迹威胁、燃油、最大拐弯角、最小航迹段代价培养优良个体。一旦综合适应度函数确定，根据遗传算法获得最优解。

（1）实验1：静态环境下的航迹规划

在本组实验中，根据预先设定的威胁源建立战场空间Voronoi图并生成初始化航迹，如图3所示。然后采用IGA和GA进行航迹搜索，在分别循环60次和61次后得到的最优航迹如图4所示。从图中可以看出，两种算法都可以搜索到最优航迹并且规划结果相同。

图2 IGA和GA的初始化航迹

图3 IGA和GA的最优化航迹

图4是IGA与GA综合适应度随进化代数的变化曲线，由于在本次实验中未出现新的威胁，综合适应度函数没发生变化，因此，两种算法的综合适应度变化过程基本相两种算法的计算过程相同。

图4 IGA与GA综合适应度变化曲线

图5 突发威胁下的最优化航迹

（2）实验2：突发威胁情况下的航迹规划

在本组实验过程中，突发威胁出现在坐标的位置，其他参数与实验一设置相同。图5给出了突发威胁情况下基于IGA和GA的最优化航迹，两种算法的规划结果仍然相同。

两种算法在规划过程中对突发威胁的处理方式是不同的。当出现突发威胁时，引起局部Voronoi图重构，由于GA在搜索航迹过程中，事先已经确定好适应度函数，先前通过遗传进化产生的种群中只有较少部分个体能适应这一变化，影响最终规划结果，甚至无法获得最优航迹。因此，GA需要重新进行初始航迹生成并进行航迹搜索，这样会造成大量的时间消耗。而基于IGA的航迹规划在搜索过程中保留了对所有可能目标函数的最优个体，当出现突发威胁后，通过调整所有可能目标函数的加权系数，形成新的综合适应度以满足优化目标要求。综合适应度随进化代数的变化曲线如图6所示，表1给出了突发威胁情况下两种算法航迹规划的部分实验数据。

图6 突发威胁下的综合适应度变化曲线

表1 突发威胁下基于IGA和GA的航迹规划部分实验数据

从图6和表1可以看出，威胁出现前，两种算法计算过程类似，综合适应度的变化趋势一致，进化代数和所需时间基本相同。第22代，出现了突发威胁，基于IGA的航迹规划调整综合适应度函数，又经过45次迭代搜索到最优航迹，总的进化代数和时间与实验一基本相同，可见突发威胁对利用IGA进行的航迹规划影响不大；而传统遗传算法需重新生成初始航迹并进行搜索，综合适应度变化剧烈，经过83代才重新搜索到最优航迹，与基于IGA的航迹规划相比，进化代数增加了38代，所需时间也增加了将近1 s。由于突发威胁无法预知，这要求航迹规划算法必须能够迅速更新环境信息，同时还要在指定时间内得出较为满意的规划结果，而基于IGA的航迹规划通过调整综合适应度函数，提高了航迹搜索的快速性。

4 结束语

本文根据分层航迹规划的思想，将一种改进的遗传算法应用到UCAV的快速航迹规划中。在深入分析了UCAV航迹规划的约束条件和战场环境基础上，利用Voronoi图的拓扑特性，建立了基于Voronoi图航迹规划空间模型；并在计算航迹代价时，全面考虑了威胁代价、燃油代价、最大拐弯角代价以及最小航迹段代价。而改进的遗传算法通过预先进化策略对遗传算法进行改进，即通过多处理机并行计算技术，在确定优化目标的过程中先进行预先进化，培养每一个可能寻优的目标函数的优良个体，在优化目标确定之后进行快速寻优，使其能够在目标函数是动态确定的情况下使用。因此，该方法运用在UCAV航迹规划中保证了实时性，实现了环境改变时，优化目标就改变并快速寻优的进化。

［1］王俊，周树道，朱国涛，等.无人机航迹规划常用算法［J］.火力与指挥控制，2012，37（8）:5-8.

［2］Wang Y Y，Wei T T，Qu X J.Study of Multi-objective Fuzzy Optimization for Path Planning［J］.Chinese Journal of Aeronautics，2012，25（4）:51-56.

［3］Tavares R S，Martins T C，Tsuzuki M S G.Simulated Annealing with Adaptive Neighborhood:A Case Study in Off-line Robot Path Planning［J］.Expert Systems with Applications，2011，38（4）:2951-2965.

［4］严江江，丁明跃，周成平.基于K均值聚类和遗传算法的多航迹规划方法［J］.火力与指挥控制，2010，35（3）: 147-150.

［5］Howard L，Simon X Y，Yevgen B.Neural Network Based Path Planning for A Multi-Robot System with Moving Obstacles［C］//The 4th IEEE Conference on Automation Science and Engineering，Washington DC，2008.

［6］Chen M，Wu Q X，Jiang C H.A Modify Ant Optimization Algorithm for Path Planning of UCAV［J］.Applied Soft Computing Journal，2008，8（4）:1712-1718.

［7］Foo J L，Knutzon J S，Oliver J H.Three-Dimensional Multi-Objective Path Planning of Unmanned Aerial Vehicles Using Particle Swarm Optimization［C］//AIAA 2007-1881.

［8］李华超，吴潜，陈春俊.VORONOI图的无人机航路快速初始规划［J］.火力与指挥控制，2009，34（1）:79-81.

［9］Yan P，Ding M Y，Zheng C W.Coordinated Route Planning via Nash Equilibrium and Evolutionary Computation［J］. Chinese Journal of Aeronautics，2006，19（1）:18-23.

［10］李少华，魏海光，周成平，等.一种海上无人飞行器的快速航迹规划方法［J］.四川兵工学报，2011，32（12）: 73-76.

［11］史建国，高晓光，李相民.“预先”进化遗传算法研究［J］.宇航学报，2005，26（2）:168-173.

Application of an Improved Genetic Algorithm in Fast Path Planning for UCAV

GU Chao-qi，ZHOU De-yun
（School of Electronic Information，Northwestern Polytechnical University，Xi’an 710129，China）

Due to the complex constraints，more uncertain factors and critical real-time demand of path planning for UCAV，an approach of fast path planning based on Voronoi diagram and improved genetic algorithm is proposed，which makes use of the principle of hierarchical path planning.First the Voronoi diagram is utilized to generate the initial paths and calculate the weight of the paths by considering the constraints.Then the optimal path is searched by using the improved genetic algorithm. Multiprocessors parallel computing techniques are used to improve the traditional genetic algorithm and the optimal time is greatly reduced.Simulation results verify that path planning based on Voronoi diagram and IGA is more favorable in the real-time operation.It can improve the adaptability of dynamic battlefield and unexpected threats for UCAV.

unmanned combat aerial vehicle，improved genetic algorithm，Voronoi diagram，path planning，real-time

TP391.9

A

1002-0640（2015）02-0070-04

2013-12-08

2014-01-24

航空科学基金（20115553021）；西北工业大学基础研究基金资助项目（JC20110222）

顾潮琪（1979-），男，浙江金华人，博士生。研究方向：航空火力与指挥控制，先进综合控制理论及应用。