ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 效率神器,一键搞定繁琐工作
HR薪酬管理数字化实战 Excel 2021函数公式学习大典 Excel数据透视表实战秘技 打造核心竞争力的职场宝典
让更多数据处理,一键完成 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
用ChatGPT与VBA一键搞定Excel WPS表格从入门到精通 Excel VBA经典代码实践指南
查看: 128941|回复: 209

[原创] 学习共享:高级蚁群算法求解1000以上城市的TSP问题(旅行商),附大量TSPLIB数据!

  [复制链接]

TA的精华主题

TA的得分主题

发表于 2012-2-12 19:28 | 显示全部楼层 |阅读模式
本帖已被收录到知识树中,索引项:
本帖最后由 灰袍法师 于 2012-5-2 14:34 编辑

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

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

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

附件是一个最简单最原始最慢速优化最差的蚁群算法,算法复杂度是O(n^3)
最好只用于求解50-100的城市数,最好指定至少3000次循环,可以说毫无实用价值,仅供入门学习之用。
最基本的蚁群算法.rar (242.47 KB, 下载次数: 4854)
真正实用的蚁群算法,还必须加上 各种加速技巧 和 强大的邻域搜索算法
邻域搜索跟蚁群算法本身几乎具有同等的重要性,而这一点是绝大多数互联网资源都没有实现,或者实现了也没有提到的关键点,我这里大字强调一下。
光靠蚁群算法本身是很废的,光靠邻域搜索也是很废的,两者相加就非常牛逼了。

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









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

评分

16

查看全部评分

TA的精华主题

TA的得分主题

发表于 2012-2-12 20:58 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2012-2-12 22:52 | 显示全部楼层
法师好帖,支持支持.最好的是,介绍了相关书籍.

评分

1

查看全部评分

TA的精华主题

TA的得分主题

发表于 2012-2-12 23:09 | 显示全部楼层
看来比较复杂,做个记号,有时间学习。

TA的精华主题

TA的得分主题

 楼主| 发表于 2012-2-13 00:09 | 显示全部楼层
本帖最后由 灰袍法师 于 2012-2-13 20:17 编辑

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

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

以一次求解 eil51.tsp 的结果为例,虽然指定了4000次循环
但是看求解结果的示意图就知道,求解结果存在交叉路径(红圈),而有交叉路径的就肯定不会是最优解,下图的巡游方案,超过最优解1.88%。
不使用邻域搜索_求解结果存在交叉.jpg

所以。。。很自然地,产生了以下优化:
蚁群算法 配合 local search 邻域搜索算法
以下是 2_opt 算法的示意图,来自 顶楼介绍的英文书 《Ant Colony Optimization》作者: Marco Dorigo and Thomas Stützle
2_opt示意图.jpg
算法的目的是做到:任意替换结果方案的两个路径,都不可能比结果方案更优,因此也就不可能存在交叉路径了,真是简单极了。
以下附件程序的做法是:
对于每一蚂蚁产生的求解结果,都应用一次 2_opt 邻域搜索
2_opt 子过程不断地尝试所有的combin(n,2)个路径,如果替换这两个路径产生更好的结果,就保留结果并且重做整个2_opt,直到仅仅交换两个路径根本无法产生更优结果为止。
最基本的蚁群算法+2opt邻域搜索_求解TSP.rar (75.34 KB, 下载次数: 1625)
附件可以看到,增加了邻域搜索的蚁群算法,性能大为提高
不会浪费成千上万的循环次数在“不好”的路径上面,而是直接搜索“相当好”的路径,优化程度大有提高。
同样以 eil51.tap 为例,只需要 50-200 次循环,就可以达到最优解,而原来的上万次循环都做不到!算法的威力真是可怕吖!
使用邻域搜索_求解结果不可能存在交叉_而且性能提高无数倍.jpg
增加了邻域搜索的蚁群算法,简直是如虎添翼,性能完全超越 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问题就是这样的,城市数增大,求解最优解的困难程度就飞速上升。。。。。。
使用邻域搜索的chn150求解结果_漂亮极了.jpg




点评

送花理由:“我相信,这个附件已经超越了95% 在CSDN 或者各种中文网站上面的找到的TSP求解器了。嘿嘿嘿。。。”,虽然自己不懂……  发表于 2014-11-29 18:18

评分

6

查看全部评分

TA的精华主题

TA的得分主题

发表于 2012-2-14 18:34 | 显示全部楼层
数学差,看到算法就头痛。本没有资格回帖,不过法师大侠的贴,得顶一顶,从中能学到一丝半点足矣。

评分

1

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2012-2-14 19:05 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
本帖最后由 灰袍法师 于 2012-2-14 19:07 编辑

嗯,我在论坛唯一一次碰到真的有人在工作中需要求解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网站的一个缺点了,太太太多学生把自己的练习,作业放上去了,真正的好东西非常稀少。

点评

“这也是CSDN网站的一个缺点了,太太太多学生把自己的练习,作业放上去了,真正的好东西非常稀少。”   法师法眼!!!  发表于 2014-11-29 18:22

TA的精华主题

TA的得分主题

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

TA的精华主题

TA的得分主题

 楼主| 发表于 2012-2-14 20:50 | 显示全部楼层
本帖最后由 灰袍法师 于 2012-2-15 16:16 编辑
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%都不入我的法眼了,嘿嘿嘿。


点评

“大脑抽筋”???只能说明有些东西似我辈就是凭想也是想不到的……  发表于 2014-11-29 22:41
心驰神往,立地成佛。 仰望高山,叹气连连。  发表于 2012-8-25 16:22

评分

1

查看全部评分

TA的精华主题

TA的得分主题

发表于 2012-2-15 11:16 | 显示全部楼层
正在查找关于蚂蚁算法相关的知识,刚入门!谢谢楼主分享资料,非常感谢!看来楼主是一牛人,小弟佩服!{:soso_e179:}
附件是网上一个同学做的关于蚁群算法的入门教程,易于理解,感觉不错!{:soso_e183:}

ant.rar

160.77 KB, 下载次数: 1189

您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2024-11-29 03:49 , Processed in 0.064867 second(s), 10 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

沪公网安备 31011702000001号 沪ICP备11019229号-2

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:李志群律师

快速回复 返回顶部 返回列表