【经典算法】有趣的算法之---蚁群算法梳理

every blog every motto: You can do more than you think.

0. 前言

蚁群算法记录

1. 简介

蚁群算法（Ant Clony Optimization， ACO）是一种群智能算法，它是由一群无智能或有轻微智能的个体（Agent）通过相互协作而表现出智能行为，从而为求解复杂问题提供了一个新的可能性。蚁群算法最早是由意大利学者Colorni A., Dorigo M. 等于1991年提出。经过20多年的发展，蚁群算法在理论以及应用研究上已经得到巨大的进步。

蚂蚁在寻找食物的过程中往往是随机选择路径的，但它们能感知当前地面上的信息素浓度，并倾向于往信息素浓度高的方向行进。信息素由蚂蚁自身释放，是实现蚁群内间接通信的物质。由于较短路径上蚂蚁的往返时间比较短，单位时间内经过该路径的蚂蚁多，所以信息素的积累速度比较长路径快。因此，当后续蚂蚁在路口时，就能感知先前蚂蚁留下的信息，并倾向于选择一条较短的路径前行。这种正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的最短路径上行进。由于其他路径上的信息素会随着时间蒸发，最终所有的蚂蚁都在最优路径上行进。

2. TSP问题

蚁群算法最早用来求解TSP问题，并且表现出了很大的优越性，因为它分布式特性，鲁棒性强并且容易与其它算法结合，但是同时也存在这收敛速度慢，容易陷入局部最优（local optimal）等缺点。

TSP问题（Travel Salesperson Problem，即旅行商问题或者称为中国邮递员问题），是一种NP-hard问题，此类问题用一般的算法是很难得到最优解的，所以一般需要借助一些启发式算法求解，例如遗传算法（GA），蚁群算法（ACO），微粒群算法（PSO）等等。

TSP问题（旅行商问题）是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次 然后回到出发城市，并要求所走的路程最短。

由上述蚂蚁找食物模式演变来的算法，即是蚁群算法。这种算法具有分布计算、信息正反馈和启发式搜索的特征，本质上是进化算法中的一种启发式全局优化算法。

蚁群算法应用广泛，如旅行商问题(traveling salesman problem,简称TSP)、指派问题、Job-shop调度问题、车辆路径问题（vehicle routing problem）、图着色问题(graph coloring problem)和网络路由问题（network routing problem）等等。

3. 原理

设整个蚂蚁群体数量为m，城市数量为n，城市i和j之间的相互距离为$d_{ij}$，t时刻城市i与城市j路径上的信息浓度为${\tau }_{ij}(t)$，初始时刻，各城市间连接路径上的信息浓度相同，不妨设$\tau (0)={\tau }_0$

3.1 转移概率

蚂蚁k根据各城市间连接路径上的信息素浓度决定其下一个访问的城市，设$P_{ij}^k(t)$表示t时刻蚂蚁k从城市i到城市j的概率，计算公式如下：

$$P_{ij}^k=?$$