旅行商问题(Traveling Salesman Problem，TSP)是一个经典的组合优化问题。经典的TSP可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。

在本文中使用的数据为来自TSPLIB的 ATT48 ，即美国本土48个州首府坐标，TSPLIB的已知最优解为10628。

从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个NP完全问题。

由于NPC问题至今没有得到解决，TSP问题往往是通过启发式搜索（我觉得也可以叫暴力）算法来“猜”出最优解。

使用遗传算法来解决TSP问题，主要思路如下：

遗传算法在TSP问题上可以融合多种算法，从而达到不同的效果，比如交叉应该如何交叉，变异应该如何变异等等。同时遗传算法的参数难以调整到最优——包括交叉率，变异率，种群容量等可以对搜索过程产生较大影响的参数都难以调整。限于个人水平，我无法从数学上给出最优参数，只能以经验论，加以多次实验选取表现优秀的样本。

语言：C++

个体（解）的表示：用 vector 储存，代表节点遍历顺序

距离的计算：取伪欧式（pseudo Euclidean）距离，计算方法如下（向上取整）：

使用 unordered_map ，内部实现为散列表，使得计算个体适应度可以达到 O (N)​级别的复杂度

随机数的生成：设置时间种子，并由此生成随机数

交叉对象的选择：轮盘赌

交叉算法的选择：顺序移位

变异算法的选择：顺序移位 / 贪婪倒位

参数的选择：由多次实验得出

关于参数选择及其他方面的详细讨论请见 遗传算法解决TSP问题 .