第4章-智能决策支持系统.ppt

第4章智能决策支持系统和智能技术的决策支持,第4章目录,4.1智能决策支持系统综述4.2人工智能基本原理4.3专家系统与智能决策支持系统4.4神经网络的决策支持4.5遗传算法的决策支持4.6机器学习的决策支持,4.1智能决策支持系统综述,4.1.1智能决策支持系统概念智能决策支持系统（IntelligentDecisionSupportSystems,IDSS）是：决策支持系统（DSS）与人工智能（ArtificialIntelligent,AI）技术相结合的系统。,人工智能技术主要利用知识推理，完成定性分析。人工智能技术融入决策支持系统后，使DSS在模型技术与数据处理技术的基础上，增加知识推理技术，提高辅助决策能力。,4.1.2智能决策支持系统结构,1、人工智能的决策支持技术从智能决策支持系统的概念可知智能决策支持系统中包含了人工智能技术，与决策支持有关的人工智能技术主要有：专家系统、神经网络、遗传算法、机器学习、自然语言理解等。,1）专家系统是利用大量的专门知识解决特定领域中的实际问题的计算机程序系统；2）神经网络是利用神经元的信息传播模型（MP模型）进行学习和应用；3）遗传算法是模拟生物遗传过程的群体优化搜索方法；,4）机器学习是让计算机模拟和实现人类的学习，获取解决问题的知识；5）自然语言理解是让计算机理解和处理人类进行交流的自然语言。,2智能决策支持系统结构形式1）基本结构智能决策支持系统（IDSS）决策支持系统（DSS）人工智能（AI）技术IDSS基本结构如图4.1所示。人工智能技术可以概括为：推理机知识库智能决策支持系统的结构可以简化为图4.2所示。,4.2.1逻辑推理1.形式逻辑形式逻辑是研究人的思维形式及其规律的科学。它是属“符号处理”范畴。形式逻辑主要研究：形成概念、作出判断、进行推理。1）概念：概念是反映事物的特有属性和它的取值。2）判断：判断是对概念的肯定或否定。3）推理：推理是从一个或几个判断推出一个新判断的思维过程。,4.2人工智能基本原理,2.推理的种类,1）演绎推理：从一般现象到个别（特殊）现象的推理。2）归纳推理：从个别（特殊）现象到一般现象的推理。3）类比推理：从个别（特殊）现象到个别（特殊）现象的推理。,1）演绎推理,专家系统的研究基本上属于演绎推理范畴。演绎推理的核心是假言推理。假言推理：以假言判断为前提，对该假言判断的前件或后件的推理。1）假言推理：pq，pq2）三段论推理：pq，qrpr3）假言易位推理（拒取式）：pq，qp,2）归纳推理,（1）数学归纳法这种推导是严格的，结论是确实可靠的。（2）枚举归纳推理S1是P，S2是P，Sn是PS1Sn是S类事物中的部分分子，没有相反事例。所以，S类事物都是P。枚举归纳推理的结论是或然的。,3）类比推理,它是由两个（或两类）事物在某些属性上相同，进而推断它们在另一个属性上也可能相同的推理。A事物有abcd属性B事物有abc属性（或a,b,c相似属性）所以，B事物也可能有d属性（或d相似属性）类比推理的结论带有或然性。,3.总结,1）演绎推理的结论没有超出已知的知识范围。而归纳推理和类比推理的结论超出已知的知识范围。演绎推理只能解释一般规律中的个别现象。而归纳推理和类比推理创造了新的知识，使科学得到新发展，是一种创造思维方式。2）演绎推理中由于前提和结论有必然联系，只要前提为真，结论一定为真。归纳推理和类比推理中前提和结论，不能保证有必然联系，具有或然性。这样推理的结论未必是可靠的。需要经过严格的验证和证明，使之形成新的理论。,4.2.2知识表示与知识推理,4.2.2.1数理逻辑表示法1、命题逻辑举例：1）如果a是偶数，那么a2是偶数p:a是偶数，g:a2是偶数，它们的关系用“”（蕴含）表示。即：pq。2）“人不犯我，我不犯人；人若犯我，我必犯人”p:人犯我，q：我犯人；表示:(pq)(pq)或pq,在命题逻辑中，有五种关系：（与），（或），（非），（如果那么，即蕴含），（等价，即当且仅当），这五个关系称为联结词，它们之间有优先关系，从高到低有：、同级联结词，先出现先优先。,定义：由命题（p，q，r，）或用联结词（、）连接的命题，组合而成的公式称为合适公式（命题逻辑）。命题逻辑的公式有：1、析取交换律：pqqp2、合取交换律：pqqp3、析取结合律:（pq）rp（qr）4、合取结合律:（pq）rp（qr）,5、对的分配律：p(qr）(pq)(pr)6、对的分配律：p（qr）(pq)(pr)7、双重否定：pp8、德摩根律1：(pq)pq9、德摩根律2：(pq)pq,10、蕴含转换1:(pq)pq11、蕴含转换2:(pq)(qp)12、等价转换1:(pq)(pq)(qp)13、等价转换2:(pq)(pq)14、转：(pq)(pq),定义：公式的标准形式称为范式。有两种基本范式：合取范式、析取范式。1)、合取范式:它是一些简单析取式的合取式，即该合取式中，其子命题都是简单析取式。如：（A）(pq)(pq)（B）(pqr)(pqr)(pqz),2)、析取范式：它是一些简单合取式的析取式。即该析取式中，其子命题都是简单合取式。一般形式：a1a2ax其中每个ai是简单合取。如：（A）:(pq)(pr)（B）:（ppq）（pqrr）,2、谓词逻辑,主要研究一阶谓词逻辑。考虑全称和存在两个量词。全称量词：表示所有的，对每一个等。存在量词：表示至少有一个。公式：（1）或（2）或,谓词逻辑的合式公式定义：,由单个谓词或由联结词联结的多个谓词或含有或的谓词，以及它们的组合公式称为谓词逻辑的合适公式,谓词公式范式：1）前束范式：谓词公式中一切量词都未被否定的处于公式的最前方，且其管辖域为整个公式。例：2）前束范式（司柯林skolem范式）：所有存在量词都在全称量词之前的前束范式称为前束范式,3.命题逻辑归结原理A：把公式转换成子句型,归结原理使用反证法来证明语句。即归结是从结论的非，导出已知语句的矛盾。利用命题逻辑公式和谓词逻辑公式，把逻辑表达式化成合取范式、前束范式，再化成子句。一子句定义为由文字的析取组成的公式。转换过程如下：1）消去蕴含符号“”用AB替换AB,2）用德摩根律缩小的辖域，让进入括号内用AB代替(AB)用AB代替(AB)用代替用代替,3）把分母化成合取范式我们可以反复应用分配律，把任一母式化成合取范式。例如：,4）消去联结词符号在合取范式中，每一个合取元，取出成为一个独立句子。用子句集来代替原来子句的合取（）。每个子句实际上是文字的析取。例如：,4.命题逻辑归结原理B：归结过程,归结过程：对两个称为母子句的子句进行归结。以产生一个新子句。归结时，对一个子句中以“正文字”形式出现，一个以“负文字”形式出现，归结后就删除这两个“正负文字”，合并剩下的文字。若最后产生空子句，则存在矛盾。没有产生空子句就一直进行下去。,例1、例2、假言推理,5、命题逻辑中的归结,对公理集F、命题S的归结：1）把F的所有命题转换成子句型。2）把否定S的结果转换成子句型。3）重复下述归结过程，直到找出一个矛盾或不能再结：（A）挑选两个子句，称之为母子句。其中一个母子句含L，另一个母子句含L。（B）对这两个母子句作归结，结果子句称为归结式。从归结式中删除L和L，得到所有文字的析取式（C）若归结式为空子句，则矛盾已找到，否则原归结式加入到该过程中的现有子句集。,举例：从公理集：证明结果。1）把公理集转换成子句型这个合取式分为两个子句：这样子句集为：2）证明命题的非为,3）归结过程最后得到空语句，是矛盾的，故可得出结论：从公理集中可以推出。,1.正向推理逐条搜索规则库，对每一条规则的前提条件，检查事实库中是否存在。前提条件中各子项，若在事实库中不是全部存在，放弃该条规则。若在事实库中全部存在，则执行该条规则，把结论放入事实库中。反复循环执行上面过程，直至推出目标，并存入事实库中为止。,4.2.2.2产生式规则,产生式规则库和事实库的初始状态为：产生式规则库事实库,1.ABG2.CDA3.ED,B,C,E,事实库的最后状态为：,B，C，E，D，A，G,逆向推理是从目标开始，寻找以此目标为结论的规则，并对该规则的前提进行判断，若该规则的前提中某个子项是另一规则的结论时，再找以此结论的规则。重复以上过程，直到对某个规则的前提能够进行判断。按此规则前提判断（“是”或“否”）得出结论的判断，由此回溯到上一个规则的推理，一直回溯到目标的判断。,2.逆(反)向推理,逆向推理中，目标改变过程：,4.2.2.3语义网络,语义网络把问题中的概念用结点表示。概念之间的关系用弧来表示。这样，语义网络把概念以及它们之间的关系表示成一种结构图形式。语义网络的推理表现为对结点的访问以及结点间关系的检索，寻找概念之间的内在联系，通过推理可以回答两类问题：1、从概念结点间问它们之间关系？2、通过概念和关系问有关结点？,例如，“海浪猛烈地晃动轮船”这句话的语义网络图,通过语义网络我们能回答如下提问：问：海浪和轮船有什么关系？（寻找概念间的关系）答：某港海浪晃动某港轮船。（通过中间概念结点建立起关系）问：怎样晃动？（通过概念和关系寻找其它结点）答：猛烈地晃动。问：晃动哪些轮船？（寻找概念间的关系）答：晃动某港轮船。,4.2.2.4框架,框架由一组描述物体的各个方面的槽（属性）所组成。每个槽（属性）又可包含若干侧面所组成，每个侧面都有自己的名字和填入的值。,槽值可以有如下几种类型：具体值value默认值default过程值procedure：该值是一个计算过程，它利用该框架的其它槽值，按给定计算过程（公式）进行计算得出具体值。另一框架名：当槽值是另一框架名时，就构成了框架调用，这样就连成了一个框架链。空（待填入）框架推理的主要形式为：填充槽值。,1、匹配框架是一类事物的完整描述。事物之间匹配只能是部分相同槽的匹配。例：王强的行动和音量象消防车。我们要知道王强的行动和音量究竟是什么，应该对两个框架进行匹配。,框架1：王强是人性别男行动-音量-进取心中等框架2：消防车是车辆颜色红行动快音量极高载物水,匹配此两框架的槽：行动和音量。王强框架没有此槽值，而消防车框架有此槽值。匹配的结果是填充王强框架的两个槽值，得到：王强的行动是快的，音量是极高的。,2、继承继承有两种继承，即直接继承和条件继承。.直接继承：在框架网络中下层框架直接从上层框架中继承所有的属性值和条件。如“墙”继承“房子”的所有属性.条件继承：有条件的继承，如时序继承。,例：框架名：旧中国政体：资产阶级专政面积：960万平方公里人口：4亿5千万领导党派：国民党框架名：新中国政体：人民民主专政面积：960万平方公里人口：4亿5千万（当时1949年）领导党派：共产党其中，面积和人口是相同的，其它槽值就改变了。这就是有条件的继承。,4.2.2.5剧本,剧本是描述一定范围内一串原型事物的结构。1、剧本的组成(1)开场条件：事件发生之前必须满足的条件。例如，肚子饿了需要进餐，且有钱等。(2)结局：事件发生之后，通常会成为现实的情况。例如，肚子不再饿了，花了钱等。(3)道具：用来表示与剧本所描述的事件有关的物体。例如，餐桌、菜单、食物等。(4)角色：剧本中描述事件中的人物。例如，经理、顾客、服务员等。(5)线索：剧本表达事件的时序模式。例如，小食店、餐厅、酒家等。(6)场次：事件发生的顺序。每个场次可用框架描述。,2、实例,我们用“饭店”剧本作为例子说明。剧本：饭店演员：顾客、服务员第一场：进入饭店事件：走进饭店寻找空桌走到桌旁坐下第二场：点菜事件：服务员送菜单顾客读菜单选定菜告诉服务员,第三场：吃饭事件：服务员上菜、饭顾客吃饭第四场：离开事件：服务员送来帐单顾客付钱顾客离开饭店该剧本描述了饭店的正常业务过程。而对于一个实际的就餐故事省略了很多正常过程，只突出某个特定事件。如有故事：李杰来到饭店，找到一个位置，要了半只烤鸭，一菜一汤。李杰又吃又喝，一小时后醉醺醺地离开了饭店。,现在利用剧本来回答一些提问（由计算机来完成）：问：李杰吃了什么？（故事中只提了“要”没提“吃”）答：烤鸭、菜和汤。（由故事通过剧本而得出）问：谁给李杰菜单？（故事未提及）答：服务员。（由剧本中得出）问：谁上的菜？答：服务员。（由剧本中得出）问：李杰付钱没有？答：付了钱。（由剧本得出）从上例中可以看出，剧本能充实故事，解释故事,3、剧本的推理,从上面的例子可见剧本的推理为解释故事。具体为1）解释故事中没有提及的发生事件。2）说明连贯事件之间的关系。剧本通过推理，具有如下用途：1）预见不直接观察到的事件。如故事中未提及的服务员送菜单和上菜。2）能建立一种连贯事件的解释。如上故事中“要菜”跟“吃”是连贯的事件。3）能集中注意特殊的事件（意外情况）。,4.2.3搜索技术,搜索技术是人工智能的一个重要研究内容。智能技术体现在减少搜索树中的盲目搜索。1.执行时间与，等成正比的算法，称为按多项式时间执行。2.执行时间与，！和等成正比的算法，称为按指数时间执行。按多项式时间执行的算法，计算机是可以实现的。按指数时间执行的算法，计算机是不可能实现的。,搜索方法分类：,1、基本搜索法对搜索树的基本搜索法有两种思想，一是按广度优先展开搜索树的搜索方法，叫广度优先搜索法；一是按深度优先展开搜索树的搜索方法，叫深度优先搜索法。（1）广度优先搜索法。（2）深度优先搜索法。,2、生成测试法。3、爬山法。4、启发式搜索。5、博弈算法。（1）极小极大搜索法。（2）-剪枝算法。,4.2.3.1广度优先搜索（宽度优先搜索）,1、广度优先搜索思想从初始状态S开始，利用规则，生成所有可能的状态。构成树的下一层节点，检查是否出现目标状态G，若未出现，就对该层所有状态节点，分别顺序利用规则。生成再下一层的所有状态节点，对这一层的所有状态节点检查是否出现G，若未出现，继续按上面思想生成再下一层的所有状态节点.这样一层一层往下展开。直到出现目标状态为止。,搜索过程如下：,图4.7广度优先搜索示意图,4.2.3.1广度优先搜索（宽度优先搜索）,2、广度优先搜索算法：（1）把起始节点S线放到OPEN表中。（2）如果OPEN是空表，则失败推出，否则继续。（3）在OPEN表中取最前面的节点node移到CLOSED表中。（4）扩展node节点。若没有后继（即叶节点），则转向（2）循环。,（5）把node的所有后继节点放在OPEN表的后面。各后继结点指针指向node节点。（6）若后继节点中某一个是目标节点，则找到一个解，成功退出。否则转向（2）循环。广度优先法适合于搜索树的宽度较小的问题。,4.2.3.2深度优先搜索法,1、深度优先搜索法思想从初始状态S开始，利用规则生成搜索树下一层任一个结点，检查是否出现目标状态G，若未出现，以此状态利用规则生成再下一层任一个结点，再检查是否为目标节点G。若未出现，继续以上操作过程，一直进行到叶节点（即不能再生成新状态节点）。,当它仍不是目标状态G时，回溯到上一层结果，取另一可能扩展搜索的分支。生成新状态节点。一直进行下去，直到找到目标状态G为止。,搜索过程如下：,图4.8深度优先搜索示意图,2、深度优先算法（1）把起始节点S线放到OPEN表中。（2）如果OPEN是空表，则失败推出，否则继续。（3）从OPEN表中取最前面的节点node移到CLOSED表中。（4）若node节点是叶结点（若没有后继节点），则转向（2）。,（5）扩展node的后继节点，产生全部后继节点，并把他们放在OPEN表的前面。各后继结点指针指向node节点。（6）若后继节点中某一个是目标节点，则找到一个解，成功退出。否则转向（2）循环。深度优先法适合于搜索树的深度较小的问题。人工智能问题求解中，用深度优先搜索法比较多。Prolog语言提供的搜索机制是以深度优先法设计的。它比广度优先搜索法要好些。,4.2.3.3生成测试法,生成测试法算法是：1、生成一个可能状态节点。2、测试该状态是否为目标状态。3、若是目标状态则结束。否则回到第1步其中：生成可能的状态，可以是有规律的，也可以是无规律的,（1）如果搜索过程中，总是利用刚生成出的状态来生成新状态，这种生成测试法就是深度优先搜索法。（2）如果搜索过程中，总是利用旧状态生成所有可能出新状态，而且状态节点以从旧到新的顺序逐个生成的原则。这种生成测试法就是广度优先搜索法。如果搜索过程中，有时利用旧状态生成新状态，有时利用新状态生成新状态，这就是无规律的生成测试法。,4.2.3.4爬山法,爬山算法：1.开始状态作为一个可能状态。2.从一个可能状态，应用规则生成所有新的可能状态集。3.对该状态集中每一状态，进行：对该状态测试，检查是否为目标，是则停止。计算该状态的好坏，或者比较各状态的好坏。4.取状态集中最好状态，作为下一个可能状态。5.循环到第2步。,在爬山法中可能出现以下几种情况：,局部极大点：它比周围邻居状态都好，但不是目标。图4.9局部极大点示意图,在爬山法中可能出现以下几种情况：,平顶：它与全部邻居状态都有同一个值，构成一个平面。图4.10平顶示意图,在爬山法中可能出现以下几种情况：,山脊：它与线状邻居状态有相同值，比其它邻居状态要好。图4.11山脊示意图,爬山法进入以上状态就得不到目标解了。为了解决以上问题，需要采用如下策略：（1）退回到某一更早状态结点，沿着另一方向（对该结点就不一定是当时最好值的方向）进行爬山。（2）朝一个方向前进一大步（按某方向深度优先搜索多次），走出平顶区，按别方向进行爬山。（3）同时朝两个或多个方向前进，即按两个或多个方向爬山。,4.2.3.5启发式搜索,启发式搜索是对每个在搜索过程中遇到的新状态，用一个估计函数（启发式函数）并计算其值的大小，确定下一步将从哪一个状态开始继续前进。一般以估计值小者为较优的状态，以此实行最优搜索。估计函数值的大小与从初始状态到达目标状态的路径有关，具体需要考虑以下问题：,（1）下一步选择哪个状态结点？（2）是部分展开几个状态结点还是全部展开所有可能产生的状态结点？（3）使用哪个规则（或算子）来展开新状态结点？（4）怎样决定舍弃还是保留新生成的状态结点？（5）如何定义启发式函数（估计值函数）？（6）如何决定搜索方向？（7）怎样决定停止或继续搜索？,一般启发式函数法用如下公式表示：f（x）=g（x）+h（x）f（x）表示由开始状态到目标状态的总耗费g（x）表示开始状态到当前状态的耗费。h（x）表示当前状态到目标状态的耗费。,启发式函数分析：1.当h（x）=0，即f（x）=g（x）取f（x）为最小，即取g（x）为最小。这要求在已扩展的结点中取最佳路径。g（x）能保证找到最好解。但对搜索速度没有太多的帮助。2.当g（x）=0，即f（x）=h（x）h（x）是从当前状态到目标状态的耗费。取它最小，将会加快搜索速度，但它并不保证得到最优解。,g（x）选取的几种特例：g（x）为搜索树的深度，h（x）=0，则启发式方法为广度优先搜索法。g（x）为搜索树的深度的负数，h（x）=0，则启发式方法为深度优先搜索法。因为深度愈深，负数愈大，搜索法总向深度发展。,4.3专家系统与智能决策支持系统,4.3.1专家系统原理1.专家系统概念1）专家系统定义专家系统是具有大量专门知识，并能运用这些知识解决特定领域中实际问题的计算机程序系统。专家系统是利用大量的专家知识，运用知识推理的方法来解决各特定领域中的实际问题。计算机专家系统这样的软件能够达到人类专家解决问题的水平。,4.3.1专家系统原理,2）专家系统的特点专家系统需要大量的知识，这些知识是属于规律性知识，它可以用来解决千变万化的实际问题。计算机的应用发展概括为：数值计算数据处理知识处理（算法）（数据库处理）（推理）,4.3.1专家系统原理,例如：求解微积分问题，是利用3040条微分、积分公式来求解千变万化的微分、积分问题，得出各自的结果。其中微积分公式就是规律性知识，求解微积分问题就是对某函数反复利用微积分公式进行推导，最后得出该问题的结果。这个推理过程是一个不固定形式的推理，即前后用哪个公式，调用多少次这些公式都随问题变化而变化。,1）专家系统对比数据库检索数据库中存放的记录可以看成是事实性知识。如果把检索数据库记录看成是推理的话，它也是一种知识推理。它与专家系统的不同在于：（A）知识只含事实性知识，不包含规律性知识。（B）推理是对已有记录的检索，记录不存在，则检索不到。不能适应变化的事实，推理不出新事实。,2）专家系统对比数值计算数值计算是用算法解决实际问题，对不同的数据可以算出不同的结果。如果把数据看成是知识，算法看成推理的话，它也是一种知识推理。它与专家系统的不同在于：,（A）算法（推理过程）是固定形式的。算法一经确定，推理过程就固定了。而专家系统的推理是不固定形式的，随着问题不同，推理过程也不一样。（B）数值计算只能处理数值，不能处理符号。从上面分析可见，数值计算、数据处理是知识处理的特定情况，知识处理则是它们的发展。,知识处理的特点,（A）知识包括事实和规则（状态转变过程）。（B）适合于符号处理（如微积分求解）。（C）推理过程是不固定形式的（推导过程中每次选用的规则知识是变化的）。（D）能得出未知的事实（如推导出新的微分公式）。,2.专家系统结构,专家系统的核心是知识库和推理机。专家系统可以概括为：专家系统知识库+推理机,知识获取,人机接口,知识库,推理机,专家,用户,咨询建议,专家系统核心,专家系统结构,3.产生式规则知识的推理机,产生式规则的推理机搜索+匹配（假言推理）在推理过程中，是一边搜索一边匹配。匹配需要找事实。这个事实一是来自于规则库中别的规则，一是来自向用户提问。在匹配时会出现成功或不成功，对于不成功的将引起搜索中的回溯和由一个分枝向另一个分枝的转移，可见在搜索过程中包含了回溯。,4.产生式规则推理的解释,推理中的搜索和匹配过程，如果进行跟踪和显示就形成了向用户说明的解释机制。好的解释机制不显示那些对于失败路径的跟踪。,4.3.2产生式规则专家系统,目前，用产生式规则知识形式建立的专家系统是最广泛和最流行的。4.3.2.1产生式规则产生式规则知识一般表示为:ifAthenB，或：如果A成立则B成立，或：AB,产生式规则知识允许有如下的特点：相同的条件可以得出不同的结论。如：ABAC相同的结论可以有不同的条件来得到。如AGBG条件之间可以是“与”（AND）连接和“或”（OR）连接如ABGABG（相当于AG，BG）一条规则中的结论，可以是另一条规则中的条件。如FB，CF其中F在前一条规则中是条件，在后一条规则中是结论。,由于以上特点，规则知识集能做到：能描述和解决各种不同的灵活的实际问题。（由前三点特点形成）能把规则知识集中的所有规则连成一棵“与、或”推理树（知识树）。即这些规则知识集之间是有关联的（由后二个特点形成）。,4.3.2.2推理树（知识树）,规则库中的各条规则之间一般来说都是有联系的。即某条规则中的前提是另外一条规则中的结论。我们按逆向推理思想把知识库所含的总目标（它是某些规则的结论）作为根结点，按规则的前提和结论展开成一棵树的形式。这棵树一般称为推理树或知识树，它把知识库中的所有规则都连结起来。由于连结时有“与”关系和“或”关系，从而构成了“与或”推理树。我们通过一个例子用示意图形式画出。该推理树是逆向推理树，是以目标结点为根结点展开的。,例：若有知识库为：A（BC）G（IJ）KAXFJLBMECWZMPQE画出“与或”推理树为：,规则知识库的逆向推理树,（注：两斜线中间的弧线表示“与”关系，无弧线表示“或”关系）,用规则的前提和结论形式画出一般的推理树形式为：,该“与或”推理树的特点是：每条规则对应的节点分枝有与（AND）关系，或（OR）关系树的根结点是推理树的总目标相邻两层之间是一条或多条规则连接每个结点可以是单值，也可以是多值。若结点是多值时，各值对应的规则将不同。所有的叶结点，都安排向用户提问，或者把它的值直接放在事实数据库中。,4.3.2.3逆向推理过程,推理树的深度优先搜索逆向推理过程在推理树中的反映为推理树的深度优先搜索过程。图4.15逆向推理的搜索过程,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,在计算机中实现时，并不把规则连成推理树，而是利用规则栈来完成。当调用此规则时，把它压入栈内（相当于对树的搜索），当此规则的结论已求出（yes或no）时，需要将此规则退栈（相当于对树的回溯）。利用规则栈的压入和退出的过程，相当于完成了推理树的深度优先搜索和回溯过程。,结点的否定,从上例可见，每个结点有两种可能，即YES和NO，叶结点为NO是由用户回答形成的。中间结点为NO是由叶结点为NO，回溯时引起该结点为NO。对中间结点的否定，若当该结点还有其它“或条件”分枝时，不能立即确定该结点为NO，必须再搜索另一分枝，当另一分枝回溯为YES时，该结点仍为YES。中间结点只有所有“或”分枝的回溯值均为NO时，才能最后确定该中间结点为NO。,4.3.2.4事实数据库和解释机制,1.事实数据库,2.解释机制解释机制是专家系统中重要内容。它把推理过程显示给用户，让用户知道目标是如何推导出来的。消除用户对目标结论的疑虑。解释机制有两种实现方法：一种是推理过程的全部解释；一种是推理过程中正确路径的解释。具体算法不在此介绍。,4.3.3专家系统与决策支持系统集成,智能决策支持系统IDSS充分发挥了专家系统以知识推理形式解决定性分析问题的特点，又发挥了决策支持系统以模型计算为核心的解决定量分析问题的特点，充分做到定性分析和定量分析的有机结合。智能决策支持系统的具体集成结构形式如下图4.16所示。,图4.16智能决策支持系统集成结构图,综合系统,4.3.3专家系统与决策支持系统集成,IDSS中DSS和ES的结合主要体现在三个方面:1.DSS和ES的总体结合。由集成系统把DSS和ES有机结合起来(即将两者一体化)。2.KB和MB的结合。模型库中的数学模型和数据处理模型作为知识的一种形式，即过程性知识，加入到知识推理过程中去。3.DB和动态DB的结合。DSS中的DB可以看成是相对静态的数据库，它为ES中的动态数据库提供初始数据，ES推理结束后，动态DB中的结果再送回到DSS中的DB中去。,DSS和ES并重的IDSS结构,图4.18DSS为主体的IDSS结构,图4.19DSS作为推理形式的IDSS,图4.20模型作为知识的IDSS,ES为主体的IDSS结构,4.3.4建模专家系统,专家系统实现模型选择的实例进行说明。例如，弹簧振动建模专家系统。该专家系统是解决弹簧在不同受力情况下（包括冲力、摩擦力等）应该满足那种类型的微分方程模型。弹簧振动建模专家系统进行简化说明如下：,1、规则20条：R1：ABCM1R2：A1AR3：A11A1R4：A12A1R5：ABEFM2R6：C1CR7：E1ER8：ABEFGM3R9：ABCGM4R10：B1B,R11：H1HR12：A2AR13：HBCM5R14：HBCGM6R15：HBEFM7R16：HBEFGM8R17：ABEIM9R18：ABIGM10R19：HBEIM11R20：HBEIGM12,A：弹簧满足胡克定律B：弹簧质量可以忽略C：可以忽略摩擦力D：没有冲力A1：弹簧有线性恢复力A11：弹力与位移成正比A12：位移量很小E：要考虑摩擦力F：摩擦力与速度之间为线性关系C1：若振动为自发时振幅为常数,E1：若振动为自发时振幅是递减的G：有冲力F（T）B1：弹簧具有质量N并且N/M远远小于1H1：弹簧势能不是关于平衡位置对称H：弹簧不潢足胡克定律A2：弹簧势能与函数X（T）成正比I：摩擦力与速度之间为非线性关系,各项英文字母含义为：,M1：X+（C2/M）X0M2：X+（C1/M）X+（C2/M）X0M3：X+（C1/M）X+（C2/M）XF（T）/MM4：X+（C2/M）XF（T）/MM5：X+F（X）/M0M6：X+F（X）/MF（T）/MM7：X+（C1/M）X+F（X）/M0,M8：X+（C1/M）X+F（X）/MF（T）/MM9：X+（G/M）X+（C2/M）X0M10：X+（G/M）X+（C2/M）XF（T）/MM11：X+（G/M）X+F（X）/M0M12：X+（G/M）X+F（X）/MF（T）/M其中X表示X对的二阶导数，X表示一阶导数。,各模型微分方程为：,3.规则库的推理树将20条规则连成的推理树见下图所示。每个叶节点提问的回答为：Yyes，Nno当用户不明白专家系统为什么要提该问题，可以回答why，专家系统将解释为证实某条规则而安排的提问。,图4.21弹簧振动推理树的标准形式,专家系统应用,现有一个弹簧，满足如下特性：H1（弹簧势能不是关于平衡位置对称）B1（弹簧具有质量N并且N/M远远小于1）C1（若振动为自发时振幅为常数）G（有冲力F（T）通过专家系统推理将得出：该弹簧满足模型6（M6）的微分方程。,4.3.5智能决策支持系统实例,松毛虫智能预测系统(PCFES)是一个智能决策支持系统。该系统把模型库、数据库、知识推理、人机交互四者有机地结合起来了。达到了定性的知识推理、定量的模型数值计算、数据库处理的高度集成。该系统是我们和南京林业大学合作完成的。系统结构见图4.22。,图4.22松毛虫智能预测系统结构图,PCFES具有预测和管理功能。如图4.23所示。图4.23PCFES系统功能图,预测系统由三大部分组成:预测咨询系统、模型预测系统和虫情报表系统。1.预测咨询系统由国防科技大学自行研制的PROLOG产生器P3生成PROLOG程序，形成了松毛虫智能预测系统中的预测咨询系统。该专家系统能进行各种以定性为主的松毛虫预测，用于完成松毛虫发生期、发生量、发生范围和危害程度的定性预测和一些简单的定量预测咨询。它基本上包括了目前国内常用的各种预测方法，对于短期的发生期预测，它将直接给出日期，而不必由用户计算。预测咨询系统结构见图4.24所示。,预测咨询系统结构图：,4.3.5智能决策支持系统实例,2.虫情报表系统（管理信息系统）将积累的全国十一个省区的四十多份测报资料都存储到数据库中。实现了对全国十一省(区)四十多个测报资料数据库中数据的直接调用、查询、修改、增删。能打印几十种气象因子的历年数据以及松毛虫发生面积、虫情级数、虫口密度和各种防治方法、防治面积的历年数据的120多种报表。,3.模型预测系统由判定主要因子、预测模型、用主要因子进行预测和预测择优决策等四个模块就组成了模型预测系统。它完成需要进行大量计算的模型预测，用于进行各种松毛虫发生量(期)的定量预测。,该系统比前的预报方法有以下优点：（1）把多个不同的模型有机结合起来，形成一个完整的预测决策支持系统。（2）实现了相似模型的预测择优决策。（3）模型直接调用数据库中的数据。（4）形成了松毛虫测报的大型管理信息系统。（5）包含了预测松毛虫的专家系统。（6）建立一个多功能的综合系统。该系统把预测咨询专家系统、模型预测决策支持系统和测报管理信息系统汇集于一体。是一个大型智能决策支持系统。,4.4神经网络的决策支持,4.4.1神经网络原理人脑神经元的形状为：,神经元由细胞体、树突和轴突三部分组成；细胞体对接收到的信息进行处理。轴突是较长的神经纤维，是发出信息的。树突的神经纤维较短，是接收信息的。一个神经元的轴突末端与另一个神经元的树突之间密切接触，称为突触。,神经元具有如下性质：（1）多输入单输出；（2）突触具有加权的效果；（3）信息进行传递；（4）信息加工是非线性。,1、神经元的数学模型,其中：V1、V2、Vn为输入；i为该神经元的输出；ij为外面神经元与该神经元连接强度（即权），为阈值，f(X)为该神经元的作用函数。,MP模型方程为：其中Wij是神经元之间的连接强度，Wii0，Wij（ij）是可调实数，由学习过程来调整。,2、神经元作用函数,0,1阶梯函数:,-1,1的阶梯函数：,神经元作用函数,(-1,1)S型函数：,(0,1)S型函数：,3、学习规则,神经元的学习规则是Hebb规则。Hebb学习规则：若i与j两种神经元之间同时处于兴奋状态，则它们间的连接应加强，即：WijSiSj(0)这一规则与“条件反射”学说一致，并得到神经细胞学说的证实。设1，当SiSj1时，Wij1，在Si，Sj中有一个为0时，Wij0。,4.4.2反向传播模型(BP模型),BP模型是1985年由Rumelhart等人提出的。1.多层网络结构神经网络不仅有输入节点、输出节点，而且有一层或多层隐节点,如图：,2.作用函数为(0,1)S型函数,3.误差函数对第p个样本误差计算公式为：,其中pi，Opi分别是期望输出与计算输出,公式推导的思想是：网络权值与阈值的修正，使误差函数沿梯度方向下降。BP网络表示为，输入结点：xj，隐结点：yi，输出结点Ol。输入结点与隐结点间的网络权值为Wij，隐结点与输出结点间的网络权值为Tli。输出结点的期望输出为tl。,1.隐结点的输出：,2.输出结点计算输出：,其中：,其中：,BP模型的计算公式为：,3.输出结点的误差公式：,1.输出结点输出Ol计算公式（1）输入结点的输入xj（2）隐结点的输出：,其中：Wij连接权值，结点阈值。,(3)输出结点输出：,其中：Tij连接权值，结点阈值。,2输出层（隐结点到输出结点间）的修正公式（1）输出结点的期望输出：tl（2）误差控制：所有样本误差：,BP模型计算公式汇总,其中一个样本误差：,其中，p为样本数，n为输出结点数。（3）误差公式：,（4）权值修正：,其中k为迭代次数。（5）阈值修正：,3、隐结点层（输入结点到隐结点间）的修正公式（1）误差公式：,（2）权值修正：（3）阈值修正：,误差反向传播示意图,隐结点误差的含义：,按问题要求，设置输入结点为两个（x1,x2），输出结点为1个（z），隐结点定为2个（y1，y2）。各结点阈值和网络权值见图说明。,异或问题求解实例,计算机计算结果迭代次数：16745次；总误差：0.05隐层网络权值和阈值：w11=5.24，w12=5.23，w21=6.68，w22=6.641=8.012=2.98输出层网络权值和阈值：T1=-10，T2=10，=4.79,一、神经网络专家系统特点1.神经元网络知识库体现在神经元之间的连接强度（权值）上。它是分布式存贮的，适合于并行处理。2.推理机是基于神经元的信息处理过程。它是以P模型为基础的，采用数值计算方法。,4.4.3神经网络专家系统及实例,3.神经元网络有成熟的学习算法。感知机采用delta规则。反向传播模型采用误差沿梯度方向下降以及隐节点的误差由输出结点误差反向传播的思想进行的。.容错性好。由于信息是分布式存贮，在个别单元上即使出错或丢失，所有单元的总体计算结果，可能并不改变。,二、神经元网络专家系统结构,（一）确定系统框架1.完成对神经元网络的拓朴结构设计：（1）神经元个数（2）神经元网络层次（3）网络单元的连接2.确定神经元的作用函数和阈值作用函数用得较多的有两种：（1）阶梯函数（2）S型函数阈值的选取可为定值如i=0或i=0.5，或者进行迭代计算。,（二）学习样本学习样本是实际问题中已有结果的实例、公认的原理，规则或事实。（三）学习算法对不同的网络模型采用不同的学习算法，但都以Hebb规则为基础。1.Perceptron(感知机)模型：采用delta规则。2.Back-propagation(反向传播)模型：采用误差反向传播方法。,（四）推理机推理机是基于神经元的信息处理过程。1.神经元j的输入：其中，Wjk为神经元j和下层神经元k之间的连接权值。Ok为k神经元的输出。2.神经元j的输出:Oj=f(Ij-j)j为阈值，f为神经元作用函数。,（五）知识库知识库主要是存放各个神经元之间连接权值。由于上下两层间各神经元都有关系，用数组表示为：(Wij)i行对应上层结点，j列对应下层结点。,（六）输入模式转换实际问题的输入，一般是以一种概念形式表示，而神经元的输入，要求以(-,)间的数值形式表示。这需要将物理概念转换成数值。建立两个向量集：（1）实际输入概念集：各输入节点的具体物理意义，一般采用表的形式。（2）神经元输入数值集：各输入节点的数值。（七）输出模式转换实际问题的输出，一般也是以一种概念形式表示。而神经元的输出，一般是在0,1间的数值形式，这需要将数值向物理概念的转换。,评价城市医疗服务能力，输入包括五个方面：（1）病床数，（2）医生数，（3）医务人员数，（4）门诊数，（5）死亡率。其输出模式包括四个级别：（1）非常好(v)；（2）好(g)；（3）可接受(a)；（4）差(b)，建立一个三层的神经元网络。选择十个城市的数据作为训练集，学习之后，对其它城市进行评价。进行神经元网络计算，需要对物理概念的数值转换。输入节点数据允许在范围(-,)中取值，输出数据在范围0,1中取值。为了便于输出数据的判别，用四个节点分别表示v,g,a,b。对输入节点，用五个节点分别表示五个指标，对每个指标节点都有v,g,a,b四种可能。,三、神经网络专家系统实例,城市医疗服务能力评价系统神经网络结构图,城市医疗服务能力训练集,这四个物理概念的数值转换，我们进行了五个方案的计算，方案如下：方案1：v=3g=1a=-1b=-3方案2：v=1.5g=0.5a=-0.5b=-1.5方案3：v=6g=2a=-2b=-6方案4：v=1g=0.66a=0.33b=0方案5：v=10g=7a=4b=1计算结果表明，方案2收敛最快Count=360，计算结果也很合理，其次是方案1，Count=451，方案3,4,5均较差。说明物理概念的数值转换，尽量采用(-1,1)附近较合适。,4.4.4神经元网络的容错性四个动物的样本：（1）某动物是暗斑点、黄褐色、有毛发、吃肉，它就是豹。（2）某动物是黄褐色、有毛发、吃肉、黑条纹，它就是虎。（3）某动物是不飞、黑白色、会游泳、有羽毛，它就是企鹅。（4）某动物是有羽毛、善飞，它就是信天翁。,完成机器学习以后，对样本进行缺省条件输入，有如下三种情况：（1）缺1个条件的情况（2）缺2个条件的情况（3）介于中间的情况缺省条件推理结果表,从计算结果中，可以看出容错效果很好，对第一种情况的第一例，对豹缺省黄褐色条件时，输出结果仍然是豹（0.8463）；对第二种情况第一个例，对虎缺省黄褐色和多一个不飞的条件时，输出结果仍然是虎（0.9286）；对第三种情况的第一个例子，输入豹和虎的共同信息（黄褐色、有毛发、吃肉）时，神经网络的输出是既靠近豹（0.3394）又靠近虎（0.4203），输出结论：该动物是一个介于豹和虎的中间新品种。,4.5、遗传算法的决策支持,遗传算法(GeneticAlgorithm，GA)是模拟生物进化的自然选择和遗传机制的一种寻优算法。它模拟了生物的繁殖、交配和变异现象，从任意一初始种群出发，产生一群新的更适应环境的后代。这样一代一代不断繁殖、进化，最后收敛到一个最适应环境的个体上。遗传算法对于复杂的优化问题无需建模和进行复杂运算，只需要利用遗传算法的算子就能寻找到问题的最优解或满意解。,遗传算法的发展过程大体上可分为以下三个阶段：,（1）70年代的兴起阶段。1975年美国Michigan大学J.Holland首次系统地阐述了遗传算法的基本理论和方法。在这一时期的大部分研究都处于理论研究和建立实验模型阶段。（2）80年代的发展阶段。1980年Smith教授将遗传算法应用于机器学习领域，研制出了一个著名的分类器(Classifier)系统。这期间许多学者对遗传算法进行了大量的改进和发展，提出了许多成功的遗传算法模型，使遗传算法应用于更广泛的领域。（3）90年代的高潮阶段。进入90年代后，遗传算法作为一种实用、高效、鲁棒性强的优化技术，得到了极为迅速的发展。,一、遗传算法的工作过程遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。选择（selecation）、交叉（crossover）和变异（mutation）是遗传算法的三个主要操作算子，它们构成了遗传操作（Geneticoperation），使遗传算法具有了其他传统方法所没有的特性。遗传算法的工作过程如图所示：,4.5遗传算法原理,遗传算法的工作过程,1.群体中个体的编码如何将问题描述成位串的形式，即问题编码。一般将问题的参数用二进制位（基因）编码构成子串，再将子串拼接起来构成“染色体”位串。2.适应值函数的确定适应值函数(即评价函数)是根据目标函数确定的。适应值总是非负的，任何情况下总是希望越大越好。如果目标函数不是取最大值时，需要将它映射成适应值函数。,遗传算法的执行过程中，每一代有许多不同的染色体（个体）同时存在，这些染色体中哪个保留(生存)、哪个淘汰(死亡)是根据它们对环境的适应能力决定的，适应性强的有更多的机会保留下来。适应性强弱是计算个体适应值函数f(x)的值来判别的，这个值称为适应值(fitness)。适应值函数f(x)的构成与目标函数有密切关系，往往是目标函数的变种。,3遗传算法的三个算子,（一）选择(Selection)算子它又称复制(reproduction)、繁殖算子。选择是从种群中选择生命力强的染色体产生新种群的过程。依据每个染色体的适应值大小，适应值越大，被选中的概率就越大，其子孙在下一代产生的个数就越多。选择操作是建立在群体中个体的适应值估评基础上的，目前常用的选择算子有以下几种。,它又称重组(recombination)、配对(breeding)算子。染色体重组是分两步骤进行的，首先在新复制的群体中随机选取两个个体，然后，沿着这两个个体(字符串)随机地取一个位置，二者互换从该位置起的末尾部分。如，有两个用二进制编码的个体A和B。长度L=5，A=a1a2a3a4a5，B=b1b2b3b4b5随机选择一整数k1，L-1，设k=4，经交叉后变为：A=a1a2a3|a4a5A=a1a2a3b4b5B=b1b2b3|b4b5B=b1b2b3a4a5交叉算子在遗传算法中起着核心作用。