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

imcjp

imcjp 发表于 2013-7-2 00:33
你3opt里应该没调用2opt吧。所以3opt里包含2opt也是必要的。因为，换3个位置的结果，并不一定比换2个位置 ...

还有，这个算法没必要每次迭代都进行信息素挥发操作，因为这一步是O(N^2)的算法。只需要累积200次左右再进行一次信息素的挥发操作，可以使得算法中O(N^2)的操作次数大大减少。这样可以节省很多时间。
由于每只蚂蚁的搜索过程在优化过后是O(N)的，因此当数据一大，刚才的优化就会很明显。
PS：3opt算法优化后也是O(N)的，因为搜索邻域的数量为K。那么复杂度大致为N*K*K

imcjp

灰袍法师 发表于 2013-7-2 00:31
确实是代码有错误，正确的代码要把这里的第三行删掉
Sub regen_pheromone()
Dim u As Long, v As Long, ...

还有邻域搜索时也要优化才能保证是O(N)的复杂度，因为如果遍历donchecked数组的话，最差情况是O(N^2)。应该用链表保存可以被check的点。就不会有一大堆无用的循环了。

imcjp

灰袍法师 发表于 2013-7-2 00:31
确实是代码有错误，正确的代码要把这里的第三行删掉
Sub regen_pheromone()
Dim u As Long, v As Long, ...

我用1000个点测试过，无用循环（donchecked为true时跳过该点）达10W次。而有用循环就1200左右。虽然无用循环单次不占什么时间，但是数据一大，它占的时间将会远远大于有用循环。

zdqwy19

为什么我用你的随机贪婪法最快。

bible20139

感谢分享~~~~~

m199

mark一下，表明我来过看过

zxzxcl

图论里的问题？

zdqwy19

zdqwy19 发表于 2013-8-10 16:55
为什么我用你的随机贪婪法最快。

谢谢点评，我想在cad中使用，连接点

beefox1bear

法师~如果只有城市间的距离，没有坐标。蚁群还能用不？有没个例子我参考一下？

ymbkxc

数学建模中，谢谢分享