教学课件-《人工智能基础》蔡自兴.ppt

1、人 工 智 能 基 础第一章 绪论1.1 人工智能的定义和发展1.2 人类智能和人工智能1.3 人工智能的学派及其争论1.4 人工智能的研究与应用领域1.5 人工智能对人类的影响1.6 对人工智能的展望 几种定义 智能（intelligence）智能机器（intelligent machine）人工智能 人工智能（学科）人工智能（能力）31.1.1 人工智能的定义1.1.2 人工智能的起源与发展 孕育时期（1956年前）数理逻辑学科（弗雷治、维纳等）计算的新思想（丘奇、图灵等）拟脑机器（麦卡洛克、皮茨）形成时期（1956 1970年）1956年，第一次人工智能的研讨会 1969年，第一届国际人

2、工智能联合会议 1970年，人工智能国际杂志创刊41.1.2 人工智能的起源与发展 暗淡时期（1966 1974年）一些人工智能研究者盲目乐观 科学技术的发展对人工智能提出新的要求甚至挑战 知识应用时期（19701988年）专家系统与知识工程迅速发展 人工智能系统是一个知识处理系统 知识表示 知识利用 知识获取51.1.2 人工智能的起源与发展 集成发展时期（1986年至今）进一步研究AI基本原理方法和技术 深入渗透到其他学科和科学技术领域 三大学派综合集成，优势互补，共同发展61.2 人工智能的各种认知观1.2.1 人工智能的主要学派 符号主义（Symbolicism）基于物理符号系统假设和

3、有限合理性原理 连接主义（Connectionism）基于神经网络及其间的连接机制与学习算法 行为主义（Actionism）基于控制论及感知动作型控制系统 7符号主义（Symbolicism）又称：逻辑主义、心理学派或计算机学派 原理：物理符号系统(即符号操作系统)假设和有限合理性原理 起源：源于数理逻辑 学派代表：纽厄尔、西蒙和尼尔逊等8连接主义（Connectionism）又称：仿生学派或生理学派 原理：神经网络及神经网络间的连接机制与学习算法 起源：源于仿生学，特别是人脑模型的研究 学派代表：卡洛克、皮茨、Hopfield、鲁梅尔哈特等9行为主义（Actionism）又称：进化主义或控制

4、论学派 原理：控制论及感知动作型控制系统 起源：源于控制论 学派代表作：布鲁克斯(Brooks)的六足行走机器人，一个基于感知动作模式的模拟昆虫行为的控制系统 101.2.2 人工智能的争论 对人工智能理论的争论 符号主义 认为人的认知基元是符号，认知过程即符号操作过程；认为人是一个物理符号系统，计算机也是一个物理符号系统，因此，能用计算机来模拟人的智能行为；认为知识是信息的一种形式，是构成智能的基础。人工智能的核心问题是知识表示、知识推理和知识运用。11对人工智能理论的争论 连接主义 认为思维基元是神经元，而不是符号处理过程；认为人脑不同于电脑，并提出连结主义的大脑工作模式，用于取代符号操作

5、的电脑工作模式。12对人工智能理论的争论 行为主义 认为智能取决于感知和行动(所以被称为行为主义)，提出智能行为的“感知动作”模式；认为智能不需要知识、不需要表示、不需要推理；人工智能可以象人类智能一样逐步进化(所以称为进化主义)；智能行为只能在现实世界中与周围环境交互作用而表现出来。13对人工智能方法的争论 符号主义 功能模拟 连接主义 结构模拟 行为主义 行为模拟141.2.2 人工智能的争论 1.3 人类智能和人工智能 心理活动的最高层级是思维策略，中间一层是初级信息处理，最底层级是生理过程。研究认知过程的主要任务是探求高层次思维决策与初级信息处理的关系，并用计算机程序来模拟人的思维策略

6、水平，而用计算机语言模拟人的 初级信息处理过程。151.3.1 研究认知过程的任务 1.3.2 智能信息处理系统的假设 人是一种智能信息处理系统 物理符号系统的六种基本功能 物理符号系统的假设 推论一 推论二 推论三161.3.3 智能信息处理系统的假设 人类的认知行为具有不同层次 认知生理学 认知心理学 认知信息学 认知工程学171.3.3 人类智能的计算机模拟 机器智能可以模拟人类智能 智能计算机 下棋 定理证明 语言翻译 新型智能计算机 神经计算机 量子计算机181.4 人工智能的研究目标和内容1.4.1 人工智能的研究目标 一般研究目标 更好地理解人类智能 通过编写程序来模仿和检验有关

7、人类智能的理论。创造有用的灵巧程序，该程序能够执行一般需要人类专家才能实现的任务。近期研究目标的远期研究目标 近期研究目标是建造智能计算机应以代替人类的某些智力活动。远期目标是用自动机模仿人类的思维活动和智力功能。191.4.2 人工智能研究的基本内容 认知建模 知识表示 知识推理 知识应用 机器感知 机器思维 机器学习 机器行为 智能系统构建201.5 人工智能研究的主要方法 功能模拟法 结构模拟法 行为模拟法 集成模拟法211.6 人工智能的研究和应用领域 人工智能的基本技术 知识表示（Knowledge Representation）状态空间法、问题归约法、谓词逻辑法 推理搜索（Sear

8、ching&Reasoning）启发式搜索、消解原理、不确定性推理 计算智能（Computational Intelligence）模糊计算、神经计算、进化计算 构成技术（系统与语言）产生式系统、LISP语言、Prolog语言221 问题求解与博弈 问题的表示、分解、搜索、归约等 进行复杂的数学公式符号运算求解2 逻辑推理与定理证明 通过对事实数据库的操作来证明定理 多种证明方法 几何定理证明的“吴氏方法”231.6 人工智能的研究和应用领域3 计算智能 计算智能 包括神经计算、模糊计算、进化计算、粒群计算、自然计算、免疫计算和人工生命等 进化计算的理论基础是生物进化论4 分布式人工智能与Ag

9、ent 是传统人工智能的延伸和扩展 研究目标是创建一种能描述自然系统和社会系统的精确概念模型241.6 人工智能的研究和应用领域5 自动程序设计 根据不同目的描述来编写的计算机程序 促进人工智能系统的发展6 专家系统 是一个智能化的计算机程序系统 和传统的计算机程序之间有本质区别251.6 人工智能的研究和应用领域7 机器学习 是机器获取智能的途径 学习是一个有特定目的的知识获取过程 学习的本质是对信息的理解与应用 有多种学习方法8 自然语言理解 语言 自然语言、人造语言、机器语言 “理解”的标准261.6 人工智能的研究和应用领域9 机器人学 操作机器人 智能机器人 机器人的广泛应用 促进人

10、工智能的发展10 模式识别 是计算机对环境识别的需要 是对人类环境的感知模拟271.6 人工智能的研究和应用领域11 机器视觉 人类80以上的外部信息来自视觉 低层视觉与高层视觉 前沿研究领域 广泛应用12 神经网络 神经计算机 在其它领域中的广泛应用281.6 人工智能的研究和应用领域13 智能控制 驱动智能机器自主地实现其目标的过程 是一个定性和定量的混合控制过程 是当今自动控制的最高水平14 智能调度与指挥 寻找最佳调度和组合 NP完全类问题的求解 军事指挥系统等领域291.6 人工智能的研究和应用领域15 智能检索 是信息时代来临的需要 智能检索系统所面临的三大问题16 系统与语言工具

11、 计算机系统的一些概念得到发展 新的编程语言与专用开发工具301.6 人工智能的研究和应用领域1.7 人工智能对人类的影响 人工智能对经济的影响 人工智能对社会的影响 人工智能对文化的影响311.7.1 人工智能对经济的影响 专家系统的效益 人工智能推动计算机技术发展321.7.2 人工智能对社会的影响 劳务就业问题思维方式与观念的变化技术失控的危险（美国科幻作家阿西莫夫提出了“机器人三守则”）社会结构变化心理上的威胁1.7.3 人工智能对文化的影响 改善人类知识 改善人类语言 改善文化生活331.8 对人工智能的展望 人工智能的近期研究目标：在于建造智能计算机，用以代替人类从事脑力劳动，即使

12、现有的计算机更聪明更有用。人工智能的远期研究目标：探究人类智能和机器智能的基本原理，研究用自动机(automata)模拟人类的思维过程和智能行为。341.8.1 更新的理论框架 人工智能尚存在的问题：宏观与微观隔离 全局与局部割裂 理论和实际脱节 351.8.2 更好的技术集成 人工智能技术是其它信息处理技术及相关学科技术的集成。要集成的信息技术除数字技术外，还包括计算机网络、远程通信、数据库、计算机图形学、语音与听觉、机器人学、过程控制、并行计算、光计算、生物信息处理等。未来的智能系统还要集成认知科学、心理学、社会学、语言学、系统学和哲学等。361.8.3 更成熟的应用方法 期望研究出通用而

13、有效的人工智能开发方法：更高级的AI通用语言；更有效的AI专用语言与开发环境或工具。37人 工 智 能 基 础第二章 知识表示2.1 概述2.2 状态空间法2.3 问题归约法2.4 谓词逻辑法2.5 语义网络法2.6 其他方法392.1 概述 知识及知识表示 人工智能系统所关心的知识及其分类 知识表示应该注意的问题402.2 状态空间法 问题求解技术包括 问题的建模与表示 求解的方法 状态空间法三要点 状态（state）算符（operator）状态空间方法412.2.1 问题状态描述 定义 状态：描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合。算符：使问题从一种状态变化

14、为另一种状态的手段称为操作符或算符。问题的状态空间：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。4243OriginalStateMiddleStateGoalState状态空间表示概念详释三数码难题44123123123312312312初始棋局目标棋局 有向图 路径 代价 图的显示说明 图的隐示说明45AB2.2.2 状态图示法 产生式系统（production system）一个总数据库（global database）：它含有与具体任务有关的信息随着应用情况的不同，这些数据库可能简单，或许复杂。一套规则：它对数据库进行操作运算。每条规则由左

15、部鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作。一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。462.2.3 状态空间表示举例 猴子和香蕉问题472.2.3 状态空间表示举例图图2.4 猴子和香蕉问题猴子和香蕉问题解题过程 用一个四元表列（W，x，Y，z）来表示这个问题状态。这个问题的操作（算符）如下：2 goto（U）表示猴子走到水平位置U或者用产生式规则表示为（W，0，Y，z）goto（U）（U，0，Y，z）48 pushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z）pushbox（V）（V，0，V，z）climbbox

16、猴子爬上箱顶，即有（W，0，W，z）climbbox （W，1，W，z）49 grasp猴子摘到香蕉，即有（c，1，c，0）grasp （c，1，c，1）该初始状态变换为目标状态的操作序列为goto(b),pushbox(c),climbbox,grasp5051(b，1，b，0)（U，0，b，0）（V，0，V，0）（c，1，c，0）（U，0，V，0）（c，1，c，1）（a，0，b，0）目标状态目标状态goto（U）goto（U）U=b，climbboxgoto（U）U=bpushbox（V）goto（U）U=V图图2.4 猴子和香蕉问题的状态空间图猴子和香蕉问题的状态空间图522.3 问题归

17、约法子问题子问题1子问题子问题n原始问题原始问题子问题集本本原原问问题题 问题归约表示的组成部分：一个初始问题描述；一套把问题变换为子问题的操作符；一套本原问题描述。问题归约的实质：从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。532.3 问题归约法2.3.1 问题归约描述 梵塔难题54123CBA解题过程（3个圆盘问题）551231231231231231231231232.3.2 与或图表示 与图、或图、与或图56ABCD与图ABC或图57BCDEFGAHMBCDEFGAN一些关于与或图的术语58HMBCDEFGAN父节点

18、与节点弧线或节点子节点终叶节点与或图定义59与或图例子与或图例子ttttttttt（a）（b）有解节点无解节点终叶节点 不可解节点的一般定义没有后裔的非终叶节点为不可解节点。全部后裔为不可解的非终叶节点且含有或后继节点，此非终叶节点才是不可解的。后裔至少有一个为不可解的非终叶节点且含有与后继节点，此非终叶节点才是不可解的。与或图构成规则60与或图定义梵塔问题归约图61（113）（123）（111）（113）（123）（122）（111）（333）（122）（322）（111）（122）（322）（333）（321）（331）（322）（321）（331）（333）2.3.3 问题归约机理 关键

19、算符 具有决定性作用的算符叫做关键算符 差别 寻找候选关键算符的一种方法涉及计算某个问题（S，F，G）的差别。粗略地说，问题（S，F，G）的差别就是用S的元对由集合G规定的目标进行测试失败原因的部分表列 62 合适公式（WFF，well-formed formulas）合适公式的递归定义合适公式的性质合适公式的真值等价（Equivalence)逻辑语句形式语言632.3.3 问题归约机理 2.4.1 谓词公式 原子公式的的定义：用P(x1，x2，xn)表示一个n元谓词公式，其中P为n元谓词，x1,x2,，xn为客体变量或变元。通常把P(x1,x2,xn)叫做谓词演算的原子公式，或原子谓词公式。

20、分子谓词公式 可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。642.4 谓词逻辑法 语法和语义基本符号谓词符号、变量符号、函数符号、常量符号、括号和逗号原子公式652.4.2 谓词演算 连词和量词(Connective&Quantifiers)连词与及合取（conjunction)或及析取（disjunction）蕴涵（Implication）非（Not）量词全称量词（Universal Quantifiers)存在量词(Existential Quantifiers)662.4.2 谓词演算2.4.3 置换与合一 置换概念假元推理全称化推理综合推理定义就是在该表达式中用置

21、换项置换变量性质可结合的不可交换的67 合一（Unification)合一：寻找项对变量的置换，以使两表达式一致。可合一：如果一个置换s作用于表达式集Ei的每个元素，则我们用Ei s来表示置换例的集。我们称表达式集Ei是可合一的。682.4.3 置换与合一2.5 产生式表示法 产生式的基本形式 通常用下列的形式表示：IF P THEN Q（如果 P 则 Q）或者P Q 产生式推理 如果已有产生式规则：P Q 并且观察到P，或者知识库中已有P，则可得到结论Q，或执行操作Q。692.6 语义网络法 语义网络的结构 定义 组成部分 词法 结构 过程 语义702.6.1 二元语义网络的表示 表示占有关

22、系和其它情况例：小燕是一只燕子，燕子是鸟；巢-1是小燕的巢，巢-1是巢中的一个。选择语义基元试图用一组基元来表示知识，以便简化表示，并可用简单的知识来表示更复杂的知识。712.6.2 多元语义网络的表示 谓词逻辑与语义网络等效72LIMINGMANISAISA（LIMING，MAN）或）或 MAN（LIMING）（语义网络）（语义网络）（谓词逻辑）（谓词逻辑）多元语义网络表示的实质把多元关系转化为一组二元关系的组合，或二元关系的合取。73R(XR(X1 1，X X2 2，X Xn n)R R1212(X(X1 1，X X2 2)R)R1313(X(X1 1，X X3 3)R R1n1n(X(X

23、1 1，X Xn n).R Rn-1 nn-1 n(X(Xn-1n-1，X Xn n)可转换为可转换为2.6.3 基于语义网络的知识推理 继承 在语义网络中所谓的继承是把对事物的描述从概念节点或类节点传递到实例节点。匹配 加注析取界限，并标记DIS，以免引起混淆。742.7 框架表示 框架理论及特点 框架理论概述 框架的特点 自然性 结构性 继承性 752.7 框架表示 框架的构成 框架通常由描述事物的各个方面的槽组成，每个槽可有若干个侧面，而每个侧面又可有若干个值 框架的推理 框架包含它所描述的情况或物体的多方面的信息 框架包含物体必须具有的属性 框架描述它们所代表的概念的典型事例 762.

24、8 面向对象表示 面向对象的概念 一切事物都是对象 任何系统都是由对象构成的，系统本身也是对象 系统的发展和进化过程都是由系统的内部对象和外部对象之间（也包括内部对象与内部对象之间）的相互作用完成的 面向对象表示中的类继承 772.8 面向对象表示 面向对象表示的推理实例 说明面向对象程序设计中实现封装性的例子 说明面向对象程序设计中实现继承性的例子 说明面向对象程序设计中实现多态性的例子 782.9 剧本表示 剧本的构成 开场条件 角色 道具 场景 结果 剧本的推理 792.10 过程表示 过程式（procedure）表示就是将有关某一问题领域的知识，连同如何使用这些知识的方法，均隐式地表达

25、为一个求解问题的过程。从程序求解问题的效率上来说，过程式表达要比陈述式表达高得多。8081方法初始问题算符目标结果 状态 空间法 归约法 谓词逻辑法 语义网络法状态状态节点节点合适公式合适公式节点节点算符算符弧弧 子句集子句集（set of clause）置换合一置换合一消解反演消解反演链链目标状态目标状态节点节点根节点根节点目标网络目标网络解答路径解答路径（path）解答树解答树（tree）nil语义网络语义网络知识表示方法间的关系知识表示方法间的关系人 工 智 能 基 础82第三章 搜索原理3.1 盲目搜索3.2 启发式搜索3.3 博弈树搜索3.4 遗传算法3.5 模拟退火算法3.6 免疫

26、算法3.1 盲目搜索3.1.1 图搜索策略 一种在图中寻找路径的方法图中每个节点对应一个状态，每条连线对应一个操作符。这些节点和连线(即状态与操作符)又分别由产生式系统的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。OPEN表和CLOSED表 图搜索过程框图8485开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向重排OPEN表失败成功图3.2 图搜索过程框图是是否否3.1.1 图搜索策略 盲目搜索 特点：不需重排OPEN

27、表 种类：宽度优先、深度优先、等代价搜索等。启发式搜索 特点：重排OPEN表，选择最有希望的节点加以扩展。种类：有序搜索、A*算法等。863.1.2 宽度优先搜索 定义 以接近起始节点的程度逐层扩展节点的搜索方法。特点：一种高代价搜索，但若有解存在，则必能找到它。算法8788开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表是否有后继节点为目标节点？扩展n，把n的后继节点放入OPEN表的末端，提供返回节点n的指针失败成功图3.4 宽度优先算法框图是否是否3.1.2 宽度优先搜索 八数码难题（8-puzzle problem）8912384567123845

28、67（目标状态）（初始状态）规定：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。901238456712384123845674123856712 384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345图3.5 八数码难题的宽度优先搜索树1456123845671238456712384567123845671 2384567232425262723782212384567123845671 238456712 384567123845

29、67123845671238456714151617181920211238456743.1.3 深度优先搜索 定义 首先扩展最新产生的(即最深的)节点。算法 防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度深度界限。与宽度优先搜索算法最根本的不同在于：将扩展的后继节点放在OPEN表的前端。91 3.1.4 等代价搜索 定义 是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。算法 若所有连接弧线具有相等代价，则简化为宽度优先搜索算法。9293开始把S放入OPEN表OPEN表为空表？

30、把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点为目标节点？失败成功图3.9 等代价搜索算法框图是否是否令g(s)=0S是否目标节点？是成功扩展i，计算其后继节点j的g(j)，并把后继节点放入OPEN表否3.2 启发式搜索3.2.1 启发式搜索策略 盲目搜索可能带来组合爆炸 启发式信息 用来加速搜索过程的有关问题领域的特征信息，按其用途分为：用于决定要扩展的下一个节点，以免像在宽度优先或深度优先搜索中那样盲目地扩展。在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。用于决定某些应该从搜索树中抛弃或修剪的节点。943.2.1

31、启发式搜索策略 估价函数 获得某些节点“希望”的启发信息 f(n)表示节点n的估价函数值 重排OPEN表3.2.2 有序搜索 实质 选择OPEN表上具有最小f值的节点作为下一个节点。9596开始把S放入OPEN表，计算估价函数 f(s)OPEN表为空表？选取OPEN表中f值最小的节点i放入CLOSED表i为目标节点吗？扩展i，得后继节点j，计算f(j)，提供返回节点i的指针，利用f(j)对OPEN表重新排序，调整亲子关系及指针失败成功图3.10 有序搜索算法框图是否是否3.2.2 有序搜索 八数码难题（8-puzzle problem）9712384567（目标状态）12384567（初始状态

32、）985714563123845671238456712384567（4）（6）（6）2123845671238456712384567（6）（5）（5）1238456712 384567（5）（7）1238456712384567（6）（7）12384567（5）813245671 2384567（5）（7）图3.11 八数码难题的有序搜索树123846（4）73.2.3 A*算法 估价函数 对节点n定义f*(n)=g*(n)+h*(n),表示从S开始约束通过节点n的一条最佳路径的代价。希望估价函数f 定义为：f(n)=g(n)+h(n)g是g*的估计，h是h*的估计 A*算法的定义 定义3

33、.3 定义3.4 定义3.5993.3 博弈树搜索3.3.1 博弈概述 对垒的MAX、MIN双方轮流采取行动，博弈的结果只有三种情况。在对垒过程中，任何一方都了解当前的格局及过去的历史。任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选取对自已为最有利而对对方最为不利的对策。1003.3.2 极小极大分析法 设博弈的双方中一方为MAX，另一方为MIN。找到当前的最优行动方案。定义一个估价函数，用来估算当前博弈树端节点的得分。当端节点的估值计算出来后，再推算出父节点的得分(倒推值)。获得较大的倒推值的方案，是最好的行动方案。1013.3.3 -剪枝技术 剪枝 对于一个与节点MIN，若能

34、估计出其倒推值的上界，并且这个值不大于 MIN的父节点(一定是或节点)的估计倒推值的下界，即，则就不必再扩展该 MIN节点的其余子节点了（因为这些节点的估值对MIN父节点的倒推值已无任何影响了）。1023.3.3 -剪枝技术 剪枝 对于一个或节点MAX，若能估计出其倒推值的下界，并且这个值不小于 MAX的父节点（一定是与节点）的估计倒推值的上界，即，则就不必再扩展该MAX节点的其余子节点了（因为这些节点的估值对MAX父节点的倒推值已无任何影响了）。1033.4 遗传算法 遗传算法的基本原理 编码与译码 适应度函数 遗传操作 控制参数 1043.4.2 遗传算法的结构 简单遗传算法的求解步骤 初

35、始化群体;计算群体上每个个体的适应度值;按由个体适应度值所决定的某个规则选择将进入下一代的个体;按概率Pc进行交叉操作;按概率Pc进行突变操作;没有满足某种停止条件，则转第步，否则进入。输出种群中适应度值最优的染色体作为问题的满意解或最优解。1053.4.3 遗传算法的性能 遗传算法性能的影响因素 种群的规模要适当 适应度函数的构造 交叉和变异操作 1063.5 模拟退火算法3.5.1 模拟退火算法的模型 解空间 目标函数 初始解 模拟退火的基本思想 模拟退火算法新解的产生和接受的几个步骤1073.5.2 模拟退火算法的简单应用 旅行商问题 解空间解空间S是遍访每个城市恰好一次的所有回路，是1

36、，n的所有循环排列的集合，S中的成员记为(w1,w2,，wn)，并记wn+1=w1。初始解可选为(1，n)。目标函数 此时的目标函数即为访问所有城市的路径总长度，或称为代价函数。1083.5.2 模拟退火算法的简单应用 模拟退火算法求解TSP问题的伪程序：begin init-of-T;T为初始温度S=1，n;S为初始值termination=false;while termination=falsebegin for i=1 to L dobegingenerate(Sform S);从当前回路S产生新回路St:=f(S)-f(S);f(S)为路径总长IF(tRandom-of-0,1)S=

37、S;IF the-halt-condition-is-TRUE THEN termination=true;End;T_lower;End;End 1093.5.3 模拟退火算法参数控制问题 模拟退火算法应用广泛，可解NP完全问题，但参数难以控制，表现为以下三点：温度T的初始值设置问题。退火速度问题。温度管理问题。1103.6 免疫算法 3.6.1 免疫计算概述 人工免疫系统（artificial immune system）基于生物免疫机制寻找解决科学和工程中实际问题的智能方法 免疫计算 与人工免疫系统相应的计算方法 1113.6.2 免疫算法的基本原理 免疫算法（Immune Algori

38、thm）在模仿生物免疫机制的基础上，综合基因进化机理，人工地构造的一类优化算法，它实现了类似于免疫系统的自我调节功能和生成不同抗体的功能。人工免疫算法（Artificial Immune Algorithm）是针对人体免疫系统而言，因为人体免疫系统已经发展到了相当完美的程度，其中的“玄机”必是蕴涵着重大的科研价值。1123.6.2 免疫算法的基本原理 抗原（antigen）在免疫算法中抗原是指非最佳个体的基因，或者是可能错误的基因 疫苗（vanccine）在免疫算法中疫苗是指根据已有的先验知识得到的关于对最佳个体的一个估计值 抗体（antibody）在免疫算法中抗体是指根据疫苗修正某个个体基因

39、所得到的新个体（新基因）1133.6.2 免疫算法的基本原理114图 3.17 人工免疫算法流程图 抗原识别产生初始抗体群计算亲和力和排斥力产生新抗体并计算其亲和力和排斥力满足结束条件？利用免疫算子产生新的抗体群结束更新记忆单元是否3.6.3 几种免疫算法 基于信息熵的免疫算法 反向选择算法 免疫遗传算法 克隆选择算法 基于疫苗的免疫算法 基于免疫网络的免疫算法 115人 工 智 能 基 础第四章 推理技术4.1 消解原理4.2 规则演绎系统4.3 产生式系统4.4 定性推理4.5 不确定性推理4.6 非单调推理4.1 消解原理 原子公式（atomic formulas）文字一个原子公式及其否

40、定。子句由文字的析取组成的合适公式。消解对谓词演算公式进行分解和化简，消去一些符号，以求得导出子句。1184.1.1 化为子句集 步骤 消去蕴涵符号 减少否定符号辖域 对变量标准化 消去存在量词 化为前束形 把母式化为合取范式 消去全称量词 消去连词符号 更换变量名称119举例：举例：(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)120(1)消去蕴涵符号只应用和符号，以AB替换AB。(1)(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)4.1.1 化为子句集(2)减少否定符号的辖域每个否定符号最多只用到一个谓词符号上，并反复应用狄摩根定律。(3)对

41、变量标准化对哑元（虚构变量）改名，以保证每个量词有其自己唯一的哑元。121(2)(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)(3)(x)P(x)(y)P(y)P(f(x,y)(w)Q(x,w)P(w)(4)消去存在量词 以Skolem函数代替存在量词内的约束变量，然后消去存在量词(5)化为前束形 把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。前束形=前缀 母式 全称量词串 无量词公式122(4)(x)P(x)(y)P(y)P(f(x,y)Q(x,g(x)）P(g(x)式中，w=g(x)为一Skolem函数。(5)(x)(y)P(x)P

42、(y)P(f(x,y)Q(x,g(x)P(g(x)(6)把母式化为合取范式任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。(7)消去全称量词所有余下的量词均被全称量词量化了。消去前缀，即消去明显出现的全称量词。123(6)(x)(y)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)(7)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)(8)消去连词符号用A,B代替(AB)，消去符号。最后得到一个有限集，其中每个公式是文字的析取。(9)更换变量名称可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。

43、124(8)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)(9)P(x1)P(y)Pf(x1,y)P(x2)Qx2,g(x2)P(x3)Pg(x3)4.1.2 消解推理规则 消解式的定义 令L1，L2为两任意原子公式；L1和L2具有相同的谓词符号，但一般具有不同的变量。已知两子句L1和L2，如果L1和L2具有最一般合一，那么通过消解可以从这两个父辈子句推导出一个新子句()。这个新子句叫做消解式。消解式求法 取各子句的析取，然后消去互补对。1254.1.2 消解推理规则 假言推理 合并 重言式 空子句（矛盾）链式（三段论）1264.1.3 含有变量的消解式 含有变量

44、的子句之消解式 要把消解推理规则推广到含有变量的子句，必须找到一个作用于父辈子句的置换，使父辈子句含有互补文字。127Px,f(y)Q(x)Rf(a),y Pf(f(a),zR(z，w)Q f(f(a)R(f(a)，y)R(f(y)，w)=f(f(a)/x,f(y)/z4.1.4 消解反演求解过程 消解反演 给出S，L 否定L，得L；把L添加到S中去；把新产生的集合L，S化成子句集；应用消解原理，力图推导出一个表示矛盾的空子句 例子储蓄问题前提：每个储蓄钱的人都获得利息。结论：如果没有利息，那么就没有人去储蓄钱。128(1)规定原子公式：S(x,y)表示“x储蓄y”M(x)表示“x是钱”I(x

45、)表示“x是利息”E(x，y)表示“x获得y”证明：129(2)用谓词公式表示前提和结论：前提：(x)(y)(S(x,y)M(y)(y)(I(y)E(x,y)结论：(x)I(x)(x)(y)(M(y)S(x,y)(3)化为子句形130(4)消解反演求NIL图4.2 储蓄问题反演树子句（1）子句（3）f(x)/zM(b)NIL子句（5）子句（7）子句（4）a/x,b/yS(x,y)M(y)子句（6）4.1.4 消解反演求解过程 反演求解过程 从反演树求取答案步骤 把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去。按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。用根部

46、的子句作为一个回答语句。实质 把一棵根部有NIL的反演树变换为根部带有回 答语句的一棵证明树。1314.2 规则演绎系统 定义 基于规则的问题求解系统运用IfThen规则来建立，每个if可能与某断言(assertion)集中的一个或多个断言匹配。有时把该断言集称为工作内存，then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统。在这种系统中，通常称每个if部分为前项，称每个then部分为后项。1324.2.1 正向规则演绎系统 定义 正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从if到then的方向进行推理的。求解过程 事实表达式的与或形

47、变换 在基于规则的正向演绎系统中，我们把事实表示为非蕴涵形式的与或形，作为系统的总数据库。1334.2.1 正向规则演绎系统 事实表达式的与或图表示134Q(w,A)R(v)P(v)S(A,v)Q(w,A)R(v)P(v)S(A,v)R(v)P(v)S(A,v)R(v)P(v)图4.5 一个事实表达式的与或树表示4.2.1 正向规则演绎系统 与或图的F规则变换这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。我们把允许用作规则的公式类型限制为下列形式：L W 式中：L是单文字；W为与或形的唯一公式。1354.2.2 逆向规则演绎系统 定义 逆向规则演绎系统是从then向if进行推

48、理的，即从目标或动作向事实或状况条件进行推理的。求解过程 目标表达式的与或形式 与或图的B规则变换 作为终止条件的事实节点的一致解图1364.2.3 双向规则演绎系统 正向和逆向规则演绎系统各有利弊 结合正向和逆向规则演绎系统的优点 建立在正向和逆向规则演绎系统相结合的基础上 总数据库由表示目标和表示事实的两个与或图结构组成 分别用正向系统的F规则和逆向系统的B规则来修正1374.3 产生式系统 定义 用来描述若干个不同的以一个基本概念为基础的系统。这个基本概念就是产生式规则或产生式条件和操作对的概念。实质 论域的知识分为两部分：用事实表示静态知识，如事物、事件和它们之间的关系；用产生式规则表

49、示推理过程和行为。1384.3.1 产生式系统的结构 产生式规则 总数据库 控制策略139控制策略图4.12 产生式系统的组成结构总数据库产生式规则4.3.1 产生式系统的结构 选择规则到执行操作的步骤 匹配把当前数据库与规则的条件部分相匹配。冲突当有一条以上规则的条件部分和当前数据库相匹配 时，就需要决定首先使用哪一条规则，这称为冲突解决。操作操作就是执行规则的操作部分。1404.3.2 产生式系统的表示 事实的表示 树状结构 网状结构 规则的表示 单个规则的表示 规则间的关系 规则按参数分类 网状结构 1414.3.3 产生式系统的推理 正向推理 从一组表示事实的谓词或命题出发，使用一组产

50、生式规则，用以证明该谓词公式或命题是否成立。逆向推理 从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先提出一批假设目标，然后逐一验证这些假设。双向推理 双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配。1424.3.4 产生式系统示例143图4.20 网上产生式系统4.4 定性推理4.4.1 定性推理概述 定性推理（qualitative reasoning）是从物理系统（包括自然系统和人造系统）的结构描述出发，以定性方法研究系统的结构、行为、功能以及它们之间的因果关系等，目的是预测系统的行为并给出合理的解释