蚂蚁系统在求解一些小规模TSP问题时，表现尚令人满意。但随着问题规模的扩大，蚂蚁系统很难在可接受的循环次数内找到最优解。针对蚂蚁系统的不足，Dorigo和Gambardella（1997）在蚂蚁系统的基础上提出了蚁群系统（ant colony system，ACS）。
蚁群系统的基本思想是将m只蚂蚁按照一定的初始化规则放置于n个顶点上。每一只蚂蚁通过状态转移规则逐步构造一条哈密尔顿回路。在构造回路的过程中，每一只蚂蚁通过局部更新规则对自己经过的边进行信息素更新。当所有的蚂蚁都完成遍历之后，再对最佳回路上的边进行信息素全局更新。
蚁群系统的伪代码如下所示：
蚁群系统与蚂蚁系统的区别主要有三点（Dorigo and Gambardella，1997）：
（1）蚁群系统的状态转移规则尝试在探索（exploration）和利用（exploitation）上取得平衡，蚂蚁k在顶点a选择下一个顶点b时采用如下的伪随机比例规则（pseudo-random-proportional rule）：
其中，q为[0，1]区间内服从均匀分布的随机数，q0为设定的系数，0<q0<1；b*为根据式（8.1）确定的后续顶点。
伪随机比例规则仍然倾向于选择信息素浓度较高且边长较短的边。但是，新引入的系数q0决定了蚁群探索和利用的相对比例：当随机数q大于q0时，伪随机比例规则采用式（8.1）的随机比例规则探索周边顶点；而当随机数q小于q0时，伪随机比例规则确定性地选择相邻的最好边，即式（8.7）中arg（）所得的最好边。
（2）全局更新规则只作用于最好回路上的边。在所有蚂蚁完成遍历后，对最短哈密尔顿回路上的边应用如下的更新规则：
其中，信息素增量为：
其中，H*为当前蚁群找到的最短哈密尔顿回路，min{H}是目前为止所有蚁群找到的最短哈密尔顿回路的长度。(www.xing528.com)
通过式（8.8）所定义的全局更新规则，蚁群系统进一步强化了最佳回路上的信息素浓度，从而引导后续蚁群的搜索方向。可见，伪随机比例规则和信息素全局更新规则都尝试指导蚁群的搜索过程更快地指向最优解。
（3）人工蚂蚁在构造哈密尔顿回路的过程中，应用局部信息素更新规则：
其中，θ为信息素衰减系数，而信息素增量则可以采用如下的三种公式进行计算（Dorigo and Gambardella，1997）：
第一种是Q-learning方法（Gambardella and Dorigo，1995）：
其中，参数γ∈[0，1）。采用这种方法的蚁群系统也被称为Ant-Q算法。
第二种方法设定信息素增量取信息素浓度初始值：
第三种方法则将信息素增量设定为0：
Dorigo和Gambardella（1997）在TSP算例库上的计算测试表明，局部更新规则有助于提高蚁群系统的算法效率，相对而言，式（8.13）定义的第三种方法效果最差。由于采用第一或第二两种方法的蚁群系统算法效率相近，而第二种方法的计算量较小，因此蚁群系统一般都采用第二种方法。通常所说的蚁群系统（ACS），即指采用第二种局部更新规则的蚁群系统。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
