摘要：针对传统的人工绘制航线费时、费力、实用性差，准确度不高等缺点，本文采用改进的遗传算法来实现船舶航线的智能最优规划，保证了船舶自动化航行的安全性和经济性。

关键词：遗传算法; 航线规划; 最优航线

1 船舶航线规划设计

遗传算法是模拟生物在自然环境中的遗传、进化过程而形成的一种全局优化的搜索算法。该算法通过对问题的解集的种群进行编码，在初始的种群产生后，通过模拟生物界中基因的交叉，突变等过程，逐渐产生最优的近似解。但是该算法也存在寻优时间长等缺点，文章提出了一种改进遗传算法的方法来改善这一问题。

1.1 仿真环境的创建

最优航线规划设计的环境信息主要包括航行区域内的各种障碍物信息和允许自由航行的区域。首先，通过对整个航线空间栅格化，构成整体连通图，最优航线的规划设计便可在连通图上实现。

根据电子海图采用的S-57 标准，障碍物的区域由一个或多个多边形环组成，本文通过栅格法对障碍物的区域进行处理时， 通过下面的方法进行：①障碍物不满一个栅格算一个栅格；②若两个障碍物的中间区域较小，可视为一个障碍物；③为了保证航行的安全，对障碍物位置区域要进行必要的扩充。

1.2 遗传算法编码方案

船舶在障碍物仿真环境中航行路径的起点、终点是固定的， 但是经过的中间转向点是不确定的。由于规划的环境采用栅格的方法划分，因此文章采用变长的浮点数编码方式对航线的各个转向点进行编码，编码如图1 所示。如果起点为1 终点为16，那么可行的航线可表述为1-6-11-16，也可以表述为1-2-3-4-8-12- 16。为了增加遗传算法在航线编制时的可行性，只选择与当前点相邻的可行的点，如1 可选择2、6 作为下一个可行的点，以此类推这样就构成了从起始点到目标点的多条路径。

图1 栅格编码示意图

1.3 适应度函数的选择

遗传算法等进化算法选择适应度函数作为个体优略的评价标准，因此适应度函数的好坏影响整个算法的有效执行。本文引入可行路径和不可行路径的惩罚函数来评价个体的适应度大小。

1.4 遗传算子的操作

对于变长的浮点数遗传算法，遗传算子的定义对算法性能的提高至关重要。结合船舶航线优化问题，文中定义了选择算子、交叉算子、变异算子、插入算子等四种遗传算子。

1) 选择算子

选择算子是从当前群体中选择一些比较优良的个体，直接复制到下一代的群体中。本文采用基于赌盘法的适应度的分配方法，不通过遗传操作直接进入下一代个体。

2) 交叉算子

模拟自然界中生物体的染色体交叉过程，通过交叉行为，染色体基因的多样性得到了加强。本文交叉过程采用单点交叉，即把交叉位置后的基因进行基因的互换。

交叉前：

交叉后：

3) 变异算子

变异算子是模拟群体中个体基因座上的基因发生变动的情况。本文设计的变异算子是随机在路径中间转向点任意选取两个位置，并将该选取的两个转向点的位置的坐标进行互换。

4) 插入算子

在上述的交叉、变异操作之后，航线规划中相邻转向点间的连线有可能会穿过障碍物，所以需要在不可行路径的两个转向点间引入插入算子，插入一个不在障碍物内的转向点，保证航线路径合理避开障碍物。

2 最优航线设计

2.1 程序流程步骤

Step1 ：开始，获得海图信息，船舶航行空间建模。

Step2 ：初始化种群，设置种群大小。

Step3 ：计算种群个体适应度函数的大小；在种群中，选择具备较高适应度函数的个体进行遗传；个体根据交叉概率大小进行交叉操作；个体根据变异概率大小进行变异操作。

Step4 ：不可行的两个转向点之间进行插入操作，判断路径可行否，若不可行，重复执行Step4，若可行，程序顺序往下执行。

Step5 ：N 个个体的新种群满足，判断是否满足终止条件，若不满足，跳转至Step3，若满足，程序顺序往下执行。

Step6 ：最优航线输出，程序结束。

2.2 偏航区域

为了保证船舶在航行过程中的安全，文中利用偏航极限来判断航线的安全与否，若没有超出偏航极限就是安全的，否则就会进行航路检测报警。综上，航线设计时，“航线带”要以预定的航线作为中心线（如图2 实线），以偏航极限范围作为偏航距离（如图2 虚线所示），不同的航行任务和不同的船舶，航线带的宽度会有不同的设定。考虑规划航线两侧的偏航距离，以保证船舶的安全行驶。

3 算法仿真结果

为了验证文章中算法的有效性，用仿真软件MATLAB7.0 进行实验仿真。仿真中选取初始种群数为50，迭代次数为100，交叉率选取0.5，突变率选取0.05，采用以上的策略进行仿真，仿真结果下图3 所示，规划的最优航线为图中蓝色的实线，航线的偏航区域为红色的虚线，起始点用蓝色的三角形表示，终止点用红色的正方形表示。

图3 遗传算法规划最优航线

4 结论

在已知航海区域障碍物位置的前提下，本文提出了基于图的改进遗传算法为船舶设计出一条最优的航线，并且该算法克服了基本遗传算法搜索时间长，搜索精度低等缺点。通过仿真结果表明，该算法能够为船舶规划出一条安全、经济的航线。

参考文献

[1] 唐琳，蔡德荣，黄猛基于改进遗传算法的舰船路径规划[J] 北京计算机工程与设计200906

[2] 文泾，朱玉文一种基于遗传算法的航线规划算法[C] 山西西安中国航空学会控制控制与应用第十二届学术年会论文集 2006

[3] J.Holland,Adaptation in natural and artificial systems,Ann.Arbor:The university of Michigan

[4] Key,William H.AUV Acoustic Payload Integration. Oceans Conference Record(IEEE),Oceans 200009

[5] 张书源，郭聪基于遗传算法的最短路径问题及其MATLAB 实现[J] 北京交通世界 200906

[6] 吴进潮陈进才谈谈船舶的航线设计 [J]