学习共享：高级蚁群算法求解1000以上城市的TSP问题（旅行商），附大量TSPLIB数据！

灰袍法师

先提个醒，本帖从最简单的蚁群算法开始，逐步深入增加各种高级技巧，最终做到求解1000个城市的TSP问题，保证不超过最优解的101%。
补充说明：
论坛新人发短消息提问，本人一概不回，有问题请回帖，难道要给你们这些懒人逐个辅导？
回帖的问题太愚蠢的（如跪求源码之类），轻飘飘扔下一句就跑的，也一概不回。


最简单的TSP问题：
给出一组城市的坐标，要求得到一个环游所有城市，最终回到出发点的最短旅行路线。
这个问题跟物流，机器加工头的轨迹优化，空中侦察等等等等都有关系
由于问题很简单易懂，但是又非常难以求解最优解
所以一直是学编程的学生习题, 以及计算机界各种牛人的竞技题目（目前世界记录是求解了8万多城市的最优解）。

蚁群算法，是求解TSP问题的其中一种算法（注：并不是最好的）
跟模拟退火算法，遗传算法等启发式搜索一样，属于每一次搜索都留下统计信息，下一次搜索利用统计信息选择优良的解。
这一类算法的性能其实都差不多。
以上知识点的具体内容请搜索互联网，我不啰嗦了。

附件是一个最简单最原始最慢速优化最差的蚁群算法，算法复杂度是O(n^3)
最好只用于求解50-100的城市数，最好指定至少3000次循环，可以说毫无实用价值，仅供入门学习之用。
最基本的蚁群算法.rar (242.47 KB, 下载次数: 4855)

2012-2-12 19:30 上传

点击文件名下载附件

真正实用的蚁群算法，还必须加上 各种加速技巧 和 强大的邻域搜索算法
邻域搜索跟蚁群算法本身几乎具有同等的重要性，而这一点是绝大多数互联网资源都没有实现，或者实现了也没有提到的关键点，我这里大字强调一下。
光靠蚁群算法本身是很废的，光靠邻域搜索也是很废的，两者相加就非常牛逼了。

附件同时给出一个 Lingo 求解 TSP 的附件，以供对比（需要另装Lingo软件）
附件同时给出一个 非常简单的随机贪婪 算法 求解 TSP，以供对比。（可以看出即使是最简单的蚁群算法，其性能已经超过贪婪法了）

附件同时包括 著名的 TSPLIB 的测试数据，此数据是196x年 到现在，收集的 TSP 问题的测试数据，一般用于跟其它算法，论文的求解结果作比较（大家都用随机数据测试，就没法知道谁更好了，对吧？）
附件同时给出这些测试数据的已知最优解，从而可以判断求解结果跟最优解相差多远。（不然我随便算一个结果，然后自吹自擂也死无对证了。。。）
备注：由于以前的计算机整数运算比浮点运算快得多，所以这些遗留下来的测试数据，其已知最优解是每一段路径都简单四舍五入取整数，然后相加作为结果，跟精确的浮点值存在误差的。
而且，VBA的取整数 round 函数，是四舍六入5看单双，跟简单地四舍五入不一致
所以，可能存在微小的误差（最明显的就是 eil51.tsp 的数据，用不同的四舍五入算出的最优路径是不一样的，426或者427）

书籍：
《Ant Colony Optimization》作者： Marco Dorigo and Thomas Stützle
Marco Dorigo 就是蚁群算法的发明人，这本书详细解释了蚁群算法，各种增强版蚁群算法，各种优化技巧，学习蚁群算法必读！
这本书有中文版，不过现在应该买不到了，而且据说翻译比较差，网上可以下载英文版
网上许多中文论文，都可以发现抄袭这本英文书的地方，有些甚至是连图片一起抄袭。
Ant Colony Optimization 一书的其中两页.rar (98.5 KB, 下载次数: 1441)

2012-2-12 19:33 上传

点击文件名下载附件

Ant Colony Optimization 有邻域搜索的建议参数 for MMAS_ACS.rar (45.45 KB, 下载次数: 1248)

2012-3-4 02:52 上传

点击文件名下载附件

(这一页涉及邻域搜索，在下一节才会详细解释。)
《蚁群算法原理及其应用》 比较有名的中文书，段海滨著，不过我看里面的内容既无系统也不连贯，好多似乎是抄袭的章节，水平不高，语焉不详，没什么价值。不过是中文版，所以。。。。。。
蚁群算法学习包，一个比较著名的下载资源，大部分是抄袭上面两本书的内容，而且其中许多论文连关键问题都没有说清楚，没什么参考价值，作为入门了解概念就好了。
附上其中的两个入门级别的文章。
蚁群算法学习包_里面的两个入门级别的文章_实用价值极低.rar (364.86 KB, 下载次数: 2036)

2012-2-13 02:12 上传

点击文件名下载附件

补充内容 (2013-7-2 07:20):
请查看 159, 160楼 imcjp 指出的程序错漏，虽然对求解结果无大影响，不过。。。还是改一下吧。

liucqa

学习一下         

excelhomeljch

法师好帖,支持支持.最好的是,介绍了相关书籍.

清风_ll

看来比较复杂，做个记号，有时间学习。

灰袍法师

顶楼简单介绍了蚁群算法，TSP问题
以及展示了最简单的蚁群算法求解TSPLIB问题集的性能

我们可以看到，程序虽然比随机求解，以及随机＋贪婪算法都好
但是求解速度仍然非常慢（收敛速度很慢）
尤其是对于大于50城市的求解，即使指定了上万次循环，求解结果仍然不理想，误差往往在5%以上。

以一次求解 eil51.tsp 的结果为例，虽然指定了4000次循环
但是看求解结果的示意图就知道，求解结果存在交叉路径（红圈），而有交叉路径的就肯定不会是最优解，下图的巡游方案，超过最优解1.88%。


所以。。。很自然地，产生了以下优化：
蚁群算法 配合 local search 邻域搜索算法
以下是 2_opt 算法的示意图，来自 顶楼介绍的英文书 《Ant Colony Optimization》作者： Marco Dorigo and Thomas Stützle

算法的目的是做到：任意替换结果方案的两个路径，都不可能比结果方案更优，因此也就不可能存在交叉路径了，真是简单极了。
以下附件程序的做法是：
对于每一个蚂蚁产生的求解结果，都应用一次 2_opt 邻域搜索
2_opt 子过程不断地尝试所有的combin(n,2)个路径，如果替换这两个路径产生更好的结果，就保留结果并且重做整个2_opt，直到仅仅交换两个路径根本无法产生更优结果为止。
最基本的蚁群算法+2opt邻域搜索_求解TSP.rar (75.34 KB, 下载次数: 1625)

2012-2-13 00:08 上传

点击文件名下载附件

附件可以看到，增加了邻域搜索的蚁群算法，性能大为提高
不会浪费成千上万的循环次数在“不好”的路径上面，而是直接搜索“相当好”的路径，优化程度大有提高。
同样以 eil51.tap 为例，只需要 50-200 次循环，就可以达到最优解，而原来的上万次循环都做不到！算法的威力真是可怕吖！

增加了邻域搜索的蚁群算法，简直是如虎添翼，性能完全超越 Lingo 软件。
现在，可以求解200以内规模的TSP问题，求解结果的精度通常不会超过3%。
下图是用50次循环求解 150个城市，chn150.tsp，求解结果只比最优解多 1.61%，只花了226秒啊！（core duo 2.13Ghz）
Lingo软件求解100城市就超过一小时！求解150城市我都没耐心等了。

蚁群算法一开始就是为了解决TSP问题的，而Lingo软件求解TSP问题用的是。。。大家耳熟能详的“分支限界法” branch and bound
这就是 专用算法 vs 通用算法 之间的巨大差距了。
我相信，这个附件已经超越了95% 在CSDN 或者各种中文网站上面的找到的TSP求解器了。嘿嘿嘿。。。

本附件进一步提高求解速度的方法：
使用邻域搜索的一个附带好处是 可以大幅度减少蚂蚁数，同时不会严重影响求解质量
如果采用 灰色单元格 去设定蚂蚁数为1-50之间的数值，而不是默认的 蚂蚁数＝城市数
那么在求解较大规模的TSP时，可以极大提高速度。
如极端地设置蚂蚁数为1，求解 chn150.tsp 将提速150倍！
我实际上设置循环数为100，需4秒钟完成！（core duo 2.13Ghz），离最优解只差2%左右，有时候是1%有时候是3%，完全秒杀Lingo了。
如果设置蚂蚁数为2，循环为200，求解精度会提高到2%以内。
但是更多的蚂蚁，更多的循环，更大的测试规模则没有明显的改善。
唔。。。TSP问题就是这样的，城市数增大，求解最优解的困难程度就飞速上升。。。。。。

onthetrip2008

数学差，看到算法就头痛。本没有资格回帖，不过法师大侠的贴，得顶一顶，从中能学到一丝半点足矣。

灰袍法师

嗯，我在论坛唯一一次碰到真的有人在工作中需要求解TSP问题的
sunsoncheng同学的贴 : 关于线路最短的解法
http://club.excelhome.net/thread-776924-1-1.html
当时我用的就是 随机＋贪婪，似乎结果还不赖。
不过后来我想了一下，结果还好的原因是 sunsoncheng 的要求存在很多 “必须连接的城市”，而且这些必须连接的路径，占总路径的百分比很高
所以就显不出各种算法之间的差距了。

另一个提到TSP的贴是 johncabin 的
使用规划求解，求解TSP问题讨论--改进了算法，轻松求取了140城市的TSP
http://club.excelhome.net/thread-372982-1-1.html
不过他只上传了结果示意图，没有数据没有求解模型没有任何细节，相信不是工作中用到，只是个学生作业而已

CSDN网站倒是很多 TSP 的贴，不过绝大多数都是学生习题的水平，毫无价值。
这也是CSDN网站的一个缺点了，太太太多学生把自己的练习，作业放上去了，真正的好东西非常稀少。

excelhomeljch

excelhome上研究算法的人真的不多.可能许多时候可以用excel自带的方法实现,知道了用这个那个就可以完成,就不用考虑是怎样完成.
个人觉得,学习了算法的思路,不会受到excel变化而变化,甚至于不受语言的影响.这个才是真正属于自己的东西.
有时候,学习了一种算法的思想,在解决其他类型的问题上也会有所得益吧.

灰袍法师

excelhomeljch 发表于 2012-2-14 19:47
excelhome上研究算法的人真的不多.可能许多时候可以用excel自带的方法实现,知道了用这个那个就可以完成,就不 ...

excelhome谈论算法的人很少，因为都是要解决现实的问题而不是在校学习吖。

我的经历跟你很接近
以前我觉得有了Lingo，规划求解这样的东西，什么都搞定了，何必自己学习算法多此一举。
现在嘛。。。原来我可以比Lingo，规划求解，线性规划软件，Matlab之类的现成产品都要好得多。（当然，还是能够不自己动手就最好，又不是搞军备竞赛。）

我在互联网目前只找到两个软件比我的VBA更好
第一个是 Concorde，目前求解TSP问题的世界纪录保持者，不好才怪！
而且此软件的算法是精确算法，也就是说，找到的解必然是最优解！ 非常牛逼。

第二个是 ACOTSP，程序作者就是写 《Ant Colony Optimization》一书的第二作者 Thomas Stutzle，他本人在一计算机科学研究机构当高级研究员的，貌似是他发明了增强版的最大最小蚁群算法。
对500以上的城市，ACOTSP的优化精度比我的VBA要好1%左右，主要是他的邻域搜索算法写的比我强，他用的是3_opt加速版，光是邻域搜索的模块就一千多行代码吖。。。。。。看得我大脑抽筋都没看明白，只好自己另写了，结果就是差一点了。

最牛逼的邻域搜索算法似乎是 LKH，据说用到高达 5_opt，都不敢想象那个代码量有多复杂了，暂时没时间研究了。
其余的各种CSDN中文资源，99.99%都不入我的法眼了，嘿嘿嘿。

中原小农

正在查找关于蚂蚁算法相关的知识，刚入门！谢谢楼主分享资料，非常感谢！看来楼主是一牛人，小弟佩服！{:soso_e179:}
附件是网上一个同学做的关于蚁群算法的入门教程，易于理解，感觉不错！{:soso_e183:}