第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] 提出 了在粒子群算法速度更新公式中引入压缩子 (con￾striction 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 Vi￾sual Studio 2002. 2.1 切换优化策略不同切换指标仿真研究 切换策略中的两种算法分别采用文献 [11] 中的 混沌粒子群算法和专用遗传算法，其中混沌粒子群 算法的惯性权重 w 取为 0.5，加速度系数 c1 和 c2 都设为 2，最大速度 Vmax 等于 2，选用 Chebyshev 序列作为混沌模型. 这里将切换策略的种群规模 N