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

计算机工程

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

基于α-邻近的改进蚁群算法

吕金秋a,游晓明a,刘 升b   

  1. (上海工程技术大学a. 电子电气工程学院; b. 管理学院,上海201620)
  • 收稿日期:2014-03-12 出版日期:2015-02-15 发布日期:2015-02-13
  • 作者简介:吕金秋(1991 - ),男,硕士,主研方向:智能信息处理,嵌入式系统;游晓明、刘 升,教授、博士。
  • 基金资助:
    国家自然科学基金资助项目(61075115);上海市教委科研创新基金资助重点项目(12ZZ185)。

Improved Ant Colony Algorithm Based on α-nearest

LV Jinqiu a ,YOU Xiaoming a ,LIU Sheng b   

  1. (a. College of Electronic and Electrical Engineering; b. School of Management,Shanghai University of Engineering Science,Shanghai 201620,China)
  • Received:2014-03-12 Online:2015-02-15 Published:2015-02-13

摘要: 为克服传统蚁群系统(ACS)在较大规模问题计算中易陷入局部最优,以及求解精度较低等不足,提出一种新的改进蚁群算法。该算法引入最小1-树中的α-邻近概念,能更好地反映给定边属于最优回路的概率,通过转换邻接矩阵,计算出最优回路的下界,以此提高α 值的精度,并给出适应性探索策略,加入3-opt 领域搜索算子,有效提高优化解的精度。实验结果表明,该算法具有更好的全局寻优能力,与ACS 等算法相比能获得更加优化 的解。

关键词: 蚁群系统, α-邻近, 最小1-树, 下界, 适应性策略, 旅行商问题

Abstract: In order to overcome the disadvantages that traditional Ant Colony System(ACS) is easy to fall into local optimum and low-precision for large-scale problems,this paper presents an improved ant colony optimization algorithm.The algorithm introduces α-nearest in the minimum 1-tree,which better reflects the chances of a given link being a member of an optimal tour. It improves α-nearest precision by transforming the adjacency matrix and computes a lower bound. Besides,it proposes the adaptive exploration strategy and 3-opt local search. Experimental results show that this algorithm has a better global searching ability in finding the best solutions and can obtain better solutions than ACS,etc.

Key words: Ant Colony System ( ACS ), α-nearest, minimum 1-tree, lower bound, adaptation strategy, Travelling Salesman Problem(TSP)

中图分类号: