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

灰袍法师

中原小农 发表于 2012-2-15 11:16
正在查找关于蚂蚁算法相关的知识，刚入门！谢谢楼主分享资料，非常感谢！看来楼主是一牛人，小弟佩服！{:so ...

这位同学的附件不错，说的很详细，是一个很好的入门教程
不过不够深入，而且有些地方明显是抄的其它中文资源
比如对MMAS的论述有很多错误，只是列举一串公式没有提到具体实现，凡是这样的文章通常都是作者自己没学会含糊其辞，要么就是直接抄的
附件应该是抄的，因为 avg 参数的论述完全错误，可见作者根本没有写过MMAS，或者写过但是不会有他声称的增强
（如果同学看中文资料看不懂，很正常，因为很可能是错的。。。。。。）
其实《Ant Colony Optimization》一书就有MMAS详细的实现方法和参数建议。
我现在看到拿 eil51.tsp 作为最终考验，或者求解规模在100以下的，都觉得作者水平低＋多半是抄书郎了，因为只要自己看过《Ant Colony Optimization》，都绝对不止求解100规模的实力。

因为只要有了邻域搜索，求解数百城市都不成问题，根据我的经验，
没有邻域搜索的，100城市以上几乎是绝对求不出最优解，所以100城市是个分水岭（我现在无视这个水平）
2_opt在求解300＋的城市会出现明显精度下降，所以300城市规模也是一个分水岭（我现在轻视这个水平）
3_opt在求解1000＋的城市会出现明显精度下降，所以1000城市规模也是一个分水岭（我现在站在这个水平）
LKH我没学习，据作者说可以直接优化10万城市！！！所以。。。10万城市也是一个分水岭（我现在仰望这个水平）

再次推书：《Ant Colony Optimization》一书里面的内容是很多的，至少还有：
1 各种蚁群算法的详细实现，及其性能比较（我在顶楼贴了性能比较和建议参数这非常重要的两页资料，很多资料都直接引用这两页而不提出处，鄙视。）
2 对算法陷入停滞的检测方法（绝绝大多数网上资源根本不提这一点，或者提到了也是错的，如楼上中原小农的附件，里面说到轮盘赌选择是避免停滞，这一句就是错误的，轮盘赌选择是最基本的蚁群算法的核心实现，目的只是每个路径都有机会被搜索到，跟避免算法停滞没有半点关系。）
3 对算法的加速技巧（应用加速技巧，可以把蚁群算法降低一个阶，变成 O(n^2) 提速几千倍！）
4 更高级的邻域搜索，如 3_opt，k_opt，LKH，绝大多数网上资源根本不提邻域搜索，所以性能一般都很差。
有能力的同学绝对应该直接看《Ant Colony Optimization》，看完就知道所有中文资源都是二手货+太监版（包括我的，呵呵）。

中原小农

小弟刚开始学习，csdn下载的资料还没有看完呢，慢慢理解，再次感谢楼主分享资料！{:soso_e181:}
祝您工作顺利，身体健康！{:soso_e130:}

灰袍法师

前面说到，蚁群算法 ＋ 邻域搜索 ＝ 很好的优化程度
但是，我们发现求解超过200城市规模的TSP问题，还是显得太慢。
在进一步深入优化蚁群算法之前，显然必须先解决速度太慢的问题。

原有的蚁群算法的性能分析如下：
算法复杂度 = O( 循环数 * 蚂蚁数 * 城市数^2 )

在没有邻域搜索辅助的情况下，设城市数 = N
循环数通常需要指定一个很大的数值，假设这个值为T
而蚂蚁数的取值，建议＝城市数，所以每次循环计算所有蚂蚁需要 O(N)
一个蚂蚁的一个方案需要选择N个城市，每次选择需要从 最多N个候选城市中遍历并且计算选择概率，所以建立一个方案是 O(N^2)
所以算法的复杂度 ＝ T * N^3，即 O(T * N^3)
这样的算法复杂度意味着，如果求解10个城市需要0.01秒，那么
求解150个城市就需要 15^3 * 0.01 = 33.75秒！
求解300个城市就需要 30^3 * 0.01 = 270秒！
求解1000个城市就需要 100^3 * 0.01 = 1万秒！
程序耗时随着城市数增大，呈现3次方增长，这显然是无法求解更大规模的问题的。

在使用了邻域搜索以后，我们发现可以大大减少需要的循环数，即T可以降低，但即使忽略不计T这个值，程序仍然是 O(N^3)增长速度，一切还是不变。

采用以下三个技巧，可以把 算法复杂度降低到 O(T * N^2)
头两个加速技巧都基于一个事实： TSP问题最优解的每个城市连接的都必定是附近的城市！
所以在蚂蚁寻路的时候，也只需要尝试附近的几个城市即可，不需要尝试所有的城市！

技巧1 ： candidate list，或者说 Nearest city list
即每个蚂蚁在计算如何选择下一个城市时，只计算距离当前城市距离最近的若干个城市，如果这些距离最近的城市已经走过，那么就放弃蚁群算法的概率选择路径，直接用贪婪法选择可用的最近城市
当然，我们需要预先建立一个“优先城市”的矩阵，以方便查找。

技巧2 ：Fixed radius search
即在邻域搜索的时候，也不需要尝试一个城市跟所有其他城市的连接能否交换出更好的结果，只需要尝试跟最靠近的若干个城市的交换
这两个技巧可以把之前的尝试N个城市，变为尝试指定范围n (n<N)，所以提速 N/n 倍，由于n取值通常是 10-30 ，所以新的算法复杂度跟N无关，而是一个常数，因此新的算法复杂度降低了一个阶，变成 O(T * N^2)。
这样的算法复杂度意味着，如果求解10个城市需要0.01秒，那么
求解150个城市就需要 15^2 * 0.01 = 2.25秒！
求解300个城市就需要 30^2 * 0.01 = 9秒！
求解1000个城市就需要 100^2 * 0.01 = 100秒！

技巧3 ： Don't look bit
原理是：如果该城市跟所有临近城市的路径，都无法交换出更好的结果，那么显然在搜索它的临近城市的时候，也不需要搜索这个城市。
做法是在邻域搜索的时候，给每个城市设置一个标志位，如果城市已经检查过无法交换出更好结果，就设置“不再检查”标志，后续的待查城市在尝试交换的时候就忽略这个城市。
最基本的蚁群算法 2opt 3项加速技巧.rar (84.95 KB, 下载次数: 957)

2012-2-17 05:06 上传

点击文件名下载附件

附件可以看出：
在应用了这三个技巧以后，程序速度极大提高，尤其是城市数量较大的TSP问题。
同样用2个蚂蚁，100次循环，求解 chn150.tsp，之前花了6秒多，现在只花了1.19秒
而求解更大规模的TSP问题，就更明显了。

实际上由于提高了程序速度，就可以把节约的时间花在更多蚂蚁和更多循环次数上，并且多次求解以得到更高精度的结果。
我采用10个蚂蚁，400次循环，求解 chn150.tsp，15秒之内，离最优解差异不超过 1%，多次求解发现最好的一次是 0.06%！
同样地设置去求解 pr299.tsp ，是一分钟之内求解出距离最优解不超过2%的解
至于 eil51.tsp 这样的小规模问题，几秒内就必定找到最优解了！所以我在前帖才毫不客气地说：一切谈论求解 eil51.tsp 的论文，都太低端了，完全不用放在眼里。
以上三个技巧全部来自《Ant Colony Optimization》（这似乎不用我再次强调了吧？呵呵。。。）
如图：

灰袍法师

这一节是介绍五个版本的增强版蚁群算法：
精英蚁群 Elitist Ant System 缩写：EAS
最好最差蚁群 Best_Worst_Ant_System 缩写：BWAS
基于排名的蚁群Rank Based Ant System 缩写：RAS 或者 AS_rank
最大最小蚁群 Max_Min_Ant_System 缩写：MMAS
蚂蚁合作群？（这个中文真不知道怎么翻译好） Ant_Colony_System 缩写：ACS
我把这个内容放在这么靠后的位置，是因为增强版的蚁群算法，单用的性能实际上不如最基本的蚁群算法＋邻域搜索
而且重要性也绝对比不上各种优化技巧的总和。
当然，增强版的蚁群算法＋邻域搜索+优化技巧，必定比上述所有附件都好的多！

先回顾一下基本蚁群算法的原理：
蚂蚁每次走完所有城市，就在走过的路径留下信息素，后续的蚂蚁根据历史信息素的多少来选择要走的路径
如果蚂蚁的环游结果比较好，留下的信息素就比较多，从而使较好路径的被选择机会增加
经过多次循环，就可以逐渐凸现最好的路径。
但是，基本蚁群算法凸现最好路径的速率非常慢（收敛太慢），需要数千，甚至上万次循环才能区分“好”路径跟“坏”路径
增加邻域搜索，可以强迫蚂蚁一定不走任何“有交叉”的路径，从而使好的路径更容易被找到。
增大信息素的蒸发率，也可以迅速使算法收敛，但是却很有可能只搜索了有限的路径，而找不到最优解。
降低信息素的蒸发率，又必定导致算法变慢，而且可选路径非常多，还是很难搜索出最优解。

增强版的蚁群算法，可以帮助算法更快地收敛，还提高求解的精度。
我在顶楼贴出的《Ant Colony Optimization》一书的其中两页，有各种增强版蚁群算法的建议参数，性能比较，必读！
从最简单的说起吧：
1 精英蚁群 Elitist Ant System 缩写：EAS
精英蚁群算法，跟基本蚁群算法几乎是完全一样的，只不过强调了“精英蚂蚁”的作用。
方法是：从所有已经走完环游的蚂蚁中，选择结果最好的蚂蚁，对其走过的路径，留下特别多的信息素
最好的蚂蚁可以选择A：从求解到现在最佳的蚂蚁，或者B：选择本次循环的最佳蚂蚁，效果其实差不多。
A方法的收敛速度快一点，B方法的随机性大一点，对很大规模很多次循环的求解，也许是B方法好一点。
这个增强版最大优点是实现非常简单，而且效果不错。
2 最好最差蚁群 Best_Worst_Ant_System 缩写：BWAS
这个算法几乎跟精英蚁群一样，也是保留一个精英蚂蚁，留下特别多的信息素。
但是增加了“最坏蚂蚁”的惩罚，本次循环的最差蚂蚁，其路径的信息素将多蒸发一次（如果这个路径也被最好蚂蚁走过，则不惩罚）
这个算法的性能只比精英蚁群好一点点。
可以想象，由于惩罚了“坏蚂蚁”，它的收敛速度也会高一点点，找到局部最优解的所需循环数会低一些。
3 基于排名的蚁群Rank Based Ant System 缩写：RAS 或者 AS_rank
这个算法也跟精英蚂蚁一样原理：奖励比较好的蚂蚁。
不同的是，RAS除了奖励最佳蚂蚁，还奖励本次循环的多个蚂蚁，而且按多个蚂蚁的结果优劣，给与不同大小的奖励。
由于多个蚂蚁的随机性比一个蚂蚁强
所以这个算法的收敛性 低于 精英蚂蚁，也就是说，需要更多的循环数才能达到好结果。
但是求解结果比 精英蚂蚁要好一些，尤其是没有邻域搜索的情况下。
4 最大最小蚁群 Max_Min_Ant_System 缩写：MMAS
这个算法是目前性能最好的蚁群算法，发明者就是《Ant Colony Optimization》一书的第二作者 Thomas Stutzle
它的做法是：
1 跟之前所有蚁群算法不同，所有蚂蚁在走完环游之后，都不留信息素！
2 跟精英算法一样，选出最佳蚂蚁，最佳蚂蚁可以留信息素。
3 为了防止所有信息素都被蒸发掉，最后只剩下最佳蚂蚁的路径，MMAS采用很小的蒸发率，从而保证所有路径不会迅速变为0
4 强制所有路径的信息素，有最大值和最小值限制，高于低于这个范围都会被自动设置为最大值或者最小值
从而保证最少信息素的路径也有机会被选择
这个复杂的信息素规则，得到非常好的结果，即使不用邻域搜索，MMAS都可以直接求解出200以内规模的最优解！
非常强悍！
当然，由于蒸发率很低，所以要分出信息素的多和少（即路径的好与坏）
MMAS需要非常多的循环数，不用邻域搜索的话，推荐至少用3000循环。
我在顶楼的两页书，有各种蚁群算法不带邻域搜索时候的性能比较，建议细读。
5 蚂蚁合作群？ Ant_Colony_System 缩写：ACS
ACS算法是个绝对的异类分子。它跟所有其他蚁群算法都大不一样
1 它是唯一一个不带邻域搜索的时候，建议蚂蚁数为10的算法（其余各种增强版算法的建议蚂蚁数都是等于城市数）
所以不带邻域搜索的时候，它的速度是最快的，比其它算法低一个阶，快N倍吖！
2 它是唯一一个边走边改变信息素的算法，而且所有路径的信息素都不蒸发，如果没有蚂蚁走过，就一直不变！
ACS在每个蚂蚁走过某个路径时，该路径的信息素马上进行蒸发，而且所有蚂蚁都不留信息素！
也就是说，蚂蚁走过的路径，信息素不但不增加，而且还减少。
3 只有最佳蚂蚁留下信息素，也就是说最佳蚂蚁走过的路径，信息素才增加。
4 ACS连选择下一个城市的方法都不一样，ACS先固定一个“直接选择最多信息素路径”的概率Q
在每个蚂蚁选择城市的时候，先扔一个随机数，如果随机数低于Q，则直接选择“所有可选路径里面，信息素最多的那一个路径”（注：不一定是最接近的路径）
如果随机数大于Q，则采用基本蚁群算法的选择法，计算所有可选路径的信息素总和，计算每个路径的选择概率，再靠随机数决定选哪一个。
不过可惜的是，这么复杂的规则，其性能却并非最好，比不上MMAS。
另外，ACS的收敛速度虽然很高，但是却不稳定，也需要较多循环才能保证求解精度。
但非常值得一提的是，在没有邻域搜索的时候，ACS的速度是极快的。
现在，增强版的蚁群算法＋邻域搜索，可以保证300以内的城市规模必定找到最优解(MMAS，多次循环＋停滞检测＋多次运行)
而1000以内的城市，求解精度一般不超过最优解的 103%。

另外，邻域搜索的加入，似乎是“抹平”了各种增强版蚁群算法的性能差距，MMAS的性能还是最好的，但优势不是那么明显了。

最后，附件还增加了对蚁群算法陷入停滞的检测方法 check_stagnation
它的做法是：
经过一定循环，如果最佳结果没有变化，则检查算法是否陷入停滞，如果停滞就重置所有路径的信息素
检查停滞是对于每个城市，计算它通往其他城市的所有路径的信息素，求出最大值
如果路径的信息素超过 最大值 * LAMBDA(LAMBDA通常选择一个低数值，0.05或者0.02)，则算作一个有效路径。
如果有效路径低于一定数目，就判定算法陷入停滞，因为所有蚂蚁都在走同一个路线了，再多的循环也不会找到更好的结果。
所以需要对信息素低的路径加强，让它们也有机会被搜索到。
加入停滞检测以后，再也不怕浪费循环和时间了，保证指定更长的循环数，将得到更好的结果。
各种版本的增强蚁群算法+2opt+加速技巧.rar (126.3 KB, 下载次数: 848)

2012-2-19 19:47 上传

点击文件名下载附件

下图是 附件用ACS算法求解 d493.tsp，用2_opt，指定1000次循环，每100次检测一次停滞，求解结果是最优解的 +0.78%，耗时333秒(core duo 2.13Ghz)
注意到：最优解在 658 of 1000，而且 restart = 0，也就是说ACS还没有收敛，如果指定更长的循环数，很可能有更好的结果。
这个就留给大家自己做了，我再运行一次的结果是 Ant_Colony_System +0.36% 最优解出现在1288 of 2000 restart = 7，698.56  秒
到了现在，200以下的小规模TSP问题，已经无法阻止这个VBA程序求出最优解了，而楼顶的基本蚁群算法，甚至不能较精确求解一再被鄙视的 eil51.tsp，算法的深度优化原来可以有这么强，我自己都吓了一跳。

无悔之鑫

楼主应该研究蚁群算法有一段时间了，对于这个很熟悉！    具体程序能否分享一下？  其次楼主主要是以TSP城市的多少及求得最优解的能力评价各种改进的蚁群算法，好像没有提到应用于连续域问题的情况。  不知楼主在连续域这一块是否有深入研究？

eyeshot

占坑学习下

灰袍法师

总算有空再写了，这也许是最后一次更新本帖。
前一节我们看到了 增强的蚁群算法 ＋ 2_opt 可以轻松解决200城市以内的TSP问题的最优解，同时可以求解将近500城市规模的TSP问题。
这一节，我们将再一次提高蚁群算法的求解质量，引入更强大的邻域搜索：3_opt

我们已经知道，2_opt 意味着被优化过的一个环游路线，任意交换此路线的两条路径，都不可能得到更好的结果。
同理，3_opt 意味着被优化过的一个环游路线，任意交换此路线的3条路径，都不可能得到更好的结果。

虽然貌似只是增加了一条路径的变化，实际上我们将会看到，3_opt 实现起来比 2_opt 复杂多了。
因为， 2_opt 优化只会有一种情况，即把两条路径的四个城市端点
a,b,c,f
原路径是 b到c 和 f到a
变换为
b到f，f到c (即逆转f到c的所有路径)，然后是c到a

3_opt 优化，则意味着牵涉到 三条路径的6个城市端点，所有的变换方案多了很多。。。。。。
雪上加霜的是： 3_opt 算法本身是 O(n^3) 复杂度，要用前面说到的加速技巧，才能降低到 O(n^2)，而对六个城市端点应用加速技巧的代码，实在是让人眼花缭乱。

总而言之，三条路径把一个完整的环游路线分成了四个部分
所有可能的变换必须最终能够形成一个完整的环游路线，所以实际上只有三种可能。
（注：有些变换实际上只是 2_opt，所以可以在 3_opt 之前先做一次 2_opt，这样就不需要在 3_opt 的过程中考虑这些变换了)
如下图：




附件程序按照上面两个图，在 3_opt 过程中全部考虑三种变化，并且如果某个变化能够产生更佳结果，就保留，并且重做 3_opt，直到无法优化为止。
理论上，应该考虑三个路径的所有6个城市的先后问题，再根据先后顺序进行变换。
不过我觉得这样搞太复杂了，就干脆只考虑路径1的城市在路径2的城市之前，而路径2的城市又在路径3之前 的情况。
照简单情况做一次 3_opt
然后逆转整个环游方案，再做一次 3_opt
然后把环游方案旋转一个随机值，再做一次 3_opt
这样的做法比较容易理解，不过实际效果却不等于 考虑所有城市先后顺序来调整对应的正确变换，因为我的VBA程序，求解精度总是比 ACOTSP 的结果差一点。

所以追求更好优化结果的筒子，自行阅读 ACOTSP 的C代码去写 3_opt 吧，我反正没看懂。

各种版本的增强蚁群算法+3opt+加速技巧.rar (166.94 KB, 下载次数: 844)

2012-3-4 02:30 上传

点击文件名下载附件

附件的VBA在 core duo 2.13Ghz CPU上，花了一小时求解 pcb1173.tsp，结果比最优解差 0.24%（注意：restart=0意味着蚁群算法没有收敛，指定更多循环次数可以找到更好的解。）
ACOTSP的结果是离最优解差 0.03%，可见我的 3_opt 实现还是有很大问题的。


至此，我已经实现了顶楼的诺言，求解超过 1000 城市的TSP，结果不超过最优解的 101%
当然，更强大的邻域搜索算法，如 ACOTSP 程序的实现，或者目前公认优化极好的 LKH 算法，都肯定可以继续提高。
不过问题是：继续增加城市数量，光是城市的距离矩阵，信息素矩阵这些数组，耗用内存都会以 O(n^2)增长，我的电脑求解 pcb1173.tsp 需要80MB内存。
这么说来，求解9000城市，即8倍城市数，将需要 64*80 = 5120MB内存
我的电脑显然是不可能满足这么多的内存需求，我本人也就在这里停步不前了
实际上我求解过的最大问题是 pcb3038.tsp 得到结果是+1.12%，花了十几个小时，所以没法告诉各位更高的水平是怎么样的了。。。。。。唉。

最后，显然用VBA去解大规模的TSP问题，是很考验耐心的，建议用VB把代码编译出来，可以提速5倍，也就是可以在12分钟完成 pcb1173.tsp 的求解。

AVEL

算法一直都没有时间精力去学习，收藏了法师许多帖子，这个也收藏了。
感谢法师坚持不懈的更新内容。

灰袍法师

AVEL 发表于 2012-3-4 02:55
算法一直都没有时间精力去学习，收藏了法师许多帖子，这个也收藏了。
感谢法师坚持不懈的更新内容。

其实我学习蚁群算法最大的收获是：
以前我以为算法是唯一决定程序性能的，同样的算法将得到差不多的结果，对算法的深度优化是不必要的。

而实际上，原始的蚁群算法，在各种版本的增强＋各种版本的邻域搜索＋各种加速技巧
深度优化后的算法 比 原始算法 提速千百倍，而求解精度也提高至少一个数量级。
这真的令我大吃一惊了。

zjwww

谢谢法师介绍并继续更新蚁群算法的帖子。