智能决策支持系统和智能技术的决策支持.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,人工智能的决策支持和 智能决策支持系统,第,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.1 逻辑推理1.形式逻辑(人的思维形式、规律),（1）概念：,反映事物的特有属性和属性的取值。,（2）判断：,对概念的肯定或否定；,判断本身有对有错；,判断有全称的肯定（或否定）判断和存在的肯定（或否定）判断。,（3）推理：,从一个或多个判断推出一个新判断的过程。,4.2.1 逻辑推理,2.推理的种类,演绎推理,归纳推理,类比推理,假言推理,三段论推理,数学归纳法,假言易位推理,枚举归纳推理,1）,演绎推理,：从一般现象到个别（特殊）现象的推理。,2）,归纳推理,：从个别（特殊）现象到一般现象的推理。,3）,类比推理,：从个别（特殊）现象到个别（特殊）现象的推理。,1）,演绎推理,专家系统的研究基本上属于演绎推理范畴。演绎推理的核心是假言推理。,假言推理,：以假言判断为前提，对该假言判断的前件或后件的推理。,1）假言推理：,p,q，p q,2）三段论推理：,p,q，q,r p,r,3）假言易位推理（拒取式）：,p,q，,q,p,符号“,”表示推出,4.2.1 逻辑推理,2）归纳推理(个别一般),（1）数学归纳法,这种推导是严格的，结论是确实可靠的,。,（2）枚举归纳推理,S,1,是P，S,2,是P，S,n,是P,S,1,S,n,是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,产生式规则（if A then B）,1.正向推理,逐条搜索规则库，对每一条规则的前提条件，检查,事实库,中是否存在。,前提条件中各子项，若在事实库中,不是全部存在,，放弃该条规则。若在事实库中,全部存在,，则执行该条规则，把,结论,放入,事实库,中。,反复循环执行上面过程，直至推出目标，并存入,事实库,中为止1.,ABG,2.CDA,3.ED,B,C,E,4.2.2.2 产生式规则,事实库的最后状态为：,B，C，E，D，A，G,产生式规则库,事实库,产生式规则库和事实库的初始状态为：,4.2.2.2,产生式规则,逆,(,反,),向推理,逆向推理是从目标开始，寻找以,此目标为结论,的规则,对该规则的前提进行判断,，若该规则的前提中某个子项是另一规则的结论时，再找以此结论的规则。,重复以上过程，直到对某个规则的前提能够进行判断。按此规则前提判断（“是”或“否”）得出结论的判断，由此回溯到上一个 规则的推理，一直回溯到目标的判断。,G,A,D,E,B,C,4.2.2.2 产生式规则,逆向推理中，目标改变过程：,1.,ABG,2.CDA,3.ED,B,C,E,产生式规则库,事实库,4.2.3 搜索技术,搜索技术是人工智能的一个重要研究内容。智能技,术体现在,减少搜索树中的盲目搜索,。,1.,执行时间与，,，,等成正比的算法，称为,按多项式时间执行,。,2.,执行时间与,，！和,等成正比的算法，称为,按指数时间执行,。,按多项式时间执行的算法，计算机是可以实现的。按指数时间执行的算法，计算机是不可能实现的。,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)把初始节点S,0,故入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个棋子，初始状态为S,0,，目标状态为S,g,，如图1所示。,可使用的算符有：,空格左移，空格上移，空格右移，空格下移。即只允许把位于空格左、上、右、下的邻近棋子移入空格。要求寻找从初始状态到目标状态的路径。,?,该路径使用的算符序列：空格上移，空格左移，空格下移，空格右移。,广度优先搜索的盲目性较大，当目标节点距离初始节点较远时将会产生许多无用节点，因此搜索效率低，但是，只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的路径。,由图2可以看出，解的路径是S0381626,广度优先法适合于搜索树的宽度较小的问题。,1、深度优先搜索法思想,从初始状态S开始，利用规则生成搜索树下一层,任一个结点,，检查是否出现目标状态G，若未出现，以此状态利用规则生成再下一层,任一个,结点，再检查是否为目标节点G。若未出现，继续以上操作过程，一直进行到叶节点（即不能再生成新状态节点）。,当它仍不是目标状态G时，回溯到上一层结果，取另一可能扩展搜索的分支。生成新状态节点。,一直进行下去，直到找到目标状态G为止。,4.2.3.2 深度优先搜索法,图,4.8,深度优先搜索示意图,（2）算法,1)把初始节点S,0,故入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所示的搜索树这只是搜索树的一部分，尚未到达目标节点，仍需继续往下搜索。,?,在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上，则可较快地得到解。但是，,如果目标节点不在此分支上，而该分支又是一个无穷分支，则就不能得到解。,所以深度优先搜索是不完备的，即使问题有解，它也不一定能求得解。显然，,用深度优先求得的解，也不一定是路径最短的解。,深度优先法适合于搜索树的深度较小的问题,4.2.3.3,生成测试法,生成测试法算法是：,1,、生成一个可能状态节点。,2,、测试该状态是否为目标状态。,3,、若是目标状态则结束。否则回到第,1,步,其中生成可能的状态，可以是有规律的，也可以,是无规律的,4.2.3.3,生成测试法,（,1,）如果搜索过程中，,总是利用刚生成出的状态来生成新状态,，这种生成测试法就是,深度优先,搜索法。,（,2,）如果搜索过程中，,总是利用旧状态生成所有可能出新状态,，而且状态节点以从旧到新的顺序逐个生成的原则。这种生成测试法就是,广度优先,搜索法。,（,3,）如果搜索过程中，,有时利用旧状态生成新状态，有时利用新状态生成新状态，,这就是,无规律,的生成测试法。,4.2.3.4,爬山法(生成测试法的变种),爬山算法：(测试函数),1.开始状态作为一个可能状态。,2.从一个可能状态，应用,规则,生成所有新的可能状态集。,3.对该状态集中每一状态，进行如下操作：,对该状态测试，检查是否为目标，是则停止。,计算该状态的好坏，或者比较各状态的好坏。,4.取状态集中最好状态，作为下一个可能状态。,5.循环到第2步。,在爬山法中可能出现以下几种情况：,局部极大点：它比,周围邻居,状态都好，但不是目标。,图4.9局部极大点示意图,在爬山法中可能出现以下几种情况：,平顶：它与,全部邻居,状态都有,同,一个值，构成一个 平面。,图4.10 平顶示意图,在爬山法中可能出现以下几种情况：,山脊：它与,线状邻居,状态有相同值，比其它邻居状态要好。,图4.11山脊示意图,4.2.3.4,爬山法,为了解决以上问题，需要采用如下策略：,（,1,）,退,回到某一,更早,状态结点，沿着,另,一方向（对该结点就不一定是当时最好值的方向）进行爬山。,（,2,）朝一个方向,前进一大步,（按某方向深度优先搜索多次），走出平顶区，按别方向进行爬山。,（,3,）同时朝,两个或多个方向,前进，即按两个或多个方向爬山。,4.2.3.5,启发式搜索,启发式搜索是对每个在搜索过程中遇到的,新状态,，用一个,估计函数,（启发式函数）并计算其值的大小，确定下一步将从哪一个状态开始继续前进。,一般以,估计值小者为较优,的状态，以此实行最优搜索。,估计函数值的大小与从,初始状态到达目标状态,的路径有关。,4.2.3.5,启发式搜索,具体需要考虑以下,问题,：,（1）下一步选择哪个状态结点？,（2）是部分展开几个状态结点还是全部展开所有可能产生的状态结点？,（3）使用哪个规则（或算子）来展开新状态结点？,（4）怎样决定舍弃还是保留新生成的状态结点？,（5）如何定义启发式函数（估计值函数）？,（6）如何决定搜索方向？,（7）怎样决定停止或继续搜索？,一般启发式函数法用如下公式表示：,f,（,x,）,=g,（,x,）,+h,（,x,）,f,（,x,）,表示由开始状态到目标状态的总耗费,g,（,x,）,表示开始状态到当前状态的耗费。,h,（,x,）,表示当前状态到目标状态的耗费。,4.2.3.5 启发式搜索,启发式函数分析：,1.,当,h,（x,）,=0,，即,f,（,x,）,=g,（,x,）,取,f,（,x,）为最小，即取,g,（,x,）为最小。这要求在,已扩展,的结点中取最佳路径。,g,（,x,）能保证找到,最好解,。但对搜索速度没有太多的帮助。,2.,当,g,（,x,）,=0,，即,f,（,x,）,=h,（,x,）,h,（,x,）是从当前状态到目标状态的耗费。取它最小，将会,加快,搜索速度，但它并,不,保证得到最优解。,4.2.3.5 启发式搜索,g,（,x,）选取的几种特例：,g,（,x,）为搜索树的深度，,h,（,x,）,=0,，则启发式方法为广度优先搜索法。,g,（,x,）为搜索树的深度的负数，,h,（,x,）,=0则启发式方法为深度优先搜索法。因为深度愈深，负数愈大，搜索法总向深度发展。,(3),g,（,x,）为初始状态到该结点的代价,则启发式方法为代价优选搜索法。,f(x),一般表示估计值，愈接近精确值，启发式效果愈好。如果是精确值,就不是启发式函数。,4.2.3.5 启发式搜索,图-4 启发式搜索,2,8,3,1,6,4,7,5,2,8,3,1,4,7,6,5,1,3,8,2,4,7,6,5,2,8,3,1,4,7,6,5,2,3,1,8,4,7,6,5,2,8,3,1,4,7,6,5,8,3,2,1,4,7,6,5,2,8,3,7,1,4,6,5,2,3,1,8,4,7,6,5,2,3,1,84,7,6,5,8,3,2,1,4,7,6,5,1,3,8,2,4,7,6,5,1,2,3,8,4,7,6,5,8,1,3,2,6,4,7,5,8,1,3,2,4,7,6,5,1,2,3,7,8,4,6,5,8,3,2,1,4,7,6,5,8,1,3,2,4,7,6,5,8,1,3,2,4,7,6,5,1,2,3,8,4,7,6,5,1,3,8,2,4,7,6,5,1,2,3,8,4,7,6,5,*,8,1,3,7,2,4,6,5,*,4,4,5,5,4,5,3,5,4,2,3,0,5,4,5,5,4,5,3,2,0,4,h（x）可以,定义为节点,x中数码位置,与目标节点,相比不同的,个数,4.3 专家系统与智能决策支持系统,4.3.1 专家系统原理,4.3.2 产生式规则专家系统,4.3.3 专家系统与DSS的集成,4.3.4 建模专家系统,4.3.4 智能决策支持系统,4.3.1专家系统原理,1.专家系统概念,1）专家系统定义,专家系统是具有,大量专门知识,，并能运用这些知识解决特定领域中实际问题的计算机程序系统。,专家系统是利用大量的,专家知识,，运用知识推理的方法来解决各特定领域中的实际问题。计算机专家系统这样的软件能够达到人类专家解决问题的水平。,4.3.1专家系统原理,2）,专家系统的特点,专家系统需要大量的知识，这些知识是属于,规律性知识,，它可以用来解决千变万化的实际问题。,4.3.1专家系统原理,例如：,求解微积分问题,，是利用3040条微分、积分公式来求解千变万化的微分、积分问题，得出各自的结果。,其中微积分公式就是规律性知识，求解微积分问题就是对某函数反复利用微积分公式进行推导，最后得出该问题的结果。,这个推理过程是一个不固定形式的推理，即前后用哪个公式，调用多少次这些公式都随问题变化而变化。,1）专家系统对比数据库检索,数据库中存放的记录可以看成是,事实性知识,。如果把检索数据库记录看成是推理的话，它也是一种知识推理。它与专家系统的不同在于：,（A）知识只含事实性知识，不包含规律性知识。,（B）推理是对已有记录的检索，记录不存在，则检索不到。不能适应变化的事实，推理不出新事实。,4.3.1专家系统原理,4.3.1专家系统原理,2）专家系统对比数值计算,数值计算是用算法解决实际问题，对不同的数据可以算出不同的结果。,如果把数据看成是知识，算法看成推理的话，它也是一种知识推理。它与专家系统的不同在于：,（A）算法（推理过程）是固定形式的。算法一经确定，推理过程就固定了。而专家系统的推理是不固定形式的，随着问题不同，推理过程也不一样。,（B）数值计算只能处理数值，不能处理符号。,知识处理的特点,从上面分析可见，数值计算、数据处理是知识处理的特定情况，知识处理则是它们的发展!,（,A）知识包括事实和规则（状态转变过程）。,（B）适合于符号处理（如微积分求解）。,（C）推理过程是不固定形式的（推导过程中每次选用的规则知识是变化的）。,（D）能得出,未知,的事实（如推导出新的微分公式）。,2.专家系统结构,专家系统的核心是知识库和推理机。,专家系统可以概括为：,专家系统知识库,+,推理机,4.3.1专家系统原理,知识获取,人机接口,知识库,推理机,专家,用户,咨询 建议,专家系统核心,专家系统结构,3.产生式规则知识的推理机,产生式规则的推理机搜索+匹配（假言推理）,在推理过程中，是,一边搜索一边匹配,。匹配需要找事实,这个事实一是来自于规则库中别的规则，一是来自向用户提问。,在匹配时会出现成功或不成功，对于不成功的将引起搜索中的回溯和由一个分枝向另一个分枝的转移，可见在搜索过程中包含了回溯。,4.3.1 专家系统原理,4.3.1 专家系统原理,4.产生式规则推理的解释,推理中的搜索和匹配过程，如果,进行跟踪,和,显示,就形成了向用户说明的解释机制。,好的解释机制,不显示,那些对于,失败路径,的跟踪。,4.3.2 产生式规则专家系统,4.3.2.1 产生式规则,4.3.2.2 推理树(知识树),4.3.2.3 逆向推理过程,4.3.2.4 事实数据和解释机制,4.3.2 产生式规则专家系统,产生式规则的优点,产生式规则知识表示形式容易被人理解,它是基于演绎推理的,保证了推理结果的正确性,大量产生式规则所连成的推理树(知识树),可以是多棵树.,树的宽度反映问题的范围,树的深度反映问题的难度,4.3.2.1 产生式规则,ES,产生式规则知识一般表示为,:,if A then B,，,或 ：,如果,A,成立则,B,成立，,或：,A,B,4.3.2.1 产生式规则,产生式规则知识表示允许有如下的特点：,相同的条件可以得出不同的结论。,如：ABAC,相同的结论可以有不同的条件来得到。,如AGBG,条件之间可以是“与”（AND）连接和“或”（OR）连接,如ABG,ABG（相当于AG，BG）,一条规则中的结论，可以是另一条规则中的条件。,如FB，CF,其中F在前一条规则中是条件，在后一条规则中是结论。,4.3.2.1 产生式规则ES,由于以上特点，规则知识集能做到：,能描述和解决各种,不同,的灵活的实际问题。（由前三点特点形成）,能把规则知识集中的所有规则连成一棵,“与、或”推理树,（知识树）。即这些规则知识集之间是有关联的（由后二个特点形成）。,4.3.2.2推理树（知识树）,规则库中的各条规则之间一般来说都是,有联系,的,某条规则中的,前提,是另外一条规则中的,结论,。,按,逆向推理,思想把知识库所含的,总目标,（它是某些规则的结论）作为根结点，按规则的前提和结论展开成一棵树的形式。这棵树一般称为推理树或知识树，它把知识库中的所有规则都连结起来,由于连结时有“与”关系和“或”关系，从而构成了,“与或”推理树X F,G,L M E,C,4.3.2.2推理树（知识树）,（注：两斜线中间的,弧线,表示“,与,”关系，无弧线表示“或”关系）,规则知识库的逆向推理树,例：若有知识库为：,A（BC）G,（IJ）KA,XFJ,LB,MEC,WZM,PQE,画出“与或”推理树,A,B,I J K,W Z,P Q,用规则的前提和结论形式画出逆向推理树形式为：,4.3.2.2推理树（知识树）,前提I 前提J 前提L 前提M 前提E,(结论)(结论)(结论),前提A 前提B 前提C,（结论)（结论）(结论),总目标G（结论),前提X 前提F 前提W 前提Z 前提P 前提Q,?,?,?,?,?,?,?,?,该“与或”推理树的特点是：,每条规则对应的节点分枝有与（AND）关系，或（OR）关系,树的,根结点,是推理树的,总目标,相邻两层之间是,一条,或,多条,规则连接,每个结点可以是单值，也可以是多值。若结点是多值时，各值对应的规则将不同。,所有的叶结点，都安排向用户提问，或者把它的值直接放在,事实数据库,中。,4.3.2.2推理树（知识树）,4.3.2.3 逆向推理过程,推理树的深度优先搜索,N,1,7,9,8,2,G,A,B,C,J,I,K,L,M,E,4,5,Y,X,F,Z,P,Q,10,11,12,3,Y,W,Y,Y,Y,N,6,逆向推理过程在推理树中的反映为推理树的深度优先搜索过程。,4.3.23 逆向推理过程,在计算机中实现时，并不把规则连成推理树，而是利用规则栈来完成。当调用此规则时，把它压入栈内（相当于对树的搜索），当此规则的结论已求出（yes或no）时，需要将此规则退栈（相当于对树的回溯）。,利用规则栈的压入和退出的过程，相当于完成了推理树的深度优先搜索和回溯过程,。,4.3.2.3 逆向推理过程,结点的否定,每个结点有两种可能，即,YES,和,NO,。,叶结点为,NO,是由用户回答形成的。,中间结点为,NO,是由叶结点为,NO,，回溯时引起该结点为,NO,。,若当该结点还有其它“或条件”分枝时，不能立即确定该结点为,NO,，必须再搜索另一分枝，当另一分枝回溯为,YES,时该结点仍为,YES,。,中间结点只有所有“或”分枝的回溯值均为,NO,时，才能最后确定该中间结点为,NO,。,4.3.2.4 事实数据库和解释机制,1.事实数据库(动态数据库),事实,Y,N值,规则号,可信度,A,11,N,0(提问),0,A,12,Y,0,0.9,A,1,Y,4,0.8,事实栏放入命题,规则号：事实取Y或N的理由,可信度：事实的可信度,2.解释机制,解释机制是专家系统中重要内容。它把推理过程显示给用户，让用户知道目标是如何推导出来的。消除用户对目标结论的疑虑。,两种实现方法,一种是推理过程的全部解释；,一种是推理过程中正确路径的解释。,4.3.2.4 事实数据库和解释机制,4.3.3 专家系统与决策支持系统集成,IDSS充分发挥了专家系统以,知识推理,形式解决,定性,分析问题的特点.,发挥了决策支持系统以,模型计算,为核心的解决,定量,分析问题的特点.,充分做到,定性分析,和,定量分析,的有机结合.,数据库,DB,DSS,控制,系统,模型库,MB,问题综合,与,交互系统,动态,DB,推理机,和,解释器,知识库,KB,集成系统,DSS,ES,图4.16智能决策支持系统集成结构图,综合系统,DSS,和,ES,的总体结合。,由集成系统把,DSS,和,ES,有机结合起来,2.KB,和,MB,的结合。,模型库中的数学模型和数据处理模型作为知识的一种形式，即,过程性知识,，加入到知识推理过程中去。,3.DB,和动态,DB,的结合。,DSS,中的,DB,可以看成是相对静态的数据库，它为,ES,中的动态数据库提供初始数据，,ES,推理结束后，动态,DB,中的结果再送回到,DSS,中的,DB,中去。,DSS与ES集成形式一：DSS和ES并重的IDSS结构,集成,系统,DSS,ES,4.3.3 专家系统与决策支持系统集成,集成特点,1.具有综合系统，具有调用和集成DSS和ES的能力。,2.扩充DSS的问题与人机交互系统功能，增加对ES的调用组合能力,DSS与ES的关系,：,DSS中DB与ES中的动态DB进行数据交换,解决问题的特点,体现定性分析和定量分析并重解决问题的特点。,DSS,控制系统,MB,DB,ES,DSS与ES集成形式二：DSS为主体的IDSS结构,4.3.3 专家系统与决策支持系统集成,集成特点,集成系统和DSS控制系统合为一体,DSS与ES的关系,：,ES被DSS控制系统调用,解决问题的特点,体现以定量分析为主，结果定性分析解决问题的特点。,推理机,（广义）,DSS,动态DB,KB,推理机,MB,动态DB,KB,图4.19,DSS作为推理形式的IDSS,图4.20,模型作为知识的IDSS,DSS与ES集成形式三：,ES,为主体的,IDSS,结构,4.3.3 专家系统与决策支持系统集成,集成特点,人机交互系统和ES合为一体,DSS与ES的关系,图4.19 DSS作为推理机，受ES的推理机控制；,图4.20数据模型作为知识出现,解决问题的特点,体现以定量分析为主，结果定性分析解决问题的特点。,4.3.4 建模专家系统,专家系统实现,模型选择,的实例进行说明。,例如，弹簧振动建模专家系统。,该专家系统是解决弹簧在不同受力情况下（包括冲力、摩擦力等）应该满足那种类型的微分方程模型。,弹簧振动建模专家系统进行简化说明如下：,1、规则20条：,R1,：ABC,M1,R2,：A1A,R3,：A11A1,R4,：A12A1,R5,：ABEF,M2,R6,：C1C,R7,：E1E,R8,：ABEFG,M3,R9,：ABCG,M4,R10,：B1B,R11,：H1H,R12,：A2A,R13,：HBC,M5,R14,：HBCG,M6,R15,：HBEF,M7,R16,：HBEFG,M8,R17,：ABEI,M9,R18,：ABIG,M10,R19,：HBEI,M11,R20,：HBEIG,M12,4.3.4 建模专家系统,A,：弹簧满足胡克定律,B,：弹簧质量可以忽略,C,：可以忽略摩擦力,D,：没有冲力,A1,：弹簧有线性恢复力,A11,：弹力与位移成正比,A12,：位移量很小,E,：要考虑摩擦力,F,：摩擦力与速度之间为线性关系,C1,：若振动为自发时振幅为常数,E1,：若振动为自发时振幅是递减的,G,：有冲力F（T）,B1,：弹簧具有质量N并且N/M远远小于1,H1,：弹簧势能不是关于平衡位置对称,H,：弹簧不潢足胡克定律,A2,：弹簧势能与函数X（T）成正比,I,：摩擦力与速度之间为非线性关系,各项英文字母含义为：,M1,：X+（C2/M）X0,M2,：X+（C1/M）X+（C2/M）X0,M3,：X+（C1/M）X+（C2/M）XF（T）/M,M4,：X+（C2/M）XF（T）/M,M5,：X+F（X）/M0,M6,：X+F（X）/MF（T）/M,M7,：X+（C1/M）X+F（X）/M0,M8,：X+（C1/M）X+F（X）/MF（T）/M,M9,：X+（G/M）X+（C2/M）X0,M10,：X+（G/M）XC2/M）XF（T）/M,M11,：X+（G/M）X+F（X）/M0,M12,：X+（G/M）X+F（X）/MF（T）/M,其中,X,表示,X,对,的二阶导数，,X,表示一阶导数。,各模型微分方程为：,3.规则库的推理树,将20条规则连成的推理树见下图所示。,每个叶节点提问的回答为：,Yyes，Nno,专家系统将解释为证实某条规则而安排的提问。用户不明白专家系统为什么要提该问题，可以回答why,4.3.4 建模专家系统,A,2,A,1,B,1,C,1,？E,1,？B,1,？,A,11,A,12,？,D E F G H I,A,B,C,？,M（M,1,，M,2,，M,12,）,图,4.21弹簧振动推理树的标准形式,专家系统应用,现有一个弹簧，满足如下特性：,H,1,（弹簧势能不是关于平衡位置对称）,B,1,（弹簧具有质量,N,并且,N/M,远远小于,1,）,C,1,（若振动为自发时振幅为常数）,G,（有冲力,F,（,T,）,通过专家系统推理将得出：,该弹簧满足模型,6,（,M,6,）的微分方程。,4.5 遗传算法的决策支持,4.5.1 遗传算法原理,4.5.2 优化模型的遗传算法求解,4.5.3 获取知识的遗传算法,4.5.4 遗传规划建立模型,4.5.1 遗传算法原理,遗传算法(Genetic Algorithm，GA),是模拟,生物进化,的自然选择和遗传机制的一种,寻优,算法适用于,复杂的非线性,问题,主要应用在组合优化和机器学习两个方面。,应用领域：,图像识别、图像恢复、自适应控制、优化调度等领域。,遗传算法的发展过程大体上可分为以下三个阶段：,（1）70年代的兴起阶段。,1975年美国Michigan 大学J.Holland首次系统地阐述了遗传算法的基本理论和方法。,在这一时期的大部分研究都处于理论研究和建立实验模型阶段,（2）80年代的发展阶段。,1980年Smith教授将遗传算法应用于机器学习领域，研制出了一个著名的分类器(Classifier)系统。,这期间许多学者对遗传算法进行了大量的改进和发展，提出了许多成功的遗传算法模型，使遗传算法应用于更广泛的领域。,（3）90年代的高潮阶段。,进入90年代后，遗传算法作为一种实用、高效的优化技术，得到了极为迅速的发展。,4.5.1 遗传算法原理,4.5.1 遗传算法原理,4.5.1.1 遗传算法工作过程,4.5.1.2 遗传算法的理论基础,4.5.1.3 遗传算法的基本特征,4.5.1.1 遗传算法的工作过程,遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。,个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。,种群(population)就是模拟生物种群而由若干个体组成的群体,它一般是整个搜索空间的一个很小的子集。,遗传算法的三个主要操作算子,：,选择,（selecation）、,交叉,（crossover）和,变异,（mutation）,构成了遗传操作（,Genetic operation,），使遗传算法具有了其他传统方法所没有的特性。,产生新一代群体,编码和初始群体形成,输出种群,个体适应值满意否？,4.5.1.1 遗传算法的工作过程,首先将问题的每个可能的解按某种形式编码，编码后的解称作染色体（个体）。,随机选取,N,个染色体构成,初始,种群，再根据,预定,的,评价函数,对每个染色体计算适应值，使得性能较好的染色体具有,较高,的适应值。,选择,适应值高,的染色体进行复制，通过遗传算子来产生一群新的更适应环境的染色体，形成新的种群。,这样一代一代不断繁殖，最后收敛到一个最适应环境的个体上，求得问题的最优解。,遗传算子,选择,交叉,变异,1.群体中个体的编码,如何将问题描述成位串的形式，即问题编码。一般将问题的参数用,二进制位,（基因）编码构成子串，再将,子串,拼接起来构成“,染色体,”位串。,4.5.1.1 遗传算法的工作过程,例如：,个体 染色体,9 -1001,（2，5，6）-010 101 110,2.适应值函数的确定,遗传算法的执行过程中，每一代有许多不同的染色体（个体）同时存在，这些染色体中哪个保留(生存)、哪个淘汰(死亡)是根据它们对环境的适应能力决定的，适应性强的有更多的机会保留下来。,适应性强弱,是计算个体适应值函数f(x)的值来判别的，这个值称为适应值(fitness)。,适应值函数(即评价函数)是根据,目标函数,确定的。适应值总是,非,负的，任何情况下总是希望越大越好。如果目标函数不是取最大值时，需要将它映射成适应值函数。适应值函数f(x)的构成与目标函数有密切关系，往往是目标函数的变种。,一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。,4.5.1.1 遗传算法的工作过程,3.遗传算法的三个算子,（一）选择(Selection)算子,（二）交叉(Crossover)算子,（三）变异(Mutation)算子,4.5.1.1 遗传算法的工作过程,它又称,复制(reproduction)、繁殖算子。,选择是从种群中选择生命力强的染色体产生,新种群的过程,。依据每个染色体的适应值大小，适应值越大，被选中的概率就越大，其子孙在下一代产生的个数就越多。,选择操作是建立在群体中个体的,适应值估评基础,上的。,4.5.1.1 遗传算法的工作过程,（一）选择,(Selection),算子,通常做法是：对于一个规模为,N,的种群,S,按每个染色体,x,i,S,的选择概率,P,(,x,i,)所决定的选中机会,分,N,次从,S,中随机选定,N,个染色体,并进行复制。,4.5.1.1 遗传算法的工作过程,这里的选择概率,P,(,x,i,),的计算公式为,（一）选择,(Sele