1

我正在审查Dorigo & Gambardella (1997)关于蚁群系统 (ACS) 的论文。信息素更新规则有两种：局部更新和全局更新。但是，我并不清楚每个应该如何应用。

本地更新

据我所知，有3个选项：

  1. 更新为蚂蚁建立一个旅游，即移动到一个新的城市之后。（正如第 56 页的文字所建议的那样）
  2. 在一只蚂蚁建立游览后更新，在下一只蚂蚁开始之前。（如第 55 页图 3 所示）
  3. 在所有蚂蚁都建立了游览之后更新。（如附录 A 中指定的那样，将使该算法像它声称的那样最可并行化）。

哪个选项是预期的？

全局更新

从文本（等式 4，第 56 页）和附录中也不清楚更新规则的信息素蒸发部分是否适用于所有边缘或仅适用于全球最佳游览上的边缘。

在全局更​​新规则下，所有边都会蒸发吗？

编辑

从那以后，我发现这个GitHub 存储库似乎包含 Dorigo 的原始代码，其中似乎发生了以下规则：

  1. 当每只蚂蚁过渡到一个新城市时，本地更新（蒸发+沉积）（即上面的选项1）。
  2. 所有边缘的全球蒸发（或仅在设置某些标志的情况下关闭城市）。
  3. 仅沿全球最佳巡回赛进行全球更新（蒸发+沉积）。

这更令人困惑，因为它表明正在发生双重（甚至三重）蒸发。

4

2 回答 2

1

Clever Algorithms 一书（Jason Brownlee 撰写）中提出的针对旅行推销员问题的 Ant Colony System 的实现声称基于 Dorigo（1997）论文。根据包含的代码，信息素更新过程如下：

  • 本地信息素更新过程在 Ant 完成构建解决方案后触发。这个过程有一个特定的信息素蒸发率，它不依赖于溶液质量。
  • 全局信息素更新过程位于迭代的最后，此时蚁群的所有蚂蚁都建立了一个解决方案。此阶段使用不同的蒸发率，它取决于溶液的质量。

在此实现中，信息素更新过程发生在所有蚂蚁及其所有解决方案组件（以及相应的信息素矩阵单元）上。我将算法移植到 Java并获得了接近最优的解决方案，因此建议的过程似乎有效。

于 2016-04-01T21:44:57.413 回答
1

在全局更​​新规则下，所有边都会蒸发吗？

是的。

这个想法是，更多蚂蚁走的路径（短路径）将有更多的信息素，因此将被更多的蚂蚁走，最终每只蚂蚁都只会走那条路。所以，一段时间后，信息素会蒸发（就像在自然过程中一样），所以你必须通过减少信息素含量来模拟蒸发。

于 2016-03-28T12:11:33.233 回答