蚁群算法

简介

属于 群体智能(Swarm Intelligence,SI)

又称 群体智能,群集智能,集群智能

Marco Dorigo 蚁群优化(Ant Colony Optimization)

解决TSP问题(Traveling Salesman Problem)旅行商问题

解决TSP问题

每只蚂蚁根据路径上的信息素和启发式信息(两城市间距离)独立地选择下一座城市:

在时刻t,蚂蚁k从城市 i 转移到城市 j 的概率为

  • 初始时,随机将m只蚂蚁放到n座城市,同时,将每只蚂蚁的禁忌表tabu的第一个元素设置为它所在城市,此时,各路径上信息素量相等
  • 每只蚂蚁根据 路径上 残留的信息素量 和 启发式信息(两城市间距离) 独立选择下一座城市
  • 每有一只蚂蚁经过此路径,就会给此路径带来一个信息素增量 \(\Delta\)
  • 随着时间的流逝(迭代的进行)每条路径上的信息素都在挥发(信息素减少)
    • 一次迭代:当所有蚂蚁完成一次周游(每只蚂蚁都到过了所有城市),此时进行一次信息素(挥发+增量)的更新
    • 每条路径都要进行 信息素更新
    • 当所有城市n座都加入了禁忌表 \(tabu_k\) 时,即蚂蚁k完成了一次周游, 此时 蚂蚁k 所走过路径 便是TSP问题一个可行解
    • 记录每只蚂蚁本次周游路径总长,最终停止时,最短路径总长,即为最优解
  • 每只蚂蚁都有一个禁忌表,记录了这只蚂蚁到过的城市,到过的不会再去,即为禁忌

TSP 问题 表示:一个 N个城市的有向图 \(G = (N, A)\)

其中 \(N = \{1,2,...,n\} \ \ A = \{(i, j)| \ \ i,j \in N \}\)

城市之间距离 \((d_{ij})_{n \times n}\)

目标函数为
\[ f(w) = \sum_{l=1}^n d_{i_{l-1}i_1} \] 其中,\(w=(i_1, i_2, ..., i_n)\) 为城市 \(1,2, ..., n\) 的一个排列, \(i_{n+1} = i_1\)

ACA 求解TSP 两大步骤:

  1. 路径构建
  2. 信息素更新

步骤

0. 公式解析

\(\alpha\) : 信息素重要程度因子,简称信息素因子,是一个信息素的加权值,初始时自己设定,之后不更新,可取 1

\(\beta\) : 启发函数重要程度因子,简称 启发函数因子,又称能见度的加权值,初始时自己设定,之后不更新,可取 2

\(\eta_{ij}(t)\) : 启发函数,蚂蚁从城市 i 到 城市 j 的期望程度,也称能见度

\(allow_k \ (k = 1,2,...,m)\) : 蚂蚁k 待访问城市集合,其实 就是全部城市 和 此蚂蚁的禁忌表 取 差集

\(p_{ij}^k (t)\) : t时刻,蚂蚁k 从城市 i 到城市 j 的概率,t时刻其实就是第t次迭代

\(\tau_{ij}(t)\) : t时刻,城市 i 与 城市 j 连接路径上的信息素浓度

\(p(0 < p < 1)\) :信息素的挥发程度,初始时自己设定,之后不更新,可取 0.5

\(\alpha\):

TODO: 蚁群算法 alpha 详解

\(\beta\) :

TODO: 蚁群算法 beta 详解

1. 城市的选择

启发函数 \(\eta_{ij}(t)\) ,简单起见取: \[ \eta_{ij}(t) = \frac{1}{d_{ij}} \] \(d_{ij}\) 为 城市 i 与 城市 j 连接路径长度

分别计算 当前蚂蚁所在城市 到 可去城市 的概率,使用 轮盘赌算法选择下一个前往城市

PS: 这里利用概率选择城市,也可以使用其他算法,轮盘赌算法只是其中一个选择

2. 信息素更新

信息素的每次更新 是在 每次迭代后进行,完成后 t = t + 1

一次迭代后(所有蚂蚁均周游所有城市一次),信息素更新,各个城市间连接路径上的信息素浓度:

城市 i 与 城市 j 连接路径上信息素浓度 \(\tau_{ij}(t + 1)\)

\(\Delta \tau_{ij}^k\) :第 k 只蚂蚁在 城市 i 与 城市 j 连接路径上释放的 信息素增量,若某只蚂蚁没有经过此路径,则 \(\Delta \tau_{ij}^k = 0\)

\(\Delta \tau_{ij}\) : 所有蚂蚁 在城市 i 与 城市 j 连接路径上释放的信息素增量 总和

PS:其实信息素浓度 = 挥发后的信息素 + 新留下来的信息素

\(\Delta \tau_{ij}^k\) 的计算:

一般 \(\Delta \tau_{ij}^k\) 的值 可由 蚁周模型(an cycle system) 进行计算

\(Q\) 为信息素常数,表示蚂蚁周游一次所释放的信息素总量,初始时自己设定,之后不需要更新,可取 100;

\(L_k\) 为第 k 只蚂蚁本次周游经过路径的总长度

模型:

蚁周模型(Ant-Cycle)

利用的是全局信息,即蚂蚁完成一个循环(周游)后更新所有路径上的信息素

蚁量模型(Ant-Quantity)

局部信息,即蚂蚁 完成一步后更新路径上的信息素

蚁密模型(Ant-Density)

局部信息,即蚂蚁 完成一步后更新路径上的信息素

TODO: 蚁群算法 模型比较

Q&A

补充

参考

感谢帮助!