摘要
旅行商问题(Traveling Salesman Problem,TSP)是一个典型的组合优化问题,并且是一个NP难题,其可能的路径总数与城市数目是呈指数型增长的,所以一般很难精确地求出其最优解,因而寻找出有效的近似求解算法就具有重要的意义。目前求解TSP问题的主要方法有模拟退火算法(Simulated Annealing,SA)、遗传算法(Genetic Algorithm,GA)和神经网络算法等。GA是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应的全局优化概率搜索算法。SA算法用于优化问题的出发点是基于物理中固体物质的退火过程与一般优化问题的相似性。文中将提出遗传算法和模拟退火算法求解TSP问题,通过试验比较两者求解TSP问题的性能,结果表明GA的性能要优于SA的性能。
TSP is a typical combination optimization problem, which is also an NP hard - problem. Its size is increased by exponential n. So, it is hard to find a precision result,and it is very important to search for the near result. Currently, the main method of solving TSP has GA, SA and the neural network algorithm. GA is a simulation of the natural environment in the biogenetic and evolutionary process of the formation of an adaptive search algorithm for global optimization probability. SA solves optimization problem, which the starting point is based on the physics of the annealing process of solids with the general similarity of optimization problems. Proposed two effective methods： genetic algorithm and simulated annealing, through the experiment, compare the two performance analysis, the resuls show that the GA＇s performance is superior to the performance of SA.
出处
《计算机技术与发展》
2009年第11期97-100,共4页
Computer Technology and Development
基金
教育部博士点基金(200403057002)
关键词
遗传算法
模拟退火算法
TSP
genetic algorithm
simulated annealing
traveling salesman problem
