第4章人工智能的决策支持和智能决策支持系统第4章目录4.1人工智能基本原理4.2专家系统与智能决策支持系统4.3神经网络的决策支持4.4遗传算法的决策支持4.5机器学习的决策支持4.1人工智能基本原理1、人工智能的决策支持技术从智能决策支持系统的概念可知智能决策支持系统中包含了人工智能技术,与决策支持有关的人工智能技术主要有:专家系统、神经网络、遗传算法、机器学习、自然语言理解等。专家系统是利用大量的专门知识解决特定领域中的实际问题的计算机程序系统;神经网络是利用神经元的信息传播模型(MP模型)进行学习和应用;遗传算法是模拟生物遗传过程的群体优化搜索方法;机器学习是让计算机模拟和实现人类的学习,获取解决问题的知识;自然语言理解是让计算机理解和处理人类进行交流的自然语言。4.1人工智能基本原理2.智能决策支持系统结构形式1)基本结构智能决策支持系统(IDSS)=决策支持系统(DSS)+人工智能(AI)技术4.1人工智能基本原理问题综合与交互系统数据库管理系统模型库管理系统模型库数据库人工智能技术专家系统神经网络遗传算法机器学习自然语言理解图4.1智能决策支持系统的基本结构图4.2智能决策支持系统结构问题综合与交互系统模型库管理系统数据库管理系统知识库管理系统推理机用户模型库知识库数据库人工智能技术可以概括为:推理机+知识库智能决策支持系统的结构可以简化为图4.24.2人工智能基本原理4.2.1逻辑推理4.2.2知识表示与知识推理4.2.3搜索技术4.2.1逻辑推理1.形式逻辑(人的思维形式、规律)(1)概念:反映事物的特有属性和属性的取值。(2)判断:对概念的肯定或否定;判断本身有对有错;判断有全称的肯定(或否定)判断和存在的肯定(或否定)判断。(3)推理:从一个或多个判断推出一个新判断的过程。4.2.1逻辑推理2.推理的种类演绎推理归纳推理类比推理假言推理三段论推理数学归纳法假言易位推理枚举归纳推理1)演绎推理:从一般现象到个别(特殊)现象的推理。2)归纳推理:从个别(特殊)现象到一般现象的推理。3)类比推理:从个别(特殊)现象到个别(特殊)现象的推理。1)演绎推理专家系统的研究基本上属于演绎推理范畴。演绎推理的核心是假言推理。假言推理:以假言判断为前提,对该假言判断的前件或后件的推理。1)假言推理:pq,p┝q2)三段论推理:pq,qr┝pr3)假言易位推理(拒取式):pq,q┝p符号“┝”表示推出4.2.1逻辑推理2)归纳推理(个别→一般)(1)数学归纳法这种推导是严格的,结论是确实可靠的。(2)枚举归纳推理S1是P,S2是P,……Sn是PS1……Sn是S类事物中的部分分子,没有相反事例。所以,S类事物都是P。枚举归纳推理的结论是或然的(并非必然地),它的可靠性和事例数量相关。4.2.1逻辑推理枚举归纳推理实例如观察到铁受热膨胀、铜受热膨胀等事实而不知其所以然,由此推出“所有金属受热膨胀”的结论就是简单枚举归纳推理。3)类比推理它是由两个(或两类)事物在某些属性上相同,进而推断它们在另一个属性上也可能相同的推理。A事物有abcd属性,B事物有abc属性(或a,b,c相似属性)所以,B事物也可能有d属性(或d相似属性)类比推理的结论带有或然性,它的可靠性和相类比事物属性之间的联系程度有关。4.2.1逻辑推理类比推理实例一1816年的一天,法国医生雷奈克出诊为一位年轻的女性看病,一见病人,雷奈克犯起愁来:她身体非常肥胖,要诊断她的心脏和肺部是否正常,按当时医生惯用的方法,把耳朵贴近病人的胸部来听,肯定听不清楚,更何况她是一位年轻的女性。雷奈克抬头看了看院子里正在玩耍的小孩,脑子里突然浮现出几年前看到一个孩子们玩的游戏:一个孩子用钉子敲打木板的一头,另外的孩子争先恐后地抱着把耳朵贴近木板的另一头,兴致勃勃地倾听着。为什么木头能够把声音清晰地传过来呢?雷奈克稍微想了想,只见他很很地拍了一下手说:“就是这样!就是这样!”雷奈克要来一叠纸,紧紧地卷成一个卷,然后把纸卷的一端放在姑娘的胸部,另一端放在自己的耳朵上,侧着脸听了起来。“真是一个妙法!”雷奈克高兴地喊了一句。回到家里,雷奈克找到一根木棒,造成了历史上第一个“听诊器”。类比推理实例一类比推理实例二19世纪30年代,英国商人威尔斯以与冯灿的茂隆皮箱商行订购的皮箱中有不是皮的木料为由,向香港法院起诉,蓄意敲诈冯灿。针对这种情况,冯灿的律师罗文锦取出口袋的金怀表,高声问法官:“请问这是什么表?”法官答道:“这是金表,可是这与本案有什么关系?”罗文锦高举金表,面对法庭上所有的人说:“有关系。这是金表,没有人怀疑是吧?但是,请问,这块金表除表面镀金之外,内部的机制都是金制吗?”旁听者同声议论:“当然不是。”罗文锦继续说:“那么人们为什么又叫它金表呢?”稍作停顿又高声说:“由此可见,茂隆行的皮箱案不过是原告无理取闹、存心敲诈而已”原告理屈词穷,法庭最后以威尔斯诬告,罚款5000元结案皮箱诉讼案的法庭辩论中,卖方律师在反驳中所使用的就是类比推理:表的外表有金,内部含有不是金的材料,但却是金表;箱的外表有皮,但也含有不是皮的材料;所以,箱仍是皮箱。类比推理实例二3.总结1)演绎推理的结论没有超出已知的知识范围。而归纳推理和类比推理的结论超出已知的知识范围。演绎推理只能解释一般规律中的个别现象而归纳推理和类比推理创造了新的知识,使科学得到新发展,是一种创造思维方式。2)演绎推理中由于前提和结论有必然联系,只要前提为真,结论一定为真。归纳推理和类比推理中前提和结论,不能保证有必然联系,具有或然性。这样推理的结论未必是可靠的。需要经过严格的验证和证明,使之形成新的理论。4.2.1逻辑推理4.2.2知识表示与知识推理4.2.2.1数理逻辑表示法(自学)4.2.2.1产生式规则4.2.2.3语义网络4.2.2.4框架4.2.2.5剧本(自学)4.2.2.2产生式规则(ifAthenB)1.正向推理逐条搜索规则库,对每一条规则的前提条件,检查事实库中是否存在。前提条件中各子项,若在事实库中不是全部存在,放弃该条规则。若在事实库中全部存在,则执行该条规则,把结论放入事实库中。反复循环执行上面过程,直至推出目标,并存入事实库中为止。1.A∧B→G2.C∧D→A3.E→DB,C,E4.2.2.2产生式规则事实库的最后状态为:B,C,E,D,A,G产生式规则库事实库产生式规则库和事实库的初始状态为:4.2.2.2产生式规则逆(反)向推理逆向推理是从目标开始,寻找以此目标为结论的规则对该规则的前提进行判断,若该规则的前提中某个子项是另一规则的结论时,再找以此结论的规则。重复以上过程,直到对某个规则的前提能够进行判断。按此规则前提判断(“是”或“否”)得出结论的判断,由此回溯到上一个规则的推理,一直回溯到目标的判断。GADEBC4.2.2.2产生式规则逆向推理中,目标改变过程:1.A∧B→G2.C∧D→A3.E→DB,C,E产生式规则库事实库4.2.3搜索技术搜索技术是人工智能的一个重要研究内容。智能技术体现在减少搜索树中的盲目搜索。1.执行时间与n,n2,n3等成正比的算法,称为按多项式时间执行。2.执行时间与2n,n!和nn等成正比的算法,称为按指数时间执行。按多项式时间执行的算法,计算机是可以实现的。按指数时间执行的算法,计算机是不可能实现的。4.2.3搜索技术人工智能中发展了一种称为启发式搜索方法,基本思想可用一个实例来说明:一个外地人到某城市出差,他想到书店看看,又不知书店在何处,如果采取盲目搜索,从住地出发沿任一方向走,在分叉路口又任选一分支走,他可能走几天几夜也找不到如果采用启发式方法,他会问路上的人,到书店怎样走。城市中的大部分人对书店不知道,问不出来。4.2.3搜索技术改一种问法:问该城市最热闹的地方在哪儿?按照这个启发式信息沿着指路人的路线,乘车到达最热闹的地方但书店在哪儿,仍然不知道。如果盲目搜索,可能仍然找不到。如果采用启发式方法,他会问路上的人,卖画的地方在哪儿,他可以通过画店再问书店在哪儿?启发式方法能减少大量盲目无效的搜索,能有效克服按指数时间执行的组合爆炸现象4.2.3搜索技术搜索方法分类:1、基本搜索法(1)广度优先搜索法。(2)深度优先搜索法。2、生成测试法。3、爬山法。4、启发式搜索。5、博弈算法。(1)极小极大搜索法。(2)剪枝算法。4.2.3.1广度优先搜索(宽度优先搜索)1、广度优先搜索思想从初始状态S开始,利用规则,生成所有可能的状态。构成树的下一层节点,检查是否出现目标状态G,若未出现,就对该层所有状态节点,分别顺序利用规则。生成再下一层的所有状态节点,对这一层的所有状态节点检查是否出现G,若未出现,继续按上面思想生成再下一层的所有状态节点.这样一层一层往下展开。直到出现目标状态G为止。图4.7广度优先搜索示意图(2)算法1)把初始节点S0故入OPEN表。2)如果OPEN表为空,则问题无解,退出。3)把OPEN表的第一个节点(记为节点n)取出放入CLOSED表。4)考察节点n是否为目标节点。若是,则求得了问题的解,退出。5)若节点n不可扩展,则转第2)步。6)扩展节点n,将其子节点放入OPEN表的尾部,并为每一个子节点都配置指向父节点的指针,然后转第2)步。广度优先搜索过程开始把n的后继节点放入OPEN表的末端,提供返回节点n的指针把S放入OPEN表OPEN表为空表?是失败否把第一个节点(n)从OPEN移至CLOSED表n为目标节点?是成功否n能否扩展是否有任何后继节点为目标节点否是是否例子1(八数码难题)重排九宫问题,在3x3的方格棋盘上放置分别标有数字1、2、3、4、5、6、7、8共8个棋子,初始状态为S0,目标状态为Sg,如图1所示。可使用的算符有:空格左移,空格上移,空格右移,空格下移。即只允许把位于空格左、上、右、下的邻近棋子移入空格。要求寻找从初始状态到目标状态的路径。该路径使用的算符序列:空格上移,空格左移,空格下移,空格右移。广度优先搜索的盲目性较大,当目标节点距离初始节点较远时将会产生许多无用节点,因此搜索效率低,但是,只要问题有解,用广度优先搜索总可以得到解,而且得到的是路径最短的路径。由图2可以看出,解的路径是:S0——3——8——16——26广度优先法适合于搜索树的宽度较小的问题。1、深度优先搜索法思想从初始状态S开始,利用规则生成搜索树下一层任一个结点,检查是否出现目标状态G,若未出现,以此状态利用规则生成再下一层任一个结点,再检查是否为目标节点G。若未出现,继续以上操作过程,一直进行到叶节点(即不能再生成新状态节点)。当它仍不是目标状态G时,回溯到上一层结果,取另一可能扩展搜索的分支。生成新状态节点。一直进行下去,直到找到目标状态G为止。4.2.3.2深度优先搜索法图4.8深度优先搜索示意图(2)算法1)把初始节点S0故入OPEN表。2)如果OPEN表为空,则问题无解,退出。3)把OPEN表的第一个节点(记为节点n)取出放入CLOSED表。4)考察节点n是否为目标节点。若是,则求得了问题的解,退出。5)若节点n不可扩展,则转第2)步。6)扩展节点n,将其全部子节点放入到OPEN表的首部,并为其配置指向父节点的指针,然后转第2)步。开始把S放入OPEN表OPEN表为空表?是失败否把第一个节点(n)从OPEN移至CLOSED表是否有任何后继节点为目标节点是成功否扩展n,把n的后继节点放入OPEN表的前头,提供返回节点n的指针s为目标节点?否是深度优先搜索例子2:对图1所示的重排九宫问题进行深度优先搜索,可得到图3所示的搜索树这只是搜索树的一部分,尚未到达目标节点,仍需继续往下搜索。在深度优先搜索中,搜索一旦进入某个分支,就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上,则可较快地得到解。但是,如果目标节点不在此分支上,而该分支又是一个无穷分支,则就不能得到解。所以深度优先搜索是不完备的