关键词: 蚂蚁算法 模拟退火算法 TSP问题 NP完全问题

Abstract:

The Traveling Salesman Problem （TSP） is a non-polynomial-complete （NPC） problem. With the scale increases,the solution space grows rapidly, making   it impossible to be solved in a polynomial time. During the past several decades, people found new ways to solve the problem based on the mechanism of  biological theory. How to use the ant algorithm and the simulated annealing algorithm to solve the large-scale traveling salesman problem is studied, an d the functions of the parameters and the method of configuring them in the two algorithms are analyzed. After the experiments with different scales of   TSPs, the efficiencies of the two algorithms are compared, and the reasons for the difference of efficiencies are discussed. Finally, the suggestions fo  r improving the algorithms are given.

Key words: ant algorithm, simulated annealing, TSP, non-polynomial-complete problem