蚁群算法及其在TSP中的应用
Macro Dorigo
Gambardella
蚁群算法
20 世纪90 年代初，意大利学者Dorigo 等受 蚂蚁觅食行为的启发，提出了蚁群算法，是一种 仿生算法。
蚂蚁在觅食过程中可以找出巢穴到食物源的最短 路径，为什么？ （1）信息素(pheromone) （2）正反馈现象：某一路径上走过的蚂蚁越 多，则后来者选择该路径的概率就越大。
最后，设置周游次数计数器NC，当达到设定值时结束，最短路径为；
Lmin min Lk minl l 1, 2, , NC
简化的蚂蚁寻食过程
蚂蚁从A点出发，速度相同，食物在D点，可能随机选 择路线ABD或ACD。假设初始时每条分配路线一只蚂 蚁，每个时间单位行走一步，本图为经过9个时间单位 时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁 刚好走到C点，为一半路程。
简化的蚂蚁寻食过程
经过18个时间单位时的情形：走ABD的蚂蚁到达终 点后得到食物又返回了起点A，而走ACD的蚂蚁刚 好走到D点。
蚂蚁寻食过程描述
寻找最短路径的蚁群算法来源于蚂蚁寻食的行为。蚁群寻找 食物时会派出一些蚂蚁分头在四周游荡, 如果一只蚂蚁找到 食物, 它就返回巢中通知同伴并沿途留下“ 信息素”(外激 素pheromone)作为蚁群前往食物所在地的标记。信息素 会逐渐挥发,如果两只蚂蚁同时找到同一食物, 又采取不同路 线回到巢中, 那么比较绕弯的一条路上信息素的气味会比较 淡, 蚁群将倾向于沿另一条更近的路线前往食物所在地。蚁 群算法设计虚拟的“蚂蚁”, 让它们摸索不同路线, 并留下 会随时间逐渐消失的虚拟“信息素”, 根据“信息素较浓的 路线更近”的原则, 即可选择出最佳路线.
蚂蚁TSP
经过N个时刻，所有蚂蚁完成了一次周游，此时应清空禁忌 表，将当前蚂蚁所在的城市置入tabu 中准备下一次周游， 这时计算每一只蚂蚁走过的路程Lk ，并保存最短路径
Lmin Lmin min Lk , k 1, , m
随着时间推移，以前的信息素会逐渐消失，用参数 1- 表示 信息消失程度，蚂蚁完成一次循环后，各路径上信息素要根 据下式调整
蚂蚁TSP
ij t 1 1
ij t
ij
m k
ij
ij
k1
其中， ijk表示第 只蚂蚁在本次循环过程中留在路径ij 上的信息素， ij 表示本次循环中各路径 ij上信息素的 增量。
蚂蚁TSP
k ij (t, t 1)
Q / Lk , 如果蚂蚁K在巡回中经过ij 0, 如果蚂蚁K在巡回中不经过ij
式中Q是常量，Lk表示第k只蚂蚁的循环路线，即如果蚂蚁经过ij则信息素 增量为一个常量除以蚂蚁k的巡回路线长，这里信息素增量只与蚂蚁巡回 路线和Q有关系而和具体的dij无关。
蚂蚁TSP
为了模拟实际蚂蚁的行为, 首先引进如下记号: 设m是蚁群中蚂蚁的数, dij(i,j=1,2,...,n)表示城市i 和城市j 之间的距离, Tij(t)表示t 时刻在城市i,j 连线上残留的信息素。初始
时刻，各条路径上的信息素相等，设 Tij(0) 蚂蚁 k(1,2,3..m) 在运动过程中，根据各条路径上的信息 素决定转移方向。 Pij(t)表示在 时刻蚂ij t
Pijk
ik t
ik
, j tabuk
k tabuk
0,
j tabuk
其中：ij 为先验知识或称为能见度，在TSP问题中为城市i转移到城市j的启发 信息，一般地取ij =1/dij ， 为在路径上残留信息的重要程度； 为启发信息的 重要程度；与实际蚁群不同，人工蚁群系统具有记忆能力，tabu 用以记录蚂 蚁K当前所走过的城市，称为禁忌表（下一步不充许选择的城市），集合 tabu 随着进化过程进行动态调整。