模拟退火算法是基于蒙特卡罗迭代求解法的一种启发式随机搜索算法。它模拟固体物质的退火过程, 在某一初始温度下, 伴随温度控制参数按照降温函数不断下降, 结合概率的突跳特性在解空间中随机寻找目标函数的全局最优解, 即能概率性地跳出局部最优解并最终趋于全局最优解。退火过程由冷却进度表(Cooling Schedule)控制, 包括温度控制参数的初值t及其衰减因子Δ t、 每个t值时的迭代次数和终止条件。模拟退火算法的优点是算法求得的解与初始解状态无关, 具有渐近收敛性, 是一种以概率1收敛于全局最优解的全局优化算法。缺点是解的质量依赖于当前解产生新解的变换方法和冷却进度表的设计。在航迹规划中, 模拟退火算法的一个解代表一条航迹, 目标函数则是代价函数, 常用于求解二维航迹规划中的TSP问题[20] , 但该算法多数没有考虑无人机的机动性能约束, 得到的航迹可飞性不高。模拟退火算法也可与易陷入局部最优解的算法相结合帮助其跳出局部最优找到全局最优解, 如遗传模拟退火算法[21] , 在交叉和变异过程中使用Metropolis准则判断是否接受新解, 当然, 这会增大原算法的计算量。
2.2 现代智能算法
相较于传统经典算法, 现代智能算法的应用更为广泛。在航迹规划中常用的现代智能算法有A*算法、 遗传算法(GA：Genetic Algorithm)、 蚁群优化(ACO：Ant Colony Optimization)算法和粒子群优化(PSO：Particle Swarm Optimization)算法。
A*算法是一种智能启发式搜索算法, 它将搜索空间表示为网格的形式, 以网格的中心点或顶点作为航迹点, 通过搜索邻域内代价函数值最小的航迹点, 从起始点逐步搜索到目标点, 最后逆向回溯当前节点的父节点生成最优航迹, 其中待扩展航迹节点存放在OPEN表中, 已扩展节点存放在CLOSE表中。代价函数的表达式如下所示
f(x)=g(x)+h(x)(8)
其中g(x)表示从起始点到当前节点的实际代价, h(x)称为启发函数, 表示从当前节点到目标点的估算代价, 常用的启发函数可选用欧氏距离、 曼哈顿距离、 对角线距离等。启发函数是A*算法的核心, 它能在搜索效率和最优解之间权衡。若h(x)小于从当前节点到目标点的实际代价, 则搜索得到最优路径, 但这时搜索节点增多, 搜索效率降低；若h(x)一直等于从当前节点到目标点的实际代价, 此时A*严格按照最优路径搜索, 搜索效率最高；若h(x)大于从当前节点到目标点的实际代价, 则搜索结果可能不是最优路径, 但搜索效率会提高。此外, OPEN表的维护方式也会影响A*算法的搜索效率, 当路径很长时, 这种影响会更明显。总之, 启发函数的选择决定了A*算法是否能找到最优解, OPEN表的维护方式和搜索节点数量决定了A*算法的运行速度。随着搜索空间增大, A*算法的计算量会呈指数增长, 导致规划时间过长, 一般用于静态航迹规划。在航迹规划中, 如何提高A*算法的运行速度并得到最优航迹是学者们重点考虑的问题。文献[7] 采用结构体式最小二叉堆和三层嵌套的二叉堆技术分别维护管理OPEN表和CLOSE表, 相比较于传统的数组式最小二叉堆维护OPEN表和单向链表管理CLOSE表的方式, 提高了最优节点的提取速度, 克服了数组二叉堆的容量可能导致OPEN表溢出的问题, 有效解决了动态二叉树易出现的极度不平衡问题, 保证了节点查找的高效率, 较大幅度提高了A*算法的规划效率。文献[22] 提出使用2.5维网格模型描述三维规划空间, 每个网格点包含经度、 纬度和高程信息, 此方法计算效率要远大于三维网格划分方式。文献[23] 将三维航迹规划分解为二维规划和高度规划, 使用动态时间规整(DTW: Dynamic Time Warping)距离作为A*算法的启发函数进行二维规划, 再由二维航迹结合高程数字地图, 利用粒子沉降法赋予每个航迹点高度信息, 生成三维航迹。这种方法有效地将三维空间的搜索节点删减至二维, 大大减少了搜索节点数量, 缩短了规划时间。使用DTW距离作为启发函数得到的航迹也要优于常用的欧氏距离、 曼哈顿距离和对角线距离, 但仍不是最优航迹。由于航迹规划问题的复杂性, 虽然学者们通过各种改进方法提高了A*算法的搜索效率, 但仍没有找到值恒等于从当前节点到目标点真实代价的启发函数, 实现A*算法的高效最优搜索。
遗传算法的基本思想是模拟生物遗传进化过程, 根据“适者生存”、 “优胜劣汰”的原则, 借助选择、 交叉、 变异等操作, 使所要解决的问题从初始解一步步逼近最优解。在航迹规划中, 遗传算法每条染色体(个体)代表无人机的一条航迹, 基因的编码方式也就是航迹节点的编码方式, 适应度函数由代价函数变化而来。遗传算法的优点是不要求优化函数具备连续、 可导和单峰等条件, 具有较强的鲁棒性, 是一种高效、 并行、 全局的搜索方法, 适用于三维全局航迹规划。缺点是种群失去多样性而导致早熟收敛, 寻优时间长, 局部搜索能力差等。针对该问题, 学者们提出了不同的改进方法, 如引入量子、 自适应等因子, 但这些改进方法仍然存在较多不足。文献[24] 针对量子遗传算法初始种群的单一性, 引入关于概率划分的小生境协同进化策略, 并对各种群采用动态量子旋转角；采用精英选择机制, 保留每一代中的最优个体, 并借鉴狼群分配原则对种群进行更新。该方法提高了量子遗传算法的稳定性和寻优精度, 但在收敛速度上没有改善, 且没有考虑无人机自身性能约束。文献[25] 使用并行遗传算法结合概率地图实现多无人机协同航迹规划, 并行遗传算法很好地克服了遗传算法早熟的缺陷, 但文献同样没有考虑无人机自身性能约束。文献[26] 通过在遗传算法主种群上附加一个病毒种群的方法, 保证可行引导段的有效积累并维持种群多样性。采用定长实值和变长实值两种编码方式分别为染色体和病毒个体编码, 通过采用反转录和转导这两种病毒感染操作实现两个种群间模块的信息交换, 使进化信息在种群内迅速、 定向地传播, 消除了寻优过程的盲目性。该方法改善了遗传算法早熟和局部收敛慢的问题, 提高了收敛速度, 但对于搜索精度几乎没有提高。文献[27] 提出多频振动遗传算法, 在遗传操作中使用两次变异操作, 分别作用于整个种群和精英个体, 为种群提供全局多样性和局部多样性, 从而有效避免早熟, 提高搜索精度, 达到快速收敛的目的。
