更新蚂蚁信息素问题

Question

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

但是答案的可重复性很差。我在Dorigo的书中写道，只有一只蚂蚁的算法结果不好，所以我试图添加更多的蚂蚁。现在我的主要问题是我应该如何更新跟踪？是否所有的蚂蚁都应该找到目标，然后更新通过的边？或者每只找到目标的蚂蚁，算法都应该立即更新轨迹？

Answer 1

为什么你应该在构建完整路径后更新你的信息素：

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

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

为什么？因为您使用的是概率模型，而正在构建的路径受两个参数的影响:信息素和“启发式”参数(即边的长度)。当你启动算法时，所有的边都有相同的信息素水平，蚂蚁以“贪婪”的方式行动，这意味着它们倾向于选择较短的可用边(这些边可能会在以后的迭代中被丢弃，因为它们会导致糟糕的结果)。如果每只蚂蚁在完成后都会更新信息素，你就有更大的机会达到早期停滞并找到局部最小值，而你不会给蚂蚁一个更好的机会去探索更广泛的搜索空间并变得更聪明。在每次迭代中保存所有蚂蚁的列表，让所有蚂蚁构建一条路径，然后让每个蚂蚁存放信息素(通过这种方式，你还可以应用“排名”方法，这意味着存放的信息素的数量将由蚂蚁在迭代中的排名决定，而不是解值，这有时有助于区分接近最优的解)。

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

我相信，如果你应用这个逻辑，你会得到预期的结果。

Answer 2

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