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

ssn_h

好强大啊，虚心学习了

568133431

不错，很好的学习材料

飘飞的絮

法师有没有考虑过结合遗传算法和蚁群算法来解决TSP问题啊，能不能给些建议

840205910

灰袍法师，你好！恳请你帮忙，能不能解决板材的最少用量问题？谢谢！http://club.excelhome.net/thread-954035-1-1.html

vikin

马克一下，供以后用

哲小

我更新了 Tomas 的 acotsp， 所有1000 以下城市 全部得到了最优解，并且 dsj1000.tsp 超过了 tsplib 中给出的结果。  其中100 以下的城市 蚂蚁数量30， 一次迭代即可达到最优， 100 - 300 之间的城市 迭代次数不超过30次。 有些得到最优 比较难 例如 d657 用了200多次迭代 rat575 300多次。 不过总体来说 已经超越了 其他现有期刊中的蚁群算法

哲小

跑1000 以上的 我改近后的 acotsp 要反复测量多次 才能达到最优 部分 求不到最优， 而且非常耗时， 一次设定1000次循环 60 只蚂蚁， 要5分钟才能跑完（实验室机器 32g ram）。 1000 以上 确实是瓶颈

哲小

法师，10万个城市的 需要很大ram， 我实验室 32g ram的 超级 电脑 用改过的acotsp 只能跑动 20000个城市的 再多 就溢出了。 Lin- Kernighan 则不同， 那个算法初始路径 是用 nearest neighbor 生成的  然后通过local search 也就是 k-opt 不断的替换，基本不需要存储 像aco 那么大的信息量。 所以 可以求解10万+城市

哲小

目前文章还未发表 正在修改 所以不能拿出来分享。
许多国内发表的文章 关于蚁群的，所有文章中提到 超过了tsplib里的最优解的， 其实 都是round off 的误差。 例如 《求解tsp问题的改进模拟退火遗传算法》王银年 葛宏伟， 中声称超越了 pr144 的最优解， 其实不过是 round off 的误差， 用concorde 解 pr144 生成的图形 和 此文一致。 还有诸多类似情况。

灰袍法师

哲小 发表于 2012-12-14 15:43
法师，10万个城市的 需要很大ram， 我实验室 32g ram的 超级 电脑 用改过的acotsp 只能跑动 20000个城市的  ...

是的，1000以上的城市，这里讨论的蚁群算法求解是比较困难的
还是要继续增强的
目前本帖以老兄你的境界最高了，哈哈哈。
世界记录保持者 Concorde 软件，其作者 David Applegate 也有一些求解TSP的论文
我写本帖的时候因为决定了用蚁群算法，所以就没有管他的，你也许可以参考一下。