遗传算法和模拟退火算法求解TSP的性能分析

摘要

旅行商问题(Traveling Salesman Problem,TSP)是一个典型的组合优化问题,并且是一个NP难题,其可能的路径总数与城市数目是呈指数型增长的,所以一般很难精确地求出其最优解,因而寻找出有效的近似求解算法就具有重要的意义.目前求解TSP问题的主要方法有模拟退火算法(Simulated Annealing,SA)、遗传算法(Genetic Algorithm,GA)和神经网络算法等.GA是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应的全局优化概率搜索算法.SA算法用于优化问题的出发点是基于物理中固体物质的退火过程与一般优化问题的相似性.文中将提出遗传算法和模拟退火算法求解TSP问题,通过试验比较两者求解TSP问题的性能,结果表明GA的性能要优于SA的性能.