基于改进模糊聚类并行蜻蜓算法的无人水面艇航迹规划

门雅范，杨宗仁，陈嫄玲

（1.河南省工业和信息化厅，河南郑州 450008；2.河南信息工程学校，河南郑州 450008；3.郑州轻工业大学，河南郑州 450008）

1 引言

无人水面艇（Unmanned Surface Vessel，USV）作为一种在水面自主航行的智能化无人平台[1]，具有灵活机动、成本低、隐蔽性强等优点，在海上搜救、水文监测、情报侦察、环境监测等军用和民用邻域具有广阔应用前景[2−3]。航迹规划作为USV重要研究邻域之一[4]，其目的是在风、浪、岛屿、礁石等复杂环境中自主寻找一条安全航线。

开展USV全局航迹规划研究具有重要意义[5]，文献[6]在采用栅格法建立海洋环境模型的基础上，利用A*算法对模型进行求解，提高了航迹的安全性，但是，该方案更侧重于航迹安全性，没有充分考虑能耗、航程等因素的影响。文献[4]提出了航程、能耗和安全避障评价指标，在栅格化海洋环境中建立航迹规划模型，并采用量子蚁群算法对模型求解，以实现最优航迹路线求解，但是，该方案将USV定位在每个栅格中心点，导致USV只能按照折现航行，因此，得到的航迹航程不一定最优，而且航迹平滑度需要进一步改善。文献[7]对传统A*算法进行改进，将USV潜在的8个前进方向扩展到24个，提高了航迹平滑度，但是，很大程度地增加了算法运算时间。研究表明，多目标航迹规划得到路线更贴近于实际应用，因此，一些具有较强多目标问题优化求解能力的智能优化算法被应用于USV 航迹规划中，文献[8−9]利用遗传算法，文献[10−11]采用蚁群算法，都得到了不错的规划效果，但是智能优化算法复杂问题收敛精度低、容易陷入局部最优等缺陷需要进一步研究[12]。

蜻蜓算法（Dragonfly Algorithm，DA）[13]是2016年才被提出的一种全新智能优化算法，DA将蜻蜓种群觅食现象抽象为静态群体、动态群体两种行为模式，有效平衡了算法局部搜索和全局搜索，具有良好的全局寻优能力，但是，面对复杂多维优化问题，DA与大部分智能优化算法一样，同样存在收敛精度不高的问题，文献[14]以牺牲运算时间为代价，赋予蜻蜓个体“记忆”，从而提高收敛精度，文献[15]对个体逐个维度进行更新，并采用贪心策略保留好的结果，一定程度提高了算法收敛效率，但是种群多样性逐渐降低，导致容易陷入局部最优。此外，文献[16−17]等在DA中融入其他智能算法，从而扩展了算法收敛空间，同样取得了良好的效果。但是，如何更加有效的结合DA进化进程和个体更新机制，来提高算法复杂问题求解能力，是亟须解决的难题，而且，这对提高DA算法收敛性能具有基础性意义。

为此，提出了一种基于改进模糊聚类并行蜻蜓算法的无人水面艇航迹规划方案，所做的工作有：

（1）设计航距、能耗、航迹弯折度、航行安全度4个评价指标，并在海洋环境栅格化处理的基础上，引入坐标转换机制，克服了“折线”式USV航行缺点，而且降低了问题求解维度。

（2）设计能够自动确定聚类个数的改进模糊聚类算法，并对蜻蜓种群进行聚类分析，以自适应确定蜻蜓静态邻域规模；设计动态非线性权重因子调整策略，以平衡算法局部搜索和全局搜索；引入并行运算机制，来提高算法运算效率。

（3）对经典测试函数和USV航迹规划实例进行仿真，以验证所提方案的有效性。

2 USV航迹规划模型构建

2.1 海洋环境栅格化处理与坐标转换

航迹规划的目的是在起点Xstar和终点Xend之间寻找一条路线，在确保航行安全的同时，使得路程、能耗等指标达到最优。为了降低复杂度，通常在Xstar(X0)与Xend(XN)之间找到N−1个节点Xi，并将这些节点依次连接，即得到航迹l=(X0，X1，…，XN)。

电子海图能够准确描述海洋环境信息，为了便于其应用到USV航迹规划中，需要进行栅格化处理：即将海图代表的区域分割成若干块大小相等的方形栅格，每个栅格详细记录海流流速、海风风速、海浪波幅，以及障碍物等信息。传统的航迹规划算法，是将USV定位在每个栅格中心，赋予其8个潜在行进方向，并根据栅格内海洋信息进行路径规划。这种“机械”式的行进方案得到的航迹不一定最优，而且也没有充分考虑USV 的机动性能。为此，提出坐标转换策略，如图1所示。

图1 海洋环境栅格化处理与坐标转换Fig.1 The Marine Environment Rasterize Processing and Coordinate Transformation

为了便于问题描述，将X0设置为原点，对覆盖X0、XN的区域进行海洋环境栅格化处理，每个栅格边长为L。以X0为原点，Ri=i×r（i=1，…，N−1）为半径画圆，在栅格区域内得到N−1个圆弧，设定Ri与L的关系为：

2.2 航迹规划目标优化函数

为了使得规划航迹更加贴近实际应用，设计基于航距、能耗、航迹弯折度和航行安全度4个评价指标，并根据应用场景和任务对各个评价进行加权，形成航迹规划目标优化函数。

（1）航行距离。定义航距总长度L(θ) 为：

式中：νUSV—推进系统产生的速度；τ—海风、海流、海浪干扰力的合力。

（3）航迹弯折度。定义航迹弯折度Θ(θ)为：

式中：Θ(θ)—航迹弯折程度，其值越小，表明航迹更加平滑。

（4）航行安全度。定义航行安全度P(θ)为：

式中：d—USV到障碍物中心距离；dsafe—最小安全距离。

（5）目标优化函数。当确定了L(θ)、E(θ)、Θ(θ)和P(θ)4个评价指标后，定义USV航迹规划目标优化函数：

式中：ωL、ωE、ωΘ—权重系数，且ωL+ωE+ωΘ=1；Lmax—USV极限航程；νmax—USV最大航速。

3 改进模糊聚类并行蜻蜓算法

蜻蜓算法（DA）作为最近才被提出的智能优化算法，最大的特点是融入了局部搜索和全局搜索。

DA算法赋予蜻蜓个体两个模态：捕食和迁徙，捕食发生在个体的邻域小群体内，具有局部搜索性质；迁徙表现为种群整体行为，具有全局搜索性质，并且个体Xi()t以避撞行为Si、结队行为Ai、聚集行为Ci、觅食行为Fi和避敌行为Ei等5种行为进行迭代更新（DA基本原理见有关文献，不在赘述）：

式中：λ—惯性权重系数；(s，a，c，f，e)—5种行为权重组合。

当Xi(t)周围没有临近个体时，Xi(t)采用随机游走行为更新：

式中：r1、r2—（0，1）随机数；χ—常数，Γ(1+χ)=χ！。

从DA进化过程可以看出，个体邻域范围及(s，a，c，f，e)是影响算法全局寻优的关键因素，为此利用改进的模糊聚类算法对种群进行动态聚类分析，并引入动态调整权重因子。

3.1 模糊聚类算法及改进

核模糊C均值聚类算法（KFCM）[18]通过采用内核诱导距离替换欧式距离，实现了对FCM算法应用邻域的有效扩展，很大程度地提高了聚类效果，其聚类目标函数J(U)，V、隶属度μik、聚类中心vi为：

式中：U、V、m、C—隶属度矩阵、聚类中心集合、模糊加权指数和聚类个数；K(x，v)—核函数内积（一般选取高斯函数）。

KFCM利用式（14）迭代计算，最终实现样本数据的分类。

聚类个数C事先确定，是KFCM算法亟须解决的难题之一，为此设计最优聚类个数评价指标Com(U，V)：

给出Com(U，V)定义后，依次设置聚类个数C的取值，并选取Com(U，V)最小值对应的Cbest为最佳聚类个数。

从式Com(U，V)定义可以看出，采用指数函数计算数据样本xi与聚类中心的距离，能够降低噪声点、离群点对Com(U，V)的影响，具有更好地鲁棒性。

Com(U，V)代表了类内数据的离散程度，取值越小，表明同一类的数据具有更多的相似性，聚类效果也更好。

3.2 动态调整权重因子

标准DA算法采用线性方式对结队行为权重a和聚集行为权重c进行调整，且规定a=c。

但是，在算法运算初期，种群个体之间样本差距性较大，应增大局部搜索权重；随着不断迭代进化，种群趋同性增加，为提高收敛效率，应增大全局搜索权重，为此提出动态调整权重因子：

式中：η—控制系数；fmax、fmin—最大最小值。从式（16）、式（17）可以看出，非线性动态调整a和c，更利于平衡局部搜索和全局搜索，能够提高收敛效率和收敛精度。

3.3 种群多样性和计算复杂度

为提高DA算法复杂函数优化性能，采用改进的模糊聚类算法对种群进行聚类分析，聚类结果作为蜻蜓个体邻域的选取依据，并采用式（16）、式（17）调整权重因子。

种群多样性分析保持种群样本多样性对智能优化算法全局寻优具有重要意义，大部分智能优化算法往往只根据个体适应度值确定进化方向，然而，具有相似适应度值的不同个体，空间特性往往存在很大差异，只有选择与自身空间特性相差较大的个体进行学习，才能扩展算法搜索空间，并利于保持样本多样性。对于DA算法这种模拟生物局部聚集行为的智能优化算法，紧紧根据适应度值选取邻域个体，并不能够真实反映种群空间聚集样态，而改进模糊聚类算法的引入，恰好根据个体空间特性进行聚类分析，得到的聚类更像是分布在空间的一个个小群体，更符合实际生物特征。因此，改进后的蜻蜓算法能够科学合理的选择学习对象和选取邻域个体，也能够很好的保持样本多样性。

计算复杂度对于N维优化问题，包含P个个体的种群初始化复杂度为O()PN，执行一次模糊聚类操作复杂度为(Cmax−1)O(P（)为KFCM算法最大迭代次数），个体更新复杂度为O(PN)，因此，算法总计算复杂度为：

从式（18）可以看出，由于每次进化都要执行Cmax−1次模糊聚类操作，增加了算法运算时间，为此，采用MPI并行运算架构：搭建具有Cmax个处理器的并行网络，安排一个节点执行初始化，Fi、Ei更新，种群最优与最差解更新，()s，a，c，f，e更新以及终止判定等操作，其余节点执行模糊聚类、邻域个体确定以及Si、Ai、Ci更新等操作，从而大大缩短了算法运算时间。

3.4 基于IFDDA的航迹规划实现

基于IFDDA算法的航迹规划流程图，如图2所示。

图2 基于IFDDA算法的航迹规划流程图Fig.2 Path Planning Based on IFDDA Algorithm Flow Chart

4 实验仿真

采用典型测试函数和USV航迹规划实例对IFDDA算法性能进行验证。

4.1 典型测试函数实验

选取f1:Sphere、f2:Rosenbrock、f3:Ackley、f4:Griewank等4个典型测试函数（函数具体设置见文献[19]），其中f1—单峰函数，主要评价算法有效性；f2—病态单模函数，很难找到全局最优解；f3—多峰函数，很容易陷入局部最优；f4—多维复杂函数，主要验证算法全局寻优能力。在MATLAB 平台上，分别采用DA（参数设置见文献[15]）、EDDA[15]、ECO[19]和这里提出的IFDDA进行仿真实验，每种算法独立运行30次，取最优解均值（）、平均运行时间（）和标准方差（）进行对比分析。对比结果，如表1所示。

表1 4种算法对比结果Tab.1 Four Kinds of Comparison Algorithm

不同函数收敛曲线，如图3～图6所示。

图3 函数f1收敛曲线Fig.3 Convergence Curve Function f1

图4 函数f2收敛曲线Fig.4 Convergence Curve Function f2

图5 函数f3收敛曲线Fig.5 Convergence Curve Function f3

图6 函数f4收敛曲线Fig.6 Convergence Curve Function f4

4.2 USV航迹规划实例仿真

设置模拟海洋环境、电子海图文件2种仿真场景，并采用文献[4]、文献[5]和基于IFDDA的航迹规划算法进行对比实验。

（1）模拟海洋环境

在长度为50km的方形区域内，采用单位长度为1km的栅格进行划分，起始点位置为（0.5，0.5）、目标点位置为（36.5，45.5），障碍物等效为不规则几何图形，海风、海浪及海流信息在合理范围内随机设置。

（2）电子海图文件

利用电子海图数据库内数据进行图层信息提取，并采用栅格法将海图区域进行栅格化处理，设定起始点位置为（119.6°W，75.4°N），对应坐标为（5.5，33.5）；目标点位置为（104.7°W，78.2°N），对应坐标为（25.5，16.5）。海风、海浪及海流信息由海图数据库获取。

两种仿真环境下不同规划算法规划路线，如图7、图8所示。不同规划算法评价指标对比结果，如表2所示。

表2 不同规划算法评价指标对比Tab.2 Different Planning Algorithm Evaluation Index Contrast

图7 航迹规划实例1仿真结果Fig.7 The Simulation Results for Instance 1

图8 航迹规划实例2仿真结果Fig.8 The Simulation Results for Instance 2

4.3 结果分析

（1）IFDDA算法收敛精度较高。对于基本单峰函数f1，在允许精度范围内，4种算法都寻找到了全局最优解，但是，IFDDA收敛精度要远远好于其它3种算法；对于病态复杂函数f2，除IFDDA外，其它3种算法都没有找到最优解；为病态单模函数，很难找到全局最优解；对于多峰高维函数f3、f4，DA、ECO、EDDA等3种算法收敛效果不是很理想，只有10−2左右的收敛精度，而IFDDA可以达到10−4级别。表明，对于复杂优化函数优化问题，IFDDA收敛精度优于其他3种算法。

（2）IFDDA算法运算较快。从图3～图6和表2可以看出，无论对于哪个函数优化问题，IFDDA 好于DA，明显好于ECO、ED‐DA，运算速度整体提高约23.7%。

（3）IFDDA能够给出更加合理的航迹规划路线。从图7、图8及表1可以看出，基于IFDDA得到的航迹更加平滑，明显好于其它2种规划结果。对于航迹规划实例1，相比于其它2种规划算法，航程降低了约43.9%、55.2%，能耗降低了约38.6%、56.5%；对于航迹规划实例2，相比于其它2 种规划算法，航程降低了约7.3%、50.4%，能耗降低了约17.1%、51.3%；

IFDDA 之所以具有较高的收敛精度，最关键的原因是采用模糊聚类算法对种群进行分析，并根据聚类结果选定种群进化学习对象，克服了仅仅依据适应度值导致盲目性较大的缺陷。之所以具有较快的运算速度，是因为采用并行运算架构，将大部分运算操作分布在各个节点进行处理，大幅度提高了运算效率。USV航迹规划仿真也表明，IFDDA在处理工程优化问题时具有突出的求解性能，具有一定的推广意义。

5 结束语

提出了一种基于改进模糊聚类并行蜻蜓算法的无人水面艇航迹规划方案。从蜻蜓算法本质出发，寻求改善算法全局优化性能的改进机制，经典测试函数结果表明，引入的改进模糊聚类算法、动态调整算法权重因子等极大地提高了算法收敛性能。从USV航迹规划实际出发，搭建多评价指标航迹模型，并采用改进的蜻蜓算法进行求解，得到的航迹更加平滑、能耗更低、能耗更短。