智能决策支持系统和智能技术的决策支持.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.2,4.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，pq2）三段论推理：pq，qrpr3）假言易位推理（拒取式）：pq，qp符号“”表示推出,4.2.1逻辑推理,2）归纳推理(个别一般)（1）数学归纳法这种推导是严格的，结论是确实可靠的。（2）枚举归纳推理S1是P，S2是P，Sn是PS1Sn是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.ABG2.CDA3.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.ABG2.CDA3.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)把初始节点S0故入OPEN表。,2)如果OPEN表为空，则问题无解，退出。,3)把OPEN表的第一个节点(记为节点n)取出放入CLOSED表。,4)考察节点n是否为目标节点。若是，则求得了问题的解，退出。,5)若节点n不可扩展，则转第2)步。,6)扩展节点n，将其子节点放入OPEN表的尾部，并为每一个子节点都配置指向父节点的指针，然后转第2)步。,广度优先搜索过程,例子1(八数码难题)重排九宫问题，在3x3的方格棋盘上放置分别标有数字1、2、3、4、5、6、7、8共8个棋子，初始状态为S0，目标状态为Sg，如图1所示。可使用的算符有：空格左移，空格上移，空格右移，空格下移。即只允许把位于空格左、上、右、下的邻近棋子移入空格。要求寻找从初始状态到目标状态的路径。,?,该路径使用的算符序列：空格上移，空格左移，空格下移，空格右移。广度优先搜索的盲目性较大，当目标节点距离初始节点较远时将会产生许多无用节点，因此搜索效率低，但是，只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的路径。,由图2可以看出，解的路径是：S0381626,广度优先法适合于搜索树的宽度较小的问题。,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)步。,深度优先搜索,例子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启发式搜索,*,*,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,产生式规则知识一般表示为:ifAthenB，或：如果A成立则B成立，或：AB,4.3.2.1产生式规则,产生式规则知识表示允许有如下的特点：相同的条件可以得出不同的结论。如：ABAC相同的结论可以有不同的条件来得到。如AGBG条件之间可以是“与”（AND）连接和“或”（OR）连接如ABGABG（相当于AG，BG）一条规则中的结论，可以是另一条规则中的条件。如FB，CF其中F在前一条规则中是条件，在后一条规则中是结论。,4.3.2.1产生式规则ES,由于以上特点，规则知识集能做到：能描述和解决各种不同的灵活的实际问题。（由前三点特点形成）能把规则知识集中的所有规则连成一棵“与、或”推理树（知识树）。即这些规则知识集之间是有关联的（由后二个特点形成）。,4.3.2.2推理树（知识树）,规则库中的各条规则之间一般来说都是有联系的某条规则中的前提是另外一条规则中的结论。按逆向推理思想把知识库所含的总目标（它是某些规则的结论）作为根结点，按规则的前提和结论展开成一棵树的形式。这棵树一般称为推理树或知识树，它把知识库中的所有规则都连结起来由于连结时有“与”关系和“或”关系，从而构成了“与或”推理树。,XF,G,LME,C,4.3.2.2推理树（知识树）,（注：两斜线中间的弧线表示“与”关系，无弧线表示“或”关系）,规则知识库的逆向推理树,例：若有知识库为：A（BC）G（IJ）KAXFJLBMECWZMPQE画出“与或”推理树,A,B,IJK,WZ,PQ,用规则的前提和结论形式画出逆向推理树形式为：,4.3.2.2推理树（知识树）,该“与或”推理树的特点是：每条规则对应的节点分枝有与（AND）关系，或（OR）关系树的根结点是推理树的总目标相邻两层之间是一条或多条规则连接每个结点可以是单值，也可以是多值。若结点是多值时，各值对应的规则将不同。所有的叶结点，都安排向用户提问，或者把它的值直接放在事实数据库中。,4.3.2.2推理树（知识树）,4.3.2.3逆向推理过程,推理树的深度优先搜索,逆向推理过程在推理树中的反映为推理树的深度优先搜索过程。,4.3.2.3逆向推理过程,在计算机中实现时，并不把规则连成推理树，而是利用规则栈来完成。当调用此规则时，把它压入栈内（相当于对树的搜索），当此规则的结论已求出（yes或no）时，需要将此规则退栈（相当于对树的回溯）。利用规则栈的压入和退出的过程，相当于完成了推理树的深度优先搜索和回溯过程。,4.3.2.3逆向推理过程,结点的否定每个结点有两种可能，即YES和NO。叶结点为NO是由用户回答形成的。中间结点为NO是由叶结点为NO，回溯时引起该结点为NO。若当该结点还有其它“或条件”分枝时，不能立即确定该结点为NO，必须再搜索另一分枝，当另一分枝回溯为YES时，该结点仍为YES。中间结点只有所有“或”分枝的回溯值均为NO时，才能最后确定该中间结点为NO。,4.3.2.4事实数据库和解释机制,1.事实数据库(动态数据库),事实栏放入命题,规则号：事实取Y或N的理由,可信度：事实的可信度,2.解释机制解释机制是专家系统中重要内容。它把推理过程显示给用户，让用户知道目标是如何推导出来的。消除用户对目标结论的疑虑。两种实现方法一种是推理过程的全部解释；一种是推理过程中正确路径的解释。,4.3.2.4事实数据库和解释机制,4.3.3专家系统与决策支持系统集成,IDSS充分发挥了专家系统以知识推理形式解决定性分析问题的特点.发挥了决策支持系统以模型计算为核心的解决定量分析问题的特点.充分做到定性分析和定量分析的有机结合.,图4.16智能决策支持系统集成结构图,综合系统,DSS和ES的总体结合。由集成系统把DSS和ES有机结合起来2.KB和MB的结合。模型库中的数学模型和数据处理模型作为知识的一种形式，即过程性知识，加入到知识推理过程中去。3.DB和动态DB的结合。DSS中的DB可以看成是相对静态的数据库，它为ES中的动态数据库提供初始数据，ES推理结束后，动态DB中的结果再送回到DSS中的DB中去。,DSS与ES集成形式一：DSS和ES并重的IDSS结构,4.3.3专家系统与决策支持系统集成,集成特点1.具有综合系统，具有调用和集成DSS和ES的能力。2.扩充DSS的问题与人机交互系统功能，增加对ES的调用组合能力DSS与ES的关系：DSS中DB与ES中的动态DB进行数据交换解决问题的特点体现定性分析和定量分析并重解决问题的特点。,DSS与ES集成形式二：DSS为主体的IDSS结构,4.3.3专家系统与决策支持系统集成,集成特点集成系统和DSS控制系统合为一体DSS与ES的关系：ES被DSS控制系统调用解决问题的特点体现以定量分析为主，结果定性分析解决问题的特点。,图4.19DSS作为推理形式的IDSS,图4.20模型作为知识的IDSS,DSS与ES集成形式三：ES为主体的IDSS结构,4.3.3专家系统与决策支持系统集成,集成特点人机交互系统和ES合为一体,DSS与ES的关系：图4.19DSS作为推理机，受ES的推理机控制；图4.20数据模型作为知识出现,解决问题的特点体现以定量分析为主，结果定性分析解决问题的特点。,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,4.3.4建模专家系统,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.3.4建模专家系统,图4.21弹簧振动推理树的标准形式,专家系统应用,现有一个弹簧，满足如下特性：H1（弹簧势能不是关于平衡位置对称）B1（弹簧具有质量N并且N/M远远小于1）C1（若振动为自发时振幅为常数）G（有冲力F（T）通过专家系统推理将得出：该弹簧满足模型6（M6）的微分方程。,4.5遗传算法的决策支持,4.5.1遗传算法原理4.5.2优化模型的遗传算法求解4.5.3获取知识的遗传算法4.5.4遗传规划建立模型,4.5.1遗传算法原理,遗传算法(GeneticAlgorithm，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）构成了遗传操作（Geneticoperation），使遗传算法具有了其他传统方法所没有的特性。,产生新一代群体,编码和初始群体形成,个体适应值满意否？,4.5.1.1遗传算法的工作过程,首先将问题的每个可能的解按某种形式编码，编码后的解称作染色体（个体）。随机选取N个染色体构成初始种群，再根据预定的评价函数对每个染色体计算适应值，使得性能较好的染色体具有较高的适应值。选择适应值高的染色体进行复制，通过遗传算子来产生一群新的更适应环境的染色体，形成新的种群。这样一代一代不断繁殖，最后收敛到一个最适应环境的个体上，求得问题的最优解。,1.群体中个体的编码如何将问题描述成位串的形式，即问题编码。一般将问题的参数用二进制位（基因）编码构成子串，再将子串拼接起来构成“染色体”位串。,4.5.1.1遗传算法的工作过程,例如：个体染色体9-1001（2，5，6）-010101110,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,按每个染色体xiS的选择概率P(xi)所决定的选中机会,分N次从S中随机选定N个染色体,并进行复制。,4.5.1.1遗传算法的工作过程,（一）选择(Selection)算子,（二）交叉(crossover)算子,它又称重组(recombination)、配对(breeding)算子，在遗传算法中起着核心作用。染色体重组是分两步骤进行的:首先在新复制的群体中随机选取两个个体然后，沿着这两个个体(字符串)随机地取一个位置，二者互换从该位置起的末尾部分。交叉率(crossoverrate)就是参加交叉运算的染色体个数占全体染色体总数的比例，记为Pc,取值范围一般为0.40.99。,4.5.1.1遗传算法的工作过程,4.5.1.1遗传算法的工作过程,例1:有两个用二进制编码的个体A和B。长度L=5，A=a1a2a3a4a5，B=b1b2b3b4b5随机选择一整数k1，L-1，设k=4，经交叉后变为：A=a1a2a3|a4a5B=b1b2b3|b4b5A=a1a2a3b4b5B=b1b2b3a4a5,s1=01000101,s2=10011011可以看做是原染色体s1和s2的子代染色体。,例2,设染色体s1=01001011,s2=10010101,交换其后4位基因,即,（二）交叉(crossover)算子,变异就是以很小的概率，随机地改变字符串某个位置上的值。变异操作是按位（bit）进行的，即把某一位的内容进行变异。在二进制编码中，就是将某位0变成1，1变成0。选择和交叉算子基本上完成了遗传算法的大部分搜索功能，而变异则增加了遗传算法找到接近最优解的能力。变异率(mutationrate)是指发生变异的基因位数所占全体染色体的基因总位数的比例，记为Pm，取值范围一般为0.00010.02。它保证了遗传算法的有效性。,4.5.1.1遗传算法的工作过程,（三）变异(Mutation)算子,4.5.1.1遗传算法的工作过程,例如:设染色体s=11001101将其第三位上的0变为1,即s=1100110111101101=s。s也可以看做是原染色体s的子代染色体。,（三）变异(Mutation)算子,4.控制参数设定遗传算法中的参数包括群体中个体的数目、交叉概率、变异概率等这些参数的设定随具体问题的不同将有所差别，带有经验性，它会影响遗传算法的迭代收敛过程。,4.5.1.1遗传算法的工作过程,1.模式定理遗传算法的理论基础是Holland提出的模式定理。一个模式(Schema)就是一个描述种群中在位串的某些确定位置上具有相似性的位串子集的相似性模板(SimilarityTemplate)。二进制串中的模式是如下的形式：（a1，a2，ai，an），ai0，1，*，其中“*”是任意符，或0，或1，模式是串的集合.模式H中确定位的个数,称为H的阶,记为O(H)。模式H中第一个确定位与最后一个确定位之间的距离称为的定义距,记为(H)。,4.5.1.2遗传算法的理论基础,例:以长度L=5的串为例,模式*101*描述了在位置2、3、4具有形式“010”的所有字符串,：*101*=(11010)，(01010)，(01011)，(11011)。其阶为3,定义距为2。,1.模式定理模式定理是遗传算法的理论基础它说明高适应值、长度短、阶数低的模式在后代中至少以指数增长包含该模式H的位串的数目。遗传使高适应值的模式复制更多的后代！,4.5.1.2遗传算法的理论基础,2基因块假设高适应值、长度短、低阶的模式叫基因块。基因块假说基因块通过遗传操作繁殖、交换、变异，再繁殖、再交换、再变异的逐渐进化，形成潜在的适应性较高的位串。该假设指出，通过遗传算法能寻找到接近全局最优解的能力。,4.5.1.2遗传算法的理论基础,1.遗传算法的处理对象是问题参数的编码个体（位串）遗传算法要求将问题的参数编码成长度有限的位串。遗传算法是在求解问题的编码串上进行操作，从中找出高适应值的位串，而不是对问题目标函数和它们的参数直接操作。遗传算法不受函数限制条件(如导数存在、连续性、单极值等)的约束。,4.5.1.3遗传算法的基本特征,2.遗传算法的搜索是从问题解位串集开始搜索，而不是从单个解开始在最优化问题中，传统的方法是从一个点开始搜索，如爬山法。一般复杂问题会在“地形”中出现若干“山峰”，传统的方法很容易走入假“山峰”。遗传算法同时从种群的每个个体开始搜索，象一张网罩在“地形”上，数量极大的个体同时在很多区域中进行搜索，这样就减少了陷入局部解的可能性。,4.5.1.3遗传算法的基本特征,3.遗传算法只使用目标函数(即适应值)来搜索，而不需要导数等其他辅助信息传统搜索算法需要一些辅助信息，如梯度算法需要导数，当这些信息不存在时，这些算法就失效了。而遗传算法只需目标函数和编码串，因此，遗传算法几乎可以处理任何问题。4.遗传算法使用的三种遗传算子是一种随机操作，而不是确定性规则遗传算法使用随机操作，但并不意味着遗传算法是简单的随机搜索。遗传算法是使用随机工具来指导搜索向着一个最优解前进。5.隐含的并行性6.易介入到已有的模型中，并具有扩展性；易于同别的技术结合使用,4.5.1.3遗传算法的基本特征,4.5.2优化模型的遗传算法求解,优化模型的计算是遗传算法最基本的也是最重要的研究和应用领域之一。一般说来，优化计算问题通常带有大量的局部极值点，往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的NP完全问题。精确地求解优化问题的全局最优解一般是不可能的。,4.5.2优化模型的遗传算法求解,4.5.2.1优化模型的遗传算法处理4.5.2.2实例,1、适应值函数优化遗传算法在进化搜索中用目标函数即适应值函数为依据。遗传算法的目标原函数不受连续可微的约束且定义域可以为任意集合对目标函数的唯一要求是，对输入个体可计算出能进行比较的非负适应值。这一特点使得遗传算法应用范围很广。遗传算法中，适应值函数要比较排序，并在此基础上计算选择概率，所以适应值函数的值要取正值。适应值函数评估是选择操作的依据，适应值函数设计直接影响到遗传算法的性能。在不少场合，将目标函数映射成求最大值形式且函数值非负的适应值函数是必要的。,4.5.2.1优化模型的遗传算法处理,2、约束条件的处理遗传算法是由适应值来评估和引导搜索，而对求解问题的约束条件不能明确地表示出来。用遗传算法求解这些带约束的问题，需要进行一些处理。在等式约束方程中，对P个等式方程中抽出P个变量，经过线性组合变换后，用其余变量表示为该P个变量的等式，并将它代入目标函数中，消去该P个变量。这样，在目标函数中，就包含了这些等式约束条件。,4.5.2.1优化模型的遗传算法处理,4.5.2.1优化模型的遗传算法处理,3、遗传算法的迭代终止条件当适应值函数的最大值已知时，一般以发现满足最大值或准最优解作为遗传算法迭代终止条件。但是，在许多优化计算问题中，适应值函数的最大值并不清楚，迭代终止条件一般定为：群体中个体的进化已趋于稳定状态，即发现占群体中一定比例的个体已完全是同一个体。,步1在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T；步2随机产生U中的N个个体s1,s2,sN，组成初始种群S=s1,s2,sN，置代数计数器t=1；步3计算S中每个个体的适应度f()；步4若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。步5按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1；步6按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；步7按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；步8将群体S3作为新一代种群，即用S3代替S，t=t+1，转步3；,基本遗传算法步聚,例4.1利用遗传算法求解区间0,31上的二次函数y=x2的最大值。,分析原问题可转化为在区间0,31中搜索能使y取最大值的点a的问题。那么，0,31中的点x就是个体,函数值f(x)恰好就可以作为x的适应度，区间0,31就是一个(解)空间。这样,只要能给出个体x的适当染色体编码,该问题就可以用遗传算法来解决。,解(1)设定种群规模,编码染色体，产生初始种群。将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)(2)定义适应度函数,取适应度函数：f(x)=x2(3)计算各代种群中的各个体的适应度,并对其染色体进行遗传操作,直到适应度最高的个体(即31（11111）)出现为止。,首先计算种群S1中各个体s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)的适应度f(si)。容易求得f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361,再计算种群S1中各个体的选择概率。,选择概率的计算公式为,由此可求得P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31,赌轮选择示意,赌轮选择法,在算法中赌轮选择法可用下面的子过程来模拟:在0,1区间内产生一个均匀分布的随机数r。若rq1,则染色体x1被选中。若qk-10有：,由上式易知，公式发现问题可以看成如下优化问题：,1、遗传规划个体编码设计对于遗传规划问题，搜索优化公式是在函数空间上进行的，采用二叉树描述遗传规划个体。在把树转化为二叉树中，树的第一棵子树变为二叉树的左子树，子树的兄弟变为二叉树中该左子树的右子树，如此递归，形成树和二叉树的一一对应关系。,4.5.4.1遗传规划建立模型的设计与实现,例如表达式f(x)=f1(x1,x2,x3)+f2(x1,C1)+C2用树及二叉树分别表示如下图所示。,初始化群体随机生成具有个公式模型的初始群体。根据公式的编码表示，这里每个公式对应一个二叉树，公式的复杂度可以由树的深度来控制。树的中间结点和叶结点元素分别从函数空间中按均匀分布选取。公式个体适应度评估计算群体内每个公式的适应值。适应度函数的确立应反映公式发现的目标，通常不仅希望误差小而且希望公式的形式比较简单。,4.5.4.1遗传规划建立模型的设计与实现,2、遗传算子（1）选择算子根据一定的选择策略对每个个体分配选择概率，再根据选择概率并使用轮盘式选择来选择个体进行繁殖，采用择优策略，将上代最好的个体保留在当前新的种群中，保证了算法的收敛性。（2）交换算子由于遗传规划中的函数的不同，定义域和值域的差异，遗传规划的搜索空间过大，趋向于随机搜索。所以，不能仿照遗传算法进行设计遗传规划的遗传算子。（具体见书）,4.5.4.1遗传规划建立模型的设计与实现,（3）变异算子变异算子首先在父体中随机选择一个结点（称为变异点），若变异点是内部结点（即非叶结点），则执行下述三种操作之一：删除以变异点为根结点的子树（称为变异子树），并在变异点插入一个随机生成的子树；交换变异子树的左右子树；化简变异子树，用计算获得的值替代某些部分,4.5.4.1遗传规划建立模型的设计与实现,step1.根据给定参数，随机产生初始群体F(0)，计算F(0)中个体的适应度。适应度由误差公式得出；step2.根据个体适应度及选择策略确定F(T)内每个个体的选择概率Pi；step3.根据给定参数，确定交换操作的个体数量为2M(交换操作的个体数量应为偶数)、变异个体数量为N；,基于遗传规划的公式发现算法流程设计,step4.依据概率Pi，在F(T)中选择2M个个体执行交换操作step5.执行变异操作，利用变异算子，产生N个个体，插入到F(T)中；step6.执行选择操作，在F(T)中依据个体适应度，选择给定数量的新个体组成新的群体F(T+1)；step7.计算F(T+1)中个体的适应值，迭代次数+1；step8.终止条件判定：发现公式的误差小于预定误差或者遗传规划的遗传代数超过预先定义的值则终止。满足终止条件，输出结果；不满足终止条件，则返回Step2继续迭代,基于遗传规划的公式发现算法流程设计,有如下已知数据：遗传建模主要参数设置：种群规模500，最大进化代数50，个体创建时最大树深10，交换操作时树深限制20，算子空间F=+，-，*，/，log，sin，cos，abs，sqrt，x，x2，x3，x-1，x-2。遗传规划发现公式为：(x)=x2+log(x+1)+log7,3、遗传规划建立模型应用实例,计算结果发现公式的误差：0.032345公式发现结果显示：,“虫与草游戏”,草地上有着一群吃草的虫子。(这些虫子不能看见远处什么地方有草)每个虫子都按自己的“遗传策略”爬行，碰到草就将草吃掉，没有碰到就继续爬行而草被吃掉后，过一段时间又会(随机的)长出来。现在的问题是：怎样的“爬行策略”才是“智慧”的能够让虫子吃到最多的草？,要回答这个问题，就可以使用“常阶遗传算法”：将虫子使用的“爬行策略”编码成“基因串”；让那些吃到足够多的草的虫子繁殖后代“遗传基因串”，反之没到草的虫子就让它“饿死”。经过很多代的“基因遗传”后，我们会看到“爬行策略”开始向“问题的解”“收敛”。,遗传收敛可以看到随着算法的运行，虫“直走的概率”会慢慢变大“长途迁徙”的虫子会越来越多，“原地打圈”的虫子则会被淘汰，这就是“遗传算法的收敛”。要想“遗传收敛”得“快”，“宽与高”就应该足够大，“生长草”的概率可以相应降低些。比如，宽=60,高=60，草能量=6，草概率=0.002，繁殖能量=120，初始虫数量=18,4.5机器学习的决策支持,4.5.1机器学习概述4.5.2机器学习分类4.5.3建立模型的发现学习,4.5.1机器学习综述,1.基本概念学习和解决问题是人类最重要的两个智能行为机器学习是让计算机模拟和实现人类的学习，获取知识。机器学习也是计算机具有智能的重要标志。,4.5.1机器学习综述,(1)人类学习概念的学习、领域知识的学习、技能（元知识即解决问题）的学习特点：过程缓慢、会忘记、知识传授困难、能不断修改知识，使人类逐渐变得聪明。,4.5.1机器学习综述,(2)机器学习（1）R.S.Michalski认为：学习是构造或修改所经历的事物的表示。该观点强调知识的表示。（2）学习是知识的获取。该观点强调知识获取。（3）H.A.Simon认为：学习是系统在相似的任务中，做一些适应性变化，使得在下一次类似的任务中，做得更好。该观点强调学习的效果。,4.5.1机器学习综述,2.机器学习与专家系统专家系统知识获取的“瓶颈”现象知识的脆弱性缺乏直觉判断能力机器学习提供知识获取提供有效途径,4.5.1机器学习综述,3.机器学习实例1.Michalski和R.L.Chilausky的PLANT/SS系统它是一个大豆病害诊断防治专家系统。该系统用示例学习AQ11算法自动产生规则进行诊断。把631种有病害的大豆的性状描述（表示为包含35种特性的向量）和每种植物的病名一起输入到计算机中选用290种做为训练例子（例子间相差很远），利用AQ11算法获得规则知识。再用340个样本作为测试例子，并将专家和计算机的诊断结果进行对比。,4.5.1机器学习综述,计算机产生的规则优于专家归纳的规则专家的正确判断率为71.8。计算机的正确判断率高达97.6。,4.5.1机器学习综述,钟鸣和陈文伟的IBLE算法利用信息论的信道容量思想，研制了IBLE算法。对已有结论的化学物质的质谱进行学习，得出了质谱规则。然后利用这些规则再去测试未知化学物质的质谱，得出它的种类。,钟鸣和陈文伟的IBLE算法,一般专家的正确识别率70%,4.5.2机器学习分类,学习过程的本质是学生(学习系统)把教师或环境(如书本)提供的信息转换成能够理解的形式记忆下来，以便将来使用.当前,国际上流行的机器学习分类方法主要有四种:按应用领域分类(专家系统、问题求解、认知模拟）按获取知识的表示分类(逻辑表达式、产生式规则、决策树、框架、神经网络)按推理策略分类(演绎推理和归纳推理)机械学习、示教学习、通过例子学习、解释学习、类比学习、发现学习按系统性分类(历史渊源、知识表示、推理策略、应用领域).,4.5.2机器学习系统基本结构,环境,学习,知识库,执行,(1)机械学习（ROTELEARNING),1.思想:记忆=检索+计算2.示意图,例子：汽车保险程序,该程序能对被损坏的汽车的修理费用进行计算.它的输入是汽车损坏情况,即生