计算机工程与应用 ›› 2019, Vol. 55 ›› Issue (15): 75-81.DOI: 10.3778/j.issn.1002-8331.1811-0349

• 理论与研发 • 上一篇    下一篇

自适应模糊蚁群系统

李娟,游晓明,刘升,陈佳   

  1. 1.上海工程技术大学 电子电气工程学院,上海 201620
    2.上海工程技术大学 管理学院,上海 201620
  • 出版日期:2019-08-01 发布日期:2019-07-26

Adaptive Fuzzy Ant Colony System

LI Juan, YOU Xiaoming, LIU Sheng, CHEN Jia   

  1. 1.College of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China
    2.College of Management, Shanghai University of Engineering Science, Shanghai 201620, China
  • Online:2019-08-01 Published:2019-07-26

摘要: 针对蚁群系统(Ant Colony System,ACS)容易陷入局部最优和收敛速度较慢的不足,提出了自适应模糊蚁群系统(AF-ACS)用于旅行商问题(TSP)。该算法的核心是引入模糊隶属度和信息熵的概念,AF-ACS将以信息熵为概率,自适应地对ACS引入模糊隶属度,以平衡算法的种群多样性与收敛速度之间的关系。算法早期引入模糊隶属度的概率较小,保证算法的多样性;算法后期引入模糊隶属度的概率较大,提高算法的收敛速度。通过与ACS和ECACS(Entropy-based Adaptive Chaotic Ant Colony Algorithm)进行14种不同规模的TSP测试集实验对比,AF-ACS以较少的迭代次数取得最优解或较优解。从而证明了AF-ACS的可行性与高效性。

关键词: 自适应, 蚁群系统, 模糊隶属度, 信息熵, 旅行商问题

Abstract: Because the Ant Colony System(ACS) is easy to fall into the local optimization and slow convergence, an Adaptive Fuzzy Ant Colony System(AF-ACS) is proposed for Traveling Salesman Problem(TSP). The core of the algorithm is to introduce the concept of fuzzy membership and information entropy. AF-ACS will adaptively introduce fuzzy membership to ACS with information entropy as the probability. This balances the relationship between the population diversity of the algorithm and the rate of convergence. The probability of introducing fuzzy membership degree early in the algorithm is small, which ensures the diversity of the algorithm. The probability of introducing fuzzy membership degree in the later stage of the algorithm is large, which improves the convergence speed of the algorithm. By comparing 14 different scale TSP test sets with ACS and ECACS(Entropy-based Adaptive Chaotic Ant Colony Algorithm), AF-ACS obtains the optimal solution or better solution with fewer iterations. This proves the feasibility and efficiency of AF-ACS.

Key words: adaptive, ant colony system, fuzzy membership degree, information entropy, travelling salesman problem