合肥工业大学人工智能2009-+-2010-+-2011级考卷-+-答案(共14页).doc

精选优质文档-倾情为你奉上合肥工业大学人工智能2009级考卷 + 答案一、 选择填空（在每题下面提供的多个答案中，为每个位置选择正确的答案，每空1分，共40分）1智能科学研究 B 和 C ，是由 E 、 G 、 J 等学科构成的交叉学科。A. 思维的基本理论 B. 智能的基本理论 C. 实现技术 D. 基本形态 E. 脑科学 F. 形象思维 G. 认知科学 H. 抽象思维 I. 感知思维 J. 人工智能 K. 灵感思维2深度优先搜索属于 A ，搜索原则是深度越 C 、越 D 产生结点的优先级越高。深度搜索是 H 。 A. 盲搜索 B. 启发式搜索 C. 大 D. 晚 E. 小 F. 早 G. 完备的 H. 不完备的 3人工智能中的符号主义在认识层次是 A ，在求解层次是 C ，在处理层次是 E ，在操作层次是 G ，在体系层次是 K 。A. 离散 B. 连续 C. 由底向上 D. 自顶向下 E. 串行 F. 并行 G. 推理 H. 映射 I. 交互 J. 分布 K. 局部4. ID3算法属于 C ，基于解释的学习属于 B ，关联分析属于 A ，SVM属于 G 。A. 发现学习 B. 分析学习 C. 归纳学习 D. 遗传学习 E. 连接学习 F. 强化学习 G. 统计学习 5封闭世界假设(CWA)属于 B ，D-S证据理论属于 D ，限定逻辑属于 B 。 A. 归结原理 B. 非单调推理 C. 定性推理 D. 不确定推理 6在不确定理论中 D 无需任何先验知识（或信息）， B 与 C 具有处理不精确和不确定数据的方法，而 A 使用概率去表示所有形式的不确定性。A. Bayes理论 B. 模糊集理论 C. 证据理论 D. 粗糙集 7SVM是建立在 B 和 C 原理基础上的，在解决 F 、 I 及 A 模式识别中表现出许多特有的优势。A. 高维 B. VC维 C. 结构风险最小 D. 经验风险最小E. 置信风险最小 F. 小样本 G. 大样本 H. 线性 I. 非线性8人工神经网络是 B 的典型，它的特点集中表现在以 D 方式存储信息、以 F 方式处理信息、具有自组织、自学习能力。神经网络可分为四大类，著名的Hopfield网络属于 J 类。A. 符号智能 B. 计算智能 C. 集中 D。分布 E. 串行 F. 并行 G. 分层前向网络 H. 反馈前向网络 I. 互连前向网络 J. 广泛互连网络 9 在遗传算法中复制操作使用来模拟 B ，交叉操作是用来模拟 C ，而变异操作是用来模拟 A 。 A. 基因突变 B. 适者生存 C. 繁殖现象 10群智能思想的产生主要源于 B 以及 D 的研究， F 是群智能领域最著名的算法。 A. 多Agent系统 B. 复杂适应系统理论 C. 进化计算 D. 人工生命 E. PSO F. ACO G. AFSA二、 将下列语句形式化（每题5分，共10分）例1：他个子高而且很胖令P表示“他个子高”，Q表示“他很胖”，于是可表示为PQ例2：任何金属都可以溶解在某种液体里以P(x)表示x是金属，Q(x)表示x是液体，R(x,y)表示x可以溶解在y中，语句的形式化为：1. 他个子矮或他不很胖都是不对的令P表示“他个子高”，Q表示“他很胖”(PQ)2. 凡实数都能比较大小以P(x)表示x是实数，Q(x,y)表示x和y可以比较大小，语句的形式化为：三、 采用广度优先搜索求解下面八数码问题，给出广度优先搜索树（10分）。四、 简答题（每题10分）1. 在不确定知识与推理研究中，模糊集理论、贝叶斯网络、粗糙集理论各有何特点？模糊集理论利用模糊隶属度来表示自然界模糊现象，从研究集合与元素的关系入手研究不确定性。广泛应用于专家系统和智能控制中。模糊集是不可计算的，即没有给出数学公式描述这一含糊概念，故无法计算出它的具体的含糊元素数目，如模糊集中的隶属函数和模糊逻辑中的算子都是如此。贝叶斯网络是用来表示变量间连接概率的图形模式，它提供了一种自然的表示因果信息的方法，用来发现数据间的潜在关系。在这个网络中，用节点表示变量，有向边表示变量间的依赖关系。贝叶斯理论给出了信任函数在数学上的计算方法，具有稳固的数学基础，同时它刻画了信任度与证据的一致性及其信任度随证据而变化的增量学习特性；在数据挖掘中，贝叶斯网络可以处理不完整和带有噪声的数据集，它用概率测度的权重来描述数据间的相关性，从而解决了数据间的不一致性，甚至是相互独立的问题；用图形的方法描述数据间的相互关系，语义清晰、可理解性强，这有助于利用数据间的因果关系进行预测分析。贝叶斯方法正在以其独特的不确定性知识表达形式、丰富的概率表达能力、综合先验知识的增量学习特性等成为当前数据挖掘众多方法中最为引人注目的焦点之一粗糙集理论反映了人们用粗糙集方法处理不分明问题的常规性，即以不完全信息或知识去处理一些不分明现象的能力，或依据观察、度量到的某些不精确的结果而进行分类数据的能力。基本粗糙集理论认为知识就是人类和其他物种所固有的分类能力，粗糙集理论利用集合（下近似集和上近似集）处理含糊和不精确性问题。粗糙集主要优点包括：除数据集之外，无需任何先验知识（或信息）；对不确定性的描述与处理相对客观。2. 群智能算法与进化算法有何异同？基于 SI 的优化算法和 EC都是基于群体迭代的启发式随机优化算法, 有着非常多相似之处, 它们都是对自然中随机系统的仿真, 都具有本质并行性。另外, 与 EC还一样的是, SI 的目的并不是为了忠实地模拟自然现象, 而是利用它们的某些特点去解决实际问题。首先，PSO和 SI 所模拟的自然随机系统不一样。EC是模拟生物系统进化过程, 其最基本单位是基因(Gene) , 它在生物体的每一代之间传播; 已有的基于 SI 的优化算法都是源于对动物社会通过协作解决问题行为的模拟, 它主要强调对社会系统中个体之间相互协同作用的模拟, 其最基本单位是敏因。其次， EC中强调“适者生存” , 不好的个体在竞争中被淘汰; SI 强调 “协同合作” , 不好的个体通过学习向好的方向转变,不好的个体被保留还可以增强群体的多样性。EC中最好的个体通过产生更多的后代来传播自己的基因, 而 SI 中的优秀个体通过吸引其它个体向它靠近来传播自己的敏因。最后，EC的迭代由选择、变异和交叉重组操作组成，而 SI的迭代中的操作是 “跟随”，ACO中蚂蚁跟随信息素浓度爬行,PSO中粒子跟随最优粒子飞行。在某种程度上看，SI 的跟随操作中隐含了选择、 变异和交叉重组操作。五、 什么是线性可分？简述支持向量机解决非线性可分问题的基本思想。（10分）假设存在训练样本（x1,y1） ， （xn,yn） ，xRd，y+1,-1，n为样本数，d为输入维数，在线性可分的情况下就会有一个超平面使得这两类样本完全分开。如果训练数据可以无误差地被划分，以及每一类数据与超平面距离最近的向量与超平面之间的距离最大则称这个超平面为最优超平面。对非线性问题支持向量机首先通过用内积函数定义的非线性变换将输入空间变换到一个高维空间，在这个空间中求广义最优分类面。六、 解答下列问题：（10分）（1） 给出ID3算法描述 ID3 算法 选出整个训练实例集X 的规模为W 的随机子集 X1（W 称为窗口规模，子集称为窗口） ； 以使得（7.29）式的值最小为标准，选取每次的测试属性形成当前窗口的决策树； 顺序扫描所有训练实例，找出当前的决策树的例外，如果没有例外则训练结束； 组合当前窗口的一些训练实例与某些在(3)中找到的例外形成新的窗口，转(2)（2）表1给出了一个可能带有噪音的数据集合。它有四个属性，Outlook、Temperature、Humidity、Windy。它被分为两类，P 与 N，分别为正例与反例。用ID3构造出决策树将数据进行分类。表 1 样本数据集合属性outlooktemperaturehumiditywindy类1overcasthothighnotN2overcasthothighveryN3overcasthothighmediumN4sunnyhothighnotP5sunnyhothighmediumP6rainmildhighnotN7rainmildhighmediumN8rainhotnormalnotP9raincoolnormalmediumN10rainhotnormalveryN11sunnycoolnormalveryP12sunnycoolnormalmediumP13overcastmildhighnotN14overcastmildhighmediumN15overcastcoolnormalnotP16overcastcoolnormalmediumP17rainmildnormalnotN18rainmildnormalmediumN19overcastmildnormalmediumP20overcastmildnormalveryP21sunnymildhighveryP22sunnymildhighmediumP23sunnyhotnormalnotP24rainmildhighveryN解：可以看出 H（X/Outlook）最小，即有关 Outlook 的信息对于分类有最大的帮助，提供最大的信息量，即 I（X；Outlook）最大。所以应该选择 Outlook 属性作为测试属性。并且也可以看出 H（X）=H（X/Windy） ，即 I（X；Windy）=0，有关 Windy 的信息不能提供任何有关分类的信息。选择 Outlook 作为测试属性之后将训练实例集分为三个子集，生成三个叶结点，对每个叶结点依次利用上面过程则生成图 1所示的决策树。图 1 表 1 所训练生成的决策树合肥工业大学人工智能2010级考卷 + 答案一、 选择填空（在每题下面提供的多个答案中，为每个位置选择正确的答案，每空1分，共40分）1智能科学研究 B 和 C ，是由 E 、 G 、 J 等学科构成的交叉学科。A. 思维的基本理论 B. 智能的基本理论 C. 实现技术 D. 基本形态 E. 脑科学 F. 形象思维 G. 认知科学 H. 抽象思维 I. 感知思维 J. 人工智能 K. 灵感思维2深度优先搜索属于 A ，搜索原则是深度越 C 、越 D 产生结点的优先级越高。深度搜索是 H 。 A. 盲搜索 B. 启发式搜索 C. 大 D. 晚 E. 小 F. 早 G. 完备的 H. 不完备的 3人工智能中的符号主义在认识层次是 A ，在求解层次是 D ，在处理层次是 E ，在操作层次是 G ，在体系层次是 K 。A. 离散 B. 连续 C. 由底向上 D. 自顶向下 E. 串行 F. 并行 G. 推理 H. 映射 I. 交互 J. 分布 K. 局部4. ID3算法属于 C ，基于解释的学习属于 B ，关联分析属于 A ，SVM属于 G 。A. 发现学习 B. 分析学习 C. 归纳学习 D. 遗传学习 E. 连接学习 F. 强化学习 G. 统计学习 5封闭世界假设(CWA)属于 B ，D-S证据理论属于 D ，限定逻辑属于 B 。 A. 归结原理 B. 非单调推理 C. 定性推理 D. 不确定推理 6在不确定理论中 D 无需任何先验知识（或信息）， B 与 C 具有处理不精确和不确定数据的方法，而 A 使用概率去表示所有形式的不确定性。A. Bayes理论 B. 模糊集理论 C. 证据理论 D. 粗糙集 7SVM是建立在 B 和 C 原理基础上的，在解决 F 、 I 及 A 模式识别中表现出许多特有的优势。A. 高维 B. VC维 C. 结构风险最小 D. 经验风险最小E. 置信风险最小 F. 小样本 G. 大样本 H. 线性 I. 非线性8人工神经网络是 B 的典型，它的特点集中表现在以 D 方式存储信息、以 F 方式处理信息、具有自组织、自学习能力。神经网络可分为四大类，著名的Hopfield网络属于 J 类。A. 符号智能 B. 计算智能 C. 集中 D。分布 E. 串行 F. 并行 G. 分层前向网络 H. 反馈前向网络 I. 互连前向网络 J. 广泛互连网络 9 在遗传算法中复制操作使用来模拟 B ，交叉操作是用来模拟 C ，而变异操作是用来模拟 A 。 A. 基因突变 B. 适者生存 C. 繁殖现象 10群智能思想的产生主要源于 B 以及 D 的研究， F 是群智能领域最著名的算法。 A. 多Agent系统 B. 复杂适应系统理论 C. 进化计算 D. 人工生命 E. PSO F. ACO G. AFSA二、 将下列语句形式化（每题5分，共10分）例1：他个子高而且很胖令P表示“他个子高”，Q表示“他很胖”，于是可表示为PQ例2：任何金属都可以溶解在某种液体里以P(x)表示x是金属，Q(x)表示x是液体，R(x,y)表示x可以溶解在y中，语句的形式化为：1. 他个子高但不很胖 令P表示“他个子高”，Q表示“他很胖”PQ2. 一切事物都是发展的以P(x)表示x是事物，Q(x)表示x是发展的，语句的形式化为：三、 采用有限深度优先搜索求解下面八数码问题，设搜索深度限制d=5，给出深度优先搜索树（10分）。四、 简答题（每题10分，共20分）1. 试解释有监督学习、无监督学习、强化学习？有监督(有指导)学习从其输入/输出的实例中学习一个函数无监督(无指导)学习在未提供明确的输出值情况下，学习输入的模式2. 什么是先验概率？什么是后验概率？先验概率是指根据历史的资料或主观判断所确定的各事件发生的概率，该类概率没能经过实验证实，属于检验前的概率，所以称之为先验概率。先验概率一般分为两类，一是客观先验概率，是指利用过去的历史资料计算得到的概率；二是主观先验概率，是指在无历史资料或历史资料不全的时候，只能凭借人们的主观经验来判断取得的概率。 后验概率一般是指利用贝叶斯公式，结合调查等方式获取了新的附加信息，对先验概率进行修正后得到的更符合实际的概率五、 简述基本遗传算法原理（10分）实现GA过程:主要包括编码;确定种群;遗传操作;优胜劣汰等运算过程. 编码：把每一可能解,编码为向量,表示为二或十进制数字字符串,称其为染色体(chromosome)或个体,而把向量中的每个元素,称之为基因(genes); 确定种群：把所有的染色体组成集群(population)，按预定的目标函数，对每个染色体进行评鉴、计算其适应度值; 根据其适应度值比较，对诸染色体进行遗传操作： 选择复制； 交换； 变异； 在进行遗传操作中，不断剔除适应度低的那些性能不佳的染色体，留下适应度高的并且性能优良的染色体，于是，就得到了性能较优的新种群。如此这样反复迭代，优胜劣汰，就使得该集群一代又一代向着更优群体的方向进化。初始种群（侯选染色体）向量编码种群 P(t)计算种群各个体适应度值基本操作：复制、交叉、变异 种群P(t+1)满足预定指标？ 解码染色体 问题最优解 种群 P(t) 种群P(t+1)遗传算法基本思想实现原理示意图六、 简要描述强化学习的基本原理并试比较与其他机器学习方法的异同。（10分）强化（reinforcement）学习是指从环境状态到行为映射的学习，以使系统行为从环境中获得的累积奖励值最大。在强化学习中，我们设计算法来把外界环境转化为最大化奖励量的方式的动作。我们并没有直接告诉主体要做什么或者要采取哪个动作，而是主体通过看哪个动作得到了最多的奖励来自己发现。主体的动作的影响不只是立即得到的奖励， 而且还影响接下来的动作和最终的奖励。试错搜索(trial-and-error search)和延期强化(delayed reinforcement)这两个特性是强化学习中两个最重要的特性。强化学习不是通过特殊的学习方法来定义的， 而是通过在环境中和响应外界环境的动作来定义的。任何解决这种交互的学习方法都是一个可接受的强化学习方法。强化学习也不是监督学习，在我们有关机器学习的部分我们都可以看出来。在监督学习中， “教师”用实例来直接指导或者训练学习程序。在强化学习中，学习主体自身通过训练，误差和反馈，学习在环境中完成目标的最佳策略。合肥工业大学人工智能2011级考卷 + 答案一、 选择填空（在每题下面提供的多个答案中，为每个位置选择正确的答案，每空1分，共30分）1. 人工智能是由 A 、 D 、 G 、神经生理学、心理学、语言学等多种学科相互渗透而发展起来。A. 计算机科学 B. 脑科学 C. 认知科学 D. 控制论 E. 形象思维 F. 智能科学 G. 信息论 H. 行为科学 I. 感知思维 J. K. 灵感思维2宽度优先搜索属于 A ，搜索原则是深度越 E 、越 F 产生结点的优先级越高。宽度搜索是 G 。 A. 盲搜索 B. 启发式搜索 C. 大 D. 晚 E. 小 F. 早 G. 完备的 H. 不完备的 3知识表示按问题求解要求可分为 D 、 E 、 F 3类，其中框架知识表示属于 D 知识表示。A. 逻辑 B. 产生式 C. 语义网络 D. 叙述性 E. 过程性 F. 控制性G. 描述性 H. 判断性I. 对象级 J. 元知识 4. ID3算法属于 C ，Q学习属于 F ，关联分析属于 A ，SVM属于 G 。A. 发现学习 B. 分析学习 C. 归纳学习 D. 遗传学习 E. 连接学习 F. 强化学习 G. 统计学习 5基于范例推理属于 F ，定性模型方法属于 C ，Reiter的缺省逻辑属于 B 。 A. 归结原理 B. 非单调推理 C. 定性推理 D. 不确定推理 F 类比推理6在不确定理论中，认为“知识”就是将对象进行分类的能力的是 D 。 B 与 C 具有处理不精确和不确定数据的方法，而 A 使用概率去表示所有形式的不确定性。A. Bayes理论 B. 模糊集理论 C. 证据理论 D. 粗糙集 7人工神经网络是 B 的典型，可分为四大类，BP网络属于 C ，Hopfield网络属于 F 类。A. 符号智能 B. 计算智能 C 分层前向网络 D. 反馈前向网络 E. 互连前向网络 F. 广泛互连网络 8在遗传算法中复制操作使用来模拟 B ，交叉操作是用来模拟 C ，而变异操作是用来模拟 A 。 A. 基因突变 B. 适者生存 C. 繁殖现象9 在群智能算法中，模拟自然界蚂蚁社会寻找食物方式的仿生优化算法是 E ，对鸟群社会系统研究的算法是 C 。 A. EC B. SI C. PSO D. AFSA E. ACO 二、 将下列语句形式化（每题5分，共15分）例1：他个子高而且很胖令P表示“他个子高”，Q表示“他很胖”，于是可表示为PQ例2：任何金属都可以溶解在某种液体里以P(x)表示x是金属，Q(x)表示x是液体，R(x,y)表示x可以溶解在y中，语句的形式化为：1. 他个子矮或他不很胖都是不对的 令P表示“他个子高”，Q表示“他很胖”(PQ)2. 如果嫦娥是虚构的，而如果圣诞老人也是虚构的，那么许多孩子受骗了。令P表示“嫦娥是虚构的”，Q表示“圣诞老人是虚构的”，R表示“许多孩子受骗了”，于是可形式化为：（PQ）R 或 P（QR）3. 在合肥工作的人未必都是合肥人。以P(x)表示x是在合肥工作，Q(x)表示x是合肥人，语句的形式化为：x(P(x) Q(x) 或x(P(x)Q(x) 三、 采用广度优先搜索求解下面八数码问题，给出广度优先搜索树（10分）。四、 简答题（每题10分，共20分）1. 支持向量机SVM支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力 。2. 蚁群算法蚁群算法(Ant Colony OptimizationACO)由 Colorni, Dorigo 和 Maniezzo 于 1991 年提出,它是通过模拟自然界蚂蚁社会的寻找食物的方式而得出的一种仿生优化算法。 自然界种蚁群寻找食物时会派出一些蚂蚁分头在四周游荡, 如果一只蚂蚁找到食物, 它就返回巢中通知同伴并沿途留下 “信息素” ( pheromone)作为蚁群前往食物所在地的标记。 信息素会逐渐挥发, 如果两只蚂蚁同时找到同一食物,又采取不同路线回到巢中, 那么比较绕弯的一条路上信息素的气味会比较淡, 蚁群将倾向于沿另一条更近的路线前往食物所在地。ACO算法设计虚拟的 “蚂蚁” , 让它们摸索不同路线, 并留下会随时间逐渐消失的虚拟 “信息素” 。根据 “信息素较浓的路线更近” 的原则, 即可选择出最佳路线。五、 什么是BP网络，试给出BP网络的学习过程和算法（15分）BP网络就是多层前向网络 结构：输入层、一层或多层隐层、输出层 激发函数：S形函数学习过程正向传播：输入信息从输入层经隐层逐层处理后传至输出层，每层神经元的状态只影响下一层神经元的状态。 反向传播：输出层得不到期望输出，把误差信号沿原连接路径返回，并修改各神经元的权值，使误差信号最小。BP学习算法 （1）选取比例参数 （2）进行下列过程直至性能满足要求为止 （a）对于每一训练（采样）输入： 按下式计算输出节点的值 z=dz-Oz 按下式计算全部其他节点 按下式计算全部权值变化 （b）对于所有训练（采样）输入，对权值变化求和，并修正各权值六、解答下列问题：（10分） 下图给出一个关于家庭防盗的贝叶斯网络。家里安装的报警器能够有效感知盗贼的侵入，并对轻微的地震有一定的感知能力。两个邻居李和张听到报警声时都会友善地来电话提醒，但偶尔李会错将门铃声当作报警声，而张则会因为大声听音乐而听不到报警声。该网络的拓扑结构表明盗贼和地震是警报声响的直接原因，而邻居李和张来电话的直接原因是听到了警报声。盗贼入侵地震发生李来电话张来电话报警声响BEALZP(B)0.001P(E)0.002BEP(A)TT0.95TF0.94FT0.29FF0.001AP(L)T0.90F0.05AP(Z)T0.70F0.01分别以字母B、E、A、L、Z指示节点（变量）“盗贼入侵”、“地震发生”、“报警声响”、“李来电话”、“张来电话”，并将节点条件概率表置于每个节点的右侧。由于所有5个节点对应的随机变量都是布尔变量，节点的条件概率分布简化为条件概率表；b、e、a、l、z分别指示这些变量取值为“Ture”，且省略变量值取“False”的条件概率。节点“盗贼入侵”和“地震发生”无父节点，就取它们的先验概率填充条件概率表。（1） 计算报警声响了，但实际并无盗贼入侵，也无地震发生，而李和张却都来电话的概率。 P(lzabe)= p(l|a)p(z|a)p(a|be)p(b)p(e)= 0.90*0.70*0.001*0.999*0.998=0.00063（2） 计算李和张都来电话时，盗贼入侵的概率= B有两个值：b，b；对于取值b： = = = =*0.001*0.002(0.95*0.90*0.70+0.05*0.05*0.01)+ 0.998*(0.94*0.90*0.70+0.06*0.05*0.01) =*0.类似地，可以计算出=*0.是归一化常数，用于确保相对于B所有取值的条件（后验）概率的综合等于1。这里 =1/（0.+0.）因此=（0.，0.）=（0.284，0.716） 即，李和张都来电话时，盗贼入侵的概率是0.284专心-专注-专业