《群智能及粒子群优化算法.》由会员分享，可在线阅读，更多相关《群智能及粒子群优化算法.（115页珍藏版）》请在金锄头文库上搜索。
1、群智能理论及粒 子群优化算法 李宁 Swarm Intelligence Swarm Intelligence (SI)的概念最早由 Beni、Hackwood和在分子自动机系统中提出 。分子自动机中的主体在一维或二维网格空 间中与相邻个体相互作用，从而实现自组织 。1999年，Bonabeau、Dorigo和Theraulaz 在他们的著作Swarm Intelligence: From Natural to Artificial Systems中对群智能进行 了详细的论述和分析，给出了群智能的一种 不严格定义：任何一种由昆虫群体或其它动 物社会行为机制而激发设计出的算法或分布 式解决问题的
2、策略均属于群智能。 Swarm Intelligence(续) Swarm可被描述为一些相互作用相邻个体的集合体 ，蜂群、蚁群、鸟群都是Swarm的典型例子。鱼聚 集成群可以有效地逃避捕食者，因为任何一只鱼发 现异常都可带动整个鱼群逃避。蚂蚁成群则有利于 寻找食物，因为任一只蚂蚁发现食物都可带领蚁群 来共同搬运和进食。一只蜜蜂或蚂蚁的行为能力非 常有限，它几乎不可能独立存在于自然世界中，而 多个蜜蜂或蚂蚁形成的Swarm则具有非常强的生存 能力，且这种能力不是通过多个个体之间能力简单 叠加所获得的。社会性动物群体所拥有的这种特性 能帮助个体很好地适应环境，个体所能获得的信息 远比它通过自身感觉
3、器官所取得的多，其根本原因 在于个体之间存在着信息交互能力。 Swarm Intelligence(续) 信息的交互过程不仅仅在群体内传播了信息，而 且群内个体还能处理信息，并根据所获得的信息 （包括环境信息和附近其它个体的信息）改变自 身的一些行为模式和规范，这样就使得群体涌现 出一些单个个体所不具备的能力和特性，尤其是 对环境的适应能力。这种对环境变化所具有适应 的能力可以被认为是一种智能（关于适应性与智 能之间的关系存在着一些争议，Fogel认为智能 就是具备适应的能力），也就是说动物个体通过 聚集成群而涌现出了智能。因此，Bonabeau 将 SI的定义进一步推广为：无智能或简单智能的
4、主 体通过任何形式的聚集协同而表现出智能行为的 特性。这里我们关心的不是个体之间的竞争，而 是它们之间的协同。 Swarm Intelligence(续) James Kennedy和Russell C.Eberhart在2001年出 版了Swarm Intelligence，是群智能发展的一 个重要历程碑，因为此时已有一些群智能理论和 方法得到了应用。他们不反对Bonabeau关于SI定 义，赞同其定义的基本精神，但反对定义中使用“ 主体”一词。其理由是“主体”所带有自治性和特殊 性是许多Swarm的个体所不具备和拥有的，这将 大大限制Swarm的定义范围。他们认为暂时无法 给出合适的定义，
5、赞同由Mark Millonas（1994） 提出的构建一个SI系统所应满足的五条基本原则 ： Swarm Intelligence(续) 1 Proximity Principle: 群内个体具有能执行简单 的时间或空间上的评估和计算的能力。 2 Quality Principle: 群内个体能对环境（包括群 内其它个体）的关键性因素的变化做出响应。 3 Principle of Diverse Response: 群内不同个 体对环境中的某一变化所表现出的响应行为具 有多样性。 4 Stability Principle: 不是每次环境的变化都会 导致整个群体的行为模式的改变。 5 Ada
6、ptability Principle: 环境所发生的变化中， 若出现群体值得付出代价的改变机遇，群体必 须能够改变其行为模式。 Swarm Intelligence(续) Swarm Intelligence最重要的观点是： Mind is social，也就是认为人的智能是源于社 会性的相互作用，文化和认知是人类社会性不 可分割的重要部分，这一观点成为了群智能发 展的基石。群智能已成为有别于传统人工智能 中连接主义和符号主义的一种新的关于智能的 描述方法。 群智能的思路，为在没有集中控制且不提 供全局模型的前提下寻找复杂的分布式问题求 解方案提供了基础。在计算智能领域已取得成 功的两种基于
7、SI的优化算法是蚁群算法和粒子 群算法。 Swarm Intelligence(续) 目前，已有的基于SI的优化算法都是源于 对动物社会通过协作解决问题行为的模拟， 它主要强调对社会系统中个体之间相互协同 作用的模拟。这一点与EC不同，EC是对生 物演化中适者生存的模拟。与EC一样的是 ，SI的目的并不是为了忠实地模拟自然现象 ，而是利用他们的某些特点去解决实际问题 。另一个与EC的相同点是,基于SI的优化算 法也是概率搜索算法。 Swarm Intelligence(续) 目前，已有的群智能理论和应用研究证明 群智能方法是一种能够有效解决大多数优化 问题的新方法，更重要是,群智能潜在的并 行
8、性和分布式特点为处理大量的以数据库形 式存在的数据提供了技术保证。无论是从理 论研究还是应用研究的角度分析,群智能理 论及应用研究都是具有重要学术意义和现实 价值的。 Swarm Intelligence(续) 由于SI的理论依据是源于对生物群落社会性的模拟 ，因此其相关数学分析还比较薄弱，这就导致了现 有研究还存在一些问题。首先，群智能算法的数学 理论基础相对薄弱，缺乏具备普遍意义的理论性分 析，算法中涉及的各种参数设置一直没有确切的理 论依据，通常都是按照经验型方法确定，对具体问 题和应用环境的依赖性比较大。其次，同其它的自 适应问题处理方法一样，群智能也不具备绝对的可 信性，当处理突发事
9、件时,系统的反应可能是不可 测的,这在一定程度上增加了其应用风险。另外,群 智能与其它各种先进技术(如:神经网络、模糊逻辑 、禁忌搜索和支持向量机等) 的融合还不足。 蚁群算法 蚁群算法（Ant Colony Optimization, ACO）由 Colorni，Dorigo和Maniezzo在1991年提出，它是通 过模拟自然界蚂蚁社会的寻找食物的方式而得出的 一种仿生优化算法。自然界种蚁群寻找食物时会派 出一些蚂蚁分头在四周游荡，如果一只蚂蚁找到食 物，它就返回巢中通知同伴并沿途留下“信息素”（ pheromone） 作为蚁群前往食物所在地的标记。 信 息素会逐渐挥发，如果两只蚂蚁同时找
10、到同一食物 ，又采取不同路线回到巢中，那么比较绕弯的一条 路上信息素的气味会比较淡，蚁群将倾向于沿另一 条更近的路线前往食物所在地。 蚁群算法(续) ACO算法设计虚拟的“蚂蚁”，让它们摸索不同路 线，并留下会随时间逐渐消失的虚拟“信息素”。 根据“信息素较浓的路线更近”的原则，即可选择 出最佳路线。 目前，ACO算法已被广泛应用于组合优化问 题中，在图着色问题、车间流问题、车辆调度问 题、机器人路径规划问题、路由算法设计等领域 均取得了良好的效果。也有研究者尝试将ACO 算法应用于连续问题的优化中。由于ACO算法 具有广泛实用价值，成为了群智能领域第一个取 得成功的实例，曾一度成为群智能的代
11、名词，相 应理论研究及改进算法近年来层出不穷。 蚁群算法(续) 其它群智能优化算法 目前，还有一些不成熟的群智能优化算法， 国内值得关注的有以下几种。 v2003年李晓磊、邵之江等提出的鱼群算法， 它利用自上而下的寻优模式模仿自然界鱼群 觅食行为，主要利用鱼的觅食、聚群和追尾 行为，构造个体底层行为；通过鱼群中各个 体的局部寻优，达到全局最优值在群体中凸 现出来的目的。在基本运算中引入鱼群的生 存机制、竞争机制以及鱼群的协调机制，提 高算法的有效效率。 其它群智能优化算法（续） 张玲等则提出了一种“松散的脑袋”群智能模型， 采用特殊的随机人工神经网络构建了一种群智 能数学模型。每个神经元被看成
12、一个主体，主 体之间的通讯连接看成各神经元之间的连接， 但连接是随机而不是固定的，即用一个随机连 接的神经网络来描述一个群体，这种神经网络 来描述一个群体。显然这种神经网络具有群体 的智能。 基于群智能的优化算法设计必须遵守简单 有效的原则，对于自然现象过于复杂的模拟往 往会导致算法不具有推广性和实用价值，许多 群智能算法不成功的原因就在于此。 优化问题简介 粒子群算法(particle swarm optimization， PSO)由Kennedy和Eberhart在1995年提出，该 算法模拟鸟集群飞行觅食的行为，鸟之间通过 集体的协作使群体达到最优目的，是一种基于 Swarm Inte
13、lligence的优化方法。同遗传算法类 似，也是一种基于群体叠代的，但并没有遗传 算法用的交叉以及变异，而是粒子在解空间追 随最优的粒子进行搜索。PSO的优势在于简单 容易实现同时又有深刻的智能背景，既适合科 学研究，又特别适合工程应用，并且没有许多 参数需要调整。 PSO算法简介 James Kennedy received the Ph.D. degree from theUniversity of North Carolina, Chapel Hill, in 1992.He is with the U.S. Department of Labor, Washington,DC. He
14、 is a Social Psychologist who has been working with the particle swarm algorithm since 1994. He has published dozens of articles and chapters on particle swarms and related topics, in computer science and social science journals and proceedings. He is a coauthor of Swarm Intelligence (San Mateo, CA:
15、 Morgan Kaufmann, 2001), with R.C. Eberhart and Y. Shi, now in its third printing. Russell C. Eberhart (M88SM89 F01) received the Ph.D. degree in electrical engineering from Kansas State University, Manhattan.He is the Chair and Professor of Electrical and Computer Engineering, Purdue School of Engi
16、neering and Technology, Indiana UniversityPurdue University Indianapolis (IUPUI),Indianapolis, IN. He is coeditor of Neural Network PC Tools(1990),coauthor of Computational Intelligence PC Tools (1996), coauthor of Swarm Intelligence(2001), Computational Intelligence: Concepts to Implementations(2004). He has published over 120 technical papers.Dr. Eberhart was awarded the IEEE Third Millenium Medal. In 2002, he became a Fellow of the American Institute for Medical and
