人工智能群智能.ppt

群智能（ Swarm Intelligence ）什么是群？l蚁群l鱼群l鸟群l蜂群“群”的特征l相互影响的相邻的个体l个体的行为简单l既有竞争又有协作l智能化的集体行为l个体之间不仅可以交换信 息而且可以处理信息，根 据信息来改变自身行为l没有一个集中控制中心， 分布式，自组织l作为群体协作工作时，能 够突显出非常复杂的行为 特征-智能行为，群智能群智能（ Swarm Intelligence ） 的提出和发展l1989年加利福尼亚大学的Beni（贝 尼）、Hackwood教授在其细胞自动 机中首次提出群智能的概念细胞自 动机中的主体在一维或二维网格空间 中与相邻个体相互作用，从而实现自 组织l任何一种由昆虫群体或其它动物社会 行为机制而激发设计出的算法或分布 式解决问题的策略均属于群智能 1999年，Bonabeau（伯纳堡）、Dorigo和 Theraulaz 在他们的著作“Swarm Intelligence: From Natural to Artificial Systems,群智能：从 自然到人工系统”Beni（贝尼）Bonabeau（伯纳堡）群智能（ Swarm Intelligence ） 的提出和发展l2001年肯尼迪和艾伯哈特合写了一本 书“群智能”l群智能发展的历程碑l赞同伯纳堡关于群智能的基本定义精神l最重要的观点：智能源于社会性的相互 作用。

群智能发展的基石l认为暂时无法给出合适的定义l群智能已经成为有别于传统人工智能中 符号主义和链接主义的一种新的关于人 工智能的研究路线Swarm Intelligence(续)《Swarm Intelligence》最重要的观点是：Mind is social，也就是认为人的智能是源于社会性的相互作 用，文化和认知是人类社会性不可分割的重要部分， 这一观点成为了群智能发展的基石群智能已成为有 别于传统人工智能中连接主义和符号主义的一种新的 关于智能的描述方法 群智能的思路，为在没有集中控制且不提供全局 模型的前提下寻找复杂的分布式问题求解方案提供了 基础在计算智能领域已取得成功的两种基于SI的优 化算法是蚁群算法和粒子群算法Swarm Intelligence(续)目前，已有的基于SI的优化算法都是源于对动 物社会通过协作解决问题行为的模拟，它主要强 调对社会系统中个体之间相互协同作用的模拟 这一点与遗传算法Genetic Algorithms-GA不 同，GA是对生物演化中适者生存的模拟与GA 一样的是，SI的目的并不是为了忠实地模拟自然 现象，而是利用他们的某些特点去解决实际问题 。

另一个与GA的相同点是,基于SI的优化算法也 是概率搜索算法Swarm Intelligence(续)目前，已有的群智能理论和应用研究证明群 智能方法是一种能够有效解决大多数优化问题 的新方法，更重要是,群智能潜在的并行性和 分布式特点为处理大量的以数据库形式存在的 数据提供了技术保证无论是从理论研究还是 应用研究的角度分析,群智能理论及应用研究 都是具有重要学术意义和现实价值的Swarm Intelligence(续)由于SI的理论依据是源于对生物群社会性的模 拟，因此其相关数学分析还比较薄弱，这就导 致了现有研究还存在一些问题 数学理论基础薄弱：群智能算法的数学理论基础相对薄弱，缺乏 具备普遍意义的理论性分析，算法中涉及的各种参数设置一直 没有确切的理论依据，通常都是按照经验型方法确定，对具体 问题和应用环境的依赖性比较大 结果的可信性：同其它的自适应问题处理方法一样，群智能也不 具备绝对的可信性，当处理突发事件时,系统的反应可能是不 可测的,这在一定程度上增加了其应用风险 另外,群智能与其它各种先进技术(如:神经网络、模糊逻辑、支持 向量机等) 的融合还不足 l无智能或简单智能的主体通过任何形式的聚集 协同而表现出智能行为的特性。

这里关心的不是个体之间的竞争，而是它们之 间的协同（获取并共享信息）蚂蚁：信息素鱼群：速度、方向、位置等，群体最佳和个 体最佳位置鸟群：速度、方向、位置等Swarm Intelligence(续)基于群智能的优化算法l典型算法 蚁群算法（蚂蚁觅食） 粒子群算法（蜂群或鸟群觅食） 鱼群算法（鱼群觅食）l优点 灵活性 稳健性 自组织 潜在的并行和分布已有的群智能理论的研究和应用证明群智能方法是一 种能够有效解决大多数优化问题的新方法蚁群算法l1992年由意大利的学者多里戈 提出l模拟自然界中蚂蚁寻找从巢穴 到食物的最佳路径的行为l一种新型的优化算法l蚁群的自组织行为1989年，戈斯等研究蚂蚁觅 食的“双桥实验”通过遗留在来往路径上的信息素（Pheromone）的挥发性化学物质来进行通信和协调蚁群算法的起源蚁群算法的起源蚁穴食物蚁群算法的起源蚁群算法的起源l增加桥的难 度l分时段记录 各路径上的 蚂蚁数量神奇的信息素l蚂蚁觅食的过程l随机移动l遇到食物返回的路上分泌信息素l信息素：易挥发性的化学物质l在回家的路上留下信息素l其它蚂蚁发现留有信息素的路径结束漫游，沿 着该路径移动，遇到食物同样返回途中分泌信 息素。

l信息素会随着时间慢慢挥发，关键路径上的信 息素相对浓度高初始运行一段时间蚂蚁系统l多里戈在其博士论文中提出了一种蚂蚁系 统（ANT SYSTEM AS）,以解决旅行商 问题（TSP）l一个售货员希望去访问若干个城市，开始 和结束于同一城市，每两个城市之间都有 一条直接通路，怎样行走才能使走过的路 径最短？蚁群算法l蚂蚁在两个城市之间移动l两个城市之间的信息素越多，蚂蚁就越有可 能选择它们之间的路径l能够成功完成遍历的蚂蚁会在路径上留下信 息素，路径越短留下的信息素会越多蚁群算法原理l基于蚂蚁觅食时的最优路径选择问题，可以构造人工 蚁群，来解决最优问题l人工蚁群中把具有简单功能的工作单元看作蚂蚁l人工蚂蚁与自然蚁群l相似之处：优先选择信息素浓度大的路径l区别：人工蚂蚁有一定的记忆能力，能够记忆已经访 问过的节点l人工蚁群在选择下一条路径的时候是按一定的算法有 意识的寻找最短路径，而不是盲目的蚁群算法中的各种行为因子范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个 参数为速度半径，那么它能观察到的范围以及能够移动的 范围都会发生在这样的一个范围之内 环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍 物，有其他的蚂蚁，还有信息素，信息素可以设计为单一 种类也可以多种类（如两种），一种是找到食物的蚂蚁撒 下的食物信息素，另外一种是找到食物的蚂蚁洒下的蚁窝 的信息素。

每个蚂蚁都仅仅能感知它范围内的环境信息 同时环境也以一定的速率让信息素消失蚁群算法中的各种行为因子觅食规则：在每只蚂蚁能感知的范围内寻找是否有食 物，如果有就直接过去否则通过比较在能感知的范围内 的信息素的多少，然后它会向信息素最多的方向移动同 时每只蚂蚁还以小概率来进行“犯错”从而并不总是向信 息素最多的方向移动蚂蚁找到窝的规则和上面的相同， 只不过它只对窝的信息素进行反应，而对食物信息素没有 任何反应 移动规则：每只蚂蚁都向信息素最多的方向前进，并 且在运动方向上有一个随机的小扰动为了防止蚂蚁原地 转圈，它会记住刚才走过了那些点，如果发现要走的下一 个点已经走过了，它就会尽量避开蚁群算法中的各种行为因子避障规则：如果蚂蚁要移动的方向有障碍物挡住，它 会随机的选择另一个方向，并且有信息素指引的 话，它会按照觅食的规则进行移动 信息素规则：每只蚂蚁在刚找到食物或者蚁窝的时候 散发的信息素最多，并随着它走远的距离，散播的信息素 越来越少蚁群算法l最初提出的蚂蚁系统有三个版本，在不大于 75个城市的系统中，这三个基本算法的求解能 力比较理想l后来提出了改进算法l精英策略，对所有已发现的最好路径给予额 外的增强l蚁群系统l负反馈机制，当一只蚂蚁由一个节点移动到 另一个节点时，该路径上的信息素被相应的消 除一部分以减少已经选择过的路径再次被选择 的概率。

蚁群算法的应用l蚁群算法具有广泛的应用价值l是群智能研究领域第一个取得成功的实例l一度成为群智能的代名词l蚁群算法已被广泛应用于许多优化问题中l聚类问题l路由算法设计l图着色l车辆调度l机器人路径规划蚁群算法应用举例-聚类问题l起源于对蚁群蚁卵的分类研究l基本思想l将待聚类数据随机地分散在一个二维平面上l虚拟蚂蚁分布在空间内，并以随机方式移动l当一个蚂蚁遇到一个待聚类数据时即将物体 拾起并继续随机移动l若运动路径附近的物体与背负的物体相似性 高于设置的标准则将其放到该位置，然后继续 移动l重复上述过程蚁群算法的应用l聚类问题-四色实验蚁群算法的应用l聚类问题-八色实验蚁群算法应用举例-路由问题lHP公司和英国电信公司在90年 代中后期都开展了这方面的研究l设计了蚁群路由算法（ANT COLONY ROUTING）蚁群算法的应用l人工生命 Tom-Cat 按照一定规则运动的个体 方格的不同类型：平坦、泥泞、陷阱、沼泽 等粒子群优化算法（Particle Swarm Optimization, PSO）l由James Kenney（社会心理学 博士）肯尼迪和Russ Eberhart（ 电子工程学博士）艾伯哈特， 1995年提出l模拟鸟群或蜂群的觅食行为l基本思想：通过群体中个体之间 的协作和信息共享来寻找最优解, 肯尼迪鸟类的觅食l一群鸟在随机的搜索食物，在一 块区域里只有一块食物，所有的鸟 都不知道食物在哪。

但是它们知道 自己的当前位置距离食物有多远l那么这群鸟找到食物的最优策略 是什么？群体协作-获取信息、共享信息粒子群优化算法粒子群优化算法l每个鸟抽象为一个无质量，无体积的“粒子”l每个粒子有一个适应度函数以模拟每只鸟与 食物的距离l每个粒子有一个速度决定它的飞行方向和距 离，初始值可以随机确定l每一次单位时间的飞行后，所有粒子分享信 息，下一步将飞向自身最佳位置和全局最优 位置的加权中心粒子群优化算法流程wPSO算法 初始化为一群随机粒子，通过迭代找到最优每次迭代中，粒子通过跟踪“个体极 值（pbest）”和“全局极值(gbest)”来更新自己的位置粒子群优化算法w粒子速度和位置的更新假设在D维搜索空间中，有m个粒子；其中第i个粒子的位置为矢量 其飞翔速度也是一个矢量，记为 第i个粒子搜索到的最优位置为 整个粒子群搜索到的最优位置为 第i个粒子的位置和速度更新为：粒子群优化算法w粒子速度和位置的更新其中，w称为惯性权重，c1和c2为两个正常系数，称为加速因子。

将 vidk 限制在一个最大速度 vmax 内惯性部分”， 对自身运动状 态的信任“认知部分”，对粒子本 身的思考，即来源于自 己经验的部分“社会部分”，粒间子的信 息共享，来源于群体中的 其它优秀微粒的经验粒子群优化算法基本粒子群算法描述w算法流程StartInitialize particles with random positionand velocity vectors.For each particle’s position (xi) evaluate fitnessIf fitness(xi) better than fitness(p) then p= xiLoop until all particles exhaustSet best of Ps as gBestUpdate particles velocity andpositionLoop until max iterStop: giving gBest, optimal solution.基本粒子群算法描述粒子群优化算法w惯性权重w使粒子保持运动惯性，使其有扩展搜索空间的趋势，有能力探索新的区域表示微粒对当前自身运动状态的信任，依据自。