【智能系统】基于改进粒子群算法的移动机器人多目标点路径规划

第12卷第3期 智能系统学报 Vol.12 No.3 2017年6月 CAAI Transactions on Intelligent Systems Jun.2017 D0I:10.11992/tis.201606046 网络出版地址：http:/kns.cmki.ne/kcms/detail/23.1538.TP.20170404.1218.004.html 基于改进粒子群算法的移动机器人多目标点路径规划 蒲兴成，李俊杰2，吴慧超2，张毅 (1.重庆邮电大学数理学院，重庆400065：2.重庆邮电大学智能系统及机器人研究所，重庆400065：3.重庆邮电大学 先进制造学院，重庆400065) 摘要：针对移动机器人遍历多个目标点的路径规划问题，提出了一种基于改进粒子群算法和蚁群算法相结合的路 径规划新方法。该方法将目标点的选择转化为旅行商问题，并利用蚁群算法进行优化，定义了每两个目标点之间的 路径规划目标函数，利用粒子群算法对其进行优化。针对粒子群算法存在的早熟现象，将反向学习策略引入粒子群 算法，并对粒子群算法的惯性权重和学习因子进行改进。性能测试结果表明，改进的粒子群算法能有效避免粒子早 熟现象，提高粒子群算法的寻优能力及稳定性。仿真实验结果验证了新方法能有效地实现机器人的多目标点无碰 撞路径规划。真实环境下的实验结果证明了新方法在机器人多目标点路径规划的实际应用中也具有有效性。 关键词：移动机器人；多目标点路径规划：蚁群算法；改进粒子群算法；反向学习策略；惯性权重：学习因子 中图分类号：TP242.6文献标志码：A文章编号：1673-4785(2017)03-0301-09 中文引用格式：蒲兴成，李俊杰，吴慧超，等.基于改进粒子群算法的移动机器人多目标点路径规划[J].智能系统学报，2017,12 (3):301-309. 英文引用格式：PU Xingcheng,LI Junjie,WU Huichao,ctal.Mobile robot multi-goal path planning using improved particle swarm optimization[J].CAAI transactions on intelligent systems,2017,12(3):301-309. Mobile robot multi-goal path planning using improved particle swarm optimization PU Xingcheng',LI Junjie2,WU Huichao2,ZHANG Yi3 (1.School of Science,Chongqing University of Posts and Telecommunications,Chongqing 400065,China;2.Research Center of Intelligent System and Robot,Chongqing University of Posts and Telecommunications,Chongqing 400065,China;3.Advanced Manufacturing Engineering School,Chongqing University of Posts and Telecommunications,Chongqing 400065,China) Abstract:To solve the problem of multi-goal path planning for mobile robots that pass multiple goals,a new path planning method,based on improved particle swarm optimization (PSO)and ant colony optimization (ACO),is proposed.In this new method,the first step is to use an improved PSO,which has high convergence,to optimize the path between two goals among a sequence of goals.The second step is to use the ACO to obtain the shortest path for all target points.The performance experimental result demonstrates that the improved PSO algorithm can effectively avoid premature convergence and enhances search ability and stability.Simulation results show that the improved PSO algorithm can make a mobile robot realize collision-free multi-goal path planning effectively Experiments in a real environment demonstrate that this algorithm has practical application for multi-goal path planning. Keywords:mobile robot;multi-goal path planning;ACO;improved PSO;opposition-based learning;inertia weight;learning factors 路径规划是研究移动机器人的一个重要内容，按其规划范围，分为全局路径规划和局部路径规 划。目前，针对这两种路径规划方式许多学者进行 收稿日期：2016-06-30.网络出版日期：2017-04-04. 基金项目：国家自然科学基金(51604056)，重庆市科学技术委员会项目 了深人研究，并提出了相应的解决方法。全局路径 (cstc2015 jcyBx(0066):重庆市数委项目(K1400432). 通信作者：李俊杰.E-mail:lijunjiel66@126.com. 规划方法有栅格法、可视图法和神经网络法等：局

第 １２ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１２ №．３ ２０１７ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１７ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０６０４６ 网络出版地址：ｈｔｔｐ： ／ ／ ｋｎｓ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１７０４０４．１２１８．００４．ｈｔｍｌ 基于改进粒子群算法的移动机器人多目标点路径规划 蒲兴成１ ，李俊杰２ ，吴慧超２ ，张毅３ （１．重庆邮电大学 数理学院，重庆 ４０００６５；２．重庆邮电大学 智能系统及机器人研究所，重庆 ４０００６５；３．重庆邮电大学 先进制造学院，重庆 ４０００６５） 摘 要：针对移动机器人遍历多个目标点的路径规划问题，提出了一种基于改进粒子群算法和蚁群算法相结合的路 径规划新方法。 该方法将目标点的选择转化为旅行商问题，并利用蚁群算法进行优化，定义了每两个目标点之间的 路径规划目标函数，利用粒子群算法对其进行优化。 针对粒子群算法存在的早熟现象，将反向学习策略引入粒子群 算法，并对粒子群算法的惯性权重和学习因子进行改进。 性能测试结果表明，改进的粒子群算法能有效避免粒子早 熟现象，提高粒子群算法的寻优能力及稳定性。 仿真实验结果验证了新方法能有效地实现机器人的多目标点无碰 撞路径规划。 真实环境下的实验结果证明了新方法在机器人多目标点路径规划的实际应用中也具有有效性。 关键词：移动机器人；多目标点路径规划；蚁群算法；改进粒子群算法；反向学习策略；惯性权重；学习因子 中图分类号：ＴＰ２４２．６ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１７）０３－０３０１－０９ 中文引用格式：蒲兴成，李俊杰，吴慧超，等．基于改进粒子群算法的移动机器人多目标点路径规划［ Ｊ］． 智能系统学报， ２０１７， １２ （３）： ３０１－３０９． 英文引用格式：ＰＵ Ｘｉｎｇｃｈｅｎｇ， ＬＩ Ｊｕｎｊｉｅ， ＷＵ Ｈｕｉｃｈａｏ， ｅｔ ａｌ． Ｍｏｂｉｌｅ ｒｏｂｏｔ ｍｕｌｔｉ⁃ｇｏａｌ ｐａｔｈ ｐｌａｎｎｉｎｇ ｕｓｉｎｇ ｉｍｐｒｏｖｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１７， １２（３）： ３０１－３０９． Ｍｏｂｉｌｅ ｒｏｂｏｔ ｍｕｌｔｉ⁃ｇｏａｌ ｐａｔｈ ｐｌａｎｎｉｎｇ ｕｓｉｎｇ ｉｍｐｒｏｖｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ＰＵ Ｘｉｎｇｃｈｅｎｇ １ ， ＬＩ Ｊｕｎｊｉｅ ２ ， ＷＵ Ｈｕｉｃｈａｏ ２ ， ＺＨＡＮＧ Ｙｉ ３ （１． Ｓｃｈｏｏｌ ｏｆ Ｓｃｉｅｎｃｅ， Ｃｈｏｎｇｑｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｐｏｓｔｓ ａｎｄ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｃｈｏｎｇｑｉｎｇ ４０００６５， Ｃｈｉｎａ； ２． Ｒｅｓｅａｒｃｈ Ｃｅｎｔｅｒ ｏｆ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍ ａｎｄ Ｒｏｂｏｔ， Ｃｈｏｎｇｑｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｐｏｓｔｓ ａｎｄ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｃｈｏｎｇｑｉｎｇ ４０００６５， Ｃｈｉｎａ； ３． Ａｄｖａｎｃｅｄ Ｍａｎｕｆａｃｔｕｒｉｎｇ Ｅｎｇｉｎｅｅｒｉｎｇ Ｓｃｈｏｏｌ， Ｃｈｏｎｇｑｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｐｏｓｔｓ ａｎｄ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｃｈｏｎｇｑｉｎｇ ４０００６５， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｏ ｓｏｌｖｅ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｍｕｌｔｉ－ｇｏａｌ ｐａｔｈ ｐｌａｎｎｉｎｇ ｆｏｒ ｍｏｂｉｌｅ ｒｏｂｏｔｓ ｔｈａｔ ｐａｓｓ ｍｕｌｔｉｐｌｅ ｇｏａｌｓ， ａ ｎｅｗ ｐａｔｈ ｐｌａｎｎｉｎｇ ｍｅｔｈｏｄ， ｂａｓｅｄ ｏｎ ｉｍｐｒｏｖｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ （ＰＳＯ） ａｎｄ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ （ＡＣＯ）， ｉｓ ｐｒｏｐｏｓｅｄ． Ｉｎ ｔｈｉｓ ｎｅｗ ｍｅｔｈｏｄ， ｔｈｅ ｆｉｒｓｔ ｓｔｅｐ ｉｓ ｔｏ ｕｓｅ ａｎ ｉｍｐｒｏｖｅｄ ＰＳＯ， ｗｈｉｃｈ ｈａｓ ｈｉｇｈ ｃｏｎｖｅｒｇｅｎｃｅ， ｔｏ ｏｐｔｉｍｉｚｅ ｔｈｅ ｐａｔｈ ｂｅｔｗｅｅｎ ｔｗｏ ｇｏａｌｓ ａｍｏｎｇ ａ ｓｅｑｕｅｎｃｅ ｏｆ ｇｏａｌｓ． Ｔｈｅ ｓｅｃｏｎｄ ｓｔｅｐ ｉｓ ｔｏ ｕｓｅ ｔｈｅ ＡＣＯ ｔｏ ｏｂｔａｉｎ ｔｈｅ ｓｈｏｒｔｅｓｔ ｐａｔｈ ｆｏｒ ａｌｌ ｔａｒｇｅｔ ｐｏｉｎｔｓ． Ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔ ｄｅｍｏｎｓｔｒａｔｅｓ ｔｈａｔ ｔｈｅ ｉｍｐｒｏｖｅｄ ＰＳＯ ａｌｇｏｒｉｔｈｍ ｃａｎ ｅｆｆｅｃｔｉｖｅｌｙ ａｖｏｉｄ ｐｒｅｍａｔｕｒｅ ｃｏｎｖｅｒｇｅｎｃｅ ａｎｄ ｅｎｈａｎｃｅｓ ｓｅａｒｃｈ ａｂｉｌｉｔｙ ａｎｄ ｓｔａｂｉｌｉｔｙ． Ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｉｍｐｒｏｖｅｄ ＰＳＯ ａｌｇｏｒｉｔｈｍ ｃａｎ ｍａｋｅ ａ ｍｏｂｉｌｅ ｒｏｂｏｔ ｒｅａｌｉｚｅ ｃｏｌｌｉｓｉｏｎ⁃ｆｒｅｅ ｍｕｌｔｉ⁃ｇｏａｌ ｐａｔｈ ｐｌａｎｎｉｎｇ ｅｆｆｅｃｔｉｖｅｌｙ ． Ｅｘｐｅｒｉｍｅｎｔｓ ｉｎ ａ ｒｅａｌ ｅｎｖｉｒｏｎｍｅｎｔ ｄｅｍｏｎｓｔｒａｔｅ ｔｈａｔ ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｈａｓ ｐｒａｃｔｉｃａｌ ａｐｐｌｉｃａｔｉｏｎ ｆｏｒ ｍｕｌｔｉ⁃ｇｏａｌ ｐａｔｈ ｐｌａｎｎｉｎｇ． Ｋｅｙｗｏｒｄｓ： ｍｏｂｉｌｅ ｒｏｂｏｔ； ｍｕｌｔｉ⁃ｇｏａｌ ｐａｔｈ ｐｌａｎｎｉｎｇ； ＡＣＯ； ｉｍｐｒｏｖｅｄ ＰＳＯ； ｏｐｐｏｓｉｔｉｏｎ⁃ｂａｓｅｄ ｌｅａｒｎｉｎｇ； ｉｎｅｒｔｉａ ｗｅｉｇｈｔ； ｌｅａｒｎｉｎｇ ｆａｃｔｏｒｓ 收稿日期：２０１６－０６－３０． 网络出版日期：２０１７－０４－０４． 基金项目：国家自然科学基金（５１６０４０５６），重庆市科学技术委员会项目 （ｃｓｔｃ２０１５ｊｃｙＢｘ００６６）；重庆市教委项目（ＫＪ１４００４３２）． 通信作者：李俊杰． Ｅ⁃ｍａｉｌ：ｌｉｊｕｎｊｉｅ１６６＠ １２６．ｃｏｍ． 路径规划是研究移动机器人的一个重要内容， 按其规划范围，分为全局路径规划和局部路径规 划。 目前，针对这两种路径规划方式许多学者进行 了深入研究，并提出了相应的解决方法。 全局路径 规划方法有栅格法、可视图法和神经网络法等；局

·302 智能系统学报 第12卷 部路径规划方法包括人工势场法、A·算法、人工蜂 了避免PS0出现早熟现象，提高算法的效率，提出 群算法等)。虽然这些算法得到广泛应用，但也存 了具有快速收敛性的粒子群算法。实验结果验证 在一些缺点：栅格力度越小，栅格法对障碍物的描 了混合算法的有效性以及改进的粒子群算法的优 述越精确，但环境信息的存储会占据大量的存储空 越性。 间，算法的搜索范围也将成指数增加)：人工势场 1问题描述 法由于斥力的作用，机器人很难准确到达目标点。 A·算法对开放列表的维护是最耗时的，尤其是在地 1.1多目标点路径规划 图过大的情况下。 假设在移动机器人多目标点路径规划中含有n 移动机器人多目标点路径规划是指在复杂的 个目标点，则移动机器人会产生n(n-1)/2条路径。 环境下找到一条从起始点开始经过所有目标点的 为了满足移动机器人行走路径最短的要求，机器人 无碰撞的最优路径。在实际应用中，移动机器人多 需要从n(n-1)/2条路线中选择出一条经过所有点 目标点路径规划多应用于电厂巡检、医院查房等。 的最短路径。图1描述了在起始点和目标点位置已 移动机器人多目标点路径规划的基本原则包括3个 知的情况下，移动机器人的运动轨迹。从图1(a)中 方面：1)当前点或起始点以及目标点提前已知；2) 可知移动机器人的移动路线有很多条，且必须经过 任意时刻机器人都可以决定移动路线：3)机器人必 所有目标点才能完成路径规划：图1(b)表示移动机 须经过的所有目标点来完成路径规划。根据移动 器人运动的理想路线。 机器人多目标点路径规划的特点，移动机器人多目 15 标点路径规划问题可以转化为旅行商(traveling saleman problem,TSP)问题。目前有很多算法用于 10 解决TSP问题)，但多目标点路径规划与TSP问题 相比更复杂。因此本文提出了一种基于粒子群算 法和蚁群算法相结合的混合算法用于解决移动机 器人多目标点路径规划问题。 81 蚁群算法(ant colony optimization,ACO)是一种 10 20 启发式进化算法，由蚂蚁觅食行为演化而来。在解 (a)所有路径 决TSP问题上，蚁群算法表现出了较强的优越性。 粒子群算法(particle swarm optimization,PSO)是 15 种群体智能算法，由鸟群觅食行为演化而来。与 ~般的群体智能算法相比，PS0具有记忆特性，可 10 以通过自我学习和向他人学习方式获得更多的信 息。由于参数少，计算方便等优点，PS0广泛应用 在优化问题上，并取得了很好的效果。随着移动机 器人技术的发展，国内外学者对粒子群算法在移动 机器人路径规划上做了大量的研究，如多机器人路 10 15 20 径规划s6,自由浮动机器人轨迹规划)以及其他 (b)理想路径 应用领域[8-。PS0在路径规划上应用广泛，ACO 图1多点之间的路径轨迹 善于解决TSP问题，因此采用两者结合的方式非常 Fig.1 The path trajectory of multi-goal 适合移动机器人多目标点路径规划问题。 为了解决上述问题，我们将目标点的选择规划 在一个包含障碍物的空间内，利用PS0算法对 为TSP问题的一个分支。目前，求解TSP问题最有 起始点到目标点及每个目标点与目标点之间进行 效的方法主要有郭涛算法、模拟退火算法、遗传算 路径规划。起始点、目标点以及障碍物位置已知， 法、蚁群算法等)。由于这些算法都有优缺点，因 但是哪一条路线会被选择是未知的。为了确定哪 此有些学者尝试结合两种或多种算法解决彼此算 一条路径会被选择，AC0被用于遍历起始点和所有 法上的缺点[]。蚁群算法作为一种自组织正反馈 目标点，以便得到一条经过所有点的最短路径。为 算法，与其他算法相比，具有很强的鲁棒性。而且

部路径规划方法包括人工势场法、Ａ ∗ 算法、人工蜂 群算法等［１］ 。 虽然这些算法得到广泛应用，但也存 在一些缺点：栅格力度越小，栅格法对障碍物的描 述越精确，但环境信息的存储会占据大量的存储空 间，算法的搜索范围也将成指数增加［２］ ；人工势场 法由于斥力的作用，机器人很难准确到达目标点。 Ａ ∗算法对开放列表的维护是最耗时的，尤其是在地 图过大的情况下。 移动机器人多目标点路径规划是指在复杂的 环境下找到一条从起始点开始经过所有目标点的 无碰撞的最优路径。 在实际应用中，移动机器人多 目标点路径规划多应用于电厂巡检、医院查房等。 移动机器人多目标点路径规划的基本原则包括 ３ 个 方面：１）当前点或起始点以及目标点提前已知；２） 任意时刻机器人都可以决定移动路线；３）机器人必 须经过的所有目标点来完成路径规划。 根据移动 机器人多目标点路径规划的特点，移动机器人多目 标点路径规划问题可以转化为旅行商 （ ｔｒａｖｅｌｉｎｇ ｓａｌｅｍａｎ ｐｒｏｂｌｅｍ， ＴＳＰ）问题。 目前有很多算法用于 解决 ＴＳＰ 问题［３］ ，但多目标点路径规划与 ＴＳＰ 问题 相比更复杂。 因此本文提出了一种基于粒子群算 法和蚁群算法相结合的混合算法用于解决移动机 器人多目标点路径规划问题。 蚁群算法（ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ， ＡＣＯ）是一种 启发式进化算法，由蚂蚁觅食行为演化而来。 在解 决 ＴＳＰ 问题上，蚁群算法表现出了较强的优越性。 粒子群算法（ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ， ＰＳＯ）是一 种群体智能算法，由鸟群觅食行为演化而来［４］ 。 与 一般的群体智能算法相比，ＰＳＯ 具有记忆特性，可 以通过自我学习和向他人学习方式获得更多的信 息。 由于参数少，计算方便等优点，ＰＳＯ 广泛应用 在优化问题上，并取得了很好的效果。 随着移动机 器人技术的发展，国内外学者对粒子群算法在移动 机器人路径规划上做了大量的研究，如多机器人路 径规划［５－６］ ，自由浮动机器人轨迹规划［７］ 以及其他 应用领域［８－９］ 。 ＰＳＯ 在路径规划上应用广泛，ＡＣＯ 善于解决 ＴＳＰ 问题，因此采用两者结合的方式非常 适合移动机器人多目标点路径规划问题。 在一个包含障碍物的空间内，利用 ＰＳＯ 算法对 起始点到目标点及每个目标点与目标点之间进行 路径规划。 起始点、目标点以及障碍物位置已知， 但是哪一条路线会被选择是未知的。 为了确定哪 一条路径会被选择，ＡＣＯ 被用于遍历起始点和所有 目标点，以便得到一条经过所有点的最短路径。 为 了避免 ＰＳＯ 出现早熟现象，提高算法的效率，提出 了具有快速收敛性的粒子群算法。 实验结果验证 了混合算法的有效性以及改进的粒子群算法的优 越性。 １ 问题描述 １．１ 多目标点路径规划 假设在移动机器人多目标点路径规划中含有 ｎ 个目标点，则移动机器人会产生 ｎ（ｎ－１） ／ ２ 条路径。 为了满足移动机器人行走路径最短的要求，机器人 需要从 ｎ（ｎ－１） ／ ２ 条路线中选择出一条经过所有点 的最短路径。 图 １ 描述了在起始点和目标点位置已 知的情况下，移动机器人的运动轨迹。 从图 １（ａ）中 可知移动机器人的移动路线有很多条，且必须经过 所有目标点才能完成路径规划；图 １（ｂ）表示移动机 器人运动的理想路线。 （ａ）所有路径 （ｂ）理想路径 图 １ 多点之间的路径轨迹 Ｆｉｇ．１ Ｔｈｅ ｐａｔｈ ｔｒａｊｅｃｔｏｒｙ ｏｆ ｍｕｌｔｉ⁃ｇｏａｌ 为了解决上述问题，我们将目标点的选择规划 为 ＴＳＰ 问题的一个分支。 目前，求解 ＴＳＰ 问题最有 效的方法主要有郭涛算法、模拟退火算法、遗传算 法、蚁群算法等［３］ 。 由于这些算法都有优缺点，因 此有些学者尝试结合两种或多种算法解决彼此算 法上的缺点［１０］ 。 蚁群算法作为一种自组织正反馈 算法，与其他算法相比，具有很强的鲁棒性。 而且 ·３０２· 智 能 系 统 学 报 第 １２ 卷

第3期 蒲兴成，等：基于改进粒子群算法的移动机器人多目标点路径规划 ·303. 从本质上讲，蚁群算法的并行特性，强化了算法的 F= 可靠性。因此在解决多目标点选择的问题上，我们 将采用蚁群算法搜索能够遍历所有目标点的方法。 √x四-x)2+0-)下] 1.2粒子的适应度函数 式中，g是目标点的个数，S是粒子个数。 粒子的适应度函数是检验粒子群算法收敛性 移动机器人在向目标点移动过程中，除了要保 的重要函数。在路径规划中，移动距离最短是机器 证其最短性，安全性也是必须要考虑的。为此，将 人首要考虑的目标，其次是安全性。因此，将移动 障碍物对目标点的斥力场函数作为安全性的惩罚 机器人运动距离作为粒子的首要适应度函数。移 函数。斥力场函数定义如下： 动机器人多目标点路径规划如图2所示。由图2可 1)2 d(xgxc),d(xgxo)d 知，移动机器人从起始位置开始避开障碍物，经过 d(xg,o)d 一系列目标点到达目标点n。 0 d(xR,xo)>d 式中：F2是障碍物对机器人的斥力：k,是斥力场系 日标点2 数；d(xR,xo)为机器人到障碍物的距离；d(xR,xc) 目标点1Q 是机器人到目标点的距离：d是障碍物的影响 障碍物 目标点n 范围。 移动机器人多目标点路径规划问题可以抽象 起始点 为当前位置到目标点的最短距离的优化问题，而障 碍物对机器人的斥力作用是保证最短路径安全性 图2移动机器人多目标点路径规划示意图 的前提。因此，针对路径规划的目标函数可以定 Fig.2 The diagram of mobile robot multi-goal path planning 义为 为了便于理解移动机器人多目标点路径规划， F=AF +uF, 可将图2中的多目标点路径规划分解为多个目标点 式中入和μ分别是最短路路径和约束条件的权重。 中的两两目标点之间路径规划。机器人在保证两 2 基本知识 点之间路径规划最短的基础上才能保证多目标路 径规划最短。分解后如图3所示，机器人在当前点 2.1标准粒子群算法 需要选择下一个所经过点，然后到达目标点，在此 在PS0算法中，每个粒子通过自我学习及向 期间要避开障碍物。 “他人”学习向问题空间中的最佳位置移动，进而找 到最优解。V维空间内粒子的位置变量为x:= p目标点 (x1,x2,…,xn）,=(,2,…,)为粒子的速度 下一个 变量。粒子迭代时，通过向两个“极值”学习来更新 经过点 自己：l)局部最优值pe;2)全局最优值gm。PS0 障碍物 充分利用局部最优值和全局最优值，可使优秀粒子 6 的基因得到传承。粒子寻优的过程是粒子根据自 当前点 我学习和向他人学习来更新自己的速度和位置，逐 步获得最优解。粒子的速度和位置更新公式为 图3当前点到目标点避障描述 yt1=wv+c1,(pt-x)+c22(gm-)(1) Fig.3 The obstacle avoidance description of current x1=x+时 (2) point to goal 式中：w是粒子的惯性权重：C1c2是学习因子；r1'2 综上所述，为了保证路径规划的最短性，下一 是[0,1]的随机数；x表示粒子t的位置且x∈ 个移动点的选取是保证移动机器人运动轨迹最短 [rin,r];速度∈[vmn,vr]。当粒子的位置超 的前提。因此，设立移动机器人路径规划目标函数 出了[xm,xm]时，粒子被限制为xn或xr;若粒 F,F,决定了移动机器人行走路径长度。本文中， 子的速度超出了y时，粒子的速度被限制为最大 F,定义为 速度vmso

从本质上讲，蚁群算法的并行特性，强化了算法的 可靠性。 因此在解决多目标点选择的问题上，我们 将采用蚁群算法搜索能够遍历所有目标点的方法。 １．２ 粒子的适应度函数 粒子的适应度函数是检验粒子群算法收敛性 的重要函数。 在路径规划中，移动距离最短是机器 人首要考虑的目标，其次是安全性。 因此，将移动 机器人运动距离作为粒子的首要适应度函数。 移 动机器人多目标点路径规划如图 ２ 所示。 由图 ２ 可 知，移动机器人从起始位置开始避开障碍物，经过 一系列目标点到达目标点 ｎ。 图 ２ 移动机器人多目标点路径规划示意图 Ｆｉｇ．２ Ｔｈｅ ｄｉａｇｒａｍ ｏｆ ｍｏｂｉｌｅ ｒｏｂｏｔ ｍｕｌｔｉ⁃ｇｏａｌ ｐａｔｈ ｐｌａｎｎｉｎｇ 为了便于理解移动机器人多目标点路径规划， 可将图 ２ 中的多目标点路径规划分解为多个目标点 中的两两目标点之间路径规划。 机器人在保证两 点之间路径规划最短的基础上才能保证多目标路 径规划最短。 分解后如图 ３ 所示，机器人在当前点 需要选择下一个所经过点，然后到达目标点，在此 期间要避开障碍物。 图 ３ 当前点到目标点避障描述 Ｆｉｇ．３ Ｔｈｅ ｏｂｓｔａｃｌｅ ａｖｏｉｄａｎｃｅ ｄｅｓｃｒｉｐｔｉｏｎ ｏｆ ｃｕｒｒｅｎｔ ｐｏｉｎｔ ｔｏ ｇｏａｌ 综上所述，为了保证路径规划的最短性，下一 个移动点的选取是保证移动机器人运动轨迹最短 的前提。 因此，设立移动机器人路径规划目标函数 Ｆ１ ，Ｆ１ 决定了移动机器人行走路径长度。 本文中， Ｆ１ 定义为 Ｆ１ ＝ ∑ ｇ ｊ ＝ １ ∑ Ｓ ｉ ＝ １ ｘ ｃｕｒｒｅｎｔ ｉ，ｊ － ｘ ｎｅｘｔ ｉ，ｊ ( ) ２ ＋ ｙ ｃｕｒｒｅｎｔ ｉ，ｊ － ｙ ｎｅｘｔ ｉ，ｊ ( ) ２ [ ＋ ｘ ｎｅｘｔ ｉ，ｊ － ｘ ｇｏａｌ ｉ，ｊ ( ) ２ ＋ ｙ ｎｅｘｔ ｉ，ｊ － ｙ ｇｏａｌ ｉ，ｊ ( ) ２ ] 式中，ｇ 是目标点的个数，Ｓ 是粒子个数。 移动机器人在向目标点移动过程中，除了要保 证其最短性，安全性也是必须要考虑的。 为此，将 障碍物对目标点的斥力场函数作为安全性的惩罚 函数。 斥力场函数定义如下： Ｆ２ ＝ ｋｒ × １ ｄ（ｘＲ，ｘＯ） － １ ｄｍ æ è ç ö ø ÷ ２ ｄ ２ （ｘＲ，ｘＧ）， ｄ（ｘＲ，ｘＯ）≤ｄｍ ０， ｄ（ｘＲ，ｘＯ）＞ｄｍ ì î í ï ï ïï 式中：Ｆ２ 是障碍物对机器人的斥力；ｋｒ 是斥力场系 数；ｄ（ｘＲ ，ｘＯ ）为机器人到障碍物的距离；ｄ（ ｘＲ ，ｘＧ ） 是机器人到目标点的距离； ｄｍ 是障碍物的影响 范围。 移动机器人多目标点路径规划问题可以抽象 为当前位置到目标点的最短距离的优化问题，而障 碍物对机器人的斥力作用是保证最短路径安全性 的前提。 因此，针对路径规划的目标函数可以定 义为 Ｆ ＝ λＦ１ ＋ μＦ２ 式中 λ 和 μ 分别是最短路路径和约束条件的权重。 ２ 基本知识 ２．１ 标准粒子群算法 在 ＰＳＯ 算法中，每个粒子通过自我学习及向 “他人”学习向问题空间中的最佳位置移动，进而找 到最优解。 Ｎ 维空间内粒子的位置变量为 ｘｉ ＝ ｘｉ１ ，ｘｉ２ ，…，ｘｉｎ ( ) ，ｖｉ ＝ ｖｉ１ ，ｖｉ２ ，…，ｖｉｎ ( ) 为粒子的速度 变量。 粒子迭代时，通过向两个“极值”学习来更新 自己：１）局部最优值 ｐｂｅｓｔ；２）全局最优值 ｇｂｅｓｔ。 ＰＳＯ 充分利用局部最优值和全局最优值，可使优秀粒子 的基因得到传承。 粒子寻优的过程是粒子根据自 我学习和向他人学习来更新自己的速度和位置，逐 步获得最优解。 粒子的速度和位置更新公式为 ｖ ｔ＋１ ｉ ＝ ωｖ ｔ ｉ ＋ ｃ１ ｒ１ ｐｂｅｓｔ － ｘ ｔ ｉ ( ) ＋ ｃ２ ｒ２ ｇｂｅｓｔ － ｘ ｔ ｉ ( ) （１） ｘ ｔ＋１ ｉ ＝ ｘ ｔ ｉ ＋ ｖ ｔ ｉ （２） 式中：ω 是粒子的惯性权重；ｃ１ 、ｃ２ 是学习因子；ｒ１ 、ｒ２ 是［０，１］ 的随机数； ｘ ｔ ｉ 表示粒子 ｔ 的位置且 ｘ ｔ ｉ ∈ ｘｍｉｎ ，ｘｍａｘ [ ] ；速度 ｖ ｔ ｉ∈ ｖｍｉｎ ，ｖｍａｘ [ ] 。 当粒子的位置超 出了 ｘｍｉｎ ，ｘｍａｘ [ ] 时，粒子被限制为 ｘｍｉｎ或 ｘｍａｘ；若粒 子的速度超出了 ｖｍａｘ时，粒子的速度被限制为最大 速度 ｖｍａｘ。 第 ３ 期 蒲兴成，等：基于改进粒子群算法的移动机器人多目标点路径规划 ·３０３·

·304. 智能系统学报 第12卷 2.2反向学习策略 远的粒子要快。但是，粒子在问题空间中是随机分 Tizhoosh]在2005年基于相反数或对立点的 布的，每一个粒子相对于最优解的位置都是未知的。 概念提出了反向学习策略。在随后的发展中，该方 基于以上分析，在改进的粒子群算法初始化时 法被应用于解决一些优化问题中[2]。反向坐标 引入反向学习策略有助于粒子寻找最优解。在初 定义如下。 始化时，首先，计算粒子的适应度值以及其反向粒 定义1)假设x在一维空间中的坐标是-5， 子适应度值，并对两者进行比较，选择适应度值较 目标点的坐标为10。那么x反向点x的坐标点为 好的粒子；其次，从种群中选择S个适应度值最好的 5,且点x到目标点的距离为15，点x到目标点的距 粒子作为初始种群。 离为5。比较可得，反向点靠近目标点。x的反向坐 3.2迭代进化过程 标点x的计算公式为 在标准PS0算法中，粒子在问题空间中选择另 x=a+b-x 一个粒子作为学习对象，根据式(1)、(2)进行移动。 式中x∈[a,b],且为实数。把上述定义应用到高维 但在粒子进化的过程中，粒子会发生早熟现象，导 空间可表示成定义2。 致算法无法得到最优解。由式(1)可知，粒子的速 定义2[)在N维空间中的一个点P可表示 度受到惯性权重和学习因子的影响：惯性权重影响 为P(x1,x2,…,xn),其中x1,x2,…,xn∈R,且x:∈ 着粒子的全局搜索和局部搜索能力，学习因子影响 粒子获取信息的能力。为了找到问题最优解，粒子 [a,b],i={1,2,…,n}。则点P对应的反向点P 在进化的过程中，其全局搜索能力和局部搜索能力 可表示为P(元，x2,…,x),其中x表示为 也应该随之发生变化，即从全局搜索渐变为局部搜 x:=a:+b:-x 索，保证粒子可以寻找到问题的最优解。同样，粒 将定义2应用到优化过程中，则反向机制的优 子也应该逐渐增强社交能力，由“自我”学习逐渐向 化过程如定义3。 “他人”学习过渡，以便获取更多有用的信息。 定义34)根据定义1和定义2，反向学习可 根据以上分析，粒子在寻优过程中，惯性权重 以描述为：假设f(x)是已知问题的函数方程，n维空 应该保持动态变化。ω取值较大时，粒子的全局搜 间中的点P(x1,x2,…,xn)是函数方程f(x)的一个 索能力较强：ω取值较小时，粒子的局部搜索能力较 解，且x∈[a:,b],i={1,2,…,n}。则P,的反向 强。由于粒子在寻优的过程中，会逐渐靠近最优 点，粒子的惯性权重应该随着寻优过程自适应变 点为P(元1，x2,…,元n)。计算P:和P:在函数f(x) 化。因此粒子的惯性权重更新公式为 中的函数值。如果f(P)>f(P),则反向点P代替 dist P,;否则保留P,。因此通过不断地计算点P,与反向 ω=0s-(0mx-wmn） max dist 点P,的f(x)值选择其中最优值。 式中：wms和wm分别是粒子惯性权重的最大值和 最小值；dist:是第i个粒子到全局最优粒子的欧几 3 反向学习粒子群算法 里德距离；max_dist是粒子到全局最优粒子的最大 基于反向学习策略的思想，本文提出一种改进 距离。dist,和max_dist表达式分别为[s 的粒子群算法(opposition-based learning improved PSO,OBLIPS0)。本文采用反向学习策略时，将反 dist=(∑8u-a)月 d=1 向学习策略应用到单个粒子中，而不是粒子群体 max_dist argmax(dist,) 中，以便减小粒子迭代过程中的计算量。性能测试 学习因子c,和c2控制粒子本身记忆与同伴记 结果证明，改进的粒子群算法能抑制粒子早熟现 忆之间的相对影响：c,的值较小时，表现为自我认 象，提高收敛效率。下面介绍改进算法的主要机制 知能力不足；C2的值较小时，表现为社交能力不足。 和流程。 为了保证在迭代过程中，粒子的自我认知和社交能 3.1初始化种群 力能够因时而异，因此，粒子的学习因子更新公 粒子在问题空间中找到最优解的时间与粒子 式6]如下： 初始化时在空间中的分布存在正比关系，距离最佳 位置近的粒子找到最优解的时间比距离最佳位置

２．２ 反向学习策略 Ｔｉｚｈｏｏｓｈ ［１１］在 ２００５ 年基于相反数或对立点的 概念提出了反向学习策略。 在随后的发展中，该方 法被应用于解决一些优化问题中［１２－１３］ 。 反向坐标 定义如下。 定义 １ ［１４］ 假设 ｘ 在一维空间中的坐标是－５， 目标点的坐标为 １０。 那么 ｘ 反向点 ｘ ～ 的坐标点为 ５，且点 ｘ 到目标点的距离为 １５，点 ｘ ～ 到目标点的距 离为 ５。 比较可得，反向点靠近目标点。 ｘ 的反向坐 标点 ｘ ～ 的计算公式为 ｘ ～ ＝ ａ ＋ ｂ － ｘ 式中 ｘ∈［ａ，ｂ］，且为实数。 把上述定义应用到高维 空间可表示成定义 ２。 定义 ２ ［１４］ 在 Ｎ 维空间中的一个点 Ｐ 可表示 为 Ｐ ｘ１ ，ｘ２ ，…，ｘｎ ( ) ，其中 ｘ１ ，ｘ２ ，…，ｘｎ ∈Ｒ，且 ｘｉ ∈ ａｉ，ｂｉ [ ] ，∀ｉ ＝{１，２，…，ｎ} 。 则点 Ｐ 对应的反向点 Ｐ ～ 可表示为 Ｐ ～ （ｘ ～ １ ，ｘ ～ ２ ，…，ｘ ～ ｎ ），其中ｘｉ ～ 表示为 ｘ ～ ｉ ＝ ａｉ ＋ ｂｉ － ｘｉ 将定义 ２ 应用到优化过程中，则反向机制的优 化过程如定义 ３。 定义 ３ ［１４］ 根据定义 １ 和定义 ２，反向学习可 以描述为：假设 ｆ（ｘ）是已知问题的函数方程，ｎ 维空 间中的点 Ｐｉ（ｘ１ ，ｘ２ ，…，ｘｎ ）是函数方程 ｆ（ ｘ）的一个 解，且 ｘｉ∈ ａｉ，ｂｉ [ ] ，∀ｉ ＝ {１，２，…，ｎ} 。 则 Ｐｉ 的反向 点为 Ｐ ～ ｉ（ｘ ～ １ ，ｘ ～ ２ ，…，ｘ ～ ｎ ）。 计算 Ｐｉ 和 Ｐ ～ ｉ 在函数 ｆ（ ｘ） 中的函数值。 如果 ｆ（Ｐ ～ ｉ） ＞ｆ（Ｐｉ），则反向点 Ｐ ～ ｉ 代替 Ｐｉ；否则保留 Ｐｉ。 因此通过不断地计算点 Ｐｉ 与反向 点 Ｐ ～ ｉ 的 ｆ（ｘ）值选择其中最优值。 ３ 反向学习粒子群算法 基于反向学习策略的思想，本文提出一种改进 的粒 子 群 算 法 （ ｏｐｐｏｓｉｔｉｏｎ⁃ｂａｓｅｄ ｌｅａｒｎｉｎｇ ｉｍｐｒｏｖｅｄ ＰＳＯ， ＯＢＬＩＰＳＯ）。 本文采用反向学习策略时，将反 向学习策略应用到单个粒子中，而不是粒子群体 中，以便减小粒子迭代过程中的计算量。 性能测试 结果证明，改进的粒子群算法能抑制粒子早熟现 象，提高收敛效率。 下面介绍改进算法的主要机制 和流程。 ３．１ 初始化种群 粒子在问题空间中找到最优解的时间与粒子 初始化时在空间中的分布存在正比关系，距离最佳 位置近的粒子找到最优解的时间比距离最佳位置 远的粒子要快。 但是，粒子在问题空间中是随机分 布的，每一个粒子相对于最优解的位置都是未知的。 基于以上分析，在改进的粒子群算法初始化时 引入反向学习策略有助于粒子寻找最优解。 在初 始化时，首先，计算粒子的适应度值以及其反向粒 子适应度值，并对两者进行比较，选择适应度值较 好的粒子；其次，从种群中选择 Ｓ 个适应度值最好的 粒子作为初始种群。 ３．２ 迭代进化过程 在标准 ＰＳＯ 算法中，粒子在问题空间中选择另 一个粒子作为学习对象，根据式（１）、（２）进行移动。 但在粒子进化的过程中，粒子会发生早熟现象，导 致算法无法得到最优解。 由式（１） 可知，粒子的速 度受到惯性权重和学习因子的影响：惯性权重影响 着粒子的全局搜索和局部搜索能力，学习因子影响 粒子获取信息的能力。 为了找到问题最优解，粒子 在进化的过程中，其全局搜索能力和局部搜索能力 也应该随之发生变化，即从全局搜索渐变为局部搜 索，保证粒子可以寻找到问题的最优解。 同样，粒 子也应该逐渐增强社交能力，由“自我”学习逐渐向 “他人”学习过渡，以便获取更多有用的信息。 根据以上分析，粒子在寻优过程中，惯性权重 应该保持动态变化。 ω 取值较大时，粒子的全局搜 索能力较强；ω 取值较小时，粒子的局部搜索能力较 强。 由于粒子在寻优的过程中，会逐渐靠近最优 点，粒子的惯性权重应该随着寻优过程自适应变 化。 因此粒子的惯性权重更新公式为 ω ＝ ωｍａｘ － ωｍａｘ － ωｍｉｎ ( ) １ － ｄｉｓｔ ｉ ｍａｘ＿ｄｉｓｔ æ è ç ö ø ÷ 式中： ω ｍａｘ 和 ω ｍｉｎ 分别是粒子惯性权重的最大值和 最小值； ｄｉｓｔ ｉ 是第 ｉ 个粒子到全局最优粒子的欧几 里德距离； ｍａｘ＿ｄｉｓｔ 是粒子到全局最优粒子的最大 距离。 ｄｉｓｔ ｉ 和 ｍａｘ＿ｄｉｓｔ 表达式分别为［１５］ ｄｉｓｔ ｉ ＝ ∑ Ｄ ｄ ＝ １ ｇｂｅｓｔｄ ( － ｘｉ，ｄ ) １ ２ ｍａｘ＿ｄｉｓｔ ＝ ａｒｇｍａｘ ｄｉｓｔ ｉ ( ) ｉ 学习因子 ｃ１ 和 ｃ２ 控制粒子本身记忆与同伴记 忆之间的相对影响：ｃ１ 的值较小时，表现为自我认 知能力不足；ｃ２ 的值较小时，表现为社交能力不足。 为了保证在迭代过程中，粒子的自我认知和社交能 力能够因时而异， 因此， 粒子的学习因子更新公 式［１６］如下： ｃ１ ＝ ｃ１ｍａｘ × ｃ１ｍｉｎ ｃ１ｍａｘ æ è ç ö ø ÷ ｔ Ｔｍａｘ ( ) ·３０４· 智 能 系 统 学 报 第 １２ 卷

第3期 蒲兴成，等：基于改进粒子群算法的移动机器人多目标点路径规划 ·305· 在表2中，OBLIPS0算法在四测试函数上的平 C2=C2min 均值均小于其他3种算法的值，尤其是在Sphere函 式中：c1m和c2max以及c1mn和c2an分别是学习因子c, 数和Rastrigin函数中。从表2中数据可知， 和c,的最大值和最小值：t是当前的迭代次数：T OBLIPS0算法具有更好的收敛性，得到的解更优。 是最大迭代次数。 表3中的数据反映出改进算法的稳定性。OBLIPSO 3.3算法实现流程 算法与IAPS0算法、IPSO算法和WPSO算法对比， 1)首先初始化种群P(S),包括粒子的位置x 在稳定性上表现得更好。 和速度y,i=1,2,…,S,S是种群的大小，初始化惯 表2平均最优值结果对比 性权重ω以及学习因子c,和c,等参数。 Table 2 The comparison of average best values 2)在速度和位置规定的范围内根据式(1)、(2) 函数OBLIPSO IAPSO IPSO WPSO 更新第i个粒子的速度"：和位置x,o 0 0.1327900.020476 0.034939 3)计算第i个粒子的适应度值∫。 0 0.0663790.066331 0.298488 4)a,=min(x:)。 5 0.0021530.0316920.017342 0.018080 5)b:=max(x:)。 f 0.0032730.0053280.006179 0.017561 6)计算第i个粒子的位置和速度反向解：x, a:+b:-Xio 表3标准方差结果对比 7)计算第i个粒子反向解的适应度值了：。 Table 3 The comparison of standard deviation 函数 OBLIPSO IAPSO IPSO WPSO 8)比较f和子：的大小，如果了：<f,则x:=x, 0 0.7147750.009423 0.006733 f=fio 9)从最优适应度值中选出S个适应度值最好 0 0.2481740.248186 0.455948 的粒子组成初始化种群。 5 0.0044180.0875050.021595 0.019151 10)接下来同粒子群算法基本流程。 f40.00456000.0046990.004650 0.032801 11)算法满足结束条件，结束算法过程。 由表2和表3数据可得：反向学习策略提高了 4 实验结果与分析 种群的多样性，增加了粒子寻优成功概率，节省了 4.1 OBLIPS0性能测试 粒子寻优时间：线性变化的惯性权重保障了粒子从 为了验证改进粒子群算法的性能是否得到改 全局搜索到局部搜索的线性转换，抑制了粒子早熟 进，笔者将反向学习的粒子群算法与其他改进算 现象：学习因子的变化保证了粒子能够充分完成自 法[15,7-1]在4个适应度函数上进行对比。这4个适 我学习和社交行为，提高了粒子的收敛速度。 应度函数分别为Sphere函数、Rastrigin函数、 4.2路径规划仿真实验 Grewank函数、Schaffer函数，测试函数参数设置如 为了验证新方法的实用性及有效性，笔者将该 表1所示。 方法在仿真环境下进行实验。仿真实验环境设置 表1测试函数参数设置 在18×16的二维矩形空间内，并设置成简单环境和 Table 1 The parameter setting of test function 复杂环境。在环境中有不规则的障碍物，起始点位 函数 取值范围 最优点 最优解 置使用方形表示，目标点处用五角形表示。 1)第1次实验中，OBLIPS0算法的参数设置 Sphere(f) [-100,100] (0,0) 0 为：0x=0.9,0mn=0.4,S=10,c1mm=2.75,c2mx= Rastrigin() [-5.12,5.12] (0,0) 0 2.25,c1n=1.25,c2in=0.5,心=1.9,0m=0,斥力场 Grewank() [-600,600] (0.0) 0 中的安全距离dn=2,k,=2.7,入=0.25,4=0.25，最大 Schaffer(f) [-100,100] (0,0) 0 迭代次数为100。图4(a)给出了在简单环境下的 OBLIPS0算法参数设置为：粒子群大小为40， OBLIPSO作用的移动机器人多目标点移动轨迹。 空间维度为2，w=[0.4,0.9],c1=[1.25,2.75],c2= 图4(b)是IAPS0作用的运动轨迹。图4(c)是 [0.5,2.25],最大迭代次数为100。 PS0作用的运动轨迹

ｃ２ ＝ ｃ２ｍｉｎ × ｃ２ｍａｘ ｃ２ｍｉｎ æ è ç ö ø ÷ ｔ Ｔｍａｘ ( ) 式中：ｃ１ｍａｘ和 ｃ２ｍａｘ以及 ｃ１ｍｉｎ和 ｃ２ｍｉｎ分别是学习因子 ｃ１ 和 ｃ２ 的最大值和最小值；ｔ 是当前的迭代次数；Ｔｍａｘ 是最大迭代次数。 ３．３ 算法实现流程 １）首先初始化种群 Ｐ（ Ｓ），包括粒子的位置 ｘｉ 和速度 ｖｉ，ｉ ＝ １，２，…，Ｓ，Ｓ 是种群的大小，初始化惯 性权重 ω 以及学习因子 ｃ１ 和 ｃ２ 等参数。 ２）在速度和位置规定的范围内根据式（１）、（２） 更新第 ｉ 个粒子的速度 ｖｉ 和位置 ｘｉ。 ３）计算第 ｉ 个粒子的适应度值 ｆ ｉ。 ４）ａｉ ＝ｍｉｎ（ｘｉ）。 ５）ｂｉ ＝ｍａｘ（ｘｉ）。 ６）计算第 ｉ 个粒子的位置和速度反向解： ｘ ～ ｉ ＝ ａｉ ＋ｂｉ －ｘｉ。 ７）计算第 ｉ 个粒子反向解的适应度值 ｆ ～ ｉ。 ８）比较 ｆ ｉ 和 ｆ ～ ｉ 的大小，如果 ｆ ～ ｉ ＜ｆ ｉ，则 ｘｉ ＝ ｘ ～ ｉ， ｆ ｉ ＝ ｆ ～ ｉ。 ９）从最优适应度值中选出 Ｓ 个适应度值最好 的粒子组成初始化种群。 １０）接下来同粒子群算法基本流程。 １１）算法满足结束条件，结束算法过程。 ４ 实验结果与分析 ４．１ ＯＢＬＩＰＳＯ 性能测试 为了验证改进粒子群算法的性能是否得到改 进，笔者将反向学习的粒子群算法与其他改进算 法［１５，１７－１８］在 ４ 个适应度函数上进行对比。 这 ４ 个适 应 度 函 数 分 别 为 Ｓｐｈｅｒｅ 函 数、 Ｒａｓｔｒｉｇｉｎ 函 数、 Ｇｒｅｗａｎｋ 函数、Ｓｃｈａｆｆｅｒ 函数，测试函数参数设置如 表 １ 所示。 表 １ 测试函数参数设置 Ｔａｂｌｅ １ Ｔｈｅ ｐａｒａｍｅｔｅｒ ｓｅｔｔｉｎｇ ｏｆ ｔｅｓｔ ｆｕｎｃｔｉｏｎ 函数 取值范围 最优点 最优解 Ｓｐｈｅｒｅ（ｆ １ ） ［－１００，１００］ （０，０） ０ Ｒａｓｔｒｉｇｉｎ（ｆ ２ ） ［－５．１２，５．１２］ （０，０） ０ Ｇｒｅｗａｎｋ（ｆ ３ ） ［－６００，６００］ （０，０） ０ Ｓｃｈａｆｆｅｒ（ｆ ４ ） ［－１００，１００］ （０，０） ０ ＯＢＬＩＰＳＯ 算法参数设置为：粒子群大小为 ４０， 空间维度为 ２，ω ＝ [０．４，０．９] ，ｃ１ ＝ [１．２５，２．７５] ，ｃ２ ＝ [０．５，２．２５] ，最大迭代次数为 １００。 在表 ２ 中，ＯＢＬＩＰＳＯ 算法在四测试函数上的平 均值均小于其他 ３ 种算法的值，尤其是在 Ｓｐｈｅｒｅ 函 数和 Ｒａｓｔｒｉｇｉｎ 函 数 中。 从 表 ２ 中 数 据 可 知， ＯＢＬＩＰＳＯ 算法具有更好的收敛性，得到的解更优。 表 ３ 中的数据反映出改进算法的稳定性。 ＯＢＬＩＰＳＯ 算法与 ＩＡＰＳＯ 算法、ＩＰＳＯ 算法和 ＷＰＳＯ 算法对比， 在稳定性上表现得更好。 表 ２ 平均最优值结果对比 Ｔａｂｌｅ ２ Ｔｈｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ａｖｅｒａｇｅ ｂｅｓｔ ｖａｌｕｅｓ 函数 ＯＢＬＩＰＳＯ ＩＡＰＳＯ ＩＰＳＯ ＷＰＳＯ ｆ １ ０ ０．１３２ ７９０ ０．０２０ ４７６ ０．０３４ ９３９ ｆ ２ ０ ０．０６６ ３７９ ０．０６６ ３３１ ０．２９８ ４８８ ｆ ２ ０．００２ １５３ ０．０３１ ６９２ ０．０１７ ３４２ ０．０１８ ０８０ ｆ ４ ０．００３ ２７３ ０．００５ ３２８ ０．００６ １７９ ０．０１７ ５６１ 表 ３ 标准方差结果对比 Ｔａｂｌｅ ３ Ｔｈｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｓｔａｎｄａｒｄ ｄｅｖｉａｔｉｏｎ 函数 ＯＢＬＩＰＳＯ ＩＡＰＳＯ ＩＰＳＯ ＷＰＳＯ ｆ １ ０ ０．７１４ ７７５ ０．００９ ４２３ ０．００６ ７３３ ｆ ２ ０ ０．２４８ １７４ ０．２４８ １８６ ０．４５５ ９４８ ｆ ２ ０．００４ ４１８ ０．０８７ ５０５ ０．０２１ ５９５ ０．０１９ １５１ ｆ ４ ０．００４ ５６０ ０ ０．００４ ６９９ ０．００４ ６５０ ０．０３２ ８０１ 由表 ２ 和表 ３ 数据可得：反向学习策略提高了 种群的多样性，增加了粒子寻优成功概率，节省了 粒子寻优时间；线性变化的惯性权重保障了粒子从 全局搜索到局部搜索的线性转换，抑制了粒子早熟 现象；学习因子的变化保证了粒子能够充分完成自 我学习和社交行为，提高了粒子的收敛速度。 ４．２ 路径规划仿真实验 为了验证新方法的实用性及有效性，笔者将该 方法在仿真环境下进行实验。 仿真实验环境设置 在 １８×１６ 的二维矩形空间内，并设置成简单环境和 复杂环境。 在环境中有不规则的障碍物，起始点位 置使用方形表示，目标点处用五角形表示。 １） 第 １ 次实验中，ＯＢＬＩＰＳＯ 算法的参数设置 为：ωｍａｘ ＝ ０． ９，ωｍｉｎ ＝ ０． ４，Ｓ ＝ １０，ｃ１ｍａｘ ＝ ２． ７５，ｃ２ｍａｘ ＝ ２．２５，ｃ１ｍｉｎ ＝ １．２５，ｃ２ｍｉｎ ＝ ０．５，ｖｍａｘ ＝ １．９，ｖｍｉｎ ＝ ０，斥力场 中的安全距离 ｄｍ ＝ ２，ｋｒ ＝ ２．７，λ ＝ ０．２５，μ ＝ ０．２５，最大 迭代次数为 １００。 图 ４（ ａ） 给出了在简单环境下的 ＯＢＬＩＰＳＯ 作用的移动机器人多目标点移动轨迹。 图 ４（ ｂ） 是 ＩＡＰＳＯ 作用的运动轨迹。 图 ４ （ ｃ） 是 ＩＰＳＯ 作用的运动轨迹。 第 ３ 期 蒲兴成，等：基于改进粒子群算法的移动机器人多目标点路径规划 ·３０５·