雷玉梅

(阜新高等专科学校，辽宁 阜新 123000)

0 引言

TSP(Traveling Salesman Problem)问题，也称旅行商问题或货郎担问题，是一个典型的NP(Non-deterministic Polynomial)完全问题。它不仅描述了商人从一个城市出发，经过其他多个城市，且只经过一次之后，又回到出发城市的问题，也是数学领域一个复杂的组合优化问题，更是诸多领域内许多复杂问题的概括的形式化描述。凡是可以抽象地表示为遍历且只遍历所有结点一次，最终回到初始结点，求代价最小的回路问题，都可以仿照求解TSP 问题的方法进行求解。因此，TSP 问题的解决方案在计算机理论和实际应用中得到广泛的关注。

目前解决TSP 问题的方法大致可以分为2 大类［1］，一类是拥有较好的数理逻辑和理论基础的精确的计算方法(Exact Algorithm)，能够找到问题的最优解，另一类是近似的计算方法(Approximation Algorithm)，没有严密的数理逻辑，但通常能够更为高效地求得可接受的问题的解，因此在实际中应用更为广泛，遗传算法就是一种典型的近似计算方法。

遗传算法是根据优胜劣汰的生物进化理论设计出来的一种优化的搜索算法，主要通过遗传染色体信息，选择对“环境”的“适应能力”高于父代的子代，直到适应能力满足一定的要求。高经纬等人在文献［2］中证明了使用遗传算法求解TSP 问题时具有结果准确、收敛速度快的特点。文献［3-9］从不同的方面对遗传算法进行改进，提升了其解决TSP 问题的能力。然而，对于大规模的TSP 问题，始终没有较好的解决办法，也吸引了越来越多的研究学者的关注。……