蚁群算法
简介
属于 群体智能(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 两大步骤:
启发函数 \(\eta_{ij}(t)\) ,简单起见取:
\[ \eta_{ij}(t) = \frac{1}{d_{ij}} \]
\(d_{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
补充
参考
感谢帮助!
蚁群优化算法
就这?蚁群优化算法详解
https://blog.csdn.net/weixin_45690272/article/details/103698475
https://blog.csdn.net/u011125673/article/details/88087479
蚁群算法详解(含例程)
蚁群算法
\[ 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 两大步骤:
-
路径构建
信息素更新
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) = \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:其实信息素浓度 = 挥发后的信息素 + 新留下来的信息素
