基于遗传算法求解TSP问题（JAVA）
一、TSP问题
TSP问题（Travelling Salesman Problem）即旅行商问题，又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。TSP问题可以分为两类，一类是对称TSP问题（Symmetric TSP），另一类是非对称问题（Asymmetric TSP）。所有的TSP问题都可以用一个图（Graph）来描述：
V={c1, c2, …, ci, …, cn}，i = 1,2, …, n，是所有城市的集合.ci表示第i个城市，n为城市的数目；
E={(r, s): r,s∈ V}是所有城市之间连接的集合；
C = {crs: r,s∈ V}是所有城市之间连接的成本度量（一般为城市之间的距离）；
如果crs = csr, 那么该TSP问题为对称的，否则为非对称的。
一个TSP问题可以表达为：
求解遍历图G = (V, E, C)，所有的节点一次并且回到起始节点，使得连接这些节点的路径成本最低。
二、遗传算法
遗传算法（Genetic Algorithms ）是基于生物进化理论的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。它是在70年代初期由美国密西根（ Michigan ）大学的霍兰（ Holland ）教授发展起来的。1975年霍兰教授发表了第一本比较系统论述遗传算法的专著《自然系统与人工系统中的适应性》（《 Adaptationin Natural and Artificial Systems 》）。遗传算法最初被研究的出发点不是为专门解决最优化问题而设计的，它与进化策略、进化规划共同构成了进化算法的主要框架，都是为当时人工智能的发展服务的。迄今为止，遗传算法是进化算法中最广为人知的算法。
遗传火算法的实施步骤如下（以目标函数求最小为例）。
第一步：初始化 t←0进化代数计数器；T是最大进化代数；随机生成M个个体作为初始群体P（t）；
第二步：个体评价 计算P（t）中各个个体的适应度；
第三步：选择运算 将选择算子作用于群体；
第四步：交叉运算 将交叉算子作用于群体；
第五步：变异运算 将变异算子作用于群体，并通过以上运算得到下一代群体P（t + 1）;
第六步：终止条件判断 tT：t← t+1 转到步骤2；t>T：终止 输出解。
遗传算法应用步骤：
1）确定决策变量及各种约束条件，即个体的表现型X和问题的解空间；
2）建立优化模型 （目标函数最大OR 最小） 数学描述形式 量化方法；
3）染色体编码方法；
4）解码方法；
5）个体适应度的量化评价方法 F(x)
6）设计遗传算子；
7）确定有关运行参数。
三、遗传算法求解TSP问题
其实之前不大想写这个遗传算法求TSP，因为我之前已经有遗传算法求01背包了，但有些读者建议，加上确实tsp与01背包差别还是很大的，就再写一个。对于TSP之类的问题NP问题，使用启发式搜索算法是一个明智的选择，因为精确算发已经力不从心了。
使用遗传算法第一件事情就是确定染色编码方式，它根据不同的问题模型使用不同编码方式，有二进制编码也有整数编码和浮点数编码，面对TSP问题，我肯定选用整数编码，因为很简单，对于每个城市用一个整数来编号，例如有48个城市，就用0到47来标识每一个城市，然后一个路径就是一条染色体编码，染色体长度为48，如：0,1,2,3,4...47就是一个染色体，它表达的意思就是旅行者从0号城市出发，依次访问1,2,...47号城市再回到0号城市；遗传算法的第二个要点就是评价函数，TSP的评价函数很简单，就是染色体编码表达的路径总长度；最后很简单，其实在这个模型中就是将0到47这48个数进行全排列，从中找出最短的一条路径（想想48个数全排列，然后比较。。。）。清楚了解了这些，咱们就可以按照上面的遗传算法框架来进行编程了。
我们使用TSP问题依然来自于tsplib上的数据att48，这是一个对称TSP问题，城市规模为48，其最优值为10628.其距离计算方法下图所示：
具体代码如下：
四、总结
看到上面两个结果差别还是相当大的，其实我代码里提供了两个进化函数，两种交叉算子，需要提醒的是上面比较好的结果其实是使用了evolution1()这个进化函数，较差的是使用了evolution()这个函数，他们的最大区别就是前者保留最好染色体不进行交叉变异，后者则是按照基本遗传算法框架的完全交叉变异操作的，其区别之大各位可以深入琢磨，两种交叉算子的区别是一个就是简单的类OX交叉算子，另外一个交叉算子改进了一下，相同染色体交叉产生不同子代染色体，实际上它两对结果影响并不是很大，以上是我的一点点简单的总结，还是那句话，或许你觉得遗传算法效率其实也不怎样，实际上基本的遗传算法是有很多不足的，如容易选入局部收敛，全局搜索能力不够强，但是基本的遗传算法是有很多可以改进的地方，如交叉算子的设计、变异算子的设计、选择策略等等，有关遗传算法个人觉得作为一种智能启发式搜索算法它甚至比别的普通算法（如动态规划）理解起来还容易，而且它特别容易与别的算法相结合，设计新的混合算法，另外在基本遗传算法的基础上还衍生出了很多别的算法，如免疫遗传算法，这些都是一些比较高级的算法。
注：本文部分内容来源于网络，但程序以及分析结果属于本人成果，转载请注明！
