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