论文部分内容阅读
[摘要]无人机任务规划技术是无人机遂行飞行任务的关键支撑技术，航迹规划是无人机任务规划的核心和主体。算法是无人机任务规划的数学工具，本文采用比较研究的方式系统研究了算法在无人机任务规划中的作用、规划算法的分类及不同适用范围，重点比较研究了人工神经网络法、人工势场法、蚁群算法、遗传算法的原理和研究情况。
[关键词]无人机任务规划；无人机任务规划算法；航迹规划算法
中图分类号：V279+.2 文献标识码：A 文章编号：1009-914X（2013）06-0155-02
1、无人机任务规划系统
无人机任务规划系统（Unmanned Aerial Vehicle Mission PlanningSystem）是根据地理信息系统（Geographic Information System）和卫星侦察系统（Satellite Reconnaissance System）提供的数字地图数据、敌方防空系统部署情况并结合无人机自身性能参数，利用航迹规划算法为无人作战飞机规划出一条或多条安全系数大、突防概率高、飞行线路或飞行时间短的飞行路线。该系统的输入为一系列地形、威胁等约束条件，输出为从初始点到目标点的一系列的参考航迹点，uAV依次飞过航迹点序列并最大限度地发挥UAV的作用遂行装订在航迹上的侦察、发射等任务，完成从起点到终点的飞行。航迹规划是任务规划的主体和核心组成部分。
2、算法在无人机任务规划中的作用
在防空技术日益先进、防空体系日趋完备的现代数字化战争环境中，任务规划是提高UAV遂行任务性能的有效手段。无人机任务规划是在综合考虑时间、油耗、威胁以及飞行区域等约束的前提下，根据UAV性能载荷及作战任务的不同对无人机进行合理的分配和规划出一条最优或者是满意的飞行航迹，以支持无人机顺利飞行并安全返回，实现耗时、耗油、承受威脅代价最小和UAV种类及数量等资源的实时、动态合理调配，是使任务目标与约束条件相匹配的函数优化问题。
算法是任务规划的核心，是飞行航迹寻优的数学实现途径。算法优劣直接决定任务规划的速度和质量。无人机任务规划算法研究的不断深入推动了无人机任务规划技术朝着实时化、精准化、智能化的方向不断发展进步。
3、无人机任务规划算法的分类
为使任务规划效能最优，学者们先后提出了基于概略图的规划方法、通视图法、Voronoi法、轮廓线法、子目标网络法、随机路标图法、最速下降法、代理法、最优控制法、模拟退火法、动态规划法、电势理论法、启发式算法、遗传算法、蚁群算法、基于合同的方法等一系列算法，又相应的提出了如改进A*搜索法、改进遗传算法等改进算法。根据智能化、自动化程度或适用范围可将规划算法划分为不同的类别。
3.1 按照智能化、自动化程度划分
按照算法的智能化、自动化程度，可将无人机任务规划算法划分为经典任务规划算法和现代任务规划算法。经典任务规划算法主要有最优控制法、导数相关法（牛顿法、梯度法等）、基于概略图的规划方法、通视图法、Voronoi法、轮廓线法、子目标网络法、随机路标图法、最速下降法、代理法、最优控制法、数学规划法、动态规划法等。现代任务规划算法突出了现代计算机技术、数学与计算科学、数字地图等科技的应用，主要有启发式寻优搜索法、人工神经网络法、遗传算法、模拟退火法、专家系统法、蚁群算法、电势理论法、启发式A*搜索法、D*优化算法等。
3.2 按照算法适用范围划分
算法从不同角度构建函数模型和描述、演绎、校验任务规划实施流程，因而不同的规划算法通常有不同的适用范围。按照适用范围将规划算法划分为航迹规划类算法和任务分配规划类算法，而航迹规划类算法又可以分为全局航迹规划类、局部航迹规划类和实时航迹规划类算法。
1）适用UAv航迹规划的算法
VORONOI法～DIJKSTRA搜索算法等几何法比较适用于uAV全局初始航迹的搜索规划，而遗传算法较适用于UAV全局航迹搜索寻优规划，启发式算法、动态规划法、人工势场法等算法较适用于UAV局部航迹规划及实时航迹规划。
2）适用UAv任务分配的算法
整数规划法、蚁群算法、基于合同网的方法及遗传算法等算法适用于多UAV协同任务分配规划。
4、几种常用的任务规划算法的比较研究
人工神经网络算法、蚁群算法、遗传算法是无人机任务规划的常用算法，这些算法各有自身优点和不足，适宜解决问题的范围也各有不同。对算法进行比较研究有利于掌握各种方法的精髓和根据实际情况予以应用。
4.1 人工神经网络法
人工神经网络算法的实质是模拟生物神经网络进行信息处理而对各信息单元构成的拓扑结构的优化。该方法具有高度的并行结构、并行实现能力、高速寻优能力，能够有效发挥计算机的高速运算优势，在无人机任务规划等复杂问题处理方面得到了广泛的应用。经学者长期研究，先后建立了感知器神经网络模型、径向基函数（RBF）神经网络模型、反向传播（BP）神经网络模型、自组织神经网络模型以及Hopfield神经网络模型。其中，Hopfield神经网络模型属于反馈型神经网络模型，适用于处理无人机航迹规划等非线性问题。
Hopfield神经网络法结合能量函数随状态变化单调递减的规律，将能量函数引入人工神经网络，通过寻优能量函数在稳定平衡下的输出等效分析无人机参考飞行航迹，该方法有效地发挥了人工神经网络的收敛性和能量函数趋于稳定状态的特点，同时发挥了Hopfield神经网络法的反馈控制机制，生成的参考航迹具有较好的避障能力和鲁棒性。该算法的实施步骤简述如下：
1）结合规划问题背景对规划空间进行离散化处理并构建与无人机任务规化问题相对应的Hopfield神经网络模型。 2）结合数字地形、障碍物、防空火力及侦测雷达信息及无人机自身约束条件构造能量函数，能量函数需充分体现出不同飞行情况下的网络连接权的变化。连接权随着飞行代价（距离障碍物远近、是否及以何种程度进入雷达侦测区、是否及以何种程度进入雷达侦测区、是否及以何种程度符合飞行半径、燃油限制等UAV自身约束条件等）而变化。
3）对建立的神经网络模型进行模拟，在规划空间则会建立起单峰梯度数值势场并结合势场梯度函数值以及无人机飞行约束条件在规划空间内搜索最优航迹。
4.2 蚁群算法
蚁群算法（Ant Colony Optimization，AC0）是一种用来在图中寻找优化路径的机率型模拟进化算法。它由Marco Dorigo提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。该算法通过个体之间的信息交流与相互协作可实现参考航迹搜索。其基本原理是：蚂蚁通过释放信息素可以影响其他蚂蚁的路径，蚂蚁在初始阶段选择不同路径概率相同，但是由于路径越短在单位时间内通过的蚂蚁数量越多，释放的信息素也就越多，从而随着信息素强度的增大，蚂蚁选择该短路径的概率也就越高，随着时间的推移，这条路径就渐渐发展成为蚂蚁从出发点到目的点的首选路径。正如鲁迅先生所说：“世界上本没有路，走的人多了，也便成了路”，同样，我们可以形象地比喻：其实规划空间中本没有路，走的蚂蚁多了，这条路也就成了它们首选的路。
蚂蚁寻找食物的问题，可归结为在一定搜索空间寻求从出发点到目的点的最优路径问题，与无人机航迹规划——寻求无人机从出发点到目的点的最优参考航迹的问题具有直接模型关联关系。因此，无人机航迹规划问题可以参照蚁群寻食模型予以研究。通过以下步骤可实现基于蚁群算法的无人机航迹规划：
（1）结合威胁、障碍物分布情况构造初始参考路径，在路径起始点设置人工蚂蚁；
（2根据由两点间的可见度以及两点间的信息素值的强度决定的蚂蚁状态转换规则选择下一节点，以此循环持续搜索直至所有蚂蚁到达终点，搜索终结；
（3）搜索得到多条可行航迹并分别计算每条可行航迹的代价（考虑航程代价、飞行威胁代价、自身约束满足情况等），选择代价最小的作为优选参考航迹。
（4）将未经过的各点的航迹点予以人为蒸发，整理规划空间而输出最优参考航迹。
蚁群算法在无人机任务规划研究领域已得到有效应用。国防科技大学的苏菲等通过蚁群算法对多无人机任务分配问题进行了深入研究并提出了基于蚁群分工的优化求解策略；Abbattista F等提出了将遗传算法和蚁群算法有机融合、优势互补的规划策略；Li S H提出了将人工神经网络方法和蚁群算法巧妙融合的灵活规划方法并通过仿真验证了其优越性。
4.3 人工势场法
人工势场法是由Khatib提出的一种虚拟力法，该算法的基本思想是将无人机在周围环境中的运动设计成一种抽象的人造引力场中的运动。将目标点和障碍物赋予两类不同的力的属性，定义目标点对无人机的作用力为“引力”，障碍物对无人机的作用力为“斥力”，通过求无人机在规划环境中受到的合力来控制无人机的运动，使无人机朝着目标点趋近并保证在此过程中不触及威胁和障碍物。
人工势场法在数学描述上简洁、美观，生成参考航迹具有平滑性好、快速性好、安全性好的特点，但对障碍物的规则性有较高要求，否则算法的计算量将很大，有时甚至是无法计算的。目前，人工势场法较多应用于航迹的平滑处理、偶遇障碍物特情的实时航迹规化及障碍物规则分布的局部航迹规划。结合算法特点，人工势场法与遗传算法、蚁群算法的有机融合也成为有效的研究方法。西北工业大学的屈耀红等通过分析不同强度威胁源构成的飞行环境，将人工势场法与遗传算法相结合，实现了无人机全局航迹规划及仿真；北京科技大学的李擎等针对传统人工势场法在航迹规划中的一类目标点不可达问题提出了一种基于遗传算法参数优化的改进人工势场法实现了威胁回避并规划出长度短且光滑的参考航迹。
4.4 遗传算法
遗传算法由美国密歇根大学的Holland等人提出，起源于仿照生物系统自然进化的计算机人工智能模拟研究。算法的基本原理是在构建评价函数、给出描述问题的基本参数后，将需要优化的问题的参数进行编码，经过模拟自然选择操作而选定初始群体后，进行交叉和变异的遗传运算，经过多次重复迭代直至得到比较理想的优化结果，整个算法实施的过程实质上是模拟自然界中基因重组与进化的过程，是模拟自然界优胜劣汰的竞争机制的寻优过程，是基于概率选择的群体进化计算过程。
遗传算法是一种搜索优化算法，它先创建基于问题的染色体个体并通过模拟自然选择操作形成种群，再通过适应度函数（目标函数或评价函数）计算染色体个体的适应性，对优者进行复制，通过交叉和突变操作改良后代品质。其中，交叉操作（单点交叉或多点交叉）是指相互交换2个单个染色体的一部分，而突变操作是指改变染色体上某个随机基因座上的基因值。将染色体（个体）的评价值等效为概率这一标量，再通过排序选择方法或者轮盘赌概率选择机制将适应性较弱的染色体淘汰。适应性较强的染色体逐渐主导了种群，最终使种群整体适应性得以提升，再从得到优化的新一代群体中比较选出其中最優个体作为理想解输出，得到的理想解答不一定是实际的最优解，但一定是近似最优解，一般可以满足优化搜索的需要，而且经遗传算法优化搜索可以同时得到一个相对最优解和多个较优解，可以满足系统多输入——多输出的要求，是遗传算法并行计算优质品质的直接体现。通过遗传算法进行问题解的优化搜索的主要方面可归纳为：
1）对拟优化问题进行基因编码，即在搜索开始之前结合问题属性对无人机位置及航迹可行性进行编码；
2）生成初始种群，即在规划空间内随机产生若干（群体大小数）个个体（染色体或串接数据），每个个体等效为一条规划航迹，每个个体由若干基因组成，等效为条规划航迹由若干航迹点组成。 3）构建评价染色体性能的适应度函数（评价函数或者目标函数）、有利于种群进化的三种遗传算子——“选择算子”、“交叉算子”、“变异算子”，从而构建有利于种群进化的数学模态；
4）参照自然界进化模式对问题模型进行合理“选择”、“交叉”、“变异”等遗传操作。
5）按照遗传算子对群体进行多代迭代计算后，在达到进化指标或及进化代数要求后输出一个或多个最优个体，将最优个体解码得到最优参考航迹。
遗传算法对所求解问题的具体细节要求不高，不要求建立描述问题的具体解析规则，具有较好的适用性、鲁棒性，该方法不要求规划空间满足连续性、导数存在和单峰等条件，其内在的种群进化策略能够很好地发挥计算机并行计算的优势，具有智能性、自适应搜索、基于概率选择的渐进式寻优、并行计算等优点，是一种具有很强的通用性、鲁棒性、全局最优性，可用于求解一系列其他方法难以解决的复杂问题。作为一种全局优化算法和搜索算法，一般可以很快地收敛到最优解附近，如果要求更精确地解，可将遗传算法与其他方法结合起来，提高解的质量。
清华大学的郑锐等通过采取保优选择策略和改进编码方式并改进交叉算子，对基本遗传算法作了改进，实现了全局选优且避免局部最优、快速收敛、高精度寻优的航迹规划；空军工程大学的鲁艺等针对实际作战环境的任务规划需要，提出了能够满足uAV机动要求的基于改进遗传算法的UAV高效航迹规化算法；西北工业大学的王景针对遗传算法易陷入局部最优的缺点和减小航迹随机搜索计算量，创新性地提出了限定搜索区域的分层遗传算法，提高了航迹寻优效率并有效地缩短了规划航迹长度；北京航空航天大学的文泾等通过将链接图法、最短路径法、遗传算法相结合，实现了高质量的任务规划并仿真验证。遗传算法渐已发展成为无人机航迹规划领域的主流研究方法。
通过上述研究情况可以看出，人工神经网络法、蚁群算法、人工势场法、遗传算法各有其比较适用范围，其中人工神经网络法适于约束具体化的局部寻优计算，蚁群算法具有并行性好、能與特定分工模型匹配的优势，人工势场法具有建模简单、快速性好、平滑性好、安全性好的特点适用于动态实时规划，遗传算法基于内在的概率选择机制、并行计算机制、按目标函数择优机制，适用于大规模规划区域的全局规划和用于任务分配问题的寻优，是当前任务规划领域的主流研究方法。
5、无人机任务规划算法研究的发展趋势
无人机任务规划技术是无人机遂行飞行任务的关键支撑技术之一，可有效支持无人机实施航迹规划、低空突防、多机协同飞行。规划算法是无人机任务规划系统的灵魂和内驱力，是通过数学手段和计算机等现代化工程技术实现无人机智能飞行的途径。本文系统论述了无人机任务规划的相关研究算法，对常用算法进行了比较研究，明确了遗传算法是无人机任务规划研究领域的主流算法。
[关键词]无人机任务规划；无人机任务规划算法；航迹规划算法
中图分类号：V279+.2 文献标识码：A 文章编号：1009-914X（2013）06-0155-02
1、无人机任务规划系统
无人机任务规划系统（Unmanned Aerial Vehicle Mission PlanningSystem）是根据地理信息系统（Geographic Information System）和卫星侦察系统（Satellite Reconnaissance System）提供的数字地图数据、敌方防空系统部署情况并结合无人机自身性能参数，利用航迹规划算法为无人作战飞机规划出一条或多条安全系数大、突防概率高、飞行线路或飞行时间短的飞行路线。该系统的输入为一系列地形、威胁等约束条件，输出为从初始点到目标点的一系列的参考航迹点，uAV依次飞过航迹点序列并最大限度地发挥UAV的作用遂行装订在航迹上的侦察、发射等任务，完成从起点到终点的飞行。航迹规划是任务规划的主体和核心组成部分。
2、算法在无人机任务规划中的作用
在防空技术日益先进、防空体系日趋完备的现代数字化战争环境中，任务规划是提高UAV遂行任务性能的有效手段。无人机任务规划是在综合考虑时间、油耗、威胁以及飞行区域等约束的前提下，根据UAV性能载荷及作战任务的不同对无人机进行合理的分配和规划出一条最优或者是满意的飞行航迹，以支持无人机顺利飞行并安全返回，实现耗时、耗油、承受威脅代价最小和UAV种类及数量等资源的实时、动态合理调配，是使任务目标与约束条件相匹配的函数优化问题。
算法是任务规划的核心，是飞行航迹寻优的数学实现途径。算法优劣直接决定任务规划的速度和质量。无人机任务规划算法研究的不断深入推动了无人机任务规划技术朝着实时化、精准化、智能化的方向不断发展进步。
3、无人机任务规划算法的分类
为使任务规划效能最优，学者们先后提出了基于概略图的规划方法、通视图法、Voronoi法、轮廓线法、子目标网络法、随机路标图法、最速下降法、代理法、最优控制法、模拟退火法、动态规划法、电势理论法、启发式算法、遗传算法、蚁群算法、基于合同的方法等一系列算法，又相应的提出了如改进A*搜索法、改进遗传算法等改进算法。根据智能化、自动化程度或适用范围可将规划算法划分为不同的类别。
3.1 按照智能化、自动化程度划分
按照算法的智能化、自动化程度，可将无人机任务规划算法划分为经典任务规划算法和现代任务规划算法。经典任务规划算法主要有最优控制法、导数相关法（牛顿法、梯度法等）、基于概略图的规划方法、通视图法、Voronoi法、轮廓线法、子目标网络法、随机路标图法、最速下降法、代理法、最优控制法、数学规划法、动态规划法等。现代任务规划算法突出了现代计算机技术、数学与计算科学、数字地图等科技的应用，主要有启发式寻优搜索法、人工神经网络法、遗传算法、模拟退火法、专家系统法、蚁群算法、电势理论法、启发式A*搜索法、D*优化算法等。
3.2 按照算法适用范围划分
算法从不同角度构建函数模型和描述、演绎、校验任务规划实施流程，因而不同的规划算法通常有不同的适用范围。按照适用范围将规划算法划分为航迹规划类算法和任务分配规划类算法，而航迹规划类算法又可以分为全局航迹规划类、局部航迹规划类和实时航迹规划类算法。
1）适用UAv航迹规划的算法
VORONOI法～DIJKSTRA搜索算法等几何法比较适用于uAV全局初始航迹的搜索规划，而遗传算法较适用于UAV全局航迹搜索寻优规划，启发式算法、动态规划法、人工势场法等算法较适用于UAV局部航迹规划及实时航迹规划。
2）适用UAv任务分配的算法
整数规划法、蚁群算法、基于合同网的方法及遗传算法等算法适用于多UAV协同任务分配规划。
4、几种常用的任务规划算法的比较研究
人工神经网络算法、蚁群算法、遗传算法是无人机任务规划的常用算法，这些算法各有自身优点和不足，适宜解决问题的范围也各有不同。对算法进行比较研究有利于掌握各种方法的精髓和根据实际情况予以应用。
4.1 人工神经网络法
人工神经网络算法的实质是模拟生物神经网络进行信息处理而对各信息单元构成的拓扑结构的优化。该方法具有高度的并行结构、并行实现能力、高速寻优能力，能够有效发挥计算机的高速运算优势，在无人机任务规划等复杂问题处理方面得到了广泛的应用。经学者长期研究，先后建立了感知器神经网络模型、径向基函数（RBF）神经网络模型、反向传播（BP）神经网络模型、自组织神经网络模型以及Hopfield神经网络模型。其中，Hopfield神经网络模型属于反馈型神经网络模型，适用于处理无人机航迹规划等非线性问题。
Hopfield神经网络法结合能量函数随状态变化单调递减的规律，将能量函数引入人工神经网络，通过寻优能量函数在稳定平衡下的输出等效分析无人机参考飞行航迹，该方法有效地发挥了人工神经网络的收敛性和能量函数趋于稳定状态的特点，同时发挥了Hopfield神经网络法的反馈控制机制，生成的参考航迹具有较好的避障能力和鲁棒性。该算法的实施步骤简述如下：
1）结合规划问题背景对规划空间进行离散化处理并构建与无人机任务规化问题相对应的Hopfield神经网络模型。 2）结合数字地形、障碍物、防空火力及侦测雷达信息及无人机自身约束条件构造能量函数，能量函数需充分体现出不同飞行情况下的网络连接权的变化。连接权随着飞行代价（距离障碍物远近、是否及以何种程度进入雷达侦测区、是否及以何种程度进入雷达侦测区、是否及以何种程度符合飞行半径、燃油限制等UAV自身约束条件等）而变化。
3）对建立的神经网络模型进行模拟，在规划空间则会建立起单峰梯度数值势场并结合势场梯度函数值以及无人机飞行约束条件在规划空间内搜索最优航迹。
4.2 蚁群算法
蚁群算法（Ant Colony Optimization，AC0）是一种用来在图中寻找优化路径的机率型模拟进化算法。它由Marco Dorigo提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。该算法通过个体之间的信息交流与相互协作可实现参考航迹搜索。其基本原理是：蚂蚁通过释放信息素可以影响其他蚂蚁的路径，蚂蚁在初始阶段选择不同路径概率相同，但是由于路径越短在单位时间内通过的蚂蚁数量越多，释放的信息素也就越多，从而随着信息素强度的增大，蚂蚁选择该短路径的概率也就越高，随着时间的推移，这条路径就渐渐发展成为蚂蚁从出发点到目的点的首选路径。正如鲁迅先生所说：“世界上本没有路，走的人多了，也便成了路”，同样，我们可以形象地比喻：其实规划空间中本没有路，走的蚂蚁多了，这条路也就成了它们首选的路。
蚂蚁寻找食物的问题，可归结为在一定搜索空间寻求从出发点到目的点的最优路径问题，与无人机航迹规划——寻求无人机从出发点到目的点的最优参考航迹的问题具有直接模型关联关系。因此，无人机航迹规划问题可以参照蚁群寻食模型予以研究。通过以下步骤可实现基于蚁群算法的无人机航迹规划：
（1）结合威胁、障碍物分布情况构造初始参考路径，在路径起始点设置人工蚂蚁；
（2根据由两点间的可见度以及两点间的信息素值的强度决定的蚂蚁状态转换规则选择下一节点，以此循环持续搜索直至所有蚂蚁到达终点，搜索终结；
（3）搜索得到多条可行航迹并分别计算每条可行航迹的代价（考虑航程代价、飞行威胁代价、自身约束满足情况等），选择代价最小的作为优选参考航迹。
（4）将未经过的各点的航迹点予以人为蒸发，整理规划空间而输出最优参考航迹。
蚁群算法在无人机任务规划研究领域已得到有效应用。国防科技大学的苏菲等通过蚁群算法对多无人机任务分配问题进行了深入研究并提出了基于蚁群分工的优化求解策略；Abbattista F等提出了将遗传算法和蚁群算法有机融合、优势互补的规划策略；Li S H提出了将人工神经网络方法和蚁群算法巧妙融合的灵活规划方法并通过仿真验证了其优越性。
4.3 人工势场法
人工势场法是由Khatib提出的一种虚拟力法，该算法的基本思想是将无人机在周围环境中的运动设计成一种抽象的人造引力场中的运动。将目标点和障碍物赋予两类不同的力的属性，定义目标点对无人机的作用力为“引力”，障碍物对无人机的作用力为“斥力”，通过求无人机在规划环境中受到的合力来控制无人机的运动，使无人机朝着目标点趋近并保证在此过程中不触及威胁和障碍物。
人工势场法在数学描述上简洁、美观，生成参考航迹具有平滑性好、快速性好、安全性好的特点，但对障碍物的规则性有较高要求，否则算法的计算量将很大，有时甚至是无法计算的。目前，人工势场法较多应用于航迹的平滑处理、偶遇障碍物特情的实时航迹规化及障碍物规则分布的局部航迹规划。结合算法特点，人工势场法与遗传算法、蚁群算法的有机融合也成为有效的研究方法。西北工业大学的屈耀红等通过分析不同强度威胁源构成的飞行环境，将人工势场法与遗传算法相结合，实现了无人机全局航迹规划及仿真；北京科技大学的李擎等针对传统人工势场法在航迹规划中的一类目标点不可达问题提出了一种基于遗传算法参数优化的改进人工势场法实现了威胁回避并规划出长度短且光滑的参考航迹。
4.4 遗传算法
遗传算法由美国密歇根大学的Holland等人提出，起源于仿照生物系统自然进化的计算机人工智能模拟研究。算法的基本原理是在构建评价函数、给出描述问题的基本参数后，将需要优化的问题的参数进行编码，经过模拟自然选择操作而选定初始群体后，进行交叉和变异的遗传运算，经过多次重复迭代直至得到比较理想的优化结果，整个算法实施的过程实质上是模拟自然界中基因重组与进化的过程，是模拟自然界优胜劣汰的竞争机制的寻优过程，是基于概率选择的群体进化计算过程。
遗传算法是一种搜索优化算法，它先创建基于问题的染色体个体并通过模拟自然选择操作形成种群，再通过适应度函数（目标函数或评价函数）计算染色体个体的适应性，对优者进行复制，通过交叉和突变操作改良后代品质。其中，交叉操作（单点交叉或多点交叉）是指相互交换2个单个染色体的一部分，而突变操作是指改变染色体上某个随机基因座上的基因值。将染色体（个体）的评价值等效为概率这一标量，再通过排序选择方法或者轮盘赌概率选择机制将适应性较弱的染色体淘汰。适应性较强的染色体逐渐主导了种群，最终使种群整体适应性得以提升，再从得到优化的新一代群体中比较选出其中最優个体作为理想解输出，得到的理想解答不一定是实际的最优解，但一定是近似最优解，一般可以满足优化搜索的需要，而且经遗传算法优化搜索可以同时得到一个相对最优解和多个较优解，可以满足系统多输入——多输出的要求，是遗传算法并行计算优质品质的直接体现。通过遗传算法进行问题解的优化搜索的主要方面可归纳为：
1）对拟优化问题进行基因编码，即在搜索开始之前结合问题属性对无人机位置及航迹可行性进行编码；
2）生成初始种群，即在规划空间内随机产生若干（群体大小数）个个体（染色体或串接数据），每个个体等效为一条规划航迹，每个个体由若干基因组成，等效为条规划航迹由若干航迹点组成。 3）构建评价染色体性能的适应度函数（评价函数或者目标函数）、有利于种群进化的三种遗传算子——“选择算子”、“交叉算子”、“变异算子”，从而构建有利于种群进化的数学模态；
4）参照自然界进化模式对问题模型进行合理“选择”、“交叉”、“变异”等遗传操作。
5）按照遗传算子对群体进行多代迭代计算后，在达到进化指标或及进化代数要求后输出一个或多个最优个体，将最优个体解码得到最优参考航迹。
遗传算法对所求解问题的具体细节要求不高，不要求建立描述问题的具体解析规则，具有较好的适用性、鲁棒性，该方法不要求规划空间满足连续性、导数存在和单峰等条件，其内在的种群进化策略能够很好地发挥计算机并行计算的优势，具有智能性、自适应搜索、基于概率选择的渐进式寻优、并行计算等优点，是一种具有很强的通用性、鲁棒性、全局最优性，可用于求解一系列其他方法难以解决的复杂问题。作为一种全局优化算法和搜索算法，一般可以很快地收敛到最优解附近，如果要求更精确地解，可将遗传算法与其他方法结合起来，提高解的质量。
清华大学的郑锐等通过采取保优选择策略和改进编码方式并改进交叉算子，对基本遗传算法作了改进，实现了全局选优且避免局部最优、快速收敛、高精度寻优的航迹规划；空军工程大学的鲁艺等针对实际作战环境的任务规划需要，提出了能够满足uAV机动要求的基于改进遗传算法的UAV高效航迹规化算法；西北工业大学的王景针对遗传算法易陷入局部最优的缺点和减小航迹随机搜索计算量，创新性地提出了限定搜索区域的分层遗传算法，提高了航迹寻优效率并有效地缩短了规划航迹长度；北京航空航天大学的文泾等通过将链接图法、最短路径法、遗传算法相结合，实现了高质量的任务规划并仿真验证。遗传算法渐已发展成为无人机航迹规划领域的主流研究方法。
通过上述研究情况可以看出，人工神经网络法、蚁群算法、人工势场法、遗传算法各有其比较适用范围，其中人工神经网络法适于约束具体化的局部寻优计算，蚁群算法具有并行性好、能與特定分工模型匹配的优势，人工势场法具有建模简单、快速性好、平滑性好、安全性好的特点适用于动态实时规划，遗传算法基于内在的概率选择机制、并行计算机制、按目标函数择优机制，适用于大规模规划区域的全局规划和用于任务分配问题的寻优，是当前任务规划领域的主流研究方法。
5、无人机任务规划算法研究的发展趋势
无人机任务规划技术是无人机遂行飞行任务的关键支撑技术之一，可有效支持无人机实施航迹规划、低空突防、多机协同飞行。规划算法是无人机任务规划系统的灵魂和内驱力，是通过数学手段和计算机等现代化工程技术实现无人机智能飞行的途径。本文系统论述了无人机任务规划的相关研究算法，对常用算法进行了比较研究，明确了遗传算法是无人机任务规划研究领域的主流算法。