artificial-intelligence - 在 MAX-MIN 蚂蚁系统 (MMAS) 中，如果尚未找到初始信息素，它如何依赖于最佳解决方案？

Question

我正在学习如何将最大最小蚂蚁系统添加到我当前的蚂蚁系统中。根据我的阅读，试用信息素初始化为 tMax，tMax 由以下公式计算，

tMax = 1 / best tour length

但是，如果跟踪信息素依赖于尚不存在的游览，那么究竟如何将跟踪信息素初始化为 tMax？

tMin 还取决于 tMax，这也使得在没有最佳解决方案的情况下无法初始化。

Answer 1

在 MMAS 中，所有边都初始化为tauMax，但 tauMax 的定义与您上面所说的略有不同：

tauMax <-- 1 / (rho * bestTourSoFarLength),

其中 rho 是蒸发率（通常设置为 0.5），到目前为止，最好关注游览长度（见下文）。tauMax 在算法执行期间重复更新，每次更新当前最佳游览（到目前为止）。

对于初始化，启发式地构造一个初始可行的旅程。通常，使用随机起始城市的最近邻游览。

回想一下，在蚁群优化 (ACO)/MMAS 等随机优化方法的背景下，我们通常无法证明算法终止时最佳现有解决方案 (tour) 的最优性（然而，我们从实践中知道，ACO/MMAS 确实在某些问题上表现良好，最显着的是旅行商问题 (TSP) 的变体。因此，在诸如此类的上下文中，“最佳解决方案”一词不严格地表示来自不同作者的不同含义；“迄今为止最好的”，“最擅长算法终止”等等，所以在阅读有关该主题的文献时要注意这一点。

最后，作为说明，tauMin 取决于——正如你所指出的——在 tauMax 上，但通常不会在初始化后更新。当施加信息素限制时，重要的“动态”部分是单调递减的 tauMax，而由于蒸发，大多数边缘的信息素最终会以恒定的 tauMin 降落。tauMin 的合适值由可怕的表达式给出（基于经验数据）

tauMin = tauMax*(1-(0.05)^(1/n))/((n/2-1)*(0.05)^(1/n)).