几种蚁群算法介绍

蚂蚁系统

最早的蚁群算法，其在小规模TSP中性能尚可，再大规模TSP问题中性能下降，容易停滞。其解决旅行商问题（TSP）过程大致如下：

在初始时刻，m只蚂蚁被随机的放到城市中，在各条路径上的信息素初始值相等。

蚂蚁按照随机比例规则从允许的城市中选择下一个城市：

p_j = \frac{(\tau_j)^\alpha (\eta_j)^\beta}{\sum (\tau_j)^\alpha (\eta_j)^\beta}pj=∑(τj)α(ηj)β(τj)α(ηj)β

τ为信息素，η 为启发式因子，a_k 为下一步被允许城市的集合。

使用禁忌表记录蚂蚁走过的城市，不允许蚂蚁选择已经访问过的城市。

所有蚂蚁完成一次周游后，计算每只蚂蚁的路径长度，保存最短路径长度。

更新每个城市信息素：

τ=(1−ρ)τ+∑Δτ, 0≤ρ≤1

Δτ=1/d

由上可知，先挥发信息素，再增加信息素。其中d为路径距离，路径越短，信息素增加越多。∑Δτ表示所有本次觅食过程中所有经过此城市的觅食成功的路线的信息素累加。

清空禁忌表，开始下一次周游。

精英蚂蚁系统

对算法每次循环之后给予最优路径额外的信息素。

对于普通路径中的每个城市：

τ(t+1)=(1−ρ)τ(t)+∑Δτ

对于最优路径中的每个城市：

τ(t+1)=(1−ρ)τ(t)+∑Δτ+eΔτ^(bs)

Δτ^(bs)=1/L

其中L代表最优路径长度，e是一个参数，表示权值大小。

最大-最小蚂蚁系统

目前解决TSP问题最好的蚁群算法之一，在蚂蚁系统的基础上进行了如下更改：

1. 信息素被限制在[τmin , τmax]。
2. 信息素的初始值被设定为取其上界。
3. 只有最优路径上的信息素会被增加，其他城市的信息素只挥发。

对于一般城市： τ(t+1)=(1−ρ)τ(t)

对于最优路径上的城市：τ(t+1)=(1−ρ)τ(t)+∑Δτ