计算机工程与应用 ›› 2015, Vol. 51 ›› Issue (16): 117-120.

• 数据库、数据挖掘、机器学习 • 上一篇    下一篇

求解TSP的蚁群与模糊自适应粒子群算法

张海俊,王  波   

  1. 上海理工大学 管理学院,上海 200093
  • 出版日期:2015-08-15 发布日期:2015-08-14

Solution of TSP of ant colony optimization and fuzzy adaptive particle swarm algorithm

ZHANG Haijun, WANG Bo   

  1. School of  Manage, University of Shanghai for Science and Technology, Shanghai 200093, China
  • Online:2015-08-15 Published:2015-08-14

摘要: 为了解决规模复杂的旅行商问题,提出了融合蚁群算法和粒子群算法的一种群体智能混合算法,并构建了惯性权值模糊自适应调整模型。针对此混合算法易陷入局部最优,设计了参数自动调节机制,以达到局部搜索和全局搜索之间的平衡。在搜索的初期时,参数[ω]会自适应调整为较大值,则算法应具有很强的全局搜索能力;当进入搜索的后期时,参数[ω]会自适应调整为较小值,则算法应具有较强的局部搜索能力。通过大量仿真实验表明,改进的混合算法搜索能力优于同类算法和传统算法,而且该模型应用在大规模TSP中,获得了满意的效果。

关键词: 蚁群算法, 粒子群算法, 模糊技术, 群体智能, 演化交叉

Abstract: In order to solve the complex scale problem of traveling salesman, it puts forward a kind of swarm intelligent hybrid algorithm of combination of ant colony algorithm and particle swarm algorithm and constructs fuzzy self-adapted adjustment model of inertia weight. For the hybrid algorithm trapped into local optimaleasily, the parameter automatic adjustment mechanism is designed to achieve local search and global search of equilibrium. In the early of search, the parameters [ω] would adaptively adjust to a larger value, after that the algorithm has strong global search ability. In the late stage of search, the parameters [ω] would adaptively adjust to a smaller value, after that the algorithm has strong local search capability. A number of simulation experiments show that search ability of the improved hybrid algorithm is superior to the similar algorithm and traditional algorithm. And it has satisfactory results applied in large scale TSP.

Key words: ant colony algorithm, particle swarm algorithm, fuzzy technology, swarm intelligence, evolution cross