第四章 人工智能的决策支持和(1)

第4章人工智能的决策支持和智能决策支持系统（1）第4章目录4.1人工智能基本原理4.2专家系统的决策支持4.3神经网络的决策支持4.4遗传算法的决策支持4.5机器学习的决策支持4.6智能决策支持系统（1）部分内容4.1人工智能基本原理4.1人工智能基本原理4.1.1逻辑推理4.1.2知识推理4.1.3搜索技术1.形式逻辑形式逻辑是研究人的思维形式及其规律的科学。它是属“符号处理”范畴。形式逻辑主要研究：形成概念、作出判断、进行推理。1）概念：概念是反映事物的特有属性和它的取值。2）判断：判断是对概念的肯定或否定。3）推理：推理是从一个或几个判断推出一个新判断的思维过程。4.2.1逻辑推理2.推理的种类1）演绎推理：从一般现象到个别（特殊）现象的推理。2）归纳推理：从个别（特殊）现象到一般现象的推理。3）类比推理：从个别（特殊）现象到个别（特殊）现象的推理。1）演绎推理专家系统的研究基本上属于演绎推理范畴。演绎推理的核心是假言推理。假言推理：以假言判断为前提，对该假言判断的前件或后件的推理。以下是等价的推理式：1）假言推理：pq，p┝q2）三段论推理：pq，qr┝pr3）假言易位推理（拒取式）：pq，q┝p2）归纳推理（1）数学归纳法这种推导是严格的，结论是确实可靠的。（2）枚举归纳推理S1是P，S2是P，……Sn是PS1……Sn是S类事物中的部分分子，没有相反事例。所以，S类事物都是P。枚举归纳推理的结论是或然的。3）类比推理它是由两个（或两类）事物在某些属性上相同，进而推断它们在另一个属性上也可能相同的推理。A事物有abcd属性B事物有abc属性（或a,b,c相似属性）所以，B事物也可能有d属性（或d相似属性）类比推理的结论带有或然性。3.总结1）演绎推理的结论没有超出已知的知识范围。而归纳推理和类比推理的结论超出已知的知识范围。演绎推理只能解释一般规律中的个别现象。而归纳推理和类比推理创造了新的知识，使科学得到新发展，是一种创造思维方式。2）演绎推理中由于前提和结论有必然联系，只要前提为真，结论一定为真。归纳推理和类比推理中前提和结论，不能保证有必然联系，具有或然性。这样推理的结论未必是可靠的。需要经过严格的验证和证明，使之形成新的理论。4.1.2知识推理4.1.2.1数理逻辑的知识推理4.1.2.2产生式规则的推理1.命题逻辑的公式有：1、析取交换律：p∨qq∨p2、合取交换律：p∧qq∧p3、析取结合律:（p∨q）∨rp∨（q∨r）4、合取结合律:（p∧q）∧rp∧（q∧r）5、∨对∧的分配律：p∨(q∧r）(p∨q)∧(p∨r)6、∧对∨的分配律：p∧（q∨r）(p∧q)∨(p∧r)7、双重否定：p~~p8、德摩根律1：~(p∨q)~p∧~q9、德摩根律2：~(p∧q)~p∨~q10、蕴含转换1:(pq)~p∨q11、蕴含转换2:(pq)(~q~p)12、等价转换1:(pq)(pq)∧(qp)13、等价转换2:(pq)(~p~q)14、∧转∨：(p∧q)~(~p∨~q)定义：公式的标准形式称为范式。有两种基本范式：合取范式、析取范式。1)、合取范式:它是一些简单析取式的合取式，即该合取式中，其子命题都是简单析取式。如：（A）(～p∨q)∧(p∨～q)（B）(p∨q∨r)∧(p∨～q∨r)∧(p∨～q∨～z)2)、析取范式：它是一些简单合取式的析取式。即该析取式中，其子命题都是简单合取式。一般形式：a1∨a2∨…∨ax其中每个ai是简单合取。如：（A）:(p∧q)∨(p∧r)（B）:（p∧～p∧q）∨（p∧q∧r∧～r）2.命题逻辑归结原理1：把公式转换成子句型归结原理使用反证法来证明语句。即归结是从结论的非，导出已知语句的矛盾。利用命题逻辑公式和谓词逻辑公式，把逻辑表达式化成合取范式、前束范式，再化成子句。一子句定义为由文字的析取组成的公式。转换过程如下：1）消去蕴含符号“→”用～A∨B替换A→B2）用德摩根律缩小~的辖域，让~进入括号内用~A∨~B代替~(A∧B)用~A∧~B代替~(A∨B)用代替用代替}){~(AXAX)(~))(~(AXAX)(~3）把公式化成合取范式我们可以反复应用分配律，把任一公式化成合取范式。例如：)())(CABACBA（4）消去联结词符号∧在合取范式中，每一个合取元，取出成为一个独立句子。用子句集来代替原来子句的合取（∧）。每个子句实际上是文字的析取。例如：}{)DCBADCBA，（）（4.命题逻辑归结原理2：归结过程归结过程：对两个称为母子句的子句进行归结。以产生一个新子句。归结时，对一个子句中以“正文字”形式出现，一个以“负文字”形式出现，归结后就删除这两个“正负文字”，合并剩下的文字。若最后产生空子句，则存在矛盾。没有产生空子句就一直进行下去。例1、例2、假言推理)(~)(QPPQPP}{}~{QQPP归结，子句集空子句（矛盾）)~(pp4、命题逻辑中的归结对公理集F、命题S的归结：1）把F的所有命题转换成子句型。2）把否定S的结果转换成子句型。3）重复下述归结过程，直到找出一个矛盾或不能再结：（A）挑选两个子句，称之为母子句。其中一个母子句含L，另一个母子句含~L。（B）对这两个母子句作归结，结果子句称为归结式。从归结式中删除L和~L，得到所有文字的析取式（C）若归结式为空子句，则矛盾已找到，否则原归结式加入到该过程中的现有子句集。举例：从公理集：证明结果。1）把公理集转换成子句型①②这个合取式分为两个子句：这样子句集为：2）证明命题的非为tqtsrqpp,)(,)(,rqprqprqp~~~)(）（qtsqtsqts)~(~)(~)()(~)(~qtqsqtqs~~，tqtqsrqpp,~,~,~~,r~r3）归结过程最后得到空语句，是矛盾的，故可得出结论：从公理集中可以推出。rqp~~r~qp~~qt~q~pt~tr1.正向推理逐条搜索规则库，对每一条规则的前提条件，检查事实库中是否存在。前提条件中各子项，若在事实库中不是全部存在，放弃该条规则。若在事实库中全部存在，则执行该条规则，把结论放入事实库中。反复循环执行上面过程，直至推出目标，并存入事实库中为止。4.1.2.2产生式规则的推理产生式规则库和事实库的初始状态为：产生式规则库事实库1.A∧B→G2.C∧D→A3.E→DB,C,E事实库的最后状态为：B，C，E，D，A，G逆向推理是从目标开始，寻找以此目标为结论的规则，并对该规则的前提进行判断，若该规则的前提中某个子项是另一规则的结论时，再找以此结论的规则。重复以上过程，直到对某个规则的前提能够进行判断。按此规则前提判断（“是”或“否”）得出结论的判断，由此回溯到上一个规则的推理，一直回溯到目标的判断。2.逆(反)向推理逆向推理中，目标改变过程：GADEBC4.1.3搜索技术搜索技术是人工智能的一个重要研究内容。智能技术体现在减少搜索树中的盲目搜索。1.执行时间与ｎ，ｎ２，ｎ３等成正比的算法，称为按多项式时间执行。2.执行时间与２ｎ，ｎ！和ｎｎ等成正比的算法，称为按指数时间执行。按多项式时间执行的算法，计算机是可以实现的。按指数时间执行的算法，计算机是不可能实现的。搜索方法分类1、基本搜索法对搜索树的基本搜索法有两种思想，一是按广度优先展开搜索树的搜索方法，叫广度优先搜索法；一是按深度优先展开搜索树的搜索方法，叫深度优先搜索法。（1）广度优先搜索法。（2）深度优先搜索法。2、生成测试法。3、爬山法。4、启发式搜索。5、博弈算法。（1）极小极大搜索法。（2）剪枝算法。4.1.3.1广度优先搜索（宽度优先搜索）1、广度优先搜索思想从初始状态S开始，利用规则，生成所有可能的状态。构成树的下一层节点，检查是否出现目标状态G，若未出现，就对该层所有状态节点，分别顺序利用规则。生成再下一层的所有状态节点，对这一层的所有状态节点检查是否出现G，若未出现，继续按上面思想生成再下一层的所有状态节点.这样一层一层往下展开。直到出现目标状态为止。搜索过程图4.4广度优先搜索示意图2、广度优先搜索算法：（1）把起始节点S线放到OPEN表中。（2）如果OPEN是空表，则失败推出，否则继续。（3）在OPEN表中取最前面的节点node移到CLOSED表中。（4）扩展node节点。若没有后继（即叶节点），则转向（2）循环。（5）把node的所有后继节点放在OPEN表的后面。各后继结点指针指向node节点。（6）若后继节点中某一个是目标节点，则找到一个解，成功退出。否则转向（2）循环。广度优先法适合于搜索树的宽度较小的问题。4.1.3.2深度优先搜索法1、深度优先搜索法思想从初始状态S开始，利用规则生成搜索树下一层任一个结点，检查是否出现目标状态G，若未出现，以此状态利用规则生成再下一层任一个结点，再检查是否为目标节点G。若未出现，继续以上操作过程，一直进行到叶节点（即不能再生成新状态节点）。当它仍不是目标状态G时，回溯到上一层结果，取另一可能扩展搜索的分支。生成新状态节点。一直进行下去，直到找到目标状态G为止。搜索过程图4.5深度优先搜索示意图2、深度优先算法（1）把起始节点S线放到OPEN表中。（2）如果OPEN是空表，则失败推出，否则继续。（3）从OPEN表中取最前面的节点node移到CLOSED表中。（4）若node节点是叶结点（若没有后继节点），则转向（2）。（5）扩展node的后继节点，产生全部后继节点，并把他们放在OPEN表的前面。各后继结点指针指向node节点。（6）若后继节点中某一个是目标节点，则找到一个解，成功退出。否则转向（2）循环。深度优先法适合于搜索树的深度较小的问题。人工智能问题求解中，用深度优先搜索法比较多。Prolog语言提供的搜索机制是以深度优先法设计的。它比广度优先搜索法要好些。4.1.3.3生成测试法生成测试法算法是：1、生成一个可能状态节点。2、测试该状态是否为目标状态。3、若是目标状态则结束。否则回到第1步其中：生成可能的状态，可以是有规律的，也可以是无规律的（1）如果搜索过程中，总是利用刚生成出的状态来生成新状态，这种生成测试法就是深度优先搜索法。（2）如果搜索过程中，总是利用旧状态生成所有可能出新状态，而且状态节点以从旧到新的顺序逐个生成的原则。这种生成测试法就是广度优先搜索法。如果搜索过程中，有时利用旧状态生成新状态，有时利用新状态生成新状态，这就是无规律的生成测试法。4.1.3.4爬山法爬山算法：1.开始状态作为一个可能状态。2.从一个可能状态，应用规则生成所有新的可能状态集。3.对该状态集中每一状态，进行：⑴对该状态测试，检查是否为目标，是则停止。⑵计算该状态的好坏，或者比较各状态的好坏。4.取状态集中最好状态，作为下一个可能状态。5.循环到第2步。在爬山法中可能出现以下几种情况⑴局部极大点：它比周围邻居状态都好，但不是目标。图4.6局部极大点示意图⑵平顶：它与全部邻居状态都有同一个值，构成一个平面。图4.7平顶示意图⑶山脊：它与线状邻居状态有相同值，比其它邻居状态要好。图4.8山脊示意图爬山法进入以上状态就得不到目标解了。为了解决以上问题，需要采用如下策略：（1）退回到某一更早状态结点，沿着另一方向（对该结点就不一定是当时最好值的方向）进行爬山。（2）朝一个方向前进一大步（按某方向深度优先搜索多次），走出平顶区，按别方向进行爬山。（3）同时朝两个或多个方向前进，即按两个或多个方向爬山。4.1.3.5启发式搜索启发式搜索是对每个在搜索过程中遇到的新状态，用一个估计函数（启发式函数）并计算其值的大小，确定下一步将从哪一个状态开始继续前进。一般以估计值小者为较优的状态，以此实行最优搜索。估计函数值的大小与从初始状态到达目标状态的路径有关，具体需要考虑以下问题：（1）下一步选择哪个状态结点？（2）是部分展开几个状态结点还是全部展开所有可能产生的状态结点？（3）使用哪个规则（或算子）来展开新状态结点？（4