algorithm - 更新 Ant 信息素问题

Question

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

但答案的可重复性很差。我已经红了 Dorigo预订一只 Ant 的算法结果不好，所以我试图添加更多的 Ant 。现在我的主要问题是我应该如何更新路径？所有的 Ant 都应该找到目标然后更新传递的边吗？或者每只找到目标的 Ant ，算法都应该立即更新轨迹？

Answer 1

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

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

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

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

这也是您不应该在每次迭代中只使用一只 Ant 的原因。因为你会得到类似的结果。我建议你将你的“计算能力”更均匀地分配给每一代 Ant 的数量和世代的数量(例如，100 只 Ant 在一个迭代中，100 次迭代)。

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