0 引　言

船舶航行路线设计是基于船舶航行的主客观需求，在构建航行环境模型的基础上，采用智能化算法规划全局船舶航行路线，实现最佳航行路径的规划，船舶航线设计是对其航行过程中航行环境信息分析性能的反映。随着技术手段的不断革新及智能化水平的提高，各种智能算法被引入到航行航线规划中，大幅提升了船舶航行效率与避障能力^[1]。

潘明阳等^[2]为防止船舶发生搁浅、碰撞事故，提出改进A～*算法的航线规划策略，在构建内河水网有向图网络的基础上，通过代价、估价函数及引入航道约束对A～*算法进行改进，以此完成航线规划目标，该算法可有效降低船舶搁浅事故的发生率，但该算法获取的最佳航线无法满足最短要求；童帮裕等^[3]为降低各因素对船舶航行的影响，减小事故发生率、保证船员人身安全，提出基于改进蚁群算法的船舶航线规划，该算法采用混合更新策略对蚁群算法进行优化，通过调整航线栅格上的信息素实现船舶可行航线的寻优，确定最佳航线，但该算法不但难于跳出局部最优怪圈，而且其收敛效率较低，还存在搁浅风险。和声搜索算法(HS)作为近年提出的智能化方法，具有结构简化特点的同时，还具备全局寻优性能，因其算法参数数量较低，大幅提高算法效率。但因其HMCR，PAR参数固定不变，大大影响了HS算法的寻优性能。本文提出改进和声搜索算法的船舶航行路线设计方法，避让航行环境中障碍物的同时，降低船舶搁浅风险，提高船舶航行路线规划的准确度。

1 船舶航行路线设计 1.1 基于K-means算法的海域栅格分类

通过K-means算法可实现相似数据的聚类处理。在对船舶航行路线规划时，需对船舶航行区域栅格作划分处理，使其包含多个方格，再在船舶航行环境中对可航、不可航海域进行标记，达到区分的目的。在此基础上进行船舶航线的设计，实现船舶航行路线规划。通常栅格的细密程度决定了障碍物的分类情况，其尺寸越小，障碍物标记得越完整，构建的船舶航行环境越逼真^[4]。由于栅格粒度具有差异性，导致时间消耗较大，且更耗用空间。另外，障碍物本身通常为非规则形状，容易与可航区域混合，难于区分其边界。因此，本文采用K-means算法实现栅格的聚类处理，将类似障碍物归于同一类别。利用Python软件工具实现栅格的聚类处理。首先获取聚类数目，表示为 $ K $ ，依据任意性规则获取聚类中心，数量为 $ K $ 。对数据作聚类处理，即对数量为 $ x $ 的数据进行聚类，将其划分成 $ K $ 个类别，确保类内数据具有较高相似性，类间数据表现出最大差异性^[5]。再对各类别数据至聚类中心点的距离进行求解，以此完成数据相似性的衡量，从而实现数据的分类处理。当聚类不发生改变后，确定距离最小的聚类中心，并对其进行更新，以此保证聚类结果更加合理。

1.2 船舶航行路线规划的数学模型 1.2.1 船舶航行环境及约束

统计不同状况下的船舶航行状态，分析航行环境是实现船舶航行路线规划模型设计的前提条件^[6]，采用网络优化高线法完成船舶航行环境的分析。船舶启航前的位置表示为 $ B $ ,航行任务终止后船舶所处位置表示为 $ O $ ,船舶从启航后，将经过若干个点方能抵达航线终点，令 $ {r_1},{r_2}, \cdots {r_{N - 1}} $ 表示船舶航行途中经过的若干个点，船舶航行路线可用下式进行描述：

$ {R_k} = \left\{ {B,{r_1},{r_2}, \cdots {r_{N - 1}},O} \right\} ，$

(1)

船舶航行需满足一定条件，因此，引入约束条件对船舶航行路线进行限制。通常采用的航行航线限制条件包括3种，一是以最近航行路径为条件对船舶航行路线进行限制，用 $ {l_{\min }} $ 描述，二是船舶航行路线满足最远路径要求，用 $ {l_{\max }} $ 描述，三是船舶在航行中途径最多的节点，通过 $ {M_{\max }} $ 反映。约束条件表达式描述为：

$ \left\{ \begin{gathered} {l_i} \geqslant {l_{\min }}，\hfill \\ L = \sum\limits_{i = 1}^M {{l_i} \leqslant {l_{\max }}}，\hfill \\ M \leqslant {M_{\max }} 。\hfill \\ \end{gathered} \right. $

(2)

式中：船舶航行线路表示为 $ {l_i} $ ；途经节点数表示为 $ M $ 。

1.2.2 船舶航行路线规划模型的构建

由式(1)、式(2)即可实现船舶航行路线规划模型的构建，可通过下式进行描述：

$ {f_k} = \min \sum\limits_{i = 1}^M {\left( {\lambda {}_1{l_i} + {\lambda _2}{f_{TAi}}} \right)}。$

(3)

其中：权值为 $ \lambda {}_1 $ ， $ {\lambda _2} $ ，危险代价为 $ {f_{TAi}} $ 。

船舶启航后，主要受以上影响因素威胁，致使船舶航行路线发生改变，船舶航行中各路段的危险代价总和即为船舶航行全航线的威胁^[7]。将船舶航行路线处理为3部分，先对各段路径所受威胁进行运算，再将其相加即可确定船舶航行的总危险代价，其公式描述为：

$ {f_{TAi}} = \frac{{{l_i}\displaystyle\sum\limits_{j = 1}^M {\left[ {{f_j}\left( {{4^{ - 1}}{l_i} + {2^{ - 1}}{l_i} + {\raise0.7ex\hbox{$3$} \mathord{\left/ {\vphantom {3 4}}\right.} \lower0.7ex\hbox{$4$}}{l_i}} \right)} \right]} }}{3}。$

(4)

1.3 基于改进和声搜索算法的船舶航行路线规划 1.3.1 和声搜索算法原理

和声搜索算法(HS)是近年来提出的智能优化算法，因其不受目标函数梯度信息的影响，在众多工程问题中受到广泛关注，该算法主要包含3个重要参数，分别为和声记忆库取值概率(HMCR)、微调概率(PAR)、音调调节带宽(bw)，和声搜索算法的基本原理为：

1）对HS算法的各个参数进行初始设置，包括HMCR，PAR，bw，设定 $ N $ 为变量数量，并对其值域范围进行定义，令 $ {T_{\max }} $ 为其迭代极值，对于和声记忆库，其数量表示为HMS。

2）对和声记忆库进行设定，基于各变量的值域区间并采用任意性原则获取解向量，HMS为其数量，通过下式描述：

$\begin{split} {\boldsymbol{HM}} =& \left[ \begin{array}{*{20}{c}} {x^1}& |& {f\left( {{x^1}} \right)} \\ {x^2}& |& {f\left( {{x^2}} \right)} \\ \vdots& | & \vdots \\ {x^{HMS}}& | & {f\left( {{x^{HMS}}} \right)} \end{array} \right] =\\ &\left[ \begin{array}{*{20}{c}} x_1^1& x_2^1& \cdots& x_N^1&|& {f\left( {{x^1}} \right)} \\ x_1^2& x_2^2&\cdots & x_N^2&|& {f\left( {{x^2}} \right)} \\ \vdots &\vdots &\cdots &\vdots &| & \vdots \\ x_1^{HMS}&x_2^{HMS} &\cdots &x_N^{HMS}& | &{f\left( {{x^{HMS}}} \right)} \end{array} \right]。\end{split} $

(5)

3）获得新和声。用 $ x' = \left( {{{x'}_1},{{x'}_2}, \cdots ,{{x'}_N}} \right) $ 表示获得的新和声，各音调表示为 $ {x'_i} $ ，且 $ i = 1,2, \cdots N $ 。音调可通过3种方式生成，分别为根据和声记忆库获得、小幅度调整音调或遵循任意原则选取，音调表达式描述为：

$ {x'_i} = \left\{ \begin{gathered} {{x'}_i} \in \left( {x_i^1,x_i^2, \cdots ,x_i^{HMS}} \right)\mathop {}\limits^{} {\rm{if}}\mathop {}\limits^{} rand \lt HMCR，\hfill \\ {{x'}_i} \in {X_i},{\rm{otherwise}}。\hfill \\ \end{gathered} \right. $

(6)

式中： $ i = 1,2, \cdots N $ ，对于变量 $ i $ ，其值域区间表示为 $ {X_i} $ ， $ rand $ 为任意数，其取值区间为[0，1]，呈均匀性分布特点。

从和声记忆库获取的和声，将 $ PAR $ 作为音调调节概率对其进行调整，通过下式描述：

$ {{x}^{\prime }}_{i}=\left\{\begin{array}{l}{{x}^{\prime }}_{i}+rand1*bw\;{\rm{if}}\; rand1 < PAR(离散型)，\\ {x}_{i}k+m{x}_{i},m\in \left\{-1,1\right\}\;{\rm{if}}\;rand < PAR\left(连续型\right)，\\ {{x}^{\prime }}_{i}\text{，}{\rm{otherwise}}。\end{array} \right.$

(7)

式中： $ i = 1,2, \cdots N $ ， $ rand1 $ 为任意数，其取值区间为[0，1]，呈均匀性分布特点。微调概率表示为 $ PAR $ ，音调调节带宽表示为 $ bw $ 。

4）对和声记忆库进行调整。将和声记忆库中最差和声 $ f\left( {{x^{worst}}} \right) $ 作为对比，实现新和声的判断，若满足下式条件，则完成和声记忆库的调整，由此便可获取到最佳路线。和声记忆库的调整条件为：

$ \begin{split} &if\;f\left( {x'} \right) < f\left( {{x^{worst}}} \right) = \mathop {\max }\limits_{j = 1,2, \cdots ,HMS} f\left( {{x^j}} \right) ，\\ &{\rm{then}}\; {x^{worst}} = x' 。\end{split} $

(8)

5）对HS算法的结束条件进行判定，当符合结束要求后，则可获得最佳搜索结果，即船舶航行路线规划结果，否则，退回步骤3，继续搜索。

1.3.2 基于自适应的和声搜索算法的改进

和声搜索算法参数对其收敛性、全局搜索能力起决定性作用，因此对和声搜索算法进行自适应改进，通过对各参数优化准确获取船舶航行路线，实现船舶航行路线的准确规划。对于传统和声搜索算法，其HMCR，PAR参数为定值，在对其改进过程中，期望在寻优初期将HMCR，PAR参数设定为较大值，以确保能够获得局部最佳解。在改进后期，将其设定为尽量小的值，保证解具有多变特性。采用通过迭代次数对HMCR，PAR参数进行更新的方法，实现和声搜索算法的改进。HMCR，PAR参数的更新公式描述为：

$ HMCR = HMC{R_{\max }} - \frac{{T\left( {HMC{R_{\max }} - HMC{R_{\min }}} \right)}}{{{T_{\max }}}} ，$

(9)

$ PAR = PA{R_{\min }} + \frac{T}{{{T_{\max }}}}\left( {PA{R_{\max }} - PA{R_{\min }}} \right)。$

(10)

式中：当下迭代次数表示为 $ n $ ，迭代次数极值为 $ {T_{\max }} $ 。通过确定参数 $ {d_1} $ ， $ {d_2} $ 实现 $ bw $ 参数的更新， $ bw $ 的求解公式描述为：

$ bw\left( i \right) = {d_1}*\left( {H\left( {i,\max } \right) - H\left( {i,\min } \right)} \right) + \frac{{{d_2}*\left( {x_{upper}^i - x_{lower}^i} \right)}}{T} ，$

(11)

$ {d_1} = \frac{{{d_{1\max }} - {d_{1\min }}}}{{{T_{\max }}}}T + {d_{1\min }}，$

(12)

$ {d_2} = \frac{{{d_{2\max }} - {d_{2\min }}}}{{{T_{\max }}}}T + {d_2}_{\max }。$

(13)

式中：对于参数 $ {d_1} $ ，其极大、极小值表示为 $ {d_{1\max }} $ ， $ {d_{1\min }} $ ，对于参数 $ {d_2} $ ，其极大、极小值表示为 $ {d_{2\max }} $ ， $ {d_{2\min }} $ 。若 $ {d_1} $ ， $ {d_2} $ 满足线性分布规律，且随着迭代次数的不断增长分别呈增加、减少趋势变化，可使改进和声搜索算法的船舶航行路线规划性能更突出。

HS算法是以任意方向实现新生成音调的微调，继续沿用此方式将加大改进和声搜索算法的计算难度，因此，对新和声微调方式进行改进，其改进公式描述为：

$ \begin{split} & {\rm{if}}\mathop {}\nolimits_{}^{} x_i^{new} \leqslant \overline {{x_i}} \;\;\;\;\;x{'}_i^{new} = x_i^{new} - bw\left( i \right) \\ & {\text{els}}e\;\;\;x{'}_i^{new} = x_i^{new} + bw\left( i \right) 。\end{split} $

(14)

其中：对于解 $ {x_i} $ ，其值表示为 $ x_i^{new} $ ，对其进行更新后，其值表示为 $x{'}_i^{new}$ 。在和声记忆库中，解 $ {x_i} $ 的均值表示为 $ \overline {{x_i}} $ 。

利用改进的和声搜索算法对船舶航行路线规划模型进行求解，实现其航行路线的设计。

2 实验结果与分析

在Python软件工具上模拟船舶航行环境，采用本文方法对船舶航行路线进行规划，为验证本文方法的航线规划性能，以30 km×30 km海域为研究对象，设定船舶航行起始坐标为(0,30)、终点坐标为(30,0)，首先需对船舶航行环境进行栅格划分，通过分析船舶航行环境地图，验证本文方法的聚类效果，实验结果如图1所示。可知，采用本文方法对船舶航行海域环境进行分析，通过聚类能够准确对船舶通行环境进行标注，达到区分的目的。其中陆地标注为黑色1、岛屿为黑色2，灰色标记为浅水区，其余均为可航范围。实验结果表明，本文方法可对船舶航行海域栅格进行聚类处理，实现不同通行环境的区分。

对本文HS及改进HS算法参数进行设定，两算法具有相同的HMS值及迭代次数极值，分别取40，300，在HS算法中，HMCR取值为0.7，PAR取值为0.35；改进HS算法的 $ PA{R_{\max }}{\text{ = }}0.95 $ ， $ PA{R_{\min }}{{ = }} 0.001 $ ， $ HMC{R_{\max }}{\text{ = }}0.95 $ ， $ HMC{R_{\min }}{\text{ = }}0.1 $ 。分别采用HS算法、改进的HS算法求取船舶航行路径，通过在Python软件工具上进行10次运行，各算法获取的船舶航行路径及其均值如表1所示。分析表1可知，分别采用以上2种算法对船舶航行路线进行设计，确定的船舶航线具有差异性，改进的HS算法确定航线长度短于HS算法，且各次运行结果未出现大幅度波动。由此可说明，改进HS算法性能更胜一筹。

在图1的船舶航行环境下，采用本文方法对船舶航行路线进行设计，并与文献[5]方法、文献[6]方法的航线规划结果进行对比，分析本文方法的航线设计能力，结果如图2所示。

各方法通过不断迭代实现船舶航行路线长度的确定，各方法的航线长度求解结果如表2所示。分析图3、表2可知，应用3种方法对船舶航行路线进行设计，得到3种不同的航线设计方案，本文方法获得航线规划路径最短，且能够准确避让障碍物及航行途中的浅水海域；文献[5]方法、文献[6]方法的航线规划路径均长于本文方法，且文献[6]方法未对航行途中的浅水海域进行避让，存在船舶搁浅风险。在运行时间方面，文献[5]方法、文献[6]方法的航线规划所需时间均高于本文方法，本文方法的船舶航行路线设计更具高效性。实验结果表明，本文方法具有船舶航行路线设计性能，航线规划路径最短、运行时间最小。

3 结　语

以30 km×30 km海域环境为研究对象，并利用Python软件工具进行模拟，通过对比分析改进前后HS算法的路线规划结果等指标验证改进算法的必要性；通过与文献[5-6]方法比较，分析本文方法的航行路线设计能力。实验结果表明：

1）改进后的HS算法具有更好的全局寻优能力。

2）本文方法可实现船舶航行路线的设计，路径长度更短、运行时间更短、路线规划能力优于文献方法。