人工智能入门 课件全套 刘峡壁 1.绪论、2.人工神经网络与机器学习 -7 总结

人工智能入门γνωθισεαυτόν(认识你自己)AI:Introduction2AI:Introduction2大纲什么是人工智能(AI)?

什么是思考？人工机器能否以及是否应该达到自我思考的程度？人工智能发展简史人工智能实现途径AI:Introduction3PartⅠ:什么是人工智能？AI:Introduction4

“使真正的机器表现得像科幻电影中的那些机器一样”--RussellBeale请仔细观看视频，思考什么是人工智能？人工智能是通过智能机器延伸、增强人类改造自然和治理社会能力的新兴技术。AI:Introduction5“有多少专家，就会有多少种关于智能的说法.”

--R.J.Sternberg什么是人工智能？？AI:Introduction6

什么是人工智能？Perception行为能力问题求解能力推理能力学习能力社交能力创造力感知能力AI:Introduction7AI:Introduction7什么是人工智能？？理解并创造智能实体多学科交叉计算机科学，哲学

，心理学，语言学，神经学，……包含多个子领域认知科学，自然语言处理，机器学习，模式识别，计算机视觉，数据挖掘，……AI:Introduction8AI:Introduction8如何衡量机器是否具有智能？两种观点强调外在表现(弱人工智能)机器是否具有智能的行为?图灵测试强调内在机制(强人工智能)机器是否真正在思考?J.R.Searle

的中文屋思想实验AI:Introduction9AI:Introduction9图灵测试机器如何表现出智能？图灵(1950)《计算机器与智能》具有可操作性的机器智能测试:模拟试验为了通过图灵测试，需要突破人工智能中的许多重要问题，如知识表示，推理，自然语言理解，机器学习等AI:Introduction10AI:Introduction10中文屋实验一个不懂中文的人呆在一间密闭的屋子里，他有一本记录中文处理规则的书。屋外的测试者从门缝塞给他中文纸条。

他在书中查找处理这些中文语句的规则。

根据规则将一些中文字符抄在纸条上作为对相应语句的回答。

呆在屋内的人显然不理解他所处理的中文。

所以，赛尔勒提出(1980):

-不存在具有理解能力的计算机程序

-赋予非生物机器以智能是语无伦次AI:Introduction11AI:Introduction11人工智能的目标远期目标揭示人类智能的根本机理，用智能机器去模拟、延伸、扩展人类智能，实现脑力劳动的自动化近期目标制造智能机器,尤其是具有智能的计算机程序.提供辅助性的智能工具以帮助人们解决一些具体问题AI:Introduction12“智能”正在变得越来越流行：AI:Introduction13AI:Introduction13人工智能与计算机科学部分类似于数学与物理的关系

计算机科学关注信息处理的一般理论,并为实现人工智能提供计算工具,但是这些不是人工智能关注的重点.人工智能对于计算机科学的发展具有重大影响.

AI:Introduction14PartⅡ:人工智能发展简史AI:Introduction15AI:Introduction15人工智能孕育期哲学

逻辑,推理方法,思维机器,学习的基础,语言,理性数学

形式逻辑符号化,计算理论,可判定性,可处理性,概率经济效用,决策论神经科学

思维活动的物质性心理学

感知,控制,实验技术计算机科学

构造更快的计算机控制论

制造能够随着时间的推移最优化其目标的系统语言学

知识表示，语法AI:Introduction16AI:Introduction16人工智能发展期1943 麦克洛奇和皮兹：大脑的布尔电路模型1950 图灵的“计算机器与智能”1956达特茅斯会议：正式采用名称“人工智能”1952-69 迅速发展，过于乐观1950s 早期的人工智能程序，包括塞缪尔的西洋跳棋程序，Newell 和Simon的定理证明程序，Gelernter的几何引擎1965鲁宾逊归结演绎推理1966-73 出现了计算复杂性问题，神经网络的研究处于停滞等

1969-79 专家系统的早期开发1980- 人工智能走向实际应用1986- 神经网络再次流行1987- 人工智能变成一门科学1995- 智能体概念的出现AI:Introduction17AI:Introduction17人工智能现状深蓝在1997年打败了世界棋王卡斯帕洛夫证明了十几年来未能解决的一个数学猜想（Robbins猜想）横跨美国的汽车无人驾驶（从匹茨堡到圣地亚哥的路途中，98%的路程为自动驾驶）1991年海湾战争期间,美国军方运用人工智能规划程序实现后勤保障，涉及50000辆车辆以及人员NASA通过自动规划程序控制宇航器的飞行PROVERB程序能比大多数人类更好地解决字谜游戏AI:Introduction18AI:Introduction18真实的故事DavidCohn：“虽然计算机已经能够打败世界上最好的棋手，我们却仍然不能使其像4岁小孩一样去思考。”

AaronSlomon：“我们现在才刚刚开始明白怎样用机器处理信息，智能是什么，以及我们人类是什么。”

何不马上开始人工智能探险之旅呢？AI:Introduction19AI:Introduction19PartⅢ:人工智能的实现途径AI:Introduction20AI:Introduction20机器学习

“婴儿机器”符号智能神经网络行为智能进化计算

”人造生命”群智能人工智能的实现途径AI:Introduction21AI:Introduction21机器学习Q.制造一个“婴儿机器”，它通过读书学习、从经验中学习等手段逐步增长智力，这个想法如何？人们早在20世纪40年代就提出了这个设想，最终它将会得到实现。

但是就目前而言，人们对人类学习机理、方法以及如何实现等问题的认识还处于非常初级的阶段，就连“婴儿是如何从经验中进行学习”的问题都知之甚少，更遑论其他。--JohnMcCarthyAI:Introduction22AI:Introduction22符号智能纽维尔和西蒙的“物理符号系统假说”机器对符号信息的处理就足以产生人工智能.人类智能的基础是对符号信息的处理.目前，“物理符号系统假说”是否成立仍然是一个有争议的问题.自上而下的人工智能实现策略AI:Introduction23AI:Introduction23问题求解

专家系统

知识工程搜索,表示,推理GPS,深蓝,DENDRAL,CYC,……问题框架问题(CYC,Go,……)用大量的计算来代替理解符号智能AI:Introduction24AI:Introduction24神经网络人类大脑的工作机制与机器有很大的不同大脑如何工作？

自下而上的人工智能实现策略生物神经网络AI:Introduction25AI:Introduction25发展简史

M-P神经元模型

感知器

霍普菲尔德网络模型,B-P学习方法(Rumelhart&McClelland)

应用

识别,视觉,商业,医学,…….主要问题

-拓扑结构-学习方法神经网络AI:Introduction26AI:Introduction26行为智能布鲁克斯(1991)<<没有表示的智能>>

机器虫:艾伦(Allen),赫伯特(Herbert),成吉思(Genghis)-智能的基本构造单元是一些非常简单的行为，更为复杂的行为是通过这些简单行为的相互作用产生的。-首先应制造具有昆虫一类低等生物智能水平的系统。

AI:Introduction27现场式人工智能

-构造不能与外界友好交互的无实体智能系统(traditional)-构造在真实环境中活动的智能系统(Nouvelle).

行为智能AI:Introduction28AI:Introduction28进化计算生物进化

-产生大量能够适应不同环境的各种生物物种.

模拟进化

-在计算机上模拟生物进化过程,可以让计算机通过进化的方式找到问题的解答。

AI:Introduction29AI:Introduction29遗传算法

像DNA中的分子串一样，用符号串编码问题的解决方案。通过符号串的突变和重组找到好的解。

进化策略

用解的原始形式表示个体,主要用突变和选择作为搜索算子，其中突变通常通过对问题的解向量进行正态随机扰动实现；选择则是按适应度排序方式进行.进化规划

与进化策略很难区分。主要区别是仅利用重组实现解的改变。它将每个个体看做一个物种，而不是同一物种中的不同个体，因此每个父代个体产生一个子代个体。进化计算AI:Introduction30AI:Introduction30群智能智能经常被认为是单个个体的行为。是因为我们有智慧所以组成社会呢？还是因为我们存在于社会中所以有智慧呢？-智能可以在社交活动中呈现出来.突现行为

–

一个群体所表现出来的在其个体身上看不到的行为.群智能-模拟生物间的社会交往-由一组简单智能体呈现出来的集体智慧AI:Introduction31群智能AI:Introduction32观察鸟群和鱼群能够以和谐的方式一起运动，但其中没有指挥员(领导)-是什么决定了没有领导的群体的行为？蚁群能够快速找到从它们的巢穴到食物源的最短路径-同时还能处理许多复杂问题，如:维持城堡，修建巢穴，清理巢穴，进行重物的搬运，等等-单个蚂蚁实际上是在进行盲目地、无记忆地随机行走！无中央控制的分布式系统不仅有助于模拟，而且有助于解决优化问题。AI:Introduction33AI:Introduction33群智能计算工具多智能体系统多个相互作用的智能体组成的系统.应用于电脑游戏,网络,交通,物流,等等。蚁群优化算法1991(Dorigo)主要用于组合优化问题粒子群优化算法1995(Kennedy&Eberhart)更通用的优化技术人工神经网络与机器学习AI:ANN35大纲什么是人工神经网络(ANN)?

多层感知器(MLP)-误差反向传播算法(B-P)机器学习的意义-学习策略监督学习1、人工神经网络01AI:ANN37PartⅠ:什么是ANN?AI:ANN38一个让汽车学习自动驾驶的神经网络T.M.Mitchell,MachineLearning,2006隐藏单元的权值AI:ANN39汽车自动驾驶的视频AI:ANN401.1人工神经网络将相互独立的单元之间连接起来形成一种图的结构，这样的图可能是有环的也可能是无环的，可能是有向图也可能是无向图.

自底向上AI

受生物神经系统的启发，从结构上模拟仿真AI功能AI:ANN41生物神经系统

时间和空间上的累积

兴奋和抑制图片来源：http://kvhs.nbed.nb.ca/gallant/biology/neuron_structure.jpgAI:ANN42人工神经系统

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

径向距离AI:ANN44激活函数

阈值型线性饱和线性S型函数双曲正切函数高斯函数AI:ANN451.2人工神经网络拓扑结构前馈型神经网络-没有环-静态结构

反馈型神经网络结构-有环-动态结构(非线性动力系统)AI:ANN46前馈网络的一般结构反馈网络的一般结构AI:ANN471.3人工神经网络的学习方法神经网络根据所处环境对它的刺激自适应的调整其网络结构中的自由参数.学习模型

渐进式vs.批处理两类

监督型vs.非监督型AI:ANN48重要的神经网络模型模型结构学习方法模型结构学习方法多层感知器前馈型网络结构误差修正玻尔兹曼机单层，反馈型网络结构随机性径向基函数网络多层，前馈型网络结构误差修正自适应共振理论两层，反馈型网络结构竞争型学习霍普菲尔德网络单层，反馈型网络结构外积Kohonen自组织特征映射网单层软竞争学习AI:ANN49PartⅡ:多层感知器(MLP)AI:ANN502.1B-P神经网络结构

一种多层感知机,其中的激活函数采用S型函数.AI:ANN51B-P学习算法学习方法

-输入数据被前向输入到隐含层,然后再输入到输出层

-误差信息被反向传播，从输出层到隐含层再到输入层Rumelhart&Meclelland,Nature,1986AI:ANN52B-P学习步骤Step1.在训练集中选择一种模式并将其输入到网络中Step2.计算输入序列中输入层，隐含层，输出层神经元的激活情况.Step3.通过比较实际输出与期望输出，计算输出神经元的误差.Step4.用计算出来的误差更新网络中的所有权重，从而使全局误差度量变小.Step5.重复上述Step1-Step5直到全局误差小于一个给定的阈值.AI:ANN53B-P求导全局误差度量理想输出实际输出平方误差目标是最小化平方误差,即达到最小均方误差(MSE)2、机器学习02AI:MachineLearning55PartⅠ:机器学习的意义

AI:MachineLearning56机器学习什么？学习是系统中的变化，这种变化使系统在重复同样工作或类似工作时，能够做得更好。

西蒙机器学习研究如何使计算机程序自动根据经验提升其性能。应用领域涵盖从大量数据中发现一般规则的数据挖掘程序到自动学习用户兴趣的信息过滤系统等。TomM.MitchellAI:MachineLearning57定义学习的任务基于经验，根据性能准则，提升完成相应任务的性能任务:下跳棋性能:对于任意对手，取胜的概率

经验:以自己为对手，进行的练习任务:识别手写字性能:被正确分类的字所占的比例经验:经过人工标注的手写字的数据库任务:视觉传感器自动驾驶性能:出错前行驶的平均距离经验:人类驾驶的时候记录下来的一系列图像和控制命令ExamplesAI:MachineLearning58为什么要进行机器学习？在环境事先未知时，学习至关重要(可用于开发能够自动适应环境的系统). 比如，当设计者缺少关于环境的全部信息时学习是一个很有用的系统构建方法(可用于构建人工方式很难实现或者很昂贵的系统).比如,将系统暴露在真实的环境中自我提升而不是直接构建该系统。AI:MachineLearning59为什么要进行机器学习？（续）从庞大的数据库里发掘新信息(数据挖掘)。商场购物数据分析(如：尿布和啤酒)医学文本挖掘(如：偏头痛和钙)对于机器学习的研究可以帮助我们理解人类以及其他生物的学习方式。AI:MachineLearning60学习系统的评价实验在不同的基准数据集上，采用交叉验证试验来比较各种不同的方法。收集评价系统性能的数据，如测试准确率、训练时间、测试时间等。分析方法在统计显著性上的不同。理论从数学上分析算法，为以下几点提供理论支持：计算复杂性拟合训练数据的能力样本复杂性(得到一个准确的函数所需要的训练数据的个数)AI:MachineLearning61S.J.RusselllandP.Norvig,“artificialintelligence:amodernapproach”.具有学习能力的智能系统的架构AI:MachineLearning62学习机构学习机构的设计需要考虑：学习性能组件中的什么部分可利用什么反馈方式来学习这些部分怎样表示性能组件？反馈类型: 监督学习:每一个输入数据都有对应的期望输出非监督学习:没有输入数据的期望输出强化学习:通过奖惩学习AI:MachineLearning63学习策略机械式学习

基于存储的学习指导式学习

将外部指导者提供的知识形式转化为可供执行机构直接使用的知识形式类比学习

利用不同领域知识的相似性AI:MachineLearning64学习策略（续）解释学习

演绎和归纳相结合归纳学习

1.人工神经网络

2.统计学习

3.决策树

4.聚类

监督非监督AI:MachineLearning65机械式学习学习==存储？存储问题的解，当遇到相同的问题时进行检索。存储和计算的权衡AI:MachineLearning66PartⅡ:监督学习AI:MachineLearning672.1什么是监督学习？最简单的形式:根据输入数据学习一个函数f

是目标函数

一个数据是一个(x,f(x))对

问题:给定一个训练数据集，找到一个函数h，以使

h≈fAI:MachineLearning68监督学习方法构造

h，使h在训练数据集上与f

吻合(如果对于所有的数据，h都与f吻合，则h与f是一致的。)如：

曲线拟合:AI:MachineLearning69监督学习方法构造

h，使h在训练数据集上与f

吻合(如果对于所有的数据，h都与f吻合，则h与f是一致的。)如：

曲线拟合:AI:MachineLearning70监督学习方法构造

h，使h在训练数据集上与f

吻合(如果对于所有的数据，h都与f吻合，则h与f是一致的。)如：

曲线拟合:AI:MachineLearning71监督学习方法构造

h，使h在训练数据集上与f

吻合(如果对于所有的数据，h都与f吻合，则h与f是一致的。)如：

曲线拟合:AI:MachineLearning72监督学习方法构造

h，使h在训练数据集上与f

吻合(如果对于所有的数据，h都与f吻合，则h与f是一致的。)如：

曲线拟合:AI:MachineLearning73监督学习方法构造

h，使h在训练数据集上与f

吻合(如果对于所有的数据，h都与f吻合，则h与f是一致的。)如：

曲线拟合:奥坎木剃刀:优先选择符合数据的最简单模型AI:MachineLearning74PartⅢ:非监督学习：聚类AI:MachineLearning754.1什么是聚类？典型的非监督学习只给出输入数据，不给出期待的输出根据数据之间的相似性，将数据分成几个簇的过程。发现数据组并鉴别出数据中令人感兴趣的数据分布AI:MachineLearning764.2划分聚类方法根据给定的标准，把数据集划分成k个子集（簇）。在所有可能的划分中搜索最优的划分。

盲目搜索

启发式搜索

AI:MachineLearning77总结学习是一个系统通过经验来提高性能的过程。有学习能力的智能系统的四个要素：

评价机构,环境机构,执行机构,学习机构AI:MachineLearning78学习策略包括机械式学习，指导式学习，类比学习，归纳学习，解释学习。机械式学习存储问题描述及其对应的正确解，当需要的时候进行检索。AI:MachineLearning79监督学习中，从输入—输出数据对中学习得到一个函数。

AI:MachineLearning80非监督学习中，只有输入数据，没有输入数据的期望输出信息。聚类分析是按照数据间的相似性，对数据集进行分类的过程。划分聚类和层次聚类是两个基本策略。搜索与问题求解AI:SearchandProblemSolving82大纲什么是搜索?问题表示–状态空间与与或图

–

它们体现了两种问题求解的思路!博弈搜索–极大极小算法–α-β剪枝AI:SearchandProblemSolving83PartⅠ:什么是搜索?AI:SearchandProblemSolving84Theseus怎样找到逃出Minotaur的迷宫的路?Ariadne的线索:AI:SearchandProblemSolving85什么是搜索?以可以接受的计算代价，在问题所有解答中找出最优解或可行解。理想的搜索算法：尽可能快地找到最优解.求解的效果与效率之间存在矛盾完备性,最优性,复杂性AI:SearchandProblemSolving86PartⅡ:问题表示AI:SearchandProblemSolving87例子:2-阶梵塔问题初始状态目标状态1目标状态2规则:1.每次移动一个金片2.大的金片不能放在小的金片上面.AI:SearchandProblemSolving88步骤1表示所有的状态,包括初始状态和目标状态初始状态目标状态步骤2表示状态转换函数AI:SearchandProblemSolving89将金片A从柱i移动到柱

j

将金片B从柱i移动到柱

j

所有函数:步骤3构造状态空间AI:SearchandProblemSolving90步骤4

搜索该图以找到问题解答AI:SearchandProblemSolving912.1状态空间S:状态集合F:状态转换函数（或行动）的集合

C:状态转换函数代价的集合(如果不求最优解，可以不考虑此因素)I:初始状态集合G:目标状态集合一个状态空间对应于一个图,其中从初始状态到目标状态的路径就是问题的一个解。AI:SearchandProblemSolving92基于状态空间的问题求解步骤1

表示所有状态，标出其中的初始状态和目标状态.步骤2

表示所有状态转换函数步骤3

以状态为节点，以状态转换函数为边，构成一个图。步骤4

搜索该图以发现对应于最优解或可行解的路径。AI:SearchandProblemSolving93例子:八数码问题状态?

动作?

初始与目标状态?

动作代价?

AI:SearchandProblemSolving94例子:八数码问题状态?

数字与空格的位置动作?

空格上、下、左、右移动初始与目标状态?

如图动作代价?

每移动一下代价为1AI:SearchandProblemSolving95与或图实现问题归约的数据结构-每一个节点对应于一个问题-“与”节点=分解-“或”节点=转换-端节点*终止节点=本原问题*其他端节点=不可解问题-可解节点与不可解节点

AI:SearchandProblemSolving96基于与或图的问题求解找出一个解图，它是代表原始问题求解方案的一个子图步骤1.表示每个问题。步骤2.对问题进行归约，用与或图表示归约过程。步骤3.从端节点向上回溯，直到根节点，标注各个节点可解或不可解。步骤4.如果根节点被标注为可解，输出相应的解图。AI:SearchandProblemSolving97例子:3-阶梵塔问题初始状态目标状态AI:SearchandProblemSolving98步骤1.表示问题

问题状态:

原始问题:(1,1,1)(3,3,3)步骤2.问题归约

将原始问题分解为:-子问题1=(1,1,1)(1,2,2)-子问题2=(1,2,2)(3,2,2)√-子问题3=(3,2,2)(3,3,3)

继续分解子问题2和3

AI:SearchandProblemSolving99步骤3.搜索该图，以决定根节点可解或不可解.步骤4.输出整个图作为解答.(如何解释?)AI:SearchandProblemSolving100PartⅣ:博弈搜索图片来自：/DL88250AI:SearchandProblemSolving1013.1博弈树代表博弈过程的数据结构

-2个玩家(MAX和MIN)-确定性的-轮流进行-零和的-信息完备AI:SearchandProblemSolving102游戏状态：(K1,K2,….,Kn,MINorMAX)每堆钱币个数当前走步方每次MIN或MAX选择一堆钱币并且把它分成数目不等的两堆。

当MIN或MAX不能完成任务时,就输了。

首先,n=1,k1=7,MIN为走步方例：分钱币游戏AI:SearchandProblemSolving103(7,MIN)(6,1,MAX)(5,2,MAX)(4,3,MAX)(5,1,1,MIN)(4,2,1,MIN)(3,2,2,MIN)(3,3,1,MIN)(4,1,1,1,MAX)(3,2,1,1,MAX)(2,2,2,1,MAX)(3,1,1,1,1,MIN)(2,2,1,1,1,MIN)(2,1,1,1,1,1,MAX)分钱币游戏的博弈树MAX的必胜招?AI:SearchandProblemSolving104游戏中的每一步MAX

和

MIN

总是采取对自己最有利的行动。为了能够胜利,MAX应该每一步选择最有利的行动,同时认为

MIN

也会每一步都采取对MIN最好的行动(也就是说，对MAX最坏)

在想象对手为最强对手的情况下采取最好的行动！在结构上，博弈树是与或图！AI:SearchandProblemSolving105(7,MIN)(6,1,MAX)(5,2,MAX)(4,3,MAX)(5,1,1,MIN)(4,2,1,MIN)(3,2,2,MIN)(3,3,1,MIN)(4,1,1,1,MAX)(3,2,1,1,MAX)(2,2,2,1,MAX)(3,1,1,1,1,MIN)(2,2,1,1,1,MIN)(2,1,1,1,1,1,MAX)作为与或图进行搜索作为与或图进行搜索?AI:SearchandProblemSolving106

实际条件的限制

如中国象棋:共有

10160

种状态。假设每秒搜索

103

个节点，需要

10145

年找到一个最优走步。(最新估计宇宙年龄为

1010年)解决办法

截断策略:限制博弈树的搜索深度

估价函数:从MAX的角度出发估计博弈状态，值越大，该状态对MAX越有利。

3.2极大极小搜索AI:SearchandProblemSolving107选择移动到具有最高极大极小值的位置!例：两个玩家的游戏AI:SearchandProblemSolving108例:一字棋估价函数:e(P)=e(+P)－e(-P)

对于对称状态只存储其中一种e(P)＝6-4＝2AI:SearchandProblemSolving109MAX第一次走步AI:SearchandProblemSolving110MAX第二次走步AI:SearchandProblemSolving111最后状态AI:SearchandProblemSolving1123.3α-β剪枝通过剪掉博弈树中不必要的分支提高搜索的效率。使用深度限制搜索(DLS)策略AI:SearchandProblemSolving113α-β剪枝例1AI:SearchandProblemSolving114α-β剪枝例1AI:SearchandProblemSolving115α-β剪枝例1AI:SearchandProblemSolving116α-β剪枝例1AI:SearchandProblemSolving117α-β剪枝例1α-β剪枝例2AI:SearchandProblemSolving118S0ABCDFGHEIJKLMNPQRS4861580-64≥4≤1≤4＝45≥5＝4≥4≤0≥0＝0≤-6＝0≤0＝4＊＊＊＊＊＊AI:SearchandProblemSolving119什么是α-β?α

是MAX顶点倒推值的最小边界如果

v

比α更小,MAX将不搜索它。

剪掉这一枝β

定义方式类似，但针对MIN节点AI:SearchandProblemSolving120确定性博弈程序现状

西洋跳棋:1994年，Chinook终结了人类世界冠军MarionTinsley长达40年的统治。

国际象棋:1997年，DeepBlue在六回合制比赛中打败了人类世界冠军GarryKasparov.

黑白棋:人类高手拒绝与机器比赛，因为机器下棋水平实在是太好了。

围棋:人类高手同样拒绝与机器比赛，因为机器下棋水平实在是太差了。AI:SearchandProblemSolving121深蓝AI:SearchandProblemSolving122总结状态空间-五个要素(S,F,C,I,G)-问题的解是从初始顶点到目标顶点的一条路径与或图-问题规约

-目标是确定根节点是否可解-问题的解是让根节点可解的一个子图AI:SearchandProblemSolving123搜索算法的效果和效率是一对矛盾。在设计和评价搜索算法时，需要综合考虑算法的完备性、最优性和复杂性。具体设计策略有盲目搜索与启发式搜索之分，全局搜索和局部搜索之分，以及搜索最优解和可行解之分。

图搜索算法的一般结构是不断扩展顶点，直到发现目标顶点（状态空间）或者确定初始顶点的可解性（与或图）。总结AI:SearchandProblemSolving124不同图搜索算法的主要区别在于顶点的扩展顺序不同。盲目搜索不考虑问题特性,包括广度优先搜索、深度优先搜索、有界深度优先搜索和迭代加深深度优先搜索。启发式搜索算法根据问题所提供的启发式信息，用估价函数估计顶点的搜索效率，选择估计效率最高的顶点进行扩展。A*算法是影响最大的，应用于状态空间的启发式搜索算法。它通过对估价函数施加一定约束，可以保证搜索到最优解。总结AI:SearchandProblemSolving125博弈树

表示博弈过程的数据结构

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

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

在有界深度优先搜索过程中，通过剪掉一些不必要的分枝达到提高搜索效率的目的。总结进化计算01AI:EC127大纲生命对搜索方法的启示什么是进化计算(EC)?进化算法(EA)遗传算法进化规划进化策略AI:EC128

一个启发式搜索的新思路?进化计算确定还是随机?若确实如此启发式搜索（优化）方法是数学和计算机科学的核心主题AI:EC129PartⅠ:生物对搜索的启示AI:EC130Q.什么是搜索问题最好的解决方案?.人类的大脑

能产生“汽车,纽约,战争,等”

(afterDouglasAdams)

神经计算

.进化机制

导致人脑的产生(afterDarwinetal.)

进化计算

AI:EC131达尔文进化基于群体的进化，而非个体的变化适者生存:有限的资源导致激烈的竞争,那些能最有效的占有资源的个体(最适应环境的个体)有更高的概率被繁殖下去(被选择)AI:EC132达尔文进化多样性引起变化:如果表现特征:有更高的概率被繁殖下去可以继承则他们往往会形成更多的后代，从而导致新的组合特征.

随机性的作用最优的解不一定都能生存下去AI:EC133自然遗传学遗传信息需要通过有机体的DNA编码遗传下去基因的微小变化导致生物体的微小变化(如身高,头发，颜色)对于一个特定的物种，其遗传物质是基本相同的AI:EC134基因和基因组由DNA链编码的基因称为染色体在大多数细胞中，有两条染色体排成双螺旋结构(diploidy)一个个体的全部遗传物质的集合称为基因组AI:EC135个体遗传物质改变的主要手段:重组从至少两个父代个体中获得遗传物质产生新的个体,如,在一对染色体的交叉点上连接交换染色体:

重组前

重组后图片来源BenPaechter:EvolutionaryComputing–APracticalIntroductionAI:EC136个体遗传物质改变的主要手段:突变一些遗传物质会发生轻微的改变，这个过程偶尔发生这意味着子代个体可能拥有父代个体所没有的遗传物质这种改变极有可能是灾难性的AI:EC137进化理论突变,重组

新的遗传物质或者新的组合.繁殖的越多则基因的性能可以得到更多的改进

好的基因得到更多被遗传的机会坏的基因则会在遗传的过程中减少在其生存环境中，有机体作为一个整体得到进化.采用进化的方法计算或求解问题能够帮助我们找到问题的最优解：进化计算AI:EC138PartⅡ:什么是进化计算?AI:EC139以这样的方式放置8皇后一个8x8的棋盘上，他们不能互相卡到对方，例子:8皇后问题

[AfterA.E.EibenandJ.E.Smith,IntroductiontoEvolutionaryComputing]

AI:E传物质:

一列数字1-8表现特性:

一个棋局配置Obviousmapping8皇后问题:表示AI:EC141一个皇后的惩罚:

它能卡住的皇后个数.

一种棋局的惩罚:

对每一个皇后的惩罚值求和.

目标:使得惩罚值最小

最优棋局:

惩罚值的倒数最大时8皇后问题:适应度评价AI:EC142

突变:

交换两个随机选择的点

(概率:80%)1234567812345678

重组:

交叉(概率:100%)876425311352467887645123135628748皇后问题:遗传算子5432126478AI:EC143父代选择:挑选五个父代个体，并选择其中最优的两个执行重组操作生存选择(替换策略)当一个新的子代个体要插入种群中时，选择种群中将被替换的一个个体，选择规则为:将种群中的个体按适应度降序排列将个体由高到低列举替换排列中第一个适应度比当前子代适应度低的个体8皇后问题:选择AI:EC144初始化:随机终止:根据适应度的评价问题得到了解决或者循环迭代次数达到最大（比如10，000）8皇后问题:初始化\终止条件AI:EC1458皇后问题:总结注意：操作和参数的选择不只有这一种可能AI:EC146生物进化与搜索的类比进化个体适应度环境搜索候选解解的质量待求解的问题AI:EC147进化算法构成tt+1突变重组繁殖选择图片来源IdaSprinkhuizen-Kuyper:Introductionto

EvolutionaryComputation,2000.AI:EC148进化机制遗传增加了多样性突变重组选择减少了多样性父代选择：选择用于繁殖的父代子代选择：选择保留下来的子代AI:EC149进化中的循环过程重组突变种群子代父代父代选择子代选择图片来源BenPaechter:EvolutionaryComputing–APracticalIntroductionAI:EC150表示基因表示:编码:表型=>基因(不一定是一一对应的)解码:基因=>表型(必须是一一对应的)表型表示:问题的特定编码AI:EC151进化(适应度)函数表示对种群（解）的要求，即质量函数

或

目标函数为每一个表型计算一个代表其适应度的实数，这样构成了遗传选择的基础因此该函数的判断能力越大越好AI:EC152基因操作产生新的候选解

通常根据父代个体数分为两类:=1:突变操作>1:重组操作=2:交叉操作有很多关于重组和突变重要性的争论现在大多数进化算法两者都有AI:EC153父代选择机制个体作为父代的概率是根据其适应度得出来的高质量的解有更高的概率被作为父代个体出现，但它并不是一定会作为父代个体出现，即使是种群中最差的个体也不是完全没有机会作为父代个体出现这种随机性可以在一定程度上避免陷入局部最优解.AI:EC154子代选择或称为替换策略从子代+父代的种群中产生新的种群的方法两种方法适应度准则

:例如挑选种群中一定数量适应度最好的个体作为新的种群年龄准则:

产生和父代个体一样多的子代个体，淘汰所有的父代个体AI:EC155初始化/终止条件初始化

通常采用随机初始化的策略。终止条件

检查每一代种群个体，看以下条件是否满足：

达到给定的或期望的适应度达到最大的种群更新次数种群中的多样性水平最小连续几代更新都没有使得种群中的适应度得到改进AI:EC156PartⅢ:进化算法AI:EC157主要进化算法遗传算法(GA)J.Holland1962(AnnArbor,MI)进化规划(EP)L.Fogel1962(SanDiego,CA)进化策略(ES)I.Rechenberg&H.-P.Schwefel1965(Berlin)遗传规划(GP)J.Koza1989(PaloAlto,CA)算法之间的相似性比差异更重要AI:EC158分类图片来源:Introductionto

EvolutionaryComputationbyIdaSprinkhuizen-KuyperAI:EC159技术总结GAEPESGP表示基因型表现型表现型基因型突变√√√√重组√×√√父代选择概率选择确定选择概率选择概率选择子代选择排斥,确定混合，随机混合，确定排斥，确定AI:EC1603.1遗传算法(GA)Holland最初提出的遗传算法现在被称作简单遗传算法(SGA)现在还常常被用作新的遗传算法的测试基准其他遗传算法可能应用不同的:表示方法突变方法交叉方法选择机制AI:EC161表示基因组通常被用来表示候选解定长二进制编码(SGA)Holland传统的

其收敛性有理论上的保证实值基因组人工进化收敛性的证明很困难AI:EC162贪婪选择:选择适应度最好的解按概率选择:概率与适应度成正比例如采用轮盘赌的方法(SGA)GA操作:选择例如适应度为：(2200,1800,1200,950,400,100)AI:EC163GA操作:交叉对于给定的父代个体，交叉以特定的概率

Pc

1发生(Pc

的典型范围为(0.6,0.9))否则父代个体直接作为子代个体(克隆)例如,A.One-pointcrossover(SGA)

B.Two-pointcrossover

图片来源:IntroductiontoStochasticSearchandOptimization(ISSO)byJ.C.SpallAI:EC164GA操作:突变独立地改变每一个基因的概率

pmpm称为

突变概率典型值介于（1/种群规模）和（1/

染色体长度）之间例如AI:EC165应用例

[AfterA.L.Nelson]在一个由方格组成的棋盘上找到两点间的最优路径该生物体:占据一个方格能够移动到最近邻的方格目标:在最短的步骤内从灰色方格移动到绿色方格AI:EC166基因组例如:通过一个方向符号串表示一条路径.方向的表示:北=00,东=10,南=11,西=01AI:EC167种群种群P

由一系列个体pn组成，N表示种群中拥有的个体数目AI:EC168适应度函数和选择策略适应度函数距离目标的最短合法路径:F(pn)=S(steps)父代选择:贪婪算法AI:EC169基因改变交叉:单点交叉突变:位串点突变AI:EC170实例方格尺寸:4X4种群中个体数目:N=4基因编码:16bits适应度函数:F(p)=距离目标的方格数选择策略:贪婪算法AI:EC171实例：初始化种群初始化种群P(0):4个随机的16位串AI:EC172实例：适应度计算F(p1)=(8-8)–4=-4F(p2)=-5F(p3)=-6F(p4)=-4AI:EC173实例：选择和更新选择p1

和

p4

作为父代个体通过交叉和重组产生子代个体AI:EC174实例：子代选择新一代个体为：AI:EC175对子代个体重复前面的操作重复:F(p1)=-4F(p2)=-4

F(p3)=0F(p4)=-4AI:EC176总结进化计算基于生物进化机制优化行为—最优解个体

–

解;适应度

–

目标;环境

–

问题EC的组成表示:个体和种群适应度估计:目标选择:父代和子代基因操作:突变和/或重组初始化/终止条件AI:EC177总结EC的主要特征:并行性和随机性易于应用主流进化算法遗传算法进化规划进化策略遗传规划AI:EC178总结遗传算法表示:位串(基因型)突变:位交换重组:交叉父代选择:根据适应度大小按概率选择子代选择:完全取代行为智能01AI:NouvelleAI180大纲智能体-结构

•没有表示和推理的智能

-学习强化学习-Q-学习AI:NouvelleAI181PartⅠ:智能体AI:NouvelleAI182机器人世界杯2008决赛

中国，苏州到2050年，组建一个可以取胜人类足球冠军队的全自主机器人队伍。

-AI:NouvelleAI183远程智能体实验(RAX)深空1号任务旨在验证技术；让AI软件成为航天器的主要指挥官；1999年5月进行测试。

NANA,USa

AI:NouvelleAI1841.1智能体定义RussellandNorvig:“能够通过传感器感知环境并根据环境做出行动的任何系统”AI:NouvelleAI185智能体的弱概念五个主要特点:现场性:工作在某种环境中，并能与环境进行交互自主性:在不用干涉的情况下自主运行主动性:在自身目标驱动下表现出主动的行为反应性:能感知外界环境并根据环境变化做出适当反应社会性:以其他智能体进行通信AI:NouvelleAI1861.2单智能体结构慎思型智能体:符号化表示和处理-IRMA,GRATE反应型智能体:感知-行为模式智能体系统-包容结构-网络结构混合型智能体:可以直接对外界刺激作出反应，也可以在内部推理的基础上采取行动-过程推理系统（PRS）-图灵机模型-InteRRaPAI:NouvelleAI1871.2.2反应型结构反应型结构不需要使用符号表示外部环境状态，也不需要复杂的符号推理。包容结构网络结构没有表示和推理的智能AI:NouvelleAI188包容结构麻省理工大学智能研究所的布鲁克斯基于包容结构构造了一些机器人。由任务导向的行为模块构成高层模块有更多特殊任务单独构建各个模块高层模块对低层模块起到一定的控制作用，但这种影响对于低层模块是不可见的，高层模块只在需要时插入来抑制低层模块的行为。没有明确的推理甚至没有模式匹配.在构造的初期生成智能体函数AI:NouvelleAI189布鲁克斯包容结构图解不同的智能体并行构建，但是以分级的形式决策行为。高层智能体能够抑制低层智能体的输出，并且接管行为的控制(b)一种应用：腿部移动控制腿向上或向下腿向前或向后霍尔克·克鲁斯（HolkCruse）：作为控制系统的神经网络（第二版），2006年包容结构AI:NouvelleAI190MIT布鲁克斯的机器人Genghis:过去在机器人实验室.目前在Smithsonian航空博物馆.Cog:类人智能需要类似人的与外界交互方式Herbert:一个基于互动的可以收集饮料瓶的机器人

Allen:机器人实验室的第一个移动机器人./projects/humanoid-robotics-group/AI:NouvelleAI191网络结构动作单元的集合各个动作单元根据内部需求和外部激励，竞争对智能体行为的控制。外部激励:环境条件内部需求:通过链式结构:激活模块增加其后续模块的兴奋性未激活模块增加其前面模块的兴奋性所有模块抑制其他竞争者的兴奋性AI:NouvelleAI192网络结构目标:保持文雅的同时解决口渴问题(即不让嘴去主动靠近水杯，而是拿起水杯送到嘴)Maes:Theagentnetworkarchitecture,1991AI:NouvelleAI1931.2.3混合结构完全的慎思型和完全的反应型都不适合用来建立智能体。

结合二者:过程推理系统（PRS）图灵机InteRRaPAI:NouvelleAI194图灵机为动态变化的现实世界中的自主智能体设计三层:反应层:直接对外部激励做出迅速的反应规划层:制定规划建模层:对外部世界状态进行建模AI:NouvelleAI195图灵机（续）每层直接与感知器和控制器相连任意两层之间存在相互联系每一层都有独自的反应，在不同的层间发生冲突时：使用上下文触发的控制规则解决.AI:NouvelleAI196图灵机架构InnesA.Ferguson:TouringMachines:AutonomousAgentswithAttitudes,1992AI:NouvelleAI197InteRRaP分层的混合结构:在不同的层次上对环境进行建模存在不同层次的表示不同层次的知识和推理在垂直分层的结构中只有相邻层之间存在通信行为层(与领域相关)规划层(非社会性的目标驱动行为)协作层(社会行为，如联合规划等)AI:NouvelleAI198InteRRaP

结构/~chrender/Agenten/Agenten.htmlAI:NouvelleAI1991.3智能体的学习智能体要与动态变化的负责的外部环境进行交互，因此智能体需要进行自主学习。学习的基本思想如下：智能体感知到的知识不只是用来决定下一步行动，也用来提高智能体的能力，以在后面的行动中表现更佳。AI:NouvelleAI200学习类型监督学习函数学习需要的输入输出对已经给定或者可以推导得到。非监督学习没有输出的信息强化学习智能体在环境中作出行动，对于智能体的每一步行动，都会得到一个评价值，但是不被告知如何行动才可以正确的达到目标。√AI:NouvelleAI201PartⅡ:强化学习（RL）AI:NouvelleAI2023.1强化学习简介强化学习是一种通过奖励和惩罚来实现智能体的方式，无需指定完成何种任务.(Kaelbling,1996)智能体怎样如何从成功和失败中学习，从奖励和惩罚中学习？基于试错交互方式AI:NouvelleAI203强化学习模型Picture：R.Sutton:ReinforcementLearning:ATutorialAI:NouvelleAI204经典示例-房间里的机器人向上的行为:80%移动到了上方,10%移动到了左方,10%移动到了右方在[4,3]处奖励为+1,在[4,2]处的奖励为-1,其他步为0RussellandNorvig,ArtificialIntelligence:AModernApproach,2ededition,2006AI:NouvelleAI205经典示例–杆平衡在一个移动的平板车上面让一个长杆平衡直立RussellandNorvig,ArtificialIntelligence:AModernApproach,2ededition,2006AI:NouvelleAI206不需要模型的方法:Q-学习算法学习V*(简记为V*)对于任何状态s，执行向前搜索以选出最好的行动如果智能体已知下面函数将会得到很好的效果fS:状态

行为

状态fR

:状态

行为

R如果fS

和fR

未知,将不能通过这种方式选择下一步行为AI:NouvelleAI207Q-值定义一个与

V*相似的新的函数如果智能体对Q进行学习，将能够在fS

和

fR

未知的情况下选择最优行动AI:NouvelleAI208r(状态,行为)立即收益值Q(状态,行为)值V*(状态)值100

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

9010008190100Q-值的计算

使用折扣收益，折扣因子为0.981=0+0.9*90AI:NouvelleAI209学习Q-值注意:Q

和

V*密切相关将Q写成递归形式：使用Q-值问题:如何学习?问题:如何选择最优行为?AI:NouvelleAI210Q-学习步骤对于每一个<s,a>初始化Q-值观察到当前状态s重复以下步骤根据当前Q-函数选择动作获得奖励r观察到新的状态s’令令s=s’AI:NouvelleAI211Q-学习举例:汉诺塔/kardi/tutorial/ReinforcementLearning/Tower-of-Hanoi.htmAI:NouvelleAI212带奖励值的状态图AI:NouvelleAI213R矩阵初始QQ矩阵最终QQ矩阵更新AI:NouvelleAI214红箭头指示的是从起始节点到目标节点的最优路径实际上,图中的Q值可以用于从图中任何一个起始节点（不只是状态1）通过最短路径走到目标节点状态图里的解决路径AI:NouvelleAI215Q-学习演示：

路径学习器AI:NouvelleAI216总结行为智能没有表示和推理的智能SituatedAI智能体弱概念和强概念结构类型有慎思型

(BDI模型),反应型

(包容结构,网络结构),and混合型

(PRS,图灵机，InteRRaP)AI:NouvelleAI217总结使用强化学习得到智能体不同于监督学习和非监督学习从奖励和惩罚中学习试错交互Q-学习群智能AI:SI219大纲什么是群智能(SI)?

模拟SI进行搜索

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

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

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

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

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

代理如何相互交互

例如：蚂蚁的信息素

单个代理的简单行为+一组代理之间的通信=该组代理的涌现复杂行为AI:ANN231间接通信信号传播：-一个代理发送一个信号，该信号被广播到环境中，并且其强度随着距离的减