蚁群算法求解旅行商问题综述

Review of Ant Colony Algorithm for Solving Traveling Salesman Problem

蚁群优化是一种元启发式的随机搜索技术,是目前解决组合优化问题最有效的工具之一。旅行商问题(TSP)是一个典型的组合优化问题,易于描述却难于求解。在介绍了求解旅行商问题的三种经典的蚁群算法的基本原理后,着重分析了蚁群算法的发展现状,总结出蚁群算法发展的五个方向,即基于局部优化算法的蚁群算法、对路径上的信息素更新方法进行改进、蚁群算法与其他算法的融合、对蚁群算法的控制参数进行优化和并行蚁群算法。而且这五个方向有相互融合的趋势。

Ant colony optimization（ACO） is a meta-heuristic random search technique to solve combination optimization problems effectively. Traveling Salesman Problem（TSP） is a typical combination optimization problem, which is easy to be described and hard to be solved. After describing the basic principle of three classical ant colony algorithm for solving the traveling salesman problem, current development situations of ant colony algorithm are emphatically analyzed. Five main de- velopment directions of ant colony algorithm are summarized, including, local optimization algorithm based ant colony algo- rithm, the improvement of the pheromone update method, the combination of ant colony algorithm and other algorithm, opti- mize parameter of ant colony algorithm and parallel ant colony algorithm. And these five development directions have the trend of integration.