第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卷
第3期 高玮：新型智能仿生模型蚁群模型 ·275 比较著名的组合问题QAP问题和JSP问题，对 是集中分布，利用蚁群算法所得呼叫拒绝率和平均 典型蚁群算法作相应调整就可以比较好地解决问 路径长度均小于最小负载法结果，在呼叫符合集中 题.除此以外，蚁群算法在其他实际问题的解决中也 分布时，蚁群算法所得呼叫拒绝率低于最短路径法 取得一定的进展.如大规模集成电路中的综合布线 35新应用领域的开发 以及电信网络中的路由布置问题等方面得到了大量 在传统的应用领域得到大量应用后，近年来，蚁 应用 群算法已经被应用到大量其他领域，包括经济、人 31QAP问题 文、生物、土木工程等，并表现出了良好的应用前景， QAP问题的目标函数可以用一个对称矩阵来 以下对一些典型应用进行简单介绍.在土木工程领 描述.蚁群算法基于它和TSP问题的相似性来解决 域，高玮等24把蚁群算法引入复杂的土木工程优化 问题2).QAP问题的目标函数矩阵S通过距离向量 问题中，解决了地下洞室群的施工排序问题.在电工 D和流向量F的组合而组成： 领域，赵强等25采用蚁群算法进行配电线网络的优 Sak d;XF 化问题.在经济分析领域，Jiejin Cai等把蚁群算 蚂蚁根据可见度信息n来选择下一个节点.其 法用于发电机系统的经济分配问题.在医学领域领 中几=1S,矩阵S的元素值用作启发式因子 域，W J.Gutjahra等I21把蚁群算法用于澳大利亚的 32JSP问题 护士日程安排，对护理行程进行了合理规划.在生物 JSP问题可以用一个加权图描述：每条边的权 信息学分析中，Christian Blum等I2把蚁群算法用 值用参数对(T,几表示.信息Tx和可见度几是通 于DAN排序分析中.在工程设计领域，L.dos S 过最长进程时间或者最短完成时间等要求决定.蚂 Coetho等2采用蚁群算法及混沌优化的融合算法 蚁遍历节点的顺序就是相应的解决答案2) 解决了工程设计问题.在水资源领域，AC.Zecchi- 在解决10×10和1015的JSP问题中，蚂蚁 na等2把蚁群算法应用于水资源的分配问题.在 算法解与最优解的误差在10%之内，这是一个相当 数据分析方面，Sung-Shun W eng等[o采用蚁群算法 不错的结果 进行了数据挖掘时间序列的分割问题.在工程可靠 33大规模集成电路综合布线问题 度设计领域，Jian-Hua Zhao等IB1把多目标蚁群算法 大规模集成电路中的综合布线可以采用蚁群算 用于工程系统概念设计的可靠度优化问题研究，得 法的思想来进行2在布线过程中，各个引脚对蚂 到了较好的效果.在人文科学领域，肖智等提出 蚁的引力可根据引力函数来计算.各个线网Agent 了一种在我国RD经费投入预测中的应用蚁群算 根据启发策略，象蚁群一样在开关盒网格上爬行.所 法的新方法」 经之处便布上一条金属线.历经一个线网的所有引 以上可以发现，由于蚁群算法的良好性能，使得 脚之后，线网便布通了.给定一个开关盒布线问题， 这种算法已经在众多领域得到了广泛应用」 问题的计算量是固定不变的.主要由算法的迭代次 4蚁群模型的比较研究 数决定，而迭代次数由Agents的智能和开关盒问题 本身的性质确定.蚁群算法本身的并行法使之比较 为了对蚁群模型的特点进行深入分析，有必要 适合于解决布线问题」 把它和其他几种仿生计算模型进行比较研究，这里 34电信网络路由问题 主要研究蚁群算法、粒子群算法、免疫算法及进化算 电信网络中的路由是通过路由表进行的.在每 法等主要仿生算法的相同点及不同点。 个节点的路由表中，对每个目的节点都列出了与该 粒子群算法是美国学者J.Kennedy.R Eber 节点相连的节点.当有数据包到达时，通过查询路由 hart等于20世纪90年代初提出的一种新仿生算 表可知道下一个将要到达的节点.首先对路由表中 法)，它主要来源于对空中鸟群捕食行为的模拟 的信息素强度进行初始化，在节点x,以节点为目 免疫算法是20世纪90年代初H Bersini及 的地址，邻节点为h处的信息素强度为T=1/dm, E Varela提出的一种来源于模拟生物免疫系统的仿 d为从x经节点h到节点路径的最小费用值.然 生优化算法 后周期性地释放蚂蚁来进行路由，并修改相应的信 进化算法[3是最早提出的一种仿生算法，它是 息素值).仿真结果表明，无论呼叫是均匀分布还 模拟生物的遗传进化过程而提出的一种优化算法， 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
比较著名的组合问题 ———QAP问题和 JSP问题 ,对 典型蚁群算法作相应调整就可以比较好地解决问 题. 除此以外 ,蚁群算法在其他实际问题的解决中也 取得一定的进展. 如大规模集成电路中的综合布线 以及电信网络中的路由布置问题等方面得到了大量 应用. 3. 1 QAP问题 QAP问题的目标函数可以用一个对称矩阵来 描述. 蚁群算法基于它和 TSP问题的相似性来解决 问题 [ 20 ] . QAP问题的目标函数矩阵 S通过距离向量 D 和流向量 F 的组合而组成 : Sih = di ×Fh . 蚂蚁根据可见度信息 ηih来选择下一个节点. 其 中 ηih = 1 /Sih ,矩阵 S的元素值用作启发式因子. 3. 2 JSP问题 JSP问题可以用一个加权图描述 :每条边的权 值用参数对 {τk l ,ηk l }表示. 信息 τk l和可见度 ηk l是通 过最长进程时间或者最短完成时间等要求决定. 蚂 蚁遍历节点的顺序就是相应的解决答案 [ 21 ] . 在解决 10 ×10和 10 ×15的 JSP问题中 ,蚂蚁 算法解与最优解的误差在 10%之内 ,这是一个相当 不错的结果. 3. 3 大规模集成电路综合布线问题 大规模集成电路中的综合布线可以采用蚁群算 法的思想来进行 [ 22 ] . 在布线过程中 ,各个引脚对蚂 蚁的引力可根据引力函数来计算. 各个线网 Agent 根据启发策略 ,象蚁群一样在开关盒网格上爬行. 所 经之处便布上一条金属线. 历经一个线网的所有引 脚之后 ,线网便布通了. 给定一个开关盒布线问题 , 问题的计算量是固定不变的. 主要由算法的迭代次 数决定 ,而迭代次数由 Agents的智能和开关盒问题 本身的性质确定. 蚁群算法本身的并行法使之比较 适合于解决布线问题. 3. 4 电信网络路由问题 电信网络中的路由是通过路由表进行的. 在每 个节点的路由表中 ,对每个目的节点都列出了与该 节点相连的节点. 当有数据包到达时 ,通过查询路由 表可知道下一个将要到达的节点. 首先对路由表中 的信息素强度进行初始化 ,在节点 x,以节点 i为目 的地址 ,邻节点为 h处的信息素强度为 τih = 1 / dih , dih为从 x经节点 h到节点 i路径的最小费用值. 然 后周期性地释放蚂蚁来进行路由 ,并修改相应的信 息素值 [ 23 ] . 仿真结果表明 ,无论呼叫是均匀分布还 是集中分布 ,利用蚁群算法所得呼叫拒绝率和平均 路径长度均小于最小负载法结果 ,在呼叫符合集中 分布时 ,蚁群算法所得呼叫拒绝率低于最短路径法. 3. 5 新应用领域的开发 在传统的应用领域得到大量应用后 ,近年来 ,蚁 群算法已经被应用到大量其他领域 ,包括经济、人 文、生物、土木工程等 ,并表现出了良好的应用前景 , 以下对一些典型应用进行简单介绍. 在土木工程领 域 ,高玮等 [ 24 ]把蚁群算法引入复杂的土木工程优化 问题中 ,解决了地下洞室群的施工排序问题. 在电工 领域 ,赵强等 [ 25 ]采用蚁群算法进行配电线网络的优 化问题. 在经济分析领域 , Jiejin Cai等 [ 14 ]把蚁群算 法用于发电机系统的经济分配问题. 在医学领域领 域 ,W J. Gutjahra等 [ 26 ]把蚁群算法用于澳大利亚的 护士日程安排 ,对护理行程进行了合理规划. 在生物 信息学分析中 , Christian B lum 等 [ 27 ]把蚁群算法用 于 DAN排序分析中. 在工程设计领域 , L. dos S. Coelho等 [ 28 ]采用蚁群算法及混沌优化的融合算法 解决了工程设计问题. 在水资源领域 , A. C. Zecchi2 na等 [ 29 ]把蚁群算法应用于水资源的分配问题. 在 数据分析方面 , Sung2Shun W eng等 [ 30 ]采用蚁群算法 进行了数据挖掘时间序列的分割问题. 在工程可靠 度设计领域 , Jian2Hua Zhao等 [ 31 ]把多目标蚁群算法 用于工程系统概念设计的可靠度优化问题研究 ,得 到了较好的效果. 在人文科学领域 ,肖智等 [ 32 ]提出 了一种在我国 R&D经费投入预测中的应用蚁群算 法的新方法. 以上可以发现 ,由于蚁群算法的良好性能 ,使得 这种算法已经在众多领域得到了广泛应用. 4 蚁群模型的比较研究 为了对蚁群模型的特点进行深入分析 ,有必要 把它和其他几种仿生计算模型进行比较研究 ,这里 主要研究蚁群算法、粒子群算法、免疫算法及进化算 法等主要仿生算法的相同点及不同点. 粒子群算法是美国学者 J. Kennedy、R. Eber2 hart. 等于 20世纪 90年代初提出的一种新仿生算 法 [ 33 ] ,它主要来源于对空中鸟群捕食行为的模拟. 免疫算法是 20世纪 90年代初 H. Bersini. 及 F. Varela提出的一种来源于模拟生物免疫系统的仿 生优化算法 [ 34 ] . 进化算法 [ 35 ]是最早提出的一种仿生算法 ,它是 模拟生物的遗传进化过程而提出的一种优化算法. 第 3期 高 玮 :新型智能仿生模型 ———蚁群模型 ·275·
·276· 智能系统学报 第3卷 一般包括4种算法，分别为美国学者Hooland提出 以来，它已经得到了很大的发展，在短短10年时间 的遗传算法(genetic algorithm),Fogel提出的进化规 里己发展出一个庞大的算法体系，己被应用于几乎 划(evolutionary pogrmming)6),Koza提出的遗传 科学的各个领域.尽管研究及应用的时间不长，但它 程序设计（genetic programm ing)及德国学者 己表现了非常良好的应用前景 Schwefe提出的进化策略(evoution stratey)). 参考文献： 通过对算法机理及运行过程的研究39)，可以 发现4种算法的异同点可以归纳如下 [1李衍达.信息科学与生物之谜[J小世界科技研究与发 相同点： 展，2000,21(3)：26-30 1)均为概率全局优化算法，2)均为随机优化算 LI Yanda Infomation science and the mystery of biology [J ]Study and Development ofWorld Science and Technol- 法；3)均为协同优化算法；4)均与求解问题的数学 0y,2000,21(3):26-30 性质无关，5)均为本质并行算法；6)均为很强的鲁 [2 ]DOR IGO M,MAN IEZZO V,COLORNI A.Ant system: 棒算法」 optm ization by a cobny of cooperaing Agents [J ]IEEE 不同点： Trans on9MC,1996,26(1):29-41. 1)问题的表示不同.进化算法中问题的表示必 [3 ]DOR IGO M,MAN IEZZ0 V,COLORNIA Positive feed- 须采用编码的形式，而其他几种算法无须编码；2) back as a search strategy[R]91016,Politecnico diMila- 求解操作过程不同.进化算法中求解过程一般需要 no,ay,1991 交叉、变异等基因操作；而蚁群算法的操作为概论移 [4 ]DOR IGO M,DICARO G The ant colony opti ization me- 动及信息素挥发等，信息素操作；粒子群算法则采用 ta-heuristic C ]//New keas in Opti ization England: McGraw-Hill,1999:11-32 粒子概论移动等粒子操作：免疫算法则采用抗体及 [5 ]DENEUBOURG JL,OSS C.Collective pattems and deci 抗原操作；3)数学基础不同.作为最早的仿生优化 sion making [J ]Ethobgy,Ecology and Evolution,1989 算法，进化算法的数学理论研究较多，既有证明优化 (1):295-311 原理的“积木块理论”，又有证明收敛性的马尔可夫 [6 ]LUMER E D,FA IETA B.D iversity and adaptation in popu- 链理论.而蚁群算法的理论研究不多，仅有的就是对 latons of clustering ants[C]//Proc of 3 rd Confon Simula- 算法收敛性的研究【2).粒子群算法的数学基础非常 tion of Adaptive Behavior Cambridge:M Ir Press,1994: 薄弱，目前还没有具有普遍意义的理论研究.免疫算 501-508 法尽管有简单的数学模型，但该模型的功能很差： [7张铃，程军盛.松散的脑袋—群体智能的数学模型 4)提出的初衷不同.进化算法中的遗传算法及进化 [J]模式识别与人工智能，2003,16(1)：1-5 规划提出的初衷是解决自适应系统问题及自动机预 ZHANG L ing,CHENG Junsheng Losing brainsthe math- ematic model of swam intelligence [J].Pattem Recognition 测问题.而蚁群算法的提出目的是解决如TSP一类 and Artificial Intelligence,2003,16(1):1-5. 的组合优化问题.粒子群算法及免疫算法是解决一 [8 ]DENEUBOURGL,GOSS C,FRANKS N,et al The dy- 般优化问题 nam ics of collective sorting robot-like ants and ant-like ro- 5结束语 bots[C]//Proceedings of the first intemational conference on smulation of adaptive behavor on from anmals to ani- 蚂蚁是一种人们常见的昆虫，它的特点是单个 mates Cambridge:MIT Press,1991:356-367 个体的行为极其简单，而整个群体却能表现非常复 [9]BONABEAU E,THERAULAZ G,DENEUBOURG J L 杂的智能行为.通过研究可以发现蚁群的集成智能 Quantitative study of the fixed threshold model or the regu- 来自于个体间的信息正反馈，它们可以解决非常复 lation of division of labour in insect societies [C]//Pro- 杂的路径优化问题.向大自然学习是人们解决实际 ceedings of Biobgical Sciences London:The Royal Socie- y,1996:1565-1569 问题的一条很好的途径.组合优化问题是自然界常 「10许剑，吕志民，徐金栋.带有侦察子群的蚁群算法 见的一种复杂问题之一.而路径优化又是一种最典 [J]北京科技大学学报，2006,28(8)：794-798 型的组合优化问题，因此，向蚁群学习可以提出解决 XU Jian,LU'Zhi in,XU J indong An ant system with 复杂组合优化问题的理想途径.蚁群模型的提出就 scouting subgroup [J ]Joumal ofUniversity of Science and 是这种思想的具体实现.自从1991年蚁群模型提出 Technobgy Beijing.2006,28(8):794-798 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
一般包括 4种算法 ,分别为美国学者 Hooland提出 的遗传算法 ( genetic algorithm) , Fogel提出的进化规 划 ( evolutionary p rogramm ing) [ 36 ] , Koza提出的遗传 程序 设 计 ( genetic p rogramm ing) [ 37 ] 及 德 国 学 者 Schwefel提出的进化策略 ( evolution strategy) [ 38 ] . 通过对算法机理及运行过程的研究 [ 39241 ] ,可以 发现 4种算法的异同点可以归纳如下. 相同点 : 1)均为概率全局优化算法 ; 2)均为随机优化算 法 ; 3)均为协同优化算法 ; 4)均与求解问题的数学 性质无关 ; 5)均为本质并行算法 ; 6)均为很强的鲁 棒算法. 不同点 : 1)问题的表示不同. 进化算法中问题的表示必 须采用编码的形式 ,而其他几种算法无须编码 ; 2) 求解操作过程不同. 进化算法中求解过程一般需要 交叉、变异等基因操作 ;而蚁群算法的操作为概论移 动及信息素挥发等 ,信息素操作 ;粒子群算法则采用 粒子概论移动等粒子操作 ;免疫算法则采用抗体及 抗原操作 ; 3)数学基础不同. 作为最早的仿生优化 算法 ,进化算法的数学理论研究较多 ,既有证明优化 原理的“积木块理论 ”,又有证明收敛性的马尔可夫 链理论. 而蚁群算法的理论研究不多 ,仅有的就是对 算法收敛性的研究 [ 42 ] . 粒子群算法的数学基础非常 薄弱 ,目前还没有具有普遍意义的理论研究. 免疫算 法尽管有简单的数学模型 ,但该模型的功能很差 ; 4)提出的初衷不同. 进化算法中的遗传算法及进化 规划提出的初衷是解决自适应系统问题及自动机预 测问题. 而蚁群算法的提出目的是解决如 TSP一类 的组合优化问题. 粒子群算法及免疫算法是解决一 般优化问题. 5 结束语 蚂蚁是一种人们常见的昆虫 ,它的特点是单个 个体的行为极其简单 ,而整个群体却能表现非常复 杂的智能行为. 通过研究可以发现蚁群的集成智能 来自于个体间的信息正反馈 ,它们可以解决非常复 杂的路径优化问题. 向大自然学习是人们解决实际 问题的一条很好的途径. 组合优化问题是自然界常 见的一种复杂问题之一. 而路径优化又是一种最典 型的组合优化问题 ,因此 ,向蚁群学习可以提出解决 复杂组合优化问题的理想途径. 蚁群模型的提出就 是这种思想的具体实现. 自从 1991年蚁群模型提出 以来 ,它已经得到了很大的发展 ,在短短 10年时间 里已发展出一个庞大的算法体系 ,已被应用于几乎 科学的各个领域. 尽管研究及应用的时间不长 ,但它 已表现了非常良好的应用前景. 参考文献 : [ 1 ]李衍达. 信息科学与生物之谜 [J ]. 世界科技研究与发 展 , 2000, 21 (3) : 26230. L I Yanda. Information science and the mystery of biology [J ]. Study and Development ofWorld Science and Technol2 ogy, 2000, 21 (3) : 26230. [ 2 ] DOR IGO M, MAN IEZZO V, COLORN I A. Ant system: op timization by a colony of cooperaing Agents[ J ]. IEEE Trans on SMC, 1996, 26 (1) : 29241. [ 3 ]DOR IGO M, MAN IEZZO V, COLORN I A. Positive feed2 back as a search strategy[ R ]. 912016, Politecnico diM ila2 no, Italy, 1991. [ 4 ]DOR IGO M, D I CARO G. The ant colony op tim ization me2 ta2heuristic [ C ] / /New Ideas in Op timization. England: McGraw2H ill, 1999: 11232. [ 5 ]DENEUBOURG J L, GOSS C. Collective patterns and deci2 sion making [ J ]. Ethology, Ecology and Evolution, 1989 (1) : 2952311. [ 6 ]LUMER E D, FA IETA B. D iversity and adap tation in popu2 lations of clustering ants[C ] / /Proc of 3 rd Conf on Simula2 tion of Adap tive Behavior. Cambridge: M IT Press, 1994: 5012508. [ 7 ]张 铃 , 程军盛. 松散的脑袋 ———群体智能的数学模型 [J ]. 模式识别与人工智能 , 2003, 16 (1) : 125. ZHANG Ling, CHENG Junsheng. Losing brains—the math2 ematic model of swarm intelligence[J ]. Pattern Recognition and A rtificial Intelligence, 2003, 16 (1) : 125. [ 8 ]DENEUBOURG L, GOSS C, FRANKS N, et al. The dy2 namics of collective sorting robot2like ants and ant2like ro2 bots[ C ] / /Proceedings of the first international conference on simulation of adap tive behavior on from animals to ani2 mates. Cambridge: M IT Press, 1991: 3562367. [ 9 ] BONABEAU E, THERAULAZ G, DENEUBOURG J L. Quantitative study of the fixed threshold model for the regu2 lation of division of labour in insect societies[ C ] / / Pro2 ceedings of Biological Sciences. London: The Royal Socie2 ty, 1996: 156521569. [ 10 ]许 剑 , 吕志民 , 徐金栋. 带有侦察子群的蚁群算法 [J ]. 北京科技大学学报 , 2006, 28 (8) : 7942798. XU Jian, LU¨Zhimin, XU Jindong. An ant system with scouting subgroup [J ]. Journal ofUniversity of Science and Technology Beijing, 2006, 28 (8) : 7942798. ·276· 智 能 系 统 学 报 第 3卷
第3期 高玮：新型智能仿生模型—蚁群模型 ·277 [11许殿，史小卫，程睿.回归蚁群算法[J1西安电 control for communications netorks[J ]J Artificial Intel- 子科技大学学报，2005,32(6)：944947 1 igence Res.1998,9:317-365 XU Dian,SH IXiaowei,CHENG Rui Retumed ant algo- [24高玮，郑颖人.蚁群算法及其在洞群施工优化中的应用 rithm [J ]Joumal of Xidian University,2005,32(6): [J]岩石力学与工程学报，2002,21(4)：471-474 944-947 GAO Wei,ZHENG Yingren Ant colony algorithm and its [12熊威清，魏平.二进制蚁群进化算法[J]自动化学 applications in optm ization of underground groups[J] 报，2007,33(3)：259-264 Joumal of China Rock Mechanics and Rock Engineering. XDNGWeiqing,WEI Ping Binary ant cobny evolution- 2002,21(4):471-474 ary algorithm [Acta Aubmatica Sinica,2007,33(3): [25赵强，敬东，李正.蚁群算法在配电网规划中的 259-264 应用[J]电力自动化设备，2003,23(2)：52-54 [13 ]KONGMin,TIN Peng,KAO Yucheng A new ant col- ZHAO Qiang.JNG Dong.LI Zheng Application of ant ny optm ization algorithm for the multidmensional Knap- colny algorithm in map of power lines[J].Electric Power sack problem [J ]Computers and Operations Research, Automation Equipment,2003,23(2):52-54 2008.35(8):2672-2683 [26WALTER J G.MARU DN S R.An ACO algorithm for a [14 ]CA I Jiejin,MA Xiaogian,L IL ixiang.et al Chaotic ant dynam ic regional nurse-scheduling problem in austria[J ] swam optiization to econom ic dispatch J ]Electric Computers and Operations Research,2007,34(3):642- Power Systems Research,2007,77(10):1373-1380. 666 [15 ]BERND S,STEFAN J,MARTN M.Hardware-oriented [27]CHR STAN B,MATEU YV,MAR A J B.An ant colony ant colny opti ization [J ]Joumal of System s A rchitec- op tm ization algorithm for DNA sequenc ing by hybrid ization tue,2007,53(7):386-402 [J Computers and Operations Research,2008,35 [16陈岭，章春方.自适应的并行蚁群算法J]小型微 (11):3620-3635 型计算机系统，2006,27(9)：1695-1699 [28 ]LEANDRO Dos S C,VN ANA C M.Use of chaotic se- CHEN L ing,ZHANG Chunfang Adap tive parallel ant col quences in a biobgically insp ired algorithm for engineering ony algorithm [J ]Minimco Computer Systems,2006, design op tm ization [J].Expert System s with App lications, 27(9):1695-1699 2008,34(3):1905-1913 [17]TRA LIW,SARRY P A new charged ant cobny algo- [29]Za AARON C.ANGS R S Application of to ant colony rithm for continuous dynam ic optm ization [J ]Applied optm isation algorithms to water distribution system optm i Mathematics and Computation,2008,197(2):604 -613 zation[J]Mathematical and Computer Modelling,2006, [18 ]DURAN TM.A heuristic approach to find the gbbal opti- 44(5):451-468 mum of function J ]Joumal of Computational and Ap- [30 IW ENG Sungshun,L U Yuanhung Mining tme series data plied Mathematics,2007,209(2):160 -166 for segnentation by using ant colony optm izaton[J]Eu- [19]L NA BM T,LUB C Y,SHYUC SJ,et al Devebopment ropean Joumal of Operational Research,2006,173(3): of new features of ant cobny optm ization or flowshop 921-937. scheduling[J]Intemational Joumal of Production Eco- [31 ]ZHAO Jianhua,L U Zhaoheng,DAO M.Reliability opti- nom ics,2008,112(2):742-755. m izaton using multiobjective ant colony system app roaches (20]GAMBARDELLA L M,TA LLARD D,DOR KGO M.Ant [J ]Reliability Engineering and System Safety,2007,92 colonies for the QAP[J ]Joumal of the Operational Re- (1):109-120 search Society,1999,50(2):167-176 [32]消智，邹刚.基于蚁群算法的组合预测方法在我 [21]TEICH T.FSCHER M,VOGEL A,et al A new ant col- 国R&D经费投入中的应用[J]科技政策与管理， ony algorithm for the job shop scheduling problem C]// 2006(9):19-27 Proc of the Genetic and Evolutionary Computation Conf XO Zhi ZOU Gang The application of combining fore- 2001.San Fransisco:Morgan Kaufnann Publishers, casting based on ant colny algorithm to R&D funds in Chi 2001:803-808 na[J].Policy and Management of Science and Technol- [22]COELLO C A.CHRISTANSEN A D,AGU RRE A H y,2006(9):19-27 Ant colny system for the design of combinational bgic cir [33 ]KENN EDY J,EBERHARTR Particle swam op ti ization cuits[M ]Evolvable Systems From Bblgy to Hardware [C]//Proceedings of the IEEE Intemational Conference Edinburgh:Springer Verlag.2000:21-30 on Neural Netorks NJ:IEEE Service Center,1995: [23 ]DiCARO G,DOR IO M.Antnet distributed stignergetic 1942-1948 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
[ 11 ]许 殿 , 史小卫 , 程 睿. 回归蚁群算法 [J ]. 西安电 子科技大学学报 , 2005, 32 (6) : 9442947. XU D ian, SH I Xiaowei, CHENG Rui. Returned ant algo2 rithm [J ]. Journal of Xidian University, 2005, 32 ( 6 ) : 9442947. [ 12 ]熊威清 , 魏 平. 二进制蚁群进化算法 [J ]. 自动化学 报 , 2007, 33 (3) : 2592264. X IONGW eiqing, W EI Ping. Binary ant colony evolution2 ary algorithm [J ]. Acta Automatica Sinica, 2007, 33 (3) : 2592264. [ 13 ]KONGM in, TIAN Peng, KAO Yucheng. A new ant colo2 ny op timization algorithm for the multidimensional Knap2 sack p roblem [ J ]. Computers and Operations Research, 2008, 35 (8) : 267222683. [ 14 ]CA IJiejin, MA Xiaoqian, L I L ixiang, et al. Chaotic ant swarm op timization to econom ic dispatch [ J ]. Electric Power Systems Research, 2007, 77 (10) : 137321380. [ 15 ]BERND S, STEFAN J, MARTIN M. Hardware2oriented ant colony op tim ization [J ]. Journal of System s A rchitec2 ture, 2007, 53 (7) : 3862402. [ 16 ]陈 岭 , 章春方. 自适应的并行蚁群算法 [J ]. 小型微 型计算机系统 , 2006, 27 (9) : 169521699. CHEN L ing, ZHANG Chunfang. Adap tive parallel ant col2 ony algorithm [ J ]. M ini2mcro Computer Systems, 2006, 27 (9) : 169521699. [ 17 ] TRA IL IW , SIARRY P. A new charged ant colony algo2 rithm for continuous dynam ic op timization [ J ]. App lied Mathematics and Computation, 2008, 197 (2) : 604 2613. [ 18 ]DURAN TM. A heuristic app roach to find the global op ti2 mum of function [ J ]. Journal of Computational and Ap2 p lied Mathematics, 2007, 209 (2) : 160 2166. [ 19 ]L INA B M T, LUB C Y, SHYUC S J, et al. Development of new features of ant colony op timization for flowshop scheduling [ J ]. International Journal of Production Eco2 nom ics, 2008, 112 (2) : 742 2755. [ 20 ] GAMBARDELLA L M, TA ILLARD D, DOR IGO M. Ant colonies for the QAP [J ]. Journal of the Operational Re2 search Society, 1999, 50 (2) : 167 2176. [ 21 ]TEICH T, F ISCHER M, VOGEL A, et al. A new ant col2 ony algorithm for the job shop scheduling p roblem [ C ] / / Proc of the Genetic and Evolutionary Computation Conf 2001. San Fransisco: Morgan Kaufmann Publishers, 2001: 8032808. [ 22 ]COELLO C A, CHR ISTIANSEN A D, AGU IRRE A H. Ant colony system for the design of combinational logic cir2 cuits[M ]. Evolvable Systems: From Biology to Hardware. Edinburgh: Sp ringer Verlag, 2000: 21230. [ 23 ]D i CARO G, DOR IGO M. Antnet: distributed stigmergetic control for communications networks[J ]. J A rtificial Intel2 ligence Res, 1998, 9: 3172365. [ 24 ]高 玮 , 郑颖人. 蚁群算法及其在洞群施工优化中的应用 [J ]. 岩石力学与工程学报 , 2002, 21 (4) : 4712474. GAO W ei, ZHENG Yingren. Ant colony algorithm and its app lications in op tim ization of underground group s [ J ]. Journal of China Rock Mechanics and Rock Engineering, 2002, 21 (4) : 4712474. [ 25 ]赵 强 , 敬 东 , 李 正. 蚁群算法在配电网规划中的 应用 [J ]. 电力自动化设备 , 2003, 23 (2) : 52254. ZHAO Q iang, J ING Dong, L I Zheng. App lication of ant colony algorithm in map of power lines[J ]. Electric Power Automation Equipment, 2003, 23 (2) : 52254. [ 26 ]WALTER J G, MARU ION S R. An ACO algorithm for a dynamic regional nurse2scheduling p roblem in austria [J ]. Computers and Operations Research, 2007, 34 (3) : 6422 666. [ 27 ]CHR ISTIAN B, MATEU YV, MAR IA J B. An ant colony op timization algorithm forDNA sequencing by hybridization [ J ]. Computers and Operations Research, 2008, 35 (11) : 362023635. [ 28 ]LEANDRO Dos S C, V IV IANA C M. U se of chaotic se2 quences in a biologically insp ired algorithm for engineering design op tim ization[J ]. Expert System s with App lications, 2008, 34 (3) : 190521913. [ 29 ] Za AARON C, ANGUS R S. App lication of two ant colony op timisation algorithm s to water distribution system op tim i2 zation[J ]. Mathematical and ComputerModelling, 2006, 44 (5) : 4512468. [ 30 ]W ENG Sungshun, L IU Yuanhung. M ining time series data for segmentation by using ant colony op tim ization[J ]. Eu2 ropean Journal of Operational Research, 2006, 173 ( 3) : 9212937. [ 31 ] ZHAO Jianhua, L IU Zhaoheng, DAO M. Reliability op ti2 mization using multiobjective ant colony system app roaches [J ]. Reliability Engineering and System Safety, 2007, 92 (1) : 1092120. [ 32 ]肖 智 , 邹 刚. 基于蚁群算法的组合预测方法在我 国 R&D经费投入中的应用 [ J ]. 科技政策与管理 , 2006 (9) : 19227. X IAO Zhi, ZOU Gang. The app lication of combining fore2 casting based on ant colony algorithm to R&D funds in Chi2 na[J ]. Policy and Management of Science and Technolo2 gy, 2006 (9) : 19227. [ 33 ] KENNEDY J, EBERHART R. Particle swarm op tim ization [C ] / / Proceedings of the IEEE International Conference on Neural Networks. NJ: IEEE Service Center, 1995: 194221948. 第 3期 高 玮 :新型智能仿生模型 ———蚁群模型 ·277·
·278 智能系统学报 第3卷 [34 ]BERSN IH,VARELA F.Hints for adap tive problem sol DUAN Haibin,WANG Daobo,YU Xiufen Research on ving leamed from mmune netork [C]//Parallel Problem some novel bionic opti ization algorithms[J]Smulation Solving fiom Nature Berlin:Springer-Verlag,1991:343- of Computers.2007,24(3):169-172 354 [41正静，蒋珉.若干优化算法的运行分析比较[J] [35]RUHUL S,MASOUD M,YAO Xin Evolutionary optimi- 计算机仿真，2006,23(3)：149-153 zation [M ]New York:Kluwer Academ ic Publishers, WANG Jing.JANG Min Comparison of operational be- 2003:1-330 havior fr several optm ization algorithms[J ]Smulation [36 ]FOGEL D B,FOGEL L J.An introduction b evolutionary of Computers,2006,23(3):149-153 programm ing [C ]//European Conf on AE'95.Berlin: [42]STUTZLE T,DOR IO M A short convergence proof for a Sp ringer,.1996:21-33. class of ant cobny optiization algrithms[J]IEEE Transac- [37]JOHN R Koza Genetic programm ing on the programm ing tons on Evolutionary Computation,2002,6(4):358-365 of computers by means of natural selection [M ]Cam- bridge:MIT Press,1992:1-430 作者简介 [38 ]SCHW EFEL H P Evoluton and Optimum Seeking[M 高玮，男，1971年生，副教授，博 New York:W iley,1995:1-250. 士，主要研究方向为仿生系统模型、仿 [39]EMAD E,TAREK H,DONALD G Comparison among 生计算理论及其应用.目前已主持国家 five evolutionary-based optm ization algorithms[J].Ad- 自然科学基金、省自然科学基金、省教 vanced Engineering Infomatics,2005,19(1):43-53. 育厅项目等科研项目多项，发表论文 [40段海滨，王道波，于秀芬.几种新型仿生优化算法的比 100余篇，被SCkE等检索50余篇， 较研究[J1计算机仿真，2007,24(3)：169-172 2008年 EEE亚太地区计算智能与工业应用研讨会 IEEE Pac ific-Asa W orkshop on Com puta tional In telligence(IEEE PAC IIA 2008) 2008年亚太地区智能计算和工业应用研讨会(PACIA2008)将于2008年12月19日至20日在武汉 工程大学召开，本次会议的主题是“先进智能计算技术及其工业应用”。会议由美国电子和电气工程师协会 (EEE)和美国电子和电气工程协会工业电子分会支持(EEE IES),由武汉工程大学主办，武汉工程大学 计算机学院和电气学院承办。该会议已经进入EEE会议列表，录用论文将被EEE CS出版，并被著名检索 机构EI和STP检索。 会议议题不限于)： 神经网络与软计算 智能控制 机器学习 模式识别 人机交互 信息安全 信号处理 无线通信工业应用 重要日期 摘要截稿日期：2008-8-1 全文截稿日期：2008-8-1 论文录用通知日期：20089-15 交修订版截止日期：2008-10-1 会议网站：htp:/ww.paciia2008cm联系人：卢老师；联系电话：027-87992077 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
[ 34 ]BERSIN I H, VARELA F. H ints for adap tive p roblem sol2 ving learned from immune network [ C ] / /Parallel Problem Solving from Nature. Berlin: Sp ringer2Verlag, 1991: 3432 354. [ 35 ]RUHUL S, MASOUD M, YAO Xin. Evolutionary op timi2 zation [M ]. New York: Kluwer Academ ic Publishers, 2003: 12330. [ 36 ] FOGEL D B, FOGEL L J. An introduction to evolutionary p rogramm ing [ C ] / /European Conf on AE’95. Berlin: Sp ringer, 1996: 21233. [ 37 ]JOHN R Koza. Genetic p rogramm ing: on the p rogramm ing of computers by means of natural selection [M ]. Cam2 bridge: M IT Press, 1992: 12430. [ 38 ] SCHW EFEL H P. Evolution and Op timum Seeking[M ]. New York: W iley, 1995: 12250. [ 39 ] EMAD E, TAREK H, DONALD G. Comparison among five evolutionary2based op timization algorithm s [ J ]. Ad2 vanced Engineering Informatics, 2005, 19 (1) : 43253. [ 40 ]段海滨 , 王道波 , 于秀芬. 几种新型仿生优化算法的比 较研究 [J ]. 计算机仿真 , 2007, 24 (3) : 1692172. DUAN Haibin, WANG Daobo, YU Xiufen. Research on some novel bionic op tim ization algorithms[J ]. Simulation of Computers, 2007, 24 (3) : 1692172. [ 41 ]王 静 , 蒋 珉. 若干优化算法的运行分析比较 [J ]. 计算机仿真 , 2006, 23 (3) : 1492153. WANG Jing, J IANG M in. Comparison of operational be2 havior for several op timization algorithm s[ J ]. Simulation of Computers, 2006, 23 (3) : 1492153. [42 ] STUTZLE T, DOR IGO M. A short convergence proof for a class of ant colony optimization algorithms[J ]. IEEE Transac2 tions on Evolutionary Computation, 2002, 6 (4): 3582365. 作者简介 : 高 玮 ,男 , 1971年生 ,副教授 ,博 士 ,主要研究方向为仿生系统模型、仿 生计算理论及其应用. 目前已主持国家 自然科学基金、省自然科学基金、省教 育厅项目等科研项目多项 ,发表论文 100余篇 ,被 SCI、EI等检索 50余篇. 2008年 IEEE亚太地区计算智能与工业应用研讨会 IEEE Pac ific2Asia Workshop on Computational Intelligence( IEEE PAC IIA 2008) 2008年亚太地区智能计算和工业应用研讨会 ( PAC IIA 2008) 将于 2008年 12月 19日至 20日在武汉 工程大学召开 ,本次会议的主题是“先进智能计算技术及其工业应用 ”。会议由美国电子和电气工程师协会 ( IEEE) 和 美国电子和电气工程协会工业电子分会支持 ( IEEE IES) ,由武汉工程大学主办 ,武汉工程大学 计算机学院和电气学院承办。该会议已经进入 IEEE会议列表 ,录用论文将被 IEEE CS出版 ,并被著名检索 机构 E I和 ISTP检索。 会议议题 (不限于 ) : 神经网络与软计算 机器学习 人机交互 信号处理 智能控制 模式识别 信息安全 无线通信 /工业应用 重要日期 摘要截稿日期 : 20082821 论文录用通知日期 : 200829215 全文截稿日期 : 20082821 交修订版截止日期 : 200821021 会议网站 : http: / /www. paciia2008. cn; 联系人 :卢老师 ; 联系电话 : 027 - 87992077 ·278· 智 能 系 统 学 报 第 3卷
