作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2012, Vol. 38 ›› Issue (23): 190-193,197. doi: 10.3969/j.issn.1000-3428.2012.23.047

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

求解子旅行商问题的改进蚁群算法

牟廉明   

  1. (内江师范学院四川省高等学校数值仿真重点实验室,四川 内江 641100)
  • 收稿日期:2012-02-20 出版日期:2012-12-05 发布日期:2012-12-03
  • 作者简介:牟廉明(1971-),男,副教授、硕士,主研方向:智能计算,机器学习
  • 基金资助:
    国家自然科学基金资助项目(10872085);四川省科技厅应用基础研究基金资助项目(07JY029-125);四川省教育厅重大培育基金资助项目(07ZZ016)

Improved Ant Colony Algorithm for Solving Subset Traveling Salesman Problem

MOU Lian-ming   

  1. (Key Laboratory of Numerical Simulation in the Sichuan Provincial College, Neijiang Normal University, Neijiang 641100, China)
  • Received:2012-02-20 Online:2012-12-05 Published:2012-12-03

摘要: 已有求解子旅行商问题的蚁群算法存在容易早熟、易于陷入局部最优的问题。为此,提出一种改进的蚁群算法。将拥挤因子嵌入到蚁群算法的状态转移和信息素更新过程中,增强全局搜索能力,设计邻域搜索技术和局部变异技术,以提高解的质量和加快收敛速度。实验结果表明,该算法的求解质量和稳定性较好。

关键词: 旅行商问题, 局部最优, 拥挤因子, 邻域搜索, 局部变异, 蚁群算法

Abstract: Existing ant colony algorithm is easy precocious and easy to fall into local optimum when the Subset Traveling Salesman Problem (STSP) is solved through it. In order to solve this problem, the crowding factor is embedding into the state transition and the pheromone update according to the characteristic of the STSP. It makes its global searching ability enhance remarkably. An efficient neighborhood searching technique and a simple and effective local mutation technique are introduced into this algorithm to improve further the quality of solution. Experimental results show that the improved algorithm has much higher quality and stability than that of existing ant colony algorithm.

Key words: Traveling Salesman Problem(TSP), local optimum, crowding factor, neighborhood searching, local mutation, ant colony algorithm

中图分类号: