遗传算法求解货郎担问题(TSP)

本代码用遗传算法求解货郎担问题(TSP)。货郎担问题是组合数学中的著名问题，在算法领域颇受关注。问题是这样提出的：某旅行推销商，要到n个城市去推销商品，从其中某个城市出发，进出每个城市一次，最后返回驻地城市，问如何安排其路线，使行程最短。对于TSP问题，若采用穷举搜索算法，则需要考虑所有可能的情况，找出所有的回路，在对其进行比较，找出最佳路径。在n个城市TSP问题中，一条有效路径可以看成n个城市的排列。n个城市的全排列共有n!种，TSP问题没有限定路径的起点及方向，因此路径总数为n!/2n，可见穷举法随着城市数n的增大复杂度急剧增长。用遗传算法求解TSP问题的思想是先随机生成若干条有效路径，在选择其中较优的路径参与繁殖，生成下一代。再对下一代进行类似操作。经过若干代的进化后，将会收敛于一个较优解。此外，在遗传过程中可以加入变异算子来模仿生物界中的变异现象。