遗传算法解决TSP问题 Python实现160行以内代码

简述

之前通过

遗传算法（Genetic Algorithm ）+C++实现解决TSP问题

写了一些基本的原理。并且给出了C++版本代码。

相比于近300行的C++程序，Python只用了160行就解决了 可以说是非常方便了~

概念

三个生成过程

select 自然选择

crossover 交叉（交配）

mutation 变异

把每个数据想象成染色体，然后从染色体到人的映射就是object function，也就是这里的适应函数。

当然可以映射到更深的程度，比如考虑人的身高之类的（可以被量化的东西）

染色体 这样的比喻，会很容易理解crossover这个步骤。

变异这个也很好理解，避免进入到局部极小值，被控制住了。

自然选择，这个根据evolutionary theory，也很容易理解

简单遗传算法框架

一般终止条件是：过了很久最优的适应值都不发生变化

整数编码问题

因为如果是二进制编码的话，会简单很多，这里就不讲了。

难点其实还是在整数编码上。

整数编码（简单的实例）：

(有些问题不是排序的问题，就可以类似于之前的二进制来实现)

对于父母分别是 0 到 9整数的排序【加上长度均为10】：

要求子代也必须是这样的排序。

自然选择：不会产生子代，只是筛选子代，所以不受这个问题影响

交叉（crossover）：会产生子代。这里只考虑排序时候的情况

基于次序的交配法：在父代1找到几个位置，之后，找到这些数字在父代2的位置。并删除（用空白填充）。之后这些空白按照父代1的中这些数字的顺序排好。（非常简单的方法）

基于位置的交配法：在父代1找到几个位置，父代2的数值直接替代上去，只会，冲突的位置（不在之前选的位置上冲突的位置），按顺序从父代1替代。

部分映射的交配法：任意选两个位置，在父代1,2直接这两个位置之间的序列构建序列对。然后，按照这样的序列对的映射方式，在父代1或者父代2上做映射交换。就可以得到子代1或子代2。

变异（mutation）：会产生子代。

基于位置的变异：随机产生两个变异位，然后将第二个变异位上的基因移动到第一个变异位之前。

基于次序的变异：随机的产生两个变异位，然后交换这两个变异位上的基因。

打乱变异：随机寻去染色体上的一段，然后打乱在该段内的基因次序。逆序交换方式是打乱变异的一个特例。

TSP问题

TSP，是货郎担问题，也就是中国邮递员问题（少数世界级问问题，用中国人命名的问题hhh）。

就是n个点直接连通需要不同的代价，如果想要找到不重复的经历完所有点，然后在回到初始点的用的代价最小。

内容如下

基于之前的C++版本的Python版本代码

所用的数据：

表示是的10个点之间的距离矩阵

随机生成数据并展示动图

黑色的点是起点。

我在知乎上看到类似的图，就试着改了下自己的代码也实现了这个效果。生成gif是基于我之前写的代码

排版|Shane

作者|Sean

审稿|威锅