用蚂蚁算法和模拟退火算法解大规模TSP问题的研究

摘要

TSP问题是一个NP完全问题.随着问题规模的增大,其解空间呈指数增长,无法在多项式时间内完成问题的求解,近几十年来,人们提出了许多基于生物理论的解决该问题的新方法,本文应用蚂蚁算法、模拟退火算法对TSP问题进行求解.在求解过程中对各算法中参数的作用和设置方法作了一些分析,使用不同参数进行多次实验,验证参数设王原则;对不同规模的TSP问题进行实验,比较两个算法的性能,分析造成其性能差异的原因,并提出了改进建议.