北京Ｔ业大学Ｔ学硕十学位论文

ＡＣＳ算法在每次迭代中对信息素浓度要进行局部和全局两次信息素的更新。首先在构造解时，蚂蚁ｋ对其走过的每条路径用下式（２－９）来进行局部信息素的更新。

ＴｇＯ＋１）＝（１一ｐ） ｆ“（ｆ）＋ｐ ｆｏ（２—９）式中Ｐ表示随着时问的推移信息素的挥发系数ｐ∈（ｏ，１）（卜Ｐ可视为残留系数），ｆ。为一很小的常数，实验值为％＝（行－￡。）～，ｎ为城市数目，Ｌ。为到目前为止算法得到的最优解路径，第一次迭代时Ｌ。。为使用最近邻域启发算法产生的一个解的旅行长度。

其次，当每次循环所有的蚂蚁都完成了一次周游后，ＡＣＳ算法对最佳路径上的信息素按式（２－１０）进行全局更新：

％聊＝（１一ｙ） 乃砌＋ｙ △勺（２—１０）瓴＝｛：ｆ‰’警最优解包含路彻艚；

旅行长度（Ｌｂ，，ｔ≤Ｌ。）。（２－１１）参数Ｙ与Ｐ的意义相同，Ｌ‰是到目前为止蚁群寻优得到的全局最优解的

在ＡＣＳ算法中，信息素浓度局部更新的目的是为了避免陷入局部最优，防止信息素浓度过强的边被所有的蚂蚁选择，而全局更新的目的在于奖励属于较短的周游路径，形成正反馈的强化学习机制。ＡＣＳ蚁群算法一方面通过强化状态变迁规则，增强蚁群搜索解路径的多样性，避免早熟现象；另一方面，通过全局信息素的更新，强化正反馈的过程，加速收敛过程。因此，ＡＣＳ算法体现出较好的求解性能。

２．３最大一最小蚂蚁系统

最大一最小蚂蚁系统（即ＭＭＡＳ）是到目前为止解决ＴＳＰ，ＱＡＰ等问题最好的ＡＣ０算法之一。和其他寻优算法相比较，它属于最好的解决方案之一。ＭＭＡＳ算法直接来源于ＡＳ算法，主要作了如下的改进：（１）每次迭代结束后，只有最优解所属路径上的信息素更新，从而更好地利用了历史信息（这与ＡＣＳ算法的调整方案有点类似）：（２）为了避免算法过早收敛于并非全局最优的解，将各条路径可能的信息素浓度限制于［ｆ血，ｆ眦］，超出这个范围的值被强制设为ｆ曲或者是ｆ。。，可以有效地避免某条路径上的信息量远大于其余路径，使得所有的蚂