基于改进基因算法的海洋平台巡检机器人路径规划.pdf

第 卷第期年月计算技术与自动化C o m p u t i n gT e c h n o l o g ya n dA u t o m a t i o nV o l ,N o J u n 收稿日期:基金项目:海洋石油工程股份有限公司科技项目(E P )作者简介:陈泽峰(),男,湖北襄阳人,硕士研究生,工程师,研究方向:仪表控制,智能化.通信联系人,E m a i l:c h e n z f c o o e c c o m c n文章编号:()D O I:/j c n k i j s j s y z d h 基于改进基因算法的海洋平台巡检机器人路径规划陈泽峰,李华山,赵瑞云,张家珍,苑宏钰(海洋石油工程股份有限公司,天津 )摘要:传统遗传算法最优路径搜索效率相对较低,容易产生无实际意义个体.为此,在遗传算法选择操作中引入邻域搜索算法,提高算法的局部搜索能力,调整可变长度染色体邻接点交叉算子进化操作,避免生成间断路径.同时,在变异操作中引入多样性约束与改进的A算法,提高遗传算法前期搜索效率.最后,在适应度函数中考虑路径长度、安全性和移动代价,生成的路径远离障碍物并在一定程度上降低转弯次数.实验证明,改进后的遗传算法在多障碍物环境下的路径规划过程中提高了搜索效率,更有利于找到实际应用中的最优解.关键词:遗传算法;A算法;变异;路径规划;适应度中图分类号:T E ;T E 文献标识码:AP a t hP l a n n i n go fO f f s h o r eP l a t f o r mI n s p e c t i o nR o b o tB a s e do nI m p r o v e dG e n e t i cA l g o r i t h mCHE NZ e f e n g,L IH u a s h a n,Z HAOR u i y u n,Z HANGJ i a z h e n,YUAN H o n g y u(O f f s h o r eO i lE n g i n e e r i n gC o,L t d,T i a n j i n ,C h i n a)A b s t r a c t:T h eo p t i m a l p a t hs e a r c he f f i c i e n c yo f t r a d i t i o n a l g e n e t i ca l g o r i t h mi sr e l a t i v e l y l o w,a n d i t i se a s yt og e n e r a t em e a n i n g l e s s i n d i v i d u a l s T h e r e f o r e,t h e i d e ao f s i m u l a t e da n n e a l i n gi s i n t r o d u c e di n t ot h es e l e c t i o no p e r a t i o no f t h eg e n e t i ca l g o r i t h mt o i m p r o v e t h e l o c a l s e a r c ha b i l i t yo f t h e a l g o r i t h m,a n dt h ee v o l u t i o no p e r a t i o no f t h ev a r i a b l e l e n g t hc h r o m o s o m ea d j a c e n t p o i n t c r o s s o v e r o p e r a t o r i s a d j u s t e d t oa v o i dg e n e r a t i n gd i s c o n t i n u o u sp a t h s A t t h e s a m e t i m e,d i v e r s i t yc o n s t r a i n t sa n da n i m p r o v e dAa l g o r i t h ma r e i n t r o d u c e d i n t o t h em u t a t i o no p e r a t i o n t o i m p r o v e t h e e a r l y s e a r c he f f i c i e n c yo f t h eg e n e t i ca l g o r i t h m F i n a l l y,t h ep a t hl e n g t h,s a f e t ya n dm o v e m e n tc o s ta r ec o n s i d e r e di nt h ef i t n e s sf u n c t i o n,a n dt h eg e n e r a t e dp a t hi s f a ra w a y f r o mo b s t a c l e s a n dr e d u c e s t h en u m b e r o f t u r n s t oa c e r t a i ne x t e n t E x p e r i m e n t s s h o wt h a t t h e i m p r o v e dg e n e t i ca l g o r i t h mi m p r o v e s t h es e a r c he f f i c i e n c y i nt h ep r o c e s so fp a t hp l a n n i n gi nam u l t i o b s t a c l ee n v i r o n m e n t,a n di sm o r ec o n d u c i v e t of i n d i n gt h eo p t i m a l s o l u t i o n i np r a c t i c a l a p p l i c a t i o n s K e yw o r d s:g e n e t i ca l g o r i t h m;Aa l g o r i t h m;m u t a t i o n;p a t hp l a n n i n g;f i t n e s s随着智能化和信息技术的迅速发展,海洋石油平台监控系统智能化水平变得至关重要.海上油气平台受限于特殊的作业环境,日常巡检工作耗费大量的时间和精力,由此可以将巡检机器人引入海计算技术与自动化 年月上油气平台生产检测工作,实现设备少人化值守、无人巡检的数字化管理,建设海上智能油田.巡检机器人采用激光/G P S进行自主导航和定位,其中关键技术是路径规划.路径规划是在二维或三维环境中,巡检机器人从起点移动到目标点找到一条无碰撞的最优或次优路径,并根据预先确定的约束条件对所得路径进行优化.海上油气平台的地形结构复杂,路径规划决定了巡检机器人能否实现可靠、高效的自主导航.路径规划是机器人技术中的一个核心问题,因为它的复杂性会随着配置区域的尺寸而显著增加,通常受到包括障碍物在内的大量环境信息的约束,已被证明是一个N Pc o m p l e t e难题.因此,路径规划在巡检机器人导航中起着至关重要的作用.根据巡检机器人作业环境信息,路径规划可分为全局路径规划和局部路径规划.全局路径规划根据已知的环境信息,计算出从起点到终点的最佳路径,主要包括蚁群算法、遗传算法、R R T算法、A算法等.局部路径规划对环境的先验信息较少,主要包括人工势场算法、人工神经网络算法、模糊算法等.在已有巡检路径算法研究的基础上,针对海上油气平台复杂环境及巡检路径特点,提出一种改进的自适应遗传算法,并结合遗传算法交叉、变异特性,引入种群多样性约束条件,不仅避免了算法局部最优解,还可以克服遗传算法早熟缺点.此外,为了提高算法收敛速度,在适应度函数中添加惩罚因子,路径转向次数越多,其适应度函数值越高,从而避免该路径遗传给下一代.实验结果表明,该算法能够有效应用于海上油气平台路径规划,降低了路径解移动代价和搜索时间,具有一定的理论支撑和应用价值.理论基础 工作空间模型考虑到海上油气平台形状大多为方形,设备布置固定,对静态障碍物海上油气平台环境使用基于网格的二维空间工作模型,为方便计算,将该空间划分为 m m相同大小的方格,如果空间边缘等无法划分为矩形,可以将其扩展到合适的形状,并将扩展的方格定义为障碍区.如图所示,其中表示可通过,表示障碍区,不可通过.S (a)(b)图工作空间模型示例 初始路径生成初始群体使用基于欧氏距离的启发式贪婪算法生成,贪婪算法以较小代价构建避开障碍物的初始路径,具体步骤为:随机选取一个中间节点pi,使用贪婪算法分别生成起始点S到中间节点无障碍路径PH(S,p,p,pi)、中间节点到目标点D的无障碍路径PH(pi,pi,pn,D).然后,将两条路径在中间节点处连接,构成一条初始路径,则单个路径P H(S,p,pi,pn,D).单个路径的长度由相邻路径点之间的欧氏距离相加得到,路径长度如公式()所示.Lnid pi,pi()nixi xi()yi yi()()适应度函数传统遗传算法适应度函数为路径相邻节点距离之和,以路径最短距离作为最优解评判标准,但靠近障碍物的潜在威胁仍然存在,为提高巡检机器人在运行过程中的巡检路径平滑度、运行时间和路径安全性,在传统遗传算法适应度函数基础上,增加巡检路径转向、靠近障碍物惩罚因子,经过多次迭代后,种群收敛于最优或接近最优解.适应度函数如式()所示:FLwmjO LjwT N()其中,L为各相邻节点长度之和,计算方法如公式()所示;O Lj为相邻节点穿过障碍物长度;第 卷第期陈泽峰,等:基于改进基因算法的海洋平台巡检机器人路径规划T N为路径总的转弯次数;w、w分别为路径穿越障碍点、转弯次数的惩罚因子,实际应用中取值较大,进而避免该路径在下一代遗传.改进基因算子 选择算子采用比例选择算子,同时为了避免适应度较好的个体被破坏,采用最优保存策略将每次迭代最优个体跳过交叉、变异操作,并保存至最优个体集合中,最优个体集合大小为种群的.交叉算子为解决传统交叉算子可能存在路径中断的问题,从最优个体集合中随机选择一条P H,与经过选择算子后的群体中任意一条路径P H进行交叉.结合最优保存策略集合中采用单点交叉算子,该算子流程如下:()随机选取最优路径P H(S,p,p,pi,D),in;当前群体P H(S,p,p,pj,D),jm;()在P H的每个路径点上,判断pi 与pj之间、pj 与pi之间是否连续,若连续,则执行步骤;()将子路径(pi,D)、(pj,D)在P H、P H间进行交换,从 而得到两条 无障碍子 路径P H(S,p,p,pi,pj,D)、P H(S,p,p,pj,pi,D),并替换当前种群适应度最大的个体.变异算子为解决传统变异算子潜在路径中断问题,采用启发式局部变异,选取个体上任意两个路径点P、P(起始点、目标点除外),使用改进的A算法生成一条从P到P的无障碍路径,可以将贪婪算法生成的路径进一步优化.改进A算法引入父节点到目标点的欧氏距离,增加了A算法评估函数中启发式代价的影响,改进的估价函数使A算法的搜索方向更有针对性地向终点靠近,可以减少算法中遍历点的数量,使算法效率得到改善,能够对贪婪算法生成的路径进一步优化.局部搜索为了避免遗传算法陷入局部最优解,增强遗传算法局部搜索能力,使用多样性阈值T判断个体是否进一步开展邻域搜索,进一步提高最优路径搜索效率,多样性阈值T计算如公式()所示.局部搜索步骤如下:)选取当前种群个体作为局部搜索对象;)依次将选取的局部搜索对象P Ho l d的任一中间节点pi作为圆心,以地图大小 为半径画圆,半径大小根据二维地图复杂程度决定;)选择圆中一点pj替换中间节点pi,并使用公式()检查新路径是否间断,若?,则路径间断.参考变异算子中路径连续方法,生成pi pj、pjpi 无障碍路径,形成一条起始点到目标点的无障碍路径P Hn e w(S,p,pi,pj,pi,pn,D),若P Hn e w适应值小于PHo l d,替换并结束该个体邻域搜索.m a xa b s xjxi(),a b s yjyi()()在迭 代 次 数 内 重 复 步 骤,直 到 达 到 结 束条件.多样性阈值传统遗传算法收敛性较差,无法避免遗传算法早熟的缺点,为了增强种群多样性,避免局部最优解,进一步研究种群多样性变化与局部搜索关系,当种群多样性低于阈值时,开展局部搜索,种群多样性如公式()所示,为了便于描述多样性并与阈值进行比较,将种群多样性转化为公式().Dnimj(xjx)(yjy)mn()式中,mj(xjx)(yjy)m为个体多样性;x、y分别为个体横纵坐标中心点;m为个体路径点数量;n为种群数量.Tm a xDm a xD()式中,m a x为多样性值最大个体;为固定常数,用以将T固定在,范围内.改进遗传算法模型改进遗传算法首先随机生成一个初始种群,通过适应函数评估每个染色体,保留最优个体不参与交叉、变异操作.然后使用交叉算子、变异算子创建新的后代,并根据阈值判断是否进行局部搜索,重复上述步骤,直到达到最大迭代次数,每次迭代都基于适应度函数来检查解决方案.当算法停止计算技术与自动化 年月时,返回最佳路径,改进的遗传算法流程如图所示.案例分析首先将遗传算法、文献、改进遗传算法在移动代价、算法运行时间上进行比较,验证改进遗传算法对路径规划的可行性和有效性,然后使用遗传算法、文献、改进遗传算法三种算法对复杂二维环境生成的路径进行比较,从路径质量、路径角度变化方面对算法性能进行评价,进一步验证改进遗传算法方法的实际应用价值.运用MAT L A B建立大小为 的二维环境格栅图,分别使用遗传算法、文献、改进遗传算法对图所示的空间模型进行巡检路径规划,为方便计算,将机器人通道设置为m(即格栅大小为mm),方法初始化参数详见表.图改进遗传算法流程表路径规划算法初始化参数参数名称初始化参数值迭代次数 初始种群大小 交叉概率 变异概率 改进A算法权重 适应度函数权重w 、w 种群多样性固定值 算法迭代 次找出最优路径,共计算 次最优路径移动代价、算法收敛时间平均值,三种路径生成算法的搜索时间、移动代价统计如表所示,可以看出,遗传算法、文献、改进遗传算法平均移动代价分别为 、.其中,改进遗传算法在平均收敛时间和平均移动代价上,均比遗传算法、文献要小,遗传算法所需时间最长,文献收敛速度较慢,导致算法早熟,陷入局部最优解.通过实验证明,对遗传算法交叉、变异、局部搜索调整和改进,在最快收敛时间内能够同时兼顾最小移动代价.表三种算法的平均移动代价、平均搜索时间遗传算法文献改进遗传算法代价时间代价时间代价时间 图显示了遗传算法、文献、改进遗传算法在二维格栅图中的最优路径收敛曲线,其中,改进遗传算法找到了全局最优解,遗传算法和文献算法收敛时间较长,只找到了局部的最优路径.遗传算法交叉变异操作均会对路径结构造成破坏,产生间断路径.文献对交叉变异操作进行调整,保护了路径连续性,但是局部搜索未作调整,导致算法前期收敛速度较慢,种群多样性没有进行实时调整,生成的最优路径也陷入局部最优解.改进遗传算法在种群多样性小于阈值时,将最优集合的个体替换当前种群适应度大的个体,并在交叉变异操作完成后开展局部搜索,因此,改进遗传算法在前期保证了群体的多样性,避免较好个体结构被破坏;交叉变异操作在保证路径连续的前提下,增加种群的多样性,使用改进A算法对选定节点之间进行路径优化,提高了算法收敛速度;适应度函数增加转向次数、靠近障碍物惩罚因子,以避免此类路径遗传至下一代,来优化巡检机器人移动代价.因此,改进遗传算法具有一定理论参考价值.图显示了遗传算法、改进遗传算法在二位格栅图中的最优路径,可以看出,改进遗传算法对适应度函数、交叉变异操作的改进和引入局部搜索,找到最优路径的迭代次数更少,转弯次数也大大减少,引入的惩罚因子也大大提高了路径安全性.第 卷第期陈泽峰,等:基于改进基因算法的海洋平台巡检机器人路径规划图三种算法最优路径图三种算法最优路径收敛曲线结论针对海洋石油平台复杂环境,提出了一种基于改进遗传算法的路径规划方法.在种群多样性小于阈值时,使用最优集合的个体替换当前种群适应度大的个体,并在交叉变异操作完成后开展局部搜索,保证群体前期多样性;交叉变异操作避免破坏路径连续性,使用改进A算法对选定节点之间进行路径优化,提高了算法前期收敛速度;在适应度函数中添加转向次数、靠近障碍物的惩罚因子来优化巡检机器人移动代价.与现有的遗传算法进行比较,结果表明,改进遗传算法能够找到全局最优路径.与其他方法相比,平均移动代价、平均收敛时间最小,算法搜索性能优于现有遗传算法.参考文献张蕾,靳泽园,李婷玉,等油田作业现场云端智能监控系统J计算机系统应用,():马小铭,靳伍银基于改进蚁群算法的多目标路径规划研究J计算技术与自动化,():王梓强,胡晓光,李晓筱,等移动机器人全局路径规划算法综述J计算机科学,():WAN G H W,Q IXY,L OUSJ,e ta l A ne f f i c i e n ta n dr o b u s t i m p r o v e dAa l g o r i t h mf o rp a t hp l a n n i n gJ S y mm e t r y,():王保剑,胡大裟,蒋玉明改进A算法在路径规划中的应用J计算机工程与应用,():孙波,姜平,周根荣,等基于改进遗传算法的A GV路径规划J计算机工程与设计,():王雷,李明,蔡劲草,等改进遗传算法在移动机器人路径规划中的应用研究J机械科学与技术,():