人工智能的主要内容和方法

人工智能的主要内容和方法 人工智能 Artificial Intelligence 简称 AI 是 50 年代兴起的一门新兴 边缘学科 二十世纪七十年代以来被称为世界三大尖端技术之一 空间技 术 能源技术 人工智能 也被认为是二十一世纪三大尖端技术之一 基 因工程 纳米科学 人工智能 广义的讲 人工智能是关于人造物的智能 行为 而智能行为包括知觉 推理 学习 交流和在复杂环境中的行为 人工智能的一个长期目标是发明出可以像人类一样或能更好地完成以上行 为的机器 另一个目标是理解这种智能行为是否存在于机器 人类或其他 动物中 目前能够用来研究人工智能的主要物质手段以及能够实现人工智 能技术的机器就是计算机 人工智能的发展历史是和计算机科学与技术的 发展史联系在一起的 除了计算机科学以外 人工智能还涉及信息论 控 制论 自动化 仿生学 生物学 心理学 数理逻辑 语言学 医学和哲 学等多门学科 一 AI 的主要内容 人工智能研究的主要内容包括 知识表示 自动推理和搜索方法 机器 学习和知识获取 知识处理系统 自然语言理解 计算机视觉 智能机器 人 自动程序设计等方面 知识表示是人工智能的基本问题之一 推理和搜索都与表示方法密切 相关 常用的知识表示方法有 逻辑表示法 产生式表示法 语义网络表 示法和框架表示法等 常识 自然为人们所关注 已提出多种方法 如非单调推理 定性推 理就是从不同角度来表达常识和处理常识的 问题求解中的自动推理是知识的使用过程 由于有多种知识表示方法 相应地有多种推理方法 推理过程一般可分为演绎推理和非演绎推理 谓 词逻辑是演绎推理的基础 结构化表示下的继承性能推理是非演绎性的 由于知识处理的需要 近几年来提出了多种非演绎的推理方法 如连接机 制推理 类比推理 基于示例的推理 反绎推理和受限推理等 搜索是人工智能的一种问题求解方法 搜索策略决定着问题求解的一 个推理步骤中知识被使用的优先关系 可分为无信息导引的盲目搜索和利 用经验知识导引的启发式搜索 启发式知识常由启发式函数来表示 启发 式知识利用得越充分 求解问题的搜索空间就越小 典型的启发式搜索方 法有 A AO 算法等 近几年搜索方法研究开始注意那些具有百万节点的 超大规模的搜索问题 机器学习是人工智能的另一重要课题 机器学习是指在一定的知识表 示意义下获取新知识的过程 按照学习机制的不同 主要有归纳学习 分 析学习 连接机制学习和遗传学习等 知识处理系统主要由知识库和推理机组成 知识库存储系统所需要的 知识 当知识量较大而又有多种表示方法时 知识的合理组织与管理是重 要的 推理机在问题求解时 规定使用知识的基本方法和策略 推理过程 中为记录结果或通信需设数据库或采用黑板机制 如果在知识库中存储的 是某一领域 如医疗诊断 的专家知识 则这样的知识系统称为专家系统 为 适应复杂问题的求解需要 单一的专家系统向多主体的分布式人工智能系 统发展 这时知识共享 主体间的协作 矛盾的出现和处理将是研究的关 键问题 二 AI 的研究方法 既为人工智能的最终研究目标打好基础 又能创造出短期效益 这是选 择人工智能研究最佳方法的标准 尽管人工智能已经创造了一些实用系统 但这些远未达到人类的智能水平 在过去的几十年里涌现出了大量的方法 大致可分为两大类 第一类包括符号处理的方法 它们基于 Newell 和 Simon 的物理符号系 统的假说 大多数被称为 经典的人工智能 均在其指导之下 这类方法 中 突出的方法是将逻辑操作应用于说明性知识库 这种风格的人工智能 运用说明语句来表达问题域的 知识 这些语句基于或实质上等同于一阶 逻辑中的语句 采用逻辑推理可推导这种知识的结果 这种方法有许多变 形 包括那些强调对逻辑语言中定义域的形式公理化的角色的变形 当遇 到 真正的问题 这一方法需要掌握问题域的足够知识 通常就称作基于 知识的方法 在大多数符号处理方法中 对需求行为的分析和为完成这一行为所做 的机器合成要经过几个阶段 最高阶段是知识阶段 机器所需知识在这里 说明 接下来是符号阶段 知识在这里以符号组织表示 例如 列表可用 列表处理语言 LISP 来描述 同时在这里说明这些组织的操作 接着 在 更低级的阶段里实施符号处理 多数符号处理采用自上而下的设计方法 从知识阶段向下到符号和实施阶段 第二类包括所谓的 子符号 方法 它们通常采用自下而上的方式 从最低阶段向上进行 在最低层阶段 符号的概念就不如信号这一概念确 切了 在子符号方法中突出的方法是 Animat approach 偏爱这种方式的 人们指出 人的智能经过了在地球上十亿年或更长时间的进化过程 认为 为了制造出真正的智能机器 我们必须沿着这些进化的步骤走 因此 我 们必须集中研究复制信号处理的能力和简单动物如昆虫的支配系统 沿着 进化的阶梯向上进行 这一方案不仅能在短期内创造实用的人造物 又能 为更高级智能的建立打好坚实的基础 第二类方法也强调符号基础 在物理基础假说中 一个 agent 不采用集 中式的模式而运用其不同的行为模块与环境相互作用来进行复杂的行为 机器与环境的相互作用产生了所谓的 自然行为 emergent behavior 一 个 agent 的功能可视作该系统与动态环境密切相互作用的自然属性 agent 本身对其行为的说明并不能解释它运行时所表现的功能 相反 其功能很 大程度上取决于环境的特性 不仅要动态的考虑环境 而且环境的具体特 征也要运用于整个系统之中 由子符号派制造的著名样品机器包括 神经网络 Neural network 根据模拟生物进化方面的进程 一些有意思的机器应运而生 包括 Sexual crossover Mutation 和 Fitness proportional reproduction 其他自下而上 含 animat 风格的方法是基于控制理论和动态系统地分析 介于自上而下和自 下而上之间的方法是一种 环境自动机 situated automata 的方法 Kaelbling 和 Rosenschein 建议编写一种程序设计语言来说明 agent 在高水平 上所要求的行为 并编写一编译程序 以从这种语言编写的程序中产生引 发行为的线路 径向基函数神经网络 MATLAB 仿真 一 RBF 网络的工作原理 径向基函数神经网络 Radial Basis Function Neural Network RBF 是 一种前馈神经网络 一般为三层结构 如下图 c1 c2 X1 y1 W Rh m X2 ch ym b0 bm Xn 1 x c1 h x ch 上图所示为 n h m 结构的 RBF 网络 即网络具有 n 个输入 h 个隐 节点 m 个输出 其中 x x1 x2 xn T Rn为网络输入矢量 W Rn m为 输出权矩阵 b0 bm为输出单元偏移 y y1 y2 ym T为网络输出 i 为第 i 个隐节点的激活函数 图中输出层节点中的 表示输出层神经元采用 线性激活函数 输出神经元也可以采用其他非线性激活函数 如 Sigmoidal 函数 RBF 网络的最显著的特点是隐节点的基函数采用距离函数 如欧式距 离 并使用径向基函数 如 Gaussian 高斯函数 作为激活函数 径向基函 数关于 n 维空间的一个中心点具有径向对称性 而且神经元的输入离该中 心点越远 神经元的激活程度就越低 隐节点的这个特性常被称为 局部 特性 因此 RBF 网络的每个隐节点都具有一个数据中心 上图中 ci就是 网络中第 i 个隐节点的数据中心值 则表示欧式范数 径向基函数 i 可以取多种形式 1 Gaussian 函数 22 t e i t i 2 Reflected sigmoidal 函数 e1 1 22 t i t i 3 逆 Multiquadric 函数 0 1 22 ii tt 以上三式中的 i称为该基函数的扩展常数 Spread 或宽度 显然i越 小 径向基函数的宽度就越小 基函数就越具有选择性 与输出节点相连的隐层第 i 个隐节点的所有参数可用三元组 ci i i 表示 每个隐层神经元都对输入 x 产生一个响应 且响应特性成 c x ii 径向对称 即是一个个同心圆 而神经网络的输出则是所有这些响应的加 权和 因此第 k 个输出可表示为 h 1i i c x iik y 由于每个神经元具有局部特性 最终整个 RBF 网络也呈现 局部映射 特性 即 RBF 网络是一种局部相应神经网络 这意味着如果神经网络有较 大的输出 必定激活了一个或多个隐节点 二 RBF 网络的聚类学习算法 RBF 网络的学习算法应该解决以下问题 结构设计 即如何确定网络 隐节点数 h 确定各径向基函数的数据中心 ci及扩展常数 i 输出权值修正 如果知道了网络的隐节点数 数据中心和扩展常数 RBF 网络从输入到输 出就成了一个线性方程组 此时权值学习可采用最小二乘法 RBF 网络最常用的学习算法有聚类方法 梯度训练方法及 OLS 优选算 法 下面将详细介绍最经典的 RBF 网络学习算法 聚类方法 并进行 MATLAB 仿真 聚类方法的思路是先用无监督学习 用 k means 算法对样本输入进行 聚类 方法确定 RBF 网络中 h 个隐节点的数据中心 并根据各数据中心之 间的距离确定隐节点的扩展常数 然后用有监督学习 梯度法 训练各隐 节点的输出权值 假设 X1 X2 XN为样本输入 相应的样本输出 教师信号 为 y1 y2 yN 网络中第 j 个隐节点的激活函数为 j k 为迭代次数 第 k 次迭代 时的聚类中心为 c1 k c2 k ch k 相应的聚类域为 1 k 2 k h k k means 聚类算法确定 RBF 网络数据中心 ci和扩展常数 i的步骤如下 1 算法初始化 选择 h 个不同的初始聚类中心 并令 k 1 初始聚类 中心的方法很多 比如 从样本输入中随机选取 或者选择前 h 个样本输 入 但这 h 个初始数据中心必须取不同值 2 计算所有样本输入与聚类中心的距离 Xj ci k i 1 2 h j 1 2 N 3 对样本输入 Xj按最小距离原则对其进行分类 即当 i xj Xj i min ci k i 1 2 h 时 Xj即被归为第 i 类 即 Xj i k 4 重新计算各类的新的聚类中心 k i 2 1 1 1 x i i hix N kc 式中 Ni为第 i 个聚类域 i k 中包含的样本数 5 如果 ci k 1 ci k 转到步骤 2 否则聚类结束 转到步骤 6 6 根据各聚类中心之间的距离确定各隐节点的扩展常数 隐节点的扩 展常数取 i di 其中 di为第 i 个数据中心与其他最近的数据中心之间的 距离 即 di cj ci k 称重叠系数 i min 一旦各隐节点的数据中心和扩展常数确定了 输出权矢量 1 2 h T就可以用有监督学习方法 如梯度法 训练得到 但更简洁的方法是 使用最小二乘方法 LMS 直接计算 假定当输入为 Xi i 1 2 N 时 第 j 个隐节点的输出如下式所示 c x j i jij h 则隐层输出阵为 ij hH 则 RN h 如果 RBF 网络的当前权值为 1 2 h T 待定 则 H 对所有样本 网络输出矢量为 Hy 令为逼近误差 则如果给定了教师信号 y y1 y2 ym T并确定 yy 了 便可通过最小化下式求出网络的输出权值 H Hyyy 通常 可用最小二乘法求得 yH 式中 为的伪逆 即 H H TT HHHH 1 三 RBF 网络 MATLAB 仿真实例 题目 基于聚类方法的题目 基于聚类方法的 y sinx 函数逼近函数逼近 解 RBF 网络隐层采用标准 Gaussian 径向基函数 输出层采用线性激 活函数 即 f u u 数据中心和扩展常数用聚类方法得到 输出权值和偏 移采用广义逆方法求解 隐节点数 即聚类数 取 10 初始聚类中心取前 10 个训练样本 MATLAB 程序 function main SamNum 200 训练样本数 TestSamNum 201 测试样本数 InDim 1 样本输入维数 ClusterNum 10 隐节点 聚类样本 数 Overlap 1 0 隐节点重叠系数 根据目标函数获得样本输入输出 rand state sum 100 clock resets the generator to a different state each time 且 state 不同产生的伪随机序列顺序不同 SamIn 14 rand 1 SamNum 7 SamOut sin SamIn TestSamIn 7 0 07 7 7 7 0 07 1 201 个样本 TestSamOut sin TestSamIn figure hold on grid plot SamIn SamOut b plot TestSamIn TestSamOut k 绘制目标函数曲线 xlabel Input x ylabel Output y title 基于聚类的 RBF 网络对函数 y sinx 的逼近曲线 Centers SamIn 1 ClusterNum 初始聚类中心取前 10 个训练样本 NumberInClusters zeros ClusterNum 1 各类中的样本数 初始化为 0 IndexInClusters zeros ClusterNum SamNum 各类所含样本的索引号 while 1 NumberInClusters zeros ClusterNum 1 IndexInClusters zeros ClusterNum SamNum 按最小距离原则对所有样本进行分类 for i 1 SamNum AllDistance dist Centers SamIn i 求欧几里德距离 MinDist Pos min AllDistance NumberInClusters Pos NumberInClusters Pos 1 求各类样本的个数 IndexInClusters Pos NumberInClusters Pos i end 报存旧的聚类中心 OldCenters Centers 重新计算各类的聚类中心 for i 1 ClusterNum Index IndexInClusters i 1 NumberInClusters i Centers i mean SamIn Index end 判断新旧聚类中心是否一致 如果是 则聚类结束 EqualNum sum sum Centers OldCenters 新旧聚类中心一致的个数 if EqualNum InDim ClusterNum break end end 计算各隐节点的扩展常数 宽度 i di 其中 di 是 Cj Ci k 的最小欧式距离 AllDistances dist Centers Centers 求隐节点数据中心间的距离 矩阵 Maximum max max AllDistances 找出其中最大的一个距离 for i 1 ClusterNum 某一类的中心到自身的欧式距离是 0 AllDistances i i Maximum 1 但要找隐节点间的最小距离 end 因此将对角线上的 0 替换为较大的值 Spreads Overlap min AllDistances 以隐节点间的最小距离作为扩展常数 计算各隐节点的输出权值 Distance dist Centers SamIn 计算各样本输入离各数据中心的距离 SpreadsMat repmat Spreads 1 SamNum repmat 径向基函数 j HiddenUnitOut radbas Distance SpreadsMat 计算隐节点输出阵 HiddenUnitOutEx HiddenUnitOut ones SamNum 1 考虑偏移 W2Ex SamOut pinv HiddenUnitOutEx 求广义输出权值 pinv 求伪逆 W2 W2Ex 1 ClusterNum B2 W2Ex ClusterNum 1 W2 B2 测试 TestDistance dist Centers TestSamIn TestSpreadsMat repmat Spreads 1 TestSamNum TestHiddenUnitOut radbas TestDistance TestSpreadsMat TestNNOut W2 TestHiddenUnitOut repmat B2 1 TestSamNum plot TestSamIn TestNNOut r 四 输出结果 当隐节点重叠系数 为 1 时 W2 Columns 1 through 8 0 9759 1 1956 1 2402 0 9509 1 3999 0 0311 0 1359 0 9232 Columns 9 through 10 0 7913 0 1700 B2 0 8289 当隐节点重叠系数 为 2 时 W2 Columns 1 through 8 7 6555 1 7326 0 0156 0 0815 11 8386 1 0188 0 7853 1 5740 Columns 9 through 10 9 3149 1 0047 B2 1 3042 五 结果分析 RBF 网络的学习过程与 BP 网络的学习过程类似 两种网络中隐节点 的非线性变换作用都是把线性不可分问题转化为线性可分问题 因此均可 用于函数逼近和分类 两者的主要区别在于各使用不同的激励函数 BP 网 络中隐层节点使用的是 Sigmoid 函数 其值在输入空间中无限大的范围内 为非零值 因而是一种全局逼近的神经网络 而 RBF 网络中的激励函数是 Gaussian 函数 是一种局部逼近的神经网络 其对于输入空间的某个局部 区域只有少数几个连接权影响网络的输出 因而与 BP 网络相比 RBF 网 络学习速度更快 聚类方法的优点是能根据各聚类中心之间的距离确定各隐节点的扩展 常数 缺点是确定数据中心时只用到了样本输入信息 而没有用到样本输 出信息 另外聚类方法也无法确定聚类的数目 RBF 网络的隐节点数 遗传算法 MATLAB 仿真 一 遗传算法 GA 的基本思想 基于达尔文进化论中的适者生存 优胜劣汰的基本原理 按生物学的 方法将问题的求解表示成 种群 Population 用计算机编程时 一般使 用二进制码串表示 从而构造出一群包括 N 个可行解的种群 将它们置于 问题的 环境 中 根据适者生存原则 对该种群按照遗传学的基本操作 不断优化生成新的种群 这样一代代地不断进化 最后收敛到一个最适应 环境的最优个体上 求得问题的最优解 遗传算法可以形式化的描述如下 GA P 0 N l s g p f t 其中 P 0 P1 0 P2 0 Pn 0 表示初始种群 N 表示种群中含有个 体的个数 l 表示二进制串的长度 s 表示选择策略 g 表示遗传算子 通 常它包括有选择 繁殖 算子 Qr 杂交算子 Qc和变异算子 Qm p 表示遗 传算子的操作概率 它包括选择概率 Pr Pc和变异概率 Pm f 是适应度 函数 t 是终止准则 二 Holland 遗传算法 SGA 该算法的操作对象是一群被称为种群的二进制位串 称为染色体 个 体 这里的每个染色体都对应求解问题的一个解 SGA 的基本思想是 从 初始种群出发 采用基于适应度比例的选择策略在当前种群中选择个体 使用杂交和变异来产生下一代种群 如此一代代演化下去 直至满足期望 的终止条件为止 执行一个简单的遗传算法时 需要做以下的准备工作 1 根据问题的要求选取设计变量 即明确需要优化的参数或方案 变量的取值范围构成问题的解空间 这是一个具体问题的数学抽象的过程 2 确定变量的约束条件 3 确定编码方案 遗传算法求解问题不是直接作用在问题的解空间上 而是利用解的某种编码表示 通常解 变量 空间中的一个解 变量 被 编码成一个串 它是由组成这个解 变量 的一系列有效信息组成 4 确定适应度函数 适应度值是对解的质量的度量 它是遗传算法对 种群中的个体执行各种遗传操作的唯一的依据 5 确定选择策略 个体的适应度值是策略中的主要依据 该步骤使适 应度值大的解在下一代有较大的存活概率 这种轮盘赌的选择策略具有正 反馈特征 在自然界中也屡屡出现这样的现象 最后的结局是可怕的 实 际设计中还可以选择锦标赛选择策略或者排序选择策略等 6 确定控制参数 它主要包括种群规模 执行不同遗传操作的概率以 及其它一些辅助性控制参数 7 设计遗传算子 进化算法中的遗传算子包括繁殖 选择 杂交变 异等操作 8 确定算法的条件终止准则 三 Holland 遗传算法流程图 GEN 0 i 0 i i i 1 i i 1 GEN GEN 1 Y N N Y 四 遗传算法 MATLAB 仿真实例 例 求下列函数的最大值例 求下列函数的最大值 f x 10 sin 5x 7 cos 4x x 0 10 其中将其中将 x 的值用一个的值用一个 10 位的二值形式表示 位的二值形式表示 解 分为八个部分 1 初始化 编码 initpop m 函数的功能是实现群体的初始化 popsize 表示群体的大小 chromlength 表示染色体的长度 二值数的长度 长度大小取决于变量的二 进制编码的长度 在本例中取 10 位 子程序文件名 initpop m 初始化 function pop initpop popsize chromlength pop round rand popsize chromlength rand 随机产生每个单元为 0 1 行数为 popsize 列数为 chromlength 的矩阵 round 对矩阵的每个单元进行取整 产生初始种群 2 计算目标函数值 1 将二进制串转化为相应的十进制 即 10 9 0 2089 2 bb b xb i i i 子程序文件名 decodebinary m 产生 2 n 2 n 1 1 的行向量 然后求和 将二进制转化为十进制 function pop2 decodebinary pop px py size pop 求 pop 行和例数 for i 1 py pop1 i 2 py 1 pop i py py 1 end pop2 sum pop1 2 求 pop1 的每行之 和 2 找到相应的实数 x 即 12 10 0 0 10 xx 其中 0 0 为区间 0 10 的左边界 10 为区间长度 decodechrom m 函数的功能是将染色体 或二进制编码 转换为十进制 参数 spoint 表示待解码的二进制串的起始位置 对于多个变量而言 如有两 个变量 采用 20 位表示 每个变量 10 位 则第一个变量从 1 开始 另一 个变量从 11 开始 本例为 1 参数 length 表示所截取的长度 本例为 10 子程序文件名 decodechrom m 将二进制编码转换成十进制 function pop2 decodechrom pop spoint length pop1 pop spoint spoint length 1 pop2 decodebinary pop1 3 计算目标函数值 calobjvalue m 函数的功能是实现目标函数的计算 子程序文件名 calobjvalue m 实现目标函数的计算 function objvalue calobjvalue pop temp1 decodechrom pop 1 10 将 pop 每行转化成十进制数 x temp1 10 2 10 1 将二值域中的数转化为变量域的数 objvalue 10 sin 5 x 7 cos 4 x 计算目标函数值 3 计算个体的适应值 子程序文件名 calfitvalue m 计算个体的适应值 function fitvalue calfitvalue objvalue global Cmin Cmin 0 px py size objvalue for i 1 px if objvalue i Cmin 0 temp Cmin objvalue i else temp 0 0 end fitvalue i temp end fitvalue fitvalue 4 选择复制 选择或复制操作是决定哪些个体可以进入下一代 程序中采用轮盘赌 式选择法进行选择 这种方法较易实现 根据方程 pi fi fi fi fsum 选择步骤 1 在第 t 代 由上式计算 fsum 和 pi 2 产生 0 1 的随机数 rand 求 s rand fsum 3 求 pi s 中最小的 k 则第 k 个个体被选中 4 进行 N 次 2 3 操作 得到 N 个个体 成为第 t t 1 代种群 子程序文件名 selection m 选择复制 function newpop selection pop fitvalue totalfit sum fitvalue 求适应值之和 fitvalue fitvalue totalfit 单个个体被选择的概率 fitvalue cumsum fitvalue 如 fitvalue 1 2 3 4 则 cumsum fitvalue 1 3 6 10 px py size pop ms sort rand px 1 从小到大排列 fitin 1 newin 1 while newin px if ms newin fitvalue fitin newpop newin pop fitin newin newin 1 else fitin fitin 1 end end 5 交叉 交叉 crossover 群体中的每个个体之间都以一定的概率 pc 交叉 即 两个个体从各自字符串的某一位置 一般是随机确定 开始互相交换 这 类似生物进化过程中的基因分裂与重组 例如 假设 2 个父代个体 x1 x2 为 x1 0100110 x2 1010001 从每个个体的第 3 位开始交叉 交叉后 得到 2 个新的子代个体 y1 y2 分别为 y1 0100001 y2 1010110 这 样 2 个子代个体就分别具有了 2 个父代个体的某些特征 利用交叉我们有 可能由父代个体在子代组合成具有更高适合度的个体 事实上交叉是遗传 算法区别于其它传统优化方法的主要特点之一 子程序文件名 crossover m 交叉 function newpop crossover pop pc px py size pop newpop ones size pop for i 1 2 px 1 if rand pc cpoint round rand py newpop i pop i 1 cpoint pop i 1 cpoint 1 py newpop i 1 pop i 1 1 cpoint pop i cpoint 1 py else newpop i pop i newpop i 1 pop i 1 end end 6 变