algorithm - 更新蚂蚁信息素问题

Question

我用一只蚂蚁开发了我的蚁群算法，所以它可以找到起点和目标点之间的最短路径。

但是答案的可重复性很差。我在Dorigo书中指出，一只蚂蚁的算法结果很糟糕，所以我正在尝试添加更多的蚂蚁。现在我的主要问题是我应该如何更新轨迹？所有蚂蚁都应该找到目标然后更新通过的边吗？还是每一个找到目标的蚂蚁，算法都应该立即更新轨迹？

Answer 1

为什么要在构建完整路径后更新信息素：

当您构建路径时，在每次迭代中您都添加了一个可用顶点，这是一个尚未添加到路径中的顶点。只有在构建完整路径后才能确定路径的值，并且在某些情况下，一些看起来很有希望的部分路径可能会导致您进入“陷阱”（当您稍后必须添加非常长的边时）路径构建的阶段），并最终导致非常糟糕的结果。

更重要的是，我建议您仅在整整一代蚂蚁构建完完整路径后才更新信息素。

为什么？因为您使用的是概率模型，并且正在构建的路径受到 2 个参数的影响：信息素和“启发式”参数（即边缘的长度）。当您启动算法时，所有边都具有相同的信息素水平，并且蚂蚁以“贪婪”的方式行事，这意味着它们倾向于选择较短的可用边（这些边可能会在以后的迭代中被丢弃，因为它们会导致坏结果）。如果每只蚂蚁在完成后都会立即更新信息素，那么您就有更大的机会达到早期停滞并找到局部最小值，并且您不会给蚂蚁一个探索更广泛的搜索空间区域并变得更聪明的好机会. 保存每次迭代中所有蚂蚁的列表，让它们都构造一条路径，

这也是为什么您不应该在每次迭代中只使用一只蚂蚁的原因。因为你会得到类似的结果。我建议你将你的“计算能力”更平均地分配在每一代蚂蚁的数量和代数之间（例如，100 只蚂蚁在一次迭代中，100 次迭代）。

我相信，如果您应用此逻辑，您将获得预期的结果。

Answer 2

当您需要可重复性时，蚁群优化针对速度进行了优化，您可以使用 k2 或 k3-opt 算法优化结果。当您想要更快的速度时，请寻找动态解决方案。我可以从 gebweb 推荐 optimap javascript。它还具有蚁群优化器和 k2 和 k3-opt 算法以及 tsp 问题或开放 tsp 问题的动态解决方案。还有一个带有可用前端的网页。