人工智能入门 课件 刘峡壁3.符号智能与问题求解、4.进化计算

搜索与问题求解AI:SearchandProblemSolving2大纲什么是搜索?问题表示–状态空间与与或图

–

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

j

将金片B从柱i移动到柱

j

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

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

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

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

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

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

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

动作?

初始与目标状态?

动作代价?

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

数字与空格的位置动作?

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

如图动作代价?

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

AI:SearchandProblemSolving16基于与或图的问题求解找出一个解图，它是代表原始问题求解方案的一个子图步骤1.表示每个问题。步骤2.对问题进行归约，用与或图表示归约过程。步骤3.从端节点向上回溯，直到根节点，标注各个节点可解或不可解。步骤4.如果根节点被标注为可解，输出相应的解图。AI:SearchandProblemSolving17例子:3-阶梵塔问题初始状态目标状态AI:SearchandProblemSolving18步骤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:SearchandProblemSolving19步骤3.搜索该图，以决定根节点可解或不可解.步骤4.输出整个图作为解答.(如何解释?)AI:SearchandProblemSolving20PartⅣ:博弈搜索图片来自：/DL88250AI:SearchandProblemSolving213.1博弈树代表博弈过程的数据结构

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

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

首先,n=1,k1=7,MIN为走步方例：分钱币游戏AI:SearchandProblemSolving23(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:SearchandProblemSolving24游戏中的每一步MAX

和

MIN

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

MIN

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

在想象对手为最强对手的情况下采取最好的行动！在结构上，博弈树是与或图！AI:SearchandProblemSolving25(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:SearchandProblemSolving26

实际条件的限制

如中国象棋:共有

10160

种状态。假设每秒搜索

103

个节点，需要

10145

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

1010年)解决办法

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

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

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

对于对称状态只存储其中一种e(P)＝6-4＝2AI:SearchandProblemSolving29MAX第一次走步AI:SearchandProblemSolving30MAX第二次走步AI:SearchandProblemSolving31最后状态AI:SearchandProblemSolving323.3α-β剪枝通过剪掉博弈树中不必要的分支提高搜索的效率。使用深度限制搜索(DLS)策略AI:SearchandProblemSolving33α-β剪枝例1AI:SearchandProblemSolving34α-β剪枝例1AI:SearchandProblemSolving35α-β剪枝例1AI:SearchandProblemSolving36α-β剪枝例1AI:SearchandProblemSolving37α-β剪枝例1α-β剪枝例2AI:SearchandProblemSolving38S0ABCDFGHEIJKLMNPQRS4861580-64≥4≤1≤4＝45≥5＝4≥4≤0≥0＝0≤-6＝0≤0＝4＊＊＊＊＊＊AI:SearchandProblemSolving39什么是α-β?α

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

v

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

剪掉这一枝β

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

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

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

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

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

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

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

表示博弈过程的数据结构

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

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

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

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

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

(afterDouglasAdams)

神经计算

.进化机制

导致人脑的产生(afterDarwinetal.)

进化计算

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

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

重组前

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

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

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

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

AI:EC6012345678遗传物质:

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

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

它能卡住的皇后个数.

一种棋局的惩罚:

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

目标:使得惩罚值最小

最优棋局:

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

突变:

交换两个随机选择的点

(概率:80%)1234567812345678

重组:

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

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

或

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

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

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

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

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

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

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

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

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

Pc

1发生(Pc

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

B.Two-pointcrossover

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

pmpm称为

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

染色体长度）之间例如