计算机工程

• 人工智能及识别技术 • 上一篇    下一篇

基于混沌的MMAS算法及其在旅行商问题中的应用

耿志强,邱大洪,韩永明   

  1. (北京化工大学信息科学与技术学院,北京 100029)
  • 收稿日期:2015-01-16 出版日期:2016-03-15 发布日期:2016-03-15
  • 作者简介:耿志强(1973-),男,教授、博士生导师,主研方向为系统建模与优化、数据挖掘、机器学习;邱大洪,硕士研究生;韩永明,讲师、博士。
  • 基金项目:

    国家自然科学基金资助项目(61374166);教育部博士点基金资助项目(20120010110010);中央高校基本科研业务费专项基金资助项目(YS1404)。

Max-min Ant System Algorithm Based on Chaos and Its Application in TSP

GENG Zhiqiang,QIU Dahong,HAN Yongming   

  1. (College of Information Science & Technology,Beijing University of Chemical Technology,Beijing 100029,China)
  • Received:2015-01-16 Online:2016-03-15 Published:2016-03-15

摘要:

最大最小蚂蚁系统算法初始信息素均匀分布,但存在无法快速进行全局搜索,容易出现停滞并陷入局部最优的缺点。为此,通过引入全局遍历性能更优的Tent混沌映射,提出一种基于混沌的最大最小蚁群改进算法。利用混沌的遍历特性产生一组较优路径指导初始信息素的非均匀分布,运用混沌扰动的方法增强算法跳出局部最优的能力。以较大规模旅行商问题为应用对象进行实验,结果表明,改进算法具有更高的全局寻优成功率和更快的收敛速度。

关键词: 混沌, Tent映射, 最大最小蚂蚁系统, 旅行商问题, 信息素

Abstract:

In Max-min Ant System(MMAS) algorithm,initial pheromone distributes well,it can not reach global search,which is easy to stop and falls into local optima.Therefore an improved MMAS algorithm is proposed based on Tent chaotic mapping to enhance the capability of escaping from local optima.This method generates a group of candidates to guide the distribution of pheromone by exploiting ergodic property of chaos.When the searching stagnation is appeared,a chaotic disturbance method is utilized to obtain a better solution.Results among different ant colony optimization algorithm on large-scale Traveling Salesman Problem(TSP) show that the improved algorithm has higher success rate and faster convergence rate for global optimization.

Key words: chaos, Tent mapping, Max-min Ant System(MMAS), Traveling Salesman Problem(TSP), pheromone

中图分类号: