用遗传算法解旅行商问题(Python 版)

旅行商问题(Travelling Salesman Problem,即TSP问题)是数学领域中著名问题之一。假设有一个旅行商人要拜访 n 个城市,他必须选择所要走的路径,路经的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

TSP 问题是一个组合优化问题,也是一个 NP 完全问题,使用通常的解法往往需要耗费大量的时间,不过我们也可以使用遗传算法,在较短的时间里找到一个可接受(不一定是最优)的解。

下面是我的代码,一共有三个文件,分别为 TSP.pyGA.pyLife.py

注:代码已迁移至:
https://gist.github.com/oldj/3c3268f875b5969e5b9c0fe33d463a85

运行 TSP.py,即可开始程序。几个快捷键说明如下:

  • n 开始新的计算(随机产生32个新的城市)
  • e 开始进化
  • s 停止
  • q 退出

程序没有设置终止进化条件,进化一旦开始,如果不手动停止,会一直计算下去。

遗传算法主要是一种思想,并没有很具体的代码,在解决大多数问题时,最难解决的部分主要是编码(如何将问题转化为合适的方便操作的“基因”)、评价(如何评价各个“基因”的得分)部分。在本例中,我们将城市的顺序做为基因编码,路径总长度的倒数为基因的得分。这种做法不一定是最好的,不过是有效的。

下面是我运行时的一次截图:

初始状态

初始状态。

第153代

第153代。

第624代

第624代,可以看到,已经比初始状态好多了。

第2331代

第2331代,除了下方有一些交叉外,已经基本差不多了。

第3710代

第3710代,完成。

【2018-01-30 更新】:JavaScript 版遗传算法求解旅行商问题

分类:编程标签:遗传算法算法Python
野有蔓草

相关文章:

评论:

CFC4N

我靠,我觉得算法什么的,都太高端了,我看到就头大。 向博主学习。

joegh

用可视化的方法展现算法迭代寻找局部最优解的过程,很赞!

DL

问下楼主,运行之后只有初始的第一代,在命令行里打n s 都不管用。想看不同代的结果应该是怎么操作,谢谢。

oldj

有没有按“e”呢?要按“e”才会开始进化。

是人参果

请问博主如果用matlab写这个程序也有这么好的运算结果吗?

oldj

不会matlab,不知道呢... -_-!

是人参果

怎么可能?c++比matlab难上一万倍,你都这么精通。呜呜,其实是我不会用matlab写遗传算法啦,求拜师!

oldj

囧囧,这个程序其实是用Python写的… :)

是人参果

额。。。c++都不是啊。难怪我好多地方看不懂。

是人参果

大牛,请教个问题额,上面那个例子运算时间是多少啊?

oldj

跑了有好几分钟吧。

发表评论: