研究生第七章智能决策支持系统和智能技术的决策支持课件

研究生第七章智能决策支持系统和智能技术的决策支持2024/5/12研究生第七章智能决策支持系统和智能技术的决策支持第7章本章内容7.1

人工智能概念7.2人工智能基本原理7.3专家系统与智能决策支持系统7.4遗传算法的决策支持7.5机器学习的决策支持研究生第七章智能决策支持系统和智能技术的决策支持开篇案例KPN电信公司的智能系统背景：KPN电信是一家卓越的电信公司，该公司在荷兰提供固定线路网络，在西欧提供数据和IP服务，并且该公司还在荷兰、德国和比利时提供移动服务。它拥有38000多名员工，他们服务于790万固定线路用户、1340万移动客户和140万网络订阅者。不仅如此，KPN电信还在阿姆斯特丹、纽约、伦敦和法兰克福的股票交易所上市。主要问题是：如何在使成本最小化的同时保持高效的运作。研究生第七章智能决策支持系统和智能技术的决策支持信息系统部面临的难题：在解决来自用户的服务电话时耗费时间严重，有时也很让人受挫。更糟糕的是，由于员工的离职或退休，导致了绝大部分知识维护的遗失。解决办法：开发了一个被称为阿基米德的基于规则的系统。该系统运用Authorete工具获取知识，这些知识包括：相关的安装问题、处理过程、步骤以及IT员工集体经验中的解决方法。阿基米德的核心是其知识库以及一个友好的用户界面。知识是用简单的语句而非复杂的结构来表达的。这些语句详细说明了当今的IT专家是如何分析软件安装并解决问题的。该系统通过下拉菜单中一系列有意义的陈述来指导用户，帮助KPN开发者并进一步完善知识。研究生第七章智能决策支持系统和智能技术的决策支持思考问题：开发智能系统的动机解释智能系统的作用及其潜在的优点，开发这些系统的主要困难是什么？人工智能与人类智能的区别是什么？研究生第七章智能决策支持系统和智能技术的决策支持基本思想：包含了学习人类的思考过程；通过机器（计算机和机器人）来描述并复制这些过程。众所周知的定义：人工智能是一种机器行为，如果由人类执行就可以称为智能。令人深思的定义：人工智能研究的是如何使计算机比人类做的更好。著名应用：深蓝——国际象棋程序。7.1人工智能的基本概念及原理研究生第七章智能决策支持系统和智能技术的决策支持人工智能具有的能力从经验中学习或理解。在模棱两可或相互矛盾的情形中进行理性分析。对新的情况进行快速成功的响应。在解决问题的过程中运用推理方法并对行为进行有效的指导。处理复杂的情况。以正常的理性方式来理解和推断。运用知识来处理环境。研究生第七章智能决策支持系统和智能技术的决策支持人工智能的特征

符号处理：数值与符号算法与启发式算法算法是一步一步地处理过程。启发式算法：从经验中获取的直觉知识或经验法则。推断：启发式算法的替代，包含运用启发式算法或从其他搜索方法从事实或规则中推断。机器学习：使系统调整行为并对外部环境做出反应。例：人工神经网络和遗传算法。研究生第七章智能决策支持系统和智能技术的决策支持人工智能比人类智能比较人工智能的优势人工智能更具有永久性。人工智能为复制和传播提供了便捷。人工智能的成本比自然智能的成本低。人工智能可以存档。人工智能执行某些任务的速度比人类快。人工智能执行某些任务的质量会比许多人甚至是大多数人高。人类智能具有的优势 人类智能富有创造性，人工智能缺乏创见。人类智能可以直接运用感官体验并且使人类受益。大多数人工智能系统必须在符号输入和表示中工作研究生第七章智能决策支持系统和智能技术的决策支持7.1人工智能的基本概念及原理人工智能的决策支持技术研究生第七章智能决策支持系统和智能技术的决策支持7.1人工智能的基本概念及原理1、人工智能的决策支持技术从智能决策支持系统的概念可知智能决策支持系统中包含了人工智能技术，与决策支持有关的人工智能技术主要有：专家系统、神经网络、遗传算法、机器学习、自然语言理解等。

研究生第七章智能决策支持系统和智能技术的决策支持专家系统是利用大量的专门知识解决特定领域中的实际问题的计算机程序系统；神经网络是利用神经元的信息传播模型（MP模型）进行学习和应用；遗传算法是模拟生物遗传过程的群体优化搜索方法；

机器学习是让计算机模拟和实现人类的学习，获取解决问题的知识；自然语言理解是让计算机理解和处理人类进行交流的自然语言。7.1人工智能的基本概念及原理研究生第七章智能决策支持系统和智能技术的决策支持2．智能决策支持系统结构形式

1）基本结构智能决策支持系统（IDSS）＝决策支持系统（DSS）＋人工智能（AI）技术7.1人工智能的基本概念及原理研究生第七章智能决策支持系统和智能技术的决策支持

问题综合与交互系统数据库管理系统模型库管理系统模型库数据库

人工智能技术专家系统神经网络遗传算法机器学习自然语言理解图7.1智能决策支持系统的基本结构

研究生第七章智能决策支持系统和智能技术的决策支持

图7.2智能决策支持系统结构问题综合与交互系统模型库管理系统数据库管理系统知识库管理系统推理机用户模型库

知识库数据库人工智能技术可以概括为：推理机＋知识库智能决策支持系统的结构可以简化为图7.2研究生第七章智能决策支持系统和智能技术的决策支持7.2人工智能基本原理7.2.1逻辑推理7.2.2知识表示与知识推理7.2.3搜索技术研究生第七章智能决策支持系统和智能技术的决策支持7.2.1逻辑推理1.形式逻辑(人的思维形式、规律)（1）概念：反映事物的特有属性和属性的取值。（2）判断：对概念的肯定或否定；判断本身有对有错；判断有全称的肯定（或否定）判断和存在的肯定（或否定）判断。（3）推理：从一个或多个判断推出一个新判断的过程。研究生第七章智能决策支持系统和智能技术的决策支持7.2.1逻辑推理2.推理的种类演绎推理归纳推理类比推理假言推理三段论推理数学归纳法假言易位推理枚举归纳推理1）演绎推理：从一般现象到个别（特殊）现象的推理。2）归纳推理：从个别（特殊）现象到一般现象的推理。3）类比推理：从个别（特殊）现象到个别（特殊）现象的推理。研究生第七章智能决策支持系统和智能技术的决策支持1）演绎推理专家系统的研究基本上属于演绎推理范畴。演绎推理的核心是假言推理。

假言推理：以假言判断为前提，对该假言判断的前件或后件的推理。1）假言推理：p

q，p┝q

2）三段论推理：p

q，q

r┝p

r3）假言易位推理（拒取式）：p

q，

q┝

p

符号“┝”表示推出7.2.1逻辑推理研究生第七章智能决策支持系统和智能技术的决策支持

2）归纳推理(个别→一般)（1）数学归纳法这种推导是严格的，结论是确实可靠的。（2）枚举归纳推理 S1是P，S2是P，…… Sn是P

S1……Sn是S类事物中的部分分子，没有相反事例。所以，S类事物都是P。

枚举归纳推理的结论是或然的(并非必然地)，它的可靠性和事例数量相关

。7.2.1逻辑推理研究生第七章智能决策支持系统和智能技术的决策支持枚举归纳推理实例如观察到铁受热膨胀、铜受热膨胀等事实而不知其所以然，由此推出“所有金属受热膨胀”的结论就是简单枚举归纳推理。

研究生第七章智能决策支持系统和智能技术的决策支持

3）类比推理它是由两个（或两类）事物在某些属性上相同，进而推断它们在另一个属性上也可能相同的推理。A事物有abcd属性,B事物有abc属性（或a,b,c相似属性）所以，B事物也可能有d属性（或d相似属性）

类比推理的结论带有或然性，它的可靠性和相类比事物属性之间的联系程度有关。7.2.1逻辑推理研究生第七章智能决策支持系统和智能技术的决策支持类比推理实例一1816年的一天，法国医生雷奈克出诊为一位年轻的女性看病，一见病人，雷奈克犯起愁来：她身体非常肥胖，要诊断她的心脏和肺部是否正常，按当时医生惯用的方法，把耳朵贴近病人的胸部来听，肯定听不清楚，更何况她是一位年轻的女性。雷奈克抬头看了看院子里正在玩耍的小孩，脑子里突然浮现出几年前看到一个孩子们玩的游戏：一个孩子用钉子敲打木板的一头，另外的孩子争先恐后地抱着把耳朵贴近木板的另一头，兴致勃勃地倾听着。研究生第七章智能决策支持系统和智能技术的决策支持

为什么木头能够把声音清晰地传过来呢？雷奈克稍微想了想，只见他很很地拍了一下手说：“就是这样！就是这样！”雷奈克要来一叠纸，紧紧地卷成一个卷，然后把纸卷的一端放在姑娘的胸部，另一端放在自己的耳朵上，侧着脸听了起来。“真是一个妙法！”雷奈克高兴地喊了一句。回到家里，雷奈克找到一根空心木管，造成了历史上第一个“听诊器”。类比推理实例一研究生第七章智能决策支持系统和智能技术的决策支持类比推理实例二

19世纪30年代，英国商人威尔斯以与冯灿的茂隆皮箱商行订购的皮箱中有不是皮的木料为由，向香港法院起诉，蓄意敲诈冯灿。针对这种情况，冯灿的律师罗文锦取出口袋的金怀表，高声问法官：“请问这是什么表？”法官答道：“这是金表，可是这与本案有什么关系？”罗文锦高举金表，面对法庭上所有的人说：“有关系。这是金表，没有人怀疑是吧？但是，请问，这块金表除表面镀金之外，内部的机制都是金制吗？”旁听者同声议论：“当然不是。”罗文锦继续说：“那么人们为什么又叫它金表呢？”稍作停顿又高声说：“由此可见，茂隆行的皮箱案不过是原告无理取闹、存心敲诈而已”原告理屈词穷，法庭最后以威尔斯诬告，罚款5000元结案研究生第七章智能决策支持系统和智能技术的决策支持皮箱诉讼案的法庭辩论中，卖方律师在反驳中所使用的就是类比推理：表的外表有金，内部含有不是金的材料，但却是金表；箱的外表有皮，但也含有不是皮的材料；所以，箱仍是皮箱。类比推理实例二研究生第七章智能决策支持系统和智能技术的决策支持

3.总结

1）演绎推理的结论没有超出已知的知识范围。而归纳推理和类比推理的结论超出已知的知识范围。演绎推理只能解释一般规律中的个别现象而归纳推理和类比推理创造了新的知识，使科学得到新发展，是一种创造思维方式。2）演绎推理中由于前提和结论有必然联系，只要前提为真，结论一定为真。归纳推理和类比推理中前提和结论，不能保证有必然联系，具有或然性。这样推理的结论未必是可靠的。需要经过严格的验证和证明，使之形成新的理论。7.2.1逻辑推理研究生第七章智能决策支持系统和智能技术的决策支持7.2.2知识表示与知识推理案例分析：礼来制药公司基于知识的实时系统的开发背景：礼来公司是一家全球性的大型美国制药公司（全球范围内有41000名员工，在158个国家销售产品）问题：生产药物产品需要一道叫做发酵的特殊工序。一个典型的发酵过程是操作一系列不停搅拌的容器。为了获得优质产品，需要小心监控发酵过程并且始终如一的控制。但是传统统计过程难以控制参数。例如：无法量化一个发酵种子所处的阶段。无法对产品搅动做出精确的预测。虽然培植采用相同的工序，但是由不同员工来执行。不同操作者根据各自的经验来控制这一过程，导致产品的质量有差异。研究生第七章智能决策支持系统和智能技术的决策支持解决：礼来公司采用专家系统来解决这一问题，目的是希望关键技术员能够24小时对发酵过程提供服务，并且专家系统中知识库的相关部分能够被复制。构建了一个智能质量报警系统，用于操作提供一致性的实时建议。开发过程：四名知识工程师参与了系统的开发，他们仅仅被要求记录专家知识，而不进行任何优化。也不能使用自身领域知识来影响专家。总共开发了6个月。步骤：知识诱出；知识融合；知识库编码；测试和评估。研究生第七章智能决策支持系统和智能技术的决策支持思考：为什么礼来公司需要开发一个智能系统来为过程操作提供建议？开发十个独立的知识库，然后通过知识融会将它们合成一个整体，你对此有何看法？这种方法的优点和缺点各是什么？使用知识获取工具有什么好处？研究生第七章智能决策支持系统和智能技术的决策支持7.2.2知识表示与知识推理研究生第七章智能决策支持系统和智能技术的决策支持7.2.2知识表示与知识推理知识获取：是指从人类专家、书本、文档、传感器或者计算机文件中采集知识。这些知识可能倾向于特殊的问题域或问题解决程序，也可能是一般性知识或者元知识。知识表示：采集的知识是在一种被称为知识表示的行为过程中组织的。这一行为过程包括知识图的表示以及将知识编码到知识库中。知识确认：知识将被不断确认和核实。推理：这一行为包括使计算机能够基于知识和问题特性来进行推理软件的设计。解释和理由：包括解释能力的设计和编程实现研究生第七章智能决策支持系统和智能技术的决策支持7.2.3搜索技术搜索技术是人工智能的一个重要研究内容。智能技术体现在减少搜索树中的盲目搜索。1.执行时间与ｎ，ｎ２，ｎ３等成正比的算法，称为按多项式时间执行。2.执行时间与２ｎ，ｎ！和ｎｎ等成正比的算法，称为按指数时间执行。按多项式时间执行的算法，计算机是可以实现的。按指数时间执行的算法，计算机是不可能实现的。研究生第七章智能决策支持系统和智能技术的决策支持7.2.3搜索技术人工智能中发展了一种称为启发式搜索方法，基本思想可用一个实例来说明：一个外地人到某城市出差，他想到书店看看，又不知书店在何处，如果采取盲目搜索，从住地出发沿任一方向走，在分叉路口又任选一分支走，他可能走几天几夜也找不到如果采用启发式方法，他会问路上的人，到书店怎样走。城市中的大部分人对书店不知道，问不出来。

研究生第七章智能决策支持系统和智能技术的决策支持7.2.3搜索技术改一种问法：问该城市最热闹的地方在哪儿？按照这个启发式信息沿着指路人的路线，乘车到达最热闹的地方但书店在哪儿，仍然不知道。如果盲目搜索，可能仍然找不到。如果采用启发式方法，他会问路上的人，卖画的地方在哪儿，他可以通过画店再问书店在哪儿？启发式方法能减少大量盲目无效的搜索，能有效克服按指数时间执行的组合爆炸现象研究生第七章智能决策支持系统和智能技术的决策支持7.2.3搜索技术搜索方法分类：基本搜索法（1）广度优先搜索法。（2）深度优先搜索法。研究生第七章智能决策支持系统和智能技术的决策支持7.2.3.1广度优先搜索（宽度优先搜索）1、广度优先搜索思想从初始状态S开始，利用规则，生成所有可能的状态。构成树的下一层节点，检查是否出现目标状态G，若未出现，就对该层所有状态节点，分别顺序利用规则。生成再下一层的所有状态节点，对这一层的所有状态节点检查是否出现G，若未出现，继续按上面思想生成再下一层的所有状态节点.这样一层一层往下展开。直到出现目标状态G为止。研究生第七章智能决策支持系统和智能技术的决策支持图7.7广度优先搜索示意图

研究生第七章智能决策支持系统和智能技术的决策支持1、深度优先搜索法思想从初始状态S开始，利用规则生成搜索树下一层任一个结点，检查是否出现目标状态G，若未出现，以此状态利用规则生成再下一层任一个结点，再检查是否为目标节点G。若未出现，继续以上操作过程，一直进行到叶节点（即不能再生成新状态节点）。当它仍不是目标状态G时，回溯到上一层结果，取另一可能扩展搜索的分支。生成新状态节点。一直进行下去，直到找到目标状态G为止。7.2.3.2深度优先搜索法研究生第七章智能决策支持系统和智能技术的决策支持图7.8深度优先搜索示意图

研究生第七章智能决策支持系统和智能技术的决策支持

在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上，则可较快地得到解。但是，如果目标节点不在此分支上，而该分支又是一个无穷分支，则就不能得到解。所以深度优先搜索是不完备的，即使问题有解，它也不一定能求得解。显然，用深度优先求得的解，也不一定是路径最短的解。

深度优先法适合于搜索树的深度较小的问题研究生第七章智能决策支持系统和智能技术的决策支持7.3专家系统与智能决策支持系统7.3.1专家系统原理7.3.2专家系统与DSS的集成研究生第七章智能决策支持系统和智能技术的决策支持7.3.1专家系统原理1.专家系统概念1）专家系统定义专家系统是具有大量专门知识，并能运用这些知识解决特定领域中实际问题的计算机程序系统。专家系统是利用大量的专家知识，运用知识推理的方法来解决各特定领域中的实际问题。计算机专家系统这样的软件能够达到人类专家解决问题的水平。研究生第七章智能决策支持系统和智能技术的决策支持7.3.1专家系统原理2）专家系统的特点专家系统需要大量的知识，这些知识是属于规律性知识，它可以用来解决千变万化的实际问题。专业技能符号推理深层知识自我知识研究生第七章智能决策支持系统和智能技术的决策支持传统系统与专家系统比较传统系统专家系统信息及其处理过程通常在连续的程序中结合知识库与处理（推理）机制明显分离程序不会出错程序可能出错通常不解释为什么要输入数据或如何得出结论解释是多数专家系统的一部分需要输入所有的数据不要求输入所有的数据。程序更改复杂改变规则容易系统只在其完成时运行系统可以在少数规则下运行系统一步一步执行系统通过启发式算法和逻辑执行数据表示和应用大数据库知识表示和应用大知识库处理定量数据处理定性数据运用数字表示运用符号和数字知识表示获取、放大和分配得到的数据或信息获取、放大和分配获取到的判断或知识研究生第七章智能决策支持系统和智能技术的决策支持人类专家与专家系统的不同特征人类专家专家系统损失率是否知识传递难易知识记录难易决策一致性低高单位使用成本高低创造性高低自适应性高低知识范围广泛狭窄知识类型常识和技术技术知识内容经验符号研究生第七章智能决策支持系统和智能技术的决策支持

2.专家系统结构专家系统的核心是知识库和推理机。专家系统可以概括为：

专家系统＝知识库+推理机7.3.1专家系统原理研究生第七章智能决策支持系统和智能技术的决策支持知识获取人机接口知识库推理机专家用户咨询建议专家系统核心专家系统结构

研究生第七章智能决策支持系统和智能技术的决策支持7.3.2专家系统与决策支持系统集成

IDSS充分发挥了专家系统以知识推理形式解决定性分析问题的特点.发挥了决策支持系统以模型计算为核心的解决定量分析问题的特点.充分做到定性分析和定量分析的有机结合.

研究生第七章智能决策支持系统和智能技术的决策支持数据库DBDSS控制系统模型库MB问题综合与交互系统动态DB推理机和解释器知识库KB集成系统DSSES图7.16智能决策支持系统集成结构图综合系统DSS和ES的总体结合。

由集成系统把DSS和ES有机结合起来2.KB和MB的结合。

模型库中的数学模型和数据处理模型作为知识的一种形式，即过程性知识，加入到知识推理过程中去。3.DB和动态DB的结合。DSS中的DB可以看成是相对静态的数据库，它为ES中的动态数据库提供初始数据，ES推理结束后，动态DB中的结果再送回到DSS中的DB中去。

研究生第七章智能决策支持系统和智能技术的决策支持DSS与ES集成形式一：DSS和ES并重的IDSS结构集成系统DSSES7.3.2专家系统与决策支持系统集成

集成特点1.具有综合系统，具有调用和集成DSS和ES的能力。2.扩充DSS的问题与人机交互系统功能，增加对ES的调用组合能力DSS与ES的关系：DSS中DB与ES中的动态DB进行数据交换解决问题的特点体现定性分析和定量分析并重解决问题的特点。研究生第七章智能决策支持系统和智能技术的决策支持DSS控制系统MBDBESDSS与ES集成形式二：DSS为主体的IDSS结构

7.3.2专家系统与决策支持系统集成

集成特点集成系统和DSS控制系统合为一体DSS与ES的关系：ES被DSS控制系统调用解决问题的特点体现以定量分析为主，结果定性分析解决问题的特点。研究生第七章智能决策支持系统和智能技术的决策支持推理机（广义）

DSS动态DBKB推理机MB动态DBKB图7.19DSS作为推理形式的IDSS图7.20模型作为知识的IDSSDSS与ES集成形式三：

ES为主体的IDSS结构7.3.2专家系统与决策支持系统集成

集成特点人机交互系统和ES合为一体DSS与ES的关系：图7.19DSS作为推理机，受ES的推理机控制；图7.20数据模型作为知识出现解决问题的特点体现以定量分析为主，结果定性分析解决问题的特点。研究生第七章智能决策支持系统和智能技术的决策支持7.4遗传算法的决策支持7.4.1遗传算法原理7.4.2优化模型的遗传算法求解7.4.3获取知识的遗传算法7.4.4遗传规划建立模型研究生第七章智能决策支持系统和智能技术的决策支持7.4.1遗传算法原理遗传算法(GeneticAlgorithm，GA)是模拟生物进化的自然选择和遗传机制的一种寻优算法。适用于复杂的非线性问题,主要应用在组合优化和机器学习两个方面。应用领域：图像识别、图像恢复、自适应控制、优化调度等领域。研究生第七章智能决策支持系统和智能技术的决策支持遗传算法的发展过程大体上可分为以下三个阶段：

（1）70年代的兴起阶段。1975年美国Michigan大学J.Holland首次系统地阐述了遗传算法的基本理论和方法。在这一时期的大部分研究都处于理论研究和建立实验模型阶段（2）80年代的发展阶段。1980年Smith教授将遗传算法应用于机器学习领域，研制出了一个著名的分类器(Classifier)系统。这期间许多学者对遗传算法进行了大量的改进和发展，提出了许多成功的遗传算法模型，使遗传算法应用于更广泛的领域。

（3）90年代的高潮阶段。进入90年代后，遗传算法作为一种实用、高效的优化技术，得到了极为迅速的发展。

7.4.1遗传算法原理研究生第七章智能决策支持系统和智能技术的决策支持7.4.1遗传算法原理7.4.1.1遗传算法工作过程7.4.1.2遗传算法的理论基础7.4.1.3遗传算法的基本特征研究生第七章智能决策支持系统和智能技术的决策支持7.4.1.1遗传算法的工作过程遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。种群(population)就是模拟生物种群而由若干个体组成的群体,它一般是整个搜索空间的一个很小的子集。遗传算法的三个主要操作算子：选择（selecation）、交叉（crossover）和变异（mutation）构成了遗传操作（Geneticoperation），使遗传算法具有了其他传统方法所没有的特性。研究生第七章智能决策支持系统和智能技术的决策支持产生新一代群体编码和初始群体形成输出种群个体适应值满意否？7.4.1.1遗传算法的工作过程

首先将问题的每个可能的解按某种形式编码，编码后的解称作染色体（个体）。

随机选取N个染色体构成初始种群，再根据预定的评价函数对每个染色体计算适应值，使得性能较好的染色体具有较高的适应值。

选择适应值高的染色体进行复制，通过遗传算子来产生一群新的更适应环境的染色体，形成新的种群。

这样一代一代不断繁殖，最后收敛到一个最适应环境的个体上，求得问题的最优解。遗传算子选择交叉变异研究生第七章智能决策支持系统和智能技术的决策支持1.群体中个体的编码如何将问题描述成位串的形式，即问题编码。一般将问题的参数用二进制位（基因）编码构成子串，再将子串拼接起来构成“染色体”位串。7.4.1.1遗传算法的工作过程例如：个体染色体9----1001（2，5，6）----010101110研究生第七章智能决策支持系统和智能技术的决策支持2.适应值函数的确定遗传算法的执行过程中，每一代有许多不同的染色体（个体）同时存在，这些染色体中哪个保留(生存)、哪个淘汰(死亡)是根据它们对环境的适应能力决定的，适应性强的有更多的机会保留下来。适应性强弱是计算个体适应值函数f(x)的值来判别的，这个值称为适应值(fitness)。适应值函数(即评价函数)是根据目标函数确定的。适应值总是非负的，任何情况下总是希望越大越好。如果目标函数不是取最大值时，需要将它映射成适应值函数。适应值函数f(x)的构成与目标函数有密切关系，往往是目标函数的变种。一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。7.4.1.1遗传算法的工作过程研究生第七章智能决策支持系统和智能技术的决策支持3.遗传算法的三个算子（一）选择(Selection)算子（二）交叉(Crossover)算子（三）变异(Mutation)算子7.4.1.1遗传算法的工作过程研究生第七章智能决策支持系统和智能技术的决策支持它又称复制(reproduction)、繁殖算子。选择是从种群中选择生命力强的染色体产生新种群的过程。依据每个染色体的适应值大小，适应值越大，被选中的概率就越大，其子孙在下一代产生的个数就越多。选择操作是建立在群体中个体的适应值估评基础上的。7.4.1.1遗传算法的工作过程（一）选择(Selection)算子研究生第七章智能决策支持系统和智能技术的决策支持通常做法是：对于一个规模为N的种群S,按每个染色体xi∈S的选择概率P(xi)所决定的选中机会,分N次从S中随机选定N个染色体,并进行复制。7.4.1.1遗传算法的工作过程

这里的选择概率P(xi)的计算公式为（一）选择(Selection)算子研究生第七章智能决策支持系统和智能技术的决策支持（二）交叉(crossover)算子它又称重组(recombination)、配对(breeding)算子，在遗传算法中起着核心作用。染色体重组是分两步骤进行的:首先在新复制的群体中随机选取两个个体然后，沿着这两个个体(字符串)随机地取一个位置，二者互换从该位置起的末尾部分。交叉率(crossoverrate)就是参加交叉运算的染色体个数占全体染色体总数的比例，记为Pc,取值范围一般为0.4～0.99。7.4.1.1遗传算法的工作过程研究生第七章智能决策支持系统和智能技术的决策支持7.4.1.1遗传算法的工作过程例1:有两个用二进制编码的个体A和B。长度L=5，A=a1a2a3a4a5，B=b1b2b3b4b5随机选择一整数k∈[1，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.0001～0.02。它保证了遗传算法的有效性。7.4.1.1遗传算法的工作过程（三）变异(Mutation)算子研究生第七章智能决策支持系统和智能技术的决策支持7.4.1.1遗传算法的工作过程例如:设染色体s=11001101将其第三位上的0变为1,即s=11001101→11101101=s′。

s′也可以看做是原染色体s的子代染色体。（三）变异(Mutation)算子研究生第七章智能决策支持系统和智能技术的决策支持4.控制参数设定遗传算法中的参数包括群体中个体的数目、交叉概率、变异概率等这些参数的设定随具体问题的不同将有所差别，带有经验性，它会影响遗传算法的迭代收敛过程。7.4.1.1遗传算法的工作过程研究生第七章智能决策支持系统和智能技术的决策支持1.遗传算法的处理对象是问题参数的编码个体（位串）遗传算法要求将问题的参数编码成长度有限的位串。遗传算法是在求解问题的编码串上进行操作，从中找出高适应值的位串，而不是对问题目标函数和它们的参数直接操作。遗传算法不受函数限制条件(如导数存在、连续性、单极值等)的约束。7.4.1.3遗传算法的基本特征

研究生第七章智能决策支持系统和智能技术的决策支持2.遗传算法的搜索是从问题解位串集开始搜索，而不是从单个解开始在最优化问题中，传统的方法是从一个点开始搜索，如爬山法。一般复杂问题会在“地形”中出现若干“山峰”，传统的方法很容易走入假“山峰”。遗传算法同时从种群的每个个体开始搜索，象一张网罩在“地形”上，数量极大的个体同时在很多区域中进行搜索，这样就减少了陷入局部解的可能性。7.4.1.3遗传算法的基本特征

研究生第七章智能决策支持系统和智能技术的决策支持3.遗传算法只使用目标函数(即适应值)来搜索，而不需要导数等其他辅助信息传统搜索算法需要一些辅助信息，如梯度算法需要导数，当这些信息不存在时，这些算法就失效了。而遗传算法只需目标函数和编码串，因此，遗传算法几乎可以处理任何问题。4.遗传算法使用的三种遗传算子是一种随机操作，而不是确定性规则遗传算法使用随机操作，但并不意味着遗传算法是简单的随机搜索。遗传算法是使用随机工具来指导搜索向着一个最优解前进。5.隐含的并行性6.易介入到已有的模型中，并具有扩展性；易于同别的技术结合使用7.4.1.3遗传算法的基本特征

研究生第七章智能决策支持系统和智能技术的决策支持7.4.2优化模型的遗传算法求解优化模型的计算是遗传算法最基本的也是最重要的研究和应用领域之一。一般说来，优化计算问题通常带有大量的局部极值点，往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的NP完全问题。精确地求解优化问题的全局最优解一般是不可能的。研究生第七章智能决策支持系统和智能技术的决策支持旅行商问题（TSP）的遗传算法求解实例

已知n个城市的地理位置（x,y），求经过所有城市，并回到出发城市且每个城市仅经过一次的最短距离。这是一个NP完全问题，其计算量为城市个数的指数量级。现用遗传算法来解决这个问题。

研究生第七章智能决策支持系统和智能技术的决策支持1、编码

31578910426每条路径对应一个个体，个体形式地表示为R={City_No|City_No互不重复}n，n为城市数。例如对于n=10的TSP问题，对其中一个个体它表示一条城市路径31 5 7 8 910 4 2 6研究生第七章智能决策支持系统和智能技术的决策支持其中ni表示个体中第i位的城市编号，n11=n1。适应值为非负，且取值越大越好。表示所有个体的路径长度的总和2、适应值函数

每个个体代表一条可能的路径。个体n的适应值为：其中N为种群数，Dn为沿个体标示的城市序列的所经过的距离:研究生第七章智能决策支持系统和智能技术的决策支持3、交叉

随机地从种群中选出要交叉的两个不同个体，随机地选取一个交叉段。交叉段中两个个体的对应部分通过匹配换位实现交叉操作。对个体A和B：

A＝984

|567|

13210

B＝871

|4103|

2965交叉段

对个体A，对交叉段中由B换位来的数，如4、10、3，在A中其它位相同的数进行反交换，即4换为5，10换为6，3换为7；对个体B，相似处理，最后得到：

A，＝98

4

|4103|

1

3

2

6

B，＝8

7

1

|567|

29

65

A，＝98

5

|4103|

1

7

2

6B，＝8

3

1

|567|

29

104研究生第七章智能决策支持系统和智能技术的决策支持4、变异

根据变异概率Pe，随机地从种群中选出要变异的个体，随机地在该个体上选出变异两个位置，然后两个位置上的城市序号进行交换。如：

A=9

8

456

7

13210下划线部分为要变异的两个位置。变异为：

A`=9

7

456

8

13210

研究生第七章智能决策支持系统和智能技术的决策支持5、遗传算法结果计算结果表明：n个城市的最佳路径接近一个外圈无交叉的环路。研究生第七章智能决策支持系统和智能技术的决策支持7.5机器学习的决策支持7.5.1机器学习概述7.5.2机器学习分类7.5.3建立模型的发现学习研究生第七章智能决策支持系统和智能技术的决策支持7.5.1机器学习综述1.基本概念学习和解决问题是人类最重要的两个智能行为机器学习是让计算机模拟和实现人类的学习，获取知识。机器学习也是计算机具有智能的重要标志。

研究生第七章智能决策支持系统和智能技术的决策支持7.5.1机器学习综述(1)人类学习概念的学习、领域知识的学习、技能（元知识即解决问题）的学习特点：过程缓慢、会忘记、知识传授困难、能不断修改知识，使人类逐渐变得聪明。研究生第七章智能决策支持系统和智能技术的决策支持7.5.1机器学习综述(2)机器学习（1）R.S.Michalski认为：学习是构造或修改所经历的事物的表示。该观点强调知识的表示。

（2）学习是知识的获取。该观点强调知识获取。

（3）H.A.Simon认为：学习是系统在相似的任务中，做一些适应性变化，使得在下一次类似的任务中，做得更好。该观点强调学习的效果。研究生第七章智能决策支持系统和智能技术的决策支持7.5.1机器学习综述2.机器学习与专家系统专家系统知识获取的“瓶颈”现象知识的脆弱性缺乏直觉判断能力机器学习提供知识获取提供有效途径研究生第七章智能决策支持系统和智能技术的决策支持7.5.1机器学习综述3.机器学习实例1.Michalski和R.L.Chilausky的PLANT/SS系统它是一个大豆病害诊断防治专家系统。该系统用示例学习AQ11算法自动产生规则进行诊断。把631种有病害的大豆的性状描述（表示为包含35种特性的向量）和每种植物的病名一起输入到计算机中选用290种做为训练例子（例子间相差很远），利用AQ11算法获得规则知识。再用340个样本作为测试例子，并将专家和计算机的诊断结果进行对比。研究生第七章智能决策支持系统和智能技术的决策支持7.5.1机器学习综述验证AQ11

算法测试例（340个）××症状

训练例

（290个）××症状：病名规

则知

识诊断病名实际病名97.6%（大豆病害实例）（If——then）（正确判别率）计算机产生的规则优于专家归纳的规则专家的正确判断率为71.8％。计算机的正确判断率高达97.6％。研究生第七章智能决策支持系统和智能技术的决策支持7.5.1机器学习综述钟鸣和陈文伟的IBLE算法利用信息论的信道容量思想，研制了IBLE算法。对已有结论的化学物质的质谱进行学习，得出了质谱规则。然后利用这些规则再去测试未知化学物质的质谱，得出它的种类。研究生第七章智能决策支持系统和智能技术的决策支持钟鸣和陈文伟的IBLE算法验证IBLE

算法测试集（5500个）正确识别率：94%

训练例八类化合物质谱15000种××特征：物质类规

则

树一般专家的正确识别率70%研究生第七章智能决策支持系统和智能技术的决策支持7.5.2机器学习分类学习过程的本质是学生(学习系统)把教师或环境(如书本)提供的信息转换成能够理解的形式记忆下来，以便将来使用.当前,国际上流行的机器学习分类方法主要有四种:按应用领域分类(专家系统、问题求解、认知模拟）按获取知识的表示分类(逻辑表达式、产生式规则、决策树、神经网络)按推理策略分类(演绎推理和归纳推理)机械学习、示教学习、通过例子学习、解释学习、类比学习、发现学习按系统性分类(历史渊源、知识表示、推理策略、应用领域).研究生第七章智能决策支持系统和智能技术的决策支持7.5.2机器学习系统基本结构环境学习知识库执行研究生第七章智能决策支持系统和智能技术的决策支持(1)机械学习（ROTELEARNING)1.思想:记忆=检索+计算2.示意图检索程序计算f(x)记录(2)无(1)存入输出yj=f(xj)有解yixixj研究生第七章智能决策支持系统和智能技术的决策支持例子：汽车保险程序该程序能对被损坏的汽车的修理费用进行计算.它的输入是汽车损坏情况,即生产厂家、生产年代、汽车种类、汽车损坏部位及程度等数据.一般是直接查找到所需的修理费用.如果系统没有发现这样的汽车,系统就利用一般的赔偿规则和计算公式计算出它的修理费用,并把它保存起来,下一次遇到这种情况就直接查找结果而不再去计算.研究生第七章智能决策支持系统和智能技术的决策支持3.机械学习系统中要注意三个问题:数据的存储组织.使得在大量的数据中能迅速地查找出所需的数据.适应变化的环境.数据要随形势的变化而变化,很多数据由于形势发展已过时或无用,就要进行相应的变化和更新.检索和计算的权衡.检索一定比计算来得更快才有意义机械学习的基本思想是用检索来代替计算.(1)机械学习（ROTELEARNING）研究生第七章智能决策支持系统和智能技术的决策支持1.思想:把外部知识(专家、教师)消化成内部可使用的知识，并把新知识和原来的知识有机的结合在一起。2.示意图:(2)示教学习（被告知学习）知识库原知识新知识知识转换外部知识内部知识一致化效果评价（矛盾、冗余）研究生第七章智能决策支持系统和智能技术的决策支持3.实现步骤(1)请求:向人类专家提出请求.(2)解释:消化吸收专家的知识并把它转化成可理解形式。(3)形式化:把专家知识转换成机器能够操作形式，即当专家的知识不能直接在机器上操作时,需要进行一些处理(形式化),使专家知识成为可使用形式.(4)并入:把知识并入知识库中.在并入知识库时要解决知识的冗余和矛盾的问题.(5)评价:评价知识的执行的结果.一般让系统使用专家的知识执行某些实际任务,检查是否工作得很好.(2)示教学习（被告知学习）研究生第七章智能决策支持系统和智能技术的决策支持1.思想:从大量例子中分析、提炼出规则知识或判定树知识。2.示意图:(3)示例学习（learningfromexamples）ID3(互信息);IBLE(信道容量)例子集示例学习算法规律性知识产生式规则判定树集合论方法信息论方法AQ系列:AQ11,AQ15AE5粗集方法ID3IBLEAQ15研究生第七章智能决策支持系统和智能技术的决策支持

例如,给出肺炎与肺结核两种病的一些病例.每个病例都含有五种症状：

发烧(无、低、高),

咳嗽(轻微、中度、剧烈),

X光所见阴影(点状、索条状、片状、空洞),

血沉(正常、快),

听诊(正常、干鸣音、水泡音).(3)示例学习（learningfromexamples）研究生第七章智能决策支持系统和智能技术的决策支持肺炎和肺结核的部分病例集为：通过示例学习得到如下诊断:

（1）血沉＝正常∧（听诊＝干呜音∨水泡音）→诊断＝肺炎（2）血沉＝快∨听诊＝正常→诊断＝肺结核这样，就从例子（病例）归纳产生了诊断规则。

肺炎肺结核病状病例号发烧咳嗽X光所见血沉听诊1高剧烈片状正常水泡音2中度剧烈片状正常水泡音3低轻微点状正常干鸣音4高中度片状正常水泡音5中度轻微片状正常水泡音1无轻微索条状正常正常2高剧烈空洞快干鸣音3低轻微索条状正常正常4无轻微点状快干鸣音5低中度片状快正常研究生第七章智能决策支持系统和智能技术的决策支持示例学习系统较多，其中较有影响的有：•J.R.Quinlan的ID3•Michalski的AQ11及洪家荣扩充的AQ15•洪家荣的AE5•钟鸣和陈文伟的IBLE(3)示例学习（learningfromexamples）研究生第七章智能决策支持系统和智能技术的决策支持4.类比学习(learningbyanalogy)类比从一个已知事物的“源”领域到一个未知的“目标”领域进行知识的映射。类比推理从一个已知事物（源），通过类比来解决另一个未知事物（目标）的推理过程。研究生第七章智能决策支持系统和智能技术的决策支持类比学习过程1.联想搜索匹配对一个新事物(目标源)提取其特征用这些特征去搜索一个与之相似的已知事物(候选源)，进行匹配。2.检验相似程度判断已知事物(候选源)与新事物(目标源)的相似程度，达到了某阈值，则类比匹配3.修正、变换的求解为了把匹配成功的已知事物(源)用于新事物(目标)，需要对已知事物的知识进行修正变换，以导出新事物的解。

4.更新知识库当新事物的解求出以后，将它并入知识库研究生第七章智能决策支持系统和智能技术的决策支持1.思想：根据两事物性质，从一个事物的特性，推出另一个事物的新特性。2.示意图：源域S元素a性质P(a)有Q(a)目标域T元素b性质P(b)有Q(b)相似类比类比学习方法研究生第七章智能决策支持系统和智能技术的决策支持S域中找P(a)->Q(a)S域中一般P(x)->Q(x)(1)归纳T域中P(x)->Q(x)(2)映射T域中P(b)->Q(b)(3)演绎类比学习算法思想（1）找出源域与目标域的相似性质P，以及找出源域中另一个性质Q和性质P对元素a的关系：

P(a)→Q(a)（2）在源域中推广P和Q的关系为一般关系，即：

x(P(x)→Q(x))这一步实际是归纳，由个别现象推广成一般规律。（3）从源域和目标域映射关系，得到目标域的新性质：

x(P(x)→Q(x))（4）利用假言推理：

P(b),P(x)→Q(x)┝Q(b)

最后得出b具有性质Q，这一步实际是演绎，由一般规律推出个别现象。研究生第七章智能决策支持系统和智能技术的决策支持类比推理描述有两个不同的领域：源域S和目标域T，S中的元素a和T中元素b具有相似的性质P，即P(a)～P(b)（“～”表示相似），a还具有性质Q，即