0 引　言

无人水面艇（USV）是一种自主式水面航行器，具有无人化、智能化的突出优势。近年来，越来越多地被用于交通运输、水面搜救、海洋资源勘探、科学研究和军事用途等领域^[1]。无人水面艇路径规划^[2]研究已成为热点问题。路径规划通常需要在整体环境中规划一条最短路径或最优路径，早期常用的路径规划算法有A*算法^[3]、Dijkstra算法^[4]、快速扩展随机树等^[5]。

随着计算机技术的发展，计算机处理算法能力增强，智能仿生算法成为当今路径规划的一种主流算法，智能仿生算法具有约束多、灵活性高、寻优能力强、模块化设计方便、不同智能仿生算法之间去劣存优的优点，因此近年来许多智能仿生算法被应用于路径规划领域^[6]，杨晶磊^[7]采用一种改进的鲸鱼优化算法解决无人水面艇避障问题，林法君等^[8]针对复杂环境下USV全局路径规划问题，提出一种改进的粒子群算法。何加文等^[9]针对复杂环境下无人机突防过程中路径搜索能力不足的问题提出了一种改进的飞蛾扑火算法。

相比与上述改进算法，麻雀搜索算法^[10]其稳定性高、寻优精度较好、收敛速度快^[11]以及算法参数设置简单，全局搜索能力强的特点。本文针对原始麻雀搜索算法在路径规划过程中出现的种群初始化不够稳定，同时算法缺少变异机制，在后期迭代中种群多样性变差的缺点，容易陷入局部最优等缺点进行算法改进，提出一种改进麻雀搜索算法（Improved Sparrow Search Algorithm，ISSA），对算法进行数值模拟实验验证，以及二维路径仿真对比，使其路径优化仿真结果对未来USV的研究具有一定价值意义。

1 麻雀搜索算法

麻雀搜索算法由发现者、跟随者和警戒者组成，分别按照各自公式进行位置更新，更新公式如下：

$X_{i,j}^{t + 1} = \left\{ {\begin{array}{*{20}{l}} {X_{i,j}^t \cdot \exp \left( {\dfrac{{ - i}}{{\alpha \cdot ite{r_{\max }}}}} \right)，{R_2} < ST}，\\ {X_{i,j}^t + Q \cdot {\boldsymbol{L}}，{R_2} \geqslant ST} 。\end{array}} \right.$

(1)

式中：$X_{i,j}^{t + 1}$为第$i$只麻雀在第$j$次迭代次数为$t$时的位置信息；$ite{r_{\max }}$为最大迭代次数；$j \in [1,{{d}}]$；${{d}}$为整体维度；$\alpha$[0,1]为随机数；$R_2$（$R_2 \in [0,1]$）为预警值；$ST$（$ST \in [0,1]$）安全值；$Q$为服从正态分布的随机数；${\boldsymbol{L}}$为$1 \times d$维的全1矩阵。当${R_2} < ST$时，当前种群所处区域安全，因此下一次位置更新时，发现者将在环境附近继续搜寻食物，当${R_2} \geqslant ST$时，麻雀种群意识到危险，发现者将带领种群前往安全的区域。

$X_{i,j}^{t + 1} = \left\{ \begin{array}{*{20}{l}} Q \cdot \exp \left(\dfrac{{X_{{\mathrm{worst}}}^t - X_{i,j}^t}}{{{i^2}}}\right)，i > n/2 ，\\ X_p^{t + 1} + |X_{i,j}^t - X_p^{t + 1}| \cdot {{\boldsymbol{A}}^ + } \cdot {\boldsymbol{L}}，i \leqslant n/2 。\end{array} \right.$

(2)

式中：$X_{{\mathrm{worst}}}^t$为t时刻最差位置；$Q$为随机数；${\boldsymbol{A}}$为一个$1 \times d$维的矩阵，该矩阵中的元素随机赋值都是1或−1，并且${{\boldsymbol{A}}^ + } = {{\boldsymbol{A}}^{\rm T}}({\boldsymbol{A}}{{\boldsymbol{A}}^{\rm T}}){{\boldsymbol{A}}^{ - 1}}$。当$i \leqslant n/2$时，代表第i个跟随者正在最佳觅食区域附近觅食，当$i >n/2$时，第i个麻雀适应度值低，此麻雀将随机前往其他位置。

$X_{i,j}^{t + 1} = \left\{ \begin{array}{*{20}{l}} X_{{\mathrm{best}}}^t + \beta \cdot \left| {X_{i,j}^t - X_{{\mathrm{best}}}^t} \right|，{f_i} >{f_g}，\\ X_{i,j}^t + K \cdot \left(\dfrac{{|x_{i,j}^t - X_{{\mathrm{worst}}}^t|}}{{({f_i} - {f_{{\mathrm{worst}}}}) + \varepsilon }}\right)，{f_i} = {f_g} 。\end{array} \right.$

(3)

式中：$X_{{\mathrm{best}}}^t$为t时刻最优位置；$\beta$为随机步长控制系数，服从方差为1均值为0的正态分布^[12]；$K$为服从均匀分布的随机数；${f_i}$为当前第$i$只麻雀的适应度值；${f_g}$和${f_{{\mathrm{worst}}}}$为当前最优和最劣的适应度值，是为了避免零除法误差所设置的最小参数。当${f_i} = {f_g}$时，该麻雀需要改变位置来使适应度趋于最优适应度；当${f_i} >{f_g}$时，表示此麻雀将向着较优麻雀群体靠拢^[13]。

2 改进麻雀搜索算法 2.1 佳点集种群初始化

佳点集是由中国数学家华罗庚和王元^[14]提出。设$Gs$是s维欧式空间中的单位立方体，若${{r}} \in G{{s}}$，则：

${P_n}(k) = \left\{ {\left( {\left\{ {r_1^{(n)} \cdot k} \right\},\left\{ {r_2^{(n)} \cdot k} \right\}, \cdots \left\{ {r_{\text{s}}^{(n)} \cdot k} \right\}} \right),1 \leqslant k \leqslant n} \right\} 。$

(4)

其偏差φ(n)满足φ(n)=C(r, ε)n^−1+εcotθ只与${{r}}$和$\varepsilon$（$\varepsilon$是任意的正数）有关的常数，称则${P_n}(k)$为佳点集$r$为佳点。$\left\{ {{r_{{s^{}}}}^{(n)} \cdot k} \right\}$代表取小数部分，${{n}}$为点数，取$r = \left\{ {2\cos (2{\text{π}} k/p),1 \leqslant k \leqslant s} \right\}$（$p$为满足$(p - 3)/2 \geqslant s$的最小素数），将其映射到搜索空间为：

${x_i}(j) = (u{b_j} - l{b_j}) \cdot \left\{ {r_j^{(i)} \cdot k} \right\} + l{b_j} 。$

(5)

式中：$u{b_j}$和$l{b_j}$为$j$维的上下界。对于麻雀搜索算法，其种群初始化采用随机的方式生成，完全随机的方式会导致麻雀个体初始位置生成不稳定^[15]，导致搜寻路径失败。加入佳点集，算法寻优过程将不会受到初始种群生成异常的影响，提升了算法搜索能力，也保证了搜索精度。

2.2 螺旋搜索策略

根据发现者公式，在${R_2} < ST$时，发现者个体的每一维都在变小，在接近零点时，有较强的局部搜索能力，这导致了麻雀算法前期搜索范围不足、全局搜索能力不强，算法在迭代后期种群多样性下降。故提出螺旋搜索策略对发现者公式进行优化，提高算法全局搜索能力。

${{X}_{{\mathrm{pbest}}}^{\text{t}} = \left\{\begin{array}{l}w\cdot {X}_{{\mathrm{pbest}}}^{t}\cdot \mathrm{exp}\left(\dfrac{-i}{\alpha \cdot ite{r}_{\mathrm{max}}}\right)，{R}_{2} < ST且{r}_{1}\geqslant a，\\ {e}^{bl}\cdot \cos(2{\text{π}} l)\cdot \left|{X}_{i,j}^{t} - {X}_{{\mathrm{pbest}}}^{t}\right| + {X}_{\text{best}}^{t}，{R}_{2} \geqslant ST且{r}_{1} \lt a，\\ w\cdot {X}_{i,j}^{t}+Q\cdot L，{R}_{2}\geqslant ST。\end{array} \right.}$

(6)

式中：$w$为螺旋探索因子$b$为螺旋形状常数，其值为1；$L$是一个从1到−1线性递减的参数；$X_{\mathrm{pbest}}$为当前迭代个体的最优位置；${r_1}$为从0到1均匀分布的随机数；$a$为常数，取值为0.5。

2.3 Tent混沌映射策略

根据跟随者位置更新公式方程，当参与者向最优区域移动时，方向仅为1或−1，使得迭代后期容易陷入局部最优解，种群多样性差，因此在跟随着方程中加入tent混沌扰动公式；

${ {X}_{i,j}^{t+1} = \left\{\begin{array}{l}Q\cdot \mathrm{exp}\left(\dfrac{{X}_{\text{worst}}^{t} - {X}_{i,j}^{t}}{{i}^{2}}\right)，i > {n/2}，\\ {X}_{i,j}^{t} + (1-\lambda ) \cdot \left|{X}_{i,j}^{t} - {X}_{\text{best}}^{t}\right|\cdot {Z}_{{\mathrm{chaos}}}\text{ }i，\leqslant {n/2}且{r}_{2}\geqslant \beta ，\\ {X}_{\text{best}}^{t} + w\cdot \left|{X}_{i,j}^{t} - {X}_{\text{best}}^{t}\right|\cdot {\text{A}}^+\cdot \text{L }，i\leqslant {n/2}且{r}_{2} < \beta。\end{array} \right.}$

(7)

式中：${Z_{{\mathrm{chaos}}}}$为混沌变量；$\lambda$为均匀分布的随机数，$\lambda \in \left[0，1\right]$。

2.4 莱维飞行机制策略

Levy是对自然界中昆虫与鸟类觅食路径随机游走过程的模拟，其以大概率短距离搜索与小概率长距离搜索的方式交错移动，产生服从重尾分布的随机步长^[16]。

Levy分布用程序语言表示比较困难，通常采用Mantegna算法表示，在Mantegna算法中，其步长$s$为：

$s = \frac{\mu }{{{{\left| v \right|}^{1/\lambda }}}}。$

(8)

式中；$\mu 、v$均服从正态分布，$\mu {\text{～}} N(0,\sigma _{\mu} ^2)，v {\text{～}} N(0,\sigma _{v}^2)$。

${\sigma _\mu } = {\left\{ {\frac{{\Gamma (1 + \lambda ) \cdot \sin ({\text{π}} \lambda /2)}}{{\Gamma [(1 + \lambda )/2] \cdot \lambda \cdot {2^{(1 + \lambda )/2}}}}} \right\}^{1/\lambda }} 。$

(9)

通常${\sigma _v} = 1$，$\Gamma (\lambda )$为Gamma函数，$\lambda$取值影响Levy飞行的飞行轨迹，$\lambda$取值越大，算法开发能力越强。

$X_{i,j}^{t + 1} = \left\{ \begin{gathered} X_{{\text{best}}}^t + s \cdot \left| {X_{i,j}^t - X_{{\text{best}}}^t} \right|，{\text{ }}{f_i} >{f_g}，\\ X_{i,j}^t + K \cdot \left( {\frac{{\left| {X_{i,j}^t - X_{{\text{w}}orst}^t} \right|}}{{\left( {{f_i} - {f_w}} \right) + \varepsilon }}} \right)，{\text{ }}{f_i} = {f_g}。\\ \end{gathered} \right.$

(10)

使用Levy飞行随机数$s$代替$\beta$，使算法容易跳出局部最优解，并增算法的局部搜索能力、种群多样性和优化性能。综上所述，ISSA算法流程如图1所示。

3 算法仿真实验与分析

为了验证改进的麻雀搜索算法性能，采用实验所使用的测试集为基准公开测试集^[17]中的12个（见表1）测试函数进行实验。将粒子群算法（Particle Swarm Optimization，PSO）、鲸鱼算法（Whale Optimization Algorithm，WOA）、飞蛾火焰优化算法（Moth-Flame Optimization，MFO）、麻雀搜索算法（Sparrow Search Algorithm，SSA），以及改进的麻雀搜索算（Gold-Sparrow Search Algorithm，GSSA）与本文改进算法ISSA进行函数性能对比实验，ISSA算法与其他对比算法参数设置如表2所示，种群设置50，迭代次数设置为300，鉴于算法求解的随机性，将算法独立运行30次所有的函数都是最小化问题。

3.1 算法对比与分析

实验以最优值、标准差和平均值作为算法的性能评价指标，可说明算法的收敛速度，收敛精度和稳定性，实验数据统计如表3所示。

根据实验结果得知，ISSA在函数F₃、F₇、F₉、F₁₀、F₁₁、F₁₂中能够寻得最优值，虽然在F₁、F₂、F₄效果差于SSA算法，但在F₄、F₅、F₆、F₈测试结果相比于其他算法更加接近最优值，说明改进算法搜寻精度高，佳点集增强种群多样性效果良好，除F₁₁外ISSA的标准差在测试函数均能达到最佳效果，性能优于其他对比算法，说明螺旋搜索策略和tent混沌扰动策略能提有效高算法开发能力，ISSA在测试函数F₁、F₂、F₃、F₄、F₅、F₆、F₁₀平均值优于其他对比算法，剩余测试函数平均值最优解与对比算法相同，说明改进算法稳定性良好。

3.2 收敛速度对比

为了直观比较各改进麻雀搜索算法收敛速度，绘制30次实验中各轮迭代适应度值均值的变化曲线如图2所示。

图2为ISSA与其他对比算法在F₁～F₁₂收敛效果，其中F₁～F₆在函数迭代过程中收敛最快，F₆、F₈分别在第32次与第9次迭代就达到了最优解，收敛速度快，在函数F₇、F₈、F₉、F₁₀、F₁₁函数中ISSA求解初始化值最小。综上得出，ISSA在测试函数实验中的收敛速度与精度优于其他对比算法。

3.3 二维路径仿真实验

在进USV路径规划前选用栅格地图法^[18]任务环境建模。这里用矩形栅格表示地图，地图中分布的障碍物（黑栅格）、可行区域（白色栅格），并包含起点和终点，将SSA、GSSA、ISSA应用于栅格地图进行路径规划，实验环境与理论验证相同。

二维路径仿真模拟实验结果如图3～图5所示。可知，在20×20，栅格地图中SSA、GSSA、ISSA路径长度分29.7990、32.7421、29.2123。30×30地图中路径长度为44.5269、44.7696、42.7696。50×50地图中路径长度为75.7401、73.9828、73.3970。明显，ISSA全局搜索最优解能力强于另外2种算法。

为了防止仿真实验存在随机性，对不同大小栅格地图各进行30次独立的二维路径规划模拟仿真实验，结果如表4所示。可知，在3种地图中ISSA平均路径规划长度最小，分别为29.5842、44.0147、73.7049，证明在整体性能上ISSA优于GSSA与SSA，规划出来的路径更加平滑。

4 结　语

根据麻雀搜索算法存在的不足，对其进行针对性改进，增强了其初始种群多样性、全局搜索能力，优化了易陷入局部最优解的问题。通过测试函数实验验证改进有效性，结果表明ISSA算法具的求解速度和精度以及稳定性优于其他算法，在不同大小二维栅格地图仿真实验中，ISSA均能搜寻到最短路径，并且在30次仿真实验中计算出的平均路径最小。