基于改进遗传算法的舰船路径规划

1、14522009,30(6)计算机工程与设计ComputerEngineeringandDesign人工智能0引言舰船路径规划对于舰船实现自动化航行和航线优化具有重要的意义，要求在复杂的海上环境中，根据已知的地理信息数据，寻找出一条从起点到终点的最安全且航程最短的航线。传统的图搜索法、栅格法、人工势场法等都有一定局限性1。由于遗传算法在解决非线性问题上具有良好的适用性，已成为路径规划中使用较多的一种方法，被广泛的应用于机器人、飞行器的路径规划1-3。但是标准的遗传算法本身也存在着一些缺陷，如早熟、局部最优解、占据较大的存储空间和运算时间，并且在实际应用中缺乏对特定知识的利用2，保证不了对路径规

2、划的计算效率和可靠性要求。为了提高路径规划问题的求解质量和求解效率，本文提出了一种用于舰船路径规划的改进遗传算法，使用简单的编码方式，有效降低了遗传算法的搜索空间；根据舰船航行的特点设计了交叉算子、插入算子、删除算子和平滑算子。最后通过计算机仿真证明了改进后的遗传算法对于搜索效率和收敛速度都有显著的提高，并能保证收敛到全局最优解，克服了标准遗传算法的缺点。1应用于舰船路径规划的改进遗传算法在本文的舰船路径规划中，目标是在一幅障碍物分布已知的二维地图上寻找一条最优路径使到达目标点距离最短，同时尽可能地最大化与障碍物的距离。为了简化讨论，舰船被作为一个质点来考虑，而障碍物的边界向外扩张舰船的最大安

3、全距离。1.1路径编码编码长度是影响遗传算法收敛速度的重要因素之一，因此应当尽量使用简单的遗传编码4。舰船航行路径可以看作由起点和终点及一系列中间点组成的路径，其结构为(x0，y0)(x1，y1)(xi，yi)(xn，yn)式中：(x0，y0)起点，(xn，yn)终点，(xi，yi)起点和终点之间的一系列中间点，称之为转向点，i=1，2，n唐琳，蔡德荣，黄猛：基于改进遗传算法的舰船路径规划2009,30(6)145311,10图1路径编码平分成x1，x2，xn-1，则路径点可以简化为一维的y轴坐标编码形式，表示为y1，y2，yn，在遗传操作中，只需要对y轴坐标进行优化即可，可以大大的提高算法的

4、速度。1.2种群初始化执行遗传算法的最优航线设计，必须对种群进行初始化，由于初始路径是随机产生的，各转向点坐标可能分布在整个规划区域范围内，包括可行和不可行的，这样增加了搜索的范围，由于对原坐标进行了映射，也就是说每个转向点的横坐标是已知的，即x1，x2，xn-1已知，只需要在这些位置的垂直线上随机选取y坐标即可。另外，根据规划环境的复杂度不同，最优航线中转向点的个数也是不确定的，一般来说，环境越复杂转向点就越多，因此算法采用变长编码技术，通过对染色体进行删除、插入等操作，能够确定合适的转向点个数，使路径达到最优。但是转向点数目太多会占用太多资源，使运算速度变慢，因此，在运算过程中，设定一个最

5、大转向点Nmax，种群中每个个体的最大长度n满足：2nNmax。1.3适应度函数舰船的路径规划，具体说就是要在起点和终点之间找出一条最短的可行路径，约束条件是不与障碍物相交，同时还受自身体积的限制，舰船在航行中的转角不能太大，本文算法以3个条件来作为规划路径的可行性评价函数，即路径总长度、安全性、和各转向点拐角平均大小，对于不可行的路径对其适应度进行惩罚，使它的适应度差于可行路径。(1)路径安全性评价：为了防止舰船与障碍物碰撞，应尽量使其与障碍物保持一定的安全距离，假设舰船的安全半径为r，舰船与障碍物的距离为d，安全性的评价函数可以式(1)来表示=1(3)d(pi-1pi)是转向点pi-1与p

6、i之间的长度，如果pi-1与pi之间的路径不可行，则使用惩罚函数法对其适应度进行惩罚，惩罚函数定义如下,=01=1(4)式中：ci的定义见式(2)，=1(5)评价路径好坏是求路径长度最短的问题，通过惩罚因子，可以使不可行路径的变长，从而降低它的适应值。(3)路径平滑度：舰船的几何外形特点决定了其在航行过程中不能以大的拐角进行转向，因此整条行驶路径应平缓而光滑，即每一转向点处的拐角值应尽可能小。这里假设拐角最大值不能超过×=i(i=2，3，nii中大于或等于/2时，对适应度进行惩罚。当n=2时，路径为起始点与终止点的连线。若其可行，则M值为0，可以看出M值越小路径的平滑度越好。得到了以

7、上3个条件的评价函数，就可以获得整条路径的适应度函数。采用各项评价函数加权求和是常用的确定适应度函数的方法4-6，因为各个加权系数不是恒定不变的，而是随着路径和障碍物的情况变化而变化，这种情况下各个加权系数就很难调整和确定。因此，在确定适应度函数时，尽量使适应度函数的项数最少，但又必须把路径规划的3个条件融合在遗传优化过程中。这里采用评价函数相乘的形式，如式(7)所示f=S/(M*L)(7)以f作为选择操作的依据，路径的长度和平均拐角越小，其适应度越好。1.4遗传算子(1)选择算子：使用锦标赛选择法和精英保留法相结合的选择策略，锦标赛选择法在选择时先随机的在群体中选择K个个体进行比较，适应度最

8、好的个体将被选择作为生成下一代的父体，参数K称为竞赛规模。这种选择方式能使种群中适应度好的个体具有较大的“生存”机会。同时，由于它只使用适应度的相对值作为选择的标准，而与适应度的数值大小不成直接比例，从而避免了超级个体的影响，在一定程度上避免了过早收敛和停滞现象的发生。精英保留法即当前种群中适应度最好的个体不参加遗传操作，直接复制到下一代，替换经交叉和变异操作产生的子种群中适应度最差的个体，其优点是在搜索过程中某一代的最优个体可不被遗传操作所破坏，这样可以保证遗传算法以概率收敛到最优解。经验证明，保留占种群总体25数量的个体，效果最为理想7。(2)交叉算子：采用单点交叉法，在两个父体上分别随机

9、选取一个交叉点(起点和终点除外)，交换两个体在各自交叉点之后的染色体。考虑到规划路径的长度可变，为了防止交叉操作后出现过于繁琐或简单的路径，对生成的新个体长度进行限制，即最大长度不能超过Nmax，并且不能产生回路，若不符合要求，重亲获取两个父个体的交叉点。(3)插入算子：设计了两种插入算子，第一种是有针对性14542009,30(6)计算机工程与设计ComputerEngineeringandDesign的，即在连线穿过障碍物的两个转向点之间插入一个或多个转向点，使产生的路径避开障碍物，如图2(a)所示，第二种是一般意义上的插入，以一定的概率插入一个随机产生的转向点，如图2(b)所示。图2中虚

10、线部分为变异后的路径1,21(4)扰动算子：同样设计了两种扰动算子，第一种只选取路径不可行的转向点来进行小范围的调整，使其路径可行，如图2(c)所示；第二种是不管路径是否可行，任意选取一个位置，以概率pm对其转向点坐标进行调整，在进化初期，不可行解数量较多，调整的范围大一些，进化后期调整范围逐渐缩小，如图2(d)所示。(5)删除算子：建立一个存储空间REC，在一条路径中，如果点(xi-1，yi-1)与点(xi，yi)的连线经过障碍物，但(xi-1，yi-1)与(xi+1，yi+1)的连线不经过障碍物，则将点(xi，yi)添加到REC中。如果REC不为空，则从中随机选取一点删除(如图2(e)所示

11、)，否则，在路径中任意选取一个路径点以概率pd进行删除，如图2(f)所示。(6)平滑算子：平滑算子只对可行路径中最大的拐角进行操作。如图2(g)所示，删除拐角(a)(b)(c)图3各种环境下的仿真结果俞骏，刘以安：模糊模式识别在潜艇威胁等级判断中的应用表2待识别对象*2009,30(6)1457用价值。,参考文献:1234567崔国桓,于德新.非声探潜技术现状及其对抗措施J.火力与指挥控制,2007,32(12):10-13.姚敏.计算机模糊信息处理技术M.上海:上海科学技术文献出版社,1999.何新贵.模糊知识处理的理论与技术M.北京:国防工业出版社,1998.徐宗本,张讲社,郑亚林.计算智

12、能中的仿生学:理论与算法M.北京:科学出版社,2003.王晓君,魏书华.模糊理论在基于特征向量的模式识别中的应用J.计算机工程与应用,2007,43(10):81-83.庞庆华.基于灰色理论的软件系统人机界面综合评价模型J.计算机工程,2007,33(18):59-61.YuXueFeng,ChenShouYu.Afuzzydecisionmakingmodelformulti-objectivesystemsanditspropertiesC.HangZhou,China:Proceedingofthe5thWorldCongressonIntelligentControlandAutoma

13、tion,2004:2505-2508.89艾芳菊.基于多维加权贴近度方法的方案优选J.微计算机应用,2007,28(6):566-570.YoungWhanPark,HyunsungPark,SehunRhee,etal.RealtimeestimationofCO2laserweldqualityforautomotiveindustryJ.OpticsandLaserTechnology,2002,34(2):135-142.LA1A2A3A4A5wjJgF0.08为极度威胁，则在该海域内存在潜艇的可能性非常大，应该采取相应的反潜措施。从实验可以看出，利用模糊识别中的择近原则对多种探测技

14、术的特征值进行融合计算，提取最大的贴近度作为输出，可以有效地提高潜艇探测的精度和效率，从而提高反潜作战的效率。4结束语随着潜艇降噪技术的发展，出现了多种非声探测技术。针对单一探测技术的不准确性，本文运用了模糊模式识别技术，将多个非声探测技术的特征值进行模糊模式识别，利用其中的择近原则选择贴近度最大的模式作为输出，有效地克服了单一探测技术的不确定因素，提高了潜艇探测的准确性和可靠性。该方法在计算机上用Matlab语言进行了实验，计算结果令人满意。该方法丰富了模糊识别理论，拓宽了其应用范围，对于现代反潜作战具有较高的理论参考价值和工程应(上接第1454页)表1环境(a)运行结果对比标准遗传算法路径

15、长度进化代数610.3290本文遗传算法610.3225单，不能完全适应种群的变化情况，如何让算法根据种群进化情况自动调整和优化这些参数，还需进一步的研究和改进。参考文献:1234刘国栋,谢宏斌,李春光.动态环境中基于遗传算法的移动机器人路径规划的方法J.机器人,2003,25(4):327-330.唐国新,陈雄,袁杨.基于改进遗传算法的机器人路径规划J.计算机工程与设计,2007,28(18):4446-4449.李思海,白存儒.基于遗传算法的飞行器航迹规划研究J.华东交通大学学报,2007,24(4):147-150.NoboruN,HideoT.Pathplanningofanagric

16、ulturalmobilerobotbyneuralnetworkandgeneticalgorithmJ.ComputersandElec-tronicsinAgriculture,1997,18:187-204.56陈华华,郭晔,杜歆,等.基于改进型遗传算法的动态避障路径规划方法J.传感技术学报,2006,19(2):520-524.WoonggieH,SeungminB,TaeyongK.GeneticalgorithmbasedpathplanninganddynamicobstacleavoidanceofmobilerobotsC.IEEEInternationalConferenceonComputationalCyberne-ticsandSimulation,1997:2747-2751.78MatBuckland.游戏编程中的人工智能技术M.吴祖增,沙鹰,译.北京:清华大学出版社,2006:110-111.王小平,曹立明.遗传算法理论、应用与软件实现M.西安:西安交通大学出版社,2002:46-47.表2环境(b)运行结果对比标准遗传算法本文遗传算法860.7340路径长度进化代数942.25160从表1和表2中可以看出，不管是运行时间还是收敛的路径长度，本文的算法都要优于标准遗