原文链接: http://blog.5long.me/2015/genetic-algorithm-on-tsp/
关于遗传算法，首先看一段维基百科的解释：
遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，它借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应的控制搜索过程以求得最优解。遗传算法操作使用适者生存的原则，在潜在的解决方案种群中逐次产生一个近似最优解的方案，在遗传算法的每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个新的近似解。这个过程导致种群中个体的进化，得到的新个体比原来个体更能适应环境，就像自然界中的改造一样。
遗传算法是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法，是进化算法的一种。这种启发式通常用来生成有用的解决方案来优化和搜索问题。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。
概括来说遗传算法：
遗传算法的基本步骤是：
3-5步是产生新种群的步骤，新群体再进行评估，然后再选择、交叉、变异，一直循环2-5步，最终找到一个近似最优解。遗传算法的流程图如下；
关于遗传算法的进一步解释请参考：经典算法研究系列：七、深入浅出遗传算法（http://blog.csdn.net/v_JULY_v/article/details/6132775）
TSP问题全称旅行商问题（Traveling Salesman Problem，TSP），别名旅行推销员问题、货郎担问题，与哈密顿回路问题有密切联系。且看维基百科的解释：
旅行推销员问题（Travelling Salesman Problem，又称为旅行商问题、货郎担问题、TSP问题）是一个多局部最优的最优化问题：有n个城市，一个推销员要从其中某一个城市出发，唯一走遍所有的城市，再回到他出发的城市，求最短的路线。也即求一个最短的哈密顿回路。
C-TSP问题就是中国旅行商问题（China Traveling Salesman Problem），求解中国34个一线城市的最优路线。给出中国34个城市的经纬度：
| 编号 | 城市名 | 东经 | 北纬 | 编号 | 城市名 | 东经 | 北纬 |
|---|---|---|---|---|---|---|---|
| 1 | 北京 | 116.46 | 39.92 | 18 | 南京 | 118.78 | 32.04 |
| 2 | 天津 | 117.2 | 39.13 | 19 | 合肥 | 117.27 | 31.86 |
| 3 | 上海 | 121.48 | 31.22 | 20 | 杭州 | 120.19 | 30.26 |
| 4 | 重庆 | 106.54 | 29.59 | 21 | 福州 | 119.3 | 26.08 |
| 5 | 拉萨 | 91.11 | 29.97 | 22 | 南昌 | 115.89 | 28.68 |
| 6 | 乌鲁木齐 | 87.68 | 43.77 | 23 | 长沙 | 113 | 28.21 |
| 7 | 银川 | 106.27 | 38.47 | 24 | 武汉 | 114.31 | 30.52 |
| 8 | 呼和浩特 | 111.65 | 40.82 | 25 | 广州 | 113.23 | 23.16 |
| 9 | 南宁 | 108.33 | 22.84 | 26 | 台北 | 121.5 | 25.05 |
| 10 | 哈尔滨 | 126.63 | 45.75 | 27 | 海口 | 110.35 | 20.02 |
| 11 | 长春 | 125.35 | 43.88 | 28 | 兰州 | 103.73 | 36.03 |
| 12 | 沈阳 | 123.38 | 41.8 | 29 | 西安 | 108.95 | 34.27 |
| 13 | 石家庄 | 114.48 | 38.03 | 30 | 成都 | 104.06 | 30.67 |
| 14 | 太原 | 112.53 | 37.87 | 31 | 贵阳 | 106.71 | 26.57 |
| 15 | 西宁 | 101.74 | 36.56 | 32 | 昆明 | 102.73 | 25.04 |
| 16 | 济南 | 117 | 36.65 | 33 | 香港 | 114.1 | 22.2 |
| 17 | 郑州 | 113.6 | 34.76 | 34 | 澳门 | 113.33 | 22.13 |
n个城市的的基因编码方式为：
随机生成m个基因编码序列作为初始种群。
TSP问题中路线越短越好，适应度取值为总距离的倒数，即1/distance。
产生新种群分为选择、交叉和变异。个体被选中的概率取决于该个体的适应度值，比如有5个个体，他们的适应度值为：
| 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| 0.3 | 0.2 | 0.1 | 0.4 | 0.8 |
在[0.0, 1.8)随机产生一个浮点数，如0.8，则4号个体被选中。
随机选择两个个体后，以概率Pc交叉，子代分别继承父母的部分基因，且保持顺序与父代一致，如父代的基因序列：
随机选取Parent1的部分基因，如678，与Parent2交叉，结果如下：
交叉完后就是变异，变异以Pm的概率发生。在TSP问题中因为每个城市只经过一次，所以在变异的时候不能只是改变基因序列中的某一位的值（这会导致一个城市经过两次），应该随机交换两个位置的值，如：
交换了3和8的位置。
参考了用遗传算法解旅行商问题的代码，也是用Python实现的，总共有4个文件：
其中TSP_GA_w.py是在TSP_GA.py增加了一个图形界面，以比较直观地方式来看结果。TSP_GA_w.py和TSP_GA.py任选一个运行即可。
代码已上传在GitHub上，下载地址：https://github.com/chaolongzhang/tsp
GA.py中实现遗传算法的核心代码如下：
def next(self):
"""产生下一代"""
self.judge()
newLives = []
newLives.append(self.best)
while len(newLives) < self.lifeCount:
newLives.append(self.newChild())
self.lives = newLives
self.generation += 1
def judge(self):
"""评估，计算每一个个体的适配值"""
self.bounds = 0.0 #适配值之和，用于选择是计算概率
self.best = self.lives[0] #保存这一代中最好的个体
for life in self.lives:
life.score = self.matchFun(life)
self.bounds += life.score
if self.best.score < life.score:
self.best = life
def newChild(self):
"""产生新后代"""
parent1 = self.getOne()
rate = random.random()
#按概率交叉
if rate < self.croessRate:
#交叉
parent2 = self.getOne()
gene = self.cross(parent1, parent2)
else:
gene = parent1.gene
#按概率突变
rate = random.random()
if rate < self.mutationRate:
gene = self.mutation(gene)
return Life(gene)
def cross(self, parent1, parent2):
"""交叉"""
index1 = random.randint(0, self.geneLenght - 1)
index2 = random.randint(index1, self.geneLenght - 1)
tempGene = parent2.gene[index1:index2] #交叉的基因片段
newGene = []
p1len = 0
for g in parent1.gene:
if p1len == index1:
newGene.extend(tempGene) #插入基因片段
p1len += 1
if g not in tempGene:
newGene.append(g)
p1len += 1
self.crossCount += 1
return newGene以下是运行中的部分截图：
初始情况：
786代的情况：
可以看出，结果比最初情况要好。
趋于稳定的情况：
另一个趋于稳定的情况：
从图中可看出，结果在向最优解发展。
本文在参考前人的基础之上，介绍了遗传算法和TSP问题，并用Python实现了算法。刚接触遗传算法，实现的效果还有很多可以优化的地方。
