信息素规则如何应用于蚁群系统？

Question

我正在回顾Dorigo & Gambardella (1997年)关于蚁群系统(蚁群系统)的论文。信息素更新有两个规则:局部更新和全局更新。然而，我并不清楚应该如何应用每一种方法。

局部更新

据我所知，有三种选择：

1. 更新作为蚂蚁建立一个旅游，即后搬到一个新的城市。(如第56页案文所建议)
2. 在蚂蚁建立了一个旅游之后，在下一个蚂蚁开始之前更新。(如图3第55页所示)
3. 更新后，所有蚂蚁已经建立了一个旅游。(如附录A所述，它将使该算法成为它声称的最可并行的)。

哪一种选择是预定的？

全局更新

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

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

编辑

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

1. 当地更新(蒸发+沉积)，因为每个蚂蚁过渡到一个新的城市(即上面的选项1)。
2. 所有边缘的全局蒸发(如果设置了某些标志，则只关闭城市)。
3. 全球更新(蒸发+沉积)只沿全球最好的旅游。

这更让人困惑，因为它表明蒸发正在发生两倍(甚至三倍)。

Answer 1

聪明算法书(杰森·布朗利著)中提出的旅行商问题蚁群系统的实现是基于Dorigo(1997)论文。根据所包含的代码，信息素更新过程如下：

• 本地信息素更新过程是在Ant构建完解决方案之后触发的。该工艺具有特异的信息素蒸发率，与溶液质量无关。
• 全局信息素更新过程位于迭代结束时，当蚁群中的所有蚂蚁都建立了一个解决方案时。此相以不同的蒸发比工作，它取决于溶液的质量。

在此实现中，信息素更新过程发生在所有蚂蚁及其所有溶液组分(以及相应的信息素矩阵单元)上。我将算法移植到Java中和我得到了接近最优的解，所以提议的过程似乎是可行的。

Answer 2

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

是。

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