求解旅行商问题的模拟退火算法

Solving TSP with Simulated Annealing Algorithm

旅行商问题TSP是一个典型的NP完全问题,模拟退火算法是求解此问题的一种理想方法。模拟退火算法是依赖邻域结构的迭代方法,模拟退火算法对选择试验解比较敏感。本文针对找领域解,提出6种策略。算法的分析和测试表明,策略F是一种简单有效的算法。

TSP (Traveling Salesman Problem) is a typical NP-Complete problem. The simulated annealing algorithm (SA) is a better method for solving TSP. The simulated annealing algorithm is an iterative search procedure based on a neighborhood structure. The quality of the annealing solution is very sensitive to the way that the trial solutions are selected. In order to search neighborhood of the trial solution, six strategies are put forward. By analysis and test, it is proved that Strategy F is a simple and effective algorithm.