关宏旭　徐言民　杨　柯　刘　强　王　岩

(武汉理工大学航运学院　内河航运技术湖北省重点实验室　武汉　430063)

针对群桥水域航路规划问题的PSO算法选比研究*

关宏旭徐言民杨柯刘强王岩

(武汉理工大学航运学院内河航运技术湖北省重点实验室武汉430063)

摘要：针对群桥水域航路规划问题，分析了群桥水域特征，建立了简化的群桥水域航路代价模型，分别运用标准PSO算法、权重改进PSO和学习因子改进PSO算法对该问题进行求解，并对不同改进方法的收敛速度和最优适应度值进行了对比分析，得出了异步变化学习因子PSO算法在几种改进策略中表现最优的结论，并应用算例进行验证，确定了后期深入研究群桥水域航路规划问题的方法.

关键词：群桥水域；航路规划；PSO算法；参数改进

关宏旭(1987- )：男,硕士，助理实验师，主要研究领域为通航安全保障、船桥防撞、自动控制

0引言

随着沿江省市经济的高速发展，大量跨江桥梁呈集群化建设，以近距离多桥梁为特征的群桥河段已在多处水域形成.2013，2014年武汉、南京长江大桥接连发生3起桥梁船撞事故，导致船舶沉没，桥墩受损，群桥水域的形成已经对水域通航构成了严重威胁.据统计，驾引人员失误是造成桥梁船撞事故的主要原因，因此进行群桥水域航路规划并最终实现桥区船舶自主航行是解决桥梁船撞问题的根本方法.目前航路规划研究方法种类较多，研究方向主要集中在无人机、机器人、导弹航路规划研究领域[1-3]，但未涉及群桥水域的船舶航路规划.本文采用粒子群((particleswarmoptimization,PSO)算法及其改进方法对群桥水域航路规划问题作了初步研究，并对各种改进方法进行对比分析，确定了后期研究所使用的算法.

1群桥水域航路规划模型

1.1群桥水域特征简要分析

群桥水域通常具有桥梁间距小的特点，以长江武汉段为例，到2015年，60km的江面上将拥有11座跨江大桥，其中白沙洲到天兴洲不足23km的武汉江面上就拥有桥梁7座，平均桥梁间隔约3km，桥梁间距较小；由于桥梁跨度、结构不同，不同桥梁通航孔也可能会不在同一轴线；桥梁通常建设在航道断面相对狭窄处，可航水域受限制；群桥河段轮渡、汽渡、游船等交通流也会对船舶正常通航造成影响；同时，由于桥墩挑流作用，群桥水域水流变化较为复杂[4].综上所述，群桥水域具有桥梁间距小、通航孔交错、水流变化显著,以及交通流复杂等特点，船舶操纵难度急剧加大，极易诱发船-桥碰撞、船-船碰撞事故.

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

根据群桥水域特征分析可知，桥梁间距小和通航孔交错是群桥水域主要特征.本文旨在探索不同改进方法的PSO算法在群桥水域航路规划问题的适应性，因此可以将群桥水域建模为一系列距离较近并且纵向间距相等的圆形多障碍物航行水域.考虑到船舶自身大小，将障碍物半径按照船舶大小向外拓展，船舶可以看成一个质点.船舶航行时需考虑燃油、障碍物等信息，航路规划的主要任务就是寻找一条从起始点(xs,ys)到目标点(xf,yf)路径最短且与障碍物无碰撞的路径.本文首先将航路规划问题转化为D维函数优化问题，将原坐标转换为以起始点和目标点连线为横轴的新坐标系X′OY′，θ为坐标系XOY与X′OY′的夹角.转换关系为：

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

本文以路径最短和障碍物威胁最小为指标，障碍物威胁最小可按照文献[5]所采用的威胁计算模型，故目标函数可设为

minJ=kJ1+(1-k)J2

式中：J为航路跟踪代价；J1为障碍物威胁代价；J2为航路长度代价；wt为航路上各点威胁代价；wl为每条边的长度;k为不同航路代价所占得比重，取0.5.

本文为计算方便，对坐标进行量纲一的量化处理，初步选定船舶长度为100m，用横向、纵向距离除以船舶长度即可实现量纲一的量化.起始点坐标(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算法[6-8]最重要的参数，惯性权重的大小直接影响PSO算法的全局和局部搜索能力[9]，针对权重的改进，一般有线性递减权重、自适应权重和随机权重3种.

1) 线性递减权重法在考虑实际优化问题时，往往希望先采用全局搜索，使搜索空间快速收敛于某一区域，然后采用局部精细搜索以获得高精度的解，因此可以采用线性变化的权重，让惯性权重从最大值线性减小到最小值，惯性权重随算法迭代次数的变化公式为：

式中：wmax，wmin分别为权重最大和最小值；t为当前迭代步数；tmax为最大迭代步数，经过试验，取ωmax=0.9,ωmin=0.4结果较为理想.

2) 自适应权重法为了平衡PSO算法的全局搜索能力和局部改良能力，还可采用非线性的动态惯性权重系数公式，其表达是如下.

式中：wmax，wmin分别为w的最大值和最小值；f为粒子当前的目标函数值；favg和fmin分别为当前所有微粒的平均目标值和最小目标值.

3) 随机权重法将标准PSO算法中的w设定为服从某种随机分布的随机数，在进化初期接近最好点，随机权重可能产生相对小的w值，加快算法的收敛速度，如果在初期找不到最好点，w线性递减可能使得算法最终收敛不到此最优点，随机w可以克服这种局限.随机权重的计算公式为：

式中：N(0,1)为标准正态分布的随机数.

4) 权重改进PSO算法流程权重改进PSO算法与标准PSO算法相比较，都是多出了权重更新步骤，权重更新后才更新粒子的速度及位置，其余步骤与标准PSO算法相同.3种权重改进的PSO算法流程图见图1.

图1　权重改进PSO算法流程图

5) 航路规划结果对比分析对于以上3种改进方法，分别运行3次，选择其中最优结果，对比情况见图2～3.

图2　权重改进PSO航路规划对比图

图3　 权重改进PSO算法收敛曲线对比图

对比上述结果可知，本文3种权重改进方法都能迅速找到精确解，分别从收敛速度和最优适应2个方面进行分析，结果见表1.

表1　权重改进PSO算法优化结果对比

由表1可见，自适应权重变化收敛速度最快，67代即开始收敛；线性权重递减方法适应度值最优，总体来说，3种改进方法在解决简化航路规划问题总体差异不是太大，都能迅速找到最优解，收敛速度均优于标准PSO算法.

2.2学习因子改进方法及其对比分析

在标准PSO算法中，学习因子c1和c2对PSO算法收敛能力影响较大[10]，通常取值2.在实际应用中，常见的学习因子变化方案有同步变化和异步变化2种方式.

2) 异步变化学习因子2个学习因子在优化过程中，其变化不同步，这样使得在优化初始阶段，粒子具有较大的自我学习能力和较小的社会学习能力，加强全局搜索能力，而在优化后期，粒子具有较强的社会学习能力和较小的自我学习能力，有利于收敛到全局最优解.学习因子的变化公式为

式中：c1,int,c2,int分别为c1和c2的初始值；c1,fin、c2,fin分别为c1和c2的迭代终值，经过试验，以下参数设置效果较好.

c1,int=2.5，c1,fin=0.5；

c2,int=0.5，c2,fin=2.5.

3) 学习因子改进PSO算法流程同样，学习因子改进PSO算法与标准PSO算法相比较，也只是多出学习因子更新的步骤，在学习因子更新之后才更新粒子的速度及位置，算法其余步骤与标准PSO算法相同.学习因子改进的PSO算法流程图见图4.

图4　学习因子改进PSO算法流程图

4) 航路规划结果对比分析分别运行2种改进方法3次，选择其中最优结果，对比情况见图5～6.

图5　学习因子改进PSO航路规划对比图

图6　学习因子改进粒子算法收敛曲线对比图

对比上述结果可知，针对本文所要解决的问题，2种改进方法都能迅速找到精确解，分别从收敛速度和最优适应2个方面进行分析，结果见表2.

表2　学习因子改进PSO算法优化结果对比

由表2可见，在解决群桥水域航路规划问题时，异步变化学习因子PSO算法无论是在收敛速度还是适应度值方面都表现出了极大的优越性.

3改进PSO算法航路规划对比

3.1对比结果分析

进过上述论述，针对PSO法权重、学习因子一共有5种改进方法，对于这5种改进方法，最后再各自运行3次，并对结果进行对比分析，规划结果及适应度值见图7～8.

图7　参数改进PSO航路规划对比图

图8　参数改进PSO算法收敛曲线对比图

图9　参数改进PSO算法适应度值及收敛代数对比

图9为适应度值及收敛代数对比.由图9可知，从收敛速度来讲，异步学习因子、同步学习因子、线性权重PSO算法收敛速度较快；从最优适应度值来说，异步学习因子和线性权重递减PSO算法适应度值最优.可以看出，异步学习因子变化PSO算法无论是在收敛速度还是适应度值方面都表现较为优异.

3.2算例分析

异步学习因子变化PSO算法在进行航路规划时，结果较为理想，为了验证该结论，在已建立的模型基础上，选择障碍物坐标[15 15 15 15 55 55 55 55 35 35 35;7 27 47 67 15 35 55 75 60 35 15]、障碍物安全半径[5 5 5 5 6 6 6 6 7 7 7]、起点[5,10]和目标点[75,65]的数据组合，采用异步学习因子变化PSO对模型求解，其规划结果及收敛曲线分别见图10～11.

由图10～11可知，异步学习因子变化PSO算法能够找到最优解，精度较高；算法在23代左右即开始稳定收敛，收敛速度较快，表明异步学习因子变化PSO算法在解决该类问题时表现优异，证明了本文结论的正确性.

图10　异步学习因子变化PSO算法航路规划示意图

图11　异步学习因子变化PSO算法收敛曲线

4结束语

本文分别运用PSO权重和学习因子改进方法进行了群桥水域简化航路规划，并对不同PSO改进策略进行了对比研究，在收敛速度方面，异步学习因子、同步学习因子、线性权重PSO算法收敛速度较快；在最优适应度值方面，异步学习因子变化PSO改进适应度值最优；综合来讲，异步学习因子改进PSO算法均表现优异，并根据算例对结论的合理性进行了验证，后期可考虑采用该种改进方法进一步开展群桥水域航路规划研究.

参 考 文 献

[1]HYONDONGO,SEUNGKEUNK,ANTONIOST.Coordinatedroad-networksearchrouteplanningbyateamofUAVs[J].InternationalJournalofSystemsScience，2014, 45(5): 825-840.

[2]ERGEZERH，LEBLEBICIOGLUK.3DPathplanningformultipleuavsformaximuminformationcollection[J].JournalofIntelligent&RoboticSystems，2014, 73(1-4): 737-762.

[3]李红亮，宋贵宝，曹延杰.多反舰导弹攻击多目标协同航路规划[J].系统工程与电子技术，2013(10)：2102-2109.

[4]艾万政，刘虎，丁天明.圆形桥墩紊流范围数值研究[J].武汉理工大学学报：交通科学与工程版，2013(5)：1003-1006.

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

[6]徐鹤鸣. 多目标粒子群优化算法的研究[D]. 上海：上海交通大学，2013.

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

[8]吴亚丽，徐丽青.一种基于粒子群算法的改进多目标文化算法[J].控制与决策，2012(8)：1127-1132.

[9]王俊伟，汪定伟.粒子群算法中惯性权重的实验与分析[J].系统工程学报，2005(2)：194-198.

[10]毕晓君，刘国安.种群分类粒子群改进算法研究[J].哈尔滨工程大学学报，2008(9)：991-996.

中图法分类号：U612.1

doi:10.3963/j.issn.2095-3844.2015.01.050

收稿日期：2014-11-19

ComparativeStudyonImprovedPSOAlgorithms
toShipRoutePlanninginMulti-bridgesWaterArea
GUANHongxuXUYanminYANGKeLIUQiangWANGYan

(School of Navigation,Wuhan University of Technology,Wuhan 430063,China)

(Hubei Inland Shipping Technology Key Laboratory,Wuhan 430063,China)

Abstract：To solve the problem of ship route planning in multi-bridges water area, the simply route cost model was established after analyzing the water features. Then, the PSO, ω improved PSO and c improved PSO algorithm are used to solve the model. Compared the convergence rates and optimal solutions of different improved PSO algorithms with each other, it concluded that the asynchronous change c PSO algorithm has the best performance, and a numerical example shows that this conclusion is reasonable, which lays the foundation for the further study on this question.

Key words：multi-bridges water area；route planning；PSO；parameters improved

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