最大最小蚂蚁系统.md

最大最小蚂蚁系统(MAX-Min Ant System,MMAS)

1 引言

最大最小蚂蚁系统是基于蚂蚁系统(AS)进行改进的产物，由于本文不再赘述关于蚂蚁系统内容，因此读者需先去阅读已完成的蚂蚁系统文章。

本文中讨论的 MAX-MIN Ant System (MMAS) 算法通过仅允许最佳解决方案在信息素轨迹更新期间添加信息素，实现了对搜索历史的强大利用。 此外，使用相当简单的机制来限制信息素轨迹的强度有效地避免了搜索的过早收敛。 最后，MMAS 可以通过添加本地搜索算法轻松扩展。

文中主要测试领域：

• 旅行商问题
• 二次分配问题

需要指出以下问题：

1. 因本文是基于AS改进，因此在描述基本算法时以AS为准
2. 在本文中关于AS的某些描述存在不一致，本人以AS原文描述为准
3. 若与本文参考文献存在冲突，请以参考文献为主

下面直接进入主题。

2 最大最小蚂蚁系统(MMAS)

对 ACO(包括蚂蚁系统、蚁群系统、精华蚂蚁系统、基于排列的蚂蚁系统) 的研究表明，可以通过对搜索过程中找到的最佳解决方案的更强利用来提高性能。 然而，使用更贪婪的搜索可能会加剧搜索过早停滞的问题。 因此，实现 ACO 算法最佳性能的关键是将搜索过程中发现的最佳解决方案的改进利用与避免早期搜索停滞的有效机制相结合。最大最小蚂蚁系统($MMAS$)专为满足这些要求而开发，在三个关键方面与 AS 不同:

• 1. 为了利用在迭代期间或算法运行期间找到的最佳解决方案，在每次迭代之后只有一只蚂蚁添加信息素。 该蚂蚁可能是在当前迭代中找到最佳解决方案的蚂蚁（迭代-最佳蚂蚁），也可能是从试验开始就找到最佳解决方案的蚂蚁（全局最佳蚂蚁）。
• 2. 为了避免搜索停滞，每个解决方案组件上可能的信息素踪迹的范围被限制在一个区间 $[τ_{min},τ_{max}]$。
• 3. 此外，将信息素轨迹初始化为 $τ_{max}$，以这种方式在算法开始时实现对解决方案的更高探索。

2.1 信息素轨迹更新

在 MMAS 中，每次迭代后仅使用一只蚂蚁来更新信息素轨迹。 因此，修改后的信息素踪迹更新规则如公式(1)所示：

$$ \tau_{ij}(t+1)=\rho \tau_{ij}(t)+\Delta\tau_{ij}^{best}\tag{1} $$

该更新方式和蚁群系统($ACS$)基本一致，不过在$\Delta\tau_{ij}^{best}$少了一个常数系数，另外，在$ACS$中，虽然只对最优路径增加信息素，但对于其他路径，信息素蒸发是一样执行的。其中 $\Delta\tau_{ij}^{best} = \frac{1}{f(s^{best})}$ ，其中 $s^{best}$ 可以选择当前迭代最优路径长度 $s_{ib}$或迭代至目前位置最优路径长度 $s_{gb}$。即在$MMAS$中，只更新当前最优的路径信息素。

仅使用 $s_{ib}$或 $s_{gb}$一种解决方案进行信息素更新是 $MMAS$中搜索利用的最重要手段。通过这种选择，经常出现在最佳解决方案中的解决方案元素得到了很大的加强。尽管如此，在用于更新信息素轨迹的迭代最佳和全局最佳蚂蚁之间的不同更新方式控制着搜索历史的利用方式。

• 当仅使用 $s_{gb}$时，搜索可能会过快地集中在此解决方案上，并且对可能更好的解决方案的探索受到限制，从而有陷入劣质解决方案的危险。
• 当为信息素轨迹更新选择 $s_{ib}$时，这种危险会降低，因为迭代最佳解决方案可能因迭代而异，并且大量的解决方案组件可能会偶尔得到强化。
• 使用混合策略，例如选择 $s_{ib}$作为更新信息素的默认值，并且仅在每固定次数的迭代中使用 $s_{gb}$。

在作者的测试结果中，最好的策略似乎是使用动态混合策略，这增加了信息素使用$s_{gb}$的频率在搜索期间更新。

2.2 信息素限制

在单独使用信息素轨迹更新方式时，算法在迭代一定次数后便会陷入停滞状态。

显然，应该避免这种停滞的情况。实现这一点的一种方法是扰动选择下一个解决方案组件的概率，这直接取决于信息素轨迹和启发式信息。

在整个算法运行过程中，启发式信息通常与问题相关并且是静态的。但是通过限制信息素轨迹的影响，可以很容易地避免在算法运行期间信息素轨迹之间的相对差异变得过于极端。为了实现这一目标，$MMAS$对最小和最大信息素轨迹施加了明确的限制 $τ_{min}$ 和 $τ_{max}$，这样对于所有信息素轨迹 $τ_{ij} (t)$，$τ_{min} ≤ τ_{ij} (t) ≤ τ_{max}$。每次迭代后，必须确保信息素踪迹遵守限制。如果我们有 $τ_{ij} (t)>τ_{max}$,则设置 $τ_{ij} (t) = τ_{max}$;类似地，如果 $τ_{ij} (t)<τ_{min}$,则设置$τ_{ij} (t) = τ_{min}$。

在设置 $\tau_{min}、\tau_{max}$过程中，需要注意$\tau_{min}$应该大于0，同时 $\tau_{max}$不能过大。

在文章中，对 $τ_{max}$ 的由来做了比较多的描述，但是简单来说，$τ_{max}$是根据公式 (2) 动态取值的。

$$ \tau_{max}=\frac{1}{(1-\rho)}\frac{1}{f(s^{opt})}\tag{2} $$

其中 $f(s^{opt})$为每次迭代的最短路径，即该值是动态改变的，$\rho$为信息素蒸发系数。在这里需要提醒，$τ_{max}$一开始并不需要，在一次迭代产生最短路径之后才会随之初始化。

为了确定$τ_{min}$的合理值，作者使用以下假设：

• 在搜索停滞发生前不久找到最佳解决方案。 在这种情况下，在一次算法迭代中重建全局最佳解决方案的概率明显高于零。 可能会在找到的最佳解决方案附近找到更好的解决方案。
• 对解决方案构建的主要影响是由信息素轨迹上下限的相对差异决定的，而不是由启发式信息的相对差异决定的。

上面假设对于了解算法实现用处并不是很大，下面直接给出$\tau_{min}$计算公式：

$$ \tau_{min}=\frac{\tau_{max}(1-\sqrt[n]{P_{best}})}{(avg-1)\sqrt[n]{P_{best}}}\tag{3} $$

其中$avg$计算公式如下：

$$ avg=\frac{n}{2}\tag{4} $$

其中对于$n$描述并不明确，在参数设置时提到$m=n$，且$m$为蚂蚁数量，那么，这里的$n$应该与蚂蚁数量相同。

个人猜想，$n$应该代表城市数目，作者指的是蚂蚁数目必须等于城市数目

2.3 信息素轨迹初始化

从上面的分析可得出，无论是信息素下限$\tau_{min}$还是信息素上限$\tau_{max}$都是经过算法一次迭代运行之后才可得到。

因此，在信息素初始化阶段，可以对信息素进行统一初始化一个足够小的值。这对算法后续运行的影响并不大！

2.4 参数设置

• β = 2
• α = 1
• m = n，其中 m 是蚂蚁的数量
• ρ = 0.98
• pbest = 0.05

在$MMAS$中，运行机制稍微与$ACS$不一致。作者提出，$MMAS$还需要自身去维护一个候选列表，该列表包含各城市最近邻居的非递减排序，即需要维护一个大小为$蚂蚁数目\times城市数目\times 20$的三维空间矩阵。当对应城市候选列表全部被选完之时，才从对应城市候选列表之外的城市进行选择。

对于候选列表，个人感觉有以下问题，首先它固定为20，当总城市数目不足二十，那么肯定就需要进行修改的；其次蚁群算法本身就是通过蚁群合作的正反馈进行合作并最终找到最短路径，通过人为的给出对应城市邻近20座城市的候选列表来使算法更加容易找到最短路径，该思想是否回到了贪婪式方法，且对于算法性能是否有足够的提升呢？

3 代码实现

该文代码实现情况如下：

• 在实现代码时并未采取候选列表的形式
• 代码中，按照$m=n$，即城市数目等于蚂蚁数目

4 参考文献

[1]Stützle T, Hoos H H. MAX–MIN ant system[J]. Future generation computer systems, 2000, 16(8): 889-914.