第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·