人工智能入门 课件 刘峡壁6.群智能、7.总结

群智能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惯性权重影响全局和局部探索之间的权衡。好的方法是在运行过程中减小惯性权重（例如，在1000代中从0.9减小到0.4）。群集大小和邻域大小。AI:ANN41PSO的优点适应操作在速度上进行大多数其他方法在位置上进行操作。效果：PSO具有内置的动力。粒子倾向于跳过最优解-这是一个优势，因为无论如何都会记住最好的位置。概念简单易于实现计算效率高对各种问题有效AI:ANN42PSO的一个应用-图像注释细化PSO用于优化反馈神经网络，以结合关键词之间的相似度测量。AI:ANN43PSO的一个应用-图像注释细化总结AI:Summary45理解并创造智能实体两种观点:弱AI(图灵测试);强AI(中文屋实验)六种途径:符号智能；人工神经网络;机器学习;行为智能;进化计算;群智能。AI:Summary46S.J.RusselllandP.Norvig,“artificialintelligence:amodernapproach”.具有学习能力的智能系统的架构AI:Summary47大纲路线图1:学习-神经网络-行为智能路线图2:搜索-图搜索-进化计算学习学习意味着变化AI:Summary49AI:MachineLearning49定义学习任务基于经验，根据性能准则，提升完成相应任务的性能任务:下跳棋性能:对于任意对手，取胜的概率

经验:以自己为对手，进行的练习任务:识别手写字性能:被正确分类的字所占的比例经验:经过人工标注的手写字的数据库任务:视觉传感器自动驾驶性能:出错前行驶的平均距离经验:人类驾驶的时候记录下来的一系列图像和对应控制命令AI:Summary50AI:NouvelleAI50学习中的信息反馈类型监督学习学习需要的输入输出对已经给定或者可以推导得到。非监督学习没有输出的信息强化学习智能体在环境中作出行动，对于智能体的每一步行动，都会得到一个评价值，但是不被告知如何行动才可以正确的达到目标。AI:Summary51学习的实质函数估计三个问题1.怎样假设函数形式?2.怎样设计学习目标?3.怎样发现最优函数?AI:Summary52AI:ANN521.1怎样假设函数形式?-1

M-P神经元θx1x2xnyω1ω2ωn输入输出阈值McClloch与Pitts，《神经活动中固有的思想逻辑运算》,1943f:激活函数g:整合函数AI:Summary53AI:ANN53整合函数加权求和

径向距离AI:Summary54AI:ANN54激活函数

阈值型线性饱和线性S型函数双曲正切函数高斯函数AI:Summary55AI:ANN55前馈网络的一般结构反馈网络的一般结构AI:Summary56AI:ANN56单层感知器阈值激活函数输出单元相互独立,即没有共享的权重Rosenblatt,1957AI:Summary57（0,0）（1,-0.5）（1,1.5）（2,0.5）

class1

class24.11设计一个感知器，用于区分两类数据，其中第一类数据是（1,1.5）和（2,0.5），第二类数据是（0,0）和（1,-0.5）输入1输入2输出11.5020.500011-0.51w1w2yx1x2AI:Summary58满足以上约束（只是一种可能）-1-1yx1x2-1AI:Summary59AI:ANN59多层感知器(MLP)层与层之间通常是全连接的隐含层单元的个数通常手动选择AI:Summary60监督学习:-使实际输出与期望输出之间的误差最小

(BP)-最大化信息增益(IG)(决策树)

强化学习:

使长期的累积收益最大非监督学习:

使数据与聚类之间的距离最小

(聚类)1.2怎样设计学习目标?AI:Summary61r(state,action)即时奖励值Q(state,action)valuesV*(state)values100

0

0

100

G

0

0

0

0

0

0

0

0

0

90

81100

G

0

81

72

90

81

81

72

90

81

100

G

90100081901001.3怎样发现最优函数?

使用累计折扣收益，折扣率=0.981=0+0.9*90Q-学习算法AI:Summary62Q值例:Hanoi塔AI:Summary63补充题：以下GridWorld中，除了到达目标状态（G）的动作获得的即时奖励为10以外，其余动作对应的即时奖励皆为0。如采用折扣系数为0.8的累积折扣收益，请计算图中的Q函数值，直接标注在图中。G1086.41086.486.41086.4搜索(最优化)01AI:Summary65什么是搜索?以可以接受的计算代价，在问题所有解答中找出最优解或可行解。理想的搜索算法：尽可能快地找到最优解。求解的效果与效率之间存在矛盾-完备性,最优性,复杂性-盲目vs.启发,局部

vs.全局,可行

vs.最优.AI:Summary66数学和计算机科学中的核心主题确定性搜索-图搜索随机和基于群体的搜索-进化计算-群智能启发式搜索方法AI:Summary67用于问题求解图搜索算法的一般结构是不断扩展顶点，直到发现目标顶点（状态空间）或者确定初始顶点的可解性（与或图）。).不同图搜索算法的主要区别在于顶点的扩展顺序不同。盲目搜索不考虑问题特性,包括广度优先搜索、深度优先搜索、有界深度优先搜索和迭代加深深度优先搜索。启发式搜索算法根据问题所提供的启发式信息，用估价函数估计顶点的搜索效率，选择估计效率最高的顶点进行扩展。2.1图搜索AI:Summary68状态空间vs.与/或图状态空间与/或图AI:Summary692.5为什么采用与或图表示法时，解决问题的答案对应于一个子图，而不是一条路径？答：因为与节点AI:Summary70A*算法是影响最大的，应用于状态空间的启发式搜索算法。它通过对估价函数施加一定约束，可以保证搜索到最优解。可容许的启发式函数:如果对于每一个顶点n都有h(n)≤h*(n)，则该启发式函数h(n)是可容许的。其中h*(n)表示从顶点n到目标顶点的最小代价。支配性:如果对于所有顶点都有

h2(n)≥h1(n)

，并且两者都是可容许的，则h2

优于h1,使用h2

搜索速度更快A*算法AI:Summary712.3请用状态空间法求解农夫过河问题，该问题是：一农夫带着一只狼、一只羊和一筐菜来到河边，欲乘船到河对岸。但船太小，农夫每次只能带一样东西过河。而在没有农夫看管的情况下，狼会吃羊，羊会吃菜。农夫应该怎样做，才能在没有任何损失的情况下把所有东西带到河对岸？2.13试用A*算法解决习题2.3中给出的农夫过河问题。解：问题状态表示为（a,b,c,d），其中a,b,c,d分别表示农夫、狼，羊和菜的位置，1表示在左岸，0表示在右岸。则起始状态为(1,1,1,1)，终止状态为(0,0,0,0)。改变状态的操作共八种，分别为：农夫带着{狼、羊、菜}从{左岸到右岸、右岸到左岸}。搜索路径为：(1,1,1,1)

(0,1,0,1)

(1,1,0,1)

(0,0,0,1)

(1,0,1,1)

(0,0,1,0)

(1,0,1,0)

(0,0,0,0)

AI:Summary72h(x)=河左岸物体个数

或无穷大（≠人：狼、羊对应位不能相等；羊、菜对应位不能相等）(1,1,1,1)h=3f=3(0,0,1,1)h=∞f=∞(0,1,0,1)h=2f=3(0,1,1,0)h=∞f=∞(1,1,0,1)h=2f=4(0,0,0,1)h=1f=4(0,1,0,0)h=1f=4(1,0,0,1)h=∞f=∞(1,0,1,1)h=2f=6(1,1,0,0)h=∞f=∞(1,1,1,0)h=2f=6102345AI:Summary73(1,0,1,1)h=2f=6(0,0,1,0)h=1f=6(0,0,0,1)h=1f=6(1,0,1,0)h=1f=7(1,1,1,0)h=2f=8(0,0,0,0)h=0f=7h(x)=河左岸物体个数

或无穷大（≠人：狼、羊对应位不能相等；羊、菜对应位不能相等）续上图6(1,0,0,1)h=∞f=∞7910(1,1,1,0)h=2f=68AI:Summary74博弈树

表示博弈过程的数据结构

在想象对手是最强对手的情况下采取最好的行动，这在结构上表现为与或图极大极小算法

-限制博弈树的深度-评价博弈状态-选择移动到具有最高极大极小值的位置!α-β剪枝

在有界深度优先搜索过程中，通过剪掉一些不必要的分枝达到提高搜索效率的目的。博弈搜索AI:Summary752.17极大极小搜索的思想基础是什么？为什么博弈子树的深度越深，计算机博弈水平越高？答：思想基础是：假设对方为最强对手，在考虑对方每一步都作出最佳应对的情况下，也就是对自己最不利的情况下（极小），选择能给自己带来最大收益的一步（极大）。原因：子树深度越深，表示思考的步数越多，从而能够得到更好的结果。AI:Summary762.21设有如图所示的一棵博弈树，其中末一行的数字是叶顶点的静态估值，请对该博弈树作如下工作：用极小极大值法计算各节点的倒推值。利用-剪枝技术剪去不必要搜索的分枝。叙述剪枝发生在何处，即剪去了哪些分枝（在剪枝处用×在图上做标记）。

AI:Summary77进化计算基于生物进化理论优化行为—最优解个体

–

解;适应度

–

目标;环境

–

问题EC的组成表示:个体和种群适应度估计:目标选择:父代和子代基因操作:突变和/或重组初始化/终止条件2.2进化计算AI:Summary78AI:EC78进化算法构成tt+1突变重组繁殖选择图片来源IdaSprinkhuizen-Kuyper:Introductionto