第3期 高玮：新型智能仿生模型—蚁群模型 ·271 此，称这类模型为“智能仿生模型”由于这类算法 影响后到者的行动（俱体表现为，后到的蚂蚁选择 模型的独特性，它显示出了解决复杂问题的特殊能 有这些物质的路径的可能性比选择没有这些物质的 力，因此，这类算法模型目前已在社会科学、自然科 路径的可能性大得多)，而后到者留下的外激素会 学、经济管理学、人类学、医学、生物学、化学、电子、对原有的外激素进行加强，同时，该物质随着时间的 计算机、机械、电信、电工土木等众多领域得到了成 推移会逐渐挥发掉，于是路径的长短及经过其上的 功的应用 蚂蚁数量就对残余信息素的强度产生了影响.反过 智能仿生模型目前已发展成为一个庞大的家族， 来信息素的强弱又指导着其他蚂蚁的行动方向，因 不可能在一篇文章中对之进行全面介绍因此，这里只 此，某一路径上走过的蚂蚁越多，则后来者选择该路 介绍一种新近发展的仿生模型—蚁群模型 径的概率就越大.这就构成了蚂蚁群体行为表现出 的一种信息正反馈现象.蚂蚁个体之间就是通过这 1蚁群模型的提出 种信息交流达到搜索食物源的目的 蚂蚁是自然界中最常见的一种社会性昆虫，人 图1给出蚁群系统工作原理的示意图 们对蚂蚁的认识大都是蚂蚁搬家，天要下雨”之类 的民谚.然而随着近代仿生学的发展，这种似乎微不 足道的小生物越来越多地受到学者们的关注.1991 20 年前后意大利学者M.Dorigp等人2首先提出了 d=0.5 (a)问题提出 (b)一次搜索状态(c)再次搜索状态 种源于蚁群觅食行为的智能仿生优化算法蚁群 优化算法(ant colny optm ization,.ACo).他们的研 图1蚁群系统工作原理示意图 究激发了人们对蚁群系统的研究：相对弱小，功能并 Fig 1 Principles of ant colony system 不强大的个体是如何完成复杂工作的（如找到食物 的最佳路径并返回等).在昆虫学家及生物学家研 图中，设A是蚁巢，E是食物源，HC连线为障碍 究的基础上，数学及计算机方面的专家和工程师经 物，距离d如图中数字所示.由于障碍物的存在，由 过抽象提出了一种有用的优化和控制模型蚁群 A外出觅食或由E返回巢穴的蚂蚁只能经由H点 模型(ant colny model)).蚁群模型目前已发展为一 或C点到达目的地.假设，蚂蚁以速度1往返于A 个包括多种具体模型算法的系统，其中，蚁群优化算 和E之间，每经过一个单位时间各有30只蚂蚁离 法是发展的最充分也是最基本的算法模型 开A和E到达B和D图1(a).初始时，各有30只 为了说明蚁群模型的基本生物原理，这里以蚁群 蚂蚁在B和D点遇到障碍物，开始选择路径.由于 模型算法中的典型算法—蚁群优化算法为例进行 此时路径上无信息素.蚂蚁便以相同的概率随机地 说明.蚁群优化算法的生物学原理可大致描述如下： 走2条路中的任意一条，因此，15只选往C,15只选 蚂蚁属于群居昆虫，其个体行为极其简单，而群 往H图1(b)).经过一个单位时间以后，路径BCD 体行为却相当复杂.相互协作的蚂蚁群体很容易找 被30只蚂蚁爬过，而路径BHD上则只被15只蚂蚁 到从蚁巢到食物源的最短路径，而单个蚂蚁则不能. 爬过.BCD上的信息量是BHD上信息量的2倍.此 此外，蚂蚁还能够适应环境的变化，例如，在蚁群的 时，又有30只蚂蚁离开B和D,于是20只选择往C 运动路线上突然出现障碍物时，它们能够很快地重 方向，而另外10只则选往H图1(c)人.这样，更多 新找到最优路径，那么，蚁群是如何完成这些复杂任 的信息量被留在更短的路径BCD上.另外，由于蚂 务的呢？人们通过大量的研究发现，蚂蚁个体之间 蚁爬行长路径花费的时间长，因此，在相同条件下 是通过在其所经过的路上留下一种可称之为信息 长路径上信息素的挥发量将更大.从而，随着时间的 素的物质来进行信息传递的.也就是说，蚁群中的 推移和上述过程的重复，短路径上的信息量便以更 蚂蚁以“外激素为媒介通过间接、异步方式进行相 快的速度增长.于是会有越来越多的蚂蚁选择这条 互间的信息传输.蚂蚁在行动（得找食物或者寻找 短路径，以致最终完全选择这条短路径 回巢的路径)的过程中，会在它们经过的路径上留 可见.在自然界中，蚁群的这种寻找路径的过程 下一些化学物质我们称之为外激素).这种物质能 表现为一种信息正反馈的过程，借助这种原理，把只 被同一蚁群中后来的蚂蚁感受到，并作为一种信号 具备了简单功能的工作单元视为蚂蚁”那么上述 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net此 ,称这类模型为“智能仿生模型 ”. 由于这类算法 模型的独特性 ,它显示出了解决复杂问题的特殊能 力 ,因此 ,这类算法模型目前已在社会科学、自然科 学、经济管理学、人类学、医学、生物学、化学、电子、 计算机、机械、电信、电工、土木等众多领域得到了成 功的应用. 智能仿生模型目前已发展成为一个庞大的家族 , 不可能在一篇文章中对之进行全面介绍 ,因此 ,这里只 介绍一种新近发展的仿生模型 ———蚁群模型. 1 蚁群模型的提出 蚂蚁是自然界中最常见的一种社会性昆虫 ,人 们对蚂蚁的认识大都是“蚂蚁搬家 ,天要下雨 ”之类 的民谚. 然而随着近代仿生学的发展 ,这种似乎微不 足道的小生物越来越多地受到学者们的关注. 1991 年前后意大利学者 M. Dorigo等人 [ 224 ]首先提出了一 种源于蚁群觅食行为的智能仿生优化算法 ———蚁群 优化算法 ( ant colony op tim ization, ACO ). 他们的研 究激发了人们对蚁群系统的研究 :相对弱小 ,功能并 不强大的个体是如何完成复杂工作的 (如找到食物 的最佳路径并返回等 ). 在昆虫学家及生物学家研 究的基础上 ,数学及计算机方面的专家和工程师经 过抽象提出了一种有用的优化和控制模型 ———蚁群 模型 ( ant colony model). 蚁群模型目前已发展为一 个包括多种具体模型算法的系统 ,其中 ,蚁群优化算 法是发展的最充分也是最基本的算法模型. 为了说明蚁群模型的基本生物原理 ,这里以蚁群 模型算法中的典型算法 ———蚁群优化算法为例进行 说明.蚁群优化算法的生物学原理可大致描述如下: 蚂蚁属于群居昆虫 ,其个体行为极其简单 ,而群 体行为却相当复杂. 相互协作的蚂蚁群体很容易找 到从蚁巢到食物源的最短路径 ,而单个蚂蚁则不能. 此外 ,蚂蚁还能够适应环境的变化 ,例如 ,在蚁群的 运动路线上突然出现障碍物时 ,它们能够很快地重 新找到最优路径 ,那么 ,蚁群是如何完成这些复杂任 务的呢 ? 人们通过大量的研究发现 ,蚂蚁个体之间 是通过在其所经过的路上留下一种可称之为“信息 素 ”的物质来进行信息传递的. 也就是说 ,蚁群中的 蚂蚁以“外激素 ”为媒介通过间接、异步方式进行相 互间的信息传输. 蚂蚁在行动 (寻找食物或者寻找 回巢的路径 )的过程中 ,会在它们经过的路径上留 下一些化学物质 (我们称之为外激素 ). 这种物质能 被同一蚁群中后来的蚂蚁感受到 ,并作为一种信号 影响后到者的行动 (具体表现为 ,后到的蚂蚁选择 有这些物质的路径的可能性比选择没有这些物质的 路径的可能性大得多 ) ,而后到者留下的外激素会 对原有的外激素进行加强 ,同时 ,该物质随着时间的 推移会逐渐挥发掉 ,于是路径的长短及经过其上的 蚂蚁数量就对残余信息素的强度产生了影响. 反过 来信息素的强弱又指导着其他蚂蚁的行动方向 ,因 此 ,某一路径上走过的蚂蚁越多 ,则后来者选择该路 径的概率就越大. 这就构成了蚂蚁群体行为表现出 的一种信息正反馈现象. 蚂蚁个体之间就是通过这 种信息交流达到搜索食物源的目的. 图 1给出蚁群系统工作原理的示意图. 图 1 蚁群系统工作原理示意图 Fig. 1 Princip les of ant colony system 图中 ,设 A是蚁巢 , E是食物源 , HC连线为障碍 物 ,距离 d如图中数字所示. 由于障碍物的存在 ,由 A外出觅食或由 E返回巢穴的蚂蚁只能经由 H点 或 C点到达目的地. 假设 ,蚂蚁以速度 1往返于 A 和 E之间 ,每经过一个单位时间各有 30只蚂蚁离 开 A和 E到达 B 和 D (图 1 ( a) ). 初始时 ,各有 30只 蚂蚁在 B 和 D 点遇到障碍物 ,开始选择路径. 由于 此时路径上无信息素. 蚂蚁便以相同的概率随机地 走 2条路中的任意一条 ,因此 , 15只选往 C, 15只选 往 H (图 1 ( b) ). 经过一个单位时间以后 ,路径 BCD 被 30只蚂蚁爬过 ,而路径 BHD上则只被 15只蚂蚁 爬过. BCD上的信息量是 BHD 上信息量的 2倍. 此 时 ,又有 30只蚂蚁离开 B 和 D,于是 20只选择往 C 方向 ,而另外 10只则选往 H (图 1 ( c) ). 这样 ,更多 的信息量被留在更短的路径 BCD 上. 另外 ,由于蚂 蚁爬行长路径花费的时间长 ,因此 ,在相同条件下 , 长路径上信息素的挥发量将更大. 从而 ,随着时间的 推移和上述过程的重复 ,短路径上的信息量便以更 快的速度增长. 于是会有越来越多的蚂蚁选择这条 短路径 ,以致最终完全选择这条短路径. 可见 ,在自然界中 ,蚁群的这种寻找路径的过程 表现为一种信息正反馈的过程 ,借助这种原理 ,把只 具备了简单功能的工作单元视为“蚂蚁 ”,那么上述 第 3期 高 玮 :新型智能仿生模型 ———蚁群模型 ·271·