AUV Global Path Panning Based on Improved T-Distribution Fireworks-Particle Swarm Optimization Algorithm

LIU Zhi-hua; ZHANG Ran; HAO Meng-nan; AN Kai-chen; CHEN Jia-xing

doi:10.12263/DZXB.20230814

PDF(6319 KB)

ACTA ELECTRONICA SINICA ›› 2024, Vol. 52 ›› Issue (9) : 3123-3134. DOI: 10.12263/DZXB.20230814

PAPERS

AUV Global Path Panning Based on Improved T-Distribution Fireworks-Particle Swarm Optimization Algorithm

Author information +

History +

Abstract

In response to the long optimization time and high energy consumption faced by traditional particle swarm optimization algorithm in global path planning for autonomous underwater vehicle, this paper proposes an improved T-distribution fireworks-particle swarm optimization algorithm (TFWA-PSO), this algorithm integrates the efficient global search capability of the fireworks algorithm with the rapid local optimization characteristics of the particle swarm optimization algorithm. In the mutation stage, an adaptive T-distribution mutation is proposed to expand the search range, and it is theoretically demonstrated that this explosive mutation approach enables individuals to enhance their search ability near the local optimal solution. In the selection stage, a fitness selection strategy is proposed to eliminate individuals with poor fitness, solving the problem of the traditional fireworks algorithm's tendency to lose excellent individuals, and comparing the convergence speed between the improved T-distribution fireworks algorithm and the traditional fireworks algorithm. The improved algorithm's explosion, mutation operations, and selection strategy are integrated into the particle swarm algorithm. The velocity update formula of the particle swarm algorithm is improved, while the convergence proof of the improved algorithm is proved theoretically. The simulation results indicate that the TFWA-PSO can effectively plan the shortest path. Compared to the given intelligent optimization algorithms, TFWA-PSO on average reduces the time to find the optimal path by 24.72%, lowers energy consumption by 17.33%, and decreases the average path length by 16.96%.

Key words

autonomous underwater vehicle / global path planning / fireworks algorithm / particle swarm optimization / adaptive T-distribution mutation / convergence proof

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

LIU Zhi-hua , ZHANG Ran , HAO Meng-nan , AN Kai-chen , CHEN Jia-xing. AUV Global Path Panning Based on Improved T-Distribution Fireworks-Particle Swarm Optimization Algorithm[J]. Acta Electronica Sinica, 2024, 52(9): 3123-3134. https://doi.org/10.12263/DZXB.20230814

1 引言

海洋是人类巨大的资源宝库，蕴藏丰富.在探索和开发海洋的过程中，自主水下机器人（Autonomous Underwater Vehicle， AUV）因具有隐蔽性好、快捷灵敏、活动范围广等优点^［1］，成为人类探索海洋资源强有力的工具，在水下监测与调查、海底勘测、海上防御等方面都得到了广泛的应用.水下环境复杂多变，不仅存在静态障碍物，还存在动态障碍物，AUV根据先验知识规划出满足航行需的路径显得尤为关键，标志着其智能化程度的高低，也是AUV能否安全、准确地完成水下作业的关键.

目前，国内外学者在AUV全局路径规划方面作了诸多研究，传统路径规划算法过程简单，易于实现，但也存在路径优化效果差、处理速度慢、动态避障能力不足等问题.因此群体智能优化算法逐渐成为主流算法，常用的有粒子群算法（Particle Swarm Optimization， PSO）^［2］、蚁群算法^［3］、遗传算法^［4］、灰狼算法^［5］等.其中粒子群算法作为一种启发式算法，在多个领域得到广泛应用.除了AUV路径规划，它还在电力系统优化、图像处理和无人飞行器路径规划等领域也表现出了出色性能和适用性.然而，单一的粒子群算法存在着鲁棒性差和计算时间长等问题.如文献［6］提出了改进的量子粒子群优化算法，通过求解薛定谔函数引入位置不确定性，以跳出局部最优解，并使用四叉树框架进行障碍物建模，提高建模精度和算法效率.文献［7］将随机惯性权值与压缩因子粒子群优化相结合，解决了局部最优解问题.

近年来，混合群体智能算法在路径规划领域得到广泛应用，学者们尝试将粒子群算法与其它优化算法结合，旨在整合各算法的优点并克服单一算法的局限性.文献［8］提出了一种动态海洋环境下的最优路径规划算法，上层使用蚁群算法生成路径，下层使用量子粒子群算法优化路径参数，使算法具有更快的收敛速度.文献［9］将强化学习和粒子群算法结合，强化学习用于实时分配的决策过程，粒子群优化用于优化决策的搜索过程，但算法需要较长的训练时间才能获得良好性能.文献［10］利用差分进化算法的交叉策略克服局部最优.文献［11］中，以遗传算法和细菌觅食算法为辅助方法，改进了粒子群算法的速度更新公式，增强了局部和全局的搜索能力.文献［12］使用粒子群算法预搜索路径并优化蚁群算法的信息素分布，提高了蚁群算法的早期搜索能力，解决了初始收敛慢的问题.文献［13］提出了一个两层多目标路径规划模型，上层模型使用蚁群优化算法生成任务序列，下层模型使用A*算法和粒子群优化算法生成相邻任务之间的航点.在文献［14］中，将神经网络与粒子群优化算法相结合，统一了障碍物表示和碰撞检测模型，提高了检测效率和平滑度，快速规划出平滑无碰撞的机器人路径.

烟花算法（Fireworks Algorithm， FWA）作为一种新型启发式算法，具有随机性、爆发性、多样性等特点.FWA在每一次的迭代过程中通过烟花的爆炸操作能够搜索到比其它算法更多的可行解，但局部搜索上表现较弱.而PSO凭借粒子间的协作与信息共享，在局部搜索和优化方面具有出色的能力，因此将两种算法结合起来，可以在搜索空间中进行全局探索，并在局部范围内进行精细调整，从而找到更优的路径规划结果.

针对上述问题，本文提出一种改进的T分布烟花-粒子群算法（T-distribution Fireworks-Particle Swarm Optimization Algorithm， TFWA-PSO），对烟花算法中的高斯变异和选择策略进行改进，提出自适应T分布变异生成变异火花增强全局搜索能力，并提出一种适应度选择策略进行下一代种群的选择.针对粒子群优化算法在迭代过程中易陷入局部最优的问题，将改进的T分布烟花算法（T-distribution Fireworks Algorithm， TFWA）中的爆炸操作、变异操作以及改进的选择策略融合到粒子群算法中，使粒子在局部最优解附近以爆炸火花的方式增强搜索能力，同时改进了粒子群算法的速度更新公式，有利于跳出局部最优解，更快地找到最优解路径，从而减少AUV路径规划时间、降低能耗.

2 问题描述

假设全局信息已知，AUV利用智能优化算法规划出能避开障碍物的可行路径并到达目标点.考虑到AUV实际工作时，航行的纵深变化范围一般较小，因此假设AUV采取定深度航行，工作区域为平面，如图1所示.

图1 水下AUV全局路径规划示意图

Full size|PPT slide

本文主要处理的关键问题为：（1）如何进行避障？在路径规划过程中，通过传感器检测障碍物信息，并计算粒子与障碍物之间的距离.根据避障距离阈值判断是否需要避开障碍物，如果需要，则调整粒子的方向和速度，并重新选择节点进行规划.（2）如何确定AUV的路径？本文通过改进的T分布烟花-粒子群算法，利用烟花爆炸的思想将粒子群的位置和速度更新转化为火花的爆炸过程，实现全局搜索和局部优化，通过不断迭代更新，找到最优路径.

2.1 环境建模及路径初始化

环境建模是路径规划的基础环节，常用的方法包括栅格法和可视图法.栅格法因简单易实现，在路径规划中应用广泛，但也存在效率低和搜索时间长的问题.相比之下可视图法更简单直观、易于发现最短路径.因此本文采用可视图法中一种新的地图创建方法——三角形法^［15］来进行建模.通过把工作平面中的非障碍物区域划分为若干三角形区域，来获得AUV初始无障碍路径.具体步骤如下：

步骤1 假设工作平面为矩形，存在

n

个障碍物

y_{i}

(i = 1,2, \dots, n)

，设

y_{i}^{(j)}

(j = 1,2, \dots, m)

表示第

i

个障碍物的第

j

个边缘点，工作平面矩形的4个顶点也看做边缘点

y_{0}^{(j)} (j = 1,2, 3,4)

.设AUV的起点为

y_{0}^{(1)}

，目标点为

y_{0}^{(3)}

，分别位于工作平面矩形的对角点上.

步骤2 对形状不规则的障碍物进行膨胀操作，具体来说，将障碍物轮廓线上的点作为输入，使用多边形拟合算法将这些点拟合成一个最小多边形.然后连接各边缘点，删掉与障碍物相交的线段，保证所有的线段除了端点均不与障碍物相交，得到线段集合

{x (i)}, i = 1,2, \dots, n

步骤3 对步骤1中生成的线段进行排序，得到一个由短到长的线段队列

{\tilde{x} (i)} = s o r t {x (i)} = {\tilde{x} (1), \tilde{x} (2), \dots}

步骤4 在队列中取出第一条最短线段

\tilde{x} (1)

，检查此线段是否和队列中其它线段相交.如果相交，则从队列中删除相交的线段，直到队列中没有与其相交的线段.

步骤5 接着取出队列中的第二短线段，检查其是否与后面的线段相交，并删除与其相交的线段.

步骤6 重复操作，直到取完队列中所有的线段，得到互不相交的线段序列

{\overset{⌢}{x} (i)}, i = 1,2, \dots

步骤7 智能优化算法中粒子根据自己的速度和方向，选择不同线段上的点，最后将这些点连接，得到无障碍路径集

X^{(0)} = {\hat{x} (n)}

，完成路径初始化.

上述三角形法，可将AUV的工作环境划分为若干个三角形区域，相较于普通的可视图法，当两条线段相交时，三角形法遵循的是最短线段原则，较长的线段被删除，较短的线段被保留下来，因此在路径初始化阶段，能获得较短的初始化无障碍路径集，如图2所示.

图2 水下三角形法环境建模图

Full size|PPT slide

2.2 传统烟花算法FWA

FWA由爆炸操作、高斯变异操作、映射规则和选择策略4部分组成，在2.1节中由三角形法得到线段序列

{\overset{⌢}{x} (i)}, i = 1,2, \dots

后，FWA计算

{\overset{⌢}{x} (i)}

中所有线段的中点，得到路径序列集

{\hat{x} (n)}

.设

X^{(l)} = {x_{1}^{(l)}, \dots, x_{i}^{(l)}, \dots, x_{N}^{(l)}}

，

(i = 1,2, \dots, N)

为第

l

次迭代的初始烟花集合，其中

N

为烟花个数，

x_{i}^{(l)}

表示第

i

个烟花的位置，

X^{(0)} = {\hat{x} (n)}

为2.1节中的初始化无障碍路径集，此时有

x_{i}^{(0)} = \hat{x} (i)

（1）爆炸操作：在FWA中，烟花 $x_{i}^{(l)}$ 的爆炸半径 $A_{i}^{(l)}$ 和爆炸产生的火花数目 $S_{i}^{(l)}$ 是根据烟花种群中其它烟花适应度计算得到的，计算公式分别为^［16］

A_{i}^{(l)} = \hat{A} \times \frac{f (x_{i}^{(l)}) - Y_{m i n}^{(l)} + ψ}{\sum_{i = 1}^{N} (f (x_{i}^{(l)}) - Y_{m i n}^{(l)}) + ψ}

（1）

S_{i}^{(l)} = M \times \frac{Y_{m a x}^{(l)} - f (x_{i}^{(l)}) + ε}{\sum_{i = 1}^{N} (Y_{m a x}^{(l)} - f (x_{i}^{(l)})) + ε}

（2）

其中

M

和

\hat{A}

是常数，用于调整爆炸产生的火花数量和爆炸半径，

Y_{m a x}^{(l)}

和

Y_{m i n}^{(l)}

分别表示当前烟花种群中适应度的最大值和最小值，

ε

和

ψ

是一个很小的常数，防止出现分母为零的情况.

对每一个烟花

x_{i}^{(l)}

进行爆炸后，产生个数为

S_{i}^{(l)}

的火花集合

Y_{i}^{(l)} = {y_{i, 1}^{(l)}, \dots, y_{i, j}^{(l)}, \dots, y_{i, S_{i}^{(l)}}^{(l)}}

，第

i

个烟花爆炸的第

j

个火花

y_{i, j}^{(l)}

表达如下

y_{i, j}^{(l)} = x_{i}^{(l)} + A_{i}^{(l)} \times r a n d (0,1)

（3）

其中

1 \leq i \leq N, 1 \leq j \leq S_{i}^{(l)}

（2）高斯变异操作：FWA引入了高斯变异来增加种群中烟花的多样性，在种群 $X^{(l)}$ 中随机选择 $p (1 \leq p \leq N)$ 个烟花进行高斯变异，产生个数为 $p$ 的高斯变异火花集合 $Z^{(l)} = {z_{1}^{(l)}, \dots, z_{h}^{(l)}, \dots, z_{p}^{(l)}}$ ， $z_{h}^{(l)}$ 表达如下

z_{h}^{(l)} = x_{i}^{(l)} + x_{i}^{(l)} \times g

（4）

其中

z_{h}^{(l)} (1 \leq h \leq p)

表示烟花

x_{i}^{(l)}

进行变异后的位置，

g

是均值为1，方差为1且满足高斯分布的随机数.

（3）映射规则：第 $i$ 个烟花爆炸后产生的第 $j$ 个火花 $y_{i, j}^{(l)}$ 和高斯变异火花 $z_{h}^{(l)}$ 可能会超出可行域范围，需要通过映射规则重新映射回可行域内，公式如下

y_{i, j}^{(l)} = x_{m i n} + |y_{i, j}^{(l)}| % (x_{m a x} - x_{m i n})

（5）

z_{h}^{(l)} = x_{m i n} + |z_{h}^{(l)}| % (x_{m a x} - x_{m i n})

（6）

其中

x_{m a x}

和

x_{m i n}

分别为边界的上、下界，%代表模运算.

（4）选择策略：在第 $l$ 次迭代的最后，烟花算法要从集合 $W^{(l)} = X^{(l)} ⋃ Y_{i}^{(l)} ⋃ Z^{(l)} = {w_{i}^{(l)}}$ 中通过轮盘赌法选择概率 $p (w_{i}^{(l)})$ 最大的前N-1个个体作为下一代烟花

p (w_{i}^{(l)}) = \frac{\sum_{w_{j}^{(l)} \in W^{(l)}} ‖w_{i}^{(l)} - w_{j}^{(l)}‖}{\sum_{w_{i}^{(l)} \in W^{(l)}} \sum_{w_{j}^{(l)} \in W^{(l)}} ‖w_{i}^{(l)} - w_{j}^{(l)}‖}

（7）

3 改进T分布烟花算法TFWA的路径规划

3.1 TFWA

（1）改进变异操作

传统FWA使用高斯变异来产生变异的火花，增加种群的多样性.然而，高斯变异在全局搜索能力上相对较弱，当解空间中存在许多局部最优解时，算法可能陷入这些局部最优解，从而阻碍了全局收敛.因此为了避免陷入局部最优解，本文提出了自适应T分布变异，使FWA能够在全局搜索中获得更优的效果.

T分布又称为学生分布，其曲线形态和自由度

d f

有关，概率密度函数如下

t (x) = \frac{Γ (\frac{d f + 1}{2})}{\sqrt[]{d f π} Γ (\frac{d f}{2})} \cdot {(1 + \frac{x^{2}}{d f})}^{- \frac{d f + 1}{2}}

（8）

式中

Γ (\frac{d f}{2}) = \int_{0}^{+ \infty} x^{\frac{d f}{2} - 1} e^{- x} d x

为第2类欧拉积分.

当

d f = 1

时，T分布为柯西分布，在

d f \to \infty

时，T分布为高斯分布.柯西分布与高斯分布是T分布的2个边界特例，通过改变

d f

的值可以得到不同的变异幅度，从而使变异过程具有更大的灵活性.

对第i个火花原位置

x_{i}^{(l)}

进行如下变异

z_{h}^{(l)} = x_{i}^{(l)} + x_{i}^{(l)} \times t (l)

（9）

其中

t (l)

是以算法的迭代次数

l

为自由度的T分布随机变量的取值.

该变异方法旨在充分利用柯西变异的大突变能力，降低陷入局部最优解的风险，并同时利用高斯变异的强大局部搜索能力.通过交替使用柯西变异和高斯变异，实现自适应T分布变异.

从图3柯西分布和高斯分布的图像上来看，柯西分布的曲线比高斯分布的曲线峰度更低，尾部更长，搜索范围更广.搜索范围，即算法在解空间中搜索解的范围，其大小可通过解的标准差来衡量，标准差越大搜索范围越广，为证明TFWA的搜索范围是随着迭代次数的增加逐渐减小的，提出定理1.

图3 高斯分布和柯西分布图像的比较

Full size|PPT slide

定理1

在迭代初期，TFWA的标准差较大，随着迭代次数的增加，TFWA的标准差逐渐减小，搜索范围也逐渐减小.

证明

对于随机变量

X

，其方差可以表示为

V a r (X) = E (X^{2}) - E^{2} (X)

（10）

其中，

E (X)

表示

X

的期望.

在TFWA的变异公式（9）中通过

x_{i}^{(l)} \times t (l)

的方差来计算变异后解向量的方差如下

V a r (x_{i}^{(l)} \times t (l)) = E [{(t (l) \times x_{i}^{(l)})}^{2}] - E^{2} [t (l) \times x_{i}^{(l)}]

（11）

由于

t (l)

服从T分布，且

E [t (l)] = 0

，

E [t {(l)}^{2}] = \frac{l}{l - 2}

，代入式（11）得到

V a r (t (l) \times x_{i}^{(l)}) = \frac{E^{2} [x_{i}^{(l)}]}{1 - \frac{2}{l}}

（12）

因此，TFWA变异后解向量的标准差

σ_{t}

为

σ_{t} = \sqrt[]{V a r (t (l) \times x_{i}^{(l)})} = \sqrt[]{\frac{E^{2} [x_{i}^{(l)}]}{1 - \frac{2}{l}}}

（13）

由式（13）可知，TFWA变异后解向量的标准差

σ_{t}

与迭代次数

l

成反比，即随着迭代次数的增加，

σ_{t}

逐渐减小，搜索范围也逐渐变窄.所以在迭代初期，TFWA搜索范围较大，随着迭代次数的增加，算法搜索范围逐渐减小.

证毕.

（2）改进选择策略

在FWA中，除了选择种群中的最优值继续迭代外，其余的火花根据聚类程度的大小使用轮盘赌法进行选择.然而，这种选择方式会导致许多优秀的个体丢失，并增加适应度较差个体被选择的概率，特别是处于边缘位置的个体.基于以上考虑，本文提出一种适应度选择策略，使得适应度较好的火花有更大的机会被选择进入下一轮循环.

设烟花

x_{i}^{(l)}

中的个体

w_{i}^{(l)}

依据概率

p (w_{i}^{(l)})

被选择

p (w_{i}^{(l)}) = \{\begin{array}{l} {(\frac{f (w_{i}^{(l)}) - Y_{m i n}^{(l)}}{Y_{m a x}^{(l)} - Y_{m i n}^{(l)}})}^{k}, f (w_{i}^{(l)}) > Y_{m i n}^{(l - 1)} \\ 1 - {(\frac{f (w_{i}^{(l)}) - Y_{m i n}^{(l)}}{Y_{m a x}^{(l)} - Y_{m i n}^{(l)}})}^{k}, f (w_{i}^{(l)}) \leq Y_{m i n}^{(l - 1)} \end{array}

（14）

其中，

Y_{m a x}^{(l)}

、

Y_{m i n}^{(l)}

为第

l

次迭代爆炸产生个体适应度的最大值和最小值，

f (w_{i}^{(l)})

为个体

w_{i}^{(l)}

的适应度.

由于

Y_{m i n}^{(l)} < f (w_{i}^{(l)}) < Y_{m a x}^{(l)}

，所以

0 < (f (w_{i}^{(l)}) - Y_{m i n}^{(l)}) / (Y_{m a x}^{(l)} - Y_{m i n}^{(l)}) < 1

.因为k>0是常数，所以

((f (w_{i}^{(l)}) - Y_{m i n}^{(l)}) / (Y_{m a x}^{(l)} - Y_{m i n}^{(l)} {))}^{k}

随着k的增大而减小，相反

1 - ((f (w_{i}^{(l)}) - Y_{m i n}^{(l)}) / (Y_{m a x}^{(l)} - Y_{m i n}^{(l)} {))}^{k}

随着k的增大而增大，因此当

f (w_{i}^{(l)})

比较小时，适应度较好的火花以更大的概率被选择进入下一轮迭代，当

f (w_{i}^{(l)})

比较大时，以较小的概率被选择，增加了优秀解被保留的概率，提高了算法的收敛速度.相比之下，传统的选择策略仅基于概率分布来选择新种群，无法有针对性地保留适应度较好的火花，容易淘汰掉优秀解.

3.2 TFWA收敛速度分析

一个好的算法不仅需要是收敛的，还要求它收敛的速度比较快，所谓迭代过程的收敛速度，是指在接近收敛时迭代误差的下降速度.

定义1 在第

l

次迭代时，以粒子位置

x_{i}^{(l)}

与全局最优解

x^{*}

之间的距离为收敛误差

e (l) = | | x_{i}^{(l)} - x^{*} | |

（15）

收敛速度

R^{(l)}

定义为收敛误差

e (l)

随迭代次数

l

的增大而逐渐减小的速度

R^{(l)} = \underset{l \to \infty}{l i m} \frac{e (l + 1)}{e (l)}

（16）

TFWA主要在变异和选择策略进行了改进，下面将针对这两个方面提出定理2，比较TFWA和FWA的收敛速度.

定理2 TFWA的收敛速度比FWA更快.

证明首先在变异阶段，由式（4）和式（9）的FWA和TFWA的迭代方程，分别计算它们的收敛速度.

对于FWA有

R_{F W A}^{(l)} = \underset{l \to \infty}{l i m} \frac{| | x_{i}^{(l + 1)} - x_{i}^{*} | |}{| | x_{i}^{(l)} - x_{i}^{*} | |} = \underset{l \to \infty}{l i m} \frac{| | (1 + g) \times x_{i}^{(l)} - x_{i}^{*} | |}{| | x_{i}^{(l)} - x_{i}^{*} | |}

（17）

对于TFWA有

R_{T F W A}^{(l)} = \underset{l \to \infty}{l i m} \frac{| | x_{i}^{(l + 1)} - x_{i}^{*} | |}{| | x_{i}^{(l)} - x_{i}^{*} | |} = \underset{l \to \infty}{l i m} \frac{| | (1 + t (l)) \times x_{i}^{(l)} - x_{i}^{*} | |}{| | x_{i}^{(l)} - x_{i}^{*} | |}

（18）

对于FWA，分子部分为

| | (1 + g) \times x_{i}^{(l)} - x_{i}^{*} | |

，其中g是满足高斯分布的随机数，由于高斯分布的随机数具有一定的随机性，会产生较大的变异，导致更大的搜索空间扩散，会减慢算法的收敛速度.相比之下TFWA的分子部分为

| | (1 + t (l)) \times x_{i}^{(l)} - x_{i}^{*} | |

，

t (l)

是以算法的迭代次数为自由度的T分布随机变量的取值，取值的大小相对较小，可以减缓搜索空间的扩散，有助于加快算法的收敛速度.

其次，从选择策略角度来看，轮盘赌法仅根据概率分布选择，容易导致种群陷入局部最优解.相比之下，适应度选择策略具有更好的搜索空间探索能力和优秀解保留能力，因此能够更快地收敛到全局最优解.

综上所述，TFWA的收敛速度比FWA的更快.

证毕.

3.3 TFWA时间复杂度分析

TFWA的时间复杂度主要由变异阶段和选择阶段两部分组成.假设种群规模为N，最大迭代次数为L.

（1）变异阶段

选择

p

个个体进行一次自适应T分布变异.假设自适应T分布变异的时间复杂度为

O (e)

，则该阶段的时间复杂度为：

O (p \times e)

（2）选择阶段

计算每个个体的适应度，并根据适应度大小进行选择.假设适应度函数的时间复杂度为

O (f)

，则计算每个个体的适应度的时间复杂度为：

O (N \times f)

，还需要进行适应度选择策略，对每个个体进行选择操作.假设适应度选择的时间复杂度为

O (h)

，则选择阶段的时间复杂度为：

O (N \times (f + h))

因此，TFWA的总时间复杂度为

O (p \times e + N \times (f + h))

（19）

其中，

e

、

f

和

h

分别表示自适应T分布变异、适应度计算和适应度选择的时间复杂度.

3.4 改进的T分布烟花-粒子群算法

TFWA具有全局搜索能力，能探索到更广的解空间，避免陷入局部最优解，为进一步提高收敛性，考虑到PSO具有全局收敛性良好的特点，因此本文将TFWA与PSO进行结合，提出一种TFWA-PSO算法，将TFWA中的爆炸操作、变异操作和改进的选择策略引入到PSO中，来提高搜索效率.

3.4.1 改进的速度更新公式

利用烟花爆炸的思想，将算法中的爆炸操作、变异操作结合到粒子群算法中，在粒子的周围爆炸生成新的粒子，并将新生成的粒子的适应度

f_{b e s t}^{(l)}

与粒子的历史最优值

p_{b e s t}^{(l)}

进行比较，选择适应度最优秀的粒子，设

ω

表示惯性权重，

c_{1}

、

c_{2}

表示学习因子，

r_{1}

、

r_{2}

为［0，1］内的随机数^［17］，更新速度公式为

V_{i}^{(l + 1)} = ω V_{i}^{(l)} + c_{1} r_{1} (x_{p l a t e r}^{(l)} - x_{i}^{(l)}) + c_{2} r_{2} (x_{g b e s t}^{(l)} - x_{i}^{(l)})

（20）

其中

x_{p l a t e r}^{(l)} = \{\begin{array}{l} x_{f_{b e s t}^{(l)}}, f_{b e s t}^{(l)} < p_{b e s t}^{(l)} \\ x_{p_{b e s t}^{(l)}}, f_{b e s t}^{(l)} > p_{b e s t}^{(l)} \end{array}

（21）

x_{p l a t e r}^{(l)}

为当前粒子因爆炸和变异产生的新粒子和该粒子的历史最优位置中更为优秀的位置，

x_{g b e s t}^{(l)}

表示当前的全局最优位置.

3.4.2 改进适应度函数

在迭代寻找最优路径的过程中，需要一个适应度函数来对其进行约束，从而得到最优的路径.本节针对路径长度、能量消耗和路径平滑度3个指标提出改进的适应度函数，对生成的路径进行评价.

（1）路径长度

设起点和目标点的坐标分别为

P_{0} (x_{0}, y_{0})

、

P_{n + 1} (x_{n + 1}, y_{n + 1})

，设

P_{i} (x_{i}, y_{i}), i = 1, \dots, n

为路径上的节点，则路径长度为

f_{l e n g t h} = \sum_{i = 0}^{n} ‖P_{i + 1} - P_{i}‖ = \sum_{i = 0}^{n} \sqrt[]{(x_{i + 1} - x_{i})^{2} + (y_{i + 1} - y_{i})^{2}}

（22）

（2）能量消耗

假设本文中的AUV以匀速运动，推进器产生的推力与水阻力相等.根据水动力公式，可以求得AUV在匀速航行状态下的航行速度

v

.本文简化计算，忽略了除推进器外的其它能耗，AUV消耗的能量主要用于克服水阻力做功，可以用式（23）表示

f_{e n e r g y} = C ρ v^{2} s L_{l e n g t h} / (2 η)

（23）

其中C为水动力系数，

ρ

为水的密度，

η

为机械效率，

s

为AUV的横截面积.

（3）路径平滑度

引入路径平滑度来衡量AUV路径的平滑程度.设第i个路径点相邻路径形成的夹角为

Φ_{ι}

，则路径平滑度

f_{s m o o t h}

的计算如下

f_{s m o o t h} = \sum_{i = 1}^{n} Φ_{ι} = \sum_{i = 1}^{n} a r c c o s (\frac{(P_{i} - P_{i - 1}) \times (P_{i + 1} - P_{i})}{|P_{i} - P_{i - 1}| |P_{i + 1} - P|})

（24）

综上所述，设

β_{1} 、 β_{2}

和

β_{3}

分别表示

f_{l e n g t h}

、

f_{e n e r g y}

和

f_{s m o o t h}

所占比重的权重因子，

\sum_{i = 1}^{3} β_{i} = 1

，则本文构建的适应度函数如下

f (x) = β_{1} f_{l e n g t h} + β_{2} f_{e n e r g y} + β_{3} f_{s m o o t h}

（25）

3.4.3 TFWA-PSO收敛性分析

为了更好地评估TFWA-PSO的收敛性提出定理3.

定理3 设

l

为当前的迭代次数，

x_{i}^{(l)}

为粒子

i

在第

l

次迭代时的位置，

x^{*}

为粒子全局最优解的位置，随着

l

的增加，TFWA-PSO能够逐渐收敛到全局最优解，即

\underset{l \to L}{l i m} x_{i}^{(l)} = x^{*}

证明由于TFWA-PSO在每次迭代过程中都采用适应度非递增的精英保留策略，因此TFWA-PSO每次迭代后都保留了种群最佳位置，即

x_{i}^{(l)} = \{\begin{array}{l} x_{i}^{(l)}, f (x_{i}^{(l)}) \leq f (x_{i}^{(l - 1)}) \\ x_{i}^{(l - 1)}, f (x_{i}^{(l)}) > f (x_{i}^{(l - 1)}) \end{array}

（26）

随着迭代次数

l

的增加，粒子的适应度逐渐趋近于全局最优解的适应度，即

\underset{l \to L}{l i m} f (x_{i}^{(l)}) = \underset{l \to L}{l i m} f (x^{*})

.其中

f (x_{i}^{(l)}) = m i n {f (x_{i}^{(l)}), f (x_{i}^{(l - 1)})}

（27）

在TFWA-PSO中，使用了自适应T分布变异和适应度选择策略来改进粒子群算法的搜索能力，因此可将式（20）作为TFWA-PSO的速度更新公式，粒子

i

的位置更新公式表示为

x_{i}^{(l + 1)} = x_{i}^{(l)} + v_{i}^{(l + 1)}

（28）

假设在

l

时刻，所有粒子的位置都处于全局最优解附近，即

x_{i}^{(l)} = x^{*}, i = 1,2, \dots, n

（29）

由式（20）可以看出，当粒子的位置在全局最优解附近时，

x_{p l a t e r}^{(l)}

和

x_{g b e s t}^{(l)}

与

x_{i}^{(l)}

的差异很小，即

c_{1} r_{1} (x_{p l a t e r}^{(l)} - x_{i}^{(l)})

和

c_{2} r_{2} (x_{g b e s t}^{(l)} - x_{i}^{(l)})

趋于0，从而使

ω V_{i}^{(l)}

对速度更新的影响占主导，其中

ω

是一个常数，所以在全局最优解附近，大部分粒子的速度逐渐趋于恒定.因此假设粒子i在第l+1次迭代时的速度可以表示为

v_{i}^{(l + 1)} = v^{*}, i = 1,2, \dots, n

（30）

其中

v^{*}

表示全局最优解的速度.

将式（29）和式（30）代入到式（28）中，可以得出

x_{i}^{(l + 1)} = x^{*} + v^{*}

（31）

假设粒子

i

第

l

次迭代的误差

ε_{i} (l)

定义为

ε_{i} (l) = f (x_{i}^{(l)}) - f (x^{*})

（32）

其中

f (x_{i}^{(l)})

和

f (x^{*})

是粒子

x_{i}^{(l)}

和

x^{*}

的适应度，将其代入到式（32）中，得到

ε_{i} (l + 1) = f (x_{i}^{(l + 1)}) - f (x^{*}) = f (x^{*} + v^{*}) - f (x^{*})

（33）

使用泰勒级数展开，可以得出

f (x^{*} + v^{*}) = f (x^{*}) + \nabla f (x^{*})^{T} v^{*} + \frac{1}{2} {v^{*}}^{T} H (x^{*}) v^{*}

（34）

其中

\nabla f (x^{*})

是目标函数在

x^{*}

的梯度，

H (x^{*})

是目标函数在

x^{*}

的Hessian矩阵.

将

f (x^{*} + v^{*})

代入到式（33）中，得到

ε_{i} (l + 1) = \nabla f (x^{*})^{T} v^{*} + (1 / 2) {v^{*}}^{T} Η (x^{*}) v^{*}

（35）

使用Cauchy-Schwarz不等式得出

| \nabla f (x^{*})^{T} v^{*} | \leq | | \nabla f (x^{*}) | | \times | | v^{*} | |

（36）

将不等式代入误差方程，得到

ε_{i} (l + 1) \leq | | \nabla f (x^{*}) | | | \times | | v^{*} | | + \frac{1}{2} | | v^{*} | |^{2} \times | | H (x^{*}) | |

（37）

利用三角形不等式和

| | v^{*} | |

是一个常数，可以写出

ε_{i} (l + 1) \leq ε_{i} (l) + | | \nabla f (x^{*}) | | | \times | | v^{*} | | + \frac{1}{2} | | v^{*} | |^{2} | | H (x^{*}) | |

（38）

第l+1次迭代时的误差由第l次迭代的误差加上一个常数，这个常数取决于目标函数的梯度和Hessian矩阵，以及全局最优解的恒定速度.因此，随着迭代次数的增加，误差逐渐减小，即随着迭代次数的增加，TFWA-PSO逐渐收敛到全局最优解.

证毕.

4 仿真实验

本文在MATLAB的R2017b版本上进行了路径规划的仿真测试，选取了4个不同规模的环境，设置实验最大迭代次数T为100，种群数N为50，将本文提出的改进算法TFWA-PSO与4种最新的高效率优化算法（APF-RRT（Artificial Potential Field-Rapidly-exploring Random Tree）^［18］、APFWA（Add Pioneers Firework Algorithm）^［19］、AGA（Adaptive Genetic Algorithm）^［20］和IWOA（Improved Whale Optimization Algorithm）^［21］）进行对比验证.

TFWA-PSO的基本参数为：爆炸火花数

M

=10，最大爆炸幅度

\hat{A}

=15，最大火花数

a

=0.2，最小火花数

b

=0.8，学习因子

c_{1} = c_{2}

=2，权重系数

ω

=0.9.在其它实验参数保持不变的前提下，通过改变k的值，对路径长度和搜索时间进行了计算，结果如图4所示.

图4 参数k与路径长度的关系

Full size|PPT slide

4.1 简单环境下路径规划

为验证TFWA-PSO在简单环境中求解路径规划问题的优越性，在图5所示的空间中加入了一定数量的障碍物，其中蓝色多边形为障碍物区域，白色区域为可行区域.5种算法的路径规划结果如图5所示，统计数据如表1所示.

图5 简单环境下路径规划对比图

(a) 环境1 (b) 环境2 (c) 环境3 (d) 环境4

Full size|PPT slide

表1 低覆盖率环境下5种算法仿真数据对比

环境	指标	TFWA-PSO	APF-RRT	APFWA	AGA	IWOA
环境1	路径长度/km	37.312	41.645	40.153	50.12	48.471
	搜索时间/s	11.880 7	17.12	12.144 6	14.210 2	21.131
	平均能耗/kJ	159.942	175.825	182.974	195.73	201.1
环境2	路径长度/km	49.282	57.272	59.200	71.381	68.037
	搜索时间/s	13.920 3	16.379	16.083 1	20.35	22.314 3
	平均能耗/kJ	167.817	189.716	192.321	197.241	190.35
环境3	路径长度/km	67.729	73.219	76.022	89.261	91.489
	搜索时间/s	16.902 1	22.701	18.921 2	23.101	25.147
	平均能耗/kJ	246.368	278.891	280.281	299.435	307.397
环境4	路径长度/km	73.565	74.975	78.21	93.33	90.32
	搜索时间/s	20.504	26.533	23.246	27.304 7	26.489 6
	平均能耗/kJ	291.069	296.551	310.034	350.093	348.321

根据表1，TFWA-PSO的路径长度在4种环境中最短.在环境1中，比APF-RRT和APFWA分别缩短了7.3%和9.5%，在环境3中，其平均能耗比其它算法显著降低，减少幅度达13.2%至24.77%.在搜索时间方面，TFWA-PSO明显少于其它算法.这是因为TFWA-PSO结合了PSO和烟花爆炸操作，具有高效的全局搜索能力，通过合理设置粒子的速度和位置更新规则，TFWA-PSO能快速找到最优解.

相比之下，其它算法在全局搜索能力上存在局限性，导致搜索时间较长.因此TFWA-PSO解决了PSO在全局路径规划中存在的寻优时间长和能耗高的问题，能够更经济高效地执行路径规划任务，减少AUV的能量消耗.在图5的4种环境中，APF-RRT、AGA和IWOA算法的路径存在过多转折点的问题，导致AUV频繁转向.相比之下，TFWA-PSO规划的路径更平滑，消除了拐角，这得益于贝塞尔曲线的平滑特性和良好拟合能力.在图5（a）和图5（b）中，AGA算法的拐点数量最多，路径长度最长，性能最差.尽管APF-RRT和IWOA算法的拐点数量减少，但路径长度仍超过TFWA-PSO.综上所述，TFWA-PSO在4种环境下展现出了较好的寻优性能和稳定性.

4.2 复杂环境下路径规划

为验证5种算法在复杂环境中路径规划的能力，利用Otsu方法得到地图的自适应阈值，将数字地图和卫星地图转换为二进制地图.图6展示了5种算法在二进制地图上的路径，蓝色和紫色的星星分别表示起点和目标点.

图6 4种二进制地图下对比算法的路径规划图

(a) 地图1 (b) 地图2 (c) 地图3 (d) 地图4

Full size|PPT slide

在图6（a）中，APF-RRT的拐点最多，导致路径曲折性增加，增加了能量消耗和路径延迟的风险.其它3种算法能够平滑到达目标点，表现较好.图6（b）~6（d）显示，AGA在4种海洋环境中的路径长度最长，且拐点较多，容易出现频繁转向的问题.相比之下，APFWA在这些海洋环境中路径较为平滑，表现较稳定，而TFWA-PSO的路径既平滑且长度最短.因此，相比其它4种算法，TFWA-PSO不仅展示出了最短的路径长度，还能够顺利到达目标点.

4.3 TFWA-PSO寻优能力评估

本文选取12个基准测试函数评估了5种算法寻优能力，包括单峰测试函数和多模态高维测试函数，用于测试算法的全局和局部的寻优能力.其中每个函数被独立模拟了30次，以获取平均值和标准差.数据结果如表2所示，表格中黑体字表示最佳结果，图7展示了在解决不同函数问题时，5种算法的收敛性能，该4种函数具有不同的问题结构和特征，可以全面评估算法在不同类型函数上的寻优能力.

表2 测试算法在基准测试函数上的实验结果

函数	指标	TFWA-PSO	APF-RRT	APFWA	AGA	IWOA
$f_{1} (x)$	平均值	$1.841 \times 10^{- 27}$	$2.357 6 \times 10^{- 4}$	$8.694 8 \times 10^{2}$	$1.681 \times 10^{- 4}$	$1.517 5 \times 10^{- 5}$
$f_{1} (x)$	标准差	$7.535 5 \times 10^{- 27}$	$3.592 5 \times 10^{- 4}$	$4.964 1 \times 10^{2}$	$7.645 3 \times 10^{- 5}$	$1.011 1 \times 10^{- 5}$
$f_{2} (x)$	平均值	$1.396 6 \times 10^{- 16}$	$9.207 3 \times 10^{- 2}$	$7.255 8 \times 10^{11}$	$3.994 7 \times 10^{- 5}$	$9.424 3 \times 10^{- 6}$
$f_{2} (x)$	标准差	$9,306 2 \times 10^{- 17}$	$9.668 5 \times 10^{- 2}$	$1.906 4 \times 10^{12}$	$5.424 1 \times 10^{- 5}$	$4.646 8 \times 10^{- 6}$
$f_{3} (x)$	平均值	$2.282 5 \times 10^{- 8}$	$6.731 3 \times 10^{- 7}$	$4.225 3 \times 10^{- 6}$	$8.111 1 \times 10^{- 4}$	$4.664 9 \times 10^{- 5}$
$f_{3} (x)$	标准差	$2.791 5 \times 10^{- 8}$	$3.051 6 \times 10^{- 6}$	$7.513 \times 10^{- 6}$	$6.988 5 \times 10^{- 5}$	$3.967 1 \times 10^{- 6}$
$f_{4} (x)$	平均值	$5.551 1 \times 10^{- 13}$	$- 5.023 7 \times 10^{- 28}$	65.843	$5.330 2 \times 10^{- 21}$	$1.210 3 \times 10^{- 7}$
$f_{4} (x)$	标准差	$2.453 5 \times 10^{- 12}$	$- 2.093 5 \times 10^{- 28}$	32.564	$4.789 7 \times 10^{- 20}$	$1.079 2 \times 10^{- 6}$
$f_{5} (x)$	平均值	$27.09$	78.591	$1.161 3 \times 10^{6}$	$1.399 8 \times 10^{2}$	$4.778 8 \times 10^{2}$
$f_{5} (x)$	标准差	43.252	19.137	$2.402 5 \times 10^{4}$	$1.192 3 \times 10^{3}$	92.772
$f_{6} (x)$	平均值	$3.075 4 \times 10^{- 5}$	$9.021 5 \times 10^{- 3}$	$7.852 6 \times 10^{2}$	$1.566 \times 10^{2}$	80.883
$f_{6} (x)$	标准差	$6.359 \times 10^{- 5}$	$3.132 \times 10^{- 3}$	$2.852 7 \times 10^{2}$	$8.088 3 \times 10^{2}$	$9.615 7 \times 10^{2}$
$f_{7} (x)$	平均值	$4.310 3 \times 10^{- 5}$	$4.118 \times 10^{- 3}$	$2.267 3 \times 10^{- 3}$	$7.493 8 \times 10^{- 4}$	$1.825 \times 10^{- 4}$
$f_{7} (x)$	标准差	$2.842 2 \times 10^{- 4}$	$1.502 1 \times 10^{- 3}$	$6.438 3 \times 10^{4}$	$2.246 2 \times 10^{- 2}$	$1.558 \times 10^{- 1}$ 0
$f_{8} (x)$	平均值	$6.282 2 \times 10^{- 6}$	$5.085 1 \times 10^{- 3}$	$5.665 4 \times 10^{- 5}$	$6.762 7 \times 10^{- 4}$	$1.152 5 \times 10^{- 3}$
$f_{8} (x)$	标准差	$1.165 7 \times 10^{- 3}$	$1.132 4 \times 10^{- 2}$	$2.417 6 \times 10^{- 3}$	$4.312 8 \times 10^{- 3}$	$6.231 4 \times 10^{- 3}$
$f_{9} (x)$	平均值	$7.678 \times 10^{- 8}$	$5.031 5 \times 10^{- 4}$	$1.606 1 \times 10^{- 6}$	$8.040 7 \times 10^{- 9}$	$4.224 9 \times 10^{- 3}$
$f_{9} (x)$	标准差	$2.098 1 \times 10^{- 8}$	$3.137 4 \times 10^{- 4}$	$5.665 4 \times 10^{- 5}$	$1.727 8 \times 10^{- 10}$	$7.566 \times 10^{- 3}$
$f_{10} (x)$	平均值	$1.551 8 \times 10^{- 18}$	$1.891 \times 10^{- 17}$	$1.719 1 \times 10^{- 7}$	$9.758 2 \times 10^{- 6}$	$1.567 3 \times 10^{- 5}$
$f_{10} (x)$	标准差	$3.055 1 \times 10^{- 17}$	$4.526 4 \times 10^{- 17}$	$3.380 2 \times 10^{- 7}$	$5.679 1 \times 10^{- 6}$	$4.459 9 \times 10^{- 5}$
$f_{11} (x)$	平均值	$3.744 6 \times 10^{- 7}$	$2.963 9 \times 10^{- 6}$	11.214	$8.911 1 \times 10^{- 9}$	$3.821 7 \times 10^{- 7}$
$f_{11} (x)$	标准差	$3.736 1 \times 10^{- 5}$	$2.400 6 \times 10^{- 6}$	$2.432 3 \times 10^{2}$	$1.875 8 \times 10^{- 8}$	$5.202 7 \times 10^{- 9}$
$f_{12} (x)$	平均值	$1.606 5 \times 10^{- 8}$	$5.036 9 \times 10^{- 4}$	$7.678 \times 10^{- 6}$	$2.600 2 \times 10^{- 5}$	$1.807 6 \times 10^{- 6}$
$f_{12} (x)$	标准差	$2.099 1 \times 10^{- 8}$	$3.11 \times 10^{- 4}$	$1.630 4 \times 10^{- 5}$	$4.571 4 \times 10^{- 6}$	$1.786 5 \times 10^{- 7}$

图7 不同测试函数下算法收敛对比图

Full size|PPT slide

表2显示，当解决单峰问题时，TFWA-PSO在大多数测试函数上提供最佳的性能，特别是在

f_{1} (x)

、

f_{2} (x)

、

f_{3} (x)

和

f_{6} (x)

上精度最高，全局寻优能力很强，这是由于在算法初期，自由度较小和T分布的特性，使得解更加分散，探索范围更广，改进的选择策略也加快了种群向更优解聚集，降低适应度差个体被选择的概率.尽管AGA在

f_{4} (x)

和

f_{9} (x)

上的性能优于TFWA-PSO，但在其它函数上的均值解均比TFWA-PSO差.其中APF-RRT在

f_{4} (x)

上的平均值为负数，这说明其在搜索过程中遇到困难，未能找到全局最优解，生成了一个较差的解，因此APF-RRT的全局搜索能力较差，易陷入局部最优.单峰函数

f_{1} (x) ~ f_{6} (x)

的测试结果表明，TFWA-PSO具备更强的全局寻优能力，能较好地在解空间中找到最优解，有效避免陷入局部最优.

在多模态高维测试函数的仿真中，相对于其它4种算法，TFWA-PSO在求解均值和稳定性上都取得了较好的优化结果.这是因为随着迭代次数的增加，T分布逐渐趋近于高斯分布，算法更注重局部范围内的精细调整和优化，以更快地接近全局最优解.由于多模态高维测试函数具有许多局部最优解，根据表2的测试结果可以得出，TFWA-PSO具有更强的局部寻优能力.

表2中可以看到算法在测试函数上运行30次后，TFWA-PSO的标准差除了在

f_{4} (x)

、

f_{5} (x)

、

f_{9} (x)

和

f_{11} (x)

上大于APF-RRT、AGA和IWOA，其余均小于其它4种算法，说明TFWA-PSO与另外4种算法相比具有较强的稳定性.

图7展示了在4种测试函数中，5种算法的函数值随迭代次数的增加而减小，特别是在

f_{3} (x)

中，TFWA-PSO虽然迭代次数较多，但下降的速度最快，寻优性能最好.在

f_{7} (x)

中，APF-RRT和TFWA-PSO均表现良好，但APF-RRT迭代速度慢且不稳定.在

f_{6} (x)

和

f_{12} (x)

中，TFWA-PSO虽收敛速度较慢，但寻优性能最佳.相比之下，APF-RRT和IWOA虽收敛快，但易受局部最优解限制.总体来看，TFWA-PSO虽收敛速度慢，但在寻优能力上优于其它算法，能找到更优的路径.

5 总结

针对AUV避障路径规划问题，本文提出了一种将烟花算法与粒子群算法融合的TFWA-PSO算法.首先使用三角形法进行海底环境建模；其次，鉴于基本烟花算法存在局部最优解的问题，提出了自适应T分布变异以及通过改进选择策略来选择适应度更好的个体，并从理论上对算法的搜索范围、收敛速度以及收敛性进行了证明；最后，将改进的T分布烟花算法融合到粒子群算法中，解决粒子群算法在迭代过程易陷入局部最优的问题.仿真结果可以看出：本文改进的算法比另外4种算法得到的路径在搜索时间和能耗等方面有明显提升，且转折点个数大大减少，在需要高效、能耗管理的路径规划应用中表现较好，可以快速地寻找到最优的路径，然而，由于本文所研究的障碍物均为静态，TFWA-PSO在动态障碍物环境下缺乏对障碍物迅速变化的响应能力，从而导致算法在动态障碍物环境下存在避障不足的缺点.因此在未来的研究中，我们应着重关注解决动态障碍物带来的挑战，以提高算法的实用性和适应性.

References

Publishing order | Descend order by publishing year | Descend order by cited within

1	陈嘉兴, 程杰, 董云玲, 等. 基于弯曲声线和测距修正的水下节点定位算法[J]. 电子学报, 2022, 50(7):1567-1572. CHENG J X, CHENG J, DONG Y L, et al. Underwater node localization algorithm based on ranging correction and curved sound ray[J]. Acta Electronica Sinica, 2022, 50(7):1567-1572. (in Chinese) Cited in this article [1]

郝诗雅, 杨媛媛, 董怡靖, 等.水声传感器网络中粒子群与蒙特卡罗优化的移动定位算法[J]. 电子学报, 2021, 49(2):292-299.

HAO

S Y

, YANG

Y Y

, DONG

Y J

, et al. Particle swarm and monte carlo optimized mobile localization algorithm in underwater acoustic sensor networks[J]. Acta Electronica Sinica, 2021, 49(2):292-299. (in Chinese)

Cited in this article [1]

3	ZENG Z, LAMMAS A, SAMMUT K, et al. Shell space decomposition based path planning for AUVs operating in a variable environment[J]. Ocean Engineering, 2014, 91: 181-195. Cited in this article [1]

4	MA Y N, GONG Y J, XIAO C F, et al. Path planning for autonomous underwater vehicles: An ant colony algorithm incorporating alarm pheromone[J]. IEEE Transactions on Vehicular Technology, 2019, 68(1): 141-154. Cited in this article [1]

5	CAO Y, WEI W Y, BAI Y, et al. Multi-base multi-UAV cooperative reconnaissance path planning with genetic algorithm[J]. Cluster Computing, 2019, 22(3): 5175-5184. Cited in this article [1]

6	张瀚彬, 史先鹏, 刘喜梅. 基于改进量子粒子群算法的AUV路径规划研究[J]. 海洋工程, 2023, 41(2): 86-92. ZHANG H B, SHI X P, LIU X M. An AUV path planning method based on improved quantum particle swarm optimization[J]. The Ocean Engineering, 2023, 41(2): 86-92. (in Chinese) Cited in this article [1]

7	LI X H, YU S H. Three-dimensional path planning for AUVs in ocean currents environment based on an improved compression factor particle swarm optimization algorithm[J]. Ocean Engineering, 2023, 280: 114610. Cited in this article [1]

8	胡致远, 王征, 杨洋, 等. 基于人工鱼群-蚁群算法的UUV三维全局路径规划[J]. 兵工学报, 2022, 43(7): 1676-1684. HU Z Y, WANG Z, YANG Y, et al. Three-dimensional global path planning for uuv based on artificial fish swarm and ant colony algorithm[J]. Acta Armamentarii, 2022, 43(7): 1676-1684. (in Chinese) Cited in this article [1]

9	WU J H, SONG C X, MA J, et al. Reinforcement learning and particle swarm optimization supporting real-time rescue assignments for multiple autonomous underwater vehicles[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(7): 6807-6820. Cited in this article [1]

10	HU Y J, WANG J, HE H J, et al. Three-dimensional marine ranching cage inspection path planning integrating the differential evolution and particle swarm optimization algorithms[J]. IEEE Access, 2023, 11: 109747-109763. Cited in this article [1]

11	胡章芳, 冯淳一, 罗元. 改进粒子群优化算法的移动机器人路径规划[J]. 计算机应用研究, 2021, 38(10): 3089-3092. HU Z F, FENG C Y, LUO Y. Improved particle swarm optimization algorithm for mobile robot path planning[J]. Application Research of Computers, 2021, 38(10): 3089-3092. (in Chinese) Cited in this article [1]

12	朱佳莹, 高茂庭. 融合粒子群与改进蚁群算法的AUV路径规划算法[J]. 计算机工程与应用, 2021, 57(6): 267-273. ZHU J Y, GAO M T. AUV path planning based on particle swarm optimization and improved ant colony optimization[J]. Computer Engineering and Applications, 2021, 57(6): 267-273. (in Chinese) Cited in this article [1]

13	SUI F L, TANG X K, DONG Z H, et al. ACO+PSO+A*: A bi-layer hybrid algorithm for multi-task path planning of an AUV[J]. Computers & Industrial Engineering, 2023, 175: 108905. Cited in this article [1]

陈秋莲, 郑以君, 蒋环宇, 等. 基于神经网络改进粒子群算法的动态路径规划[J]. 华中科技大学学报(自然科学版), 2021, 49(2): 51-55.

CHEN

Q L

, ZHENG

Y J

, JIANG

H Y

, et al. Improved particle swarm optimization algorithm based on neural network for dynamic path planning[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2021, 49(2): 51-55. (in Chinese)

Cited in this article [1]

15	郗安民, 王琦, 孙学彬. 一种有效的地图创建方法和机器人的路径规划[J]. 机械设计, 2010, 27(1): 35-38. XI A M, WANG Q, SUN X B. A kind of effective map creation method and path planning of robot[J]. Journal of Machine Design, 2010, 27(1): 35-38. (in Chinese) Cited in this article [1]

16	魏振春, 傅宇,马仲军,等.带时间窗的无线可充电传感器网络多目标路径规划算法[J]. 电子学报, 2022, 50(8): 1819-1829. WEI Z C, FU Y, MA Z J, et al. Multi-objective path planning algorithm for WRSN with time window[J]. Acta Electronica Sinica, 2022, 50(8): 1819-1829. (in Chinese) Cited in this article [1]

17	黄湘松, 于日龙, 潘大鹏. 面向目标定位精度的主从式无人机编队航迹规划方法[J]. 电子学报, 2023, 51(9): 2289-2300. HUANG X S, YU R L, PAN D P. Route planning method of master-slave UAV formation for target positioning accuracy[J]. Acta Electronica Sinica, 2023, 51(9): 2289-2300. (in Chinese) Cited in this article [1]

18	XIE C X, WANG Y, LIU Y F, et al. An AUV path planning method based on improved APF-RRT[C]//2023 IEEE International Conference on Mechatronics and Automation (ICMA). Piscataway: IEEE, 2023: 1190-1195. Cited in this article [1]

张玮, 马焱, 赵捍东, 等. 基于改进烟花-蚁群混合算法的智能移动体避障路径规[J]. 控制与决策, 2019, 34(2): 335-343.

ZHANG

, MA

, ZHAO

H D

, et al. Obstacle avoidance path planning of intelligent mobile based on improved fireworks-ant colony hybrid algorithm[J]. Control and Decision, 2019, 34(2): 335-343. (in Chinese)

Cited in this article [1]

20	HAO K, ZHAO J L, LI Z S, et al. Dynamic path planning of a three-dimensional underwater AUV based on an adaptive genetic algorithm[J]. Ocean Engineering, 2022, 263: 112421. Cited in this article [1]

21	李广强, 董文超, 朱大庆, 等. 基于改进鲸鱼优化算法的AUV三维路径规划[J]. 系统工程与电子技术, 2023, 45(7): 2170-2182. LI G Q, Dong W C, ZHU D Q, et al. 3D path planning for AUV based on improved whale optimization algorithm[J]. Systems Engineering and Electronics, 2023, 45(7): 2170-2182. (in Chinese) Cited in this article [1]

Funding

National Natural Science Foundation of China(62171179)

PDF(6319 KB)

3304

Accesses

Citation

Detail

Sections

Recommended

Abstract
Key words
Cite this article
1 引言
2 问题描述
图1 水下AUV全局路径规划示意图
2.1 环境建模及路径初始化
图2 水下三角形法环境建模图
2.2 传统烟花算法FWA
（1）爆炸操作：在FWA中，烟花 x i ( l )的爆炸半径 A i ( l )和爆炸产生的火花数目 S i ( l )是根据烟花种群中其它烟花适应度计算得到的，计算公式分别为［16］
（2）高斯变异操作：FWA引入了高斯变异来增加种群中烟花的多样性，在种群 X ( l )中随机选择 p ( 1 ≤ p ≤ N )个烟花进行高斯变异，产生个数为 p的高斯变异火花集合 Z ( l ) = { z 1 ( l ) , ⋯ , z h ( l ) , ⋯ , z p ( l ) }， z h ( l )表达如下
（3）映射规则：第 i个烟花爆炸后产生的第 j个火花 y i , j ( l )和高斯变异火花 z h ( l )可能会超出可行域范围，需要通过映射规则重新映射回可行域内，公式如下
（4）选择策略：在第 l次迭代的最后，烟花算法要从集合 W ( l ) = X ( l ) ⋃ Y i ( l ) ⋃ Z ( l ) = { w i ( l ) }中通过轮盘赌法选择概率 p ( w i ( l ) )最大的前N-1个个体作为下一代烟花
3 改进T分布烟花算法TFWA的路径规划
3.1 TFWA
（1）改进变异操作
图3 高斯分布和柯西分布图像的比较
（2）改进选择策略
3.2 TFWA收敛速度分析
3.3 TFWA时间复杂度分析
（1）变异阶段
（2）选择阶段
3.4 改进的T分布烟花-粒子群算法
3.4.1 改进的速度更新公式
3.4.2 改进适应度函数
（1）路径长度
（2）能量消耗
（3）路径平滑度
3.4.3 TFWA-PSO收敛性分析
4 仿真实验
图4 参数k与路径长度的关系
4.1 简单环境下路径规划
图5 简单环境下路径规划对比图
表1 低覆盖率环境下5种算法仿真数据对比
4.2 复杂环境下路径规划
图6 4种二进制地图下对比算法的路径规划图
4.3 TFWA-PSO寻优能力评估
表2 测试算法在基准测试函数上的实验结果
图7 不同测试函数下算法收敛对比图
5 总结
References
Funding

Received	Revised	Published
2023-08-26	2024-01-06	2024-09-25
Issue Date
2024-10-29

模态框（Modal）标题

Please choose a citation manager

Content to export

Abstract

Key words

Cite this article

1 引言

2 问题描述

图1 水下AUV全局路径规划示意图

2.1 环境建模及路径初始化

图2 水下三角形法环境建模图

2.2 传统烟花算法FWA

（1） 爆炸操作：在FWA中，烟花 xi(l)的爆炸半径 Ai(l)和爆炸产生的火花数目 Si(l)是根据烟花种群中其它烟花适应度计算得到的，计算公式分别为［16］

（2） 高斯变异操作：FWA引入了高斯变异来增加种群中烟花的多样性，在种群 X(l)中随机选择 p(1≤p≤N)个烟花进行高斯变异，产生个数为 p的高斯变异火花集合 Z(l)={z1(l),⋯,zh(l),⋯,zp(l)}， zh(l)表达如下

（3） 映射规则：第 i个烟花爆炸后产生的第 j个火花 yi,j(l)和高斯变异火花 zh(l)可能会超出可行域范围，需要通过映射规则重新映射回可行域内，公式如下

（4） 选择策略：在第 l次迭代的最后，烟花算法要从集合 W(l)=X(l)⋃Yi(l)⋃Z(l)={wi(l)}中通过轮盘赌法选择概率 p(wi(l))最大的前N-1个个体作为下一代烟花

3 改进T分布烟花算法TFWA的路径规划

3.1 TFWA

（1） 改进变异操作

图3 高斯分布和柯西分布图像的比较

（2） 改进选择策略

3.2 TFWA收敛速度分析

3.3 TFWA时间复杂度分析

（1） 变异阶段

（2） 选择阶段

3.4 改进的T分布烟花-粒子群算法

3.4.1 改进的速度更新公式

3.4.2 改进适应度函数

（1） 路径长度

（2） 能量消耗

（3） 路径平滑度

3.4.3 TFWA-PSO收敛性分析

4 仿真实验

图4 参数k与路径长度的关系

4.1 简单环境下路径规划

图5 简单环境下路径规划对比图

表1 低覆盖率环境下5种算法仿真数据对比

4.2 复杂环境下路径规划

图6 4种二进制地图下对比算法的路径规划图

4.3 TFWA-PSO寻优能力评估

表2 测试算法在基准测试函数上的实验结果

图7 不同测试函数下算法收敛对比图

5 总结

{{custom_sec.title}}

{{custom_sec.title}}

References

{{custom_fnGroup.title_en}}

Footnotes

Funding

（1）爆炸操作：在FWA中，烟花 $x_{i}^{(l)}$ 的爆炸半径 $A_{i}^{(l)}$ 和爆炸产生的火花数目 $S_{i}^{(l)}$ 是根据烟花种群中其它烟花适应度计算得到的，计算公式分别为^［16］

（3）映射规则：第 $i$ 个烟花爆炸后产生的第 $j$ 个火花 $y_{i, j}^{(l)}$ 和高斯变异火花 $z_{h}^{(l)}$ 可能会超出可行域范围，需要通过映射规则重新映射回可行域内，公式如下

（4）选择策略：在第 $l$ 次迭代的最后，烟花算法要从集合 $W^{(l)} = X^{(l)} ⋃ Y_{i}^{(l)} ⋃ Z^{(l)} = {w_{i}^{(l)}}$ 中通过轮盘赌法选择概率 $p (w_{i}^{(l)})$ 最大的前N-1个个体作为下一代烟花

（1）改进变异操作

（2）改进选择策略

（1）变异阶段

（2）选择阶段

（1）路径长度

（2）能量消耗

（3）路径平滑度