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

《第8章：人工智能与专家系统.ppt》由会员分享，可在线阅读，更多相关《第8章：人工智能与专家系统.ppt（92页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第8章人工智能与专家系统Nothing is impossible for a willing heart.心之所愿，无所不成。心之所愿，无所不成。本章主要内容本章主要内容l人工智能的基本原理人工智能的基本原理l专家系统原理与产生式规则专家系统专家系统原理与产生式规则专家系统l遗传算法的决策支持遗传算法的决策支持一、人工智能的基本原理什么是智能?l请说出请说出3 3种你身边或你所知道的智能化事物种你身边或你所知道的智能化事物什么是智能?l智能（Intelligence)即智力功能，是人类大脑所具有的感知、认识、学习、理解、分析、综合、判断、推理、创造等局部功能的总和与它们的有机综合的统称；因此

2、，完善的智能中还应包完善的智能中还应包含有人类的情感、意识、意志等这种高级因素含有人类的情感、意识、意志等这种高级因素。计算机与智能计算机与智能l例子：IBM超级计算机l通常我们用计算机，不仅要告诉计算机，要做什么，还必须通常我们用计算机，不仅要告诉计算机，要做什么，还必须详细地、正确地告诉计算机怎么做。也就是说，人们要根据详细地、正确地告诉计算机怎么做。也就是说，人们要根据任务的要求，以适当的计算机语言，编制针对该任务的应用任务的要求，以适当的计算机语言，编制针对该任务的应用程序，才能应用计算机完成此项任务。这样实际上是人完全程序，才能应用计算机完成此项任务。这样实际上是人完全控制计算机完成

3、的，是谈不上计算机有真正的控制计算机完成的，是谈不上计算机有真正的“智能智能”。一个例子-IBM超级计算机“深蓝”l19971997年年5 5月月1111日，世界国际象棋棋王卡斯帕罗夫与美国日，世界国际象棋棋王卡斯帕罗夫与美国IBMIBM公公司的司的RSRS60006000（深蓝）计算机系统进行了六局深蓝）计算机系统进行了六局“人机大战人机大战”，结果，结果“深蓝深蓝”以以3.53.5比比2.52.5的总比分获胜。的总比分获胜。一个例子-IBM超级计算机“沃森”l20112011年，年，IBMIBM超级计算机超级计算机WatsonWatson在在危险边缘危险边缘竞赛节目中竞赛节目中击败了该节目

4、历史上最成功的两位人类选手，继击败了该节目历史上最成功的两位人类选手，继“深蓝深蓝”之之后，聪明的人脑再一次败给了智慧程序。后，聪明的人脑再一次败给了智慧程序。l视频视频 http:/ Intelligence)？l就是研究怎样让计算机做一些通常认为就是研究怎样让计算机做一些通常认为需要智能才能做的需要智能才能做的事情事情，又称机器智能。，又称机器智能。l虽然是计算机科学的一个分支，但并不只涉及到计算机科虽然是计算机科学的一个分支，但并不只涉及到计算机科学，而且还涉及到学，而且还涉及到脑科学、神经生理学、心理学、语言学、脑科学、神经生理学、心理学、语言学、逻辑学、认知（思维）科学、行为科学和数

5、学以及信息论、逻辑学、认知（思维）科学、行为科学和数学以及信息论、控制论和系统论控制论和系统论等许多学科领域。等许多学科领域。21世纪三大尖端技术世纪三大尖端技术 n基因工程基因工程n纳米科学纳米科学n人工智能人工智能 关于人工智能问题l是一个是一个古老的但又十分新颖古老的但又十分新颖的研究课题的研究课题l各国在人工智能的研究上都已经获得巨大的进展各国在人工智能的研究上都已经获得巨大的进展l各种传统的或新颖的智能模型迄今还各种传统的或新颖的智能模型迄今还不能完全而圆满地对不能完全而圆满地对大脑思维活动的过程进行解释和模拟大脑思维活动的过程进行解释和模拟人们还不十分了解信息在大脑中的底层结构和编

6、码方法；人们还不十分了解信息在大脑中的底层结构和编码方法；象人们的概念、意识、情感和创造性思维过程等，还根本无象人们的概念、意识、情感和创造性思维过程等，还根本无从着手；从着手；l在哲学上、自然科学以及社会学科上在哲学上、自然科学以及社会学科上还有很大的争论还有很大的争论，还，还不能得到一致认同。不能得到一致认同。谷歌无人驾驶汽车谷歌无人驾驶汽车 内华达州是美国对公共道路无人驾驶立法的第一个州。截至内华达州是美国对公共道路无人驾驶立法的第一个州。截至2012年年6月，谷歌的无人驾驶汽车已经在该州行进了月，谷歌的无人驾驶汽车已经在该州行进了25万英里。万英里。谷歌无人驾驶汽车的构造示意图及其描绘

7、的谷歌无人驾驶汽车的构造示意图及其描绘的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如果说现在有一台电脑，其运算速度非常快、记亿容量和如果说现在有一台电脑，其运

8、算速度非常快、记亿容量和逻揖单元的数目也超过了人脑，而且还为这台电脑编写了逻揖单元的数目也超过了人脑，而且还为这台电脑编写了许多智能化的程序，并提供了合适种类的大量数据，使这许多智能化的程序，并提供了合适种类的大量数据，使这台电脑能够做一些人性化的事情，如简单地听或说。回答台电脑能够做一些人性化的事情，如简单地听或说。回答某些问题等。那么，我们是否就能说这台机器具有思维能某些问题等。那么，我们是否就能说这台机器具有思维能力了呢力了呢?或者说，或者说，我们怎样才能判断一台机器是否具存了我们怎样才能判断一台机器是否具存了思维能力呢思维能力呢?l19501950年英国数学家图灵（年英国数学家图灵（A

9、.M.Turing,19121954A.M.Turing,19121954）发表发表了了”计算机与智能计算机与智能”的论文中提出的论文中提出著名的著名的“图灵测试图灵测试”，形象地形象地提出人工智能应该达到的智能标准提出人工智能应该达到的智能标准。图灵测试图灵测试l即一个人在不接触对方的情况下，通过一种特殊的方式，和即一个人在不接触对方的情况下，通过一种特殊的方式，和对方进行一系列的问答，对方进行一系列的问答，如果在相当长时间内，如果在相当长时间内，他无法根据他无法根据这些问题判断对方是人还是计算机，那么，就可以认为这个这些问题判断对方是人还是计算机，那么，就可以认为这个计算计算机机具有同人相

10、当的智力具有同人相当的智力，即这台计算机是，即这台计算机是能思维的能思维的。如果由你来提问，你会问哪些问题呢？如果由你来提问，你会问哪些问题呢？图灵测试示范性问题图灵测试示范性问题问：问：请给我写出有关“第四号桥”主题的十四行诗。答：答：不要问我这道题，我从来不会写诗。问：问：34957加70764等于多少？答：答：（停30秒后）105721问：问：你会下国际象棋吗？答：答：是的。问：问：我在我的K1处有棋子K；你仅在K6处有棋子K，在R1处有棋子R。现在轮到你走，你应该下那步棋？答：答：（停15秒钟后）棋子R走到R8处，将军！可以通过编制可以通过编制特殊的程序来特殊的程序来实现。实现。l从表

11、面上看，要使机器回答按一定范围提出的问题似乎没从表面上看，要使机器回答按一定范围提出的问题似乎没有什么困难，可以通过编制特殊的程序来实现。然而，如有什么困难，可以通过编制特殊的程序来实现。然而，如果提问者并不遵循常规标准，编制回答的程序是极其困难果提问者并不遵循常规标准，编制回答的程序是极其困难的事情。的事情。图灵测试的示范性问题不按常规的提问图灵测试的示范性问题不按常规的提问(1)l问：问：你会下国际象棋吗？答：答：是的。问：问：你会下国际象棋吗？答：答：是的。问：问：请再次回答，你会下国际象棋吗？答：答：是的。你多半会想你多半会想到，面前的到，面前的这位是一部这位是一部笨机器笨机器!l问：

12、问：你会下国际象棋吗？答：答：是的。问：问：你会下国际象棋吗？答：答：是的，我不是已经说过了吗？问：问：请再次回答，你会下国际象棋吗？答：答：你烦不烦，干嘛老提同样的问题。图灵测试的示范性问题不按常规的提问图灵测试的示范性问题不按常规的提问(2)那么，你面那么，你面前的这位，前的这位，大概是人而大概是人而不是机器不是机器!“图灵梦想”的对话l在这段对话中“询问者询问者”代表人代表人，“智者智者”代表机器代表机器，并且假定他们都读过狄更斯（C.Dickens）的著名小说匹克威克外传，对话内容如下：询问者：询问者：在14行诗的首行是“你如同夏日”，你不觉得“春日”更好吗？智者：智者：它不合韵。询问

13、者：询问者：“冬日”如何？它可完全合韵的。智者：智者：它确是合韵，但没有人愿意被比作“冬日”。询问者：询问者：你不是说过匹克威克先生让你想起圣诞节吗？智者：智者：是的。询问者：询问者：圣诞节是冬天的一个日子，我想匹克威克先生对这个比喻不会介意吧。智者：智者：我认为您不够严谨，“冬日”指的是一般冬天的日子，而不是某个特别的日子，如圣诞节。能满足这样的能满足这样的要求，要求计算机要求，要求计算机不仅能模拟而且可不仅能模拟而且可以延伸、扩展人的以延伸、扩展人的智能，达到甚至超智能，达到甚至超过人类智能的水平，过人类智能的水平，在目前是难以达到在目前是难以达到的！的！人工智能的应用人工智能的应用l减少

14、密集型劳动强度，提高可靠性。减少密集型劳动强度，提高可靠性。l提高自动化程度，降低对人员质量，数量的需求，提高自动化程度，降低对人员质量，数量的需求，降低成本。降低成本。l人工智能技术应用于机器人，可以代替人类完成人工智能技术应用于机器人，可以代替人类完成危险的、不适于人来完成的工作。危险的、不适于人来完成的工作。人工智能的应用人脸识别人工智能的应用人脸识别她是谁她是谁?人工智能的应用机器翻译人工智能的应用机器翻译l翻译句子翻译句子“The spirit is willing but the flesh is weak”l翻译工具翻译工具谷歌在线翻译谷歌在线翻译http:/ http:/ 等等

15、.二、人工智能的基本原理知识的分类知识的分类l事实事实对客观事物属性的值或状态的描述对客观事物属性的值或状态的描述如：今天很热、我今年如：今天很热、我今年50岁、大海是蓝色的等岁、大海是蓝色的等l规则规则如果如果A则则B如果今天下雨，我就留在家里如果今天下雨，我就留在家里l规律规律同一类现象的本质关系或本质之间的稳定联系同一类现象的本质关系或本质之间的稳定联系 自然规律：水加热后会变成水蒸气自然规律：水加热后会变成水蒸气 知识：是经过提炼加工的信息，是一个或多个信息之知识：是经过提炼加工的信息，是一个或多个信息之间的关联。间的关联。知识的推理方法知识的推理方法l演绎推理演绎推理从一般现象到个别

16、现象的推理从一般现象到个别现象的推理“苏格拉底之死苏格拉底之死”l归纳推理归纳推理从大量个别现象到一般现象的推理从大量个别现象到一般现象的推理金受热后体积膨胀，金受热后体积膨胀，银受热后体积膨胀，银受热后体积膨胀，铜受热后体积膨胀，铜受热后体积膨胀，铁受热后体积膨胀，铁受热后体积膨胀，因此，金属受热后都体积膨胀。，因此，金属受热后都体积膨胀。l类比推理类比推理 从个别现象到个别现象的推理从个别现象到个别现象的推理如汽车：运输如汽车：运输；鱼网：捕鱼；鱼网：捕鱼l知识的表示就是对知识的一种描述，或者说是一组约定，就是对知识的一种描述，或者说是一组约定，一种计算机可以接受的用于描述知识的数据结一种

17、计算机可以接受的用于描述知识的数据结构。构。对知识进行表示的过程就是把知识编码成某种对知识进行表示的过程就是把知识编码成某种数据结构的过程。数据结构的过程。知识的表示方法知识的表示方法l直接表示直接表示计算机对直接表示的信息难以处理。计算机对直接表示的信息难以处理。直接表示难以表示定量信息（语言设计失败）直接表示难以表示定量信息（语言设计失败）直接表示不能描述自然世界的全部信息直接表示不能描述自然世界的全部信息 l逻辑表示：逻辑表示：一阶谓词逻辑是谓词逻辑中最直观的一一阶谓词逻辑是谓词逻辑中最直观的一种逻辑。它以谓词形式来表示动作的主题、客体。种逻辑。它以谓词形式来表示动作的主题、客体。客体可

18、以多个。客体可以多个。如：张三与李四打网球（如：张三与李四打网球（Zhang and Li play tennis），可写为：），可写为：play(Zhang,Li,tennis)这里谓词是这里谓词是play，动词主体是，动词主体是Zhang和和 Li，而客体是，而客体是tennis。l产生式规则表示法产生式规则表示法l语义网络表示法语义网络表示法l如何选择知识表示方法？如何选择知识表示方法？表示知识的范围是否广泛表示知识的范围是否广泛例如，数理逻辑表示是一种广泛的知识表示办法，例如，数理逻辑表示是一种广泛的知识表示办法，如果单纯用数字表示，则范围就有限制。如果单纯用数字表示，则范围就有限制。

19、是否适于推理是否适于推理人工智能只能处理适合推理的知识表示，因此所选人工智能只能处理适合推理的知识表示，因此所选用的知识表示必须适合推理。数学模型（拉格朗日插值用的知识表示必须适合推理。数学模型（拉格朗日插值法）适合推理，普通的数据库只能供浏览检索，但不适法）适合推理，普通的数据库只能供浏览检索，但不适合推理。合推理。是否适于计算机处理是否适于计算机处理计算机只能处理离散的、量化的计算机只能处理离散的、量化的bytebyte字节流。因此，字节流。因此，用文字表述的知识和连续形式表示的知识（如微分方程）用文字表述的知识和连续形式表示的知识（如微分方程）不适合计算机处理。不适合计算机处理。v是否有

20、高效的求解算法是否有高效的求解算法 考虑到实用的性能，必须有高效的求解算法，知识表考虑到实用的性能，必须有高效的求解算法，知识表示才有意义。示才有意义。v能否表示不精确知识能否表示不精确知识 自然界的信息具有先天的模糊性和不精确性，能否表自然界的信息具有先天的模糊性和不精确性，能否表示不精确知识也是考虑的重要因素示不精确知识也是考虑的重要因素。v知识和元知识能否用统一的形式表示知识和元知识能否用统一的形式表示 知识和元知识是属于不同层次的知识，使用统一的表知识和元知识是属于不同层次的知识，使用统一的表示方法可以使知识处理简单。示方法可以使知识处理简单。三、专家系统原理与产生式规则专家系统知识就

21、是力量知识就是力量,而积累了知识的计算机会全而积累了知识的计算机会全面增强我们的力量。面增强我们的力量。-费根鲍姆费根鲍姆(斯坦福大学教授斯坦福大学教授)一个实例：智能农业专家系统一个实例：智能农业专家系统实例（续）实例（续）专家系统的概念专家系统的概念l什么是专家？l专家系统（ES，Expert System）人类之所以能求解问题，是因为人类具有知识。定义定义l专家系统是利用大量的领域专家知识，运用知识推理方专家系统是利用大量的领域专家知识，运用知识推理方法解决特定领域实际问题的计算机程序系统。法解决特定领域实际问题的计算机程序系统。学科代表人物学科代表人物l爱德华爱德华费根鲍姆（费根鲍姆（

22、Edward Edward FeigenbaumFeigenbaum）1968年世界上第一个专家系统DENDRAL问世。用于诊断传染病和提供治疗建议的著名专家系统MYCIN 专家系统的特点l专家系统是一种模拟人类专家解决领域问题的计模拟人类专家解决领域问题的计算机程序系统算机程序系统。具有大量的专门知识与经验根据某领域一个或多个专家提供的知识和经验，进行推理和判断需要解决的问题要足够的复杂专家系统的优点专家系统的优点具体地说，包括下列几个方面：具体地说，包括下列几个方面：(1)(1)专家系统能够专家系统能够高效率、准确、周到、迅速和不知疲倦地进高效率、准确、周到、迅速和不知疲倦地进行工作行工作

23、。(2)(2)专家系统解决实际问题时专家系统解决实际问题时不受周围环境的影响不受周围环境的影响，也，也不可能不可能遗漏忘记遗漏忘记。(3)(3)可以使专家的专长可以使专家的专长不受时间和空间的限制不受时间和空间的限制，以便推广珍贵，以便推广珍贵和稀缺的专家知识与经验。和稀缺的专家知识与经验。(4)(4)专家系统能汇集多领域专家的知识和经验以及他们协作专家系统能汇集多领域专家的知识和经验以及他们协作解解决重大问题决重大问题的能力。的能力。第一个商用专家系统：R1l世界上第一个成功的商用专家系统，世界上第一个成功的商用专家系统，19821982年开始正式在年开始正式在DECDEC公司使用。该程序帮

24、助为新计算机系统配置订单；到公司使用。该程序帮助为新计算机系统配置订单；到19861986年为止，估计它为公司每年节省了年为止，估计它为公司每年节省了4 4千万美元。千万美元。l在在19911991年的海湾危机中，美国军队使用专家系统用于年的海湾危机中，美国军队使用专家系统用于自动的后勤规划和运输日程安排。这项工作同时涉及自动的后勤规划和运输日程安排。这项工作同时涉及到到5000050000个车辆、货物和人，而且必须考虑到起点、目个车辆、货物和人，而且必须考虑到起点、目的地、路径以及解决所有参数之间的冲突。的地、路径以及解决所有参数之间的冲突。AIAI规划技规划技术使得一个计划可以在几小时内产

25、生，而用旧的方法术使得一个计划可以在几小时内产生，而用旧的方法需要花费几个星期。需要花费几个星期。海湾战争中的专家系统海湾战争中的专家系统专家系统的主要构成l“系统”？l体系结构？知识库知识库结果解释器结果解释器知识推理机知识推理机知识获取器知识获取器人机接口人机接口用户用户 知识工程师知识工程师 领域专家领域专家专家系统的核心部件专家系统的核心部件4.2.3基于规则的表达方法l规则是什么？规则是什么？IF （条件）（条件）THEN（结论）（结论）l例子：例子：IF（动物有毛发）（动物有毛发）THEN（动物是哺乳动物）（动物是哺乳动物）IF（动物有奶）（动物有奶）THEN（动物是哺乳动物）（动

26、物是哺乳动物）IF（动物有羽毛）（动物有羽毛）THEN（动物是鸟）（动物是鸟）IF（动物会飞）并且（动物会飞）并且（动物会产蛋）（动物会产蛋）THEN（动物是（动物是鸟）鸟）产生式规则表示法l美美国国数数学学家家PostPost，19431943年年提提出出了了一一种种计计算算形形式式体体系系里里所所使使用用的的术术语语。主主要要是是使使用用类类似似文文法法的的规规则则，对对符符号号串做替换运算。这就是最早的一个产生式系统。串做替换运算。这就是最早的一个产生式系统。l到到了了6060年年代代，产产生生式式系系统统成成为为认认知知心心理理学学研研究究人人类类心心理理活活动动中中信信息息加加工工过

27、过程程的的基基础础，由由此此心心理理学学家家认认为为，人人脑脑对对知知识识的的存存储储就就是是产产生生式式形形式式。因因此此，用用它它来来建建立人类认知模型。立人类认知模型。l到到目目前前为为止止，产产生生式式系系统统已已发发展展成成为为人人工工智智能能系系统统中中最最典典型型最最普普遍遍的的一一种种结结构构。产产生生式式表表示示方方法法是是专专家家系系统的第一选择的知识表达方式。统的第一选择的知识表达方式。产生式规则知识的表示l表示形式表示形式if A then B或表示为或表示为“如果如果A成立则成立则B成立成立”，简化为，简化为AB举例规则规则1：如果如果发动机在抽油而且发动机会旋转发动

28、机在抽油而且发动机会旋转那么那么火花塞有故障火花塞有故障规则规则2：如果如果发动机不旋转而且灯不亮发动机不旋转而且灯不亮那么那么电池或电缆有故障电池或电缆有故障规则规则3：如果如果发动机不旋转而且灯不亮发动机不旋转而且灯不亮那么那么启动马达有故障启动马达有故障规则规则4：如果如果油箱中有油而且化油器中有油油箱中有油而且化油器中有油那么那么发动机在抽油发动机在抽油产生式规则的基本特征产生式规则的基本特征l相同的条件可以得出不同的结论相同的条件可以得出不同的结论如：如：AB，ACl相同的结论可以由不同的条件来得到相同的结论可以由不同的条件来得到如：如：AG，BGl条件之间可是以条件之间可是以“与与

29、”连接和连接和“或或”连接连接如：如：A BG，A BGl一条规则中的结论，可以是另一条规则中的条件一条规则中的结论，可以是另一条规则中的条件如：如：F BZ，C DF产生式规则的两种推理方法产生式规则的两种推理方法n正向推理正向推理n逆向（反向）推理逆向（反向）推理正向推理正向推理l逐条搜索规则库，对每一条规则的前提条件，检查逐条搜索规则库，对每一条规则的前提条件，检查事实库中是否存在。前提条件中各子项，若在事实事实库中是否存在。前提条件中各子项，若在事实库中不是全部存在，放弃该条规则；若在事实库中库中不是全部存在，放弃该条规则；若在事实库中全部存在，则执行该条规则，把结论放入事实库中。全部

30、存在，则执行该条规则，把结论放入事实库中。反复循环执行上面过程，直到推出目标，并存入事反复循环执行上面过程，直到推出目标，并存入事实库中为止。实库中为止。正向推理举例正向推理举例ABGCDAEDB，C，E产生式规则库产生式规则库事实库事实库在产生式规则库中有在产生式规则库中有3条规则，在事实库中存在条规则，在事实库中存在B，C，E3个事实，且它们均为真。希望通过正向推理，证明目标个事实，且它们均为真。希望通过正向推理，证明目标G为真。为真。推理过程：搜索每条规则的前提条件是否在事实库中推理过程：搜索每条规则的前提条件是否在事实库中步骤步骤搜索规则搜索规则是否激发该规是否激发该规则则原因原因事实

31、库状态事实库状态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逆向推理是从目标开始，寻找以此目标为结论的规逆向推理是从目标开始，寻找以此目标为结论的规则，并对该规则的前提进行判断，若该规则的前

32、提则，并对该规则的前提进行判断，若该规则的前提中某个子项是另一规则的结论，再找此结论的规则，中某个子项是另一规则的结论，再找此结论的规则，直到对某个规则的前提能够进行判断。直到对某个规则的前提能够进行判断。逆向推理举例逆向推理举例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，

33、G推理过程：搜索每条规则的结论，检查其前提是否在事实库中推理过程：搜索每条规则的结论，检查其前提是否在事实库中根据规则库得到的逆向推理树（知识树）根据规则库得到的逆向推理树（知识树）GABCIJKLMEXFWZPQABCG(IJ)KAXFJLBMECWZMPQE若有知识库为若有知识库为“与或与或”推理树的特点推理树的特点总目标总目标G（结论）（结论）前提前提A（结论）（结论）前提前提B（结论）（结论）前提前提C（结论）（结论）前提前提IJ前提前提K前提前提LME前提前提X 前提前提F前提前提W前提前提Z前提前提P前提前提Q每条规则对应的结点分支有与、或关系每条规则对应的结点分支有与、或关系树的

34、根结点是推理树的总目标树的根结点是推理树的总目标相邻两层之间是一条或多条规则连接相邻两层之间是一条或多条规则连接每个结点可以是单值，也可以是多值。若结点是多值时，各值对应的规则将每个结点可以是单值，也可以是多值。若结点是多值时，各值对应的规则将不同不同可以把所有的叶结点直接放在事实数据库中，也可以安排向用户提问可以把所有的叶结点直接放在事实数据库中，也可以安排向用户提问推理树的深度优先搜索过程推理树的深度优先搜索过程逆向推理过程逆向推理过程GABC IJKLMEXFWZPQYYNNYYY1264578910111235NNYYYY专家系统的开发专家系统的开发l由专家和知识工程师共同配合完成由专

35、家和知识工程师共同配合完成专家：可以不懂计算机，但一定是专家：可以不懂计算机，但一定是某个实际领域经验丰富某个实际领域经验丰富的人的人知识工程师：既知识工程师：既懂计算机懂计算机和和专家系统原理专家系统原理，同时又具有，同时又具有编编程程专家系统能力的人专家系统能力的人l开发途径开发途径直接使用智能程序专用设计语言（如直接使用智能程序专用设计语言（如LISP或或PROLOG）利用专家系统开发工具（如利用专家系统开发工具（如CLIPS：可从：可从http:/ 1、专家系统的局限、专家系统的局限l专家系统只是人的经验的汇集专家系统只是人的经验的汇集,因而它存在先天的缺陷因而它存在先天的缺陷,其解也

36、可能未其解也可能未必正确必正确;l专家系统不能由第一原理推理专家系统不能由第一原理推理,不能抓住相似不能抓住相似,缺乏普通的感知缺乏普通的感知,所以所以专家系统不是一个通用的专家专家系统不是一个通用的专家,不是一个问题求解器不是一个问题求解器;l对于复杂系统对于复杂系统,专家系统这种表达知识的方法也很难表达专家系统这种表达知识的方法也很难表达,解就更难解就更难;l专家系统的维护也很不容易专家系统的维护也很不容易,尤其对快速发展的医学和信息领域尤其对快速发展的医学和信息领域,有时有时一年就有一年就有30%的规则要加以改变。的规则要加以改变。2 2、专家系统的适用范围、专家系统的适用范围l在相对窄

37、的知范围和一些定义好的领域能成功应用；在相对窄的知范围和一些定义好的领域能成功应用；l在企业的管理信息系统中专家系统能起到它应有的作用。在企业的管理信息系统中专家系统能起到它应有的作用。专家系统的局限及适用范围专家系统的局限及适用范围四、遗传算法的决策支持遗传算法起源遗传算法起源 l 遗传算法是由美国的遗传算法是由美国的J.HollandJ.Holland教授于教授于19751975年在他的专著年在他的专著自然界和人工系统的适应性自然界和人工系统的适应性中中首先提出的，它是一类首先提出的，它是一类借鉴生物界自然选择和自借鉴生物界自然选择和自然遗传机制的随机化搜索算法然遗传机制的随机化搜索算法

38、。遗传学概述l达尔文进化论：达尔文进化论：“物竞天择、适者生存物竞天择、适者生存”l遗传学认为，遗传信息封装在遗传学认为，遗传信息封装在染色体染色体中，并以中，并以基因基因（位）（位）的形式包含在染色体（个体）中。的形式包含在染色体（个体）中。l每个基因有特殊的位置并控制某个特殊的性质。基因杂交每个基因有特殊的位置并控制某个特殊的性质。基因杂交和基因突变能产生对环境适应性强的后代，通过优胜劣汰和基因突变能产生对环境适应性强的后代，通过优胜劣汰的自然选择，的自然选择，适应值高的基因结构就保存下来适应值高的基因结构就保存下来。遗传算法（遗传算法（Genetic Algorithm,GA）l遗传算法

39、模拟自然界中的生命进化机制，遗传算法模拟自然界中的生命进化机制，是具有是具有“生存检生存检测测”的迭代过程的搜索算法的迭代过程的搜索算法 l遗传算法尤其适用于传统方法难以实现的遗传算法尤其适用于传统方法难以实现的最优化问题求解最优化问题求解实践证明，遗传算法已经在求解旅行商问题、背包问题、装箱实践证明，遗传算法已经在求解旅行商问题、背包问题、装箱问题、布局优化、网络路由等具有问题、布局优化、网络路由等具有NPNP难度的组合优化问题上取难度的组合优化问题上取得了成功的应用。得了成功的应用。l在人工智能研究中，人们认为在人工智能研究中，人们认为“遗传算法、自适应系统、细遗传算法、自适应系统、细胞自

40、动机、混沌理论与人工智能一样，都是对今后十年的计胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术算技术有重大影响的关键技术”。生物进化与遗传算法生物进化与遗传算法群体群体种群种群子群子群选择选择婚配婚配变异变异遭淘汰遭淘汰的群体的群体生物进化与遗传算法之间的对应关系生物进化与遗传算法之间的对应关系生物进化中的概念生物进化中的概念遗传算法中的作用遗传算法中的作用环境环境适应函数适应函数适应性适应性适应函数值适应函数值适者生存适者生存适应函数值最大的解被保留的概率最大适应函数值最大的解被保留的概率最大个体个体问题的一个解问题的一个解染色体染色体解的编码解的编码基因基因

41、编码的元素编码的元素群体群体被选定的一组解被选定的一组解种群种群根据适应函数选择的一组解根据适应函数选择的一组解交配交配以一定的方式由双亲产生后代的过程以一定的方式由双亲产生后代的过程变异变异编码的某些分量发生变化的过程编码的某些分量发生变化的过程遗传算法的工作示意图实际问题参数集实际问题参数集三个基本算子三个基本算子选择选择交叉交叉变异变异编码成位串形式编码成位串形式种群种群1计算适应函数值计算适应函数值选择和遗传选择和遗传统计结果统计结果种群种群2经过优化的一个或多个参数集经过优化的一个或多个参数集改善或解决实际问题改善或解决实际问题不满足要求遗传算法的三个主要操作l选择：选择：选出繁殖后

42、代的个体选出繁殖后代的个体轮盘赌法轮盘赌法期望值法期望值法最佳个体保存法最佳个体保存法其它其它l交叉：交叉：互换染色体，从而产生新的染色体互换染色体，从而产生新的染色体一点交叉、二点交叉、多点交叉一点交叉、二点交叉、多点交叉l变异变异：以很小的概率，随机地改变字符串某个位：以很小的概率，随机地改变字符串某个位置的值置的值染色体的选择染色体的选择l“轮盘赌轮盘赌”法法：每个个体的选择概率和其适应值：每个个体的选择概率和其适应值成比例，个体适应值越大，其被选择的概率就越成比例，个体适应值越大，其被选择的概率就越高。高。x1x2x3x4x5x6设群体大小为设群体大小为n，其中个体，其中个体i的的的的

43、适应度值为适应度值为fi，则，则i被选择的概率被选择的概率Pi为：为：染色体的选择染色体的选择l期望值方法：计算群体中每个个体在下一代生存期望值方法：计算群体中每个个体在下一代生存的期望数目，即的期望数目，即若某个体被选中并要参与配对和交叉，则它在下一若某个体被选中并要参与配对和交叉，则它在下一代中的生存的期望数目减去代中的生存的期望数目减去0.50.5；若不参与配对和交叉，；若不参与配对和交叉，则该个体的生存期望数目减去则该个体的生存期望数目减去1 1。因此，。因此，若一个个体的若一个个体的期望值小于零，则该个体不参与选择期望值小于零，则该个体不参与选择。l被选择次数的期望值被选择次数的期望

44、值对于规模为对于规模为N的群体，一个选择概率为的群体，一个选择概率为p(xi)的染色的染色体体xi被选择次数的期望值被选择次数的期望值e(xi)：对于群体中的每一个对于群体中的每一个xi，首先选择首先选择 次。这样次。这样共得到共得到 个染色体。然后按照个染色体。然后按照 从从大到小对染色体排序，依次取出大到小对染色体排序，依次取出 个染个染色体，这样就得到了色体，这样就得到了N个染色体。个染色体。染色体的选择染色体的选择染色体交叉染色体交叉l交叉发生在两个染色体之间，由两个被称之为双亲的父代交叉发生在两个染色体之间，由两个被称之为双亲的父代染色体，经杂交以后，产生两个具有双亲的部分基因的新染

45、色体，经杂交以后，产生两个具有双亲的部分基因的新的染色体。当染色体采用二进制形式编码时，交叉过程是的染色体。当染色体采用二进制形式编码时，交叉过程是以这样一种形式进行的：以这样一种形式进行的：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，如果变

46、异位发生在第三位，则变异后的染色体，如果变异位发生在第三位，则变异后的染色体变成了变成了y=11101。例：求函数的最大值例：求函数的最大值其中其中x为为0,31间的整数间的整数 编码：采用二进制形式编码编码：采用二进制形式编码 由于由于x的定义域是的定义域是0,31间的整数，刚好可以用间的整数，刚好可以用5位二进制数表位二进制数表示，因此可以用示，因此可以用5位二进制数表示该问题的解，即染色体。如位二进制数表示该问题的解，即染色体。如00000表示表示x0，10101表示表示x21，11111表示表示x31等等 l适应函数：适应函数：直接使用函数直接使用函数f(x)作为适应函数。作为适应函数

47、。l假设群体的规模假设群体的规模N4，交配概率，交配概率pc100，变异概，变异概率率pm1。l设随机生成的初始群体为：设随机生成的初始群体为：01101，11000，01000，10011染色体的选择方法：轮盘赌法染色体的选择方法：轮盘赌法序号序号群体群体适应值适应值选择概率（）选择概率（）选中次数选中次数10110116914.44121100057649.23230100064 5.47041001136130.851第第0代情况表代情况表 序号序号种群种群交配对像交配对像交配位交配位（随机选择）（随机选择）子代子代适应值适应值101101240110014421100014110016

48、2531100042110117294100113210000256第第0代种群的交叉情况代种群的交叉情况 序号种群交配对像交配位子代适应值1110112311001625211101131111196131000042100012894110113211010676第第2代种群的交配情况代种群的交配情况 序号序号群体群体适应值适应值选择概率（）选择概率（）选中次数选中次数101100144 8.21021100162535.62131101172941.56241000025614.601第第1代情况表代情况表 序号序号种群种群交配对象交配对象交配位交配位（随机选择）（随机选择）子代子代适应

49、值适应值1110012311011729211011131100162531101141100002564100003111011729第第1代种群的交配情况代种群的交配情况 l由于选择的变异概率由于选择的变异概率Pm=0.001，则平均每，则平均每1000位中才有一位中才有一位变异，由位变异，由4个位串组成的种群中共有个位串组成的种群中共有4520位，则变异位，则变异的期望值为的期望值为200.0010.02位。事实上在该例中没有变异发位。事实上在该例中没有变异发生。生。l对比对比1,2，3代的结果，可以看出，代的结果，可以看出，每一代的平均值及最大值每一代的平均值及最大值都比前一代有了很大

50、提高都比前一代有了很大提高，说明种群正朝优化的方向前进，说明种群正朝优化的方向前进最大适应值、平均适应值进化曲线最大适应值、平均适应值进化曲线 遗传算法的应用遗传算法的应用l遗传算法是多学科结合与渗透的产物。目前遗传遗传算法是多学科结合与渗透的产物。目前遗传算法所涉及的主要领域有自动控制、规划设计、算法所涉及的主要领域有自动控制、规划设计、组合优化、图象处理、信号处理、人工生命等。组合优化、图象处理、信号处理、人工生命等。课堂练习课堂练习l请用请用“抛硬币抛硬币”的方式，随机生成初始种群，求解的方式，随机生成初始种群，求解函数函数F(x)=x2的最大值（其它条件与例题相同）的最大值（其它条件与