基于改进人工鱼群算法的飞行器三维路径规划

高翟 ,  李一鸣 ,  贺宏亮

东北大学学报(自然科学版) ›› 2026, Vol. 47 ›› Issue (3) : 38 -50.

PDF (2836KB)
东北大学学报(自然科学版) ›› 2026, Vol. 47 ›› Issue (3) : 38 -50. DOI: 10.12068/j.issn.1005-3026.2026.20249060
信息与控制

基于改进人工鱼群算法的飞行器三维路径规划

作者信息 +

Three-Dimensional Path Planning for Aircraft Based on Improved Artificial Fish Swarm Algorithm

Author information +
文章历史 +
PDF (2903K)

摘要

针对传统人工鱼群算法的缺陷,提出了一种面向飞行器路径规划的改进人工鱼群算法.该算法首先运用改进的Sine混沌映射完成种群初始化,并在聚群行为的基础上增加了基于模拟退火改进粒子群算法的更新方式,然后采用狼群算法多种自适应移动步长策略优化追尾行为,同时以正余弦算法替代随机行为,并设计若干自适应参数,以提高搜索的灵活性.为验证该算法的性能,构造了三维山地测试地图,从收敛性能、路径形态和复杂程度等方面进行分析.结果表明,相较于传统算法,改进后的人工鱼群算法在收敛速度、寻优性能等指标上均有明显提升.

Abstract

An improved artificial fish swarm algorithm tailored for aircraft route planning was proposed to address the limitations of the traditional artificial fish swarm algorithm. Initially, an improved Sine chaotic mapping was employed for population initialization. On the basis of schooling behavior, an update mechanism based on particle swarm optimization algorithm improved by simulated annealing was incorporated. Furthermore, the following behavior was optimized by adopting multiple adaptive movement step length strategies derived from the wolf pack algorithm. Additionally, the random behavior was replaced with a sine-cosine algorithm, and several adaptive parameters were designed to enhance the search process flexibility. To validate the performance of the proposed algorithm, a three-dimensional mountainous test map was constructed, and analyses were conducted regarding several aspects such as convergence performance, route morphology, and complexity. The results demonstrate that, compared with the traditional algorithm, the improved artificial fish swarm algorithm achieves significant enhancements in indicators such as convergence speed and optimization performance.

Graphical abstract

关键词

智能优化算法 / 人工鱼群算法 / 路径规划 / 飞行器 / 混沌映射

Key words

intelligent optimization algorithm / artificial fish swarm algorithm / path planning / aircraft / chaotic mapping

引用本文

引用格式 ▾
高翟,李一鸣,贺宏亮. 基于改进人工鱼群算法的飞行器三维路径规划[J]. 东北大学学报(自然科学版), 2026, 47(3): 38-50 DOI:10.12068/j.issn.1005-3026.2026.20249060

登录浏览全文

4963

注册一个新账户 忘记密码

随着科技的进步,针对飞行器的研究不断深入,目前在交通、消防、物流和军事等众多领域都有广泛的应用.飞行器在实际飞行任务中常常需要面临多种复杂的低空环境,例如不规则的障碍物、复杂的地形地貌以及存在信号干扰的危险区域,这些都会成为飞行器运行过程中的重大威胁.因此,为了避免飞行事故、提升工作效率、节省时间和能源,在执行飞行任务之前确定最优路径是非常必要的[1].本研究采用智能优化算法在空间地图内搜索最优曲线,以解决飞行器在复杂三维环境中的飞行路径规划问题.
由于飞行器的应用场景存在诸多阻碍,且三维环境的空间自由度较高,导致二维图形搜索算法不能有效应对,而传统的凸优化方法则需要繁杂的数学推导过程.此外,当前飞行器在实际应用中需要面对很多艰巨挑战,例如障碍物形状不规则、飞行环境风速大等问题[2-3].因此,采用一种高效且可靠的方法来解决飞行器路径规划问题成为了重点研究方向.
飞行器路径规划研究的目的是为飞行器在复杂环境中找到一条从起点到目标点的最优路径.近年来,随着计算机技术的快速发展,路径规划领域涌现出了多种研究策略.①基于数学优化方法的策略包含凸优化、线性规划和非线性规划等,通过建立路径规划的数学模型并进行演算推导,最终得到最优路径.这是一类最原始的优化策略,其优点是能够证明结果为全局最优,缺点是原理复杂、计算过程烦琐、实施效率低[4-5].②传统路径规划策略主要包括A*算法、Dijkstra算法和快速扩展随机树等,这些算法在实际应用中具有较高的可靠性,常用于解决低维度的经典路径规划问题,但在面临复杂问题时往往存在计算复杂度高和收敛速度慢的缺陷[6-7].③强化学习方法通过智能体与环境的交互来学习最优策略,常用的方法包括Q-learning和深度强化学习.这类方法的优势在于其灵活性高,能够处理高维连续空间中的复杂问题,但是训练过程需要大量数据,计算复杂度高[8-9].④智能优化算法的求解原理模拟了自然界中的群体行为,如粒子群算法、免疫算法、蚁群算法等.这类算法易于改进和融合,结合多种原理的融合算法可以汲取各原始算法的优点,提升整体性能[10-11].智能优化算法原理简单,适合解决复杂环境下的路径规划问题,但缺点是算法性能依赖于参数的选择.
人工鱼群算法结构巧妙,具有并行运行的特性,执行效率高、复杂度低.然而传统人工鱼群算法在无人机路径规划中存在收敛速度慢、局部搜索能力不足、对参数敏感等缺陷.研究表明,采用动态参数调整[12]、混合优化[13]、多目标优化[14]和并行化改进[15]等方法,可以显著提升算法的性能.
在无人机及机器人路径规划领域,采用改进的人工鱼群算法作为解决方案的研究主要包含如下类型:①改变参数设置,使拥挤度因子、鱼群视野和移动步长等参数随着迭代过程自适应变化[16-17];②与其他算法相结合,综合其他策略的优势,以实现参数优化或整体性能提升 [18-20];③改进算法的基本结构或原理,使某一方面的优势更突出,以解决特定的需求[21-22].
目前的研究仍然存在以下不足:①为了提升性能,只专注于算法的收敛速度和精度,而忽略了复杂度问题[20];②很多研究是基于二维栅格地图的路径规划,这些测试模型优化出的算法灵活性较低,难以满足飞行器实际应用的需求[16-19,21];③一些基于原理的改进虽然增强了算法在迭代初期的收敛速度,并且额外设置了跳出局部最优的操作,但会影响整体的收敛效果和灵活性[22].
因此,分析传统方法的缺陷,融合其他高效策略,设计出一种收敛能力强、计算复杂度低、运行效率高的改进算法,以更好地应对复杂的飞行器路径规划任务,是值得研究且具有意义的.

1 问题描述

该问题的已知条件包括三维空间地形信息和起点与终点的位置坐标.问题的本质是寻找一条从起点到终点的三维路径曲线,要求该曲线避开障碍物,且尽可能短,尽量平滑顺畅.

本研究使用一系列算法在空间地图中进行坐标采样,选取n个不与障碍物重合的坐标点,通过三次样条曲线拟合散点的方式,对包括起点、终点和采样点的n+2个坐标进行拟合,得到最终路径.

定义一个有限三维空间U=X0,X1×Y0,Y1×[Z0,Z1],设障碍物区域为O,O为U的非空真子集,即O⊂U且O≠∅.设待求的三维曲线方程为r(t),t表示分布在三维曲线上的一维参数,它可以被看作是数据点在曲线上的位置或顺序的索引,t∈[tstart,tend],tstart和tend分别是起点和终点位置在曲线r(t)上的映射刻度,Sx(t),Sy(t)和Sz(t)分别表示参数t对应点在x,y和z轴上的坐标分量,那么完整的三维曲线表达式为r(t)=[Sx(t),Sy(t),Sz(t)].

在三维空间中进行三次样条插值时,需要为每个坐标轴x(t),y(t)和z(t)分别建立三次样条插值函数.假设需要拟合的n个坐标点分别为t1,x1,y1,z1,t2,x2,y2,z2,…,tn,xn,yn,zn,其中ti表示曲线上的第i个点,i∈1,2,…,n,而xi,yi和zi分别是ti在x,y和z坐标轴上的值,那么就需要对n个点之间的n-1段曲线方程分别进行求解.

三次样条插值是一种通过多项式插值来平滑连接各个点的方法,在每个区间[ti,ti+1]内的插值函数Sit都是独立的三次多项式,因此局部误差不会影响其他区间,能够保证较高的精确度,且计算复杂度低于高次多项式插值方法,适用于拟合非均匀分布的数据点.

插值函数Sit需要满足以下约束条件:

1) 在每个区间内Sit连续;

2) 在所有节点处Siti的一阶导数连续;

3) 在所有节点处Siti的二阶导数连续;

4) 自然边界条件,即曲线两端的二阶导数为零.

通过这些约束,三次样条插值能够避免高次多项式插值可能出现的振荡现象,提供更稳定的结果.以下为各约束条件的具体描述.

1.1 插值函数

在各维度上分别用一个三次函数来描述曲线形态,各坐标轴上的插值函数可以表示为

Sxt=ax+bxt-ti+cxt-ti2+dxt-ti3,Syt=ay+byt-ti+cyt-ti2+dyt-ti3,Szt=az+bzt-ti+czt-ti2+dzt-ti3.

式中,各维度上的a,b,c,d分别为待求解的系数.

1.2 一阶约束

一阶导数表示曲线的切线斜率,一阶约束保证了曲线在节点处的切线方向连续,避免斜率突变.这意味着对于xt,yt和zt,在相邻区间ti,ti+1和ti+1,ti+2中的插值函数Sit的一阶导数Si'(t)在ti+1处相等,如式(2)所示.其中,ti+1-表示点ti+1的左邻域,ti+1+表示点ti+1的右邻域.

Sx'ti+1=Sx'ti+1-=Sx'ti+1+,Sy'ti+1=Sy'ti+1-=Sy'ti+1+,Sz'ti+1=Sz'ti+1-=Sz'ti+1+.

1.3 二阶约束

二阶导数表示曲线的曲率,即弯曲程度,二阶约束保证了曲线在节点处的曲率连续,避免出现突兀的弯曲变化.这意味着对于xt,yt和zt,在相邻区间ti,ti+1和ti+1,ti+2中的插值函数Sit的二阶导数Si″t在ti+1处相等,如式(3)所示.

Sx″ti+1=Sx″ti+1-=Sx″ti+1+,Sy″ti+1=Sy″ti+1-=Sy″ti+1+,Sz″ti+1=Sz″ti+1-=Sz″ti+1+.

1.4 自然边界条件

假设曲线在首末端点处没有额外的弯曲趋势,同时作为边界条件,为保证整体插值结果的平滑性和自然性,要求曲线在端点处的二阶导数为零:

Sx″t1=Sx″tn=0,Sy″t1=Sy″tn=0,Sz″t1=Sz″tn=0.

求解上述方程,计算出各段曲线上的a,b,c,d系数值,最终确定三维曲线r(t)的数学表达式.

该问题的适应度,即曲线的长度L可以表示为

L=∫tstarttenddSxtdt2+dSytdt2+dSztdt2dt.

当n→∞时(即∆t→0),L的值将趋近于三维曲线的真实长度.

综合以上分析,再加入障碍物碰撞约束,可得到该问题的数学模型:

mint ∫tstarttenddSxtdt2+dSytdt2+dSztdt2dt,s.t. ∀t∈tstart,tend,rt∈U,∀t∈tstart,tend,rt∉O,式1~式4.

2 传统人工鱼群算法的原理

人工鱼群算法(artificial fish swarm algorithm,AFSA)模拟鱼群寻找食物的行为,以实现全局寻优.在人工鱼群算法中,存在聚群、追尾、觅食和随机行为,这4种行为的执行原理如下.

2.1 聚群行为

向视野范围内伙伴的中心位置移动,执行条件是目标位置的鱼群拥挤度小于最大拥挤度;若不满足,则执行觅食行为.

设第i条鱼的位置为Xi,该位置的适应度为Yi,其视野范围内的伙伴数为nf,伙伴的中心位置为Xc,伙伴中心位置的适应度为Yc,δ为拥挤度因子.若Yc/nf<δ Yi,则表明Yc位置不拥挤,可以向该方向移动;否则退出聚群行为,执行觅食行为.聚群行为的位置更新规则为

Xi=Xi+rand0,1×step×Xc-XiXc-Xi.

其中:rand0,1为0,1范围内的随机数;step表示人工鱼的移动步长.

2.2 追尾行为

追逐视野范围内适应度最低的个体,执行条件是目标位置的鱼群拥挤度小于最大拥挤度;若不满足,则执行觅食行为.

设人工鱼i视野范围内适应度最低个体的位置为Xj.若Yc/nf<δYj,则表明Xj位置不拥挤,可以向Xj移动;否则退出追尾行为,执行觅食行为.追尾行为的位置更新规则为

Xi=Xi+rand0,1×step×Xj-XiXj-Xi.

2.3 觅食行为

在视野范围内随机选择一个位置,并且比较自身位置与该位置的适应度大小.若该位置更优,则向该位置前进;否则重复这一操作,直至达到最大尝试次数.若仍然不满足前进条件,则退出觅食行为,执行随机行为.觅食行为的位置更新规则为

Xk=Xi+rand0,1×visual,Xi=Xi+rand0,1×step×Xk-XiXk-Xi.

其中:visual表示人工鱼的视野范围;Xk表示第i只鱼在视野范围内随机选择的位置.

2.4 随机行为

人工鱼在其视野范围内随机选择一个位置,并向该位置移动.其位置更新规则如式(10)所示.当某次迭代的搜索次数大于最大次数限度时,将执行该操作,以确定本次迭代的最终结果,结束搜索过程.

Xi=Xi+rand0,1×step.

虽然觅食行为与随机行为都采用了向随机位置前进的更新策略,但随机行为不会比较新旧结果的优劣,而是直接将随机值作为最终结果.

在每轮迭代中,该算法将分成两个部分执行:首先从聚群行为开始,按照上述规则执行相应操作;待这部分完成后,再开始追尾行为.第二部分完成后,对比两个部分的结果,选择较优的一方作为本次迭代的优胜者,最后与全局最优解作比较,若该结果更优,则将其更新为全局最优解.

3 算法改进思路

人工鱼群算法具备诸多优势,不需要严格的问题机理模型,拥有并行处理能力;然而传统人工鱼群算法仍然存在缺陷.经过分析,归纳出3个主要缺陷.

缺陷Ⅰ:4种行为的位置更新方式完全相同,均采用“步长乘以方向”的移动方法,缺乏灵活性和针对性,搜索效果不佳.

缺陷Ⅱ:采用固定的视野和步长,不利于搜索全局最优解,应当根据实际的迭代次数进行自适应调整.

缺陷Ⅲ:觅食行为和随机行为实际上都采取了“随机寻找位置”的方式,本质上没有区别.

针对以上缺陷,本研究提出了相应的改进思路.

3.1 针对缺陷Ⅰ,采用粒子群算法改进聚群行为

由于粒子群优化算法(particle swarm optimization, PSO)在位置更新时能够高效地平衡个体与全局的关系,并且充分利用迭代过程的历史信息进行搜索,因此考虑采用改进的粒子群算法实现位置更新.粒子群算法是一种经典的智能优化算法,适用于处理高维度、非线性、非凸等问题.该算法的更新原理模拟了鸟群捕食过程中的协作机制,能够协调个体与群体之间的关系,考虑历史状态对当前状态的影响,具有收敛速度快的优势.传统粒子群算法的更新方式:

vi=w vi+c1r1pi-xi+c2r2pg-xi,xi=xi+vi.

其中:w为惯性权重;c1和c2为学习因子;r1和r2为[0,1]范围内的均匀随机数;vi表示粒子i的速度;xi表示粒子i的位置;pi表示个体极值,即粒子i迄今为止搜索到的最优位置;pg表示全局极值,即整个粒子群迄今为止搜索到的最优位置.

在速度更新表达式中,第一项表示之前运动状态对当前的影响,第二项表示个体最优位置对当前的影响,第三项表示全局最优位置对当前的影响.

本研究提出的改进方案在于,以原始聚群行为为基础,利用粒子群算法的更新原理,将鱼群视野范围内的中心位置作为粒子群算法的个体最优位置.为了提升算法的效率,采用模拟退火、自适应惯性权重、自适应学习因子和压缩因子等方法设计粒子群更新策略.

3.1.1 基于模拟退火的粒子群算法

模拟退火算法(simulated annealing,SA)模仿热力学系统中的金属退火过程,具有跳出局部最优解的能力.在基于模拟退火的粒子群算法中,粒子更新时,若新位置的适应度小于原位置的适应度,则选择新位置;若不满足该条件,则以一定概率接纳该结果,而非直接否定.概率值随温度变化,迭代前期温度较高,概率更大,使算法倾向于探索更多位置以避免陷入局部最优;随着迭代的进行,温度不断降低,概率减小,算法收敛并集中搜索最优解.

选取结果的概率为

P=1,                     fx+1<fx;e-fx+1-fxKl,fx+1≥fx.

其中:Kl表示第l次迭代的温度值;f(x)表示原位置的适应度;f(x+1)表示新位置的适应度.

初始温度K0和退温方式分别为

K0=Tκ,
Kl+1=μ Kl.

其中:T表示最大迭代次数;κ为初始温度系数;μ为降温系数.

3.1.2 对粒子群参数的改进

对粒子群参数的改进包括对惯性权重、学习因子和压缩因子等参数设定方式的改进,通过引入自适应机制,使算法的搜索过程更加灵活高效.

自适应惯性权重为

w=wmax-wminfi-fminfavg-fmin,fi≤favg;wmax,                                  fi>favg.

其中:wmin和wmax为惯性权重w的最小值和最大值;fi表示粒子i的实时目标函数值;favg和fmin分别表示当前所有粒子的平均值和最小目标值.

自适应学习因子为

c1=c1max-c1max-c1mintT,c2=c2max-c2max-c2mintT.

其中:c1min和c1max为学习因子c1的最小值和最大值;c2min和c2max为学习因子c2的最小值和最大值.

将压缩因子应用于模拟退火算法,能够调整解的搜索空间或步长,从而在迭代过程中更快地逼近最优解.在模拟退火算法的后期阶段,当温度较低时,解的变化通常较小且趋于稳定.此时,引入压缩因子可以进一步缩小搜索范围,减少不必要的计算量.因此,在自适应惯性权重w和学习因子c的基础上加入压缩因子操作:

ξ=22-φ-φ2-4φ,φ=c1+c2.

那么,粒子的速度和位置更新式变为

vi=w vi+c1r1pi-xi+c2r2pg-xi,xi=xi+ξ vi.

因此,聚群行为模块的执行流程如图1所示.

3.2 针对缺陷Ⅱ,采用自适应视野和步长

随着迭代次数改变的自适应参数能够在搜索的不同阶段执行不同的策略,其求解效率优于传统的固定参数方法.因此,本研究考虑将鱼群的视野和步长参数设置为自适应变化模式,其变化规则为

visual=maxvisual0×αvisiont,λ×visual0}.

其中:visual0为视野参数;αvision为视野衰减因子;λ为视野阈值,其范围在[0,1];t为当前迭代次数.

在追尾行为中,采用自适应步长的更新策略.该策略借鉴了狼群算法的思想.狼群算法(wolf pack algorithm,WPA)模拟狼群在捕食猎物过程中的协作行为,该算法设置了不同职责个体之间相互协作的搜索模式,包含头狼、探狼和猛狼3种个体:将当前适应度最优的个体作为头狼,头狼具有召唤猛狼靠近的能力;其余适应度较高的个体作为探狼,负责呼唤其他狼进行围攻行为;其余的狼作为猛狼.

处于游走行为时,整个狼群以游走步长移动;处于围攻行为时,狼群跟随头狼和探狼以围攻的方式按照小步长搜索;处于奔袭行为时,狼群以大步长向头狼的方向奔袭.在整个移动过程中,如果除头狼之外的个体搜索到适应度更优的位置,则该个体将替代原头狼成为新头狼.

受到狼群算法的启发,将追尾行为的迭代过程划分为3个区间,每个区间分别采用特定的搜索策略和目标,并通过自适应更新机制动态调整移动步长,从而增强搜索过程的灵活性和针对性,提高搜索效率和精度.

改进后追尾行为的自适应步长更新方式如式(20)所示.

step=lnρ1+η1 T1-tT1λ1 step0,0<t≤T1;lnρ2+η2 T2-tT2-T1λ2 step0,T1<t≤T2;lnρ3+η3 T-tT-T2λ3 step0,T2<t≤T.

其中:step0=maprange/S;maprange为三维地图的长宽高范围;S为步长因子;T1和T2为迭代次数阈值,用于将整个迭代过程划分成3个区间,且满足0<T1<T2<T;ρ1,ρ2,ρ3和η1,η2,η3为常数,用于调节对数函数的大小;λ1,λ2和λ3为常数,用于控制所在区间步长的大小,其大小关系为λ1>λ2>λ3,在不同迭代时期使用不同的步长,分别实现奔袭、游走和围攻的效果.

为了明确界定各时期的主要任务,整个迭代过程被划分为3个区间,分别对应迭代前期、中期和后期.随着迭代次数的增加,种群移动的步长逐渐减小:在前期采用大尺度的奔袭步长,有利于扩大探索范围,快速锁定最优路径的大致方向,避免陷入局部最优;后期采用小尺度的围攻步长,有利于逼近最优解,在小范围内进一步探索,提升搜索精度.追尾行为模块的执行流程如图2所示.

3.3 针对缺陷Ⅲ,采用正余弦算法完成随机行为

在传统人工鱼群算法中,如果不满足聚群行为或追尾行为的拥挤度条件,表明算法存在陷入局部最优的风险,那么将执行觅食行为和随机行为,通过随机搜索的方式探索新的解空间,以跳出当前的局部最优状态.

由此可见,觅食行为和随机行为探索新位置的能力决定了算法的整体收敛效率,且随机行为是兜底方案.但是,这两种行为都采用随机搜索方法,本质上没有区别,难以有效寻找到优质解.此外,随机搜索的效率较低,当问题维度较高时,随机采样点覆盖解空间的概率较低.因此需考虑改进随机行为的更新方式.

正余弦算法(sine cosine algorithm, SCA)利用正弦和余弦函数模型,促使解能够振荡性地趋近最优解.相比于随机搜索方法,该策略具有更强的全局覆盖和搜索能力,能有效应对高维问题,其基本原理如式(21)所示.

r1=σ-tσT,r2=2π×rand0,1,r3=2×rand0,1,r4=rand0,1,Xit+1=Xit+r1sinr2r3 Pit-Xit,r4<0.5;Xit+r1cosr2r3 Pit-Xit,r4≥0.5.

其中:σ是一个常数;r2,r3,r4均为随机因子,r2为区间[0,2π]内的随机数,r3为区间[0,2]内的随机数,r4为区间[0,1]内的随机数;Pit表示在第t次迭代时个体i的历史最优位置.

觅食行为和随机行为的执行流程如图3所示.

在改进后的方案中,用于兜底的正余弦搜索策略可以有效弥补觅食行为的无序搜索过程,将两个过程结合能够增强算法探索新位置的能力,更有利于跳出局部最优解.

3.4 改进的Sine混沌映射

为了保证粒子在初始状态的随机性和多样性,这里在种群初始化阶段引入混沌映射操作.混沌映射是一类具有较高随机性的非线性动力系统,能够产生看似无规律的混沌序列.

Sine混沌映射是一种经典的非线性映射系统,其表达式为

xi+1=μsinπxi.

其中:初始值x0为在(0,1)内的随机数;μ为映射控制参数,其取值可以是任意实数.

改进的Sine混沌映射的空间分布和频数分布情况分别如图4和图5所示.

本研究采用了一种改进的Sine混沌映射方法,具体的数学表达式为

ui+1=sinμπui,vi+1=sinμπui,wi+1=sinμπui,xi+1=ui+1+vi+12+wi+1-2%1.

其中:初始值u0,v0和w0是在(0,1)范围内的随机数;μ为映射控制参数,取值可以是任意实数;“%1”表示除以1之后取余数,即提取运算结果的小数部分.

该映射的概率密度分布非常均匀,随机性较强,其分布情况如图6和图7所示.

由原始的Sine混沌映射结果可知,虽然中间部分的数据点分布较为均匀,但在0和1附近的分布频率非常高,整体并不均匀,呈现两端密集、中间稀疏的情况.改进后的Sine混沌映射分布明显更为均匀,而且保持了良好的随机性.

4 改进人工鱼群算法的实现步骤

基于前文所述的分析和构想,本研究提出了一种改进的人工鱼群算法,具体分为7个步骤.

步骤1 生成环境地图,初始化算法中的各参数;设置人工鱼的初始速度为0,按照正态分布随机生成鱼群的初始位置,并将其更新为个体最优值;设置全局最优值为无穷大;更新最优适应度的值.

步骤2 探索视野范围内同伴位置的中心点及拥挤度,判断拥挤度是否大于最大拥挤度.若否,则执行聚群行为,采用基于模拟退火的粒子群算法实现位置更新,完成聚群行为后得到结果1,跳过步骤3转到步骤4;若是,则执行觅食行为,随机移动搜索新位置.

步骤3 完成觅食行为后,判断当前的搜索次数是否大于最大搜索次数.若否,则得到结果1;若是,则执行随机行为,通过正余弦算法搜索一个新位置,得到结果1.

步骤4 探索视野范围内最优个体位置及拥挤度,判断拥挤度是否大于最大拥挤限度.若否,则执行追尾行为,以狼群算法自适应步长的方式移动,完成后得到结果2,跳过步骤5转到步骤6;若是,则执行觅食行为,随机移动搜索新位置.

步骤5 完成觅食行为后,判断当前的搜索次数是否大于最大搜索次数.若否,则得到结果2;若是,则执行随机行为,通过正余弦算法搜索一个新位置,得到结果2.

步骤6 比较结果1和结果2的适应度值,选择较小者作为本次迭代的较优解,再判断该解的适应度是否小于全局最优解的适应度.若否,则不更新全局最优解;若是,则更新全局最优解.

步骤7 判断当前迭代次数是否达到最大迭代次数.若否,则将迭代次数加1,更新自适应参数,并返回步骤2;若是,则输出最终结果,流程结束.

算法的整体流程如图8所示.

5 地图建模与仿真方法

建模与仿真采用如下方法进行:将各种待测试算法在同一个测试地形图中迭代100次,然后比较各算法的性能.测试地形图采用基于指数函数构造的三维山地模型,具体表达式为

fx,y=∑n=1Nzn e-x-xnγn2-y-ynγn2.

其中:N为山峰的总个数;xn为第n个山峰中心的横坐标;yn为第n个山峰中心的纵坐标;zn为第n个山峰的高度;γn表示第n个山体高度在当前坐标轴方向的衰减量,γn越大,山体坡度越缓.

为了模拟实际山区的复杂地形状况,此处设置了一个包含10座山的地形图模型,并尽可能设置更多障碍物,以避免从起点走直线直接到达终点的情况,从而提升测试难度.

在本研究中,定义一个有限三维空间U以限定模型的范围,U=0,100×0,100×0,200,模型的三维视图如图9所示.每个山峰的横坐标、纵坐标、高度及衰减量的具体参数如表1所示.

在仿真过程中,每次迭代都更新3个控制点的位置.在完成一轮迭代之后,采用三次样条插值法拟合散点的方式得到一条曲线,用以表示算法搜索到的飞行路径.

图9中的方块表示起点位置,五角星表示终点位置.将三维空间的x,y,z三个维度离散化处理,均分为100等分,然后以3个控制点和起点、终点为基准,利用“spline函数”拟合出一条平滑的曲线.此外,还需要通过二维线性插值的方式判断其是否与障碍物相交,若不相交则选取该路径,否则重新寻找控制点并拟合曲线.

6 仿真结果分析

仿真部分对比7种算法的性能,为了便于描述,此处采用英文缩写的方式表示各算法:①PSO为基本粒子群算法;②AFSA为传统人工鱼群算法;③AFSA-SCA为正余弦算法替换人工鱼群的随机行为;④AFSA-WCA为利用狼群算法中多种固定步长的方式对人工鱼群的追尾行为进行优化;⑤AFSA-PSO为传统粒子群算法优化人工鱼群的聚群行为;⑥A-P-W-S表示将③,④,⑤的改进方法整合到人工鱼群算法中,是AFSA,PSO,WCA和SCA这4种算法的简单融合;⑦IAFSA(improved artificial fish swarm algorithm,IAFSA)是本文提出的改进算法,IAFSA在A-P-W-S的基础上,应用了基于模拟退火的改进粒子群算法,并加入了自适应鱼群视野和自适应追尾行为步长操作.

对各改进算法的仿真结果分析将从3个方面进行,具体来说,“算法收敛性能分析”结合适应度迭代图分析各算法的收敛速度和搜索精度;“路径的空间形态分析”结合曲率情况和三维视图,分析路径的三维形态及平滑程度;“算法稳定性分析”对比各算法在多次运行之后得到的适应度平均值和方差,分析这些算法获得解的稳定情况和算法实际执行的复杂程度.

6.1 算法收敛性能分析

L*=∑m=1M-1xm+1-xm2+ym+1-ym2+zm+1-zm2.

其中:L*表示计算得到的适应度;M表示空间分割的等分数;(xm,ym,zm)表示曲线在第m等分处的坐标;(xm+1,ym+1,zm+1)表示曲线在第m+1等分处的坐标.适应度能够反映曲线的长度,因此适应度越小,曲线越短,该路径更优.式(5)展示的是三维路径适应度的理论计算方法,在实际计算中,将按照式(25)的方式计算曲线的适应度.

该部分通过仿真得到了图10和表2中的结果.图10为各算法的迭代情况比较图,其横坐标表示迭代次数,纵坐标表示适应度.表2记录了各算法完成迭代后得到的最优适应度数据,表2中标注的“理论最优适应度”表示从起点到终点的直线距离.

由图10可知,PSO的收敛速度较慢,多次呈现平缓的阶梯型,说明该算法容易陷入局部最优;AFSA前期的收敛速度较快,但找到局部最优位置后便难以进一步探索;AFSA-SCA的收敛速度较慢,且无法在迭代中后期进一步搜索;AFSA-WCA在迭代前期有非常快的收敛速度,但过早陷入局部最优,被困住一段时间之后才恢复收敛;相较于PSO,AFSA-PSO的搜索精度有所提升,算法在迭代中后期展现出良好的探索能力,但一开始便陷入局部最优;A-P-W-S最终得到的适应度较低,在找到较优结果后仍然具备明显的局部探索能力,但收敛速度较慢;IAFSA得到的适应度最低,且收敛速度快,相较于A-P-W-S,IAFSA的性能有明显提升.

为了进一步分析这些算法的细节搜索能力,这里记录了算法达到较优适应度和最优适应度时的情况,结果如图11所示.在图11中,“达到最优适应度的迭代次数”指的是算法完成整个收敛过程所需的迭代次数;为了分析算法在细节处的优化能力,设计了“达到较优适应度的迭代次数”这一指标,它指的是当搜索到比最优适应度值略大的结果时,算法所需的迭代次数.

由图10可知,对于该问题的求解是不断获取更小适应度值的过程,通过100次迭代,最终会得到最小的适应度结果Lα.当执行到第tα代时,算法适应度降低至Lα,则认定tα为“达到最优适应度的迭代次数”.设定一个较小的区间系数ε,当算法执行到第tβ代时,其适应度值Lβ首次低于Lα+ε,则认定tβ为“达到较优适应度的迭代次数”.

此处设定ε=3,即当算法适应度降低至比最优适应度值大3个单位的范围内时,所需的迭代次数即为“达到较优适应度的迭代次数”,该指标能真实反映算法的收敛精度.

综合这两个指标来看,可以分析出算法的细节优化能力:当找到较优的结果后,算法是否还能进一步探索以提升精度.两项指标差距越大,算法的局部探索能力越强,搜索精度越高.由图11可知,PSO和AFSA算法两项指标的值相同,说明这两种算法在得到较好的结果之后就停止了进一步搜索,陷入了局部最优;而A-P-W-S和IAFSA在找到较优结果后,仍然能够在小范围内不断搜索更优的结果.

6.2 路径的空间形态分析

为了评估路径的优劣,这里对比6.1节所得结果的曲率及三维空间视图.将各条空间曲线分成100等分,然后计算每段的曲率值,得出各算法的曲率最大值及平均值,结果如表3所示.

表3中的“曲率最大值”可以反映曲线在最大拐弯处的弯曲程度,“曲率平均值”可以反映曲线的整体弯曲情况.由表可知,AFSA和AFSA-SCA的曲率最大值较高.

图12更加直观地呈现了这一情况,该图显示了7种算法路径曲线的曲率情况,横坐标表示曲线的段数,纵坐标表示曲率值的大小.由该图可知,AFSA和AFSA-SCA的曲率出现了较高的峰值,说明这两条曲线的弯曲程度较大;PSO和AFSA-WCA的曲率出现了多个峰值,说明这两条曲线存在多个弯曲位置;而AFSA-PSO,A-P-W-S和IAFSA的曲率全程都比较低,说明这些曲线比较平滑且拐弯次数较少.

为了更全面地分析各算法曲线的三维形态,接下来将通过三维视图分析曲线的空间情况.图13a为山体背景下的三维路径图,图13b为去掉山体的三维路径图.通过图13可以明显看出,AFSA的路径最长,弯曲程度最大,明显陷入了局部最优;IAFSA则在众多障碍物之间找到了一条较优的路径.A-P-W-S,AFSA-PSO和IAFSA都能较好地绕开障碍物并拟合出曲线.IAFSA路径避开了较大的障碍物,从山峰的空隙之间穿过,整条曲线平滑且直接,弯曲的幅度非常小,方向稳定,高程合理.

6.3 算法整体性能分析

算法的整体性能分析包含算法获取解的稳定性以及运算复杂度.为了得出更真实可靠的结果,本文将7种算法各运行100次.

为了探究算法是否每次都能获取有效解并分析其稳定性,本文通过仿真计算了适应度和每条曲线总曲率的平均值及方差.其中,总曲率是将空间曲线各等分段的曲率值相加得到的结果.各算法的适应度和曲率情况分别如表4和表5所示.

由表4可知,AFSA的适应度平均值和方差最大,说明该算法整体稳定性不佳;相比于AFSA,AFSA-SCA和AFSA-WCA的性能都有所提升;PSO作为一种经典的优化算法,具备一定的稳定性;基于AFSA和PSO改进的AFSA-PSO算法,其性能优于这两种传统算法;相比于AFSA-SCA和AFSA-WCA算法,AFSA-PSO,A-P-W-S和IAFSA的适应度平均值更小,且方差更低,性能更好.

由表5可知,AFSA的总曲率平均值最大,表明该算法所得曲线的弯曲程度最高、弯曲频率最大;AFSA-PSO,A-P-W-S和IAFSA的总曲率方差较小,说明这些算法得到的路径更为平缓顺畅.综合比较表4和表5数据可知,相较于AFSA和PSO算法,AFSA-PSO在适应度和曲率上都有非常明显的提升;A-P-W-S和IAFSA的适应度及曲率的平均值都较小,且方差也很低,说明这两种算法能够稳定有效地获取到较优的结果.

算法的复杂程度是一个不能忽视的指标,过高的运算复杂度会增加时间成本和硬件开销.这里将算法运行所需的时间视为算法复杂程度的反映.图14展现的是7种算法所需运行时间的平均值,其中时间的单位为s.由该图可知,PSO的平均运行时间最短,体现了该算法复杂度低的特性;AFSA的运行规则较多,然而其运行总时间较短,表明该算法具有执行效率高的优势;AFSA-SCA和AFSA-WCA在AFSA的基础上加入了改进操作,因此增加了复杂程度,导致AFSA-PSO和A-P-W-S的复杂度显著提高;IAFSA的运行总时间比A-P-W-S和AFSA-PSO低一些,虽然IAFSA在A-P-W-S的基础上添加了更多操作,但其中包括“自适应粒子群参数”“自适应视野”和“自适应移动步长”,这些自适应方法使IAFSA在搜索目标时更有针对性,而非盲目地重复固定操作,从而提高了算法的灵活性,降低了整体的复杂度.

7 结  语

本研究提出了一种改进的人工鱼群算法,一方面采用改进的Sine混沌映射初始化种群;另一方面结合粒子群、狼群和正余弦算法的思想,对传统人工鱼群算法进行优化.为验证优化效果,建立了三维模型地图,模拟飞行器在山区环境中的飞行情况;随后调试运行7种算法,得出适应度对比图和三维路径图,并对这些算法的性能进行对比和分析.改进后的算法具有如下优点:

1) 收敛速度快且搜索精度高.在迭代前期,算法反应迅速,能够快速掌握全局信息,避开较大山体的障碍,判断出最优解的大致方向;当接近较优解的位置后,算法仍然能够在小范围内不断调整,对结果进一步优化.

2) 路径短且安全可靠.算法最终能够搜索到适应度低的路径,而且整体平滑流畅,拐弯次数少,弯曲程度小;最终得出的路径短且平缓,对于飞行器运行意味着更小的风险和意外.

3) 算法复杂度适中,运行稳定性高.该算法巧妙运用自适应参数,使搜索过程更有针对性,从而将复杂度控制在合理范围内;通过多次运行后,适应度结果的均值和方差均较小,表明该算法具备稳定求解的能力.

此外,本研究提出的算法融合了多种算法,整体结构中涉及的参数较多,因此如何合理设置这些参数以最大限度地发挥算法性能可作进一步探讨;对飞行器进行动力学建模,能够研究基于已有路径的运动控制和轨迹跟踪方法,进而探究控制策略及能量损耗等问题,这亦可作为进一步的研究内容.

参考文献

[1]

Li B W, Zhang H H, Zhang L D, et al. Research on path planning and evaluation method of urban logistics UAV[C]//2021 3rd International Academic Exchange Conference on Science and Technology Innovation (IAECST). Guangzhou, 2021: 1465-1470.

[2]

Yang X J, Du Z J, Zhang D Y, et al. Research on dynamic path planning algorithm of UAV[C]//2021 IEEE 4th International Conference on Electronics Technology (ICET). Chengdu, 2021: 946-950.

[3]

Li G Q, Liang D W, Zhao Q Y, et al. Improved artificial fish swarm algorithm approach to robot path planning problems[C]//2020 5th International Conference on Automation, Control and Robotics Engineering (CACRE). Dalian, 2020: 71-75.

[4]

胡锟, 张亮. 罚函数凸优化迭代算法及在无人机路径规划中的应用[J]. 计算机应用研究, 2021, 38(3): 725-728.

[5]

Hu Kun, Zhang Liang. Penalty function convex optimization iterative algorithm and its application in UAV path planning[J]. Application Research of Computers, 2021, 38(3): 725-728.

[6]

Rocha G, Bradshaw J. Nonlinear optimal control for autonomous UAV flight planning[C]// 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Vancouver :IEEE,2017:6617-6622.

[7]

施成龙, 行鸿彦, 王水璋, 等. 融合三步平滑与改进RRT算法的无人机路径规划[J]. 电子测量技术, 2023, 46(23): 43-49.

[8]

Shi Cheng-long, Xing Hong-yan, Wang Shui-zhang, et al. UAV path planning combing three-step smoothing and improved RRT algorithm[J]. Electronic Measurement Technology, 2023, 46(23): 43-49.

[9]

顾秋逸, 李大鹏. 基于改进RRT算法的无人机路径规划[J]. 无线电通信技术, 2024, 50(6): 1184-1191.

[10]

Gu Qiu-yi, Li Da-peng. Unmanned aerial vehicle path planning based on improved RRT algorithm[J]. Radio Communications Technology, 2024, 50(6): 1184-1191.

[11]

Zhou Z W, Xing X J, Li Y, et al. Multi-UAV path planning based on potential field dense reward in unknown environments with static and dynamic obstacles[C]//2023 China Automation Congress (CAC). Chongqing, 2023: 1289-1294.

[12]

周文娟, 张超群, 汤卫东, 等. 一种新的基于强化学习改进SAR的无人机路径规划[J]. 控制与决策, 2024, 39(4): 1203-1211.

[13]

Zhou Wen-juan, Zhang Chao-qun, Tang Wei-dong, et al. A novel modified search and rescue optimization algorithm based on reinforcement learning for UAV path planning[J]. Control and Decision, 2024, 39(4): 1203-1211.

[14]

Ge F W, Li K, Xu W S, et al. Path planning of UAV for oilfield inspection based on improved grey wolf optimization algorithm[C]//2019 Chinese Control and Decision Conference (CCDC). Nanchang, 2019: 3666-3671.

[15]

Liang Q, Yang Z Y, Zhang J J, et al. An improved sparrow search path planning algorithm for UAV[C]//2023 19th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD). Harbin, 2023: 1-6.

[16]

Liu Y Z. Improved artificial fish swarm algorithm for UAV path planning in complex environments[J]. International Journal of Advanced Robotic Systems, 2015,12(6):1-10.

[17]

Wang G G. A hybrid artificial fish swarm algorithm for solving large-scale reliability-redundancy allocation problems[J]. Applied Soft Computing, 2013,13(5):2517-2532.

[18]

Chen J L. A multi-objective artificial fish swarm algorithm for UAV path planning[J]. IEEE Transactions on Aerospace and Electronic Systems, 2018,54(3):1235-1247.

[19]

Yang X Z. A parallel artificial fish swarm algorithm for UAV path planning in dynamic environments[J]. Journal of Intelligent & Robotic Systems, 2020,98(3/4):1-15.

[20]

Yan S K, Pan F, Xu J H, et al. Research on UAV path planning based on improved artificial potential field method[C]//2022 2nd International Conference on Computer, Control and Robotics (ICCCR). Shanghai, 2022: 1-5.

[21]

Zhang X, Xin B, Chen J. Differential evolution based path planning for UAVs surveillance in wind[C]//Proceedings of the 32nd Chinese Control Conference. Xi’an, 2013: 4220-4225.

[22]

Qi B L, Xiong L Y, Wang L J, et al. A weights and improved adaptive artificial fish swarm algorithm for path planning[C]//2019 IEEE 8th Joint International Information Technology and Artificial Intelligence Conference (ITAIC). Chongqing, 2019: 1698-1702.

[23]

Huang Y Q, Wang P P, Yuan M R, et al. Path planning of mobile robots based on logarithmic function adaptive artificial fish swarm algorithm[C]//2017 36th Chinese Control Conference (CCC). Dalian, 2017: 4819-4823.

[24]

Huang S, Li F Y, Cao X, et al. UUV path planning based on GA-AFSA algorithm[C]//2022 5th Asia Conference on Machine Learning and Computing (ACMLC). Bangkok, 2022: 117-121.

[25]

Lei Y M, Feng Z B. The optimization of fuzzy neural network based on artificial fish swarm algorithm[C]//2013 IEEE 9th International Conference on Mobile Ad-Hoc and Sensor Networks. Dalian, 2013: 469-473.

[26]

Li G Q, Liu Q, Yang Y W, et al. An improved differential evolution based artificial fish swarm algorithm and its application to AGV path planning problems[C]//2017 36th Chinese Control Conference (CCC). Dalian, 2017: 2556-2561.

基金资助

国家自然科学基金资助项目(62301514)

广东省基础与应用基础研究基金资助项目(2022A1515010760)

AI Summary AI Mindmap
PDF (2836KB)

892

访问

0

被引

详细

导航
相关文章

AI思维导图

/

〈 〉