计算机科学与探索 ›› 2019, Vol. 13 ›› Issue (10): 1754-1767.DOI: 10.3778/j.issn.1673-9418.1810022

• 人工智能与模式识别 • 上一篇    下一篇

协同过滤策略的异构双种群蚁群算法

朱宏伟,游晓明,刘升   

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

Heterogeneous Dual Population Ant Colony Algorithm Based on Cooperative Filtering Strategy

ZHU Hongwei, YOU Xiaoming, LIU Sheng   

  1. 1. College of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China
    2. School of Management, Shanghai University of Engineering Science, Shanghai 201620, China
  • Online:2019-10-01 Published:2019-10-15

摘要: 针对蚁群算法收敛速度较慢,易陷入局部最优等问题,提出一种基于协同过滤策略的异构双种群蚁群算法。针对两个异构种群,引入协同过滤策略,奖励两个种群中蚂蚁更加偏好的路径,使算法更具导向性,加快算法的收敛速度;根据种群之间信息的动态反馈,自适应调整两个种群的交流频率,增加算法多样性;算法停滞时,两个种群协同交互,均化每个种群信息素,跳出局部最优。最后,引入神经网络失活思想,采用城市范围失活的方法,使程序运行时间更短。在对中大规模商旅问题(TSP)测试集仿真实验上,该算法提高了解的质量,保证了算法的多样性,加快了算法的收敛速度。

关键词: 蚁群算法, 双种群, 商旅问题(TSP), 协同过滤, 城市失活

Abstract: Aiming at the problems that the ant colony algorithm is easy to fall into local optimum and the convergence speed is slow, a heterogeneous dual population ant colony algorithm based on cooperative filtering strategy is proposed. For the two heterogeneous populations, a collaborative filtering strategy is introduced to reward the more preferred paths of ants in the two populations, which is used for making the algorithm more oriented and speeding up the convergence of the algorithm; the frequency of dual population information exchange is adaptively adjusted based on the dynamic feedback of information between populations and the diversity of algorithm is increased. When the algorithm is stagnant, each population pheromone is averaged according to the dynamic interaction feedback between the populations, and the local optimum is jumped out. Finally, according to the idea of neural network inactivation, the method of city-wide inactivation is used to make the program run time shorter. In the medium and large scale traveling salesman problem (TSP) experiment, the algorithm improves the quality of the understanding, ensures the diversity of the algorithm, and accelerates the convergence speed of the algorithm.

Key words: ant colony algorithm, dual population, traveling salesman problem (TSP), collaborative filtering, city inactivation