旅行商问题

github项目：https://github.com/xclovehsy/geneticAlgoTSP

1. 项目描述

一个旅行者需要到国内的10个城市旅行，各城市的坐标见cities.csv文档。请设计一个合理的线路使旅行者所行的路程之和最小。注意：每个城市只能访问一次，且最后要回到原来出来的城市。

2. 算法思路

遗传算法是一种模仿自然界生物进化机制的全局搜索和优化方法。其具有以下几个基本的特征，接下来是对各个特征详细的说明。

表现型：旅行依次经过的城市，即旅行的路径。例如“重庆—>北京—>上海—>天津—>成都—>… —>重庆”这是一种旅行路径，这里需要注意的是最终需要回到起点。
基因型：我根据cities.csv文件中的城市出现的顺序，对城市进行1.2.3….编码。然后旅行经过的城市依次以序号进行编码。同时因为最后要回到起点，因此起点和终点的序号应该相同。
这里我们根据cities.csv文件中城市的次序进行编码，即：北京-0、天津-1、上海-2、重庆-3、拉萨-4、乌鲁木齐-5、银川-6、呼和浩特-7、南宁-8、哈尔滨-9。
编码：这里我选择的编码方式为：对城市进行1.2.3…次序编码，然后一条旅行路线为一个个体，编码方式为起点到终点依次经过城市的序号编码。
进化：种群逐渐适应生存环境，即总的路径长度不断得到缩小。旅行线路的进化是以种群的形式进行的。
适应度：度量某个旅行线路对于生存环境的适应程度。这里我使用旅行线路总的路径长度倒数作为种群的适应度
选择：以一定的概率从种群中选择若干个个体。我使用轮盘赌的方式对种群中的个体进行选择。
交叉：两个旅行线路的某一相同位置处城市编码，前后两串分别交叉组合形成两个新的旅行线路。也称基因重组或杂交；
变异：以一定的概率对种群中的个体进行基因突变，即随机选择个体基因中两个城市的编号进行交换。