第1章绪论

人工智能的基本概念

智能的特征

智能的定义：智能是知识与智力的总和。知识是一切智能行为的基础，智力是获取知识并应用知识求解问题的能力。

智能的特征：具有感知能力、记忆与思维能力、学习能力、行为能力（表达能力）等特征。

感知能力：通过视觉、听觉、触觉、嗅觉等感觉器官感知外部世界的能力。
记忆与思维能力：存储由感知器官感知到的外部信息以及由思维所产生的知识对信息进行处理
学习能力：学习既可能是自觉的、有意识的，也可能是不自觉的、无意识的；既可以是有教师指导的，也可以是通过自己实践的。
行为能力：信息的输出。

人工智能定义

人工智能：用人工的方法在机器（计算机）上实现的智能；或者说是人们是机器具有类似于人的智能。

图灵测试和中文屋实验

图灵测试：测试者和被测试者（一个人和一台机器）在隔开的情况下，通过一些装置（如键盘）向被测试者随意提问，进行多次测试后，如果机器让平均每个参与者做出超过30%的误判（误认为是人类所答），那么这台机器就通过了测试，并被认为具有人类智能。

中文屋实验：锁在屋里的看不懂卡片上汉字的人，根据英文说明书把从门缝里得到的汉字与屋内的汉字进行匹配然后扔出去，从外观上看好像这个人懂中文，而且正确匹配的速度会越来越快，实际上他不懂中文。

证明：即使通过图灵测试也不能说明计算机能思维。

人工智能研究的基本内容

人工智能研究内容

人工智能研究：知识表示、机器感知、机器思维、机器学习、机器行为。

知识表示：将人类知识形式化或者模型化。

知识表示方法：符号表示法、连接机制表示法。

符号表示法：用各种包含具体含义的符号，以各种不同的方式和顺序组合起来表示知识的一类方法。例如，一阶谓词逻辑、产生式等。
连接机制表示法：把各种物理对象以不同的方式及顺序连接起来，并在其间互相传递及加工各种包含具体意义的信息，以此来表示相关的概念及知识。例如，神经网络等。

机器感知：使机器具有类似于人的感知能力。以机器视觉与机器听觉为主。

机器思维：对通过感知得来的外部信息及机器内部的各种工作信息进行有目的的处理。

机器学习：研究如何使计算机具有类似于人的学习能力，使它能通过学习自动地获取知识。

机器行为：计算机的表达能力，即“说”、“写”、“画”等能力。

人工智能学派：符号主义、连接主义、行为主义

人工智能的研究目标

远期目标：制造具有完全智能的机器。
近期目标：部分地或某种程度地实现机器智能。

人工智能研究领域

自动定理证明、博弈、模式识别、计算机视觉、自然语言处理、专家系统、自动程序设计、机器人、组合优化问题、人工神经网络、智能控制、仿真、CAD、管理决策、多媒体、通信、医疗

第2章知识表示与知识图谱

知识与知识表示的概念

知识的概念

知识：

在长期的生活及社会实践中、在科学研究及实验中积累起来的对客观世界的认识与经验。
把有关信息关联在一起所形成的信息结构
知识反映了客观世界中事物之间的关系，不同事物或者相同事物间的不同关系形成了不同的知识。

知识的特征：相对正确性、不确定性、可表示性、可利用性

任何知识都是在一定的条件及环境下产生的，在这种条件及环境下才是正确的。
造成知识不确定性的原因主要有随机性、模糊性、经验性和不完全性
知识可以用适当形式表示出来，如用语言、文字、图形、神经网络等。
知识可以被利用。

知识表示：将人类知识形式化或者模型化。

选择知识表示方法的原则：

充分表示领域知识。
有利于对知识的利用。
便于对知识的组织、维护与管理。
便于理解与实现。

知识的表示方法：一阶谓词逻辑表示法、产生式表示法、框架表示法、语义网络表示法（知识图谱）

一阶谓词逻辑表示法

命题

命题：一个非真即假的陈述句。

若命题的意义为真，称它的真值为真，记为 T。
若命题的意义为假，称它的真值为假，记为 F。
一个命题可在一种条件下为真，在另一种条件下为假。

命题逻辑：研究命题及命题之间关系的符号逻辑系统。

命题逻辑表示法特点：无法把它所描述的事物的结构及逻辑特征反映出来，也不能把不同事物间的共同特征表述出来。

谓词

谓词的一般形式：$P (x_1, x_2,…, x_n)$

个体$ x_1, x_2,…, x_n $：某个独立存在的事物或者某个抽象的概念；
- 个体是常量：一个或者一组指定的个体。
- 个体是变元（变量）：没有指定的一个或者一组个体。
- 个体是函数：一个个体到另一个个体的映射。
- 个体是谓词：个体就是另一种谓词。
谓词名 $P$：刻画个体的性质、状态或个体间的关系。

谓词公式

连接词(连词)

﹁： “否定” 或 “非”。
∨： “析取”或“或”。
∧： “合取”或“与”。
→：“蕴含”或 “条件”。
↔：“等价”或“双条件”。

谓词逻辑真值表

量词

全称量词（$\forall x$）：“对个体域中的所有（或任一个）个体 x
存在量词（$\exists x$）：“在个体域中存在个体 x

谓词公式

可按下述规则得到谓词演算的谓词公式：

单个谓词是谓词公式，称为原子谓词公式。
若A是谓词公式，则﹁A也是谓词公式。
若A，B都是谓词公式，则A∧B，A∨B，A→B，A↔B也都是谓词公式。
若A是谓词公式，则 ($\forall x$) A，($\exists x$)A也是谓词公式。
有限步应用上述规则生成的公式也是谓词公式。

连接词的优先级别从高到低排列：﹁， ∧， ∨， →，↔

量词的辖域：位于量词后面的单个谓词或者用括弧括起来的谓词公式。

约束变元与自由变元：辖域内与量词中同名的变元称为约束变元，不同名的变元称为自由变元。

谓词公式的性质

谓词公式的解释：

谓词公式在个体域上的解释：个体域中的实体对谓词演算表达式的每个常量、变量、谓词和函数符号的指派。
对于每一个解释，谓词公式都可求出一个真值（T或F）。

谓词公式的永真性、可满足性、不可满足性：

如果谓词公式P对个体域D上的任何一个解释都取得真值T，则称P在D上是永真的；如果P在每个非空个体域上均永真，则称P永真。
如果谓词公式P对个体域D上的任何一个解释都取得真值F，则称P在D上是永假的；如果P在每个非空个体域上均永假，则称P永假。
对于谓词公式P，如果至少存在一个解释使得P在此解释下的真值为T，则称P是可满足的，否则，则称P是不可满足的。

谓词公式的等价性

设P与Q是两个谓词公式，D是它们共同的个体域，若对D上的任何一个解释，P与Q都有相同的真值，则称公式P和Q在D上是等价的。如果D是任意个体域，则称P和Q是等价的，记为P↔Q 。
德.摩根律
- 对于两个命题 p 和 q，其表达形式为：¬(p∧q) ≡ (¬p)∨(¬q)，即：否定p 且 q等价于非 p 或非 q。
- 对于两个命题 p 和 q，其表达形式为：¬(p∨q) ≡ (¬p)∧(¬q)，即：否定 p 或 q 等价于非 p 且非 q。
连接词化规律（蕴含、等价等值式）
- 蕴含的表达式 p→q（如果 p，那么 q）可以通过其他逻辑运算符来表示：p→q ≡ ¬p∨q，解释：如果 p 为真，那么 q 必须为真；如果 p 为假，则 q 可以为真也可以为假，整个蕴含表达式仍为真。因此，蕴含可以等价地表示为非 p 或 q。
- 等价的表达式 p↔q（p 当且仅当 q，也叫“双向蕴含”）可以通过“与”、“或”和“非”来表示：p↔q ≡ (p→q)∧(q→p)
量词转换律
- 对全称量词 ∀x 的否定可以转化为存在量词 ∃x：¬(∀xP(x)) ≡ ∃x¬P(x)，意思是：并非所有 x 都满足 P(x)等价于存在一个 x 不满足 P(x)。
- 对存在量词 ∃x 的否定可以转化为全称量词 ∀x：¬(∃xP(x)) ≡ ∀x¬P(x)，意思是：不存在 x 满足 P(x)等价于对于所有 x 都不满足 P(x)。

谓词公式的永真蕴含

对于谓词公式P与Q，如果P→Q永真，则称公式P永真蕴含Q，且称Q为P的逻辑结论，称P为Q的前提，记为P→Q。
假言推理
- 肯定前件：前提1：如果 p，那么 q；前提2：p 成立。结论：因此，q 成立。符号表示：p→q , p∴q
- 否定后件：前提1：如果 p，那么 q；前提2：q 不成立。结论：因此，p 也不成立。符号表示：p→q , ¬q∴¬p
拒取式推理
- 如果 p 或 q 成立，且 p 不成立，那么 q 成立。符号表示：p∨q , ¬p∴q
假言三段论
- 前提1：如果 p，那么 q；前提2：如果 q，那么 r。结论：因此，如果 p，那么 r。符号表示：p→q,q→r∴p→r

谓词逻辑的其他推理规则

P规则：在推理的任何步骤上都可引入前提。
T规则：在推理过程中，如果前面步骤中有一个或多个公式永真蕴含公式S，则可把S引入推理过程中。(结论引用)
CP规则：如果能从任意引入的命题R和前提集合中推出S来，则可从前提集合推出R → S来。
反证法：P → Q，当且仅当P∧﹁Q↔F，即Q为P的逻辑结论，当且仅当P∧﹁Q是不可满足的。

一阶谓词逻辑知识表示方法

谓词公式表示知识的步骤

定义谓词及个体
变元赋值
用连接词连接各个谓词形成谓词公式

一阶谓词逻辑表示法的特点

优点
- 自然性
- 精确性
- 严密性
- 容易实现
局限性
- 不能表示不确定的知识
- 组合爆炸
- 效率低

产生式表示法

产生式

产生式通常用于表示事实、规则以及它们的不确定性度量，适合于表示事实性知识和规则性知识。

确定性规则知识的产生式表示
- 基本形式： IF P THEN Q
- 或者：P → Q
不确定性规则知识的产生式表示
- 基本形式： IF P THEN Q （置信度）
- 或者：P → Q（置信度）
确定性事实性知识的产生式表示
- 三元组表示：（对象，属性，值）
- 或者：（关系，对象1，对象2）
不确定性事实性知识的产生式表示
- 四元组表示：（对象，属性，值，置信度）
- 或者：（关系，对象1，对象2，置信度）

产生式与谓词逻辑中的蕴含式的区别：

除逻辑蕴含外，产生式还包括各种操作、规则、变换、算子、函数等。
蕴含式只能表示精确知识，而产生式不仅可以表示精确的知识，还可以表示不精确知识。

产生式的形式描述及语义——巴科斯范式BNF：

<产生式>::=<前提> <结论>
<前提>::=<简单条件>|<复合条件>
<结论>::=<事实>|<操作>
<复合条件>::=<简单条件>AND<简单条件>[AND<简单条件>…

                      |<简单条件>OR<简单条件>[OR<简单条件>…

<操作>::=<操作名>[(<变元>，…)]

符号“::=”表示“定义为”；符号“|”表示“或者是”；符号“[ ]”表示“可缺省”。

产生式系统

产生式系统的基本结构：

规则库: 用于描述相应领域内知识的产生式集合。

综合数据库：一个用于存放问题求解过程中各种当前信息的数据结构。

控制系统：由一组程序组成，负责整个产生式系统的运行，实现对问题的求解。

控制系统做以下几项工作：推理、冲突消解、执行规则、检查推理终止条件

从规则库中选择与综合数据库中的已知事实进行匹配。
匹配成功的规则可能不止一条，进行冲突消解。
执行某一规则时，如果其右部是一个或多个结论，则把这些结论加入到综合数据库中：如果其右部是一个或多个操作，则执行这些操作。
对于不确定性知识，在执行每一条规则时还要按一定的算法计算结论的不确定性。
检查综合数据库中是否包含了最终结论，决定是否停止系统的运行。

产生式表示法的特点

产生式表示法的优点：自然性、模块性、有效性、清晰性

产生式表示法的缺点：效率不高、不能表达结构性知识

适合产生式表示的知识：

领域知识间关系不密切，不存在结构关系。
经验性及不确定性的知识，且相关领域中对这些知识没有严格、统一的理论。
领域问题的求解过程可被表示为一系列相对独立的操作，且每个操作可被表示为一条或多条产生式规则。

框架表示法

框架表示法：一种结构化的知识表示方法

框架的一般结构

框架：一种描述所论对象属性的数据结构。

一个框架由若干个被称为“槽”的结构组成，每一个槽又可根据实际情况划分为若干个“侧面”。
一个槽用于描述所论对象某一方面的属性。
一个侧面用于描述相应属性的一个方面。
槽和侧面所具有的属性值分别被称为槽值和侧面值。

框架表示法的特点

结构性 ：便于表达结构性知识，能够将知识的内部结构关系及知识间的联系表示出来。
继承性 ：框架网络中，下层框架可以继承上层框架的槽值，也可以进行补充和修改。
自然性 ：框架表示法与人在观察事物时的思维活动是一致的。

知识图谱

知识图谱：是一种互联网环境下的知识表示方法。

知识图谱的定义

知识图谱：又称科学知识图谱，用各种不同的图形等可视化技术描述知识资源及其载体，挖掘、分析、构建、绘制和显示知识及它们之间的相互联系。

知识图谱是由一些相互连接的实体及其属性构成的。

三元组是知识图谱的一种通用表示方式：

(实体1-关系-实体2)：中国-首都-北京
(实体-属性-属性值)：北京-人口-2069万

知识图谱的架构

知识图谱在逻辑上分为数据层和模式层

数据层主要是由一系列的事实组成，而知识以事实为单位进行存储。
模式层构建在数据层之上，是知识图谱的核心。

获取知识的资源对象大体可分为：结构化数据、半结构化数据、非结构化数据

结构化数据是指知识定义和表示都比较完备的数据。
半结构化数据是指部分数据是结构化的，但存在大量结构化程度较低的数据。
非结构化数据是指没有定义和规范约束的“自由”数据。

知识图谱的构建

自顶向下：指的是先为知识图谱定义好本体与数据模式，再将实体加入到知识库。

自底向上：指的是从一些开放链接数据中提取出实体，选择其中置信度较高的加入到知识库，再构建顶层的本体模式。

第3章确定性推理方法

推理的基本概念

推理：通过已知事实和知识通过某种策略得到结论的过程。

推理方式及其分类

演绎推理、归纳推理、默认推理

演绎推理 : 一般 → 个别

三段论式（三段论法）

例子：足球运动员的身体都是强壮的（大前提）；高波是一名足球运动员（小前提）；所以，高波的身体是强壮的。

归纳推理 : 个别 → 一般

完全归纳推理（必然性推理）
例子：检查全部产品合格，所以该厂产品合格（完全归纳推理）
不完全归纳推理（非必然性推理）
例子：检查全部样品合格，所以该厂产品合格（不完全归纳推理）

默认推理（缺省推理）知识不完全的情况下假设某些条件已经具备所进行的推理。

例子：制造鸟笼；鸟会飞?（默认成立）。结论鸟笼要有盖子

确定性推理、不确定性推理

确定性推理：推理时所用的知识与证据都是确定的，推出的结论也是确定的，其真值或者为真或者为假。
不确定性推理：推理时所用的知识与证据不都是确定的，推出的结论也是不确定的。

似然推理（概率论）
近似推理或模糊推理（模糊逻辑）

单调推理、非单调推理

单调推理：随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。
非单调推理：由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前面的某一步，重新开始。

启发式推理、非启发式推理

启发式知识：与问题有关且能加快推理过程、提高搜索效率的知识。

推理的方向

推理方向：正向推理、逆向推理、混合推理、双向推理

正向推理（事实驱动推理）: 已知事实 → 结论
- 实现正向推理需要解决的问题：
  - 确定匹配（知识与已知事实）的方法。
  - 按什么策略搜索知识库。
  - 冲突消解策略。
- 正向推理的特点：正向推理简单，易实现，但目的性不强，效率低。
逆向推理（目标驱动推理）：以某个假设目标作为出发点。
- 主要优点：不必使用与目标无关的知识，目的性强，同时它还有利于向用户提供解释。
- 主要缺点：起始目标的选择有盲目性。
混合推理
- 正反向混合推理
  - 先正向后逆向：先进行正向推理，帮助选择某个目标，即从已知事实演绎出部分结果，然后再用逆向推理证实该目标或提高其可信度；
  - 先逆向后正向：先假设一个目标进行逆向推理，然后再利用逆向推理中得到的信息进行正向推理，以推出更多的结论。
- 混合推理适用于以下几种情况
  - 已知的事实不充分
  - 正向推理推出的结论可信度不高
  - 希望得到更多的结论

冲突消解策略

已知事实和知识发生多种匹配（一对多、多对一、多对多）时才会产生冲突。

按一定的策略从匹配成功的多个知识中挑出一个知识用于当前的推理的过程称为冲突消解。

按针对性排序（包含更多的条件）
按已知事实的新鲜性排序（后生成的事实）
按匹配度排序（不确定性推理）
按条件个数排序（优先应用条件少的规则）

自然演绎推理

自然演绎推理：从一组已知为真的事实出发，运用经典逻辑的推理规则推出结论的过程。

推理规则：P规则、T规则、假言推理、拒取式推理

假言推理：p → P, P → Q；p → Q

例子：“如果x是金属，则x能导电” , “铜是金属” 推出 “铜能导电”

拒取式推理： P → Q, ﹁Q → ﹁P

例子：“如果下雨，则地下就湿” , “地上不湿” 推出 “没有下雨”

两种错误：否定前件、肯定后件

否定前件： P→Q, ﹁P无法推断﹁Q
- 例子：如果下雨，则地上是湿的（ P→Q ）；没有下雨（﹁P ）得不到地上不湿（﹁Q ）。
肯定后件： P→Q, Q无法推断P
- 例子：如果行星系统是以太阳为中心的，则金星会显示出位相变化（ P→Q ）；金星显示出位相变化（ Q ）得不到行星系统是以太阳为中心（ P ）。

优点：

表达定理证明过程自然，易理解。
拥有丰富的推理规则，推理过程灵活。
便于嵌入领域启发式知识。

缺点：易产生组合爆炸，得到的中间结论一般呈指数形式递增。

归结演绎推理

反证法： P→Q，当且仅当 P∧﹁Q↔F，即 Q为 P 的逻辑结论，当且仅当是不可满足的。

$Q$ 为 ,$P_1, P_2, \dots, P_n$ 的逻辑结论，当且仅当$(P_1 \land P_2 \land \dots \land P_n) \land \neg Q$是不可满足的。

思路：P→Q得到 P∧﹁Q不可满足得到子句集不可满足，在这种情况下使用鲁宾逊归结原理、海伯伦定理

谓词公式化子句集的方法

原子谓词公式：一个不能再分解的命题。

文字：原子谓词公式及其否定。

$P$：正文字，﹁$P$：负文字。

子句：任何文字的析取式。任何文字本身也都是子句。

空子句：不包含任何文字的子句。空子句是永假的，不可满足的。

子句集：由子句构成的集合。

将谓词逻辑公式化为子句集步骤

消除蕴含和等价

将公式中的蕴含$ (P \rightarrow Q ) $转换为 $(\neg P \vee Q )$。
将公式中的等价$ (P \leftrightarrow Q ) $转换为$ ((P \rightarrow Q) \wedge (Q \rightarrow P) )$。

标准化量词

转换为前束范式：将公式中的量词移到公式的最前面，量词统一排列。
例：$ (\forall x (P(x) \rightarrow \exists y Q(x, y)) ) $转换为$ (\forall x \exists y (P(x) \rightarrow Q(x, y)) )$。

消除存在量词

通过Skolem化方法消除存在量词。存在量词 $(\exists y ) $的引入会被一个函数替代，通常这个函数的参数是所有自由变量。
例如：$(\exists y \, Q(x, y) ) $可以通过引入一个Skolem函数 $(f(x) ) $来转换为 $(Q(x, f(x)) )$。

将公式转换为子句形式

公式被转化为一个以合取连接的子句的集合。每个子句是一个析取的文字，文字是谓词或其否定。
对于量词部分已经消除的公式，通过分配律将公式转化为合取范式：
- 例如：$((A \vee B) \wedge (C \vee D) )$ 其中 (A, B, C, D ) 是文字。

去掉量词，得到子句集

最终，量词被移除，得到的公式就是由子句（字面）的合取组成的子句集。每个子句是一个文字的析取。

例子

假设我们有以下谓词逻辑公式：

$
\forall x \exists y (P(x) \rightarrow Q(x, y)) \wedge \forall x (R(x) \vee \neg Q(x, f(x)))
$

消除蕴含：
$
\forall x \exists y (\neg P(x) \vee Q(x, y)) \wedge \forall x (R(x) \vee \neg Q(x, f(x)))
$
消除存在量词（Skolem化）：
- (\exists y ) 被替换为 Skolem 函数 (f(x) )：
  $
  \forall x (\neg P(x) \vee Q(x, f(x))) \wedge \forall x (R(x) \vee \neg Q(x, f(x)))
  $
去掉量词，得到子句集：
- 子句集形式：
  $
  { \neg P(x) \vee Q(x, f(x)), R(x) \vee \neg Q(x, f(x)) }
  $

谓词公式不可满足的充要条件是其子句集不可满足。

鲁宾逊归结原理

子句集中子句之间是合取关系，只要有一个子句不可满足，则子句集就不可满足。

鲁宾逊归结原理（消解原理）的基本思想：

检查子句集 S 中是否包含空子句，若包含，则 S 不可满足。
若不包含，在 S 中选择合适的子句进行归结，一旦归结出空子句，就说明 S 是不可满足的。

命题逻辑中的归结原理（基子句的归结）

定义3.1（归结）：设$C_1$与$C_2$是子句集中的任意两个子句，如果 $C_1$中的文字$L_1$与 $C_2$中的文字$L_2$互补，那么从$C_1$和 $C_2$中分别消去$L_1$和$L_2$，并将二个子句中余下的部分析取，构成一个新子句$C_{12}$ 。

定理3.2：归结式$C_{12}$是其亲本子句$C_1$与$C_2$的逻辑结论。即如果$ C_1$与$C_2$为真，则$C_{12}$为真。

推论1：设$C_1$与$C_2$是子句集$S$中的两个子句，$C_{12}$是它们的归结式，若用$C_{12}$代替$C_1$与$C_2$后得到新子句集$S_1$，则由$S_1$不可满足性可推出原子句集$S$的不可满足性，即：$S_1$的不可满足性 $\rightarrow S$的不可满足性

推论2：设C1与C2是子句集S中的两个子句，C12是它们的归结式，若C12 加入原子句集S，得到新子句集S1，则S与S1在不可满足的意义上是等价的，即：$S_1$的不可满足性 $\rightarrow S$的不可满足性

谓词逻辑中的归结原理（含有变元的子句的归结）

定义 3.2：设$ C_1 $与$ C_2 $是两个没有相同变元的子句，$L_1$和 $L_2$分别是 $C_1$和 $C_2$ 中的文字，若 $\sigma$ 是 $L_1$ 和 $L_2$ 的 最一般合一，则称$C_{12} = (C_1 \sigma - \{ L_1 \sigma \}) \vee (C_2 \sigma - \{ L_2 \sigma \})$为 $C_1$ 和 $C_2$ 的二元归结式。

给定两个逻辑表达式（或谓词）$L_1$和 $L_2$，如果存在一个替换$ \sigma $可以将它们变得相同，那么我们称$ \sigma$是 $L_1$和 $L_2$的合一。可能存在多个合一，而最一般合一就是其中最“宽松”的一个。

对于谓词逻辑，归结式是其亲本子句的逻辑结论。

对于一阶谓词逻辑，即若子句集是不可满足的，则必存在一个从该子句集到空子句的归结演绎；若从子句集存在一个到空子句的演绎，则该子句集是不可满足的。

如果没有归结出空子句，则既不能说 S 不可满足，也不能说 S 是可满足的。

归结反演

应用归结原理证明定理的过程称为归结反演。

用归结反演证明的步骤是：

将已知前提表示为谓词公式 $F$。
将待证明的结论表示为谓词公式 $Q$，并否定得到 $\neg Q$。
把谓词公式集 $\{ F, \neg Q \}$ 化为子句集 $S$。
应用归结原理对于子句集 $S$ 中的子句进行归结，并把每次归结得到的归结式都并入到 $S$ 中。如此反复进行，若出现了空子句，则停止归结，此时就证明了 $Q$ 为真。

应用归结原理求解问题

应用归结原理求解问题的步骤：

已知前提 $F$ 用谓词公式表示，并化为子句集 $S$；
把待求解的问题 $Q$ 用谓词公式表示，并否定 $Q$，再与 $\text{ANSWER}$ 构成析取式 $(\neg Q \vee \text{ANSWER})$；
把 $(\neg Q \vee \text{ANSWER})$ 化为子句集，并入到子句集 $S$ 中，得到子句集 $S'$；
对 $S'$ 应用归结原理进行归结；
若得到归结式 $\text{ANSWER}$，则答案就在 $\text{ANSWER}$ 中。

第4章不确定性推理方法

不确定性推理中的基本问题

推理：从已知事实（证据）出发，通过运用相关知识逐步推出结论或者证明某个假设成立或不成立的思维过程。

不确定性推理：从不确定性的初始证据出发，通过运用不确定性的知识，最终推出具有一定程度的不确定性但却是合理或者近乎合理的结论的思维过程。

不确定性推理中的基本问题:

不确定性的表示与量度
- 知识不确定性的表示
  在专家系统中知识的不确定性一般是由领域专家给出的，通常是一个数值——知识的静态强度
- 证据不确定性的表示——证据的动态强度
  - 用户在求解问题时提供的初始证据。
  - 在推理中用前面推出的结论作为当前推理的证据。
- 不确定性的量度
  - 能充分表达相应知识及证据不确定性的程度。
  - 度量范围的指定便于领域专家及用户对不确定性的估计。
  - 便于对不确定性的传递进行计算，而且对结论算出的不确定性量度不能超出量度规定的范围。
  - 度量的确定应当是直观的，同时应有相应的理论依据。
不确定性匹配算法及阈值的选择
- 不确定性匹配算法：用来计算匹配双方相似程度的算法。
- 阈值：用来指出相似的“限度”。
组合证据不确定性的算法
最大最小方法、Hamacher方法、概率方法、有界方法、Einstein方法等。
不确定性的传递算法
- 在每一步推理中，如何把证据及知识的不确定性传递给结论。
- 在多步推理中，如何把初始证据的不确定性传递给最终结论。
结论不确定性的合成

可信度方法

可信度：根据经验对一个事物或现象为真的相信程度。

C－F模型：基于可信度表示的不确定性推理的基本方法。

知识不确定性的表示

产生式规则表示:

　　　　IF　　 E　　 THEN　　 H　　 (CF(H,E))

解释：如果E然后H，E的可能性是CF(H,E)

CF(H, E) ：可信度因子，反映前提条件与结论的联系强度。

CF（H，E）的取值范围: [-1,1]。
若由于相应证据的出现增加结论 H 为真的可信度，则 CF（H，E）> 0，证据的出现越是支持 H 为真，就使CF（H，E) 的值越大。
反之，CF（H，E）< 0，证据的出现越是支持 H 为假，CF（H，E）的值就越小。
若证据的出现与否与 H 无关，则 CF（H，E）= 0。

证据不确定性的表示

CF(E)＝0.6： E的可信度为0.6

证据E的可信度取值范围：[-1，1] 。
对于初始证据，若所有观察S能肯定它为真，则CF(E)= 1。
若肯定它为假，则 CF(E) = –1。
若以某种程度为真，则 0 < CF(E) < 1。
若以某种程度为假，则－1 < CF(E) < 0 。
若未获得任何相关的观察，则 CF(E) = 0。

静态强度CF（H，E）：知识的强度，即当 E 所对应的证据为真时对 H 的影响程度。

动态强度 CF（E）：证据 E 当前的不确定性程度。

组合证据不确定性的算法

多个单一证据的合取：

E = E₁ AND E₂ AND ⋯ AND Eₙ 则　CF(E) = min{CF(E₁), CF(E₂), ⋯, CF(Eₙ)}

多个单一证据的析取：

E = E₁ OR E₂ OR ⋯ OR Eₙ 则　CF(E) = max{CF(E₁), CF(E₂), ⋯, CF(Eₙ)}

不确定性的传递算法

C–F模型中的不确定性推理：从不确定的初始证据出发，通过运用相关的不确定性知识，最终推出结论并求出结论的可信度值。结论 H 的可信度由下式计算：

CF(H) = CF(H, E) × max{0, CF(E)}

当 CF(E) < 0 时，则 CF(H) = 0
当 CF(E) = 1 时，则 CF(H) = CF(H, E)

结论不确定性的合成算法

设知识：

　　　　IF　　 E₁　　 THEN　　 H　　 (CF(H, E₁))

　　　　IF　　 E₂　　 THEN　　 H　　 (CF(H, E₂))

（1）分别对每一条知识求出 CF(H)：

　　　　CF₁(H) = CF(H, E₁) × max{0, CF(E₁)}

　　　　CF₂(H) = CF(H, E₂) × max{0, CF(E₂)}

（2）求出 E₁ 与 E₂ 对 H 的综合影响所形成的可信度 CF₁,₂(H)：

$$ CF_{1,2}(H) = \begin{cases} CF_1(H) + CF_2(H) - CF_1(H) \cdot CF_2(H), & \text{若 } CF_1(H) \geq 0, \, CF_2(H) \geq 0 \\ CF_1(H) + CF_2(H) + CF_1(H) \cdot CF_2(H), & \text{若 } CF_1(H) < 0, \, CF_2(H) < 0 \\ \frac{CF_1(H) + CF_2(H)}{1 - \min\{|CF_1(H)|, |CF_2(H)|\}}, & \text{若 } CF_1(H) \text{ 与 } CF_2(H) \text{ 异号} \end{cases} $$

证据理论

概率分配函数

设 D 是变量 x 所有可能取值的集合，且 D 中的元素是互斥的，在任一时刻 x 都取且只能取 D 中的某一个元素为值，则称 D 为 x 的样本空间。

在证据理论中，D 的任何一个子集 A 都对应于一个关于 x 的命题，称该命题为“ x 的值是在 A 中”。

设 x ：所看到的颜色，D={红，黄，蓝}，
则 A={红}：“ x 是红色”；

 A={红，蓝}：“x 或者是红色，或者是蓝色”。

设 D为样本空间，领域内的命题都用 D 的子集表示，则概率分配函数定义如下：

定义 4.1 设函数$M: 2^D \rightarrow [0, 1]$，（对任何一个属于 D 的子集 A，命它对应一个数 $M \in [0, 1]$且满足：

$M(\varnothing) = 0$
$\sum_{A \subseteq D} M(A) = 1$

则 M是定义在 $2^D$上的基本概率分配函数，M(A):A的基本概率数。

几点说明：

设样本空间 D中有 n个元素，则 D中子集的个数为 $2^n$。
$2^D$：D 的所有子集。
概率分配函数：把 D 的任意一个子集 A 都映射为 [0, 1] 上的一个数 M(A)。
当 $A \subseteq D$, $A \neq D$ 时，M(A)：对相应命题 A 的精确信任度。
概率分配函数与概率不同。

信任函数

定义 4.2 命题的信任函数 Bel

$ Bel: 2^D \rightarrow [0, 1] $ 且 $ Bel(A) = \sum_{B \subseteq A} M(B) \quad \forall A \subseteq D $

$ Bel(A) $：对命题 $ A $ 为真的总的信任程度。

由信任函数及概率分配函数的定义推出：

$ Bel(\varnothing) = M(\varnothing) = 0 $
$ Bel(D) = \sum_{B \subseteq D} M(B) = 1 $

似然函数

似然函数：不可驳斥函数或上限函数。

定义 4.3 似然函数$Pl: 2^D \rightarrow [0,1] $且$ Pl(A) = 1 - Bel(\neg A) $对所有的$A \subseteq D $

概率分配函数的正交和（证据的组合）

以下是内容的行内数学公式表示：

定义 4.4 设 $ M_1 $ 和 $ M_2 $ 是两个概率分配函数；则其正交和 $ M = M_1 \oplus M_2 $：

$ M(\varnothing) = 0 $
$ M(A) = K^{-1} \sum_{x \cap y = A} M_1(x) M_2(y) $

其中：
$ K = 1 - \sum_{x \cap y = \varnothing} M_1(x) M_2(y) = \sum_{x \cap y \neq \varnothing} M_1(x) M_2(y) $

如果 $ K \neq 0 $，则正交和 $ M $ 也是一个概率分配函数；

如果 $ K = 0 $，则不存在正交和 $ M $，即没有可能存在概率函数，称 $ M_1 $ 与 $ M_2 $ 矛盾。

基于证据理论的不确定性推理

基于证据理论的不确定性推理的步骤：

建立问题的样本空间D
由经验给出，或者由随机性规则和事实的信度度量算基本概率分配函数。
计算所关心的子集的信任函数值、似然函数值。
由信任函数值、似然函数值得出结论。

模糊推理方法

模糊集合

模糊集合的定义

论域：所讨论的全体对象，用 U 等表示。

元素：论域中的每个对象，常用a,b,c,x,y,z表示。

集合：论域中具有某种相同属性的确定的、可以彼此区别的元素的全体，常用A，B等表示。

元素a和集合A的关系：a属于A或a不属于A，即只有两个真值“真”和“假”。

模糊逻辑给集合中每一个元素赋予一个介于0和1之间的实数，描述其属于一个集合的强度，该实数称为元素属于一个集合的隶属度。集合中所有元素的隶属度全体构成集合的隶属函数。

模糊集合的表示方法

以下是内容的行内数学公式表示：

当论域中元素数目有限时，模糊集合 $ A $ 的数学描述为

$
A = {(x, \mu_A(x)) \mid x \in X}
$

其中，$ \mu_A(x) $：元素 $ x $ 属于模糊集 $ A $ 的隶属度，$ X $ 是元素 $ x $ 的论域。

Zadeh表示法
1. 论域是离散且元素数目有限：
  $
  A = \mu_A(x_1)/x_1 + \mu_A(x_2)/x_2 + \cdots + \mu_A(x_n)/x_n = \sum_{i=1}^{n} \mu_A(x_i)/x_i
  $或
  $
  A = {\mu_A(x_1)/x_1, \mu_A(x_2)/x_2, \cdots, \mu_A(x_n)/x_n}
  $
2. 论域是连续的，或者元素数目无限：
  $
  A = \int_{x \in U} \mu_A(x)/x
  $
序偶表示法
$
A = {(\mu_A(x_1), x_1), (\mu_A(x_2), x_2), \cdots, (\mu_A(x_n), x_n)}
$
向量表示法
$
A = {\mu_A(x_1), \mu_A(x_2), \cdots, \mu_A(x_n)}
$

隶属函数

常见的隶属函数有:正态分布、三角分布、梯形分布

隶属函数确定方法：

模糊统计法
专家经验法
二元对比排序法
基本概念扩充法

模糊集合的运算

模糊集合的包含关系
若 $ \mu_A(x) \geq \mu_B(x) $，则 $ A \supseteq B $
模糊集合的相等关系
若 $ \mu_A(x) = \mu_B(x) $，则 $ A = B $
模糊集合的交并补运算
1. 交运算（intersection）$ A \cap B $
  $
  \mu_{A \cap B}(x) = \min {\mu_A(x), \mu_B(x)} = \mu_A(x) \land \mu_B(x)
  $
2. 并运算（union）$ A \cup B $
  $
  \mu_{A \cup B}(x) = \max {\mu_A(x), \mu_B(x)} = \mu_A(x) \lor \mu_B(x)
  $
3. 补运算（complement）$ \overline{A} $ 或 $ A^C $
  $
  \mu_{\overline{A}}(x) = 1 - \mu_A(x)
  $
模糊集合的代数运算：
1. 代数积：
  $
  \mu_{A B}(x) = \mu_A(x) \cdot \mu_B(x)
  $
2. 代数和：
  $
  \mu_{A + B}(x) = \mu_A(x) + \mu_B(x) - \mu_{A B}(x)
  $
3. 有界和：
  $
  \mu_{A \oplus B}(x) = \min {1, \mu_A(x) + \mu_B(x)} = 1 \land [\mu_A(x) + \mu_B(x)]
  $
4. 有界积：
  $
  \mu_{A \circledast B}(x) = \max {0, \mu_A(x) + \mu_B(x) - 1} = 0 \lor [\mu_A(x) + \mu_B(x) - 1]
  $

模糊关系与模糊关系的合成

模糊关系

普通关系:两个集合中的元素之间是否有关联

模糊关系:两个模糊集合中的元素之间关联程度的多少。

模糊关系的定义：

A、B：模糊集合，模糊关系用叉积表示：
$R : A \times B \rightarrow [0, 1]$
又积常用最小算子运算：
$
\mu_{A \times B}(a, b) = \min{\mu_A(a), \mu_B(b)}
$
$A, B$： 离散模糊集，其隶属函数分别为：
$
\mu_A = [\mu_A(a_1), \mu_A(a_2), \cdots, \mu_A(a_n)], \quad
\mu_B = [\mu_B(b_1), \mu_B(b_2), \cdots, \mu_B(b_n)]
$
则其又积运算：$\mu_{A \times B}(a, b) = \mu_A^T \circ \mu_B$

模糊关系的合成

设模糊关系 $ Q \in X \times Y, R \in Y \times Z$ ，那么模糊关系 $S \in X \times Z $ 称为 $ Q $ 与 $ R $ 的合成。
模糊关系 $ Q $ 与 $ R $ 的合成 $ S $ 是模糊矩阵的又乘。

常见计算方法：

最大-最小合成法（乘积运算用取小运算代替，求和运算用取大运算代替）
最大-代数积合成法（乘积运算不变，求和运算用取大运算代替）

模糊推理

模糊知识表示

模糊规则：从条件论域到结论论域的模糊关系矩阵 R。通过条件模糊向量与模糊关系 R 的合成进行模糊推理，得到结论的模糊向量，然后采用“清晰化”方法将模糊结论转换为精确量。

若已知输入为 $ A $，则输出为 $ B $；若现在已知输入为 $ A' $，则输出 $ B' $ 用合成规则求取：
$
B' = A' \circ R
$
其中模糊关系 $ R $：
$
\mu_R(x, y) = \min[\mu_A(x), \mu_B(y)]
$
控制规则库的 $ N $ 条规则有 $ N $ 个模糊关系：
$
R_1, R_2, \dots, R_n
$
对于整个系统的全部控制规则所对应的模糊关系 $ R $：
$
R = R_1 \cup R_2 \cup \cdots \cup R_n = \bigcup_{i=1}^n R_i
$

模糊决策

最大隶属度法

例如，得到模糊向量： $$ U'' = 0.5 / -3 + 0.5 / -2 + 0.5 / -1 + 0.0 / 0 + 0.0 / 1 + 0.0 / 2 + 0.0 / 3 $$ 取结论： $$ U = \frac{-3 - 2 - 1}{3} = -2 $$

加权平均判决法

$$ U = \frac{\sum_{i=1}^n \mu(u_i) u_i}{\sum_{i=1}^n \mu(u_i)} $$

例如： $$ U' = 0.1 / 2 + 0.6 / 3 + 0.5 / 4 + 0.4 / 5 + 0.2 / 6 $$ 则： $$ U' = \frac{0.1 \times 2 + 0.6 \times 3 + 0.5 \times 4 + 0.4 \times 5 + 0.2 \times 6}{0.1 + 0.6 + 0.5 + 0.4 + 0.2} = 4 $$

中位数法

$$ U' = 0.1 / -4 + 0.5 / -3 + 0.1 / -2 + 0.0 / -1 + 0.1 / 0 + 0.2 / 1 + 0.4 / 2 + 0.5 / 3 + 0.1 / 4 $$ 当 $u^* = u_6$ 时， $$ \sum_{u_1}^{u_6} \mu(u_i) = \sum_{u_6}^{u_9} \mu(u_i) = 1 $$ 所以中位数 $u^* = u_6$，则 $U = 1$

第5章探索求解策略

搜索的概念

搜索的基本问题与主要过程

搜索中需要解决的基本问题：

是否一定能找到一个解
找到的解是否是最佳解
时间与空间复杂性如何
是否终止运行或是否会陷入一个死循环

搜索的主要过程：

从初始或目的状态出发，并将它作为当前状态
扫描操作算子集，将适用当前状态的一些操作算子作用于当前状态而得到新的状态，并建立指向其父结点的指针
检查所生成的新状态是否满足结束状态，如果满足，则得到问题的一个解，并可沿着有关指针从结束状态反向到达开始状态，给出一解答路径；否则，将新状态作为当前状态，返回第2步再进行搜索

搜索策略

搜索方向：

数据驱动：从初始状态出发的正向搜索。

正向搜索——从问题给出的条件出发。

目的驱动：从目的状态出发的逆向搜索。

逆向搜索：从想达到的目的入手，看哪些操作算子能产生该目的以及应用这些操作算子产生目的时需要哪些条件。

双向搜索：从开始状态出发作正向搜索，同时又从目的状态出发作逆向搜索，直到两条路径在中间的某处汇合为止。

盲目搜索与启发式搜索

盲目搜索：在不具有对特定问题的任何有关信息的条件下，按固定的步骤进行的搜索。

启发式搜索：考虑特定问题领域可应用的知识，动态地确定调用操作算子的搜索

状态空间的搜索策略

状态空间表示法

状态：表示系统状态、事实等级描述型知识的一组变量或数组： $$ Q = [q_1, q_2, \cdots, q_n]^T $$

操作：表示引起状态变化的过程型知识的一组关系或函数： $$ F = \{f_1, f_2, \cdots, f_m\} $$

状态空间：
利用状态变量和操作符号，表示系统或问题的有关知识的符号体系，状态空间是一个四元组：

$$ (S, O, S_0, G) $$

$S$：状态集合。
$O$：操作算子的集合。
$S_0$：包含问题的初始状态，是 $S$ 的非空子集。
$G$：若干具体状态或满足某些性质的路径信息描述。

求解路径：从 $S_0$ 结点到 $G$ 结点的路径。

状态空间解：一个有限的操作算子序列。

$$ S_0 \xrightarrow{o_1} S_1 \xrightarrow{o_2} S_2 \xrightarrow{o_3} \cdots \xrightarrow{o_k} G $$

$O_1, \cdots, O_k$：状态空间的一个解。

盲目的图搜索策略

回溯策略

从初始状态出发，不停地、试探性地寻找路径，直到它到达目的或“不可解结点”为止。若它遇到不可解结点就回溯到路径中最近的父结点上，查看该结点是否还有其他的子结点未被扩展。若有，则沿这些子结点继续搜索；如果找到目标，就成功退出搜索，返回解题路径。

回溯搜索的算法：

PS表：保存当前搜索路径上的状态。如果找到了目的，PS就是解路径上的状态有序集。
NPS表：新的路径状态表。它包含了等待搜索的状态，其后裔状态还未被搜索到，即未被生成扩展。
NSS表：不可解状态集，列出了找不到解题路径的状态。如果在搜索中扩展出的状态是它的元素，则可立即将之排除，不必沿该状态继续搜索。

宽度优先搜索策略

宽度优先搜索(广度优先搜索): 以接近起始节点的程度（深度）为依据，进行逐层扩展的节点搜索方法。

特点:

每次选择深度最浅的节点首先扩展，搜索是逐层进行的；
一种高价搜索，但若有解存在，则必能找到它。

算法:

open表（NPS表）：已经生成出来但其子状态未被搜索的状态(特点：先进先出)。
closed表（ PS表和NSS表的合并）：记录了已被生成扩展过的状态。

深度优先搜索策略

深度优先搜索: 首先扩展最新产生的节点, 深度相等的节点按生成次序的盲目搜索。

特点：扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；仅当搜索到达一个没有后裔的状态时，才考虑另一条替代的路径。

算法：

防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度——深度界限；
与宽度优先搜索算法最根本的不同：将扩展的后继节点放在OPEN表的前端。
深度优先搜索算法的OPEN表后进先出。

启发式图搜索策略

启发式策略

什么是启发式信息：用来简化搜索过程有关具体问题领域的特性的信息叫做启发信息。

启发式图搜索策略的特点：重排OPEN表，选择最有希望的节点加以扩展。

种类：A、A*算法等。

运用启发式策略的两种基本情况：

一个问题由于存在问题陈述和数据获取的模糊性，可能会使它没有一个确定的解。
虽然一个问题可能有确定解，但是其状态空间特别大，搜索中生成扩展的状态数会随着搜索的深度呈指数级增长。

启发信息和估价函数

启发信息

启发信息：在具体求解中，能够利用与该问题有关的信息来简化搜索过程。

启发式搜索：利用启发信息的搜索过程。

按运用的方法分类：

陈述性启发信息：用于更准确、更精炼地描述状态
过程性启发信息：用于构造操作算子
控制性启发信息：表示控制策略的知识

按作用分类：

用于扩展节点的选择，即用于决定应先扩展哪一个节点，以免盲目扩展。
用于生成节点的选择，即用于决定要生成哪些后继节点，以免盲目生成过多无用的节点。
用于删除节点的选择，即用于决定删除哪些无用节点，以免造成进一步的时空浪费。

估价函数

估价函数：估算节点“希望”程度的量度。

估价函数值 $f(n) $：从初始节点经过 $n$节点到达目标节点的路径的最小代价估计值，其一般形式是

$$ f(n)=g(n)+h(n) $$

$g(n)$：从初始节点$S_0$到节点$n$的实际代价

$h(n)$：从节点$n$到目标节点$S_g$的最优路径的估计代价，称为启发函数

$h(n)$比重大：降低搜索工作量，但可能导致找不到最优解

$h(n)$比重小：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解

A搜索算法

A 搜索算法：使用了估价函数 f 的最佳优先搜索。

估价函数 $f(n) = g(n) +h(n)$

如何寻找并设计启发函数 $h(n)$ ，然后以$ f(n) $的大小来排列OPEN表中待扩展状态的次序，每次选择$ f(n) $值最小者进行扩展。

OPEN表：保留所有已生成而未扩展的状态；

CLOSED表：记录已扩展过的状态。

$g(n)$：状态n的实际代价，例如搜索的深度；

$h(n)$：对状态n与目标“接近程度”的某种启发式估计

A*搜索算法

定义$h*(n)$为状态n到目的状态的最优路径的代价，则当A搜索算法的启发函数h(n)小于等于h*(n)，即对所有节点n满足h(n)≤h*(n)时，被称为A*搜索算法。

如果某一问题有解，那么利用A*搜索算法对该问题进行搜索则一定能搜索到解，并且一定能搜索到最优的解而结束。

可采纳性
当一个搜索算法在最短路径存在时能保证找到它，就称该算法是可采纳的。
A*搜索算法是可采纳的。
A*搜索算法( h(n)=0 )
单调性
A*搜索算法并不要求$g(n)=g*(n)$，则可能会沿着一条非最佳路径搜索到某一中间状态。
如果对启发函数h(n)加上单调性的限制，就可以总从祖先状态沿着最佳路径到达任一状态。
如果某一启发函数h(n)满足：
1. 对所有状态$n_i$和$n_j$，其中$n_j$是$n_i$的后裔，满足$h(n_i)-h(n_j)<=cost(n_i, n_j)$，其中$cost(n_i, n_j)$是从$n_i$到$n_j$的实际代价。
2. 目的状态的启发函数值为0。
则称h(n)是单调的。
A*搜索算法中采用单调性启发函数，可以减少比较代价和调整路径的工作量，从而减少搜索代价。
信息性
在两个A*启发策略的h1和h2中，如果对搜索空间中的任一状态n都有$h_1(n) ≤ h_2(n)$，就称策略$h_2$比$h_1$具有更多的信息性。
如果某一搜索策略的$h(n)$越大，则A*算法搜索的信息性越多，所搜索的状态越少。
但更多的信息性需要更多的计算时间，可能抵消减少搜索空间所带来的益处。

第6章智能计算及其应用

进化算法的概念

（1）进化算法(evolutionary algorithms，EA)是基于自然选择和自然遗传等生物进化机制的一种搜索算法。

（2）生物进化是通过繁殖、变异、竞争和选择实现的；而进化算法则主要通过选择、重组和变异这三种操作实现优化问题的求解。

（3）进化算法是一个“算法簇”，包括遗传算法(GA)、遗传规划、进化策略和进化规划等。

（4） 进化算法的基本框架是遗传算法所描述的框架。

（5）进化算法可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。

进化算法的设计原则

（1）适用性原则：一个算法的适用性是指该算法所能适用的问题种类，它取决于算法所需的限制与假定。

（2）可靠性原则：算法的可靠性是指算法对于所设计的问题，以适当的精度求解其中大多数问题的能力。

（3）收敛性原则：指算法能否收敛到全局最优。在收敛的前提下，希望算法具有较快的收敛速度。

（4）稳定性原则：指算法对其控制参数及问题的数据的敏感度。

（5）生物类比原则：生物界有效方法及操作可以通过类比的方法引入到算法中，有时会带来较好的结果。

基本遗传算法的基本思想（详细掌握）

在求解问题时从多个解开始，然后通过一定的法则进行逐步迭代以产生新的解。

遗传算法的一般步骤

编码、群体设定、适应度函数、选择、交叉、变异

编码：由于遗传算法不能直接处理问题空间的参数，因此必须通过编码将要求解的问题表示成遗传空间的染色体或者个体。对一个具体问题如何进行编码是应用遗传算法的首要问题，也是其难点。

群体设定：

群体设定主要包括初始种群的产生和种群规模的确定：

（1）初始群体的产生

1）根据问题固有知识，把握最优解所占空间在整个问题空间中的分布范围，然后在此分布范围内设定初始群体。

2）随机产生一定数目的个体，从中挑选最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数目达到了预先确定的规模。

（2）种群规模的确定

群体规模太小，遗传算法的优化性能不太好，易陷入局部最优解。群体规模太大，计算复杂。种群规模一般取20-100。

适应度函数：适应度是评价个体优劣的标准。适应度函数是用来区分群体中个体好坏的标准，一般而言适应度函数是由目标函数变换得到的。

选择：选择操作也称为复制（reproduction）操作：从当前群体中按照一定概率选出优良的个体，使它们有机会作为父代繁殖下一代子孙。判断个体优良与否的准则是各个个体的适应度值，即个体适应度越高，其被选择的机会就越多。

交叉：当两个生物机体配对或者复制时，它们的染色体相互混合，产生一个由双方基因组成的全新的染色体组。这一过程称为重组（recombination）或者交叉（crossover）。遗传算法中起核心作用的是交叉算子，也称为基因重组（recombination）。采用的交叉方法应能够使父串的特征遗传给子串。子串应能够部分或者全部地继承父串的结构特征和有效基因。

变异：进化机制除了能够改进已有特征，也能够产生新的特征。在遗传算法中，变异是将个体编码中的一些位进行随机变化。变异的主要目的是维持群体的多样性，为选择、交叉过程中可能丢失的某些遗传基因进行修复和补充。变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。变异操作是按位进行的，即把某一位的内容进行变异。变异概率是在一个染色体中按位进行变化的概率。

群智能算法产生的背景
群智能算法（swarm algorithms，SI）：受动物群体智能启发的算法。
群体智能：由简单个体组成的群落与环境以及个体之间的互动行为。
群智能算法包括：粒子群优化算法、蚁群算法、蜂群算法、……

群智能算法（SI）与进化算法（EC）的异同

相同之处：

（1）EC和SI都是受自然现象的启发。基于抽取出的简单自然规则而发展出的计算模型；（2）两者都是基于种群的方法，且种群中的个体之间、个体与环境之间存在相互作用；

（3）两者都是一种元启发式随机搜索方法。

不同之处：EC强调种群的达尔文主义的进化模型，而SI优化方法则注重对群体中个体之间的相互作用与分布式协同的模拟。

粒子群优化算法的思想

粒子群优化（Particle Swarm Optimization, PSO）算法的基本概念源于对鸟群觅食行为的研究。其基本思想是将每个个体看作n维搜索空间中一个没有体积质量的粒子，在搜索空间中以一定的速度飞行，该速度决定粒子飞行的方向和距离。所有粒子还有一个由被优化的函数决定的适应值。PSO初始化为一群随机粒子，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解，这个解称为个体极值。另个一是整个种群目前找到的最优解，这个解称为全局极值。

蚁群算法的思想

20世纪90年代初，意大利科学家Marco Dorigo等受蚂蚁觅食行为的启发，提出蚁群算法(Ant Colony Optimization，ACO)。一种应用于组合优化问题的启发式搜索算法。在解决离散组合优化方面具有良好的性能。

基本思想：

（1）信息素跟踪：按照一定的概率沿着信息素较强的路径觅食。

（2）信息素遗留：会在走过的路上会释放信息素，使得在一定的范围内的其他蚂蚁能够觉察到并由此影响它们的行为。

规则：

（1）环境：有障碍物、有其他蚂蚁、有信息素。

（2）觅食规则：范围内寻找是否有食物，否则看是否有信息素，每只蚂蚁都会以小概率犯错。

（3）移动规则：都朝信息素最多的方向移动，无信息素则继续朝原方向移动，且有随机的小的扰动，有记忆性。

（4）避障规则：移动的方向如有障碍物挡住，蚂蚁会随机选择另一个方向。

（5）信息素规则：越靠近食物播撒的信息素越多，越离开食物播撒的信息素越少。

第8章人工神经网络及其应用

神经元与神经网络

神经元的数学模型由加权求和、线性动态系统和非线性函数映射三部分组成。

神经元具有两种常规工作状态：兴奋与抑制，即满足“0—1”律。当传入的神经冲动使细胞膜电位升高超过阈值时，细胞进入兴奋状态，产生神经冲动并由轴突输出；当传入的冲动使膜电位下降低于阈值时，细胞进入抑制状态，没有神经冲动输出。

神经网络的学习就是调整神经网络的连接权值或结构，使输入输出具有需要的特性。

BP算法包括信号的前向传播和误差的反向传播两个过程。

卷积神经网络使用了局部连接、权值共享、多卷积核、池化的使用四个关键技术。

深度学习的模型大致可分为判别模型和生成模型。

生成对抗网络由生成网络和判别网络构成。

BP神经网络的结构

BP神经网络（Back-Propagation Neural Network）就是多层前向网络，其结构如下图：

BP学习算法

可以把BP神经网络看成是一个从输入到输出的非线性映射，对网络的连接权进行学习和调整，以使该网络实现给定样本的输入输出映射关系。要解决BP神经网络的学习问题，关键是解决两个问题：

（1）是否存在一个BP神经网络能够逼近给定的样本或者函数。Kolmogorov定理

（2）如何调整BP神经网络的权值，使网络的输入与输出之间的关系与给定的样本相同。BP学习算法

名词解释

智能：智能是知识与智力的总和。其中知识是一切智能行为的基础，智力是获取知识求解问题的能力。
人工智能：用人工的方法在机器（计算机）上实现的智能；或者说是人们使机器具有类似于人的智能。
知识：把有关信息关联在一起所形成的信息结构；在长期的生活及社会实践、科学研究及实验中积累起来的对客观世界的认识与经验。
知识表示：将人类知识形式化或者模型化。知识表示是对知识的一种描述，或者说是一组约定，一种计算机可以接受的用于描述知识的数据结构。
知识图谱：知识图谱是一种互联网环境下的知识表示方法。知识图谱（Knowledge Graph/Vault），又称科学知识图谱，用各种不同的图形等可视化技术描述知识资源及其载体，挖掘、分析、构建、绘制和显示知识及它们之间的相互联系，揭示知识领域的动态发展规律。
推理：从初始证据出发，按某种策略不断运用知识库中的已有知识，逐步推出结论的过程称为推理。
确定性推理：推理时所用的知识与证据都是确定的，推出的结论也是确定的，其真值或者为真或者为假。
不确定性推理：从不确定性的初始证据出发，通过运用不确定性的知识，最终推出具有一定程度的不确定性但却是合理或者近乎合理的结论的思维过程。（推理时所用的知识与证据不都是确定的，推出的结论也是不确定的。）
自然演绎推理：从一组已知为真的事实出发，运用经典逻辑的推理规则推出结论的过程。
鲁滨逊归结原理：检查子句集 S 中是否包含空子句，若包含，则 S 不可满足。若不包含，在 S 中选择合适的子句进行归结，一旦归结出空子句，就说明 S 是不可满足的。
归结反演：应用归结原理证明定理的过程称为归结反演。
可信度：根据经验对一个事物或现象为真的相信程度。
启发信息：在具体求解中，能够利用与该问题有关的信息来简化搜索过程，称此类信息为启发信息。
进化算法：进化算法(evolutionary algorithms，EA)是基于自然选择和自然遗传等生物进化机制的一种搜索算法。
基本遗传算法：在求解问题时从多个解开始，然后通过一定的法则进行逐步迭代以产生新的解。
群智能算法：由简单个体组成的群落与环境以及个体之间的互动行为称为群体智能。群智能算法（swarm algorithms，SI）是受动物群体智能启发的算法。群智能算法包括：粒子群优化算法、蚁群算法、蜂群算法等。

简答题

智能的特征

（1） 感知能力：通过视觉、听觉、触觉、谢绝等感知器官感知外部世界的能力。

（2） 记忆与思维能力：存储由感知器官感知到的外部信息以及由思维所产生的知识。对记忆的信息进行处理。

（3） 学习能力：自学的、有意识的、不自觉的、无意识的、有教师教导的、自己实践的

（4） 行为能力（表达能力）：用于信息的输出。

人工智能研究的基本内容

（1） 知识表示：将人类知识形式化或模型化。

（2） 机器感知：使机器（计算机）具有类似人的感知能力。

（3） 机器思维：对通过感知得来的外部信息及机器内部的各种工作信息进行有目的的处理。

（4） 机器学习：研究如何使计算机具有类似人的学习能力，使它通过学习自动地获取知识。

（5） 机器行为：计算机的表达能力，即说、写、画等能力。

知识表示方法有哪些

（1）谓词逻辑表示法

（2）产生式表示法

（3）框架表示法

（4）知识图谱

（5）状态空间表示法

（6）人工神经网络

（7）遗传编码

用谓词公式表示知识的一般步骤

（1）定义谓词及个体

（2）变元赋值

（3）用连接词连接各个谓词形成谓词公式

冲突消解策略有哪些

（1）按针对性排序（包含更多的条件）

（2）按已知事实的新鲜性排序（后生成的事实）

（3）按匹配度排序（不确定性推理）

（4）按条件个数排序（优先应用条件少的规则）

归结反演（定理证明）的基本步骤

导致不确定性的因素

（1）随机性引起的不确定性

（2）模糊性引起的不确定性

（3）经验引起的不确定性

（4）不完全性引起的不确定性

如何利用启发信息