改进CS算法在无人机航路规划中的应用

郑洪清

（广西外国语学院 信息工程学院，南宁 530222）

改进CS算法在无人机航路规划中的应用

郑洪清

（广西外国语学院 信息工程学院，南宁 530222）

目前，智能算法成为求解无人机航路规划问题的主流方法，其重点是在无人机安全的前提下，如何快速到达目的地。针对这一问题，本文提出一种离散型布谷鸟搜索算法的航路规划方法，设计了基于八个方向的整形编码，采用航行的方向表示路径。仿真实验表明，该航路规划算法效率高，稳定性好，是一种行之有效的航路规划方法，且具有一定的推广意义。

无人机；布谷鸟搜索算法；航路规划

1 引言

无人机航路规划的任务是在待定的规划空间内，在给定约束条件下寻找一条从起点到终点的最佳航路，它本质上是一个多约束的优化问题，而航路规划算法是航路规划的灵魂，目前国内外学者提出了多种规划方法，如遗传算法［1］、粒子群算法［2］、人工势场法［3］和蚁群算法［4］等。这些算法存在各自的缺陷。人工势场法随着栅格数的增加迅速变慢，遗传算法早熟，易陷入局部最优。布谷鸟搜索算法（Cuckoo search algorithm， CS）是一种新型的全局搜索算法，它是通过布谷鸟的雷维飞行随机选择鸟巢下蛋的行为来完成寻优的过程，其在工程优化等实际问题中得到广泛应用，但基本的布谷鸟搜索算法并不能直接应用于无人机航路规划问题的求解。

为了克服基本布谷鸟搜索算法存在的这一问题，本文提出一种改进的布谷鸟搜索算法，设计一种基于八个移动方向的整形编码，通过修正编码及解码，使其适合求解无人机航路规划问题，通过仿真实验，结果表明该方法的可行性和有效性。

2 航路规划问题

2.1 飞行环境和任务描述

无人机在飞行之前需要对航路进行规划，根据地形信息和敌情信息自动生成最佳航路。由于无人机飞行高度较高，地形不能实现遮蔽，因此只考虑其水平航迹，将三维航路规划转换为二维问题。无人机飞行的任务区域如图1所示，对任务区域进行栅格化，建立如下所示的坐标系。圆圈表示威胁区，其飞行任务是从s点到t点既短又安全的最佳航路。

2.2 航路编码

通过上节的内容，将部分栅格信息摘录如图2所示，0表示可飞行区域；1表示障碍区域，若障碍区不满一格时，扩充为一个格子。

在栅格图中，每个栅格的序号是从左至右、从上到下依次递增的顺序从1开始编号，用公式（1）进行转换：

（1）式中的i 表示行，j表示列。算法的编码直接关系到算法的效率与可行性，一个好的算法应该与具体问题相关。现有的研究是在栅格化后的电子地图上有针对性地进行编码。文献［5］采用y轴的坐标作为编码，文献［6］将坐标轴进行旋转后再取纵坐标进行编码；文献［7］直接采用航路点的坐标作为编码；文献［8］采用起飞点、目标点和航路点的节点信息作为编码；文献［4］将栅格区域转换为一个有向图，将每一个栅格区域对应到有向图中的节点，用邻接矩阵来反映节点之间的连通信息，其空间复杂度O（n4），而本文设计一种新的编码方式，即无人机的航行方向，无人机在每一个栅格处，航行的方向至多为8个，如图3所示。以图2为例将栅格中的每一个区域对应到方向矩阵A中（在该例中只显示了3个方向，方向增多依次类推），其空间复杂度为O（n2）。因此本文的航路编码采用整型编码，路径节点的直角坐标采用文献［4］的计算公式：

（2）式中的Pm为栅格的大小，为取余函数，为取整函数。

方向节点集合w=｛1，2，…，m｝，m为移动方向的数目，故从起点到目标点航路以方向的形式表示为：

Path=｛S，L1，L2，…，Ln，E｝，其中Ln的取值为w集合中的某一个。

2.3 编码修正

随机产生的初始解代表的是每一个栅格的方向，由于飞行区域有许多威胁区，有些方向是不可行的，因此需依据方向矩阵A加以修正，其思想如下：

算法1：修正初始解

对于鸟巢内的每一个值，判断在方向矩阵相应的行里是否存在，若存在，则随机选择一个赋给鸟巢，否则赋为0。

2.4 解码

利用上述思想求得的最优解是方向矩阵，因此应将其解码为航路节点信息，算法2伪代码如下：

通过该算法可以将编码解码为航路的具体节点，ls表示栅格的列数。

2.5 航路性能评价

在确定飞机航路之前，要确定每条航路的性能指标，它主要包括耗油代价和威胁代价，航路的目标就是使得总代价最小，本文采用（3）式来评价航路性能［4］

为第i段航路的耗油代价，

它与航程Li是成正比；

为第i 段航路的威胁代价，k为权重系数，可以根据无人机的要求做出倾向性选择，k∈［0，1］。为了准确计算每段航路的威胁代价，在每段航路中找出5个均匀分布点并计算每个点到威胁源的威胁代价，累加求和即为该航段的威胁代价。其计算公式定义为：

式中的n为飞机当前所能探测到的威胁个数，Kj为第j个威胁的强度；Rij为该航路上的点到第j 个威胁中心的距离。

3 基于CS算法的无人机航路规划

3.1 基本CS算法

布谷鸟搜索算法是由英国剑桥大学学者 YANG Xin-she和DEB Suash对布谷鸟寻窝产卵的行为进行模拟，提出了一种新的搜索算法，即Cuckoo Search算法（CS）［9］。由于这种算法简单、高效且易于实现，并在各个领域得到广泛应用。该算法将模拟布谷鸟寻窝产卵的自然过程，把待解决问题的参数编码构成鸟巢，多个鸟巢构成种群，种群中的个体通过布谷鸟的Levy飞行选择鸟巢和一定概率抛弃鸟巢来更新种群。经过多次迭代直至得到最后的优化结果。

布谷鸟寻窝的路径和位置更新公式如下：

（5）式中乘法，∂表示步长，L（ λ）为Levy随机搜索路径，并且L～u=t-λ，（1＜λ≤3）。通过位置更新后，用随机数r∈［0，1］与pa对比，表示第i 个鸟巢在第t 代的鸟巢位置，⊕表示点若r＞pa，则对进行随机改变，反之不变。最后保留测试值较好的一组鸟巢位置

3.2 改进的CS算法

基本的CS算法适合求解连续优化问题，根据上一节编码的分析和结合无人机航路规划的特点， 需改进布谷鸟搜索算法使其适合求解无人机航路规划问题。通过公式（6）和（7）将其离散化。，此时仍把记为。

其中stepsize 为（5）式Levy飞行所产生的步长，m为方向的个数。

3.3 算法步骤

步骤1：将飞行区域栅格化并转化为0-1矩阵。

步骤2：由0-1矩阵判断无人机在每一个栅格的飞行方向，求出其方向矩阵。

步骤3：随机生成1-m个方向作为鸟巢nest的初始解。

步骤4：利用算法（1）生成有效矩阵。

步骤5：用公式（3）计算当前的最优值fmin及最优解fbest。

步骤6：利用公式（5）产生新解，并用公式（6）和（7）进行离散化处理，再利用算法（1）加以修正。

步骤7： 利用公式（3）重新评估最优值fnew和最优解fbest1，如果fnew＜fmin则用fnew，fbest1替换原来的最优值及最优解，否则不变。

步骤8：判断循环是否结束，如果是，根据算法（7）进行解码，输出航路点信息；否则跳转步骤6。

4 仿真实例与分析

为了检测所提出算法的性能，实例运行在处理器为Celeron（R）双核CPU T3100， 1.90GHZ 、内存为2G的PC上，以Matlab R2010a编写代码。假设无人机的飞行区域为20km×20km的电子地图，按1km×1km进行20等分，S表示起点，T表示终点，用不同的形状表示威胁区域。参数设置为：种群规模25，总迭代次数为50；权重系数k =0.4。每个实验独立运行10次。

实验一：4个威胁区域

对于不规则的4个威胁区域，其实验结果如图4所示。

实验二：11个威胁区域

这里对威胁区域采取近似圆表示，半径为威胁区域的有效距离，圆内为威胁区。设威胁点坐标为：（2，18），（2.5，13），（3，5），（7.5，4），（8，9），（7.5，15），（12，11），（12.5，6.5），（11，3），（14.5，2），（18，3），（17，6.5）；威胁半径（1，1.5，1，1，1，2.5，2，1.5，1， 0.5，1，1.5）。实验结果如图6所示。从图4和图6不难发现，采用改进的布谷鸟搜索算法能够规避风险，安全快速到达目的地，并且提高了路径规划的成功率，算法更加稳定。仿真结果表明本规划算法设计的航线是可行的，但由于航路的拐角太多，不利于无人机的飞行，故对航路进行了B样条函数处理后的结果如图5和图7所示。

5 结束语

利用一种新型的布谷鸟搜索算法对无人机航路规划问题时行分析与研究，设计了一种基于八个移动方向的编码方式，并提出离散型的布谷鸟搜索算法求解该问题，通过实验仿真，表明该方法的可行性，同时该方法可应用于类似的路线规划问题，具有一定的推广作用。

［1］K E Parsopoulos，M N Vrahatis.Unified Particle Swarm Optimization in Dynamic Environments［J］.EvoWork，2005，3449：590-599.

［2］Hwang，Y K，Ahuja N.A Potential Field Approach to Path Planning［J］.IEEE Transactions on Robotics and Automation （S1042-296X），1992，8（01）：23-32.

［3］税薇，葛艳，韩玉.基于混合蚁群算法的无人机航路规划，系统仿真学报，2011，30（04）：574-597.

［4］鱼佳欣，周春来，刘东平.改进遗传算法的无人机航路规划与仿真，计算机仿真，2013，30（12）：17-20.

［5］郑锐，冯振明，陆明泉.基于遗传算法的无人机航路规划优化研究，计算机仿真，2011，28（06）：88-91.

［6］邱小湖，邱永成.优化蚁群算法在无人机航路规划中的应用，计算机仿真，2010，27（09）：102-105.

［7］华珊珊.无人机航路自动规划优化方法研究与仿真，计算机仿真，2013，30（04）：45-48.

［8］YANG X S，DEB S.Cuckoo search via Levy flights［C］. proceedings of World Congress on nature & Biologically Inspired Computing，India：IEEE Publications，2009：210-214.

10.16640/j.cnki.37-1222/t.2016.20.129

郑洪清（1978-），男，硕士，讲师，研究方向为计算智能技术与应用。