文档介绍：Artificial Intelligence (AI) 人工智能
第九章：群智能系统
内容提要
第九章：群智能系统
……
描述
群智能作为一种新兴的演化计算系统
……
蚁群算法原理
蚁群的觅食行为
蚁群算法原理
蚁群的分工
蚁群算法原理
蚁穴的结构
蚁群算法原理
蚁穴的结构
育婴室
储备室
寝室
蚁后室
日光浴场
入口
蚁群算法原理
蚁群觅食的“双桥试验”
通过遗留在来往路径上的信息素（Pheromone）的挥发性化学物质来进行 通信和协调。
蚁群算法
蚁群觅食过程
算法基本原理
自然界蚂蚁觅食行为
蚁群优化算法
蚁群
搜寻空间的一组有效解
问题的搜寻空间
信息素浓度变量
一个有效解
问题的最优解
觅食空间
信息素
蚁巢到食物的一条路径
找到的最短路径
对应关系
算法基本原理
蚁群优化算法（ Ant Colony Optimization , ACO）
蚂蚁在找寻食物的过程中往往是随机选择路径的，但它们能感知当前地面上的信息素浓度，并倾向于往信息素浓度高的方向行进。信息素由蚂蚁自身释放，是实现蚁群内间接通信的物质。
由于较短路径上蚂蚁的来回时间比较短，单位时间内经过该路径的蚂蚁多，所以信息素的积累速度比较长路径快。因此，当后续蚂蚁在路口时，就能感知从前蚂蚁留下的信息，并倾向于选择一条较短的路径前行。
这种正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的最短路径上行进。由于其他路径上的信息素会随着时间蒸发，最终全部的蚂蚁都在最优路径上行进。
蚁群算法流程
路径构建
每只蚂蚁都随机选择一个城市作为其出发城市，并维护一个路径记忆向量，用来存放该蚂蚁依次经过的城市。蚂蚁在构建路径的每一步中，按照一个随机比例规则选择下一个要到达的城市。
ACO基本要素
信息素更新
当所有蚂蚁构建完路径后，算法将会对所有的路径进行全局信息素的更新。注意，我们所描述的是AS的ant-cycle版本，更新是在全部蚂蚁均完成了路径的构造后才进行的，信息素的浓度变化与蚂蚁在这一轮中构建的路径长度相关。
蚂蚁系统 (Ant System，AS ) 的蚂蚁圈（Ant -cycle）版本是最基本的ACO算法，是以TSP作为应用实例提出的。
蚁群算法流程
路径构建：伪随机比例选择规则
对于每只蚂蚁k，路径记忆向量Rk依据访问依次记录了全部k已经经过的城市序号。
设蚂蚁k当前所在城市为i，则其选择城市j作为下一个访问对象的概率如上式。Jk(i) 表示从城市i 可以干脆到达的、且又不在蚂蚁访问过的城市序列Rk中的城市集合。
η(i, j) 是一个启发式信息，通常由η (i, j)=1/dij 干脆计算。
τ (i, j) 表示边(i, j)上的信息素量。
蚁群算法流程
路径构建：伪随机比例选择规则
长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。
α和β是两个预先设置的参数，用来限制启发式信息与信息素浓度作用的权重关系。
当α =0时，算法演化成传统的随机贪心算法，最邻近城市被选中的概率最大。当β =0时，蚂蚁完全只依据信息素浓度确定路径，算法将快速收敛，这样构建出的最优路径与实际目标差异较大，算法性能较差。
蚁群算法流程
信息素更新：
(1) 在算法初始化时，问题空间中全部的边上的信息素都被初始化为τ0。
(2) 算法迭代每一轮，问题空间中的全部路径上的信息素都会发生蒸发，我们为全部边上的信息素乘上一个小于1的常数( ρ: 信息素的蒸发率)。信息素蒸发是自然界本身固有的特征，在算法中能够帮助避开信息素的无限积累，使得算法可以快速丢弃之前构建过的较差的路径。
(3) 蚂蚁依据自己构建的路径长度在它们本轮经过的边上释放信息素。蚂蚁构建的路径越短、释放的信息素就越多。一条边被蚂蚁爬过的次数越多、它所获得的信息素也越多。
(4) 迭代 (2)，直至算法终止。
蚁群算法流程
信息素更新：
信息素的更新公式：
m：蚂蚁个数；
ρ：信息素的蒸发率，规定0<r≤1。
Δτ (i, j)：第k只蚂蚁在它经过的边上释放的信息素量，它等于蚂蚁k本轮构建路径长度的倒数。
Ck：路径长度，它是Rk中全部边的长度和。
蚁群算法流程
路径构建
信息素更新
蚁群算法的应用
车辆路径问题
（Vehicle Routing Problem，VRP）
车间作业调度问题
（Job-Shop Sch