基于混合PSO算法的简化群桥水域航路规划研究*

徐言民 杨 柯 高如江 金 城 陈 敏

(武汉理工大学航运学院 武汉 430063)

基于混合PSO算法的简化群桥水域航路规划研究*

徐言民 杨 柯 高如江 金 城 陈 敏

(武汉理工大学航运学院 武汉 430063)

针对群桥水域航路规划问题，分析了群桥水域特征，建立了群桥水域航路代价模型，分别运用基于自然选择的PSO、基于杂交思想的PSO和基于模拟退火的PSO对该问题进行了求解.通过与标准PSO算法规划结果对比，发现3种混合算法均能快速找到最优解，并且精度较高，得出了3种混合PSO算法在解决群桥水域航路规划问题方面均优于标准PSO算法的结论.

群桥水域；航路规划；标准PSO算法；混合PSO算法

随着沿江省市经济的高速发展，大量跨江桥梁呈集群化建设，以近距离多桥梁为特征的群桥河段已在多处水域形成.目前，桥梁船撞事故时有发生，群桥水域航路规划问题研究必要性日益凸显.现有航路规划研究方法种类较多，研究方向主要集中在无人机、机器人、导弹航路规划研究领域[1-2]，未涉及群桥水域的船舶航路规划问题.本文采用了3种混合PSO算法对群桥水域航路规划问题作了对比研究，为后期开展群桥水域航路规划研究奠定了基础.

1 群桥水域航路规划简化模型

群桥水域具有桥梁间距小、通航孔交错、水流变化显著[3]，以及交通流复杂等特点，船舶操纵难度急剧加大，极易诱发船-桥碰撞、船-船碰撞事故.本文旨在探索3种混合PSO算法对于群桥水域航路规划问题的适应性，因此可以将群桥水域简化建模为一系列距离较近并且纵向间距相等的圆形多障碍物航行水域.考虑到船舶自身大小，将障碍物半径按照船舶大小向外拓展，船舶可以看成一个质点，暂时不考虑船舶操纵性，在后期研究中可以考虑增加船舶操纵性约束条件对最优航路加以约束.船舶航行时需考虑燃油、障碍物等信息，航路规划的主要任务就是寻找一条从起始点(xs,ys)到目标点(xf,yf)路径最短且与障碍物无碰撞的路径.本文首先将航路规划问题转化为多维函数优化问题.将原坐标转换为以起始点和目标点连线为横轴的新坐标系X′OY′，θ为坐标系XOY与X′OY′的夹角.转换关系为

将起始点与目标点连线分为d+1份，在每个等分点做横轴的垂线，从起始点到目标点按顺序去各垂线上任一点组成一个路径序列点，用路径点纵坐标组成的向量y=(ys，y1，y2，…，yd，yf)即可确定一条惟一路径.

本文以路径最短和障碍物威胁最小为指标，障碍物威胁最小可按照文献[4]所采用的威胁计算模型，故目标函数可设为minJ=kJ1+(1-k)J2

当船舶沿着航路Lij航行时(见图1)，船舶的航路长度代价J1计算模型为

取相应的路径点计算产生的碍航代价，N个障碍物对其产生的总碍航代价J2为

若障碍物中心与该边的距离小于安全半径，则碍航代价可以按照下式计算.

图1 障碍物碍航代价示意图

综上所述，本文群桥水域航路规划代价函数可建立为

以船长L为单位，建立坐标系，本文起始点坐标(5，15)，目标点坐标(95，60)，障碍物设置为4座连续桥梁，共计14个桥墩，桥墩中心(15，15，15，15，55，55，55，55，80，80，80，35，35，35；27，47，67，15，35，55，75，30，55，85，60，35，15)，桥墩安全水域半径[5，5，5，5，6，6，6，6，8，8，8，7，7，7].

2 混合PSO算法航路规划

2.1 基于杂交思想的PSO算法

PSO算法在迭代过程中通过跟踪个体极值点和全局最优解以达到求解函数最优值的目标[5-6]，借鉴遗传算法中的杂交概念[7]，在每次迭代中，根据一定的杂交概率选取指定数量的粒子放入杂交池内，池中的粒子随机两两杂交，产生同样数目的子代粒子(child)，并用子代粒子替换亲代粒子(parent).子代位置由父带位置进行算术交叉得到：

child(x)=p×parent1(x)+(1-p)parent2(x)

式中：p为0到1之间的随机数.子代的速度为

设定种群数量为30，粒子维数20，迭代500次，根据实验，选取权重0.7，杂交比例为0.9，杂交池大小比例为0.2时算法效果较好，求解航路规划结果如图2，3所示.

图2 基于杂交思想的PSO算法航路规划结果

图3 基于杂交思想的PSO算法收敛曲线

根据图2和图3可以看出，基于杂交思想的PSO算法同样也能实现群桥水域航路规划，并且精度较高，算法在60代左右开始收敛，106代左右稳定收敛，稳定性较高.

2.2 基于自然选择的PSO算法

将自然选择机理与粒子群算法相结合得到基于选择PSO算法，其基本思想是在每次迭代过程中将整个粒子群按适应值排序，用群体中最好的一半粒子的速度和位置替换最差的一半粒子位置和速度，同时保留原来每个个体所记忆的历史最优值.对于本文所建立的航路规划模型，设定粒子种群数量为30，粒子维数20，迭代500次，结果如图4，5所示.

图4 基于自然选择的PSO算法航路规划结果

图5 基于自然选择的PSO算法收敛曲线

由图4～5可知，基于自然选择的PSO算法航路规划结果较为理想，计算速度较快，能迅速找到最优解，算法精度较高，航路较为平滑，算法在75代左右开始收敛，93代左右稳定收敛，算法稳定性高.

2.3 基于模拟退火的PSO算法

模拟退火算法在搜索过程中具有概率突跳的能力，能够有效地避免搜索过程陷入局部极小解[8].模拟退火算法在退火过程中不但接受好的解，而且还以一定概率接受差的解，同时这种概率随着温度的下降而减小，最终收敛于全局最优解.

在本文中其他2种混合PSO算法设置同样的种群大小、粒子维数和迭代步数，经过试验，选择学习因子2.05和退火常数为0.5组合结果较为理想，航路规划结果如图6，7所示.

图6 基于模拟退火的PSO算法航路规划

图7 基于模拟退火的PSO算法迭代曲线图

由图6，图7可知，基于模拟退火的PSO算法也能迅速搜索到最优解，算法在43代左右开始收敛，87代左右稳定收敛于最优解，稳定性较高.

3 混合PSO算法对比研究

3种改进方法分别借鉴遗传、自然选择和模拟退火的思想对PSO算法内部迭代过程中生成下一代粒子的方式进行修改，这种改进方式并不会对标准PSO算法适用性产生影响.为了便于观察，种群数量均设置为30，粒子维数为20，迭代步数设置为500步，将以上3种改进方法和标准粒子群算法分别运行3次，选择其中最优结果，对比情况如图8，9，10所示.

图8 混合PSO航路规划对比图

图9 混合PSO算法收敛曲线对比图

图10 混合PSO算法收敛速度

对比上述结果可知，与标准PSO算法相比，3种混合PSO算法无论是在收敛速度还是最优适应度值方面，均表现出了一定的优越性，3种改进算法最优适应度值均优于标准PSO算法，最优适应度值方面，基于杂交思想的PSO算法最优适应度值最小，模拟退火次之；收敛速度方面，模拟退火PSO的收敛速度最快，基于杂交思想的PSO次之.综合考虑，基于杂交思想的PSO和模拟退火PSO算法结果较为理想.

4 结 束 语

本文对针对群桥水域规划问题，建立了具有群桥水域的简化航路规划模型，运用基于杂交思想、自然选择思想和模拟退火思想PSO算法分别对模型进行了求解，并对混合PSO算法和标准PSO算法规划结果和收敛速度进行了对比研究，三种混合PSO算法收敛速度和最优适应度值均优于标准PSO算法，综合来说，基于杂交思想的PSO算法和基于模拟退火的PSO算法在收敛速度和最优适应度值表现较优，可以考虑应用该两种方法开展后期研究.

[1]ARNE A. BEDNAR N M, REINHARD M R. Improved 3D interpolation-based path planning for a fixed-wing unmanned aircraft[J]. Theory and Applications, 2013:1-13.

[2]马潇潇，张 宁.蚁群算法在巡航导弹航路规划中的应用[J].舰船电子工程，2013(3)：38-39,130.

[3]罗伟林，甘浪雄，邹早建.桥墩附近流场分布及对通航船舶的影响[J].中国航海，2014(1)：66-70.

[4]韩 超，王 赢.一种基于改进PSO的无人机航路规划方法[J].舰船电子工程，2014(4)：49-53.

[5]徐玉杰.粒子群算法的改进及应用[D].南京：南京师范大学，2013.

[6]黄太安，生佳根，徐红洋，等.一种改进的简化粒子群算法[J].计算机仿真，2013(2)：327-330，335.

[7]张干清，龚宪生.变量相关情况下基于杂交GA-PSO算法的结构协同优化[J].机械工程学报，2012(15)：113-125.

[8]郑申海，胡小兵，郑满满，等.改进粒子群和模拟退火混合算法及其应用[J].计算机技术与发展，2013(7)：26-30.

Study on Ship Route Planning in Multi-bridges Water Area Based on Hybrid PSO Algorithms

XU Yanmin YANG Ke GAO Rujiang JIN Cheng CHEN Min

(SchoolofNavigation,WuhanUniversityofTechnology,Wuhan430063,China)

To solve the problem of ship route planning in multi-bridges water area, the route cost model was established after analyzing the water features. Then, the Hybrid based PSO, Natural Selection based PSO, and Simulated Annealing based PSO algorithm are used to solve the model. It turns out that all of the Hybrid PSO algorithms are better than the standard PSO algorithm, which lays the foundation for the further study on this question.

multi-bridges water area；route planning；PSO；hybrid PSO algorithms

2015-03-20

*国家自然科学基金项目(批准号：51109173)、中央高校基本科研业务费专项资金项目(批准号：2013-II-019)资助

U612.1

10.3963/j.issn.2095-3844.2015.03.001

徐言民(1976- )：男，博士，教授，主要研究领域为通航安全保障、船桥防撞、自动控制