科学技术与工程

算法1 PPACO
1.建立静态、涡旋、流体动力环境模型 2.初始化惩罚信息素δ_ij、引导信息素τ_ij、蚂蚁数量m、最大迭代次数N_max 3.初始化权重参数 4.for N=1 to N_max do 5. for i=1 to m do 6. 将蚂蚁置于初始点 7. while 蚂蚁k未到达终点 8. 计算启发式函数η_ij、η″_ij和信息素τ'_ij 9. 根据式(25)选择下一位置 10. if 蚂蚁寻路失败 11. 更新惩罚信息素 12. end if 13. if 蚂蚁寻路成功 14. 更新惩罚信息素 15. 更新最优路径 16. end if 17. end while 18. end for 19. 更新全局信息素 20.end for

算法1 PPACO
1.建立静态、涡旋、流体动力环境模型 2.初始化惩罚信息素δ_ij、引导信息素τ_ij、蚂蚁数量m、最大迭代次数N_max 3.初始化权重参数 4.for N=1 to N_max do 5. for i=1 to m do 6. 将蚂蚁置于初始点 7. while 蚂蚁k未到达终点 8. 计算启发式函数η_ij、η″_ij和信息素τ'_ij 9. 根据式(25)选择下一位置 10. if 蚂蚁寻路失败 11. 更新惩罚信息素 12. end if 13. if 蚂蚁寻路成功 14. 更新惩罚信息素 15. 更新最优路径 16. end if 17. end while 18. end for 19. 更新全局信息素 20.end for

ω₁	0	0.5	1	1.5	2	3
F_长度	40.70	40.70	40.70	40.11	40.11	40.70
F_风险	25	18	20	20	17	23
F_航向	405	495	360	225	135	135

ω₁	0	0.5	1	1.5	2	3
F_长度	40.70	40.70	40.70	40.11	40.11	40.70
F_风险	25	18	20	20	17	23
F_航向	405	495	360	225	135	135

ω₂	0	0.5	1	1.5	2	3
F_长度	40.70	40.11	40.11	40.70	41.28	40.70
F_风险	33	24	20	17	16	13
F_航向	540	450	360	495	540	630

ω₂	0	0.5	1	1.5	2	3
F_长度	40.70	40.11	40.11	40.70	41.28	40.70
F_风险	33	24	20	17	16	13
F_航向	540	450	360	495	540	630

算法	F_长度	F_风险	F_航向	迭代次数
传统ACO	47.63	37	900	68
JPS	45.38	25	630	—
双向搜索的改进ACO	42.70	18	675	15
本文算法	40.11	17	135	7

算法	F_长度	F_风险	F_航向	迭代次数
传统ACO	47.63	37	900	68
JPS	45.38	25	630	—
双向搜索的改进ACO	42.70	18	675	15
本文算法	40.11	17	135	7

算法	F_长度	F_风险	F_航向	涡旋影响数量
传统ACO	46.80	30	900	2
双向搜索的改进ACO	41.28	26	540	4
本文算法	40.70	17	135	0

算法	F_长度	F_风险	F_航向	涡旋影响数量
传统ACO	46.80	30	900	2
双向搜索的改进ACO	41.28	26	540	4
本文算法	40.70	17	135	0

参数	数值
ρ_o/(kg·m^-3)	1.225
A_Fc/m²	2.56
A_Lc/m²	7.52
C_Xc	0.52
C_Yc	0.83
M_ship/t	40 000

参数	数值
ρ_o/(kg·m^-3)	1.225
A_Fc/m²	2.56
A_Lc/m²	7.52
C_Xc	0.52
C_Yc	0.83
M_ship/t	40 000

算法	F_长度	F_风险	F_航向	耗时/s
传统ACO	48.46	41	1 080	486.62
双向搜索的改进ACO	42.11	27	675	419.57
本文算法	40.70	20	180	404.90

算法	F_长度	F_风险	F_航向	耗时/s
传统ACO	48.46	41	1 080	486.62
双向搜索的改进ACO	42.11	27	675	419.57
本文算法	40.70	20	180	404.90

基于惩罚信息素蚁群算法的船舶路径规划

PDF下载

杨玉 , 蒋效伟 , 陈若彤 , 徐子瑞 , 戴红伟 ^*

科学技术与工程 | 论文·自动化技术、计算机技术 2025,25(10): 4246-4255

收起

科学技术与工程 | 论文·自动化技术、计算机技术 2025, 25(10): 4246-4255

基于惩罚信息素蚁群算法的船舶路径规划

全屏

杨玉, 蒋效伟, 陈若彤, 徐子瑞, 戴红伟^*

作者信息

江苏海洋大学计算机工程学院, 连云港 222005

杨玉(1979—),女,汉族,江苏扬州人,博士,副教授。研究方向:智能计算、智慧教育。E-mail:yangyu@jou.edu.cn。

通讯作者:

* 戴红伟(1975—),男,汉族,河南新郑人,博士,教授。研究方向:智能计算、最优化问题、复杂网络。E-mail:hwdai@jou.edu.cn。

Punishment Pheromone Based Ant Colony Optimization for Ship Path Planning

Yu YANG, Xiao-wei JIANG, Ruo-tong CHEN, Zi-rui XU, Hong-wei DAI^*

Affiliations

School of Computer Engineering, Jiangsu Ocean University, Liangyungang 222005, China

出版时间: 2025-04-08 doi: 10.12404/j.issn.1671-1815.2403141

文章导航

摘要

收起

针对现有算法求解大规模船舶路径规划问题性能不佳且对涡旋等海洋环境因素考虑较少等问题,提出了一种基于惩罚信息素蚁群优化算法(punishment pheromone ant colony optimization,PPACO)的船舶路径规划方法。首先,设计了长度、风险和航向3个评价函数;其次利用强化学习启发的蚁群优化算法来搜索最优路径,在传统引导信息素的基础上加入了惩罚信息素,可以防止蚂蚁的无效搜索;最后对改进算法进行仿真实验,在静态环境下的规划结果表明,在路径长度、风险值和航向累积角等指标方面,本文算法相比较传统蚁群算法(ant colony optimization,ACO)、跳点搜索算法(jump point search,JPS)和双向搜索的改进蚁群算法表现出更优越的性能,相对于3个对比算法的最好指标,路径长度减少6.1%,风险值降低5.6%,航向积累角减少78.6%,迭代次数减少53.3%,改进显著。特别是在引入了中尺度涡旋和水流运动因素的情况下,本文算法仍能规划出更优的船舶航行路径,有着积极的应用意义。

关键词

船舶路径规划 / 惩罚信息素 / 蚁群算法 / 海洋环境

Abstract

收起

Aiming at the poor performance of existing algorithms in solving large-scale ship path planning problems and the lack of consideration of marine environmental factors such as eddies, a ship path planning method based on punishment pheromone ant colony optimization was proposed. Firstly, three evaluation functions were designed for the planned path: length, risk and heading. Secondly, ACO(ant colony optimization) algorithm inspired by reinforcement learning was designed to search the optimal path, which adds punishment pheromone to the traditional guidance pheromone, which can prevent ants from conducting ineffective searches. Finally, the simulation experiments of the improved algorithm under static environments demonstrate that the proposed algorithm is superior to traditional ACO, jump point search algorithm, and bi-directional search improved ACO in terms of path length, risk value and turn accumulation angle. Compared to the best metrics among these three algorithms, proposed algorithm still achieves a significant improvement in path length reduction of 6.1%, risk value reduction of 5.6%, heading accumulation angle reduction of 78.6%, and iteration number reduction of 53.3%. Especially when the mesoscale eddies and water flow are introduced, the proposed algorithm can still plan a more suitable path for ship navigation, which has positive application significance.

Key words

ship path planning / punishment pheromones / ant colony algorithm / marine environment

引用本文

杨玉, 蒋效伟, 陈若彤, 徐子瑞, 戴红伟. 基于惩罚信息素蚁群算法的船舶路径规划. 科学技术与工程, 2025 , 25 (10) : 4246 -4255 . DOI: 10.12404/j.issn.1671-1815.2403141

Yu YANG, Xiao-wei JIANG, Ruo-tong CHEN, Zi-rui XU, Hong-wei DAI. Punishment Pheromone Based Ant Colony Optimization for Ship Path Planning[J]. Science Technology and Engineering, 2025 , 25 (10) : 4246 -4255 . DOI: 10.12404/j.issn.1671-1815.2403141

正文

收起

船舶路径规划问题是现代海洋科学和工程领域中一个至关重要的问题^[1]。有效的路径规划不仅可以提高船舶的航行效率,还可以避免暗礁、海洋涡旋等潜在的海洋危险^[2]。然而,由于海洋环境的复杂性和不确定性,船舶路径规划仍然是一个具有挑战性的问题^[3]。

目前,中外有大量关于船舶路径规划的研究^[4],Zhang等^[5]针对在航海途中需要真实导航路线的问题,提出了一种基于自动识别系统数据的最短路径规划方法,可以更快、更有效地获取更短的路径,但仍可以通过引入16邻域A^*搜索算法等来获得更高的精度;程细得等^[6]针对多数船舶全局路径规划缺乏合理性和安全性的问题,构建了一种人工势场-操纵运动混合模型,得到了更符合真实的船舶航行工况的路径,提高了实用性,但存在计算效率不高等不足;童帮裕等^[7]针对船舶冰区航行将人工势场法与蚁群算法进行结合,能够有效解决船舶在冰区复杂环境中航行困难等问题,但未考虑冰山的动态可变性和船舶之间避让问题;Sun等^[8]提出利用粒子群算法求解无人潜航器路径规划问题,该算法具有易于实现且收敛速度快的特点,但仍容易陷入局部最优解;许志远^[9]提出了一种改进神经网络的船舶路径规划方法,规划长度与航行速度符合预期,但存在路径规划规模过小的问题;马凯强等^[10]提出改进人工鱼群算法,并采用多指标决策方法构建海洋环境威胁场,在考虑了地形、海风和海浪的情况下进行路径规划,但只考虑海洋环境的部分因素;余梦珺等^[11]考虑海冰密集度、海表温度、风强度等因素来构建西北航道海洋环境威胁场,并基于改进蚁群算法进行路径规划,但未能解决其他恶劣海况下的救援路径规划,且算法性能有很大改进空间。

由于多数研究并未讨论在特定海洋环境下对船舶路径进行规划,现针对海洋环境多变且不易预测、传统的路径规划方法往往无法达到理想效果等问题,现提出一种改进的蚁群算法—惩罚信息素蚁群优化算法(punishment pheromone ant colony optimization,PPACO)来解决船舶路径规划问题。改进算法受强化学习的启发,学习系统根据从环境中反馈信号的奖惩状态,调整系统参数。在惩罚信息素蚁群算法中,当蚂蚁找到不可行路径时,基于强化学习的原理对不良行为进行惩罚,释放出惩罚信息素,使得蚂蚁在后续的搜索过程中更倾向于选择其他路径,避免了无效搜索。其次,设计3个路径启发函数和两个海洋环境启发函数,为路径规划提供有效指导。最后,通过设计评价函数来评估本文算法在不同环境下时路径规划的优势。

1 路径规划模型

收起

船舶路径规划是一种基于特定目标和约束条件的决策过程,用来确定船舶从某一地点到目标的理想路径^[12]。在本文研究中,除了传统路径规划需要考虑的障碍物外,还需要考虑到不同的海洋环境以及路径长度、转向积累角等多个优化目标。

1.1 航行环境的建立

船舶的工作环境是一个基于网格的二维栅格地图,本文研究只考虑静态障碍物^[13-14]。障碍物的位置是已知的,如图1(a)所示。为了增加船舶航行安全性,对栅格内的障碍物进行填充处理,将含有障碍物的栅格用障碍物全填充^[15],如图1(b)所示。

为了防止船舶距离障碍物过近而发生的碰撞、搁浅等危险,将障碍物四周的栅格定为危险区域,如图1(c)所示,灰色格子被定为危险区域,船舶在行驶过程中应避开此区域。

1.2 路径规划约束条件的建立

本文研究在二维栅格地图中进行路径规划,环境是已知的,船舶可选择周围8个方向进行移动,每次移动一个栅格距离,直到到达终点,这些栅格不能与危险区域和已走过栅格发生任何碰撞。如果船舶的下一移动位置不在可行区域内,则本次寻路失败。船舶的可移动位置为

(1)$\begin{aligned} P_{t+1}= & \left\{(x, y) \mid(x, y) \in G_{\mathrm{f}},(x, y) \notin G_{\mathrm{v}},\right. \\ & \left.x \in\left[x_{t}-1, x_{t}+1\right], y \in\left[y_{t}-1, y_{t}+1\right]\right\} \end{aligned} $

式(1)中: G_f为可行区域;G_v为已走过的栅格;x_t为船舶当前位置横坐标;y_t为船舶当前位置纵坐标。

1.3 路径规划目标的建立

路径规划目标因不同的需求而存在差异。为更全面评价路径规划效果,本文研究选取了路径长度、风险和航向等作为评判标准。

1.3.1 路径长度

通过计算所有相邻路径的距离之和,得到最终路径的总长度。

(2)F_长度=

∑ i = 0 n - 1 (x i - x i + 1) 2 + (y i - y i + 1) 2

式(2)中:F_长度为长度评价函数;n为蚂蚁运动路径上所有栅格的总数量。

1.3.2 风险

船舶在行驶过程中需要尽可能远离障碍物,靠近障碍物行驶有可能会出现船体、设备损坏的风险。

(3)F_风险=

∑ i = 0 n - 1

obs_num(x_i,y_i)+1

式(3)中:F_风险为风险评价函数;obs_num为当前节点周围8个栅格内的障碍物数量。

1.3.3 航向

船舶在海面上航行时,航向变化是一个重要的概念,它反映了船舶在航行过程中航向的改变程度。以正北方向为0°,顺时针依次增加,由此用相邻路径之间的角度差来衡量船舶行驶时候的航向变化。

计算方式如下:对于每个航段,计算航向与正北方向的夹角;然后,对于相邻的航段,计算航向角度差的绝对值;最后将所有相邻航段的航向角度差值相加,得到总航向转向累积角。

(4)F_航向=

∑ i = 0 n - 1 Δ θ i

式(4)中:F_航向为航向评价函数;Δθ_i为相邻航段之间的角度差值。

2 改进的蚁群算法

收起

蚁群算法是一种通过模拟蚂蚁利用信息素交流来寻找最短路径的优化算法,它最早是由Dorigo等^[16]于20世纪90年代提出,目前在路径规划^[17]、任务调度^[18]、路由优化^[19]等领域已得到广泛运用。但在船舶路径规划领域,该算法容易陷入局部最优解的缺点限制了其在复杂航行规划中的应用。本文设计了3个路径启发函数,引导船舶进行高效、节能和安全的路径规划;增加了两个海洋环境启发函数,能够模拟复杂海洋环境下的真实路径规划情况;引入惩罚信息素来改进信息素更新规则,避免无效搜索,显著加快了算法的收敛速度。

2.1 船舶路径启发函数

2.1.1 距离启发函数

传统蚁群算法中的启发式函数η_ij为当前节点到下一步可选点之间的距离的倒数,由于在本次实验的栅格地图中,当前节点到下一节点的距离只能为1或1/

2

,由于没有考虑可选节点到目标点的距离,缺乏全局搜索的能力。改进算法加入目标节点的引导函数,减少蚂蚁的盲目搜索,加快收敛速度。改进后的启发式函数为

(5)η_ij(t)=

1 d i j + d j e

(6)d_ij=

(x i - x j) 2 + (y i - y j) 2

(7)d_je=

(x j - x e) 2 + (y j - y e) 2

式中:d_ij为当前节点i到可选节点j的距离;d_je为可选节点j到目标点e的距离。

2.1.2 变向启发函数

船舶在改变航向时会消耗更多的油量。因此,在船舶行驶过程中要减少变向,保证船舶尽可能地在一条直线上行驶。

在栅格地图中,船舶的行驶方向为8个方向。当蚂蚁在栅格地图中移动时,蚂蚁爬行时能够变化的方向角度为0°、45°、90°、135°。如图2所示,当蚂蚁从i节点移动到j节点时,判断j节点移动方向与i节点移动方向的角度θ。

变向启发函数为

(8)η_变向(t)=1-sin

θ 2

式(8)中:η_变向(t)为变向启发函数;θ为节点i移动到节点j时的角度差值。

2.1.3 风险启发函数

船舶路径规划在考虑路径长度尽可能短的同时,也需要远离障碍物,尽可能地在安全水域中行驶。蚂蚁在爬行过程中需要判断周围8个栅格中是否有危险区域以及危险区域的数量。如图3所示,蚂蚁在i点时,周围的危险区域有2个。

风险启发函数为

(9)η_风险(t)=

1 1 + o b s_n u m (x i, y i)

2.2 海洋环境启发函数

2.2.1 中尺度涡旋

中尺度涡旋在海洋环境中扮演非常重要的角色,它影响着海洋环流的形状和强度,参与调控全球气候变化,改变海洋生态系统的结构和分布,影响着海洋生物的生境和生存,甚至影响人类的海上安全和海洋经济活动^[20]。为了表示复杂海洋环境中的中尺度涡,本文研究采用构建旋转速度场的方式来表示涡旋。

(10)η_涡旋(t)=

1 Q s d i s + ε

d i s + ε Q s

(11)d_i_s=

(x i - x s) 2 + (y i - y s) 2

(12)ε=1×10^-6

式中:η_涡旋(t)为中尺度涡启发函数;Q_s为涡旋因子;d_i_s为蚂蚁当前位置与涡旋中心的位置;ε为一个极小的正值;x_i和y_i为当前节点的横坐标和纵坐标;x_s和y_s为涡旋中心的横坐标和纵坐标。

2.2.2 水流作用力

船舶在海面上航行时,水流会对船舶产生作用力,从而对船舶的速度与航向产生影响。为降低模型复杂性,本文研究参考文献[21]对水流作用环境进行模拟。

(13)τ_current=

X c u r r e n t Y c u r r e n t

12 ρ o A F c C X c (γ r c) V r c 2 12 ρ o A L c C Y c (γ r c) V r c 2

式(13)中:τ_current为船舶受水流的干扰力矢量;ρ_o为海水密度;A_Fc和A_Lc分别为水面下水流的正投影和侧投影面积;C_X_c和C_Y_c分别为水流作用力沿X方向和Y方向的负荷系数;γ_rc为水流运动方向与船舶夹角;V_rc为水流对于船舶的相对速度。

计算船舶所受的水流合力为

(14)F_current=

12

ρ_o(A_Fcsin²γ_rc+A_Lccos²γ_rc)C_Xc(γ_rc)

V r c 2

船舶失速矢量与水流作用力的关系为

(15)M_ship

v ˙

=τ_current

式(15)中:M_ship为船舶的质量;

v ˙

为船舶在水流影响下产生的失速矢量。

船舶为了避免失速,需要尽可能与水流方向一致,失速启发函数为

(16)η_失速(t)=

V' + v ˙ V' + v ˙ m a x

V' + V c o s φ V' + V

式(16)中:η_失速(t)为失速启发函数;V为海流速度;V'为船舶速度;φ为海流与船舶航向间的夹角。

最终得到的算法启发式函数为

(17)η″=

η 变 向 ω 1 η 风 险 ω 2

η'

式(17)中:

(18)η'=α_m

η 涡 旋 ω 3

+β

η 失 速 m ω 4

式中:η″为最终启发式函数;ω₁为变向权重、ω₂为风险权重;ω₃为涡旋权重;ω₄为失速权重;

η 变 向 ω 1

为加权变向启发函数;

η 风 险 ω 2

为加权风险启发函数;

η 涡 旋 ω 3

为加权涡旋启发函数;

η 失 速 ω 4

为加权失速启发函数;α_m为权重因子。

(19)α_m+β_m=1

式(19)中:β_m为权重因子。

2.3 改进信息素更新规则

传统蚁群算法是在蚂蚁寻到一个可行解后才会存入信息素,目的是引导蚂蚁的后续搜索能够向更优解的方向发展。而本文提出的改进的蚁群算法在全局更新中不仅要更新引导信息素,还要更新惩罚信息素。引导信息素为

(20)τ_ij(t+1)=1-ρτ_ij(t)+ρΔτ_ij(t)

(21)Δτ_ij(t)=

∑ k = 1 m

τ i j k

(t)

(22)Δ

τ i j k

(t)=

Q L k, M (i, j) ∈ M k 0, M (i, j) ∉ M k

式中:ρ为信息素蒸发系数;Δτ_ij(t)为i点到j点上释放出的信息素的和;Δ

τ i j k

(t)为i点到j点的信息素增量;L_k为蚂蚁k经过的路径长度;Q为信息素增量系数;M_k为蚂蚁k经过的路径的集合。

在蚂蚁移动的途中,需要关注每一只蚂蚁是否成功地建立了一条可行的移动路径,寻路失败的蚂蚁会在其路径上增加惩罚信息素,且该惩罚信息素的增量会随迭代次数的增加而减少;寻路成功的蚂蚁则会减少惩罚信息素,且惩罚信息素的值不小于0。这样就能把不可行的路径通过惩罚信息素标记出来从而能够提醒其他蚂蚁选择更合适的路径^[22],也能在算法早期让蚂蚁探索新路径,在算法后期减少对蚂蚁寻路失败的惩罚,给予蚂蚁更多机会去探索早期由于随机因素而寻路失败的路径。

蚂蚁惩罚信息素的更新公式为

(23)δ_ij(t)=

δ i j (t) + N m a x - N c u r N m a x, 蚂 蚁 寻 路 失 败 δ i j (t) - 1, 蚂 蚁 寻 路 成 功 且 δ i j (t) ≥ 1

式(23)中:δ_ij(t)为惩罚信息素;N_max为迭代最大次数;N_cur为当前迭代次数。

根据这两种信息素的定义,可以得出蚂蚁应该选择当前路径点有较大的引导信息素和较小的惩罚信息素,最终得到的改进的信息素更新公式为

(24)τ'_ij=τ_ij

1 δ i j (t) + 1

此时,状态转移规则更新为

(25)

p i j k

(t)=

[τ' i j (t)] α [η i j (t)] β [η ″ i j (t)] ∑ s ∈ N k [τ' i s (t)] α [η i s (t)] β [η ″ i s (t)], s ∈ N k; k = 1,2, ···, m 0, s ∉ N k

式(25)中:

p i j k

(t)为蚂蚁k从栅格i移动到栅格j的概率;α为信息素启发因子;β为启发函数因子; N_k为蚂蚁下一步可到达的点的集合。

2.4 算法流程图及伪代码

本文提出的PPACO算法流程图如图4所示。

本文提出的PPACO算法伪代码如算法1所示。

本文研究采用大O法分析算法的时间复杂度,假设算法的最大迭代次数为N_max,蚂蚁数量为m,每只蚂蚁在最坏情况下的寻路步骤数为T,那么该算法的时间复杂度为O(N_max×m×T)。

3 仿真实验

收起

为验证本文提出的改进蚁群算法在静态障碍物环境以及真实海洋模拟环境下船舶路径规划的有效性,以Python编码,在12th Gen Intel(R) Core(TM) i7-12700H(2 300 MHz) 32 GB RAM的计算机上对改进算法进行仿真。仿真实验拟定两种环境以适应不同海域背景下的应用,分别为静态仿真环境和包含涡旋等海洋环境因素影响的复杂仿真环境。其中,静态仿真环境为船舶在栅格地图中行驶中,对船舶路径的干扰因素只包含海面上的障碍物;而复杂仿真环境为船舶在栅格地图行驶中,对船舶路径的干扰因素不仅有海面上的障碍物,还包含了中尺度涡旋和水流作用力来模拟海上的海洋环境。

3.1 静态环境仿真

3.1.1 敏感性分析

目前对于蚁群算法的参数设置一般通过人工经验设定,为了对本文算法进行敏感性分析,在静态仿真环境中选取PPACO算法中的ω₁和ω₂,通过对不同参数组合进行比较。其他参数设置如下:蚂蚁数量设为80只,最大迭代次数设为50次,α取值为4,β取值为10,Q设置为5,ρ初始值为0.2。ω₁和ω₂的取值范围为ω₁,ω₂∈{0,0.5,1,1.5,2,3}。在每一次仿真实验过程中只改变一个值进行分析,其余值不变。ω₁和ω₂默认取值为1。参数敏感性分析如表1和表2所示。

由表1和表2可知,当ω₁增大时,路径长度变化范围不大,风险值在不停波动,航向积累角在逐渐减少;当ω₂增大时,路径长度变化范围也不大,风险值在逐渐变小,航向积累角在不停波动,会出现航向积累角极小值点。这表明ω₁和ω₂对路径长度的直接影响较小;ω₁对航向积累角的影响较大,更高的变向权重使路径变得更直;而ω₂对风险值的影响较大,更高的风险权重使路径点远离危险区域,但当ω₂过大时,船舶为了远离危险区域会进行更多的转向。本文算法在不同的权重设置下路径长度变化不大,能够保持稳定的性能,且能较好地响应权重变化,有着较强的稳健性。综合考虑路径规划评价指标,本文研究选取参数ω₁=2,ω₂=1。

3.1.2 算法对比和分析

在30×30的栅格地图中进行仿真实验,分别用传统ACO、JPS、双向搜索的改进ACO^[23]和PPACO算法对路径进行规划。其中传统ACO最大迭代次数设为100次,双向搜索的改进ACO最大迭代次数设为50次,其余参数与PPACO一致。3种算法的路径规划图如图5所示,收敛曲线变化趋势如图6所示,静态环境下3种算法对比结果如表3所示。

表3展示了4种算法对比结果,给出了4个评价指标,分别为路径长度、风险、航向和迭代次数。四种算法都能在一定的迭代次数内找到一个稳定的解决方案,具有良好的收敛性。但在路径合理性方面,PPACO算法很明显优于其他3种算法,相比较传统ACO算法来说,PPACO算法的路径长度减少15.7%,风险值降低54.0%,航向积累角减少85.0%,迭代次数减少89.7%;与JPS算法相比,PPACO算法的路径长度降低11.6%,风险值降低32%,航向积累角降低78.6%;与双向搜索的改进ACO算法相比,PPACO算法的路径长度降低6.1%,风险值降低5.6%,航向积累角降低80.0%,迭代次数降低53.3%。可以看出本文算法在各个评价指标上均有显著提升。

3.2 复杂海洋环境仿真

为验证该算法在真实海洋环境中的效果,利用美国国家海洋和大气管理局(National Oceanic and Atmospheric Administration,NOAA) 高分辨率海军沿海海洋模型(navy coastal ocean model,NCOM)分析海流数据,构建了包含中尺度涡旋和水流作用的模拟环境。为确认各种海洋现象对路径规划的影响,每次实验只考虑一个海洋相关环境,将与其他海洋要素相关的权重值设为0。

3.2.1 中尺度涡旋

为了观察船舶在中尺度涡旋环境下的路径规划,将参数α_m设为1,β_m设为0。为了减少船舶选择靠近涡旋中心的概率,将ω₃设为10。涡旋环境路径规划图如图7所示,其中红色的箭头为流矢量,可以看到明显的涡流,涡旋环境下3种算法实验数据对比如表4所示。

表4中,涡旋影响指的是规划后的路径点受到涡旋影响过大的点。从涡旋环境路径规划图中可以看出3种算法都能选择一条合适的路径来避开涡旋影响较大的区域,但是在3种对比算法中,PPACO算法在路径长度、风险值、航向积累角以及涡旋影响方面均优于其他两种对比算法,表明PPACO在遭受涡旋环境时能有更合适的应对表现,能够规划出一条路程短、低油耗、低风险和受涡旋影响最小的路径,保证了船舶的安全及效率。

3.2.2 水流作用力

为了观察船舶在水流作用力下的路径规划,假设船舶为中型商业货轮,设置水域内流体速度为2 m/s,流体方向为北偏东45°,静水速度为10 m/s,环境负荷参数参照文献[21]设置如表5所示。在本次实验中,将α_m设为0,β_m设为1。为了使船舶既考虑到失速风险,又不忽视其他关键因素的优化,将ω₄设为1。图8展示了三种算法在水流作用下的路径规划情况。

根据水流环境路径规划图可以看出,在水流作用环境中,船舶为了节省能耗和避免失速,会与水流方向尽可能相同,规划的路径会受到水流影响从而向北偏东45°方向偏移,得到的路径较为符合实际情况。水流环境3种算法实验数据对比如表6所示。

由表6可知,在考虑了水流作用力对船舶航行的影响后,可以看出PPACO算法在该环境下得到的4个评价指标均优于传统ACO算法和双向搜索的改进ACO算法,其中使用PPACO算法时的船舶航行时间为404.90,在实际应用中可以使船更快地到达目的地,提高船舶航行效率。

4 结论

收起

(1)为解决复杂海洋环境下大规模船舶路径规划问题,提出了一种惩罚信息素蚁群优化算法(PPACO),引入惩罚信息素对算法进行改进,并设计了距离、变向和风险启发函数;在路径规划模型方面本文提出障碍危险区域,并将海洋环境因素引入船舶路径规划的计算中,最后通过评价指标来验证改进算法在静态和复杂环境中的实用性和优势。

(2) 在静态环境中,本文算法相比较传统ACO算法、JPS和双向搜索的改进ACO算法,在路径长度上分别降低了15.7%、11.6%和6.1%,在风险值上分别降低了54.0%、32%、5.6%。在航向积累角上分别减少了85.0%、78.6%和80.0%,而相比较传统ACO算法和双向搜索的改进ACO算法,在迭代次数上分别降低了89.7%和53.3%,效果显著;在中尺度涡旋环境中,本文算法所受涡旋影响最小,能够规划出一条更安全的路径;在水流作用力环境中,本文算法航行耗时最短,大大提高了船舶航行效率。

(3)尽管PPACO算法在处理中尺度涡旋和水流作用力的二维模型中表现出良好的效果,然而,实际的海洋环境还包括海底地形、海水温度和盐度的变化等因素。因此,后续研究将侧重于三维海洋环境下的航行器路径规划。

基金

收起

国家自然科学基金(62373171)

参考文献

收起

文献

收起

参考文献引证文献

排序方式：

[1]

王孝元, 黄宇晴, 曹建萍. 基于粒子群算法的电池船运行优化[J]. 船舶工程, 2022, 44(2): 94-98, 133.

Wang

Xiaoyuan

, Huang

Yuqing

, Cao

Jianping

. Optimal operation of battery ship based on particle swarm optimization[J]. Ship Engineering, 2022, 44(2): 94-98, 133.

[2]

蒋美芝, 吕靖. 基于Pareto蚁群算法的船舶风险规避路径优化[J]. 交通运输系统工程与信息, 2019, 19(1): 192-199.

Jiang

Meizhi

, Lü

Jing

. Ship risk aversion path optimization based on pareto ant colony algorithm[J]. Journal of Transportation Systems Engineering and Information Technology, 2019, 19(1): 192-199.

[3]

魏照坤, 谢新连, 魏明. 风浪影响下的集装箱班轮航速优化[J]. 交通运输系统工程与信息, 2016, 16(3): 154-160.

Wei

Zhaokun

, Xie

Xinlian

, Wei

Ming

. Container ship speed optimization under influence of wind and wave[J]. Journal of Transportation Systems Engineering and Information Technology, 2016, 16(3): 154-160.

[4]

刘祥, 叶晓明, 王泉斌, 等. 无人水面艇局部路径规划算法研究综述[J]. 中国舰船研究, 2021, 16(S1): 1-10.

Liu

Xiang

, Ye

Xiaoming

, Wang

Quanbin

, et al. Review on the research of local path planning algorithms for unmanned surface vehicles[J]. Chinese Journal of Ship Research, 2021, 16(S1): 1-10.

[5]

Zhang

, Wen

, Tu

. A method for ship route planning fusing the ant colony algorithm and the A^* search algorithm[J]. IEEE Access, 2023, 11: 15109-15118.

[6]

程细得, 刘鹏辉, 韩琨羽, 等. 基于人工势场-操纵运动混合模型的船舶路径规划[J]. 华中科技大学学报(自然科学版), 2024, 52(1): 85-90.

Cheng

Xide

, Liu

Penghui

, Han

Kunyu

, et al. Path planning of ship based on artificial potential field-maneuvering motion hybrid model[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2024, 52(1): 85-90.

[7]

童帮裕, 胡坚堃. 基于改进蚁群算法的船舶冰区航行路径规划[J]. 中国航海, 2020, 43(1): 24-28.

Tong

Bangyu

, Hu

Jiankun

. Improved ant colony optimization for navigation path planning in ice zone[J]. Navigation of China, 2020, 43(1): 24-28.

[8]

Sun

, Liu

. Path plan of unmanned underwater vehicle using particle swarm optimization[C]// International Conference on Intelligent Systems Research and Mechatronics Engineering. Paris: Atlantis Press, 2015: 1764-1767.

[9]

许志远. 基于改进神经网络的船舶航行路径规划[J]. 舰船科学技术, 2022, 44(14): 57-60.

Zhiyuan

. Research on ship navigation path planning based on improved neural network[J]. Ship Science and Technology, 2022, 44(14): 57-60.

[10]

马凯强, 任利锋, 曾喆, 等. 顾及恶劣海况的船舶救援路径规划[J]. 海洋科学, 2021, 45(5): 39-46.

Kaiqiang

, Ren

Lifeng

, Zeng

Zhe

, et al. Ship rescue path planning considering adverse sea conditions[J]. Marine Sciences, 2021, 45(5): 39-46.

[11]

余梦珺, 张韧, 高顶, 等. 基于蚁群算法的西北航道海上救援路径规划[J]. 海洋预报, 2019, 36(6): 62-72.

Mengjun

, Zhang

Ren

, Gao

Ding

, et al. Route planning for maritime rescue in arctic northwest passage based on ant colony algorithm[J]. Marine Forecasts, 2019, 36(6): 62-72.

[12]

董翼宁, 曹景胜, 李刚. 融合A-Star与DWA双优化算法的自动引导车路径规划[J]. 科学技术与工程, 2023, 23(30): 12994-13001.

Dong

Yining

, Cao

Jingsheng

, Li

Gang

. Automatic guided vehicle path planning based on A-Star and DWA dual optimization algorithms[J]. Science Technology and Engineering, 2023, 23(30): 12994-13001.

[13]

刘晨霞, 朱大奇, 周蓓, 等. 海流环境下多AUV多目标生物启发任务分配与路径规划算法[J]. 控制理论与应用, 2022, 39(11): 2100-2107.

Liu

Chenxia

, Zhu

Daqi

, Zhou

Bei

, et al. A novel algorithm of multi-AUVs task assignment and path planning based on biologically inspired neural network for ocean current environment[J]. Control Theory & Applications, 2022, 39(11): 2100-2107.

[14]

陆辉山, 张燕飞, 王福杰, 等. 融合插点和跳跃点改进A^*算法的路径规划[J]. 科学技术与工程, 2023, 23(24): 10387-10393.

Huishan

, Zhang

Yangfei

, Wang

Fujie

, et al. Path planning of improved A^* algorithm by integrating interpolation and jump points[J]. Science Technology and Engineering, 2023, 23(24): 10387-10393.

[15]

Yang

, Qi

, Miao

, et al. A new robot navigation algorithm based on a double-layer ant algorithm and trajectory optimization[J]. IEEE Transactions on Industrial Electronics, 2018, 66(11): 8557-8566.

[16]

Dorigo

, Gambardella

L M

. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.

[17]

郝兆明, 安平娟, 李红岩, 等. 增强目标启发信息蚁群算法的移动机器人路径规划[J]. 科学技术与工程, 2023, 23(22): 9585-9591.

Hao

Zhaoming

, An

Pingjuan

, Li

Hongyan

, et al. Mobile robot path planning based on enhanced goal heuristic information ant colony algorithm[J]. Science Technology and Engineering, 2023, 23(22): 9585-9591.

[18]

田智慧, 张帅永, 高需. 遗传-蚁群算法在高性能计算任务调度中的应用[J]. 计算机应用与软件, 2024, 41(3): 253-257.

Tian

Zhihui

, Zhang

Shuaiyong

, Gao

. Application of genetic ant colony optimization in high performance computing task sche-duling[J]. Computer Applications and Software, 2024, 41(3): 253-257.

[19]

史郑延慧, 何刚. 基于遗传-蚁群优化算法的QoS组播路由算法设计[J]. 科学技术与工程, 2024, 24(11): 4626-4632.

Shi

Zhengyanhui

, He

Gang

. Design of QoS multicast routing algorithm based on genetic ant colony optimization algorithm[J]. Science Technology and Engineering, 2024, 24(11): 4626-4632.

[20]

, Lü

, Li

, et al. Three-dimensional underwater path planning of submarine considering the real marine environment[J]. IEEE Access, 2022, 10: 37016-37029.

[21]

谢新连, 王余宽, 何傲, 等. 考虑风浪流影响的船舶路径规划及算法[J]. 重庆交通大学学报(自然科学版), 2022, 41(7): 1-8.

Xie

Xinlian

, Wang

Yukuan

, He

, et al. Ship path planning and algorithm considering the effect of wind, wave and current[J]. Journal of Chongqing Jiaotong University(Natural Science Edition), 2022, 41(7): 1-8.

[22]

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, 2018, 68(1): 141-154.

[23]

白响恩, 江明哲, 徐笑锋, 等. 基于双向搜索的改进蚁群算法的船舶路径规划[J]. 中国航海, 2022, 45(3): 13-20.

Bai

Xiangen

, Jiang

Mingzhe

, Xu

Xiaofeng

, et al. Ship route planning using improved ant colony algorithm with bi-directional search strategy[J]. Navigation of China, 2022, 45(3): 13-20.

2025年第25卷第10期

PDF下载

390

162

引用本文

BibTeX

文章信息

doi: 10.12404/j.issn.1671-1815.2403141

接收时间：2024-04-25
首发时间：2025-07-09
出版时间：2025-04-08

补充材料

相关文章

文章信息

作者

出版历史

收稿日期：2024-04-25
修回日期：2025-01-01

基金

国家自然科学基金(62373171)

作者信息

江苏海洋大学计算机工程学院, 连云港 222005

通讯作者:

* 戴红伟(1975—),男,汉族,河南新郑人,博士,教授。研究方向:智能计算、最优化问题、复杂网络。E-mail:hwdai@jou.edu.cn。

参考文献

分享链接

https://castjournals.cast.org.cn/joweb/kxjsygc/CN/10.12404/j.issn.1671-1815.2403141

分享至

全文二维码

扫描看全文

引用本文

BibTeX

本文的引用情况

2种不同金属材料的力学参数

科 Family	属数 Number of genus	种数 Number of species	占总种数比例 Percentage of total species (%)	属 Genus	种数 Number of species	占总种数比例 Percentage of total species (%)
鹅膏菌科Amanitaceae	2	11	5.26	鹅膏菌属 Amanita	10	4.78
小菇科 Mycenaceae	2	12	5.74	丝盖伞属 Inocybe	5	2.39
多孔菌科 Polyporaceae	8	14	6.70	蜡蘑属 Laccaria	5	2.39
红菇科 Russulaceae	3	23	11.00	小皮伞属 Marasmius	6	2.87
				小菇属 Mycena	11	5.26
				光柄菇属 Pluteus	5	2.39
				红菇属 Russula	17	8.13
				栓菌属 Trametes	5	2.39

关闭全屏

BibTeX
EndNote
RefWorks
TxT

算法1 PPACO
1.建立静态、涡旋、流体动力环境模型 2.初始化惩罚信息素δ_ij、引导信息素τ_ij、蚂蚁数量m、最大迭代次数N_max 3.初始化权重参数 4.for N=1 to N_max do 5. for i=1 to m do 6. 将蚂蚁置于初始点 7. while 蚂蚁k未到达终点 8. 计算启发式函数η_ij、η″_ij和信息素τ'_ij 9. 根据式(25)选择下一位置 10. if 蚂蚁寻路失败 11. 更新惩罚信息素 12. end if 13. if 蚂蚁寻路成功 14. 更新惩罚信息素 15. 更新最优路径 16. end if 17. end while 18. end for 19. 更新全局信息素 20.end for

算法1 PPACO

1.建立静态、涡旋、流体动力环境模型
2.初始化惩罚信息素δ_ij、引导信息素τ_ij、蚂蚁数量m、最大迭代次数N_max
3.初始化权重参数
4.for N=1 to N_max do
5. for i=1 to m do
6. 将蚂蚁置于初始点
7. while 蚂蚁k未到达终点
8. 计算启发式函数η_ij、η″_ij和信息素τ'_ij
9. 根据式(25)选择下一位置
10. if 蚂蚁寻路失败
11. 更新惩罚信息素
12. end if
13. if 蚂蚁寻路成功
14. 更新惩罚信息素
15. 更新最优路径
16. end if
17. end while
18. end for
19. 更新全局信息素
20.end for

ω₁	0	0.5	1	1.5	2	3
F_长度	40.70	40.70	40.70	40.11	40.11	40.70
F_风险	25	18	20	20	17	23
F_航向	405	495	360	225	135	135

ω₁

0.5

1.5

F_长度

40.70

40.11

40.70

F_风险

F_航向

405

495

360

225

135

ω₂	0	0.5	1	1.5	2	3
F_长度	40.70	40.11	40.11	40.70	41.28	40.70
F_风险	33	24	20	17	16	13
F_航向	540	450	360	495	540	630

ω₂

0.5

1.5

F_长度

40.70

40.11

40.70

41.28

40.70

F_风险

F_航向

540

450

360

495

540

630

算法	F_长度	F_风险	F_航向	迭代次数
传统ACO	47.63	37	900	68
JPS	45.38	25	630	—
双向搜索的改进ACO	42.70	18	675	15
本文算法	40.11	17	135	7

算法

F_长度

F_风险

F_航向

迭代次数

传统ACO

47.63

900

JPS

45.38

630

—

双向搜索的改进ACO

42.70

675

本文算法

40.11

135

算法	F_长度	F_风险	F_航向	涡旋影响数量
传统ACO	46.80	30	900	2
双向搜索的改进ACO	41.28	26	540	4
本文算法	40.70	17	135	0

算法

F_长度

F_风险

F_航向

涡旋影响数量

传统ACO

46.80

900

双向搜索的改进ACO

41.28

540

本文算法

40.70

135

参数	数值
ρ_o/(kg·m^-3)	1.225
A_Fc/m²	2.56
A_Lc/m²	7.52
C_Xc	0.52
C_Yc	0.83
M_ship/t	40 000

参数

数值

ρ_o/(kg·m^-3)

1.225

A_Fc/m²

2.56

A_Lc/m²

7.52

C_Xc

0.52

C_Yc

0.83

M_ship/t

40 000

算法	F_长度	F_风险	F_航向	耗时/s
传统ACO	48.46	41	1 080	486.62
双向搜索的改进ACO	42.11	27	675	419.57
本文算法	40.70	20	180	404.90

算法

F_长度

F_风险

F_航向

耗时/s

传统ACO

48.46

1 080

486.62

双向搜索的改进ACO

42.11

675

419.57

本文算法

40.70

180

404.90