D0L:10.13374.issn1001-053x.2013.06.017 第35卷第6期 北京科技大学学报 Vol.35 No.6 2013年6月 Journal of University of Science and Technology Beijing Jun.2013 基于混沌粒子群-专用遗传算法切换策略的移动机 器人路径规划 张超，李擎网，董冀媛，韩彩卫，刘启晗 北京科技大学自动化学院，北京100083 ☒通信作者，E-mail:liging@ies.ustb.edu.cm 摘要为了发挥粒子群算法和专用遗传算法的各自优点，提出了一种将二者结合的切换优化策略。该策略前期采用一 种基于种群最优个体混沌化的混沌粒子群算法，后期选用专用遗传算法.通过大量仿真实验确定了在迭代代数、种群标 准差和最优个体适应度差三种切换指标下各自的最优切换条件.与单一专用遗传算法和单一混沌粒子群算法的仿真对比 表明：本文提出的切换优化策略在综合路径长度、平滑性和规划时间三个性能指标后具有一定的优越性 关键词移动机器人：路径规划：粒子群算法：遗传算法：切换 分类号TP242.6 Switch strategy based on chaos particle swarm optimization and spe- cialized genetic algorithm for path planning of mobile robots ZHANG Chao,LI Qing DONG Ji-yuan,HAN Cai-wei,LIU Qi-han School of Automation and Electrical Engineering,University of Science and Technology Beijing,Beijing 100083,China Corresponding author,E-mail:ligingaies.ustb.edu.cn ABSTRACT A switching strategy based on chaos particle swarm optimization and specialized genetic algorithm (CPSO-SGA)was presented by combining their own advantages.In the switching strategy,CPSO is applied in the former step and SGA is executed in the later step.The best switching conditions under three switching indices of iteration steps,population standard deviation,and optimal individual fitness values were determined by large amounts of simulation experiments.In comparison with single SGA and single CPSO,the proposed switching strategy CPSO-SGA has a better performance when path length,smoothness,and running time are taken into consideration. KEY WORDS mobile robots;path planning;particle swarm optimization;genetic algorithms;switching 移动机器人路径规划就是在具有障碍物的工传算法的适应度函数：冯琦和周德云6在极坐标 作环境中，按照规划时间、机器人运行时间、路径长 系下用遗传算法进行路径规划，缩小了搜索空间， 度及其平滑性、能量消耗等性能指标为机器人提供简化了编码方式，并对生成的初始路径进行提炼处 一条从起点到终点的最优或次优无碰撞可达路径. 理，剔除不必要拐点，取得了较好的效果.孙波等口 近年来，蚁群算法1-2、模拟退火算法3-4、 提出了一种基于粒子群算法的移动机器人全局路径 遗传算法6-)、粒子群算法7-等智能优化算法开 规划方法，该方法具有模型简单和算法复杂度低的 始大量应用于移动机器人的路径规划研究.文献⑤) 优点，但存在诸如容易陷入局部极小、搜索性能对 使用人工神经网络模型描述机器人工作环境并采用 参数依赖性大等缺陷.针对这些缺陷，国内外对粒 遗传算法优化路径，其中由神经网络的输出建立遗 子群算法提出了很多改进，如陶新民等⑨将粒子 收稿日期：2012-03-11 基金项目：教育部第36批留学回国人员科研启动基金资助项目(1341)：国家自然科学基金资助项目(60374032)：北京市重点学科 建设资助项目(XK100080537)
第 35 卷 第 6 期 北 京 科 技 大 学 学 报 Vol. 35 No. 6 2013 年 6 月 Journal of University of Science and Technology Beijing Jun. 2013 基于混沌粒子群--专用遗传算法切换策略的移动机 器人路径规划 张 超，李 擎 ，董冀媛，韩彩卫，刘启晗 北京科技大学自动化学院，北京 100083 通信作者，E-mail: liqing@ies.ustb.edu.cn 摘 要 为了发挥粒子群算法和专用遗传算法的各自优点，提出了一种将二者结合的切换优化策略. 该策略前期采用一 种基于种群最优个体混沌化的混沌粒子群算法，后期选用专用遗传算法. 通过大量仿真实验确定了在迭代代数、种群标 准差和最优个体适应度差三种切换指标下各自的最优切换条件. 与单一专用遗传算法和单一混沌粒子群算法的仿真对比 表明：本文提出的切换优化策略在综合路径长度、平滑性和规划时间三个性能指标后具有一定的优越性. 关键词 移动机器人；路径规划；粒子群算法；遗传算法；切换 分类号 TP242.6 Switch strategy based on chaos particle swarm optimization and specialized genetic algorithm for path planning of mobile robots ZHANG Chao, LI Qing , DONG Ji-yuan, HAN Cai-wei, LIU Qi-han School of Automation and Electrical Engineering, University of Science and Technology Beijing, Beijing 100083, China Corresponding author, E-mail: liqing@ies.ustb.edu.cn ABSTRACT A switching strategy based on chaos particle swarm optimization and specialized genetic algorithm (CPSO-SGA) was presented by combining their own advantages. In the switching strategy, CPSO is applied in the former step and SGA is executed in the later step. The best switching conditions under three switching indices of iteration steps, population standard deviation, and optimal individual fitness values were determined by large amounts of simulation experiments. In comparison with single SGA and single CPSO, the proposed switching strategy CPSO-SGA has a better performance when path length, smoothness, and running time are taken into consideration. KEY WORDS mobile robots; path planning; particle swarm optimization; genetic algorithms; switching 移动机器人路径规划就是在具有障碍物的工 作环境中，按照规划时间、机器人运行时间、路径长 度及其平滑性、能量消耗等性能指标为机器人提供 一条从起点到终点的最优或次优无碰撞可达路径. 近年来，蚁群算法 [1−2]、模拟退火算法 [3−4]、 遗传算法 [5−6]、粒子群算法 [7−8] 等智能优化算法开 始大量应用于移动机器人的路径规划研究. 文献 [5] 使用人工神经网络模型描述机器人工作环境并采用 遗传算法优化路径，其中由神经网络的输出建立遗 传算法的适应度函数；冯琦和周德云 [6] 在极坐标 系下用遗传算法进行路径规划，缩小了搜索空间， 简化了编码方式，并对生成的初始路径进行提炼处 理，剔除不必要拐点，取得了较好的效果. 孙波等 [7] 提出了一种基于粒子群算法的移动机器人全局路径 规划方法，该方法具有模型简单和算法复杂度低的 优点，但存在诸如容易陷入局部极小、搜索性能对 参数依赖性大等缺陷. 针对这些缺陷，国内外对粒 子群算法提出了很多改进，如陶新民等 [9] 将粒子 收稿日期：2012–03–11 基金项目：教育部第 36 批留学回国人员科研启动基金资助项目 (1341)；国家自然科学基金资助项目 (60374032)；北京市重点学科 建设资助项目 (XK100080537) DOI:10.13374/j.issn1001-053x.2013.06.017
第6期 张超等：基于混沌粒子群一专用遗传算法切换策略的移动机器人路径规划 827· 种群划分为随机和进化两个子群，通过协调两个子 搜索空间相对有限，此时应切换到专用遗传算法继 群的工作，克服了算法易陷入局部极小值的缺陷， 续搜索.标准差的计算公式如下： 并提高了算法的收敛速度和稳定性.Clercl1o提出 了在粒子群算法速度更新公式中引入压缩子(con- (x1-)2 N (1) striction factor)来控制粒子群算法的收敛趋势，该 法能够有效搜索解空间的不同区域，得到高质量的 式中，sd为标准差，N为种群规模，x为第i个粒 解。李擎等分别用专用遗传算法和混沌粒子群 子的适应度值，元为N个粒子适应度的平均值 算法进行了移动机器人的路径规划，并通过仿真对 比实验分析了两种算法各自的优缺点.本文提出了 开始 一种前期采用混沌粒子群算法(CPSO),后期使用 专用遗传算法(SGA)的切换优化策略，目的是为 了充分利用二者各自的优势，弥补相互之间的不足. 混沌粒子群算法 在移动机器人最优路径规划中的应用验证了本文所 否 提切换策略的有效性 是否满足切换条件 1混沌粒子群-专用遗传算法切换优化策略 1.1切换思想 是 本文采用的混沌粒子群算法具有全局搜索 专用遗传算法 能力强、对初始解质量要求不高等优点，但由于 每个粒子每一维均需同时更新，故其运算量较大， 否 搜索速度较慢.相比较而言，文献[11]中的专用 遗传算法的交叉、变异和删除操作只针对个别基因 是否满足终止条件 进行，其运算量相对于混沌粒子群算法而言要小得 是 多，且这种优势在路径规划这类维数高、约束条件 复杂的问题中表现得尤为明显，但其搜索效果严重 结束 依濑于初始解的质量.为了发挥混沌粒子群算法和 图1混沌粒子群-专用遗传算法切换优化策略流程图 专用遗传算法各自的优点，本文提出一种将二者结 Fig.1 Flow chart of the CPSO-SGA switching strategy 合的切换优化策略.该策略前期执行混沌粒子群算 法，主要是考虑到粒子群算法对初始解质量要求不 (3)最优个体适应度差.当最优个体适应度差 高的特点（当然，为了缩短混沌粒子群算法的搜索 值连续若干代小于设定的误差限时，说明种群已经 时间，这里仍采用启发式方法产生初始路径)进行 难以再进化，可以认为混沌粒子群算法发生了未成 全局搜索：后期采用专用遗传算法，将混沌粒子群 熟收敛，此时应切换到专用遗传算法作进一步的搜 算法收敛到一定程度后，具有较高质量（路径长度 索 较短、平滑性较好)的解群作为专用遗传算法的初 2仿真研究 始解，并利用其运算简单、搜索速度快的优点，进 一步进行局部搜索.切换策略简易流程如图1所示. 为了验证以上切换策略的有效性，本文在PC 1.2切换指标 平台上进行了仿真实验，其硬件平台为主频2.27 GHz的Intel Core3CPU和2 GB RAM.软件环 切换指标是切换策略中最主要的参数，对切换 境为Microsoft Windows7 Ultimate和Microsoft Vi- 策略效果有着至关重要的影响.根据实际情况本文 sual Studio 2002. 分别设计了三种切换指标，分别是迭代代数、种群 2.1切换优化策略不同切换指标仿真研究 标准差和最优个体适应度差 切换策略中的两种算法分别采用文献[11]中的 (1)迭代代数.混沌粒子群算法迭代到规定代 混沌粒子群算法和专用遗传算法，其中混沌粒子群 数时，切换到专用遗传算法 算法的惯性权重w取为0.5，加速度系数c1和c2 (2)种群标准差.标准差衡量了个体的分散程 都设为2，最大速度Vmax等于2，选用Chebyshev 度，当它较小时，说明种群个体间差别相对较小， 序列作为混沌模型.这里将切换策略的种群规模N
第 6 期 张 超等：基于混沌粒子群--专用遗传算法切换策略的移动机器人路径规划 827 ·· 种群划分为随机和进化两个子群，通过协调两个子 群的工作，克服了算法易陷入局部极小值的缺陷， 并提高了算法的收敛速度和稳定性. Clerc[10] 提出 了在粒子群算法速度更新公式中引入压缩子 (constriction factor) 来控制粒子群算法的收敛趋势，该 法能够有效搜索解空间的不同区域，得到高质量的 解. 李擎等 [11] 分别用专用遗传算法和混沌粒子群 算法进行了移动机器人的路径规划，并通过仿真对 比实验分析了两种算法各自的优缺点. 本文提出了 一种前期采用混沌粒子群算法 (CPSO)，后期使用 专用遗传算法 (SGA) 的切换优化策略，目的是为 了充分利用二者各自的优势，弥补相互之间的不足. 在移动机器人最优路径规划中的应用验证了本文所 提切换策略的有效性. 1 混沌粒子群--专用遗传算法切换优化策略 1.1 切换思想 本文采用的混沌粒子群算法 [11] 具有全局搜索 能力强、对初始解质量要求不高等优点，但由于 每个粒子每一维均需同时更新，故其运算量较大， 搜索速度较慢. 相比较而言，文献 [11] 中的专用 遗传算法的交叉、变异和删除操作只针对个别基因 进行，其运算量相对于混沌粒子群算法而言要小得 多，且这种优势在路径规划这类维数高、约束条件 复杂的问题中表现得尤为明显，但其搜索效果严重 依赖于初始解的质量. 为了发挥混沌粒子群算法和 专用遗传算法各自的优点，本文提出一种将二者结 合的切换优化策略. 该策略前期执行混沌粒子群算 法，主要是考虑到粒子群算法对初始解质量要求不 高的特点 (当然，为了缩短混沌粒子群算法的搜索 时间，这里仍采用启发式方法产生初始路径) 进行 全局搜索；后期采用专用遗传算法，将混沌粒子群 算法收敛到一定程度后，具有较高质量 (路径长度 较短、平滑性较好) 的解群作为专用遗传算法的初 始解，并利用其运算简单、搜索速度快的优点，进 一步进行局部搜索. 切换策略简易流程如图 1 所示. 1.2 切换指标 切换指标是切换策略中最主要的参数，对切换 策略效果有着至关重要的影响. 根据实际情况本文 分别设计了三种切换指标，分别是迭代代数、种群 标准差和最优个体适应度差. (1) 迭代代数. 混沌粒子群算法迭代到规定代 数时，切换到专用遗传算法. (2) 种群标准差. 标准差衡量了个体的分散程 度，当它较小时，说明种群个体间差别相对较小， 搜索空间相对有限，此时应切换到专用遗传算法继 续搜索. 标准差的计算公式如下： sd = vuutX N i=1 (xi − x¯) 2 N . (1) 式中，sd 为标准差，N 为种群规模，xi 为第 i 个粒 子的适应度值，x¯ 为 N 个粒子适应度的平均值. 图 1 混沌粒子群–专用遗传算法切换优化策略流程图 Fig.1 Flow chart of the CPSO-SGA switching strategy (3) 最优个体适应度差. 当最优个体适应度差 值连续若干代小于设定的误差限时，说明种群已经 难以再进化，可以认为混沌粒子群算法发生了未成 熟收敛，此时应切换到专用遗传算法作进一步的搜 索. 2 仿真研究 为了验证以上切换策略的有效性，本文在 PC 平台上进行了仿真实验，其硬件平台为主频 2.27 GHz 的 Intel Core i3 CPU 和 2 GB RAM. 软件环 境为 Microsoft Windows 7 Ultimate 和 Microsoft Visual Studio 2002. 2.1 切换优化策略不同切换指标仿真研究 切换策略中的两种算法分别采用文献 [11] 中的 混沌粒子群算法和专用遗传算法，其中混沌粒子群 算法的惯性权重 w 取为 0.5，加速度系数 c1 和 c2 都设为 2，最大速度 Vmax 等于 2，选用 Chebyshev 序列作为混沌模型. 这里将切换策略的种群规模 N
828 北京科技大学学报 第35卷 设为16，初始路径由文献11]所提专用启发式方法 差小于误差限的连续代数逐渐增加，路径长度变化 得到，以路径长度L、角度变化和S以及规划时间 不大，但平滑性有较大幅度提升，规划时间也有所 T的三者之和作为适应度函数值，终止条件为切换 增加.由于以上过程不具单调性，将三个评价指标 策略中专用遗传算法连续20代最优个体不变或切 综合考虑后，本文认为连续40代种群标准差小于 换策略整体达到最大的迭代代数1300. 0.01是该切换指标下的最佳切换条件. 2.1.1迭代代数 表1迭代代数作为切换指标时的仿真结果 为克服切换策略中的随机性，对每个迭代代数 Table 1 Simulation results when the iteration step is se- 均运行10次.不同迭代代数下路径长度、路径平滑 lected as the switching index 性和规划时间的平均值如表1所示.从表1中可以 迭代代数路径长度，L角度变化和，S/rad规划时间，T/s 200 60.051 0.204 看到，随着切换迭代代数的增加，路径长度和平滑 6.301 300 59.818 4.461 0.366 性的变化不大，但规划时间却持续增加，经过综合 400 59.465 3.844 0.394 考虑，本文中认为700为最佳切换代数 500 59.312 2.178 0.470 600 59.577 2.374 0.615 2.1.2种群标准差 700 59.284 2.300 0.640 当以种群标准差连续20~50代小于某一误差 800 59.475 1.955 0.815 限作为切换指标时，仿真程序运行10次后得到的 900 59.509 2.110 0.908 1000 59.149 3.006 1.051 路径长度、平滑性和规划时间的平均值如表2所示 1100 59.312 2.476 1.145 从表2可以看出，随着误差限逐渐变小，种群标准 1200 59.279 2.257 1.261 表2 种群标准差作为切换指标时的仿真结果 Table 2 Simulation results when the standard deviation of population is selected as the switching index 误差限 20代 30代 40代 50代 L S/rad T/s L S/rad T/s L S/rad T/s L S/rad T/s 0.01 59.513 3.2220.626 59.316 2.6350.137 59.044 2.567 0.527 59.0211.300 0.638 0.02 59.972 2.996 0.576 59.890 6.762 0.152 60.259 7.731 0.316 59.746 3.770 0.210 0.03 60.871 7.7880.210 60.885 10.4810.077 59.848 3.367 0.387 60.349 4.678 0.240 0.04 60.545 6.259 0.128 60.861 8.493 0.105 61.017 14.463 0.222 59.874 4.761 0.332 0.05 60.348 5.8260.184 59.953 7.7100.214 59.796 4.483 0.331 59.712 4.2420.631 2.1.3最优个体适应度差 加的趋势.将三个评价指标综合考虑后，本文选取 当以最优个体适应度差连续2050代小于某 连续30代最优个体适应度差值小于0.005为该切 一误差限作为切换指标时，仿真程序运行10次后 换指标下的最佳切换条件 得到的路径长度、平滑性和规划时间的平均值如表 2.1.4不同切换指标下的仿真对比研究 3所示.从表3可以看出，随着误差限变小，最优个 体适应度差值与误差限的连续代数增加，路径长度 将以上三种切换指标下各自的最佳切换条件 和平滑性变化不大，但规划时间却在总体上呈现增 加以对比，结果如表4所示 表3最优个体适应度差作为切换指标时的仿真结果 Table 3 Simulation results when the difference of optimal individual fitness values is selected as the switching index 误差限 20代 30代 40代 50代 S/rad T/s L S/rad T/s L S/rad T/s S/rad T/s 0.001 60.953 4.7310.347 58.938 1.4980.898 59.3533.008 1.147 59.536 2.8360.932 0.002 59.592 2.393 1.144 59.438 2.008 0.756 59.259 2.359 1.295 58.547 3.980 0.828 0.003 60.348 2.6450.630 61.300 5.673 0.618 59.227 3.832 0.876 59.814 3.113 0.738 0.004 59.832 3.183 0.360 61.132 6.020 0.602 59.502 4.824 0.865 59.807 3.154 0.795 0.005 59.305 2.208 0.737 58.735 1.295 0.782 60.274 2.969 0.604 59.943 4.165 0.669 0.006 58.951 2.322 0.932 59.099 2.921 0.390 60.604 5.800 0.597 59.489 4.297 0.754 0.007 59.204 4.207 0.342 58.715 3.178 0.882 60.229 6.697 0.418 60.976 6.982 0.634 0.008 59.649 3.672 0.262 59.645 6.686 0.593 59.721 2.980 0.639 60.803 6.184 0.693 0.00959.328 4.9850.326 60.2275.468 0.618 59.677 3.7020.635 60.0347.8360.435
· 828 · 北 京 科 技 大 学 学 报 第 35 卷 设为 16，初始路径由文献 [11] 所提专用启发式方法 得到，以路径长度 L、角度变化和 S 以及规划时间 T 的三者之和作为适应度函数值，终止条件为切换 策略中专用遗传算法连续 20 代最优个体不变或切 换策略整体达到最大的迭代代数 1300. 2.1.1 迭代代数 为克服切换策略中的随机性，对每个迭代代数 均运行 10 次. 不同迭代代数下路径长度、路径平滑 性和规划时间的平均值如表 1 所示. 从表 1 中可以 看到，随着切换迭代代数的增加，路径长度和平滑 性的变化不大，但规划时间却持续增加，经过综合 考虑，本文中认为 700 为最佳切换代数. 2.1.2 种群标准差 当以种群标准差连续 20∼50 代小于某一误差 限作为切换指标时，仿真程序运行 10 次后得到的 路径长度、平滑性和规划时间的平均值如表 2 所示. 从表 2 可以看出，随着误差限逐渐变小，种群标准 差小于误差限的连续代数逐渐增加，路径长度变化 不大，但平滑性有较大幅度提升，规划时间也有所 增加. 由于以上过程不具单调性，将三个评价指标 综合考虑后，本文认为连续 40 代种群标准差小于 0.01 是该切换指标下的最佳切换条件. 表 1 迭代代数作为切换指标时的仿真结果 Table 1 Simulation results when the iteration step is selected as the switching index 迭代代数 路径长度, L 角度变化和, S/rad 规划时间, T/s 200 60.051 6.301 0.204 300 59.818 4.461 0.366 400 59.465 3.844 0.394 500 59.312 2.178 0.470 600 59.577 2.374 0.615 700 59.284 2.300 0.640 800 59.475 1.955 0.815 900 59.509 2.110 0.908 1000 59.149 3.006 1.051 1100 59.312 2.476 1.145 1200 59.279 2.257 1.261 表 2 种群标准差作为切换指标时的仿真结果 Table 2 Simulation results when the standard deviation of population is selected as the switching index 误差限 20 代 30 代 40 代 50 代 L S/rad T/s L S/rad T/s L S/rad T/s L S/rad T/s 0.01 59.513 3.222 0.626 59.316 2.635 0.137 59.044 2.567 0.527 59.021 1.300 0.638 0.02 59.972 2.996 0.576 59.890 6.762 0.152 60.259 7.731 0.316 59.746 3.770 0.210 0.03 60.871 7.788 0.210 60.885 10.481 0.077 59.848 3.367 0.387 60.349 4.678 0.240 0.04 60.545 6.259 0.128 60.861 8.493 0.105 61.017 14.463 0.222 59.874 4.761 0.332 0.05 60.348 5.826 0.184 59.953 7.710 0.214 59.796 4.483 0.331 59.712 4.242 0.631 2.1.3 最优个体适应度差 当以最优个体适应度差连续 20∼50 代小于某 一误差限作为切换指标时，仿真程序运行 10 次后 得到的路径长度、平滑性和规划时间的平均值如表 3 所示. 从表 3 可以看出，随着误差限变小，最优个 体适应度差值与误差限的连续代数增加，路径长度 和平滑性变化不大，但规划时间却在总体上呈现增 加的趋势. 将三个评价指标综合考虑后，本文选取 连续 30 代最优个体适应度差值小于 0.005 为该切 换指标下的最佳切换条件. 2.1.4 不同切换指标下的仿真对比研究 将以上三种切换指标下各自的最佳切换条件 加以对比，结果如表 4 所示. 表 3 最优个体适应度差作为切换指标时的仿真结果 Table 3 Simulation results when the difference of optimal individual fitness values is selected as the switching index 误差限 20 代 30 代 40 代 50 代 L S/rad T/s L S/rad T/s L S/rad T/s L S/rad T/s 0.001 60.953 4.731 0.347 58.938 1.498 0.898 59.353 3.008 1.147 59.536 2.836 0.932 0.002 59.592 2.393 1.144 59.438 2.008 0.756 59.259 2.359 1.295 58.547 3.980 0.828 0.003 60.348 2.645 0.630 61.300 5.673 0.618 59.227 3.832 0.876 59.814 3.113 0.738 0.004 59.832 3.183 0.360 61.132 6.020 0.602 59.502 4.824 0.865 59.807 3.154 0.795 0.005 59.305 2.208 0.737 58.735 1.295 0.782 60.274 2.969 0.604 59.943 4.165 0.669 0.006 58.951 2.322 0.932 59.099 2.921 0.390 60.604 5.800 0.597 59.489 4.297 0.754 0.007 59.204 4.207 0.342 58.715 3.178 0.882 60.229 6.697 0.418 60.976 6.982 0.634 0.008 59.649 3.672 0.262 59.645 6.686 0.593 59.721 2.980 0.639 60.803 6.184 0.693 0.009 59.328 4.985 0.326 60.227 5.468 0.618 59.677 3.702 0.635 60.034 7.836 0.435
第6期 张超等：基于混沌粒子群-专用遗传算法切换策略的移动机器人路径规划 829· 表4三种切换指标下的仿真结果 Table 4 Simulation results under three switching conditions 切换指标 切换条件 路径长度，L 角度变化和，S/rad 规划时间，T/s 迭代代数 700 59.284 2.300 0.640 种群标准差 误差限0.01：连续40代 59.044 2.567 0.527 最优个体适应度差 误差限0.005：连续30代 58.735 1.295 0.782 综合考虑表4中的各项指标后，本文将连续30 见，本文所提切换策略在综合性能上较单一算法具 代最优个体适应度差小于0.005作为本仿真环境下 有一定的优越性.SGA、CPS0和CPSO-SGA在10 的最佳切换条件.切换策略在三种切换指标各自最 次运行中的最优路径如图3所示 佳切换条件下10次运行中的最优路径如图2所示. 40 CPSO-SGA 最优个体适应度差 End 35 CPSO SGA 35 种群标准差 迭代代数 30 30 25 20 .20 15 10 10 Start 10 152025 30 35 Start 10 1520 25 30 35 图3SGA、CPSO和CPSO-SGA的最优路径 Fig.3 Optimum paths of SGA,CPSO and CPSO-SGA 图2三种切换指标在各自最优切换条件下的最优路径 Fig.2 Optimum paths under the best switching conditions 3结论 of three switching indices 2.2混沌粒子群-专用遗传算法切换策略同单一 (1)提出了一种用于机器人路径规划的混沌粒 算法对比 子群-专用遗传算法相切换的优化策略，并探讨了 将本文所提切换策略同文献[11]中的单一专用 三种不同的切换指标. 遗传算法及混沌粒子群算法进行仿真对比，其中本 (2)将所提切换优化策略与单一专用遗传算法 文切换策略的切换条件为连续30代最优个体适应 及单一混沌粒子群算法进行了简单静态障碍物环境 度差小于0.005，进行10次仿真程序得到的平均结 下的仿真对比研究，仿真结果表明本文所提切换优 果如表5所示. 化策略在路径长度、平滑性和规划时间三方面上的 综合表现要优于两种单一优化算法 表5SGA、CPSO和CPSO-SGA的仿真结果 Table 5 Simulation results of SGA,CPSO and CPSO-SGA 参考文献 算法 路径长度角度变化和/rad规划时间/s SGA 60.933 1.680 0.086 [1]He J,Tu Z Y,Niu Y G.A method of mobile robotic path CPSO 59.207 1.447 1.122 planning based on integrating of GA and ACO.Comput CPSO-SGA 58.735 1.295 0.782 Smul,2010.27(3):170 从表5中看到：两种单一算法和本文所提切换 (何娟，涂中英，牛玉刚。一种遗传蚁群算法的机器人路径 规划方法.计算机仿真，2010,27(3)：170) 优化策略在路径平滑性上相差不多：单一专用遗传 [2]Liu C A,Yan X H,Liu C Y,et al.Dynamic path planning 算法虽然在规划时间上有绝对优势，但其路径较其 for mobile robot based on improved ant colony optimiza- 他两种规划方法相对较长：单一混沌粒子群算法虽 tion algorithm.Acta Electron Sin,2011,5(5):1220 然在路径长度和平滑性上较本文所提切换优化策略 (柳长安，鄂小虎，刘春阳，等.基于改进蚊群算法的移动机 相差不大，但其时间消耗却是切换策略的1.5倍.可 器人动态路径规划方法.电子学报，2011,5(5)：1220)
第 6 期 张 超等：基于混沌粒子群--专用遗传算法切换策略的移动机器人路径规划 829 ·· 表 4 三种切换指标下的仿真结果 Table 4 Simulation results under three switching conditions 切换指标 切换条件 路径长度, L 角度变化和, S/rad 规划时间, T/s 迭代代数 700 59.284 2.300 0.640 种群标准差 误差限 0.01；连续 40 代 59.044 2.567 0.527 最优个体适应度差 误差限 0.005；连续 30 代 58.735 1.295 0.782 综合考虑表 4 中的各项指标后，本文将连续 30 代最优个体适应度差小于 0.005 作为本仿真环境下 的最佳切换条件. 切换策略在三种切换指标各自最 佳切换条件下 10 次运行中的最优路径如图 2 所示. 图 2 三种切换指标在各自最优切换条件下的最优路径 Fig.2 Optimum paths under the best switching conditions of three switching indices 2.2 混沌粒子群--专用遗传算法切换策略同单一 算法对比 将本文所提切换策略同文献 [11] 中的单一专用 遗传算法及混沌粒子群算法进行仿真对比，其中本 文切换策略的切换条件为连续 30 代最优个体适应 度差小于 0.005，进行 10 次仿真程序得到的平均结 果如表 5 所示. 表 5 SGA、CPSO 和 CPSO-SGA 的仿真结果 Table 5 Simulation results of SGA, CPSO and CPSO-SGA 算法 路径长度 角度变化和/rad 规划时间/s SGA 60.933 1.680 0.086 CPSO 59.207 1.447 1.122 CPSO-SGA 58.735 1.295 0.782 从表 5 中看到：两种单一算法和本文所提切换 优化策略在路径平滑性上相差不多；单一专用遗传 算法虽然在规划时间上有绝对优势，但其路径较其 他两种规划方法相对较长；单一混沌粒子群算法虽 然在路径长度和平滑性上较本文所提切换优化策略 相差不大，但其时间消耗却是切换策略的 1.5 倍. 可 见，本文所提切换策略在综合性能上较单一算法具 有一定的优越性. SGA、CPSO 和 CPSO-SGA 在 10 次运行中的最优路径如图 3 所示. 图 3 SGA、CPSO 和 CPSO-SGA 的最优路径 Fig.3 Optimum paths of SGA, CPSO and CPSO-SGA 3 结论 (1) 提出了一种用于机器人路径规划的混沌粒 子群–专用遗传算法相切换的优化策略，并探讨了 三种不同的切换指标. (2) 将所提切换优化策略与单一专用遗传算法 及单一混沌粒子群算法进行了简单静态障碍物环境 下的仿真对比研究，仿真结果表明本文所提切换优 化策略在路径长度、平滑性和规划时间三方面上的 综合表现要优于两种单一优化算法. 参 考 文 献 [1] He J, Tu Z Y, Niu Y G. A method of mobile robotic path planning based on integrating of GA and ACO. Comput Simul, 2010, 27(3): 170 (何娟, 涂中英, 牛玉刚. 一种遗传蚁群算法的机器人路径 规划方法. 计算机仿真, 2010, 27(3): 170) [2] Liu C A, Yan X H, Liu C Y, et al. Dynamic path planning for mobile robot based on improved ant colony optimization algorithm. Acta Electron Sin, 2011, 5(5): 1220 (柳长安, 鄢小虎, 刘春阳, 等. 基于改进蚁群算法的移动机 器人动态路径规划方法. 电子学报, 2011, 5(5): 1220)
.830 北京科技大学学报 第35卷 (3]Wang Z M,Yue H,Liu J Y.Path planning for mobile (孙波，陈卫东，席裕庚.基于粒子群优化算法的移动机器人 robot based on modified simulated annealing algorithm 全局路径规划.控制与决策，2005,20(9)：1052) Comput Eng Appl,2005,41(19):59 [8 Li Q,Xu Y M,Zhang DZ,et al.Global path planning (任仲民，岳宏，柳继岩.。基于改进模拟退火算法的移动机 method for mobile robots based on the particle swarm al- 器人路径规划.计算机工程与应用，2005,41(19)：59) gorithm.J Univ Sci Technol Beijing,2010,32(3):397 (4]Liang Y M,Xu L H.Mobile robot global path plan- (李擎，徐银梅，张德政，等.基于粒子群算法的移动机器人 ning based modified simulated annealing hybrid algo- 全局路径规划策略.北京科技大学学报，2010,32(3)：397) rithm.Control Decis,2010,25(2):237 [9]Tao X M,Xu J,Yang L B,et al.Particle-swarm algo- (梁毓明，徐立鸿.基于改进模拟退火混合算法的移动机器 rithm coordinating the exploration and the exploitation 人全局路径规划.控制与决策，2010.25(2)：237) Control Theory Appl,2010,27(5):636 (5]Liu L,Wang Y N,Kuang F,et al.Path planning of mo- (陶新民，徐品，杨立标，等.一种协调勘探和开采能力的粒 bile robot based on neural network and genetic algorithm. 子群算法.控制理论与应用，2010,27（⑤5）：636) Appl Res Comput,2007,24(2):264 [10 Clerc M.The swarm end queen:towards a deterministic (刘玲，王耀南，况菲，等.基于神经网络和遗传算法的移动 end adaptive particle optimization /Proceedings of the 机器人路径规划.计算机应用研究，2007,24(2)：264) IEEE Congress on Evolutionary Computation.Trond- [6]Feng Q,Zhou DY.Path planning method using genetic al- heim,1999:1951 gorithm under polar coordinates.Mech Sci Technol,2004, [11]Li Q,Zhang C,Xu Y M,et al.Path Planning of mo- 23(5):625 bile robots based on specialized genetic algorithm and im- (冯琦，周德云.极坐标系下基于遗传算法的路径规划方法. proved particle swarm optimization /Proceedings of the 机械科学与技术，2004,23(5：625) Chinese Control Conference.Hefei,2012:7204 [7]Sun B,Chen W D,Xi Y G.Particle swarm optimization (李擎，张超，徐银梅，等。基于专用遗传算法和改进粒子 based global path planning for mobile robots.Control De- 群算法的移动机器人路径规划//中因控制会议论文集.合 cis,2005,20(9):1052 肥，2012：7204)
· 830 · 北 京 科 技 大 学 学 报 第 35 卷 [3] Wang Z M, Yue H, Liu J Y. Path planning for mobile robot based on modified simulated annealing algorithm. Comput Eng Appl, 2005, 41(19): 59 (王仲民, 岳宏, 柳继岩. 基于改进模拟退火算法的移动机 器人路径规划. 计算机工程与应用, 2005, 41(19): 59) [4] Liang Y M, Xu L H. Mobile robot global path planning based modified simulated annealing hybrid algorithm. Control Decis, 2010, 25(2): 237 (梁毓明, 徐立鸿. 基于改进模拟退火混合算法的移动机器 人全局路径规划. 控制与决策, 2010, 25(2): 237) [5] Liu L, Wang Y N, Kuang F, et al. Path planning of mobile robot based on neural network and genetic algorithm. Appl Res Comput, 2007, 24(2): 264 (刘玲, 王耀南, 况菲, 等. 基于神经网络和遗传算法的移动 机器人路径规划. 计算机应用研究, 2007, 24(2): 264) [6] Feng Q, Zhou D Y. Path planning method using genetic algorithm under polar coordinates. Mech Sci Technol, 2004, 23(5): 625 (冯琦, 周德云. 极坐标系下基于遗传算法的路径规划方法. 机械科学与技术, 2004, 23(5): 625) [7] Sun B, Chen W D, Xi Y G. Particle swarm optimization based global path planning for mobile robots. Control Decis, 2005, 20(9): 1052 (孙波, 陈卫东, 席裕庚. 基于粒子群优化算法的移动机器人 全局路径规划. 控制与决策, 2005, 20(9): 1052) [8] Li Q, Xu Y M, Zhang D Z, et al. Global path planning method for mobile robots based on the particle swarm algorithm. J Univ Sci Technol Beijing, 2010, 32(3): 397 (李擎, 徐银梅, 张德政, 等. 基于粒子群算法的移动机器人 全局路径规划策略. 北京科技大学学报, 2010, 32(3): 397) [9] Tao X M, Xu J, Yang L B, et al. Particle-swarm algorithm coordinating the exploration and the exploitation. Control Theory Appl, 2010, 27(5): 636 (陶新民, 徐晶, 杨立标, 等. 一种协调勘探和开采能力的粒 子群算法. 控制理论与应用, 2010, 27(5): 636) [10] Clerc M. The swarm end queen: towards a deterministic end adaptive particle optimization // Proceedings of the IEEE Congress on Evolutionary Computation. Trondheim, 1999: 1951 [11] Li Q, Zhang C, Xu Y M, et al. Path Planning of mobile robots based on specialized genetic algorithm and improved particle swarm optimization // Proceedings of the Chinese Control Conference. Hefei, 2012: 7204 (李擎, 张超, 徐银梅, 等. 基于专用遗传算法和改进粒子 群算法的移动机器人路径规划//中国控制会议论文集. 合 肥, 2012: 7204)