基于群体智能的算法研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于群体智能的算法研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：计算机技术不断发展，从而带动着算法技术不断更新，尤其是在模仿社会性动物的行为领域，产生了很多的智能算法。本文主要介绍当前几种热门研究的算法，阐述了其工作原理和特点，同时对其发展进行了展望。

关键词：群体智能；蚁群算法；粒子群优化算法；人工鱼群算法

中图分类号：TP183文献标识码：A文章编号：1009-3044(2008)11-20318-02

1 引言

在人工智能的研究领域，基于群体智能(Swarm Intelligence)的算法的研究成为了众多专家研究的热点。群体智能中的群体(Swarm)指的是“一组相互之间可以进行直接通信或者间接通信(通过改变局部环境)的主体，这组主体能够合作进行分布问题求解”。而所谓群体智能指的是“无智能的主体通过合作表现出智能行为的特性”[1]。群体智能在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了基础。本文的工作是阐述几种基于群体智能的算法基本原理和模型及其展望。

2 基于群体智能的算法的特点

群体智能是基于种群行为对给定的目标进行寻优的启发式搜索算法，群体中相互合作的个体是分布式的(Distributed)，这样更能够适应当前网络环境下的工作状态；没有中心的控制与数据，这样的系统更具有鲁棒性(Robust)，不会由于某一个或者某几个个体的故障而影响整个问题的求解。可以不通过个体之间直接通信而是通过非直接通信进行合作，这样的系统具有更好的可扩充性(Scalability)。由于系统中个体的增加而增加的系统的通信开销在这里十分小。系统中每个个体的能力十分简单，这样每个个体的执行时间比较短，并且实现也比较简单，具有简单性(Simplicity)。但是对于每个个体，其定义本身是相对的，其大小和功能根据所求解的问题而定，所以其智能的寻优方式的实现是通过整个智能群的总体特征来体现的。

虽然现在的研究还处在初级阶段，但是从一些实验来看，他代表了智能算法的研究方向。目前，比较成熟的群体智能算法有，蚁群算法(Ant Colony Algorithm,ACA)、粒子群优化算法(Particle Swarm Optimization,PSO)和人工鱼群算法(Artificial Fish―Swarm Algorithm,AFSA)。

2 基于群体智能的算法的研究现状

2.1 蚁群算法

蚁群算法是由20世纪90年代意大利的M．Dorigo等学者提出的。这种算法源于取食行为中的通信机制启发而研究得来。蚂蚁这类群居动物，单个蚂蚁在运动过程中会留下一种称之为“信息激素”(pheromone)的分泌物，后面的蚂蚁可以感知前边蚂蚁所留下的信息激素的存在及其强度，并选择自己要走的方向。蚂蚁倾向于朝着该物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。而且，蚂蚁还能够适应环境的变化，如在蚁群运动路线上突然出现障碍物时，蚂蚁能够很快地重新找到最优路径。

2.1.1 蚁群算法基本模型

蚁群算法[2]的核心是：选择机制，信息素越多的路径，被选择的概率越大；更新机制，路径上面的信息素会随蚂蚁的经过而增长，而且同时也随时间的推移逐渐挥发消失；协调机制，蚂蚁间实际上是通过分泌物来互相通信、协同工作的。

蚁群算法的首先成功应用于TSP问题，现就简单描述其基本方法：给定一个有n个城市的TSP问题，人工蚂蚁的数量为m。每个人工蚂蚁的行为符合下列规律：根据路径上的激素浓度，以相应的概率来选取下一步路径；不再选取自己本次循环已经走过的路径为下一步路径。用一个数据来控制这一点，当完成了一次循环后，根据整个路径长度来释放相应浓度的信息素，并更新走过的路径上的信息浓度。其基本流程是：初始化的时候，m个蚂蚁被放置在不同的城市，赋予每条边上的信息浓度都为零，每个蚂蚁的数据库的第一元素赋值为他所在的城市，当蚂蚁们完成一次完整的寻径过程后，计算信息素浓度，并且更新每条边上的信息素浓度。然后开始新一轮的循环。当循环次数达到事先定义好的次数时或者所以的蚂蚁都选择了同一种路径方式时，整个程序终止。

2.2 粒子群优化算法

粒子群优化算法[3]是一种进化计算技术(Evolutionary Computation)，由Eberhart博士和Kennedy博士发明。源于对鸟群捕食的行为而研究所得。一群鸟在随机搜索食物的飞行过程中会通过参考同伴的运动信息来调整自己的运动状态，在运动中，每个个体的信息都是共享的，正是通过这种相互借鉴可以是个体运动达到最优状态。PSO中，空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子(随机解)，然后通过叠代找到最优解，在每一次叠代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest，另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分最优粒子的邻居，那么在所有邻居中的极值就是局部极值。

2.2.1 PSO算法过程

①种群随机初始化。

②对种群内的每一个个体计算适应值(fitness value)。适应值与最优解的距离直接有关。

③种群根据适应值进行复制。

④如果终止条件满足的话，就停止，否则转步骤②。

从以上步骤，算法使用适应值来评价系统，根据适应值来进行一定的随机搜索。粒子还有一个重要的特点，就是有记忆。在PSO中，只gBest(or IBest)给出信息给其他的粒子，这是单向的信息流动。整个搜索更新过程是跟随当前最优解的过程。与遗传算法比较，在大多数的情况下，所有的粒子可能更快的收敛于最优解。

2.3 人工鱼群算法

人工鱼群算法[4]是李晓磊等在前人对群体智能行为研究的基础上提出的一种新型仿生优化算法．这种算法源于鱼群的觅食行为。在一片水域中，鱼往往能自行或尾随其它鱼，找到营养物质多的地方，因而鱼生存数目最多的地方一般就是本水域中营养物质最多的地方．人工鱼群算法根据这一特点，通过构造人工鱼来模仿鱼群的觅食、聚群、追尾及随机行为，从而实现寻优。

2.3.1 鱼群算法的基本模型

（1）觅食行为：一般情况下鱼在水中随机、自由地游动，当发现附近有食物时，则会向着食物逐渐增多的方向游去。

（2）聚群行为：为了保证生存和躲避危害，鱼会自然地聚集成群．鱼聚群时所遵守的规则有3条。① 分隔规则，尽量避免与临近伙伴过于拥挤；② 对准规则，尽量与临近伙伴的平均方向一致；③ 内聚规则，尽量朝临近伙伴的中心移动．

（3）追尾行为：当某条鱼发现食物时，其他鱼会尾随其临近的伙伴快速到达食物点。

（4）随机行为：当闲暇无事时，鱼在水中随机、自由地游动寻找。

（5）约束行为：在寻优过程中，由于聚群行为，随机行为等操作，可能出现不是可行解的情况，这时需要加人相应的约束条件来调整，使它们由无效状态变为可行解。

（6）公告板：公告板用来记录最优人工鱼个体的状态。各人工鱼个体在寻优过程中，每次行动完毕就检验自身状态与公告板的状态，如果自身状态优于公告板状态，就将公告板的状态改写为自身状态，这样就使公告板记录下历史最优的状态。

（7）移动策略：对人工鱼当前所处的环境进行评价，即模拟执行聚群、追尾行为，然后选择行动后食物浓度值较高的动作来执行，缺省行为方式为觅食行为。

本算法实质上是一种序列覆盖算法，利用鱼群算法具有良好的克服局部极值和获取全局最优值（在这里是规则的质量）的能力，搜索出一个质量最好的规则，然后移去该规则所正确覆盖的样例，直至最后不能被覆盖的样例数小于允许最大未覆盖的样例数，则整个训练算法结束，最终算法将得到一组最优的分类规则．

3 展望

基于智能的算法为解决一类优化问题提供了新思路，并且通过改进的算法在很多的领域得到应用，如构建网站，优化搜索引擎，构建电力系统，优化选择和配送等。但是单纯的对优化算法的研究很难再有其他大的突破。但是，生物群体拥有巨大的潜力供人们研究，目前还没有形成系统的理论。以下几个方面将是研究的热点：（1）刺激产生新的算法的生物体的行为模型；（2）各种算法的完善和结合在实际问题上的应用；（3）充分挖掘智能算法在实际应用中的潜力；（4）系统的建模、仿真以及实际应用。

参考文献：

[1] Kennedy J，Eberhart R C.Swarm intelligence[M].San Francisco: Morgan Kaufmann,2001．

[2] 段海滨,王道波,朱家强,等.蚁群算法理论及应用研究的进展[J].控制与决策,2004,19(12):1321-1326.

[3] 康琦.微粒群优化算法的研究与应用[D].上海：同济大学,2005.

[4] 李晓磊,邵之江,钱积新.一种基于动物自治的寻优模式：鱼群算法[J].系统工程理论与实践,2002.

[5] 段海滨,王道波,于秀芬.几种新型仿生优化算法的比较研究[J].计算机仿真,2007,03-0169-04.

[6] 王玫,朱云龙,何小贤.群体智能研究综述[J].计算机工程,2005,22-0194-03.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文