搜索
群体智能的研究与发展概述摘要群体智能所表现出的特性是低级个体与它们的环境局部交互所表现的集体行为形成了一致功能的整体模式。它为不需要集中控制或提供全局模型就能探索集体合作（或分布式）问题提供了基础。本文探讨了群体智能的发展现状，并研究了主要的蚁群算法、蜂巢算法和微粒群算法，并介绍了群体智能应用于并行计算的发展状况。关键词：群体智能，蚁群算法，蜂巢算法，微粒群算法，并行计算。1．群体智能背景群居性生物的群体行为涌现的群体智能正越来越得到人们的重视。一些启发于群居性生物的寻食、打扫巢穴等行为而设计的算法成功地解决了组合优化、通信网络和机器人等领域的实际问题.Bonabeau等人认为群体智能是任何启发于群居性昆虫群体和其它动物群体的集体行为而设计的算法和分布式问题解决装置。群体智能的特点是最小智能但自治的个体利用个体与个体和个体与环境的交互作用实现完全分布式控制，并具有自组织、可扩展性、健壮性等特性。群体智能作为一个新兴领域，自从20世纪80年代出现以来，引起了多个学科领域研究人员的关注，已经成为人工智能以及经济、社会、生物等交叉学科的热点和前沿领域。由单个复杂个体完成的任务可由大量简单的个体组成的群体合作完成，而后者往往更具有健壮性、灵活性和经济上的优势。群体智能（swarmintelligence）利用群体优势，在没有集中控制，不提供全局模型的前提下，为寻找复杂问题解决方案提供了新的思路。对群体智能的定义进行扩展，普遍意义上有以下几种理解。一是由一组简单智能体（agent）涌现出来的集体的智能（collectiveintelligence），以蚁群优化算法（AntColonyOptimization，ACO）和蚂蚁聚类算法等为代表；二是把群体中的成员看作粒子，而不是智能体，以粒子群优化算法（ParticleSwarmOptimization，PSO）为代表。群体智能是对生物群体的一种软仿生，即有别于传统的对生物个体结构的仿生。可以将个体看成是非常简单和单一的，也可以让它们拥有学习的能力，来解决具体的问题。基于群体智能的聚类算法起源于对蚁群蚁卵的分类研究。Lumer和Faieta将Deneubourg提出的蚁巢分类模型应用于数据聚类分析，与经典的层次聚类算法和k均值动态聚类算法相比，基于群体智能的聚类算法具有群体智能算法的共同特点，它利用个体与个体和个体与环境的交互作用，不必预设聚类中心的数目，实现自组织聚类过程，具有健壮性、可视化等特点。基于群体智能的聚类算法的主要思路是将待聚类的对象随机放置在一个两维网格的环境中，每一个对象有一个随机初始位置，每一只蚂蚁能够在网格上移动，并测量当前对象在局部环境的群体相似度，通过概率转换函数将群体相似度转换成移动对象的概率，以这个概率拾起或放下对象。蚁群联合行动导致属于同一类别的对象在同一个空间区域能聚集在一起。群体相似度是一个待聚类模式（对象）与其所在一定的局部环境中所有其它模式的综合相似度。2．群体智能算法群体智能典型的代表算法有蚁群（AntColony）、蜂巢（WaspNest）、微粒群（ParticleSwarm）。2.1蚁群算法蚁群寻找食物时会派出一些蚂蚁分头在四周游荡，如果一只蚂蚁找到食物，它就返回巢中通知同伴并沿途留下“信息素”（外激素）作为蚁群前往食物所在地的标记。信息素会逐渐挥发，如果两只蚂蚁同时找到同一食物，又采取不同路线回到巢中，那么比较绕弯的一条路上信息素的气味会比较淡，蚁群将倾向于沿另一条更近的路线前往食物所在地。用于旅行商问题的蚁群算法采用虚拟的“蚂蚁”，让它们摸索不同路线，并留下会随时间逐渐消失的虚拟“信息素”。根据“信息素较浓的路线更近”的原则，即可选择出最佳路线。这种信息素起到了非直接通信的作用。而后面的蚂蚁就会选择这条短的路径，并且留下更多的信息素。蚁群算法在应用到小规模问题上时，取得了快速收敛的好效果。随着研究的深入，将基本蚁群算法应用到更大一些规模的TSP问题上时，计算结果不是很理想，表明基本蚁群算法在求解大规模复杂问题上能力有限。这是因为蚁群算法主要利用正反馈原理强化一些次优解，但当迭代到一定代数后，由于次优解路径上的信息素不断得到强化，使得大量的蚂蚁聚集到较少的几条路径上，在以后的迭代计算中，蚂蚁都一遍一遍的重复经过这其中的一条或几条路径，从而构造出几乎完全相同解，在这种情况下，就无法探索新的路径，不能发现新的解，于是就出现早熟、停滞现象。在规模较小的TSP问题中，最优解往往就存在于这些次优解集中，所以较容易发现；而对于较大规模的TSP问题，存在很多的局部极小点，单一的信息素调整方法使得基本蚁群算法较容易陷入这些局部极小点，从而出现停滞现象。蚁群算法优化过程的本质在于：（1）选择机制。信息量越大的路径，被选择的概率越大；（2）更新机制。路径上面的信息量会随蚂蚁的经过而增长，同时也随着时间的推移逐渐减小。（3）协调机制。蚂蚁之间实际上是通过信息量来互相通信、协同工作的。这样的机制使得蚁群算法具有很强的发现较好解的能力。但是，蚁群算法也有一些缺陷。例如，由于蚁群中多个个体的运动是随机的，当群体规模较大时，要找出一条较好的路径需要较长的搜索时间。另外，蚁群算法主要利用正反馈原理强化较优解，当进化到一定代数后就容易因为较优解的信息量不断强化使得蚂蚁大量聚集于较少的几条路径上，出现早熟、停滞现象，使得到的最优解是局部最优的。2.2蜂巢算法蜂群围绕着蜂巢的行为也表现了群体的智能。经常会看到蜂群围绕着蜂巢忙碌的情境，它们时而在空中飞舞徘徊，时而降落在蜂巢上走来走去忙着什么，时而又飞离蜂巢，远赴他方。其实在这些简单的行为中，它们完成了觅食和抚养幼蜂的工作。单只蜂的智能是有限的，它们是如何对工作进行分配的，如何保证有足够的食物，如何保证每只幼蜂都能照顾得到。目光不得不瞄向这些简单的个体联合起来形成的群体，瞄向它们之间的协作。对蜂巢的研究提出了许多模型，均是借鉴蜂群之间的自组织行为。蜂之间的交互以及蜂与局部环境的交互导致了像觅食、抚幼这样工作的动态分配，而且通过它们之间的交互建立了一个等级的社会秩序，这种出现的社会秩序是在蜂不断地从优势地位到非优势地位的过程中形成的，这是等级社会模型思想。响应阈模型描述了蜂群的任务分配。每只蜂对蜂巢的每个格都有一个响应阈，根据对给定巢格的响应阈和那个巢格内幼蜂的刺激量，一只蜂决定为或者不为那个巢格的幼蜂觅食。如果刺激量一定，对给定巢格的响应阈越低，决定为之觅食的可能就越大。而且响应阈也会根据任务的分配和完成情况及时更新。2.3微粒群算法1986年CraigReynolds提出了Boid（Bird-oid）模型用以模拟鸟类聚集飞行的行为，仿真的目的主要是研究如何对各种可能的运动进行描述和控制。他们通过对现实世界中这些群体运动的观察并在计算机中复制重建这些运动轨迹，并对这些运动进行抽象建模以发现新的运动模式。自然界中这些呈现群体特征的行为特征，在某些情况下可以用简单的几条规则将这种群体行为（SwarmBehavior）在计算机中建模，实际上就是在计算机中用简单的几条规则来建立个体的运动模型，但这个群体的行为可能很复杂。社会心理学博士JamesKennedy和电子工程学博士RussellEberhart早期的工作就是对不同的鸟群运动进行建模和计算机仿真，例如，Reynolds使用了下列三个规则作为简单的行为规则。1）向背离最近的同伴的方向运动。2）向目的地运动。3）向群体的中心运动。在这个群体中每个个体的运动都遵循这三条规则，通过这个模型来模拟整个群体的运动。后来受到生物学家FrankHeppner建立的鸟群运动模型影响，JamesKennedy和RussellEberhart于1995年提出了粒子群优化算法（ParticleSwarmOptimization，PSO）。与其它模型不同的是Heppner在他的鸟群模型中增加了一个条件，即这个群体中的鸟会受到栖息地的吸引。鸟群在起飞时并无目的地，在空中自然地形成群体，当群体中一只鸟发现栖息地，就会飞向这个栖息地，同时也会将它周围的鸟拉过来，而周围的鸟也将影响群体中其它的鸟，最终将整个群体引向这个栖息地。在PSO模型中，每个优化问题的潜在解都可以想象成D维搜索空间上的一个点，称之为“粒子”（Particle）。粒子在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。所有的粒子都有一个被目标函数决定的适应值（fitnessvalue），并且知道自己到目前为止发现的最好位置和当前的位置。这个可以看作是粒子自己的飞行经验。除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置，这个可以看作是粒子的同伴的经验每个粒子使用下列信息改变自己的当前位置：（1）当前位置；（2）当前速度；（3）当前位置与自己最好位置之间的距离；（4）当前位置与群体最好位置之间的距离；简化粒子群算法粒子只在群最优邻域进行搜索。因为所有的粒子都参与了群最优的邻域搜索，所以简化粒子群算法是局部搜索最高效的搜索算法，但也是最易陷入局部最优的算法。基本粒子群算法与简化的粒子群算法相比，提出了个体极值来延缓粒子群搜索范围的快速收敛而提高搜索精度一但同时也增大了粒子利用的信息量—粒子同时利用了自身的个体极值。目前，对粒子群算法的研究才刚刚起步，相对其它比较成熟的进化算法，应用的范围还较小。但随着研究的进一步深入，粒子群算法将会应用到越来越多的领域中，如电路设计、分类、作业调度、机器人路径规划、系统辨识、模式识别、信号处理、生产调度等领域。3．群体智能并行算法群体智能是通过对群居生物的行为模拟来解决实际中的一些问题。群居生物的行为方式有天然的并行性，很适用于并行计算。有文献分析和比较了基本蚁群算法在部分异步并行和同步并行两种不同并行模式下算法的加速比、运算效率和运算效果等指标优劣，指出并行模块间通讯量的不同影响了两个算法的效率。还有文献分析了蚁群算法并行的可能性，在基本蚁群算法的基础上，提出了一种主从模式的并行策略。另外的一些文献中蚁群算法的并行机制比较简单，如果进一步设计较精细的并行机制会大大增进算法的效率。个体适应值的评价或计算在群体智能算法的运行过程中所占用的运行时间比较长。群体中各个体间的适应值无相互依赖关系，这样各个体适应值的评价或计算过程就可以相互独立、相互并行地进行，即不同个体的适应值评价或计算过程可以在不同的处理机上同时进行。从总体来看，群体智能的操作对象是由多个个体组成的一个群体，而多个这样的群体也同时遵循共同的规则。换句话说，遵循相同规则的群体应该可以同时分成多组小的群体，这些多组小群体可以看作是一个大的群体划分而成的子群体，若将它们分别置于不同的处理机上，一定能够提高运行效率。也就是说，可以对群体按照一定要求进行分组，分组后的单个或一组个体的计算过程可以分布在不同的处理机上相互独立地进行，并在适当的时候，各子群之间以适当的方式交换信息，保证整个群体的“前进”方向。这种方法是符合自然界中群体生物行为方式的，是一种自然的并行方式，在并行机或局域网环境下也较容易实现。4．总结在群体智能的研究领域，已经取得了相当多的研究成果。研究和掌握群体智能系统的特性与规律，是一个具有理论和应用两个方面重要意义的课题。它的研究与发展，将为人工智能领域带来新的活力，提供解决问题的全新的角度和方法，同时由于它广阔的市场前景，也是和人类社会经济密切相关的，现实意义非常明显。可以预见，对群体智能的研究即将全面展开，必将在某些方面出现新的成果。