遗传算法解决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

审稿|威锅

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181218G1KW9B00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券