人工智能导论-第三章高级搜索1课件

第三章高级搜索主要内容局部搜索方法模拟退火算法遗传算法优化与组合优化问题很多问题属于优化问题，或者可以转化为优化问题如TSP问题，皇后问题优化问题的描述设x是决策变量，D是x的定义域，f(x)是指标函数，g(x)是约束条件集合。则优化问题可以表示为，求解满足g(x)的f(x)最小值问题。如果在定义域D上，满足条件g(x)的解是有限的，则优化问题称为组合优化问题。算法的时间复杂度对于组合优化问题，由于其可能的解是有限的，当问题的规模比较小时，总可以通过枚举的方法获得问题的最优解，但当问题的规模比较大时，就难于求解了。常用的算法复杂度函数

输入量n复杂性函数10203040100n10ns20ns30ns40ns100nsnlogn10ns26.0ns44.3ns64.1ns200nsn2100ns400ns900ns1.6us10us2n1.0us1.0ms1.1s18.3min4.0世纪n!3.6ms77.1年8.4×1013世纪2.6×1029世纪3.0×10139世纪时间复杂性函数比较（10亿次/秒）一些难的组合优化问题旅行商问题背包问题装箱问题...寻求在可以接受的时间内得到满意解的方法邻域的概念邻域，简单的说就是一个点附近的其他点的集合。在距离空间，邻域就是以某一点为中心的圆。在组合优化问题中的定义：设D是问题的定义域，若存在一个映射N，使得：则称N(S)为S的邻域。领域中的元素称为邻居。例：皇后问题S={Si}表示一个可能解，其中Si表示在第i行，第Si列有一个皇后。如四皇后问题的一个解：S=(2,4,1,3)

Q

QQ

Q

定义映射N为棋盘上任意两个皇后的所在行或列进行交换，即S中任意两个元素交换位置。例：当S=(2,4,1,3)时，其邻域为：N(S)={(4,2,1,3),(1,4,2,3),(3,4,1,2),(2,1,4,3),(2,3,1,4),(2,4,3,1)}例：旅行商问题用一个城市的序列表示一个可能的解。通过交换两个城市的位置获取S的邻居例：简单交换方法设S=(x1,x2,…xi-1,xi,xi+1,…,xj-1,xj,xj+1,…,xn)则通过交换xi和xj两个城市的位置可以得到S的一个邻居：S'=(x1,x2,…xi-1,xj,xi+1,…,xj-1,xi,xj+1,…,xn)x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+1例：逆序交换方法设xi、xj是选取的两个城市，所谓的逆序交换方式是指，通过逆转xi、xj两个城市之间的城市次序来得到S的邻居。设：S=(x1,x2,…xi-1,xi,xi+1,…,xj-1,xj,xj+1,…,xn)则：S'=(x1,x2,…xi-1,xi,xj-1,xj-2…,xi+1,xj,xj+1,…,xn)x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+1局部搜索算法基本思想：在搜索过程中，始终向着离目标最接近的方向搜索。目标可以是最大值，也可以是最小值。在后面的介绍中，如果没有特殊说明，均假定是最小值。局部搜索算法（LocalSearch）1，随机的选择一个初始的可能解x0∈D，xb=x0，P=N(xb)；2，如果不满足结束条件，则3，Begin4， 选择P的一个子集P'，xn为P'中的最优解5， 如果f(xn)<f(xb)，则xb＝xn，P=N(xb)，转2；f(x)为指标函数。6， 否则P=P–P'，转2。7，End8，输出计算结果9，结束例：5城市旅行商问题●●●●●ABCDE71361071010965设初始的可能解：x0=(a,b,c,d,e)f(xb)=f(x0)=38通过交换两个城市获得领域P={(a,c,b,d,e),(a,d,c,b,e),(a,e,c,d,b),(a,b,d,c,e),(a,b,e,d,c),(a,b,c,e,d)}设每次随机从P中选择一个邻居。第一次循环从P中选择一个元素，假设xn=(a,c,b,d,e),f(xn)=42,f(xn)>f(xb),P=P–{xn}={(a,d,c,b,e),(a,e,c,d,b),(a,b,d,c,e),(a,b,e,d,c),(a,b,c,e,d)}第二次循环从P中选择一个元素，假设xn=(a,d,c,b,e),f(xn)=45,f(xn)>f(xb),P=P–{xn}={(a,e,c,d,b),(a,b,d,c,e),(a,b,e,d,c),(a,b,c,e,d)}第三次循环从P中选择一个元素，假设xn=(a,e,c,d,b),f(xn)=44,f(xn)>f(xb),P=P–{xn}={(a,b,d,c,e),(a,b,e,d,c),(a,b,c,e,d)}第四次循环从P中选择一个元素，假设xn=(a,b,d,c,e),f(xn)=44,f(xn)>f(xb),P=P–{xn}={(a,b,e,d,c),(a,b,c,e,d)}第五次循环从P中选择一个元素，假设xn=(a,b,e,d,c),f(xn)=34,f(xn)<f(xb),xb=(a,b,e,d,c),P={(a,e,b,d,c),(a,d,e,b,c),(a,c,e,d,b),(a,b,d,e,c),(a,b,c,d,e),(a,b,e,c,d)}第六次循环从P中选择一个元素，假设xn=(a,e,b,d,c),f(xn)=44,f(xn)>f(xb),P=P–{xn}={(a,d,e,b,c),(a,c,e,d,b),(a,b,d,e,c),(a,b,c,d,e),(a,b,e,c,d)}第七次循环从P中选择一个元素，假设xn=(a,d,e,b,c),f(xn)=39,f(xn)>f(xb),P=P–{xn}={(a,c,e,d,b),(a,b,d,e,c),(a,b,c,d,e),(a,b,e,c,d)}第八次循环从P中选择一个元素，假设xn=(a,c,e,d,b),f(xn)=38,f(xn)>f(xb),P=P–{xn}={(a,b,d,e,c),(a,b,c,d,e),(a,b,e,c,d)}第九次循环从P中选择一个元素，假设xn=(a,b,d,e,c),f(xn)=38,f(xn)>f(xb),P=P–{xn}={(a,b,c,d,e),(a,b,e,c,d)}第十次循环从P中选择一个元素，假设xn=(a,b,c,d,e),f(xn)=38,f(xn)>f(xb),P=P–{xn}={(a,b,e,c,d)}第十一次循环从P中选择一个元素，假设xn=(a,b,e,c,d),f(xn)=41,f(xn)>f(xb),P=P–{xn}={}P等于空，算法结束，得到结果为xb=(a,b,e,d,c),f(xb)=34。存在的问题局部最优问题

解决方法每次并不一定选择邻域内最优的点，而是依据一定的概率，从邻域内选择一个点，指标函数优的点，被选中的概率比较大，而指标函数差的点，被选中的概率比较小。选择概率的计算设求最大值时：选择概率的计算当求最小值时：局部搜索算法1（LocalSearch1）1，随机的选择一个初始的可能解x0∈D，xb=x0，P=N(xb)2，如果不满足结束条件，则3，Begin4，对于所有的x∈P计算指标函数f(x)，并按照式（3）或者式（4）计算每一个点x的概率5，依计算的概率值，从P中随机选择一个点xn，xb＝xn，P=N(xb)，转26，End7，输出计算结果8，结束存在的问题步长问题初始值搜索到的最优解解决方法变步长初始值搜索到的最优解局部搜索算法2（LocalSearch2）1，随机的选择一个初始的可能解x0∈D，xb=x0，确定一个初始步长计算P=N(xb)2，如果不满足结束条件，则3，Begin4， 选择P的一个子集P'，xn为P'中的最优解5， 如果f(xn)<f(xb)，则xb＝xn6， 按照某种策略改变步长，计算P=N(xb)，转27， 否则P=P–P'，转2。8，End9，输出计算结果10，结束存在问题起始点问题AB全局最大值局部最大值解决方法随机的生成一些初始点，从每个初始点出发进行搜索，找到各自的最优解。再从这些最优解中选择一个最好的结果作为最终的结果。局部搜索算法3（LocalSearch3）1，k=02，随机的选择一个初始的可能解x0∈D，xb=x0，P=N(xb)3，如果不满足结束条件，则4，Begin5， 选择P的一个子集P'，xn为P'中的最优解6， 如果f(xn)<f(xb)，则xb＝xn，P=N(xb)，转37， 否则P=P–P'，转3。8，End9，k=k+110，如果k达到了指定的次数，则从k个结果中选择一个最好的结果输出，否则转（2）11，输出结果12，结束多种方法的集成以上几种解决方法可以结合在一起使用，比如第一、第二种方法的结合，就产生了我们将在后面介绍的模拟退火方法。皇后搜索算法（QueenSearch）1，随机地将n个皇后分布在棋盘上，使得棋盘的每行、每列只有一个皇后。2，计算皇后间的冲突数conflicts。3，如果冲突数conflicts等于0，则转（6）4，对于棋盘上的任意两个皇后，交换他们的行或者列，如果交换后的冲突数conflicts减少，则接受这种交换，更新冲突数conflicts，转3。5，如果陷入了局部极小，既交换了所有的皇后后，冲突数仍然不能下降，则转1。6，输出结果7，结束。不同规模下皇后问题的

平均求解时间

皇后数1005001000200050001000030000平均时间（秒）55122817090010000说明：早期比较慢的机器的结果(PIII)模拟退火算法是局部搜索算法的一种扩展最早由Metropolis在1953年提出，Kirkpatrick等人在1983年成功地将模拟退火算法用于求解组合优化问题。基本思想是借用金属的退火过程改进局部搜索算法固体退火过程溶解过程：随着温度的不断上升，粒子逐渐脱离开其平衡位置，变得越来越自由，直到达到固体的溶解温度，粒子排列从原来的有序状态变为完全的无序状态。退火过程：随着温度的下降，粒子的热运动逐渐减弱，粒子逐渐停留在不同的状态，其排列也从无序向有序方向发展，直至到温度很低时，粒子重新以一定的结构排列。

粒子不同的排列结构，对应着不同的能量水平。如果退火过程是缓慢进行的，也就是说，温度的下降如果非常缓慢的话，使得在每个温度下，粒子的排列都达到一种平衡态，则当温度趋于0（绝对温度）时，系统的能量将趋于最小值。如果以粒子的排列或者相应的能量来表达固体所处的状态，在温度T下，固体所处的状态具有一定的随机性。一方面，物理系统倾向于能量较低的状态，另一方面，热运动又妨碍了系统准确落入低能状态。Metropolis准则

从状态i转换为状态j的准则：如果E(j)≤E(i)，则状态转换被接受；如果E(j)＞E(i)，则状态转移被接受的概率为：其中E(i)、E(j)分别表示在状态i、j下的能量，T是温度，K＞0是波尔兹曼常数。在给定的温度T下，当进行足够多次的状态转换后，系统将达到热平衡。此时系统处于某个状态i的概率由波尔兹曼（Boltzmann）分布给出：（6）其中为归一化因子，S是所有可能状态的集合。考察一下式（6）随温度T的变化情况：同一温度下，两个能量不同的状态高温下的情况低温下的情况当温度下降时的情况在给定的温度T下，设有i、j两个状态，E(i)＜E(j)：即在任何温度T下，系统处于能量低的状态的概率大于处于能量高的状态的概率。

由于E(i)＜E(j)，所以该项小于1

当温度趋于无穷时：其中|S|表示系统所有可能的状态数。

当温度很高时，系统处于各个状态的概率基本相等，接近于平均值，与所处状态的能量几乎无关。

当温度趋于0时：设Sm表示系统最小能量状态的集合，Em是系统的最小能量。上式分子、分母同乘以当温度趋近于0时，系统以等概率趋近于几个能量最小的状态之一，而系统处于其他状态的概率为0。以概率1达到能量最小的状态。当温度上升或下降时：系统落入低能量状态的概率随着温度的下降单调上升，而系统落入高能量状态的概率随着温度的下降单调下降。在高温下，系统基本处于无序的状态，基本以等概率落入各个状态。在给定的温度下，系统落入低能量状态的概率大于系统落入高能量状态的概率，这样在同一温度下，如果系统交换的足够充分，则系统会趋向于落入较低能量的状态。随着温度的缓慢下降，系统落入低能量状态的概率逐步增加，而落入高能量状态的概率逐步减少，使得系统各状态能量的期望值随温度的下降单调下降，而只有那些能量小于期望值的状态，其概率才随温度下降增加，其他状态均随温度下降而下降。因此，随着能量期望值的逐步下降，能量低于期望值的状态逐步减少，当温度趋于0时，只剩下那些具有最小能量的状态，系统处于其他状态的概率趋近于0。因此最终系统将以概率1处于具有最小能量的一个状态。达到最小能量状态的三个条件

（1）初始温度必须足够高；（2）在每个温度下，状态的交换必须足够充分；（3）温度T的下降必须足够缓慢。组合优化问题与退火过程的类比固体退火过程组合优化问题物理系统中的一个状态组合优化问题的解状态的能量解的指标函数能量最低状态最优解温度控制参数1，随机选择一个解i，k=0，t0=Tmax（初始温度），计算指标函数f(i)。2，如果满足结束条件，则转（15）。3，Begin4， 如果在该温度内达到了平衡条件，则转（13）。5， Begin6， 从i的邻域N(i)中随机选择一个解j。7， 计算指标函数f(j)。8， 如果f(j)<f(i)，则i=j，f(i)=f(j)，转（4）。9， 计算10， 如果Pt(i=>j)>Random(0,1)，则i=j，f(i)=f(j)。11， 转（4）12， End13， tk+1=Drop(tk)，k=k+1。14，End15，输出结果。16，结束。算法中的问题初始温度的选取内循环的结束条件，即每个温度状态交换何时结束外循环的结束条件，即温度下降到什么时候结束温度的下降方法在模拟退火过程中，给定温度下状态（解）的转移可以看作是一个马尔可夫链。对于任意两个状态i和j，我们用Pt(i,j)表示温度t下，从状态i转移到状态j的一步转移概率，则有：其中：Gt(i,j)是产生概率，表示从状态i产生状态j的概率。At(i,j)是接受概率，表示在状态i产生状态j后，接受状态j的概率。定理1满足条件的Gt(i,j)、At(i,j)举例：

说明：条件2的后半部分除外，该条件与具体的问题有关。定理2：在定理1的条件下，如果对于任意两个状态

有：则有：定理3（放宽了定理1的条件）

Gt(i,j)、At(i,j)满足定理1中除条件（2）以外的所有其他条件，并且：1，对于任意两个状态i、j，它们相互为邻居或者相互都不为邻居；2，对于任意i，Gt(i,j)满足：3，状态空间S对于邻域是连通的；则与模拟退火算法相伴的时齐马尔可夫链存在平稳分布，其分布概率为：

算法的实现（1）初始温度t0；（2）温度t的衰减函数，即温度的下降 方法；（3）算法的终止准则，用终止温度tf或 者终止条件给出；（4）每个温度t下的马尔可夫链长度Lk。起始温度的选取（1）一个合适的初始温度，应保证平稳分布中每一个状态的概率基本相等，也就是接受概率P0近似等于1。在Metropolis准则下，即要求：如果我们给定一个比较大的接受概率P0，则：其中，可以有以下估计方式：起始温度的选取（2）假设在t0下随机的生成一个状态序列，分别用m1和m2表示指标函数下降的状态数和指标函数上升的状态数，表示状态增加的平均值。则m2个状态中，被接受的个数为：所以平均接受率为：求解有：起始温度的选取（3）模拟固体的升温过程：（1）给定一个希望的初始接受概率P0，给定一个较低的初始温度t0，比如t0＝1；（2）随机的产生一个状态序列，并计算该序列的接收率：如果接收率大于给定的初始接受概率P0，则转（4）；（3）提高温度，更新t0，转（2）；（4）结束。温度的下降方法（1）等比例下降温度的下降方法（2）等值下降温度的下降方法（3）由定理1我们知道，在一定的条件下，与模拟退火算法相伴的时齐马尔可夫链存在平稳分布。如果温度每次下降的幅度比较小的话，则相邻温度下的平稳分布应该变化不大，也就是说，对于任意一个状态i，相邻温度下的平稳分布应满足：一个充分条件是：两边取对数，并整理得：用代替可得温度的衰减函数：每一温度下的停止准则（1）

固定长度方法在每一个温度下，都使用相同的Lk。Lk的选取与具体的问题相关，一般与邻域的大小直接关联，通常选择为问题规模n的一个多项式函数。每一温度下的停止准则（2）基于接受率的停止准则：规定一个接受次数R，在某一温度下，只有被接受的状态数达到R时，在该温度下的迭代才停止，转入下一个温度。规定一个状态接受率R，R等于该温度下接受的状态数除以总生成的总状态数。如果接受率达到了R，则停止该温度下的迭代，转入下一个温度。在迭代的过程中，若干相邻的状态称为“一代”，如果相邻两代的解的指标函数差值小于规定的值的话，则停止该温度下的迭代。算法的终止原则（1）零度法设定一个正常数e，当时tk<e时，算法结束。算法的终止原则（2）循环总控制法

给定一个指定的温度下降次数K，当温度的迭代次数达到K次时，则算法停止。算法的终止原则（3）无变化控制法如果在相邻的n个温度中，得到的解的指标函数值无任何变化，则说明算法已经收敛。算法的终止原则（4）接受概率控制法给定一个小的概率值p，如果在当前温度下除了局部最优状态外，其他状态的接受概率小于p值，则算法结束。算法的终止原则（5）领域平均概率控制法设大小为N的一个邻域，在邻域内一个状态被接受的平均概率为1/N。设f0、f1为该领域中的局部最优值和局部次最优值。则次最优解是除了局部最优解以外接受概率最大的，其接受概率为：如果该概率值小于平均值1/N时，即：可以认为从局部最优解跳出的可能性已经很小了，因此可以终止算法。此时的终止温度tf为：算法的终止原则（6）相对误差估计法设温度t时指标函数的期望值为：则当终止温度<<1时，由泰勒展开近似有：由于：所以可用下式估计当前解与最优解之间的误差：或者使用相对于的相对误差：说明：推导请见补充教材实际计算时：其中：应用举例——旅行商问题

解的表示：n个城市的任何一种排列均是问题的一个可能解，表示为:指标函数(能量函数)其中新解的产生采用第一节介绍的两个城市间的逆序交换方式得到问题的一个新解。设当前解是，被选中要逆序交换的城市是第u和第v个到访的城市，u<v。则逆序排列u和v之间的城市，得到问题的新解为：则两个路径的距离差为：新解的接受准则初始参数的确定康立山等人的方法：初始温度t0=280；在每个温度下采用固定的迭代次数，Lk=100n，n为城市数；温度的衰减系数＝0.92，即tk+1=0.92×tk；算法的停止准则为：当相邻两个温度得到的解无任何变化时算法停止。NirwanAnsari和EdwinHou的方法：初始温度t0是这样确定的：从t0=1出发，并以t0=1.05×t0对t0进行更新，直到接受概率大于等于0.9时为止，此时得到的温度为初始温度；在每个温度下采用固定的迭代次数，Lk=10n，n为城市数；温度的衰减系数＝0.95，即tk+1=0.95×tk；10城市旅行商问题求解结果

路径长度出现次数平均转移次数路径最优2.6919063952BCADEFGHIJ次优2.752464056BCADEGFHIJ第三2.769104053DEFGHIJCBA最差2.89854497ABCDEFHIJG20城市旅行商问题求解结果

路径长度出现次数平均转移次数路径最优24.527928740ACLBIQFTMEPRGSOJHDKN次优24.621678638ADCLBIQFTMEPRGSOJHKN第三25.17399902ANKDHIOJSGRPEMTFQBLC最差25.5015794AQFTMEPRGSJOIBLCDHKN人工智能

是一门交叉学科

脑科学认知科学心理学语言学逻辑学哲学计算机科学人工智能什么是人工智能人工智能的定义可以分为两部分，即“人工”和“智能”。关于什么是“智能”？智能需要具备的特征？具有感知能力（系统输入）:

机器视觉，机器听觉，图像语音识别……具有记忆与思维能力：思维是智能的根本原因，思维是一个动态的过程。思维分为：逻辑思维，形象思维和顿悟思维。具有学习能力及自适应能力：适应环境的变换、积累经验的能力

具有行为能力（系统输出）：对外界的智能化反应早期判断是否有智能的方法———图灵测试英国数学家阿兰·图灵(AlanTuring)提出了现称为“图灵测试”(TuringTest)的方法。简单来讲,图灵测试的做法是:让一位测试者分别与一台计算机和一个人进行交谈(当时是用电传打字机),而测试者事先并不知道哪一个是人,哪一个是计算机。如果交谈后测试者分不出哪一个被测者是人,

哪一个是计算机,则可以认为这台被测的计算机具有智能。

Turing测试存在的问题“图灵测试”没有规定问题的范围和提问的标准仅反映了结果的比较，无涉及思维过程没指出是什么人争论：通过了图灵检验的电脑就具备思维能力了么？测试主持人被测机器被测人中文屋子约翰·西尔勒的中文屋子假设是说:有一台计算机阅读了一段故事并且能正确回答相关问题,这样这台计算就通过了图灵测试。而西尔勒设想将这段故事和问题改用中文描述(因为他本人不懂中文),然后将自己封闭在一个屋子里,代替计算机阅读这段故事并且回答相关问题。描述这段故事和问题的一连串中文符号只能通过一个很小的缝隙被送到屋子里。西尔勒则完全按照原先计算机程序的处理方式和过程(如符号匹配、查找、照抄等)对这些符号串进行操作,然后把得到的结果即问题答案通过小缝隙送出去。西尔勒也得到了问题的正确答案。西尔勒认为尽管计算机用这种符号处理方式也能正确回答问题,并且也可通过图灵测试,但仍然不能说计算机就有了智能。

人工智能的发展概况

1.形成期（1956--1970年）AI诞生于一次历史性的聚会(Dartmouth人工智能夏季研讨会)时间：1956年夏季地点：美国达特茅斯(Dartmouth)大学目的：为使计算机变得更“聪明”，或者说使计算机具有智能发起人：麦卡锡(J.McCarthy），Dartmouth的年轻数学家、计算机专家，后为MIT教授明斯基(M.L.Minsky），哈佛大学数学家、神经学家，后为MIT教授洛切斯特(N.Lochester)，IBM公司信息中心负责人香农(C.E.Shannon)，贝尔实验室信息部数学研究员会议结果：由麦卡锡提议正式采用了“ArtificialIntelligence”这一术语人工智能的发展概况2.形成期（1956----1970年）其他开创性贡献1958年，美籍华人数理逻辑学家王浩在IBM-740计算机上仅用了3-5分钟就证明了《数学原理》命题演算全部220条定理。1965年，费根鲍姆(E.A.Feigenbaum)开始研究化学专家系统DENDRAL，用于质谱仪分析有机化合物的分子结构。1969年召开了第一届国际人工智能联合会议（InternationalJointConferenceonAI，IJCAI），标志着人工智能作为一门独立学科登上了国际学术舞台。此后IJCAI每两年召开一次。1970年《InternationalJournalofAI》创刊。人工智能的发展概况3.暗淡期（1966----1974年）失败的预言给人工智能的声誉造成重大伤害“20年内，机器将能做人所能做的一切”---------1965在博弈方面：塞缪尔的下棋程序在与世界冠军对弈时，5局败了4局。在定理证明方面：发现鲁宾逊归结法的能力有限。当用归结原理证明两个连续函数之和还是连续函数时，推了10万步也没证出结果。在机器翻译方面：发现并不那么简单，甚至会闹出笑话。例如，把“心有余而力不足”的英语句子翻译成俄语，再翻译回来时竟变成了“酒是好的，肉变质了”在问题求解方面：对于不良结构，会产生组合爆炸问题。在神经生理学方面：研究发现人脑有1011-12以上的神经元，在现有技术条件下用机器从结构上模拟人脑是根本不可能的。在英国，剑桥大学的詹姆教授指责“人工智能研究不是骗局，也是庸人自扰”。从此，形势急转直下，在全世界范围内人工智能研究陷入困境、落入低谷。

人工智能的发展概况

4.知识应用期（1970----1988年）整个20世纪80年代，专家系统和知识工程在全世界得到了迅速发展。专家系统为企业等用户赢得了巨大的经济效益。在开发专家系统过程中，许多研究者获得共识，即人工智能系统是一个知识处理系统，而知识获取、知识表示和知识利用则成为人工智能系统的三大基本问题。同时出现新的问题：专家系统本身所存在的应用领域狭窄、缺乏常识性知识、知识获取困难、推理方法单一、没有分布式功能、不能访问现存数据库等问题被逐渐暴露出来。人工智能的发展概况

5.集成发展期（1986年以来）1997年5月11日，由IBM研制的超级计算机“深蓝”首次击败了国际象棋特级大师卡斯帕洛夫。2000年，中国科学院计算所开发出知识发现系统MSMiner。该系统是一种多策略知识发现平台，能够提供快捷有效的数据挖掘解决方案，提供多种知识发现方法。2011年，IBM超级电脑“沃森”亮相美国最受欢迎的智力竞赛节目《危险边缘》战胜该节目两位最成功的选手。人工智能研究形成了三大学派符号主义连接主义行为主义符号主义又称：逻辑主义、心理学派或计算机学派符号主义的实现基础是纽威尔和西蒙提出的物理符号系统假设。该学派认为：人类认知和思维的基本单元是符号，而认知过程就是在符号表示上的一种运算。它认为人是一个物理符号系统,计算机也是一个物理符号系