# 最大最小蚂蚁系统(MAX-Min Ant System,MMAS)
## 1 引言
最大最小蚂蚁系统是基于蚂蚁系统(**AS**)进行改进的产物，由于本文不再赘述关于蚂蚁系统内容，因此读者需先去阅读已完成的[蚂蚁系统](../蚂蚁系统/蚂蚁系统.md)文章。
本文中讨论的 **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)+\De
