一种可用于AUV航路规划的改进粒子群优化算法

刘鲲

doi:10.3969/j.issn.1673-3819.2018.02.011

指挥控制与仿真 >

2018 , Vol. 40 >Issue 2: 61 - 64

DOI: https://doi.org/10.3969/j.issn.1673-3819.2018.02.011

理论研究

一种可用于AUV航路规划的改进粒子群优化算法

刘鲲

展开

北京长城电子装备有限责任公司, 北京 100082

刘鲲(1978-),男,辽宁凤城人,高级工程师,研究方向为水中兵器指挥控制。

收稿日期: 2018-01-16

修回日期: 2018-01-30

网络出版日期: 2022-05-09

收起

Particle Swarm Optimization Algorithm Used on Route Planning for AUV

LIU Kun

Expand

Beijing the Great Wall Electronic Equipment Co., Ltd, Beijing 100082, China

Received date: 2018-01-16

Revised date: 2018-01-30

Online published: 2022-05-09

Fold

摘要

在差分进化算法(DE)和量子粒子群优化算法(QPSO)基础上,提出了一种改进量子粒子群优化算法,并将其成功地应用于海洋环境下的AUV航路规划。仿真实验结果表明,在不同的战场环境下(不同的发射点,不同的目标点,不同的侦测威胁),改进量子粒子群优化算法寻优能力强、收敛速度快、算法稳定性好,可较好地适应AUV航路规划。

关键词： AUV; 航路规划; 粒子群优化算法; 差分进化算法

本文引用格式

刘鲲 . 一种可用于AUV航路规划的改进粒子群优化算法[J]. 指挥控制与仿真, 2018 , 40(2) : 61 -64 . DOI: 10.3969/j.issn.1673-3819.2018.02.011

Abstract

Based on the differential evolution algorithm (DE) and quantum particle swarm optimization algorithm (QPSO), this paper proposes an improved quantum particle swarm optimization algorithm, which is successfully applied to AUV route planning in the marine environment. Simulation results show that in different battlefield environment (different launch points, different target points, different detection threats), the improved quantum particle swarm optimization algorithm has the advantages of strong searching efficiency, fast convergence speed and good algorithm stability, which can be well adapted to AUV route planning.

Key words： AUV; route planning; particle swarm optimization; differential evolution

AUV在水下航行时,因海洋环境复杂,且对能耗要求较高,在远距离条件下如何保证航路规划最优显得尤为重要,而且在遇到未知障碍或任务变更时,为保证任务时敏性,航路规划算法的快速性也很重要。

作为一种智能优化算法,粒子群优化算法由于原理简单、易于实现,自提出就受到广泛关注并被应用于多个领域,并出现了很多改进算法,其中我国学者孙俊提出了量子粒子群优化算法(Quantum-behaved Particle Swarm Optimization,QPSO),一定程度上解决了算法容易早熟收敛从而陷入局部最优的问题,但是该算法稳定性和寻优能力依然不理想^[1]。差分进化算法(Differential Evolution, DE)^[2⇓-4]算法稳定性好,适应性强,简单易行,不足是前期收敛速度缓慢,影响了算法的快速性。

本文将DE算法与QPSO算法进行了混合,充分考虑了两种算法的优缺点,扬长避短,提出了一种改进量子粒子群优化算法,简称DE-QPSO算法,并以真实的海洋环境为背景,将DE-QPSO算法应用于海洋环境下的AUV航路规划,并通过仿真证明了算法的适应性和优越性。

1 差分量子粒子群优化算法

1)DE算法描述

施主因子:

(1)

v i j m + 1

x r 1, j m

+λ(

x r 2, j m

x r 3, j m

), (i=1,2,···n; j=1,2,···,d)

其中r₁,r₂,r₃∈{1,2,···,n}\{i}且r₁≠r₂≠r₃。λ∈[0,2]为控制差分向量

x r 2, j m

x r 3, j m

的常数因子。上标m表示第m次迭代。d表示粒子的维数。

试验向量

A i m + 1

(2)

a i j m + 1

v i j m + 1, r a n d (j) ≤ C R, j = r n b r (i) x i j m, r a n d (j) > C R, j ≠ r n b r (i)

其中,CR∈[0,1]为交叉概率,rand(j)为[0,1]上服从均匀分布的随机数,rnbr(i)∈{1,2,···,d}为[1,d]内的随机整数。

目标向量

X i m

(3)

X i m + 1

A i m + 1, J (A i m + 1) ≤ J (X i m) X i m, J (A i m + 1) > J (X i m)

其中J(·)为待优化的目标函数,A_i为试验向量。

2)量子粒子群优化算法(QPSO)描述^[5-6]

粒子的速度和位置更新模型为

(4)

u i j (m + 1)

u i j (m)

+c₁

r 1 i (m)

(

p i j (m)

x i j (m)

)+c_&₂

r 2 i (m)

(

p g j (m)

x i j (m)

)

(5)

x i j (m + 1)

x i j (m)

u i j (m + 1)

, (i=1,2,···,n;j=1,2,···,k)

其中,速度向量U_i=[u_i₁,u_i₂···,u_ik],位置向量X_i=[x_i₁,x_i₂···,x_ik],局部最优(个体)粒子P_i=[p_i₁,p_i₂···,p_ik]和全局最优粒子P_g=[p_g₁,p_g₂···,p_gk]。

更新方程可等价于

(6)

U i m + 1 = U i m + c 1 r 1 i m (P i m - X i m) + c 2 r 2 i m (P g m - X i m) X i m + 1 = X i m + U i m + 1, (i = 1,2, ···, n)

其中c₁和c₂分别学习因子或加速因子。r₁和r₂为[0,1]之间服从均匀分布的随机数,上标m表示第m次迭代,n为种群的大小,即种群中粒子的个数。

3)差分进化量粒子群优化算法(DE-QPSO)构建

该算法可分解为两个过程:1)采用量子粒子群优化算法,通过每次的迭代计算对选定的种群进行更新;2)利用差分进化算法进行寻优计算。

令施主向量为

V i k + 1

_,则可通过下式得出:

(7)

v i j m + 1

p g j m

12

[(

p r 1, j m

p r 2, j m

)+(

p r 3, j m

p r 4, j m

)]

其中r₁,r₂,r₃,r₄∈{1,2,···,n}\{i,g}且r₁≠r₂≠r₃≠r₄。g为第一阶段的QPSO算法产生的全局极值的索引号,

p g j m

为随机选择的由第一阶段的QPSO算法产生的个体极值,

p r i, j m

为第j维分量的个体极值,r_i为随机数。

将V_i和个体极值P_i进行交叉,得到试验向量A_i:

(8)

a i j m + 1

v i j m + 1, r a n d (j) ≤ C R^j = r n b r (i) p i j m, r a n d (j) > C R, j ≠ r n b r (i)

其中,p_ij为第i个粒子个体极值的第j维分量,CR∈[0,1]为交叉概率。

经过变异和交叉操作后,对每个个体X_i,均产生了一个试验向量A_i,比较A_i和X_i的适应度,如果A_i的适应度值优于X_i,则由A_i代替X_i进入下一代;否则,舍弃A_i,保留X_i。

2 DE-QPSO算法在AUV航路规划中的应用

AUV在航行过程中,除避开岛屿、岛礁等障碍外,还要考虑其隐蔽性等约束,因此海洋环境下的AUV航路规划问题,可认为是一个最优化问题。本文将DE-QPSO算法为作为优化工具,探讨在AUV航路规划中的应用和其优越性。

2.1 航迹表示

假定AUV在固定的深度航行,将航迹规划简化为二维平面规划问题。

第i条航迹L_i可以表示为

(9)L_i=[l_i₁,l_i₂,···,l_in,l_i_,_n₊₁,l_i_,_n₊₂,···,l_i_,2_n]

其中,前n维分量为n个航迹节点的横坐标,后n维分量为n个航迹节点的纵坐标。基于上式的编码结构,第i条航迹上的第j个节点的坐标可以表示为(l_ij,l_i_,_j₊_n),其中i=1,2,···,m;j=1,2,···,n。如果航迹节点个数为n,则个体的维数为2n_。

B样条航迹L'_i可以构造为:

(10)L'_i=[l'_i₁,···,l'_iN,l'_i_,_N₊₁,···,l'_i_,2_N],

其中,N为B样条形式的航迹中离散点的个数(除起始点和目标点外)。

令W_ij=(l'_ij,l'_i_,_j₊_N),j=1,···,N,则B样条曲线可表示为

(11)L'_i={W_i₁,W_i₂,···,W_iN},i=1,···,m

2.2 航路代价模型

因AUV速度较低,因此不考虑AUV的机动性,从而,航迹代价由航迹长度代价,威胁代价这两部分组成。对航迹L_i而言,其航迹代价可以表示为

(12)J(L_i)=w₁J₁(L_i)+w₂J₂(L_i)

(13)$J_{1}\left(L_{i}\right)=\sum_{j=0}^{N}\left\|W_{i j} \vec{W}_{i, j+1}\right\|$,

(14)J₂(L_i)=

∑ k = 1 K ∑ j = 0 N

s_kJ_2,_k(W_i_,_jW_i_,_j₊₁)

其中,J₁,J₂分别为航迹的长度代价、威胁代价,w_i(i=1,2)为相应的权系数。W_i₀和W_i_,_N₊₁分别为起始点和目标点。其中K为威胁集的势,s_k表示第k个威胁的强度。

2.3 实验结果与分析

本文从航迹质量、算法稳定性和收敛速度三个方面来比较DE算法、QPSO算法和DE-QPSO算法这三种算法的性能。

假设:

1)种群规模、粒子维数和最大迭代次数分别设定为80、6和100;航迹节点设定为6。

2)试验样例:如表1。

表1 实验样例

样例编号	起始点	目标点	侦测威胁集
1	(45,20)	(480,480)	{(122,162,40),(241,165,69),(250,376,68), (383,370,50),(413,224,60)}
2	(6,324)	(478,98)	{(48,289,26),(160,277,46),(246,154,59), (279,381,52),(403,181,43)}

两个实验样例,起始点和目标点用二维平面坐标描述。侦测威胁数据用在不同中心和不同半径的圆来模拟。威胁(122,162,40)表示该威胁的中心为(122,162),半径为40。

所有实验结果均是20次独立重复实验的平均值。

试验结果:

1)三种算法在样例1上的最优航迹、收敛曲线和性能比较如图1和表2所示。

显示原图|下载原图ZIP|生成PPT

图1 最优航迹图和收敛曲线

表2 三种算法在样例1上的性能比较

算法	最小代价	最大代价	平均代价	标准差
DE	68.3233	120.5631	93.2255	16.1201
QPSO	24.8852	130.3124	80.4321	38.3536
DE-QPSO	13.1124	89.1113	42.5241	16.0982

可以看出,三种算法中DE-QPSO算法航迹平滑、航程短,且有更强的全局搜索能力和更快的收敛速度,DE-QPSO算法对应的平均代价和标准差最小,这进一步表明了DE-QPSO算法高效的性能和较好的稳定性。

2)三种算法在样例2上的最优航迹、收敛曲线和性能比较如图2和表3所示。

显示原图|下载原图ZIP|生成PPT

图2 最优航迹图和收敛曲线

表3 三种算法在样例2上的性能比较

算法	最小代价	最大代价	平均代价	标准差
DE	60.3211	146.4589	88.6546	23.7521
QPSO	28.5623	167.5213	67.4666	36.3322
DE-QPSO	13.1234	172.5621	55.7812	21.6589

实验结果表明,在样例2上,DE-QPSO算法仍然保持了它的优势地位,表现出比其他算法更好的性能。就收敛速度而言,DE-QPSO算法的位于最顶端,具有最快的收敛速度,进一步说明了混合策略非常有效。

3)为了研究不同的航迹节点个数对规划结果的影响,将航迹节点的个数由6设定为8,其他环境和例1相同,结果如表4和图3所示。

表4 三种算法在样例3上的性能比较

算法	最小代价	最大代价	平均代价	标准差
DE	108.7821	163.4578	146.7855	18.7258
QPSO	33.9544	119.7841	85.1548	27.9672
DE-QPSO	23.4523	84.3787	44.9752	22.2458

显示原图|下载原图ZIP|生成PPT

图3 最优航迹图和收敛曲线

结果表明,随着粒子维数的增加,算法优化起来更加困难,三种算法都趋于更加稳定,但DE-QPSO算法在收敛速度方面仍然保持较好地优势,且航迹明显由于其他两种算法,这进一步表明将DE算法与QPSO算法混合是相当有效的。

3 结束语

本文结合差分进化算法和量子粒子群优化算法的优缺点,提出了一种改进量子粒子群优化算法,仿真实验结果表明,该算法寻优能力强、收敛速度快、算法稳定性好,可较好地适应不同海洋环境下的AUV航路规划。该算法还可以为其他领域中的优化问题提供借鉴。

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序

[1]	傅阳光, 周成平, 丁明跃. 基于混合量子粒子群优化算法的三维航迹规划[J]. 宇航学报, 2010, 31(12): 2657-2664.

[2]	Storn R., Price K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, 1997, 11(4): 341-359. DOI

[3]	Price K., Storn R., Lampinen J., Differential evolution: a practical approach to global optimization[M]. 2005: Springer Verlag.

[4]	刘波, 王凌, 金以慧. 差分进化算法研究进展[J]. 控制与决策, 2007, 22(7): 721-729.

[5]	Sun J., Feng B., Xu W. Particle Swarm Optimization with Particles Having Quantum Behavior[C]. in Proceedings of the IEEE Congress on Evolutionary Computation, 2004, 325-331.

[6]	Sun J., Xu W., Feng B. A global search strategy of quantum-behaved particle swarm optimization[C]. in Proceedings of IEEE Conference on Cybernetics and Intelligent Systems, 2004, 111-116.

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract

1 差分量子粒子群优化算法

2 DE-QPSO算法在AUV航路规划中的应用

2.1 航迹表示

2.2 航路代价模型

2.3 实验结果与分析

表1 实验样例

图1 最优航迹图和收敛曲线

表2 三种算法在样例1上的性能比较

图2 最优航迹图和收敛曲线

表3 三种算法在样例2上的性能比较

表4 三种算法在样例3上的性能比较

图3 最优航迹图和收敛曲线

3 结束语

参考文献