蚁群算法

作者: ZhSong | 来源:发表于2020-04-16 18:01 被阅读0次

TSP解决之道——蚁群算法
蚁群算法简单介绍
蚁群算法
蚁群算法
蚁群算法
蚁群算法
TSP问题—蚁群算法(ACO)
awesome 蚁群算法
蚁群算法aoc
蚁群算法代码

蚁群可以在不同的环境下，寻找到达实物源的最短路径。这是因为蚁群内的蚂蚁可以通过某种信息机制实现信息的传递。这种信息机制就是在蚂蚁走过的路径上，会留下”信息素“，而这些信息素就形成了一种正反馈的机制，当然信息素会随着时间的流逝，逐渐消失。这种正反馈会最终帮助蚁群找到一条到达实物源的路径。利用这种机制，就可以找到图结构中的最短路径。

蚁群系统的模型

包含的元素：

图
图中的结点，初始结点和目标结点
智慧的蚂蚁
信息素 $\tau$ (在图结构中体现为边上的数字)

蚂蚁是如何在一个分叉口做选择的呢？

选择某一条路的可能性 = 这条路上的信息素数量/所有可能路线上的信息素数量的总和

蚂蚁是如何在更新信息素数量的呢？
$\tau(e) = \left\{ \begin{array}{**lr**} (1-\rho)\cdot \tau(e) \ \ \ 如果该路径没有被走过 & \\ (1-\rho)\cdot \tau(e) + 新的信息素 \ 如果该路径被走过 & \end{array} \right.$
在公式中：

$\rho, 0\le \rho \le1$ 是蒸发率，也就是信息素消失的速率

$\tau(e)$ 是在路径 $e$ 上的信息素总量

如果蚂可以记住已经走过的路，那么就会根据下面这个公式选择：
$选择某一条路径的可能性 = \left\{ \begin{aligned} &0 ，如果这条路已经走过\\ & 当前路径的信息素/所有不存在于已经走过的路的信息素之和，如果这条路还没走过\\ \end{aligned} \right.$
如果蚂蚁可以记住已经走过的路径，而且还能知道没走过的路的路径长度，那么就会根据下面这个公式选择
$选择某一条路径的可能性 = \left\{ \begin{aligned} &0 ，如果这条路已经走过\\ & \frac{[\tau(e)]^\alpha\cdot[\eta(e)]^\beta}{\sum_{e' = (u,v'),v'\notin M_k}[\tau(e')]^\alpha\cdot[\eta(e')]^\beta} \\ \end{aligned} \right.$
$\tau(e)$ 是某条路径上的信息素总数