一、麻雀算法求解无人机三维路径规划简介
1 引言
随着无人机（Unmanned Aerial Vehicle,UAV）技术的不断发展，国内外学者对于无人机作战应用的研究日益增多。无人机航迹规划是任务规划系统的关键部分，是一个典型的非确定性多项式（Nondeterministic Polynomial,NP）问题。随着规划问题复杂度的不断增加，其难度和计算量迅速增长，很难找到一种有效应对所有复杂环境的航迹规划方法。为解决不同条件下的航迹规划问题，学者们不断对航迹规划算法进行研究和改进。研究了快速扩展随机树（Rapidexploration Random Tree,RRT）算法、A star算法、粒子群优化（Particle Swarm Optimization,PSO）算法、遗传算法（Genetic Algorithm,GA）在UAV航迹规划中的运用。Yang等将环境势场引入RRT算法，但得到的规划航迹与实际最短航迹有一定差距；刘华伟等将人的智能决策引入RRT算法，但是该算法依赖人的主观判断，容易陷入局部最优；赵锋等将启发式权重系数引入A star算法，但权重系数的线性调整策略不能很好地适应复杂的优化问题；Zhang等在PSO算法中设置异步变化学习因子，但搜索能力依赖于步长的分段设置；程泽新等在GA中引入差分进化策略，但改进后的算法计算量增大，航迹规划实时性较差。
自1975年美国教授Holland根据达尔文进化论以及自然界优胜劣汰机制提出了GA以后，越来越多的学者通过对不同生物种群和物理现象进行分析，从中获取灵感，提出了多种群智能优化算法，包括：灰狼优化算法（Grey Wolf Optimizier,GWO)、萤火虫算法（Firefly Algorithm,FA)、天牛须搜索（Beetle Antennae Search,BAS）算法、鲸鱼优化算法（Whale Optimization Algorithm,WOA)、天牛群优化算法（Beetle Swarm Optimization,BSO)。
麻雀搜索算法（Sparrow Search Algorithm,SSA)通过麻雀个体搜寻食物和反捕食进行迭代寻优，具有调整参数少、收敛速度快、计算简单等优点；但和其他群智能算法一样，在求解复杂工程优化问题时，容易“早熟”，导致收敛精度不高，且易于陷入局部最优解。SSA的更新方式可大致分为两种：1）向当前最优位置靠近；2）向原点靠近。通过仿真实验可知，在进行航迹模型最优航迹求解时，每次收敛是直接跳跃到当前最优解附近，容易丢失全局最优航迹解，仅可能得到满足约束的可行解，并且有概率得不到可行解。
2 麻雀搜索算法
SSA主要模拟了麻雀觅食的过程。麻雀觅食过程是发现者-跟随者模型的一种，同时还叠加了侦查预警机制。麻雀中容易找到食物的个体作为发现者，其他个体作为跟随者，同时种群中选取一定比例的个体进行侦查预警，如果发现危险则放弃食物，安全第一。由文献[13]可知，SSA是一种优于GWO、PSO、引力搜索算法（Gravity Search Algorithm,GSA）等算法的一种新的群智能优化算法。
SSA算法中有发现者、追随者以及警戒者，分别按照各自规则进行位置更新，更新规则如下：
其中：t为当前代数；Xit+1表示在t+1代第i只麻雀的适应值；itermax是最大迭代数；ξ∈(0,1)是一个随机数；R2表示警戒值；ST表示安全阈值；q是一个服从正态分布的随机数；L是一个一行多维的全一矩阵。
其中：Xp表示被发现者占据的最佳位置；Xworst表示当前最差位置；A是一个各元素为1或-1的一行多维矩阵。
其中：Xtbest是当前全局最佳位置；β是步长控制参数；K∈(0,1)是一个随机数；fi是当前麻雀的适应度，fg和fw是当前最佳适应度和最差适应度；ε是一个常数，用于避免分母为零，本文设置为10E-8。
算法实现具体如下：
步骤1初始化麻雀数量，定义相关参数；
步骤2对适应度进行排序，找到当前最佳适应度个体和最差适应度个体；
步骤3使用式（1）更新适应度靠前麻雀（发现者）位置；
步骤4使用式（2）更新适应度靠后麻雀（追随者）位置；
步骤5使用式（3）随机更新部分麻雀（警戒者）位置；
步骤6得到当前更新后的位置；
步骤7如果新位置优于旧位置，更新旧位置；
步骤8重复进行步骤3)～7);
步骤9输出最佳适应值和麻雀个体。
二、部分源代码
clc;clear;
三、运行结果
四、matlab版本及参考文献
1 matlab版本
a
2 参考文献
[1] 包子阳,余继周,杨杉.智能优化算法及其MATLAB实例（第2版）[M].电子工业出版社，.
[2]张岩,吴水根.MATLAB优化算法源代码[M].清华大学出版社，.
[3]巫茜,罗金彪,顾晓群,曾青.基于改进PSO的无人机三维航迹规划优化算法[J].兵器装备工程学报. ,42(08)
[4]邓叶,姜香菊.基于改进人工势场法的四旋翼无人机航迹规划算法[J].传感器与微系统. ,40(07)
[5]马云红,张恒,齐乐融,贺建良.基于改进A*算法的三维无人机路径规划[J].电光与控制. ,26(10)
[6]汤安迪,韩统,徐登武,谢磊.基于混沌麻雀搜索算法的无人机航迹规划方法[J].计算机应用. ,41(07)
