TSP问题(Traveling Salesman Problem)是已知有n个城市,现有一推销员必须遍访这n个城市,且每个城市只能访问一次,最后又必须返回出发城市。要安排其访问次序,使其旅行路线的总长度最短。TSP是经典的NP-hard组合优化问题之一,也是一个测试算法优劣性的标准问题,且现实中有很多应用问题都可归结或转化为TSP问题。故对此问题的求解具有理论与实用两方面的意义。传统的求解方法在面对较大规模的问题时,很不容易得到最优解。
人们一直在尝试用新的方法来改进求解该问题的复杂程度。目前求解TSP问题的主要方法有启发式搜索法、模拟退火算法、遗传算法、Hopfield神经网络算法、二叉树描述算法。所以,有效解决TSP问题在计算理论上和实际应用上都有很高的价值,本文采用Hopfield神经网络和遗传算法来求解TSP问题,深入讨论了Hopfield神经网络和遗传算法解决TSP问题的求解过程,并通过MATLAB对算法进行了实现,最后对实验结果进行分析,并将两种方法进行比较与分析,最终通过仿真得出结论。
关键字:TSP,Hopfield神经网络,遗传算法,HopfieldTSP,GeneticTSP