第8章人工智能与专家系统

第8章人工智能与专家系统Nothing is impossible for a willing heart.心之所愿，无所不成。心之所愿，无所不成。本章主要内容本章主要内容l人工智能的基本原理人工智能的基本原理l专家系统原理与产生式规则专家系统专家系统原理与产生式规则专家系统l遗传算法的决策支持遗传算法的决策支持一、人工智能的基本原理什么是智能?l请说请说出出3种你身种你身边边或你所知道的智能化事物或你所知道的智能化事物什么是智能?l智能（Intelligence)即智力功能，是人类大脑所具有的感知、认识、学习、理解、分析、综合、判断、推理、创造等局部功能的总和与它们的有机综合的统称；因此，完善的智能中完善的智能中还应还应包含包含有人有人类类的情感、意的情感、意识识、意志等、意志等这这种高种高级级因素因素。计算机与智能计算机与智能l例子：IBM超级计算机l通常我们用计算机，不仅要告诉计算机，要做什么，还必须通常我们用计算机，不仅要告诉计算机，要做什么，还必须详细地、正确地告诉计算机怎么做。也就是说，人们要根据详细地、正确地告诉计算机怎么做。也就是说，人们要根据任务的要求，以适当的计算机语言，编制针对该任务的应用任务的要求，以适当的计算机语言，编制针对该任务的应用程序，才能应用计算机完成此项任务。这样实际上是人完全程序，才能应用计算机完成此项任务。这样实际上是人完全控制计算机完成的，是谈不上计算机有真正的控制计算机完成的，是谈不上计算机有真正的“智能智能”。一个例子-IBM超级计算机“深蓝”l1997年年5月月11日，世界国日，世界国际际象棋棋王卡斯帕象棋棋王卡斯帕罗罗夫与美国夫与美国IBM公司的公司的RS6000（深深蓝蓝）计计算机系算机系统进统进行了六局行了六局“人机大人机大战战”，结结果果“深深蓝蓝”以以3.5比比2.5的的总总比分比分获胜获胜。一个例子-IBM超级计算机“沃森”l2011年，年，IBM超超级计级计算机算机Watson在在危危险边缘险边缘竞赛节竞赛节目目中中击败击败了了该节该节目目历历史上最成功的两位人史上最成功的两位人类选类选手，手，继继“深深蓝蓝”之之后，后，聪聪明的人明的人脑脑再一次再一次败给败给了智慧程序。了智慧程序。l视频视频 计算机战胜人类的计算机战胜人类的“诀窍诀窍”是什么？是什么？返回返回2、什么是人工智能、什么是人工智能(AI,Artificial Intelligence)？l就是研究怎样让计算机做一些通常认为就是研究怎样让计算机做一些通常认为需要智能才能做的需要智能才能做的事情事情，又称机器智能。，又称机器智能。l虽然是计算机科学的一个分支，但并不只涉及到计算机科虽然是计算机科学的一个分支，但并不只涉及到计算机科学，而且还涉及到学，而且还涉及到脑脑科学、神科学、神经经生理学、心理学、生理学、心理学、语语言学、言学、逻辑逻辑学、学、认认知（思知（思维维）科学、行）科学、行为为科学和数学以及信息科学和数学以及信息论论、控制控制论论和系和系统论统论等许多学科领域。等许多学科领域。21世纪三大尖端技术世纪三大尖端技术 n基因工程基因工程n纳米科学纳米科学n人工智能人工智能 关于人工智能问题l是一个是一个古老的但又十分新古老的但又十分新颖颖的研究的研究课题课题l各国在人工智能的研究上都已各国在人工智能的研究上都已经获经获得巨大的得巨大的进进展展l各种各种传统传统的或新的或新颖颖的智能模型迄今的智能模型迄今还还不能完全而不能完全而圆满圆满地地对对大大脑脑思思维维活活动动的的过过程程进进行解行解释释和模和模拟拟人们还不十分了解信息在大脑中的底层结构和编码方法；人们还不十分了解信息在大脑中的底层结构和编码方法；象人们的概念、意识、情感和创造性思维过程等，还根本无象人们的概念、意识、情感和创造性思维过程等，还根本无从着手；从着手；l在哲学上、自然科学以及社会学科上在哲学上、自然科学以及社会学科上还还有很大的争有很大的争论论，还还不能得到一致不能得到一致认认同。同。谷歌无人驾驶汽车谷歌无人驾驶汽车 内华达州是美国对公共道路无人驾驶立法的第一个州。截至内华达州是美国对公共道路无人驾驶立法的第一个州。截至2012年年6月，谷歌的无人驾驶汽车已经在该州行进了月，谷歌的无人驾驶汽车已经在该州行进了25万英里。万英里。谷歌无人驾驶汽车的构造示意图及其描绘的谷歌无人驾驶汽车的构造示意图及其描绘的3D3D地形图地形图关于无人驾驶汽车的争议话题关于无人驾驶汽车的争议话题l如果无人驾驶汽车因为避让行人而损害了其他车辆或给车内人员带来危险，它应该避让吗？为为什么要研究人工智能？什么要研究人工智能？lPeople like to make machines that can do what we can.lBecause we are curiouslBecause we are lazylBecause we are not so able人工智能研究的目标人工智能研究的目标l如果如果说现说现在有一台在有一台电脑电脑，其运算速度非常快、，其运算速度非常快、记亿记亿容量和容量和逻逻揖揖单单元的数目也超元的数目也超过过了人了人脑脑，而且，而且还为这还为这台台电脑编电脑编写了写了许许多智能化的程序，并提供了合适种多智能化的程序，并提供了合适种类类的大量数据，使的大量数据，使这这台台电脑电脑能能够够做一些人性化的事情，如做一些人性化的事情，如简单简单地听或地听或说说。回答。回答某些某些问题问题等。那么，我等。那么，我们们是否就能是否就能说这说这台机器具有思台机器具有思维维能能力了呢力了呢?或者或者说说，我我们们怎怎样样才能判断一台机器是否具存了才能判断一台机器是否具存了思思维维能力呢能力呢?l1950年英国数学家年英国数学家图图灵（灵（A.M.Turing,19121954）发发表表了了”计计算机与智能算机与智能”的的论论文中提出文中提出著名的著名的“图图灵灵测试测试”，形象，形象地地提出人工智能提出人工智能应该应该达到的智能达到的智能标标准准。图灵测试图灵测试l即一个人在不接触对方的情况下，通过一种特殊的方式，和即一个人在不接触对方的情况下，通过一种特殊的方式，和对方进行一系列的问答，对方进行一系列的问答，如果在相当如果在相当长时间长时间内，内，他无法根据他无法根据这些问题判断对方是人还是计算机，那么，就可以认为这个这些问题判断对方是人还是计算机，那么，就可以认为这个计算机计算机具有同人相当的智力具有同人相当的智力，即这台计算机是，即这台计算机是能思能思维维的的。如果由你来提问，你会问哪些问题呢？如果由你来提问，你会问哪些问题呢？图灵测试示范性问题图灵测试示范性问题问：问：请给我写出有关“第四号桥”主题的十四行诗。答：答：不要问我这道题，我从来不会写诗。问：问：34957加70764等于多少？答：答：（停30秒后）105721问：问：你会下国际象棋吗？答：答：是的。问：问：我在我的K1处有棋子K；你仅在K6处有棋子K，在R1处有棋子R。现在轮到你走，你应该下那步棋？答：答：（停15秒钟后）棋子R走到R8处，将军！可以通过编制可以通过编制特殊的程序来特殊的程序来实现。实现。l从表面上看，要使机器回答按一定范从表面上看，要使机器回答按一定范围围提出的提出的问题问题似乎没似乎没有什么困有什么困难难，可以通，可以通过编过编制特殊的程序来制特殊的程序来实现实现。然而，如。然而，如果提果提问问者并不遵循常者并不遵循常规标规标准，准，编编制回答的程序是极其困制回答的程序是极其困难难的事情。的事情。图灵测试的示范性问题不按常规的提问图灵测试的示范性问题不按常规的提问(1)l问：问：你会下国际象棋吗？答：答：是的。问：问：你会下国际象棋吗？答：答：是的。问：问：请再次回答，你会下国际象棋吗？答：答：是的。你多半会想你多半会想到，面前的到，面前的这位是一部这位是一部笨机器笨机器!l问：问：你会下国际象棋吗？答：答：是的。问：问：你会下国际象棋吗？答：答：是的，我不是已经说过了吗？问：问：请再次回答，你会下国际象棋吗？答：答：你烦不烦，干嘛老提同样的问题。图灵测试的示范性问题不按常规的提问图灵测试的示范性问题不按常规的提问(2)那么，你面那么，你面前的这位，前的这位，大概是人而大概是人而不是机器不是机器!“图灵梦想”的对话l在这段对话中“询问者询问者”代表人代表人，“智者智者”代表机器代表机器，并且假定他们都读过狄更斯（C.Dickens）的著名小说匹克威克外传，对话内容如下：询问者：询问者：在14行诗的首行是“你如同夏日”，你不觉得“春日”更好吗？智者：智者：它不合韵。询问者：询问者：“冬日”如何？它可完全合韵的。智者：智者：它确是合韵，但没有人愿意被比作“冬日”。询问者：询问者：你不是说过匹克威克先生让你想起圣诞节吗？智者：智者：是的。询问者：询问者：圣诞节是冬天的一个日子，我想匹克威克先生对这个比喻不会介意吧。智者：智者：我认为您不够严谨，“冬日”指的是一般冬天的日子，而不是某个特别的日子，如圣诞节。能满足这样的能满足这样的要求，要求计算机要求，要求计算机不仅能模拟而且可不仅能模拟而且可以延伸、扩展人的以延伸、扩展人的智能，达到甚至超智能，达到甚至超过人类智能的水平，过人类智能的水平，在目前是难以达到在目前是难以达到的！的！人工智能的应用人工智能的应用l减少密集型减少密集型劳动劳动强强度，提高可靠性。度，提高可靠性。l提高自提高自动动化程度，降低化程度，降低对对人人员质员质量，数量的需求，量，数量的需求，降低成本。降低成本。l人工智能技人工智能技术应术应用于机器人，可以代替人用于机器人，可以代替人类类完成完成危危险险的、不适于人来完成的工作。的、不适于人来完成的工作。人工智能的应用人脸识别人工智能的应用人脸识别她是谁她是谁?人工智能的应用机器翻译人工智能的应用机器翻译l翻译句子翻译句子“The spirit is willing but the flesh is weak”l翻译工具翻译工具谷歌在线翻译谷歌在线翻译http:/爱词霸英语翻译爱词霸英语翻译 http:/如何如何实现实现智能？智能？l专家系统专家系统l神经网络神经网络l机器学习机器学习l遗传算法遗传算法l自然语言理解自然语言理解l 等等.二、人工智能的基本原理知识的分类知识的分类l事实事实对客观事物属性的值或状态的描述对客观事物属性的值或状态的描述如：今天很热、我今年如：今天很热、我今年50岁、大海是蓝色的等岁、大海是蓝色的等l规则规则如果如果A则则B如果今天下雨，我就留在家里如果今天下雨，我就留在家里l规律规律同一类现象的本质关系或本质之间的稳定联系同一类现象的本质关系或本质之间的稳定联系 自然规律：水加热后会变成水蒸气自然规律：水加热后会变成水蒸气 知识：是经过提炼加工的信息，是一个或多个信息之知识：是经过提炼加工的信息，是一个或多个信息之间的关联。间的关联。知识的推理方法知识的推理方法l演绎推理演绎推理从一般现象到个别现象的推理从一般现象到个别现象的推理“苏格拉底之死苏格拉底之死”l归纳推理归纳推理从大量个别现象到一般现象的推理从大量个别现象到一般现象的推理金受热后体积膨胀，金受热后体积膨胀，银受热后体积膨胀，银受热后体积膨胀，铜受热后体积膨胀，铜受热后体积膨胀，铁受热后体积膨胀，铁受热后体积膨胀，因此，金属受热后都体积膨胀。，因此，金属受热后都体积膨胀。l类比推理类比推理 从个别现象到个别现象的推理从个别现象到个别现象的推理如汽车：运输如汽车：运输；鱼网：捕鱼；鱼网：捕鱼l知识的表示就是就是对对知知识识的一种描述，或者的一种描述，或者说说是一是一组约组约定，定，一种一种计计算机可以接受的用于描述知算机可以接受的用于描述知识识的数据的数据结结构。构。对对知知识进识进行表示的行表示的过过程就是把知程就是把知识编码识编码成某种成某种数据数据结结构的构的过过程。程。知识的表示方法知识的表示方法l直接表示直接表示计算机对直接表示的信息难以处理。计算机对直接表示的信息难以处理。直接表示难以表示定量信息（语言设计失败）直接表示难以表示定量信息（语言设计失败）直接表示不能描述自然世界的全部信息直接表示不能描述自然世界的全部信息 l逻辑表示：逻辑表示：一阶谓词逻辑是谓词逻辑中最直观的一一阶谓词逻辑是谓词逻辑中最直观的一种逻辑。它以谓词形式来表示动作的主题、客体。种逻辑。它以谓词形式来表示动作的主题、客体。客体可以多个。客体可以多个。如：张三与李四打网球（如：张三与李四打网球（Zhang and Li play tennis），可写为：），可写为：play(Zhang,Li,tennis)这里谓词是这里谓词是play，动词主体是，动词主体是Zhang和和 Li，而客体是，而客体是tennis。l产生式规则表示法产生式规则表示法l语义网络表示法语义网络表示法l如何选择知识表示方法？如何选择知识表示方法？表示知识的范围是否广泛表示知识的范围是否广泛例如，数理例如，数理逻辑逻辑表示是一种广泛的知表示是一种广泛的知识识表示表示办办法，法，如果如果单纯单纯用数字表示，用数字表示，则则范范围围就有限制。就有限制。是否适于推理是否适于推理人工智能只能人工智能只能处处理适合推理的知理适合推理的知识识表示，因此所表示，因此所选选用的知用的知识识表示必表示必须须适合推理。数学模型（拉格朗日插适合推理。数学模型（拉格朗日插值值法）适合推理，普通的数据法）适合推理，普通的数据库库只能供只能供浏览检浏览检索，但不适索，但不适合推理。合推理。是否适于计算机处理是否适于计算机处理计计算机只能算机只能处处理离散的、量化的理离散的、量化的byte字字节节流。因此，流。因此，用文字表述的知用文字表述的知识识和和连续连续形式表示的知形式表示的知识识（如微分方程）（如微分方程）不适合不适合计计算机算机处处理。理。v是否有高效的求解算法是否有高效的求解算法 考考虑虑到到实实用的性能，必用的性能，必须须有高效的求解算法，知有高效的求解算法，知识识表表示才有意示才有意义义。v能否表示不精确知识能否表示不精确知识 自然界的信息具有先天的模糊性和不精确性，能否表自然界的信息具有先天的模糊性和不精确性，能否表示不精确知示不精确知识识也是考也是考虑虑的重要因素的重要因素。v知识和元知识能否用统一的形式表示知识和元知识能否用统一的形式表示 知知识识和元知和元知识识是属于不同是属于不同层层次的知次的知识识，使用，使用统统一的表一的表示方法可以使知示方法可以使知识处识处理理简单简单。三、专家系统原理与产生式规则专家系统知知识识就是力量就是力量,而而积积累了知累了知识识的的计计算机会全面算机会全面增增强强我我们们的力量。的力量。-费费根根鲍鲍姆姆(斯坦福大学教授斯坦福大学教授)一个实例：智能农业专家系统一个实例：智能农业专家系统实例（续）实例（续）专家系统的概念专家系统的概念l什么是专家？l专家系统（ES，Expert System）人类之所以能求解问题，是因为人类具有知识。定定义义l专专家系家系统统是利用大量的是利用大量的领领域域专专家知家知识识，运用知，运用知识识推理方推理方法解决特定法解决特定领领域域实际问题实际问题的的计计算机程序系算机程序系统统。学科代表人物学科代表人物l爱德华爱德华费根鲍姆（费根鲍姆（Edward FeigenbaumEdward Feigenbaum）1968年世界上第一个专家系统DENDRAL问世。用于诊断传染病和提供治疗建议的著名专家系统MYCIN 专家系统的特点l专家系统是一种模拟人类专家解决领域问题的计模拟人类专家解决领域问题的计算机程序系统算机程序系统。具有大量的专门知识与经验根据某领域一个或多个专家提供的知识和经验，进行推理和判断需要解决的问题要足够的复杂专家系统的优点专家系统的优点具体地具体地说说，包括下列几个方面：，包括下列几个方面：(1)专专家系家系统统能能够够高效率、准确、周到、迅速和不知疲倦地高效率、准确、周到、迅速和不知疲倦地进进行工作行工作。(2)专专家系家系统统解决解决实际问题时实际问题时不受周不受周围环围环境的影响境的影响，也，也不可能不可能遗遗漏忘漏忘记记。(3)可以使可以使专专家的家的专长专长不受不受时间时间和空和空间间的限制的限制，以便推广珍，以便推广珍贵贵和稀缺的和稀缺的专专家知家知识识与与经验经验。(4)专专家系家系统统能能汇汇集多集多领领域域专专家的知家的知识识和和经验经验以及他以及他们协们协作作解解决重大决重大问题问题的能力。的能力。第一个商用专家系统：R1l世界上第一个成功的商用世界上第一个成功的商用专专家系家系统统，1982年开始正式在年开始正式在DEC公司使用。公司使用。该该程序帮助程序帮助为为新新计计算机系算机系统统配置配置订单订单；到；到1986年年为为止，估止，估计计它它为为公司每年公司每年节节省了省了4千万美元。千万美元。l在在1991年的海湾危机中，美国年的海湾危机中，美国军队军队使用使用专专家系家系统统用于用于自自动动的后勤的后勤规规划和运划和运输输日程安排。日程安排。这项这项工作同工作同时时涉及涉及到到50000个个车辆车辆、货货物和人，而且必物和人，而且必须须考考虑虑到起点、到起点、目的地、路径以及解决所有参数之目的地、路径以及解决所有参数之间间的冲突。的冲突。AI规规划划技技术术使得一个使得一个计计划可以在几小划可以在几小时时内内产产生，而用旧的方生，而用旧的方法需要花法需要花费费几个星期。几个星期。海湾战争中的专家系统海湾战争中的专家系统专家系统的主要构成l“系统”？l体系结构？知识库知识库结果解释器结果解释器知识推理机知识推理机知识获取器知识获取器人机接口人机接口用户用户 知识工程师知识工程师 领域专家领域专家专家系统的核心部件专家系统的核心部件基于规则的表达方法l规则是什么？规则是什么？IF （条件）（条件）THEN（结论）（结论）l例子：例子：IF（动物有毛发）（动物有毛发）THEN（动物是哺乳动物）（动物是哺乳动物）IF（动物有奶）（动物有奶）THEN（动物是哺乳动物）（动物是哺乳动物）IF（动物有羽毛）（动物有羽毛）THEN（动物是鸟）（动物是鸟）IF（动物会飞）并且（动物会飞）并且（动物会产蛋）（动物会产蛋）THEN（动物是（动物是鸟）鸟）产生式规则表示法l美美国国数数学学家家Post，1943年年提提出出了了一一种种计计算算形形式式体体系系里里所所使使用用的的术术语语。主主要要是是使使用用类类似似文文法法的的规规则则，对对符符号号串做替串做替换换运算。运算。这这就是最早的一个就是最早的一个产产生式系生式系统统。l到到了了60年年代代，产产生生式式系系统统成成为为认认知知心心理理学学研研究究人人类类心心理理活活动动中中信信息息加加工工过过程程的的基基础础，由由此此心心理理学学家家认认为为，人人脑脑对对知知识识的的存存储储就就是是产产生生式式形形式式。因因此此，用用它它来来建建立人立人类认类认知模型。知模型。l到到目目前前为为止止，产产生生式式系系统统已已发发展展成成为为人人工工智智能能系系统统中中最最典典型型最最普普遍遍的的一一种种结结构构。产产生生式式表表示示方方法法是是专专家家系系统统的第一的第一选择选择的知的知识识表达方式。表达方式。产生式规则知识的表示l表示形式表示形式if A then B或表示为或表示为“如果如果A成立则成立则B成立成立”，简化为，简化为AB举例规则规则1：如果如果发动机在抽油而且发动机会旋转发动机在抽油而且发动机会旋转那么那么火花塞有故障火花塞有故障规则规则2：如果如果发动机不旋转而且灯不亮发动机不旋转而且灯不亮那么那么电池或电缆有故障电池或电缆有故障规则规则3：如果如果发动机不旋转而且灯不亮发动机不旋转而且灯不亮那么那么启动马达有故障启动马达有故障规则规则4：如果如果油箱中有油而且化油器中有油油箱中有油而且化油器中有油那么那么发动机在抽油发动机在抽油产生式规则的基本特征产生式规则的基本特征l相同的条件可以得出不同的结论相同的条件可以得出不同的结论如：如：AB，ACl相同的结论可以由不同的条件来得到相同的结论可以由不同的条件来得到如：如：AG，BGl条件之间可是以条件之间可是以“与与”连接和连接和“或或”连接连接如：如：A BG，A BGl一条规则中的结论，可以是另一条规则中的条件一条规则中的结论，可以是另一条规则中的条件如：如：F BZ，C DF产生式规则的两种推理方法产生式规则的两种推理方法n正向推理正向推理n逆向（反向）推理逆向（反向）推理正向推理正向推理l逐条搜索逐条搜索规则库规则库，对对每一条每一条规则规则的前提条件，的前提条件，检查检查事事实库实库中是否存在。前提条件中各子中是否存在。前提条件中各子项项，若在事，若在事实实库库中不是全部存在，放弃中不是全部存在，放弃该该条条规则规则；若在事；若在事实库实库中中全部存在，全部存在，则执则执行行该该条条规则规则，把，把结论结论放入事放入事实库实库中。中。反复循反复循环执环执行上面行上面过过程，直到推出目程，直到推出目标标，并存入事，并存入事实库实库中中为为止。止。正向推理举例正向推理举例ABGCDAEDB，C，E产生式规则库产生式规则库事实库事实库在产生式规则库中有在产生式规则库中有3条规则，在事实库中存在条规则，在事实库中存在B，C，E3个事实，且它们均为真。希望通过正向推理，证明目标个事实，且它们均为真。希望通过正向推理，证明目标G为真。为真。推理过程：搜索每条规则的前提条件是否在事实库中推理过程：搜索每条规则的前提条件是否在事实库中步骤步骤搜索规则搜索规则是否激发该规是否激发该规则则原因原因事实库状态事实库状态1第第1条规则条规则否否A不在事实库不在事实库B，C，E2第第2条规则条规则否否D不在事实库不在事实库B，C，E3第第3条规则条规则是是E在事实库在事实库B，C，E，D4第第1条规则条规则否否A不在事实库不在事实库B，C，E，D5第第2条规则条规则是是C和和D在事实库在事实库B，C，E，A6第第1条规则条规则是是A在事实库在事实库B，C，E，A，G逆向推理逆向推理l逆向推理用得逆向推理用得较较多，主要是目多，主要是目标标明确，推理快。明确，推理快。l逆向推理是从目逆向推理是从目标标开始，开始，寻寻找以此目找以此目标为结论标为结论的的规规则则，并，并对该规则对该规则的前提的前提进进行判断，若行判断，若该规则该规则的前提的前提中某个子中某个子项项是另一是另一规则规则的的结论结论，再找此，再找此结论结论的的规则规则，直到直到对对某个某个规则规则的前提能的前提能够进够进行判断。行判断。逆向推理举例逆向推理举例ABGCDAEDB，C，E产生式规则库产生式规则库事实库事实库步骤步骤规则规则搜索目标搜索目标前提成立前提成立否否原因原因事实库状态事实库状态11G否否A不在事实库不在事实库B，C，E22A否否D不在事实库不在事实库B，C，E33D是是E在事实库在事实库B，C，E，D42A是是C和和D在事实在事实库库B，C，E，D，A51G是是A和和B在事实在事实库库B，C，E，A，G推理过程：搜索每条规则的结论，检查其前提是否在事实库中推理过程：搜索每条规则的结论，检查其前提是否在事实库中根据规则库得到的逆向推理树（知识树）根据规则库得到的逆向推理树（知识树）GABCIJKLMEXFWZPQABCG(IJ)KAXFJLBMECWZMPQE若有知识库为若有知识库为“与或与或”推理树的特点推理树的特点总目标总目标G（结论）（结论）前提前提A（结论）（结论）前提前提B（结论）（结论）前提前提C（结论）（结论）前提前提IJ前提前提K前提前提LME前提前提X 前提前提F前提前提W前提前提Z前提前提P前提前提Q每条规则对应的结点分支有与、或关系每条规则对应的结点分支有与、或关系树的根结点是推理树的总目标树的根结点是推理树的总目标相邻两层之间是一条或多条规则连接相邻两层之间是一条或多条规则连接每个结点可以是单值，也可以是多值。若结点是多值时，各值对应的规则将每个结点可以是单值，也可以是多值。若结点是多值时，各值对应的规则将不同不同可以把所有的叶结点直接放在事实数据库中，也可以安排向用户提问可以把所有的叶结点直接放在事实数据库中，也可以安排向用户提问推理树的深度优先搜索过程推理树的深度优先搜索过程逆向推理过程逆向推理过程GABC IJKLMEXFWZPQYYNNYYY1264578910111235NNYYYY专专家系家系统统的开的开发发l由专家和知识工程师共同配合完成由专家和知识工程师共同配合完成专家：可以不懂计算机，但一定是专家：可以不懂计算机，但一定是某个实际领域经验丰富某个实际领域经验丰富的人的人知识工程师：既知识工程师：既懂计算机懂计算机和和专家系统原理专家系统原理，同时又具有，同时又具有编编程程专家系统能力的人专家系统能力的人l开发途径开发途径直接使用智能程序专用设计语言（如直接使用智能程序专用设计语言（如LISP或或PROLOG）利用专家系统开发工具（如利用专家系统开发工具（如CLIPS：可从：可从http:/clips/download/executables/pc/下载）下载）1 1、专家系统的局限、专家系统的局限l专家系统只是人的经验的汇集专家系统只是人的经验的汇集,因而它存在先天的缺陷因而它存在先天的缺陷,其解也可能未其解也可能未必正确必正确;l专家系统不能由第一原理推理专家系统不能由第一原理推理,不能抓住相似不能抓住相似,缺乏普通的感知缺乏普通的感知,所以所以专家系统不是一个通用的专家专家系统不是一个通用的专家,不是一个问题求解器不是一个问题求解器;l对于复杂系统对于复杂系统,专家系统这种表达知识的方法也很难表达专家系统这种表达知识的方法也很难表达,解就更难解就更难;l专家系统的维护也很不容易专家系统的维护也很不容易,尤其对快速发展的医学和信息领域尤其对快速发展的医学和信息领域,有时有时一年就有一年就有30%的规则要加以改变。的规则要加以改变。2 2、专家系统的适用范围、专家系统的适用范围l在相对窄的知范围和一些定义好的领域能成功应用；在相对窄的知范围和一些定义好的领域能成功应用；l在企业的管理信息系统中专家系统能起到它应有的作用。在企业的管理信息系统中专家系统能起到它应有的作用。专家系统的局限及适用范围专家系统的局限及适用范围四、遗传算法的决策支持遗传算法起源遗传算法起源 l 遗传遗传算法是由美国的算法是由美国的J.Holland教授于教授于1975年年在他的在他的专专著著自然界和人工系自然界和人工系统统的适的适应应性性中首中首先提出的，它是一先提出的，它是一类类借借鉴鉴生物界自然生物界自然选择选择和自然和自然遗传遗传机制的随机化搜索算法机制的随机化搜索算法。遗传学概述l达尔文进化论：达尔文进化论：“物物竞竞天天择择、适者生存、适者生存”l遗传学认为，遗传信息封装在遗传学认为，遗传信息封装在染色体染色体中，并以中，并以基因基因（位）（位）的形式包含在染色体（个体）中。的形式包含在染色体（个体）中。l每个基因有特殊的位置并控制某个特殊的性质。基因杂交每个基因有特殊的位置并控制某个特殊的性质。基因杂交和基因突变能产生对环境适应性强的后代，通过优胜劣汰和基因突变能产生对环境适应性强的后代，通过优胜劣汰的自然选择，的自然选择，适适应值应值高的基因高的基因结结构就保存下来构就保存下来。遗传算法（遗传算法（Genetic Algorithm,GA）l遗传算法模拟自然界中的生命进化机制，遗传算法模拟自然界中的生命进化机制，是具有是具有“生存检生存检测测”的迭代过程的搜索算法的迭代过程的搜索算法 l遗传算法尤其适用于传统方法难以实现的遗传算法尤其适用于传统方法难以实现的最优化问题求解最优化问题求解实实践践证证明，明，遗传遗传算法已算法已经经在求解旅行商在求解旅行商问题问题、背包、背包问题问题、装箱、装箱问题问题、布局、布局优优化、网化、网络络路由等具有路由等具有NP难难度的度的组组合合优优化化问题问题上取上取得了成功的得了成功的应应用。用。l在人工智能研究中，人们认为在人工智能研究中，人们认为“遗传算法、自适应系统、细遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术算技术有重大影响的关键技术”。生物进化与遗传算法生物进化与遗传算法群体群体种群种群子群子群选择选择婚配婚配变异变异遭淘汰遭淘汰的群体的群体生物进化与遗传算法之间的对应关系生物进化与遗传算法之间的对应关系生物进化中的概念生物进化中的概念遗传算法中的作用遗传算法中的作用环境环境适应函数适应函数适应性适应性适应函数值适应函数值适者生存适者生存适应函数值最大的解被保留的概率最大适应函数值最大的解被保留的概率最大个体个体问题的一个解问题的一个解染色体染色体解的编码解的编码基因基因编码的元素编码的元素群体群体被选定的一组解被选定的一组解种群种群根据适应函数选择的一组解根据适应函数选择的一组解交配交配以一定的方式由双亲产生后代的过程以一定的方式由双亲产生后代的过程变异变异编码的某些分量发生变化的过程编码的某些分量发生变化的过程遗传算法的工作示意图实际问题参数集实际问题参数集三个基本算子三个基本算子选择选择交叉交叉变异变异编码成位串形式编码成位串形式种群种群1计算适应函数值计算适应函数值选择和遗传选择和遗传统计结果统计结果种群种群2经过优化的一个或多个参数集经过优化的一个或多个参数集改善或解决实际问题改善或解决实际问题不满足要求遗传算法的三个主要操作l选择：选择：选出繁殖后代的个体选出繁殖后代的个体轮盘赌法轮盘赌法期望值法期望值法最佳个体保存法最佳个体保存法其它其它l交叉：交叉：互换染色体，从而产生新的染色体互换染色体，从而产生新的染色体一点交叉、二点交叉、多点交叉一点交叉、二点交叉、多点交叉l变异变异：以很小的概率，随机地改变字符串某个位：以很小的概率，随机地改变字符串某个位置的值置的值染色体的选择染色体的选择l“轮盘赌轮盘赌”法法：每个个体的选择概率和其适应值：每个个体的选择概率和其适应值成比例，个体适应值越大，其被选择的概率就越成比例，个体适应值越大，其被选择的概率就越高。高。x1x2x3x4x5x6设群体大小为设群体大小为n，其中个体，其中个体i的的的的适应度值为适应度值为fi，则，则i被选择的概率被选择的概率Pi为：为：染色体的选择染色体的选择l期望值方法：计算群体中每个个体在下一代生存期望值方法：计算群体中每个个体在下一代生存的期望数目，即的期望数目，即若某个体被选中并要参与配对和交叉，则它在下一若某个体被选中并要参与配对和交叉，则它在下一代中的生存的期望数目减去代中的生存的期望数目减去0.50.5；若不参与配对和交叉，；若不参与配对和交叉，则该个体的生存期望数目减去则该个体的生存期望数目减去1 1。因此，。因此，若一个个体的若一个个体的期望值小于零，则该个体不参与选择期望值小于零，则该个体不参与选择。l被被选择选择次数的期望次数的期望值值对于规模为对于规模为N的群体，一个选择概率为的群体，一个选择概率为p(xi)的染色的染色体体xi被选择次数的期望值被选择次数的期望值e(xi)：对于群体中的每一个对于群体中的每一个xi，首先选择，首先选择 次。这样次。这样共得到共得到 个染色体。然后按照个染色体。然后按照 从从大到小对染色体排序，依次取出大到小对染色体排序，依次取出 个染个染色体，这样就得到了色体，这样就得到了N个染色体。个染色体。染色体的选择染色体的选择染色体交叉染色体交叉l交叉发生在两个染色体之间，由两个被称之为双亲的父代交叉发生在两个染色体之间，由两个被称之为双亲的父代染色体，经杂交以后，产生两个具有双亲的部分基因的新染色体，经杂交以后，产生两个具有双亲的部分基因的新的染色体。当染色体采用二进制形式编码时，交叉过程是的染色体。当染色体采用二进制形式编码时，交叉过程是以这样一种形式进行的：以这样一种形式进行的：a1 a2 .ai ai+1 .anb1 b2 .bi bi+1 .bna1 a2 .ai bi+1 .bnb1 b2 .bi ai+1 .an交叉前交叉前交叉后交叉后交叉位置交叉位置变异变异l变异发生在染色体的某一个基因上，当以二进制编码时，变异发生在染色体的某一个基因上，当以二进制编码时，变异的基因由变异的基因由0变成变成1，或者由，或者由1变成变成0。如对于染色体。如对于染色体x=11001，如果变异位发生在第三位，则变异后的染色体，如果变异位发生在第三位，则变异后的染色体变成了变成了y=11101。例：求函数的最大值例：求函数的最大值其中其中x为为0,31间的整数间的整数 编码：采用二进制形式编码编码：采用二进制形式编码 由于由于x的定义域是的定义域是0,31间的整数，刚好可以用间的整数，刚好可以用5位二进制数表位二进制数表示，因此可以用示，因此可以用5位二进制数表示该问题的解，即染色体。如位二进制数表示该问题的解，即染色体。如00000表示表示x0，10101表示表示x21，11111表示表示x31等等 l适应函数：适应函数：直接使用函数直接使用函数f(x)作为适应函数。作为适应函数。l假设群体的规模假设群体的规模N4，交配概率，交配概率pc100，变异概，变异概率率pm1。l设随机生成的初始群体为：设随机生成的初始群体为：01101，11000，01000，10011染色体的选择方法：轮盘赌法染色体的选择方法：轮盘赌法序号序号群体群体适应值适应值选择概率（）选择概率（）选中次数选中次数10110116914.44121100057649.23230100064 5.47041001136130.851第第0代情况表代情况表 序号序号种群种群交配对像交配对像交配位交配位（随机选择）（随机选择）子代子代适应值适应值1011012401100144211000141100162531100042110117294100113210000256第第0代种群的交叉情况代种群的交叉情况 序号种群交配对像交配位子代适应值1110112311001625211101131111196131000042100012894110113211010676第第2代种群的交配情况代种群的交配情况 序号序号群体群体适应值适应值选择概率（）选择概率（）选中次数选中次数101100144 8.21021100162535.62131101172941.56241000025614.601第第1代情况表代情况表 序号序号种群种群交配对象交配对象交配位交配位（随机选择）（随机选择）子代子代适应值适应值1110012311011729211011131100162531101141100002564100003111011729第第1代种群的交配情况代种群的交配情况 l由于选择的变异概率由于选择的变异概率Pm=0.001，则平均每，则平均每1000位中才有一位中才有一位变异，由位变异，由4个位串组成的种群中共有个位串组成的种群中共有4520位，则变异位，则变异的期望值为的期望值为200.0010.02位。事实上在该例中没有变异发位。事实上在该例中没有变异发生。生。l对比对比1,2，3代的结果，可以看出，代的结果，可以看出，每一代的平均值及最大值每一代的平均值及最大值都比前一代有了很大提高都比前一代有了很大提高，说明种群正朝优化的方向前进，说明种群正朝优化的方向前进最大适应值、平均适应值进化曲线最大适应值、平均适应值进化曲线 遗传算法的应用遗传算法的应用l遗传算法是多学科结合与渗透的产物。目前遗传遗传算法是多学科结合与渗透的产物。目前遗传算法所涉及的主要领域有自动控制、规划设计、算法所涉及的主要领域有自动控制、规划设计、组合优化、图象处理、信号处理、人工生命等。组合优化、图象处理、信号处理、人工生命等。课堂练习课堂练习l请用请用“抛硬币抛硬币”的方式，随机生成初始种群，求解的方式，随机生成初始种群，求解函数函数F(x)=x2的最大值（其它条件与例题相同）的最大值（其它条件与例题相同）l在确定种群的交配对象和染色体交换位置时，也请在确定种群的交配对象和染色体交换位置时，也请“抛硬币抛硬币”来决定。来决定。一个遗传算法的应用实例l下表是一个客下表是一个客户户的信息的信息组组成数据表，可以利用成数据表，可以利用遗传遗传算法在客算法在客户户群中群中预测预测最最佳客佳客户户的的类类型。企型。企业业的最佳客的最佳客户户群，即可以从客群，即可以从客户处获户处获取最大利取最大利润润的特征的特征应该应该由客由客户户的收入水平、客的收入水平、客户户的家庭人口、客的家庭人口、客户户的年的年龄龄所构成。而从客所构成。而从客户户处处所所获获取的利取的利润则润则是从客是从客户户的累的累计购买计购买商品金商品金额额乘以乘以2%，减去每次，减去每次购买购买商品的手商品的手续费续费10元。元。客户客户ID年龄年龄累计购买金额累计购买金额收入收入家庭人口家庭人口性别性别10985461843中等中等4女女18595490中等中等2男男47382613628低低5男男749123618463高高6女女95623298463高高3男男8552632274中等中等2男男58753521846低低2女女64957480中等中等3女女769572721634高高5男男6583945842低低1女女遗传编码的定义l根据客户数据中的条件，可用如下八个染色体来定义客户类型基因1：客户的年龄下限基因2：客户的年龄上限基因3：高收入基因4：中等收入基因5：低收入基因6：家庭人口少（12人）基因7：家庭人口一般（34人）基因8：家庭人口多（5人以上）附表：客户群的新基因组成年龄年龄上限上限年龄年龄下限下限高收高收入入中等中等收入收入低收低收入入人口人口少少人口人口一般一般人口人口多多客户客户群群13864是是是是否否否否是是是是客户客户群群22650是是否否是是是是否否是是客户客户群群32040否否是是是是是是否否否否在对这些染色体进行遗传计算时，通常要将染色体的在对这些染色体进行遗传计算时，通常要将染色体的等位基因转换成二进制数，如，用等位基因转换成二进制数，如，用“1”表示表示“是是”，“0”表示表示“否否”l环境适应函数环境适应函数客客户户群的群的购买购买收益扣除手收益扣除手续费续费限制条件：客限制条件：客户户的年的年龄龄下限必下限必须须小于年小于年龄龄上限上限l由于适应性函数是从利润角度定义的，群体的进由于适应性函数是从利润角度定义的，群体的进化应该逐渐收敛于客户收益最大的客户特征群化应该逐渐收敛于客户收益最大的客户特征群本章内容回顾本章内容回顾l人工智能的基本原理人工智能的基本原理l专专家系家系统统原理与原理与产产生式生式规则规则的推理方法的推理方法l遗传遗传算法的原理及算法的原理及应应用用本章作业本章作业R1：A B CGR2：D EAR3：FBR4：H PCR5：QE问题：问题：1.请根据该知识库的规则画出推理树。请根据该知识库的规则画出推理树。2.若用户对结点若用户对结点D，Q，F，P的回答为的回答为Yes，对结点，对结点H的回答为的回答为No，那么根据推理树，可以推出根结点为，那么根据推理树，可以推出根结点为Yes吗？请给出正吗？请给出正向推理和反向推理的过程。向推理和反向推理的过程。The End.什么是专家？l与领域相关l有丰富知识：对该领域的事物精通，有丰富的知识或者说有独到的见解l能进行判断：对该领域的复杂问题能进行独到明确的判断返回l1936年生于美国新泽西州l1952年进入卡耐基梅隆大学电气工程系学习，师从西蒙，获博士学位l1965在斯坦福大学发明世界上第一个专家系统DENDRALl1977年在IJCAI上在世界上第一次提出知识工程的概念。l现为SKL教授返回知识库知识库l知识库是用来存放领域专家知识的仓库。其中的知识来源于知识获取器，并为推理器提供求解问题所需要的知识。l主要涉及的问题：知识表达问题知识管理问题知识库知识库返回推理机推理机l推理机是模拟人类专家的思维过程，控制并执行对问题的推理机是模拟人类专家的思维过程，控制并执行对问题的求解。它能根据已知的事实，利用知识库中的知识，按照求解。它能根据已知的事实，利用知识库中的知识，按照一定的推理方法和控制策略进行推理，直到得出相应的结一定的推理方法和控制策略进行推理，直到得出相应的结论为止论为止l主要研究问题：主要研究问题：推理方法：精确推理方法：精确/非精确非精确控制策略：推理方向控制策略：推理方向/规则规则搜索策略搜索策略返回知识获取知识获取l知识获取是建设专家系统的关键。没有知识的专家系统就是知识获取是建设专家系统的关键。没有知识的专家系统就是一个空壳，不能起任何作用。一个空壳，不能起任何作用。l知识获取的任务知识获取的任务抽取知识、知识的转换、输入、检测抽取知识、知识的转换、输入、检测l知识获取方式知识获取方式非自动知识获取非自动知识获取l与领域专家交流，提取专家的经验知识与领域专家交流，提取专家的经验知识l查阅文献，获得有关概念的描述及参数查阅文献，获得有关概念的描述及参数l对知识进行分析，比较，归纳，整理，找出知识的内在联系及对知识进行分析，比较，归纳，整理，找出知识的内在联系及规律规律l将整理出的知识交专家审查将整理出的知识交专家审查l把确定下来的知识用知识表示模式表示出来把确定下来的知识用知识表示模式表示出来自动知识获取自动知识获取l具有识别语音，文字和图像的能力具有识别语音，文字和图像的能力l具有理解，分析，归纳的能力具有理解，分析，归纳的能力l具有从运行实践中学习的能力具有从运行实践中学习的能力返回结果解释器结果解释器l“为什么呀？为什么呀？”-2008年的流行语年的流行语l人们在涉及重大决策的时候，一般不会满足于结论，还关人们在涉及重大决策的时候，一般不会满足于结论，还关心得出这个结论的原因。心得出这个结论的原因。l解释器的任务就是跟踪推理器的推理过程，并展示给用户。解释器的任务就是跟踪推理器的推理过程，并展示给用户。返回序号序号群体群体适应值适应值选择概率（）选择概率（）选中次数选中次数10110116914.44121100057649.23230100064 5.47041001136130.851计算个体被选择次数的期望值计算个体被选择次数的期望值e(xi)：计算式为：计算式为：e(x1)：0.144440.5776，向下取整得，向下取整得0e(x2)：0.492341.9692，向下取整得，向下取整得1e(x3)：0.054740.2188，向下取整得，向下取整得0e(x4)：0.308541.234，向下取整得，向下取整得1所以，所以，共得到共得到 2个染色体。个染色体。然后按照然后按照 从大到小对染色体排序：从大到小对染色体排序：0.57760.96920.21880.234因此，各群体被选择的次数如上表所示。因此，各群体被选择的次数如上表所示。返回