D0I:10.133745.issn1001-053x.2013.07.017 第35卷第7期 北京科技大学学报 Vol.35 No.7 2013年7月 Journal of University of Science and Technology Beijing Jul.2013 一种基于粒子群参数优化的改进蚁群算法及其应用 张超，李擎)凶，陈鹏)，杨守功)，尹怡欣) 1)北京科技大学自动化学院，北京1000832)中国科学院国家天文台，北京100012 ☒通信作者，E-mail:liqing@ies.ustb.edu.cm 摘要针对现有基于粒子群参数优化的改进蚁群算法耗时较大的问题，提出了一种新的解决方案.方案中采用一种全 局异步与精英策略相结合的信息素更新方式，同时合理减少蚁群算法被粒子群算法调用一次所需的迭代代数.对日本旭 川垃圾场巡查机器人路径规划问题仿真求解的结果表明，与其他算法相比，该改进算法具有比较明显的速度优势 关键词粒子群算法：蚁群算法：机器人：路径规划：旅行商问题 分类号TP181 Improved ant colony optimization based on particle swarm optimiza- tion and its application ZHANG Chao),LI Qing),CHEN Peng?),YANG Shou-gong),YIN Yi-rin!) 1)School of Automation,University of Science and Technology Beijing,Beijing 100083,China 2)National Astronomical Observatories,Chinese Academy of Sciences,Beijing 100012,China Corresponding author,E-mail:liqingaies.ustb.edu.cn ABSTRACT This article introduces a novel algorithm to solve the large time-consuming problem of the existing improved ant colony optimization (ACO)based on particle swarm optimization(PSO).A new pheromone update method which combines the global asynchronous feature and elitist strategy was used in the algorithm.Moreover,the iteration steps of ACO invoked by PSO were reasonably reduced.The algorithm was applied to solve the path planning problem of landfill inspection robots in Asahikawa,Japan.It is shown that the algorithm has a better performance in search speed compared with other algorithms recently reported. KEY WORDS particle swarm optimization;ant colony optimization;robots;path planning;traveling salesman problem 目前，蚁群算法已广泛地应用于多种组合优化 成果r-周 及控制系统领域的问题，如路由优化)、模糊神经 本文提出了一种新的基于粒子群参数优化的 控制回、函数优化周、车辆调度【-、图着色同等. 改进蚁群算法.该算法通过采用全局异步与精英策 在蚁群算法中，参数的选取较大地依赖于实验者的 略相结合的信息素更新方法、减少粒子群算法中每 个人经验，人为试凑选取参数的方式极大地影响着 个粒子调用蚁群算法迭代代数等方式大大降低了算 算法的效率和智能性.一旦参数选取不当，蚁群算 法的迭代规模，减小了时间成本 法会出现未成熟收敛等问题，制约了蚁群算法发挥 其最好的性能.因此蚁群算法参数优化，一直是国 1基于粒子群参数优化改进蚁群算法的提出 内外学者研究的热点问题.一些研究人员尝试应用 本文所提基于粒子群参数优化的改进蚁群算 粒子群算法优化蚁群算法中的参数，并取得了一些 法的步骤如下， 收稿日期：2012-04-11 基金项目：教育部第36批“留学回国人员科研启动基金”资助项目(1341)：国家自然科学基金资助项目(60374032)：北京市重点 学科建设项目(XK100080537)第 35 卷 第 7 期 北 京 科 技 大 学 学 报 Vol. 35 No. 7 2013 年 7 月 Journal of University of Science and Technology Beijing Jul. 2013 一种基于粒子群参数优化的改进蚁群算法及其应用 张 超 1)，李 擎 1) ，陈 鹏 2)，杨守功 1)，尹怡欣 1) 1) 北京科技大学自动化学院, 北京 100083 2) 中国科学院国家天文台，北京 100012 通信作者，E-mail: liqing@ies.ustb.edu.cn 摘 要 针对现有基于粒子群参数优化的改进蚁群算法耗时较大的问题，提出了一种新的解决方案. 方案中采用一种全 局异步与精英策略相结合的信息素更新方式，同时合理减少蚁群算法被粒子群算法调用一次所需的迭代代数. 对日本旭 川垃圾场巡查机器人路径规划问题仿真求解的结果表明，与其他算法相比，该改进算法具有比较明显的速度优势. 关键词 粒子群算法；蚁群算法；机器人；路径规划；旅行商问题 分类号 TP181 Improved ant colony optimization based on particle swarm optimiza￾tion and its application ZHANG Chao1), LI Qing1) , CHEN Peng2), YANG Shou-gong1), YIN Yi-xin1) 1) School of Automation, University of Science and Technology Beijing, Beijing 100083, China 2) National Astronomical Observatories, Chinese Academy of Sciences, Beijing 100012, China Corresponding author, E-mail: liqing@ies.ustb.edu.cn ABSTRACT This article introduces a novel algorithm to solve the large time-consuming problem of the existing improved ant colony optimization (ACO) based on particle swarm optimization (PSO). A new pheromone update method which combines the global asynchronous feature and elitist strategy was used in the algorithm. Moreover, the iteration steps of ACO invoked by PSO were reasonably reduced. The algorithm was applied to solve the path planning problem of landfill inspection robots in Asahikawa, Japan. It is shown that the algorithm has a better performance in search speed compared with other algorithms recently reported. KEY WORDS particle swarm optimization; ant colony optimization; robots; path planning; traveling salesman problem 目前，蚁群算法已广泛地应用于多种组合优化 及控制系统领域的问题，如路由优化 [1]、模糊神经 控制 [2]、函数优化 [3]、车辆调度 [4−5]、图着色 [6] 等. 在蚁群算法中，参数的选取较大地依赖于实验者的 个人经验，人为试凑选取参数的方式极大地影响着 算法的效率和智能性. 一旦参数选取不当，蚁群算 法会出现未成熟收敛等问题，制约了蚁群算法发挥 其最好的性能. 因此蚁群算法参数优化，一直是国 内外学者研究的热点问题. 一些研究人员尝试应用 粒子群算法优化蚁群算法中的参数，并取得了一些 成果 [7−8] . 本文提出了一种新的基于粒子群参数优化的 改进蚁群算法. 该算法通过采用全局异步与精英策 略相结合的信息素更新方法、减少粒子群算法中每 个粒子调用蚁群算法迭代代数等方式大大降低了算 法的迭代规模，减小了时间成本. 1 基于粒子群参数优化改进蚁群算法的提出 本文所提基于粒子群参数优化的改进蚁群算 法的步骤如下. 收稿日期：2012-04-11 基金项目：教育部第 36 批 “留学回国人员科研启动基金” 资助项目 (1341)；国家自然科学基金资助项目 (60374032)；北京市重点 学科建设项目 (XK100080537) DOI:10.13374/j.issn1001-053x.2013.07.017