蚁群算法：优越性及应用领域

21世纪是信息化世纪，信息化的核心技术就是智能化技术（人工智能技术）。“智能”从何而来？只能从模拟生物和人的智能而来。当然，人类的智能远高于其他生物的智能，所以首先受到关注的就是模拟人类大脑神经系统。1943年，心理学家W.McCulloh和数理逻辑学家W.Pitts首先提出了神经元的数学模型，M-P神经网络模型。1965年，计算机自动控制专家L.A.Zadeh在美国杂志Information and Control上发表了世界上第一篇模糊集合论的论文。1967年，美国密歇根大学的博士生J.D.Bagley在他的博士论文中首次提出了遗传算法的术语，后来该校的J.H.Holland教授于1975年发表了关于遗传算法的专著。

到20世纪末，人们发现除了人类社会以外，还有许多社会性生物，如蚂蚁、蜜蜂、鸟类、鱼类等。它们个体虽然很简单，但却表现出高度结构化的组织性。它们具备了社会性的三要素：有组织、有分工、有信息交换。生物学家和仿生学家经观察研究发现，蚂蚁在觅食走过的路径上释放了一种特有的分泌物——信息素（pheromone），蚂蚁个体之间正是通过这种信息素传递信息，从而相互协作，完成从蚁穴到食物源寻找最短路径的复杂任务。

1.蚁群算法的由来

从蚂蚁群体寻找最短路径的觅食行为受到启发，意大利学者M.Dorigo于1991年在巴黎召开的第一届欧洲人工生命大会上最早提出蚂蚁算法的概念，后来又于1992年在他的博士论文中首次系统地总结了一种模拟自然界蚁群行为的模拟进化算法——人工蚁群算法。其主要的特点是通过正反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索算法。它充分利用了蚁群通过个体间简单的信息传递，根据集体寻优的特点，搜索从蚁穴至食物间的最短路径。在蚁群算法中，每个蚂蚁个体只能给出小范围的局部信息，但通过群体协作，就能显示出复杂的求解性能，这也就是人工生命和复杂性科学的根本规律。

M.Dorigo等人的实验研究表明，蚁群算法在求解节点数为5～100的组合优化问题上，只要选用合适的参数，其优化结果普遍好于遗传算法（GA）、进化算法（EP）和模拟退火算法（SA）。蚁群算法在解决TSP问题、车间作业调度问题、二次指派问题、背包问题中，都显示了其优越的特点。近年来，蚁群算法已被大量应用于国民经济各个领域和人工智能各学科中，取得了令人惊叹的成绩。

2.蚂蚁觅食的行为特性

在介绍蚁群算法之前，我们先了解一下蚂蚁觅食的具体过程。

蚂蚁觅食时，当它们碰到一个还没有走过的路口时，就会随机地选择一条路径前行，与此同时会在路径上释放出一定的信息素。后来的蚂蚁再次碰到这个路口时，就选择信息素浓度较高的路径走过去，同时释放一定的信息素，由此形成了一个正反馈。最优路径上的信息素浓度将会越来越大，而其他路径上的信息素浓度却会随时间的流逝而逐渐消减。最终，整个蚁群便能寻找到食物源与巢穴之间的一条最短路径。具体的觅食过程如图9.9.1所示。

图9.9.1（a）为蚁群觅食的最初情况。当一只侦察蚁发现食物后，回巢告之其他成员，于是蚂蚁成群结队地从巢穴出发去搬运食物。因为在巢穴和食物之间有一障碍物，觅食初始，障碍物两侧的蚂蚁是随机选择路径的，蚂蚁在两条路径上的分布基本是均等的。随着时间流逝，蚂蚁倾向于向信息浓度高的方向移动。相等时间内较短路径上的信息素遗留得较多，因此较短路径上的蚂蚁也随之增多，如图9.9.1（b）所示。不难看出，由大量蚂蚁组成的蚁群系统表现出了一种正反馈现象。最终，蚁群系统结构发生了变化，即某一路径上通过的蚂蚁越多，后面的蚂蚁选择此路径的概率越大。于是，所有蚂蚁将沿着最短路径行进，如图9.9.1（c）所示。

图9.9.1　蚁群觅食路径

3.蚁群算法的基本数学模型与流程

M.Dorigo是基本依据TSP问题的算法，提出蚁群算法数学模型的。设m是蚁群中蚂蚁的个数，n为城市数，dij（i，j=1，2，…，n）为城市i和城市j之间的距离，τij（t）表示t时刻在路段（ij）上多的信息量强度，则在时刻t第k只蚂蚁从i点向j点转移的概率常表示为

式中：allowedk=｛n-tabuk｝，表示allowedk为蚂蚁k向下一点城市运动时允许选择的城市集合（亦指未被访问的节点集合）。tabuk是该蚂蚁已访问的城市集合（又称禁忌表（tabu list））。禁忌表是为了满足蚂蚁必须经过的所有n个不同城市这个约束条件而设计的一个表。它记录了在t时刻蚂蚁已经走过的城市，不允许（即禁忌）该蚂蚁在本次循环中再经过这些市。当本次循环结束后，禁忌表用来计算该蚂蚁所经历过的路径长度。S是在本次循环中允许访问的城市，它是allowedk这个集合中的元素。α与β的相对大小决定了蚂蚁对路段信息素和质量的取向偏好。ηij=1/dij表示路段（ij）的“能见度”，可理解为信息素被打折扣的程度。

经过T时刻，所有蚂蚁完成一次循环，信息素的强度需要调整。由于信息素在路段上随时间的流逝会有所蒸发，设信息素蒸发率为1-ρ，每次循环结束时，路段（ij）上的信息素强度为

式中：表示第k只蚂蚁在本次循环中留在路径（ij）上的信息量，Δτij=。(www.xing528.com)

根据不同的定义，M.Dorigo给出了三种不同的蚂蚁系统模型，分别称为“蚁周”模型（ant-cycle）、“蚁量”模型（ant-quantity），“蚁密”模型（ant-density）。第一种模型利用的是整体信息，后两种模型利用的是局部信息，在TSP问题求解中，第一种模型性能较好，通常用它作为基本模型。

求解TSP问题的蚁群算法的具体步骤如下：

（1）初始化，设最大循环次数Ncmax，初始化信息量τij，信息素增量Δτij=0，令当前循环次数Nc=0，将m只蚂蚁置于n个顶点（城市）上；初始禁忌表为空，tabuk=；

（2）循环次数Nc=Nc+1；

（3）对每只蚂蚁k（k=1，2，…，m），按式（9.9.1）移至下一顶点j，j∈（ntabuk）；

（4）更新禁忌表，将每个蚂蚁上一步走过的城市移动到该蚂蚁的个体禁忌表中；

（5）根据式（9.9.2）更新每条路径上的信息量；

（6）若Nc≥Ncmax，算法终止，并输出最短路径和路径长度，否则返回到步骤（2），并清空禁忌表。

基本蚂蚁算法的流程图如图9.9.2所示。

图9.9.2　基本蚂蚁算法流程图

4.改进的蚁群优化算法

基本蚁群算法的缺点是当“城市”数较多时，或各路径长度相差不大时，计算循环数大量增加，收敛速度减慢，甚至“停滞”。研究表明，改进的方向都是集中在搜索策略上，要根据具体问题作灵活有效的改进。

蚁群算法过去十多年都是欧美学者研究与应用较多。21世纪以来，我国由于人工智能技术的飞速发展，蚁群算法的研究与应用也随之快速发展并取得了许多创新成就。

表9.9.1列出蚁群算法的一些重要改进及创新进展。限于篇幅及本人的见闻，可能遗漏不少优秀之作，敬请读者谅解。

表9.9.1　蚁群算法的重要改进及创新进展