基于差分进化算法的时间最优路径规划

© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 　　收稿日期 :2005 - 06 - 18 　　作者简介 :冯 　旭 (1970 - ) ,男 ,陕西长安人 ,工程师 ,研究方向为网络技术、数据库 . 第 18 卷第 3 期 2005 年 9 月 海南师范学院学报 (自然科学版) Journal of Hainan Normal University(Natural Science) Vol . 18 No. 3Sep . 2005 基于差分进化算法的时间最优路径规划 冯　旭 (西北民族大学 现代教育技术学院 ,甘肃 兰州 730030) 摘 　要 :提出了一种利用差分进化算法进行机器人路径规划的方法 ,在极坐标系下采用路 径点列的极角和极径作为参数进行个体成员的矢量合成 ,生成的初始路径点集经过提练处理 极大提高机器人移动速度 ;仿真结果表明该方法可以解决大范围、多障碍环境的机器人路径规 划问题. 关键词 :差分进化算法 ;路径规划 ;极坐标 中图分类号 :TP 301. 6 　　文献标识码 :A 　　文章编号 :1671 - 8747 (2005) 03 - 0006 - 04 差分进化 (Dofferemtoa ; Evolution 简称DE)算法是新近提出的一种智能优化方法 ,已被 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 在求优过程中 具有高效性、收敛性、鲁棒性等优点[1 ,2 ] . DE算法可以采用实数分量合成参数矢量 ,因此描述问题的方式接近 实际 ;同时其采用的变异操作具有遗传算法所不具备的微调功能 ,加之进化过程控制变量较少 ,因此本文尝 试利用 DE算法进行复杂环境下的机器人路径规划问题求解 ,并与同一问题采用遗传算法的运行结果进行 了比较 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 . 1 　差分进化算法 DE算法主要包括以下几个基本操作步骤 :参数矢量构造 ,初始群体生成 ,变异扰动矢量合成 ,交叉操作 , 边界处理以及目标函数的构造. 结合路径规划问题 ,以下各小节分别介绍 DE算法的实现过程. 1. 1 　参数矢量及初始群体的构造 同遗传算法一样 ,初始群体通常采用统一的概率分布来随机选择 ,第 g 代群体以 S ( g) 来表示 : S ( g) = { x1 ( g) , ⋯, xμ ( g) } . 其中 :μ为群体规模 ;个体 xi ∈Rd ( i = 1 , ⋯,μ) ,参数矢量由实数分量构成 ,表示一个优 化问题的一个可能解 ,其构成方式依据具体问题而定. 图 1 　规划环境的描述 路径规划范围和坐标系的选取如图1所示. O 点为极坐标原点 , Po 为 出发点 , PM +1 为目的地. 图中阴影多边形为规划场景内的地理阻隔或者障 碍物. 路径规划目的就是计算出一系列路径节点 Pi ( i = 1 ,2 , ⋯, M) 的位 置 ,其中每个节点的位置用 (ρi ,θi ) 来表示. 路径规划问题的个体参数矢量由以下 2 3 M 维实矢量构成 : x = (ρi ,θi , ⋯,ρi ,θi , ⋯,ρM ,θM ) . (1) 可以看出 ,过多的节点数量 M 势必增加计算量 ,影响进化速度. 合理的节 点个数应该使得进化过程的计算可以在合理时间范围内实现 ,同时不失去优良路径个体. 本文依据障碍数 量确定节点个数 ,根据大量仿真实验可知 ,节点个数应该取 T + 1 ～ T + 3 之间 ,其中 T 是障碍个数. 群体规 模中矢量个数 N 一般取 20 3 M ,亦即 10 倍于参数矢量的维数. 1. 2 　变异扰动矢量合成 不同于遗传算法按照一定的概率对子代基因位点进行变异操作的方式 ,DE算法对 g 代的每一个参数矢 量 xi ( i = 1 , ⋯,μ) 通过下式的计算得到其对应的 g 代扰动矢量 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net vi = xr1 + F ·( xr2 - xr3 ) . (2a) 式中 r1 、r2 、r3 ∈{1 ,2 , ⋯,μ} 是随机选取的整数 ,且满足 r1 ≠ r2 ≠ r3 ≠ i . F ∈[0 ,2 ] 是加权系数两个参数 矢量差别的放大倍数. 通常 ,还可以采用别的扰动矢量生成方法 : vi = xbest + F ·( xr2 - xr3 ) , 　　　 (2b) vi = xbest + F ·( xr1 + xr2 - xr3 - xr4 ) , (2c) vi = xi + F ·( xr1 + xr2 - xr3 - xr4 ) . (2d) 其中 xbest 为第 g 代中的最佳个体矢量 ,式 (2c) (2d) 都使用了随机选择的互不相同的两对参数矢量进行扰动 计算. 式 (2a) - (2d) 分别命名为 DEΠrandΠ1、DEΠbestΠ1、DEΠrandΠ2、DEΠbestΠ2 ,代表着 DE 算法的不同实现形 式 , rand 和 best 分别表示DE算法中被扰动的矢量为随机选取和第 g 代中的最佳矢量 ;1 和 2 分别表示采用 1 对或者 2 对矢量的差. 1. 3 　交叉操作及下一代群体生成 同遗传算法一样 ,在 DE算法中引入交叉操作以保持群体的多样性. 第 g 代参与交叉的两上矢量是互相 对应的原个体矢量和扰动矢量并产生一个新的矢量 x′( g) : x′i = CROSSOVER( xi , vi ) , i ∈{1 , ⋯,μ} , (3) 比较 x 和 x′即可以求得第 g + 1 代群体 : xi ( g + 1) = x′i ( g) Ф( x′i ( g) ) < Ф( xi ( g) ) , xi ( g + 1) = xi ( g) Ф( x′i ( g) ) > Ф( xi ( g) ) . (4) 式中 Ф为个体矢量的极小化目标函数. 1. 4 　边界处理 扰动矢量合成过程中计算出的矢量分量有可能超越实际问题取值范围 ,DE 算法一般采取下面方法处 理 : x ′ ij ( g) = βj x′ij ( g) > βj , αj x′ij ( g) < αj , 　j = 1 , ⋯, d ; i = 1 , ⋯,μ. (5) 其中βj 、αj 分别为参数矢量的最大值和最小值. 控制极角和极径 (ρi ,θi ) 的取值范围也是加快进化过程的一 个重要途径 ,在极坐标系框架内则可以方便直观地确定路径节点的极角和极径范围. 根据规划范围和障碍 分布情况 ,如图 2 所示 ,定出边界 OA (极角为θmin ) 和边界 OA (极角为θmax) ,同时确定极点的最近障碍点 Z . 图 2 　极角和极径的范围 考虑到机器人有时可能经过边界抵达目标 ,最大、最小极角可分别取为θmin - 5·和θmax + 5·. 极径的最小值取 | OZ | (1 - 1Π4) ,最大值取 | OPM | (1 + 1Π10) . 1. 5 　目标函数 本文采用如下算式计算每个参数矢量 x 的目标函数值 : Ф( x) = 62 i = 1 wi f i , 62 i = 1 wi = 1 , (6) 式中 wi 系权值系数 ,分别决定着对路径长度、障碍规避能力两个因素的重视程 度. f 1 表示图 1 中所有折线段的长度即路径长度. f 2 表示在所有折线段上固定步长采样所取得的点列集落在地理阻隔或者障碍物中点的个数. 如果障碍 区域为一多边形 ,判定该点是否在多边形的方法是对该多边形各边两两求夹角后累加 ,位于多边形内的点 , 逆时针方向旋转之总和为 + 2π,顺时针旋转为 - 2π,其绝对值为 2π,而任一位于多边形外的点 ,其夹角累加 之和为 0 ;如果障碍区域为圆形 ,则判断该点距圆心的距离是否大于圆半径即可. 2 　仿真实验 DE算法在求解路径规划问题时的可行性需要验证 ,本节首先比较不同形式DE算法的效果 ,然后对比了 512第 3 期 　　　　　　　　　　冯 　旭 :基于差分进化算法的时间最优路径规划 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net DE算法和遗传算法的运行结果 ,并通过实例说明了在实际应用中如何确定节点个数. 2. 1 　DE算法的不同实现形式 障碍区域及规划范围如图 2所示 , T = 4 ,先选取节点数为 M = 5 ,群体规模即种群数量选 100 ,交叉概率 取 0. 75 ,放大倍数 F 取 1. 2 ,以 (6) 作为目标函数 ,其中 w1 = w2 = 0. 5. 分别采用式 (2a) - (2d) 不同实现形 式 ,所消耗时间和目标最终目标函数值如表 1 所示 : 表 1 　DE算法的不同实现形式对比 实现形式 目标函数值 CPU 耗时Πh 进化代数 (103 ) DEΠrandΠ1 63. 335 0. 29 83. 2 DEΠbestΠ1 66. 479 0. 21 94. 5 DEΠrandΠ2 61. 285 0. 31 75. 6 DEΠbestΠ2 64. 904 0. 37 92. 6 由表可以看出 ,DEΠrandΠ2 虽然计算时间稍长于 DEΠrandΠ1 和 DEΠbestΠ1 ,但这种实现形式求得的路径最 短 ,并且进化代数最小 ,因此本文采用 DEΠrandΠ2 来进行求解. 图 3 　仿真实验图 2. 2 　与遗传算法运行结果比较 在各种参数一致的情况下 ,采用 DEΠrandΠ2 形式和采用的遗传算法比较 ,运算对比如表 2 所示 : 表 2 　DEΠrandΠ2 与遗传算法运算对比 算 　法 目标函数值 CPU 耗时Πh 进化代数 (103 ) DEΠrandΠ2 61. 285 0. 31 75. 6 遗传算法 65. 379 0. 14 42. 3 可以看出 ,DE算法具有更好的搜索性能 ,可以得到更优的目标函数值 ,遗传算法虽然在较短时间内得到 结果 ,但存在着过早收剑的问题. 由于引入了扰动矢量 ,DE 算法提高了个体矢量之间的距离和方向控制因 素 ,因此 ,在寻求全局最优解的同时 ,能更好地对每个可能的最优解进行进一步的局部优化 ,克服了遗传算 法过早收敛不足. 2. 3 　节点个数确定 节点个数 M 的选取应用依据障碍的分布密度而定 ,最大为 T + 3 ,最小取 T + 1. 图 3 中标注的[1 ]、[2 ]、 [3 ] 折线段分别是 M取7、6、5的计算结果 ,由于该图中障碍分布密度较小 ,选取较大的造成了不必要的拐点. 实际中 ,可以通过大量的实验方能合理确定. 2. 4 　路径点列的提练 DE算法产生的初始路径是由一系列依次连接节点的折线段组成的 ,有时可能造成不必要的拐点 (见图 3) , 从而响机器人的移动速度[3 ] .本文采用一种简练的方法来剔除这些拐点 ,其算法如下 : 输入 :path 　DE - DE算法产生的节点加上出发点和目标点构成的向量 ,即 [ P0 , P1 , P2 , ⋯, Pi , ⋯, PM , PM+1 ] . 输出 :提练后的路径向量 (图 3 中的虚线部分) . start = 0 ;target = M ; push 　vector (path 　DE[ start ]) ;finsh = false ; while ( ! finsh) { if (see (path 　DE[ start ]) ,path 　DE[target ]) ) { push 　vector (path 　DE[target ]) ; start = target ; target = size (path 　DE) - 1 ; if (start = = target) finsh = true ;} else{ target - - ; if (start = = target) {start + + ; 612 海南师范学院学报 (自然科学版) 　　　　　　　　　　　　2005 年 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net push 　vector (path 　DE[ start ]) ; target = size (path 　DE) - 1 ;}} 3 　结论 采用差分进化算法求解路径规划问题 ,具有实现简单、优化效果好等特点 ,仿真实验的结果表明该方法 适用于解决大范围、复杂障碍环境下的机器人运动路径规划问题. 参考文献 : [1 ] 　STORN R ,PRICE K. Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces[J ] . Journal of Global Optimization ,Kluwer Academic Publishers ,1997 ,11 :341 - 359. [2 ] 　STORN R. Sytem design by constraint adaptation and differential evolution[J ] . IEEE Transactions on Evolutionary Computation ,1999 ,3 (1) :22 - 34. [3 ] 　WANG C H. HONGJ G. Constrained minimum2time path planning for robot manipulators via virtual knots of the cubic b - spine func2 tions[J ] . IEEE Transactions on Automatic Control ,1990 ,AC - 35 (5) :573 - 577. Time optimal path planning based on differential evolution algorithm FEN G Xu ( School of Modern Education Technology , Northwest University for Nationalities ,Lanzhou 730030 , China) Abstract : This paper presented a novel method for robot path planning using the differential evolution (DE) algorithm under polar coordinate space . A single parameter vector was constructed by the polar angles and polar distance of waypoints and a refining process was adopted to remove the unnecessary points of path made by DE algorithm. Results of simulation show that this path planning method can be used to generate a path in the complex and multi2obstacle environment for the robot . Key words :differential evolution (DE) ; path planning ; polar coordinates (上接第 210 页) 注　当 T是一致φ- 伪压缩映像或不动点集非空的φ2伪压缩映像时 ,相应结果也成立 ,因而文章改进并推广了 Chidume C E[3 ] 、DengL 、Ding X P[4 ]等的相关结论 . 参考文献 : [1 ] 　CHANG S . S Iterative approximations of fixed points and solutions for strongly accretive and strongly pseudo2comtractive mappings in Banach spaces [J ] . J Math Anal Appl ,2004 ,1 998 :149 - 165. [2 ] 　TAN K K , XU H K. Approximating fixed points of nonexpansive mappings by the Ishikawa iteration process [J ] . J Math Appl , 1993 , 178 :301 - 308. [3 ] 　CHIDUME C E. Convergence theorems for strongly psedo2contractive and strongly accretive maps [J ] . J Math Anal Appl ,1998 ,228 : 245 - 264. [4 ] 　DENG L , DING X P. Iterative approximation of Lipshitz strictly pseudo2contractive mappings in uniformly smooth Banach spaces [J ] . J Nonlinear Anal ,1989 ,24 :981 - 987. A convengence theorem on fixed points of asymptoticallyφ- pseudo contractive mapping by ishika wa iterative process LIU Cai2gui ( Donggang College , Huaihai Institute of Technology , Lianyungang 222069 , China) Abstract :We used the modified Ishikawa iterative process to approximate the fixed points of asymptoticallyφ- pseudo contractive mappings . The result presented extends and improves many recent results . Key words :normalized duality mapping ; modified Ishikawa iterative process ;asymptoticallyφ- pseudo contractive mapping ; fixed point 712第 3 期 　　　　　　　　　　冯 　旭 :基于差分进化算法的时间最优路径规划