第3卷第3期 智能系统学报 Vol 3 Na 3 2008年6月 CAA I Transactions on Intelligent Systems Jun 2008 新型智能仿生模型 蚁群模型 高玮 (武汉工业学院土木工程系，湖北武汉430023) 摘要：智能仿生模型是一种多学科交叉的产物，其发展对很多相关学科的发展具有极大的促进作用.蚁群模型是 模拟自然界蚁群系统行为而提出的一种新型智能仿生模型，其研究在短短的10余年时间里得到了飞速发展，已成为 很多学科的研究热点.我国在这方面的研究尚没有全面开展，为此从仿生原理及实现途径入手，对蚁群模型的几大 模型算法进行了详细介绍，并对模型的发展进行了展望.其次，对蚁群模型的典型应用进行了说明，并对模型的最新 应用进行了介绍.最后，通过对其他几种仿生算法的介绍，进行了蚊群算法同粒子群算法、免疫算法及进化算法等的 比较研究，指出它们的相同点和差异之处.通过对蚁群模型的全面的介绍，以期促进该模型在我国的发展. 关键词：智能仿生模型：蚁群模型：学科交叉，生物原理 中图分类号：Q811.21文献标识码：A文章编号：1673-4785(2008)03027009 The intelligent bion ic model ant colony GAO Wei (Deparment of Civil Engineering.Wuhan Polytechnic University,Wuhan 430023,China) Abstract:mp roving the intelligent bionic ant cobny modelwill require multidisc plinary research,and so its devel opment will promote progress in related subjects The ant colny model,a new intelligent bionic model which mm- ics the behavior of an ant colony,has progressed substantially in the last ten years However,there has been no systematic study of this field in China To encourage more research this paper gives a detailed introduction o sever al major ant colony models according to their underlying bionic princ ples and smulation methods The latest devel- opments in this field are also described Then,typical applications of ant colny models are summarized,and new areas where they can be used are presented Finally,comparisons are made between the ant colny algorithm,the particle swam opti ization algorithm,the mmune algorithm,and the evolutionary algorithm.The si ilarities and differences beteen these algorithms are pointed out This comprehensive introduction should promote research on ant colony algorithms in China Keywords:intelligent bionic model ant colony model,subjects intersection;biolgical princ ples 随着自然科学的发展及人类对自然认识水平及的新学科包括人工生命(artificial lif论，ALFE)、计算 能力的提高，20世纪的科学出现了日新月异的新局智能(computational intelligence,.C)、生物信息学 面，科学研究领域出现了一些令人耳目一新的新趋(bioinfomatics)、自然计算(natural computation, 向.而学科的交叉及渗透是科学发展的源泉，随着各 NC)等，这些学科都在20世纪末期产生并迅速成为 学科的交叉及渗透，20世纪中、后期出现了大量新 各国学者的研究热点， 兴的边缘交叉学科.其中，生命科学与计算机科学的 本文主要介绍近来迅速发展的新学科一人工 结合产生出了大量新学科的火花).其中有代表性 生命、计算智能、生物信息学等产生出的一类新型算 法模型.由于这类算法模型可归结于智能科学的范 收稿日期：2007-11-10 围，从而均属于智能模型.而又由于这类新型算法模 基金项目：湖北省教育厅科研基金资助项目(D200618004) 通讯作者：高玮.Email:gaow@whpu edu cn 型主要基于仿生学原理，从而也可称为仿生模型.因 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 3卷第 3期 智 能 系 统 学 报 Vol. 3 №. 3 2008年 6月 CAA I Transactions on Intelligent System s Jun. 2008 新型智能仿生模型 ———蚁群模型 高 玮 (武汉工业学院 土木工程系 ,湖北 武汉 430023) 摘 要 :智能仿生模型是一种多学科交叉的产物 ,其发展对很多相关学科的发展具有极大的促进作用. 蚁群模型是 模拟自然界蚁群系统行为而提出的一种新型智能仿生模型 ,其研究在短短的 10余年时间里得到了飞速发展 ,已成为 很多学科的研究热点. 我国在这方面的研究尚没有全面开展 ,为此从仿生原理及实现途径入手 ,对蚁群模型的几大 模型算法进行了详细介绍 ,并对模型的发展进行了展望. 其次 ,对蚁群模型的典型应用进行了说明 ,并对模型的最新 应用进行了介绍. 最后 ,通过对其他几种仿生算法的介绍 ,进行了蚁群算法同粒子群算法、免疫算法及进化算法等的 比较研究 ,指出它们的相同点和差异之处. 通过对蚁群模型的全面的介绍 ,以期促进该模型在我国的发展. 关键词 :智能仿生模型 ;蚁群模型 ;学科交叉 ;生物原理 中图分类号 : Q811. 21 文献标识码 : A 文章编号 : 167324785 (2008) 0320270209 The intelligent bion ic model—ant colony GAO W ei (Department of Civil Engineering,W uhan Polytechnic University, W uhan 430023, China) Abstract: Imp roving the intelligent bionic ant colonymodelwill require multidiscip linary research, and so its devel2 opment will p romote p rogress in related subjects. The ant colony model, a new intelligent bionic modelwhich m im2 ics the behavior of an ant colony, has p rogressed substantially in the last ten years. However, there has been no systematic study of this field in China. To encourage more research this paper gives a detailed introduction to sever2 almajor ant colony models according to their underlying bionic p rincip les and simulation methods. The latest devel2 opments in this field are also described. Then, typ ical app lications of ant colony models are summarized, and new areas where they can be used are p resented. Finally, comparisons are made between the ant colony algorithm, the particle swarm op tim ization algorithm, the immune algorithm, and the evolutionary algorithm. The sim ilarities and differences between these algorithm s are pointed out. This comp rehensive introduction should p romote research on ant colony algorithm s in China. Keywords: intelligent bionic model; ant colony model; subjects intersection; biological p rincip les 收稿日期 : 2007211210. 基金项目 :湖北省教育厅科研基金资助项目 (D200618004). 通讯作者 :高 玮. E2mail: gaow@whpu. edu. cn. 随着自然科学的发展及人类对自然认识水平及 能力的提高 , 20世纪的科学出现了日新月异的新局 面 ,科学研究领域出现了一些令人耳目一新的新趋 向. 而学科的交叉及渗透是科学发展的源泉 ,随着各 学科的交叉及渗透 , 20世纪中、后期出现了大量新 兴的边缘交叉学科. 其中 ,生命科学与计算机科学的 结合产生出了大量新学科的火花 [ 1 ] . 其中有代表性 的新学科包括人工生命 ( artificial life, AL IFE)、计算 智能 ( computational intelligence, CI)、生物信息学 ( bioinformatics)、自 然 计 算 ( natural computation, NC)等 ,这些学科都在 20世纪末期产生并迅速成为 各国学者的研究热点. 本文主要介绍近来迅速发展的新学科 ———人工 生命、计算智能、生物信息学等产生出的一类新型算 法模型. 由于这类算法模型可归结于智能科学的范 围 ,从而均属于智能模型. 而又由于这类新型算法模 型主要基于仿生学原理 ,从而也可称为仿生模型. 因
第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·
·272· 智能系统学报 第3卷 寻找路径的过程便成了蚁群优化算法的基本过程， on 如果，j∈N,则广()= 尽管，蚁群优化算法的人工蚁群同生物蚁群基本原 ∑(w 理相同，但为了具体的优化应用，人工蚁群也有自己 式中：ā表示路径上残留信息的相对重要程度：B表 的一些特点.如，人工蚁群具有一定的记忆能力，它 示期望值的相对重要程度：N表示所有可能的目标 能够记忆己经访问过的节点；另外，人工蚁群在选择 城市集合，即还没有访问的城市集合 下一条路径的时候并不是完全盲目的，而是按一定 由上式可以发现，算法中蚂蚁选中某一个城 的算法规律有意识地寻找最短路径如在以上问题 市的概率是问题本身所提供的启发式信息与从蚂 中，可以预先知道下一个目标的距离). 蚁目前所在城市到目标城市路径上残留信息量的 2蚁群模型的发展 函数】 另外，为了避免对同一个城市的多次访问，每一 21基本蚁群模型 只蚂蚁都保存一个列表abu(),用于记录到目前 由于蚁群优化算法是最典型的蚁群模型，而蚁 为止已经访问的城市 群优化算法最经典的解决问题为T$P问题，因此， 为了避免残留信息素过多引起的残留信息淹没 这里用TSP问题为例来说明算法的实现过程，这里 启发式信息的问题，在每一只蚂蚁完成对所有n个 以最基本的蚁群算法蚂蚁系统AS(ant system) 城市的访问后他即一个循环结束后，必须对残留 为例进行说明 信息素进行更新处理，模仿人类记忆的特点，对旧的 假设将m只蚂蚁放入到n个随机选择的城市 信息素进行削弱.同时，必须将最新的蚂蚁访问路径 中，那么每一只蚂蚁每一步的行动为：根据一定的依 的信息素加入T,从而得到： 据选择下一个它还没有访问的城市：同时在完成一步 从一个城市到达另外一个城市)或者一个循环完 Tg1+m)=prg()+∑A 成对所有个城市的访问)后，更新所有路径上的残 式中：P表示残留信息素的剩余率；1-P表示残留信 留信息浓度选择下一个城市的依据主要有2点： 息素被削弱的部分，即信息素的挥发率.另外，为了 1)τ，()为时刻连接城市和的路径上残留 防止信息素的无限累积，P必须小于1：△表示蚂蚁 信息的浓度，即由算法本身提供的信息：2)1为由 k在时间段到(1+n)内的访问过程中，在到的 城市转移到城市的启发信息，该启发信息是由要 路径上留下的残留信息浓度 解决的问题给出的，由一定的算法实现.在TSP问 另外，关于△的选择，M.Dorig还介绍了3种 题中一般取ng=1/d(d,表示城市i间的距离，ng 不同的实现方法，分别称为Ant Cycle,Ant Density, 在这里可以称为先验知识) Ant Quantity算法.3种算法的具体表达式为 那么，时刻位于城市的蚂蚁k选择城市为 目标城市的概率P广（按以下方法计算 Q,如果第k只妈蚁在时刻和时刻1+1之间经过 0,其他 式中：Q是常数：L表示第k只蚂蚁在本次循环中所走路径的长度 2)△ Q,如果第k只蚂蚁在时刻和时刻t+1之间经过访 0,其他 3)△ ,如果第k只蚂蚁在时刻和时刻1+1之间经过年 d的 (0,其他 在初始时刻，g0)=C 而后2种算法与前一种算法的区别在于，后2种算法中每走一步卿从时间到(1+))都要更 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
寻找路径的过程便成了蚁群优化算法的基本过程. 尽管 ,蚁群优化算法的人工蚁群同生物蚁群基本原 理相同 ,但为了具体的优化应用 ,人工蚁群也有自己 的一些特点. 如 ,人工蚁群具有一定的记忆能力 ,它 能够记忆已经访问过的节点;另外 ,人工蚁群在选择 下一条路径的时候并不是完全盲目的 ,而是按一定 的算法规律有意识地寻找最短路径 (如在以上问题 中 ,可以预先知道下一个目标的距离 ). 2 蚁群模型的发展 2. 1 基本蚁群模型 由于蚁群优化算法是最典型的蚁群模型 ,而蚁 群优化算法最经典的解决问题为 TSP问题 ,因此 , 这里用 TSP问题为例来说明算法的实现过程 ,这里 以最基本的蚁群算法 ———蚂蚁系统 AS( ant system) 为例进行说明. 假设将 m 只蚂蚁放入到 n个随机选择的城市 中,那么每一只蚂蚁每一步的行动为:根据一定的依 据选择下一个它还没有访问的城市;同时在完成一步 (从一个城市到达另外一个城市 )或者一个循环 (完 成对所有 n个城市的访问 )后 ,更新所有路径上的残 留信息浓度. 选择下一个城市的依据主要有 2点 : 1)τij ( t)为 t时刻连接城市 i和 j的路径上残留 信息的浓度 ,即由算法本身提供的信息; 2)ηij为由 城市 i转移到城市 j的启发信息 ,该启发信息是由要 解决的问题给出的 ,由一定的算法实现. 在 TSP问 题中一般取 ηij = 1 / dij ( dij表示城市 i, j间的距离 ,ηij 在这里可以称为先验知识 ). 那么 , t时刻位于城市 i的蚂蚁 k选择城市 j为 目标城市的概率 P k ij ( t)按以下方法计算 : 如果 , j ∈N k i ,则 P k ij ( t) = τα ij ( t)ηβ j j∈∑N k i τ α ij ( t)η β j . 式中 :α表示路径上残留信息的相对重要程度;β表 示期望值的相对重要程度; N k i 表示所有可能的目标 城市集合 ,即还没有访问的城市集合. 由上式可以发现 ,算法中“蚂蚁 ”选中某一个城 市的概率是问题本身所提供的启发式信息与从“蚂 蚁 ”目前所在城市到目标城市路径上残留信息量的 函数. 另外 ,为了避免对同一个城市的多次访问 ,每一 只蚂蚁都保存一个列表 tabu ( k) ,用于记录到目前 为止已经访问的城市. 为了避免残留信息素过多引起的残留信息淹没 启发式信息的问题 ,在每一只蚂蚁完成对所有 n个 城市的访问后 (也即一个循环结束后 ) ,必须对残留 信息素进行更新处理 ,模仿人类记忆的特点 ,对旧的 信息素进行削弱. 同时 ,必须将最新的蚂蚁访问路径 的信息素加入 τ,从而得到 : τij ( t + n) =ρτij ( t) + ∑ m k =1 Δτk ij . 式中 :ρ表示残留信息素的剩余率; 1 -ρ表示残留信 息素被削弱的部分 ,即信息素的挥发率. 另外 ,为了 防止信息素的无限累积 ,ρ必须小于 1;Δτk ij表示蚂蚁 k在时间段 t到 ( t + n) 内的访问过程中 ,在 i到 j的 路径上留下的残留信息浓度. 另外 ,关于 Δτk ij的选择 , M. Dorigo还介绍了 3种 不同的实现方法 ,分别称为 Ant Cycle, Ant Density, Ant Quantity算法. 3种算法的具体表达式为 1)Δτk ij = Q Lk ,如果第 k只蚂蚁在时刻 t和时刻 t + 1之间经过 ij; 0,其他. 式中 : Q是常数; Lk 表示第 k只蚂蚁在本次循环中所走路径的长度. 2) Δτk ij = Q,如果第 k只蚂蚁在时刻 t和时刻 t + 1之间经过 ij; 0,其他. 3)Δτk ij = Q dij ,如果第 k只蚂蚁在时刻 t和时刻 t + 1之间经过 ij; 0,其他. 在初始时刻 ,τij (0) =C. 而后 2种算法与前一种算法的区别在于 ,后 2 种算法中每走一步 (即从时间 t到 ( t + 1) )都要更 ·272· 智 能 系 统 学 报 第 3卷
第3期 高玮：新型智能仿生模型蚁群模型 ·273· 新残留信息的浓度，而不是当所有蚂蚁完成对所有 面BM中所描述的蚂蚁行为相似.不同之处在于，它 n个城市的访问以后；在Ant Density算法中，△，= 们不是观察当前所背负的物体与周围的物体是否相 Q:而在Ant Quantity算法中，△-号(d表示城市i 同，而是判断是否相似，这样最终能够将相似的数据 d 聚为一类 和的距离).也就是说，在Ant Density算法中，从城 23蚁群群体智能模型 市到的蚂蚁在路径上残留的信息浓度为一个与 蚂蚁群最令人惊叹的能力是筑巢”，这类‘群 路径无关的常量Q.而在Ant Quantity算法中，以d, 体智能“是自然界中普遍存在的现象，其中道理人 为城市到城市的距离，残留信息浓度为Q/dp,即 们并不清楚，但人们可以对这种现象进行唯象地 残留信息浓度会因为城市距离的减小而增大」 建模研究」 在以上算法中Q、ā、B、P的最佳组合可以由实 蚂蚁能筑巢，人们可能感到很惊讶，而看到人建 验经验确定叫 筑高楼大厦并不感到惊奇.这也许是因为，人们认为 相关研究表明，基本蚁群算法具有如下优点： 人有一个聪明的脑袋，故能设计建筑高楼大厦.那 1)较强的鲁棒性.对基本蚁群算法模型稍加修 么，为什么有一个聪明的脑袋，就能完成各种工作 改，便可以应用于其他问题： 而没有聪明脑袋的动物就不能完成复杂的任务？是 2)分布式计算.蚁群算法是一种基于种群的算 不是只有聪明的脑袋”才能完成复杂的任务？若 法，具有本质并行性，易于并行实现： 是这样，那么脑袋是什么？是否都一定像人们现 3)易于与其他方法结合.蚁群算法很容易与多 在看到的那样？是否可以有其他形式？比如可否将 种启发式算法结合，以改善算法的性能， 整个蚁群看成一个“松散的脑袋”？因为人和蚂 虽然基本蚁群算法有许多优点，但是，这种算法 蚁都是从低等单细胞生物进化而来的.一个分支进 也存在一些缺陷，如：与其他方法相比，该算法一般 化成像人这样的大型动物包括其中的脑袋)，另一 需要较长的搜索时间，基本蚁群算法的复杂度可以 分支进化成像蚂蚁一样的蚁群.两者的不同在于前 反映这一点；而且该方法容易出现停滞现象(stagna 者脑袋)是连通的，后者蚁群)是离散的.在这样 tion behavir),即搜索进行到一定程度后，所有个体 所发现的解完全一致，不能对解空间进一步进行搜 的看法下，一个蚂蚁就相当于脑中的一个细胞神 索，不利于发现更好的解 经元)，蚂蚁之间的信息交流，就相当于大脑中各个 22蚁群聚类模型 细胞之间的联接.人工智能中用人工神经网络的技 观察可以发现.蚂蚁特别讲究卫生，它们能够将 术来模拟人的大脑中某些功能，从而也可以用某种 蚂蚁巢穴中的尸体聚集成几堆.如果一个地方己经 数学的模型来模拟“群体智能”，用来说明蚂蚁筑巢 有一些尸体的聚集，那么它将吸引蚂蚁将其余的尸 的功能.不同点在于一个是用固定连接的神经网络 体放在这里，越聚越多，最终形成几个较大的尸体的 来模拟，另一个是用离散随机连接的神经网络来模 聚集堆.Deneubourg等s人对上述现象提出了解释， 拟.正是以这种想法为出发点，安徽大学人工智能研 并提出了一个基本模型(basic model,BM),这种模 究所提出“群体智能的数学模型，并研究了其基 型主要是基于对于单只蚂蚁拾起、放下物体的行为 本性质泪前研究“群体智能的方法多是将“群体” 方式进行建模.一只随机移动的无负载蚂蚁在遇到 看成为一个多Aent系统进行研究.他们是从一个 一个物体时，周围与这个物体相同的物体越少，则拾 全新的观点出发，进行“群体智能的研究.下面简 起这个物体的概率越大：一只随机移动的有负载蚂 单介绍这方面的工作. 蚁如果周围的与所背负物体相同的物体越多，则放 假设群体智能是指由众多简单的个体组成的 下这个物体的概率越大.这样可以保证不破坏大堆 群体，若具有能通过之间的简单合作来完成一个整 的物体，并且能够收集小堆的物体.实验表明，这种 体的任务的能力，则称该群体具有“群体智能” 方法可以将相同种类的物体聚集在一起 “简单个体就是指单个个体只具有很简单的 后来，Lmer和Faieta将Deneubourg等人的 能力，这种能力用某一简单功能函数来表示就像 BM推广应用到数据分析.主要思想是将待聚类数 神经元一样，用一种很简单的功能函数来表示 据初始随机散放在一个二维平面内，然后在这个平 “简单合作能力，就是指个体只能与其邻近的 面上产生一些虚拟的蚂蚁”这些蚂蚁的行为和上 个体进行某种简单的通讯和协同动作如几个蚂蚁 1994-2009 China Academie Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
新残留信息的浓度 ,而不是当所有蚂蚁完成对所有 n个城市的访问以后;在 Ant Density算法中 ,Δτk ij = Q;而在 Ant Quantity算法中 ,Δτk ij = Q dij ( dij表示城市 i 和 j的距离 ). 也就是说 ,在 Ant Density算法中 ,从城 市 i到 j的蚂蚁在路径上残留的信息浓度为一个与 路径无关的常量 Q. 而在 Ant Quantity算法中 ,以 dij 为城市 i到城市 j的距离 ,残留信息浓度为 Q / dij ,即 残留信息浓度会因为城市距离的减小而增大. 在以上算法中 Q、α、β、ρ的最佳组合可以由实 验经验确定 [ 2 ] . 相关研究表明 ,基本蚁群算法具有如下优点 : 1) 较强的鲁棒性. 对基本蚁群算法模型稍加修 改 ,便可以应用于其他问题; 2) 分布式计算. 蚁群算法是一种基于种群的算 法 ,具有本质并行性 ,易于并行实现; 3) 易于与其他方法结合. 蚁群算法很容易与多 种启发式算法结合 ,以改善算法的性能. 虽然基本蚁群算法有许多优点 ,但是 ,这种算法 也存在一些缺陷 ,如 :与其他方法相比 ,该算法一般 需要较长的搜索时间 ,基本蚁群算法的复杂度可以 反映这一点;而且该方法容易出现停滞现象 ( stagna2 tion behavior) ,即搜索进行到一定程度后 ,所有个体 所发现的解完全一致 ,不能对解空间进一步进行搜 索 ,不利于发现更好的解. 2. 2 蚁群聚类模型 观察可以发现 ,蚂蚁特别讲究卫生 ,它们能够将 蚂蚁巢穴中的尸体聚集成几堆. 如果一个地方已经 有一些尸体的聚集 ,那么它将吸引蚂蚁将其余的尸 体放在这里 ,越聚越多 ,最终形成几个较大的尸体的 聚集堆. Deneubourg等 [ 5 ]人对上述现象提出了解释 , 并提出了一个基本模型 ( basic model, BM ) ,这种模 型主要是基于对于单只蚂蚁拾起、放下物体的行为 方式进行建模. 一只随机移动的无负载蚂蚁在遇到 一个物体时 ,周围与这个物体相同的物体越少 ,则拾 起这个物体的概率越大; 一只随机移动的有负载蚂 蚁如果周围的与所背负物体相同的物体越多 ,则放 下这个物体的概率越大. 这样可以保证不破坏大堆 的物体 ,并且能够收集小堆的物体. 实验表明 ,这种 方法可以将相同种类的物体聚集在一起. 后来 , Lumer和 Faieta [ 6 ]将 Deneubourg等人的 BM推广应用到数据分析. 主要思想是将待聚类数 据初始随机散放在一个二维平面内 ,然后在这个平 面上产生一些虚拟的“蚂蚁 ”. 这些蚂蚁的行为和上 面 BM中所描述的蚂蚁行为相似. 不同之处在于 ,它 们不是观察当前所背负的物体与周围的物体是否相 同 ,而是判断是否相似 ,这样最终能够将相似的数据 聚为一类. 2. 3 蚁群群体智能模型 蚂蚁群最令人惊叹的能力是“筑巢 ”, 这类“群 体智能“是自然界中普遍存在的现象 ,其中道理人 们并不清楚 ,但人们可以对这种现象进行“唯象 ”地 建模研究. 蚂蚁能筑巢 ,人们可能感到很惊讶 ,而看到人建 筑高楼大厦并不感到惊奇. 这也许是因为 ,人们认为 人有一个聪明的脑袋 , 故能设计建筑高楼大厦. 那 么 ,为什么有一个聪明的脑袋 ,就能完成各种工作 , 而没有聪明脑袋的动物就不能完成复杂的任务 ? 是 不是只有“聪明的脑袋 ”才能完成复杂的任务 ? 若 是这样 ,那么“脑袋 ”是什么 ? 是否都一定像人们现 在看到的那样 ? 是否可以有其他形式 ? 比如可否将 整个“蚁群 ”看成一个“松散的脑袋 ”? 因为人和蚂 蚁都是从低等单细胞生物进化而来的. 一个分支进 化成像人这样的大型动物 (包括其中的脑袋 ) ,另一 分支进化成像蚂蚁一样的蚁群. 两者的不同在于前 者 (脑袋 )是连通的 ,后者 (蚁群 )是离散的. 在这样 的看法下 ,一个蚂蚁就相当于脑中的一个细胞 (神 经元 ) ,蚂蚁之间的信息交流 ,就相当于大脑中各个 细胞之间的联接. 人工智能中用人工神经网络的技 术来模拟人的大脑中某些功能 ,从而也可以用某种 数学的模型来模拟“群体智能 ”,用来说明蚂蚁筑巢 的功能. 不同点在于一个是用固定连接的神经网络 来模拟 ,另一个是用离散随机连接的神经网络来模 拟. 正是以这种想法为出发点 ,安徽大学人工智能研 究所 [ 7 ]提出“群体智能 ”的数学模型 ,并研究了其基 本性质 (目前研究“群体智能“的方法多是将“群体 ” 看成为一个多 Agent系统进行研究. 他们是从一个 全新的观点出发 ,进行“群体智能 ”的研究 ). 下面简 单介绍这方面的工作. 假设 群体智能是指由众多简单的个体组成的 群体 ,若具有能通过之间的简单合作来完成一个整 体的任务的能力 ,则称该群体具有“群体智能 ”. “简单个体 ”就是指单个个体只具有很简单的 能力 ,这种能力用某一简单功能函数来表示 (就像 神经元一样 ,用一种很简单的功能函数来表示 ). “简单合作 ”能力 ,就是指个体只能与其邻近的 个体进行某种简单的通讯和协同动作 (如几个蚂蚁 第 3期 高 玮 :新型智能仿生模型 ———蚁群模型 ·273·
·274· 智能系统学报 第3卷 共同搬动一个物体，这与前向神经网络中各神经元 介绍 只与其前面一层中的神经元可以通讯一样人.或通 针对基本蚁群算法收敛速度慢、容易出现停滞 过环境间接与其他个体通讯如一蚂蚁将外激素留 等缺陷，许剑等提出一种新的算法模型一带侦察 在环境中，而其他的蚂蚁可从留下的外激素中得到 子群的蚁群系统，该算法从整个蚁群中分离出一部 一些有用的信息. 分蚂蚁组成侦察子群，在优化过程中侦察子群以一 这样，就可以建立群体智能的数学模型 定概率做随机搜索，这样可以提高了解的多样性：同 设有一群体，包含有n个个体各个体的能力 时，在信息素更新策略上同时使用本代和全局最优 是相同的)，每个个体具有一个能力￡即每个个体 蚂蚁，兼顾了本代和历史的搜索成果.仿真研究证明 能完成某一函数运算f其次，每个个体能与其邻近 该算法可以有效的预防早熟现象，而且能够大大加 的个体进行通讯”，即将一信息传给对方.个体的 快收敛速度.许殿等提出了回归蚁群算法，该算 行动是随机的、并行进行的.个体接收终止的指令， 法通过外加牵引力使得蚂蚁按照城市的整体分布规 就停止工作.这时，整个任务就完成 律寻优，增加了算法的全局收敛性.并通过圈地算 在这种假设下，“蚁群就像一个随机连接的神 法，减少了局部搜索的计算量.熊伟清等提出了 经网络，若神经网络能模拟人的某些“智能“能力. 一种二进制蚁群算法，该算法从生物进化角度把将 那么，上述的随机连接的神经网络，就有可能模拟 群体中的每个个体看成一个神经元，提出一个模拟 松散的脑袋”—群体智能 蚁群的二元网络，并采用二进制编码模拟单个蚂蚁 24其他模型 该算法证明具有很好的收敛速度和稳定性Kong 241蚂蚁搬大食物模拟 Min等Iusl也提出了binary ant system(BAS),该算法 蚂蚁同心协进行搬运大食物，是见得最多的蚂 设计了一种独特的在二进制空间分配信息素的方 蚁行为，有人以此为蓝本设计出几个机器人共同推 法，允许在空间产生不可行解，又设计了一种修复算 盒子的算法？其基本算法为 子来处理不可行解.Jiejin Cai等提出了chaotic 1)一群蚂蚁随机出发找食物： ant swam opti ization(CASO),该算法把混沌思想 2)遇到大食物，先调整方向使食物处在自己 容入蚂蚁的自适应行为模拟中，可以解决复杂动态 和目标之间： 系统问题.Bemd Scheuemann等s为了硬件实现的 3)推动食物： 方便，提出了一种Counter-based ACO,该算法允许 4)群体推动，计算其合力 蚂蚁穿过处理元件的管路，为此设计了一种新的信 美国阿尔伯塔大学设计出几个小机器人共同推 息素编码方法及定义蚂蚁次序的方法.陈岭等6提 盒子的实验 出了一种自适应并行蚁群算法，该算法提出了一种 242任务分配问题模拟 基于适应度和基于距离选择的2种不同的信息交流 在蚁群中，蚂蚁的职责分工明确蚁皇管生男 策略，使得各处理机自适应地选择与之进行信息交 育女、工蚁管干活、兵蚁管保卫)，各司其职.借助蚂 换的处理机，然后采用自适应的更新策略进行信息 蚁分工合作的特点，人们设计了求解任务分配问题 素的更新，为了增强该算法的搜索能力，还根据解的 的蚂蚁算法，并应用于工厂中汽车喷漆问题).如 多样性给出了自适应地调节处理机之间的信息交流 美国西北大学将蚂蚁算法用于卡车厂油漆车间，负 周期的方法.另外，W.Traili等针对动态连续优 责给离开装配线的卡车上漆的工作安排.他们采取 化问题，提出了一种新型算法模型.MD.Tok 工人分组，各组只喷一种颜色，只有当某小组任务特 也提出了一种进行全局优化的新蚁群算法模型.B. 别紧张时，才分配另一小组前去帮助.通过这种设计 MTLin等J根据真实蚁群行为的信息分享机 后工厂各车间改变颜色的次数更少，从而提高了整 制，提出了一种新的算法模型 体的生产率 3蚁群模型的典型应用 25蚁群模型研究的新进展 为了提高基本蚁群模型的搜索效率，近年来众 蚁群优化算法是蚁群模型中应用最广泛的模型 多学者进行蚁群模型的改进研究，提出了大量新型 算法之一，它在解决很多组合问题(combination opti- 蚁群模型算法，下面对这方面的一些研究进行简单 m ization problem)上都取得理想的效果.其中，2个 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
共同搬动一个物体 ,这与前向神经网络中各神经元 只与其前面一层中的神经元可以通讯一样 ). 或通 过环境间接与其他个体通讯 (如一蚂蚁将外激素留 在环境中 ,而其他的蚂蚁可从留下的外激素中得到 一些有用的信息 ). 这样 ,就可以建立“群体智能 ”的数学模型. 设有一群体 ,包含有 n个个体 (各个体的能力 是相同的 ) ,每个个体具有一个能力 f. 即每个个体 能完成某一函数运算 f. 其次 ,每个个体能与其邻近 的个体进行“通讯 ”,即将一信息传给对方. 个体的 行动是随机的、并行进行的. 个体接收终止的指令 , 就停止工作. 这时 ,整个任务就完成. 在这种假设下 ,“蚁群 ”就像一个随机连接的神 经网络 ,若神经网络能模拟人的某些“智能“能力. 那么 ,上述的随机连接的神经网络 , 就有可能模拟 “松散的脑袋 ”———群体智能. 2. 4 其他模型 2. 4. 1 蚂蚁搬大食物模拟 蚂蚁同心协进行搬运大食物 ,是见得最多的蚂 蚁行为 ,有人以此为蓝本设计出几个机器人共同推 盒子的算法 [ 8 ] . 其基本算法为 1)一群蚂蚁随机出发找食物; 2)遇到大食物 ,先调整方向 (使食物处在自己 和目标之间 ) ; 3)推动食物; 4)群体推动 ,计算其合力. 美国阿尔伯塔大学设计出几个小机器人共同推 盒子的实验. 2. 4. 2 任务分配问题模拟 在蚁群中 , 蚂蚁的职责分工明确 (蚁皇管生男 育女、工蚁管干活、兵蚁管保卫 ) ,各司其职. 借助蚂 蚁分工合作的特点 ,人们设计了求解任务分配问题 的蚂蚁算法 ,并应用于工厂中汽车喷漆问题 [ 9 ] . 如 美国西北大学将蚂蚁算法用于卡车厂油漆车间 ,负 责给离开装配线的卡车上漆的工作安排. 他们采取 工人分组 ,各组只喷一种颜色 ,只有当某小组任务特 别紧张时 ,才分配另一小组前去帮助. 通过这种设计 后工厂各车间改变颜色的次数更少 ,从而提高了整 体的生产率. 2. 5 蚁群模型研究的新进展 为了提高基本蚁群模型的搜索效率 ,近年来众 多学者进行蚁群模型的改进研究 ,提出了大量新型 蚁群模型算法 ,下面对这方面的一些研究进行简单 介绍. 针对基本蚁群算法收敛速度慢、容易出现停滞 等缺陷 ,许剑等 [ 10 ]提出一种新的算法模型 —带侦察 子群的蚁群系统 ,该算法从整个蚁群中分离出一部 分蚂蚁组成侦察子群 ,在优化过程中侦察子群以一 定概率做随机搜索 ,这样可以提高了解的多样性;同 时 ,在信息素更新策略上同时使用本代和全局最优 蚂蚁 ,兼顾了本代和历史的搜索成果. 仿真研究证明 该算法可以有效的预防早熟现象 ,而且能够大大加 快收敛速度. 许殿等 [ 11 ]提出了回归蚁群算法 ,该算 法通过外加牵引力使得蚂蚁按照城市的整体分布规 律寻优 ,增加了算法的全局收敛性. 并通过圈地算 法 ,减少了局部搜索的计算量. 熊伟清等 [ 12 ]提出了 一种二进制蚁群算法 ,该算法从生物进化角度把将 群体中的每个个体看成一个神经元 ,提出一个模拟 蚁群的二元网络 ,并采用二进制编码模拟单个蚂蚁 , 该算法证明具有很好的收敛速度和稳定性 Kong M in等 [ 13 ]也提出了 binary ant system (BAS) ,该算法 设计了一种独特的在二进制空间分配信息素的方 法 ,允许在空间产生不可行解 ,又设计了一种修复算 子来处理不可行解. Jiejin Cai等 [ 14 ]提出了 chaotic ant swarm op tim ization (CASO ) ,该算法把混沌思想 容入蚂蚁的自适应行为模拟中 ,可以解决复杂动态 系统问题. Bernd Scheuermann等 [ 15 ]为了硬件实现的 方便 ,提出了一种 Counter2based ACO,该算法允许 蚂蚁穿过处理元件的管路 ,为此设计了一种新的信 息素编码方法及定义蚂蚁次序的方法. 陈岭等 [ 16 ]提 出了一种自适应并行蚁群算法 ,该算法提出了一种 基于适应度和基于距离选择的 2种不同的信息交流 策略 ,使得各处理机自适应地选择与之进行信息交 换的处理机 ,然后采用自适应的更新策略进行信息 素的更新. 为了增强该算法的搜索能力 ,还根据解的 多样性给出了自适应地调节处理机之间的信息交流 周期的方法. 另外 , W. Traili等 [ 17 ]针对动态连续优 化问题 ,提出了一种新型算法模型. M. D. Toksar [ 18 ] 也提出了一种进行全局优化的新蚁群算法模型. B. M. T. L in等 [ 19 ]根据真实蚁群行为的信息分享机 制 ,提出了一种新的算法模型. 3 蚁群模型的典型应用 蚁群优化算法是蚁群模型中应用最广泛的模型 算法之一 ,它在解决很多组合问题 ( combination op ti2 m ization p roblem )上都取得理想的效果. 其中 , 2个 ·274· 智 能 系 统 学 报 第 3卷