人工智能入门 课件 6.群智能

群智能AI:SI2大纲什么是群智能(SI)?

模拟SI进行搜索

-蚁群优化算法（ACO）-粒子群优化算法（PSO）AI:SI3PartⅠ:什么是SI?KevinKelly:“这些不起眼的组件，只要正确地组合在一起，就能产生出人意料的智能效果。”什么是群智能？AI:SI4尽管自然界中的一些社会系统是由简单的个体组成的，但它们可以表现出一种智能的集体行为。问题的智能解决方案自然地从这些个体的自组织和交流中产生。这些系统提供了重要的技术，可用于开发人工智能系统。自然之美AI:SI5自然界和社会中的集体行为的例子这可以被视为多智能体系统。AI:SI6涌现Goldstein：“在复杂系统的自组织过程中，新奇、一致的结构、模式和性质的产生。”默里·盖尔曼：“从深层次的简单性中产生的表面复杂性”Bottom-upbehavior:“遵循简单规则的简单代理产生复杂的结构/行为。代理不遵循来自领导者的命令。”白蚁“大教堂”土堆是由白蚁群体建造的：这是自然界中涌现的一个经典例子AI:SI7生物学动机：昆虫社会社会性昆虫的群体能够从刻板、不可靠、不智能且简单的昆虫个体中实现灵活、可靠、智能和复杂的系统层面性能。

昆虫遵循简单规则，使用简单的局部通信（气味轨迹、声音、触觉）并且计算需求低。全局结构（例如，巢穴）可靠地由许多不可靠的个体行动涌现出来。AI:SI8生物学动机：群落、畜群和鱼群在80年代末，克雷格·雷诺兹创建了一个名为“Boids”的动物运动模型。它根据三条简单规则产生非常逼真的运动，这些规则定义了boid的转向行为。这个模型及其变种已被用于驱动电影中的鸟、昆虫、人、鱼、羚羊等的动画效果（例如，《蝙蝠侠归来》、《狮子王》）AI:SI9Boid规则分离：转向以避免拥挤的本地群体成员优先于其他规则的基本规则在避免与环境中的其他物体发生碰撞时也很有用。对齐：朝向本地同群伙伴的平均航向和速度转向强制保持凝聚，以保持同群伙伴在一起。也有助于避免碰撞。凝聚力：转向以朝向本地同群伙伴的平均位置移动畜群边缘的代理更容易受到捕食者的攻击有助于保持畜群在一起AI:SI10一个应用：《狮子王》Videofrom:/471/current/notes/AI:SI群体智能

群体智能（SI）是一种基于对去中心化、自组织系统中的集体行为的研究的人工智能技术。1989年，Beni、Hackwood和Wang在细胞机器人系统的背景下首次使用了“群体智能”这一表述，用于描述简单机械代理的自组织行为。后来，该术语扩展为包括“任何受社会昆虫群落和其他动物群体集体行为启发的算法设计或分布式问题解决设备的尝试”[Bonabeau、Dorigo和Theraulaz，1999]。11AI:ANN12群体智能（续）群体智能系统通常由相互之间以及与环境进行局部交互的大量简单代理组成。虽然通常不存在决定个体代理应如何行为的集中控制结构，但这些代理之间的局部交互往往会导致全局行为的涌现。有时被称为“集体智能”AI:SI13群体智能的组成部分代理：

与世界和其他代理（直接或间接）进行交互简单的行为

例如：蚂蚁、白蚁、蜜蜂、黄蜂通信：

代理如何相互交互

例如：蚂蚁的信息素

单个代理的简单行为+一组代理之间的通信=该组代理的涌现复杂行为AI:ANN14间接通信信号传播：-一个代理发送一个信号，该信号被广播到环境中，并且其强度随着距离的减小而减小。-在点x处，信号可能有以下强度之一：V(x)=V(x0)/dist(x,x0)V(x)=V(x0)/dist(x,x0)2

路径-代理留下“放射性碎屑”形成路径-一个代理跟随路径，使路径逐渐变淡，直到消失AI:SI15间接通信黑板系统-一个公共区域（共享内存），代理可以在其中交换信息、数据和知识。-黑板=强大的分布式知识计算范例-代理=知识源（KS）

IntelligentAgentsIntelligentAgentsIntelligentAgentsBlackboardMessageReplyAgentsIntelligentAgentsIntelligentAgentsIntelligentAgentsIntelligentAgentsIntelligentAgentsIntelligentAgentsAI:SI16直接通信Actor语言一个Actor执行一系列动作以回复接收到的消息言语行为理论言语行为具有以下三个方面：Locution=说话者的物理表达Illocution=说话者话语的意图意义（施为）Perlocution=Locution产生的动作例如：张告诉李：“请把门关上”。

locution

illocutioncontent perlocution：门关上了（希望如此！）AI:ANN17群智能特点分布式，没有中央控制或数据源通信有限没有（显式的）环境模型感知环境（感知）能够应对环境变化。

群体智能与人类有关吗？AI:SI18PartⅡ-Ⅲ：如何模拟群体智能进行搜索？示例1：蚂蚁-->蚁群优化算法（ACO）示例2：鸟群-->粒子群优化算法（PSO）AI:SI19PartⅡ蚁群优化算法（ACO）AI:SI20蚂蚁

单个蚂蚁是具有有限记忆并且能够执行简单动作的简单昆虫。个体蚂蚁是具有有限记忆并能执行简单动作的简单昆虫。然而，一个蚂蚁群能够展现出复杂的集体行为，为问题提供智能解决方案搬运大型物品搭建桥梁寻找从巢穴到食物源的最短路线，根据距离和易接近性对食物源进行优先排序。AI:ANN21蚂蚁此外，在蚁群中，每只蚂蚁都有其规定任务，但如果集体需要，蚂蚁可以切换任务。

在巢外，蚂蚁可以执行以下四种任务：觅食：寻找和获取食物巡逻：寻找食物来源垃圾清理工作：对巢内垃圾进行分类巢穴维护工作：建造和清理巢穴

蚂蚁是否执行某项任务取决于：环境物理状态：如果巢的一部分受损，会有更多的蚂蚁进行巢穴维护工作来修复它与其他蚂蚁的社会互动

交流（直接或间接）是必要的AI:ANN22蚂蚁如何找到最短路径？他们通过在其所走的路径上留下信息素，建立了一个间接通信系统。孤立的蚂蚁随机移动，但当它发现信息素痕迹时，这只蚂蚁有很大可能会决定沿着这条痕迹前进。觅食的蚂蚁会在其路径上留下信息素。当它找到食物来源时，它会返回巢穴并加强其痕迹。因此，其他蚂蚁有更大的可能性开始跟随这条痕迹，从而在其上留下更多的信息素。这个过程就像一个正反馈循环系统，因为一条痕迹上的信息素浓度越高，蚂蚁开始沿着它旅行的可能性就越大。AI:SI23蚂蚁如何找到最短路径？这个过程就像一个正反馈循环系统，因为一条痕迹上的信息素浓度越高，蚂蚁开始沿着它旅行的可能性就越大。B路上的信息素浓度将以比A路更高的速度增加，很快A路上的蚂蚁将选择跟随B路。由于大多数蚂蚁将不再走A路，并且由于信息素是易挥发的，A路上的痕迹将开始蒸发。只有最短的路线将保留下来！AI:SI24蚂蚁群优化模型每只人工蚂蚁都是一个概率机制，用于构建问题的解决方案，使用以下方法：人工信息素沉积启发式信息：信息素痕迹等真实蚂蚁与人工蚂蚁之间的区别：信息素只在构建出解决方案后才更新。其他机制AI:ANN25蚂蚁群优化模型构造蚂蚁解决方案解决方案组件的随机选择规则。更新信息素用于增加与良好或有前途的解决方案相关联的信息素值，并减少与不良解决方案相关联的信息素值。通过信息素蒸发减少所有信息素值-->允许“遗忘”->有利于探索新区域增加与一组选定的良好解决方案相关联的信息素水平-->使算法收敛到解决方案AI:ANN26蚁群系统（AS）：第一个蚁群优化算法构造蚂蚁解决方案

信息素的数量启发式距离α、β常数AI:ANN27蚁群系统（AS）更新信息素蒸发率每只蚂蚁在边(i,j)上留下的信息素AI:ANN28对于旅行推销员问题(TSP)的蚁群系统(AS)初始化将每只蚂蚁放置在随机选择的城市中为每个蚂蚁选择下一个城市更多的城市需要访问遍历每只蚂蚁返回初始城市使用每个蚂蚁的旅行成本更新信息素水平打印最佳旅行yesNo停止准则yesNoB.Ombuki-Berman之后的流程图：群体智能AI:ANN29TSP的简单示例（4个城市）图片来自OlleGallmo：群体智能AI:ANN30AS的扩展蚁群系统倾向于快速收敛这意味着它对找到的最佳解的利用程度太高，它应该更多地探索解空间信息素蒸发/更新规则（可能存在更好的规则）蚁群系统的扩展蚁群系统的精英策略(EAS)基于排名的蚁群系统(RANK)MAX-MIN蚁群系统(MMAS)蚁群系统(ACS)AI:ANN31PartⅢ:粒子群优化算法(PSO)“再次，大自然为我们提供了一种处理信息的方法，既优雅又灵活”AI:ANN32鸟群飞行在粒子群优化中，“群”被定义为一组看似无序的移动个体集合，这些个体倾向于聚集在一起，而每个个体似乎都朝着随机的方向移动。鸟群飞行是粒子群优化在自然界中的最好例子之一。AI:ANN33鸟群飞行的建模鸟群飞行的同步性被认为是一种功能，鸟类努力保持自己与邻居之间的最佳距离。鸟类和鱼类通过调整自身的物理运动来避免捕食者、寻找食物和配偶。人类倾向于调整自己的信仰和态度，以符合社会同龄人的信仰和态度。人类在抽象的多维空间中自由变化。AI:ANN34从鸟类到粒子想象一个鸟群在一个只有一个食物源的区域。一只鸟不知道食物在哪里，但它知道它与食物的距离。最好的策略是跟随离食物更近的鸟。粒子保存和传播它们找到的最佳解决方案。AI:ANN35粒子群优化的特点通过分配随机位置和速度进行种群初始化；然后让潜在的解通过超空间飞行。每个粒子跟踪其在超空间中的“最佳”（最高适应度）位置。这被称为个体粒子的“pBest”它被称为种群中的“gBest”它被称为定义邻域中的“lBest”在每个时间步，每个粒子随机地加速向其pBest和gBest（或lBest）移动。AI:ANN36粒子群优化过程步骤1.在超空间中初始化种群。步骤2.评估个体粒子的适应度。步骤3.根据先前的最佳和全局（或邻域）最佳修改速度。步骤4.根据某些条件终止。步骤5.转到步骤2。AI:ANN37粒子是如何飞行的？gBest和pBest（lBest）的组合lBest可以是：社会性：周围的粒子总是相同的，无论它们在空间中的位置如何地理性：周围的粒子是距离最短的那些粒子全局PSO与局部PSOAI:ANN38粒子群优化速度更新方程全局版本：其中k是维度，c1和c2是正的常数，rand()是随机函数，w是惯性权重。对于邻域版本，将pgk更改为plk。AI:ANN39全局PSO的速度更新方案。AI:ANN40PSO：相关问题控制速度（确定Vmax的最佳值）通常将最大速度设置为变量的动态范围通常将c1和c2设置为2惯性权重影响全局和局部探索之间的