蚁群算法（1）

蚁群算法（Ant colony algorithm）

蚂蚁几乎是没有视力的，它们是如何找到食物和家之间的路径的？

在觅食过程中，蚂蚁在它所经过的路径上留下浓度与食物源质量成比例的信息素（pheromone），并能够感知信息素的存在及其浓度，以此指导自己的运动方向，倾向于朝着信息素浓度高的方向移动。

于是，蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大，因此质量好、距离近的食物源会吸引越来越多的蚂蚁，信息素浓度的增长速度会更快。蚂蚁个体之间正是通过这种信息的交流达到寻找食物和蚁穴之间最短路径的目的。

算法概述

• 路径选择概率

其中， 表示第 条路径的信息素浓度； 表示第 条路径的路径信息，通常用此路径长度的倒数来描述 ，表示路径越短，选择此路径的概率越大； 和 这两个参数用于对控制信息素浓度和路径信息在选择概率中的贡献度。

其中， 代表信息素的挥发率， 表示新增加的信息素。

基本蚁群算法是针对旅行商问题提出的：

在 t 时刻，第 k 只蚂蚁从城市 i 到 城市 j 。

城市 i 和 城市 j 间路径的信息素更新为：

认为一只蚂蚁走完整个回路才更新信息素，所以要通过 n 个时间后，保留的信息素加上增加的信息素。

增加的信息素：

注：所有的蚂蚁从 i 到 j 留下的信息素累计

注：第 k 只蚂蚁留下的信息素

其中， 为常量， 为第 只蚂蚁在此次更新中经由的旅行商回路总长

算法改进

对基本蚁群算法的改进

• 在路径选择中采用了 利用（exploitation） 和 探索（exploration） 相结合的方法

随机数 ，当这个随机数 时，蚂蚁选择目前的最优路径 当 时，系统采用了探索策略，即如同基本蚁群算法，按照概率的方式选择路径。

• 对基本蚁群算法的改进

信息素的更新采用了 全局更新 和 局部更新 相结合的方案

局部更新是 所有 蚂蚁完成一次移动后执行
另

城市 i 到城市 j 之间的新增信息素：从城市 j 到所有的下一个城市 k 之间寻找信息素最大的城市 × 系数

代入就是：

城市 i 到 城市 j 更新的时候除了考虑当前剩余的信息素，还需要考虑下一节点带来的权重

全局更新是在所有的蚂蚁完成了旅行商回路后执行，全局更新仅仅对目前的最优回路上的路径（边）进行信息素的添加。