蚁群算法
简介
属于 群体智能（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)\) ，简单起见取：\[ \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
补充
参考
感谢帮助！
蚁群优化算法
就这？蚁群优化算法详解
https://blog.csdn.net/weixin_45690272/article/details/103698475
https://blog.csdn.net/u011125673/article/details/88087479
蚁群算法详解（含例程）
蚁群算法