文档介绍：蚁群算法及其应用讲座
20
简化的蚂蚁寻食过程
经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。
8
自然蚁群与人工蚁群
相似之处在于：都是优先选择信蚁群算法及其应用讲座
20
简化的蚂蚁寻食过程
经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。
8
自然蚁群与人工蚁群
相似之处在于：都是优先选择信息素浓度大的路径。
两者的区别：
（1）在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。
（2）人工蚁群选择路径时不是盲目的。而是按一定规律有意识地寻找最短路径。例如，在TSP问题中，可以预先知道当前城市到下一个目的地的距离。
9
应用一：TSP问题
旅行商问题（TSP,traveling salesman problem）1960年首先提出。
问题描述：
一商人去n个城市销货，所有城市走一遍再回到起点，使所走路程最短。
TSP在许多工程领域具有广泛的应用价值
例如电路板布线、VLSI芯片设计、机器人控制、交通路由等。
TSP的求解是NP-hard问题。随着城市数目的增多,问题空间将呈指数级增长。
10
TSP问题的数学描述
TSP问题表示为一个N个城市的有向图G=（N，A），其中
城市之间距离
目标函数为
其中，，为城市1,2，…n的
一个排列，。
11
蚂蚁算法求解TSP
下面以TSP为例说明基本蚁群算法模型。
首先将m只蚂蚁随机放置在n个城市，位于城市i的第k只蚂蚁选择下一个城市j的概率为:
12
蚂蚁算法求解TSP
其中：
表示边（i，j）上的信息素浓度；
是启发信息，d是城市i和j之间的距离；
α和β反映了信息素与启发信息的相对重要性；
表示蚂蚁k已经访问过的城市列表。
当所有蚂蚁完成周游后，按以下公式进行信息素更新。
13
蚂蚁算法求解TSP
其中：ρ为小于1的常数，表示信息的持久性。
其中：Q为常数；lk表示第k只蚂蚁在本次迭代中走过的路径，Lk为路径长度。
14
求解TSP算法步骤
⑴初始化　随机放置蚂蚁，为每只蚂蚁建立禁忌表tabuk，将初始节点置入禁忌表中;
⑵迭代过程
k=1
while k=<ItCount do (执行迭代)
for i = 1 to m do (对m只蚂蚁循环)
for j = 1 to n - 1 do (对n个城市循环)
　　根据式(1)，采用***赌方法在窗口外选择下一个城市j;
将j置入禁忌表,蚂蚁转移到j;
　 end for
end for
计算每只蚂蚁的路径长度;
根据式(2)更新所有蚂蚁路径上的信息量;
k = k + 1;
end while
⑶输出结果,结束算法.
15
蚁群的规模和停止规则
一、蚁群大小
一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数。
二、终止条件
1 给定一个外循环的最大数目；
2 当前最优解连续K次相同而停止，其中K是一个给定的整数，表示算法已经收敛，不再需要继续。
16
蚂蚁算法的缺点
蚂蚁算法的缺点：
1）收敛速度慢
2）易于陷入局部最优
改进：
1）采用局部优化，设计了三种优化算子。
2）采用蚁群优化算法。
3）其它优化算法
17
改进一：局部优化（算子1 ）
18
对Kroa100，算子1优化前后的路径如图所示。优化前（28596），算子1优化后（26439）
19
改进一：局部优化（算子2 ）
20
对Kroa100，算子2优化前后的路径如图所示。算子1（26439），算子2优化后（23012）
21
TSP具有邻域特征，设置候选窗口，窗口大小应取一个合理值。
蚂蚁总是优先选择候选窗口中的城市。搜索结束后，根据候选窗口对路径进行优化，如果将候选窗口内的节点交换到当前节点附近后距离更短，则进行变异。
改进一：局部优化（算子3 ）
22
对Kroa100，算子3优化前后的路径如图所示。（23012），算子3优化后（21282）
23
收敛特性对比
24
改进二：蚁群优化算法
1)ACS采用了更为大胆的行为选择规则，在城市r的蚂蚁k转移到城市s的规则为:
25

第三，仅对全局最优解边