简述
之前通过
遗传算法(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
审稿|威锅
领取专属 10元无门槛券
私享最新 技术干货