第四章(1)-智能决策支持系统和智能技术的决策支持2.ppt

第4章人工智能的决策支持和智能决策支持系统 第4章目录 4 1人工智能基本原理4 2专家系统与智能决策支持系统4 3神经网络的决策支持4 4遗传算法的决策支持4 5机器学习的决策支持 4 1人工智能基本原理 1 人工智能的决策支持技术从智能决策支持系统的概念可知智能决策支持系统中包含了人工智能技术 与决策支持有关的人工智能技术主要有 专家系统 神经网络 遗传算法 机器学习 自然语言理解等 专家系统是利用大量的专门知识解决特定领域中的实际问题的计算机程序系统 神经网络是利用神经元的信息传播模型 MP模型 进行学习和应用 遗传算法是模拟生物遗传过程的群体优化搜索方法 机器学习是让计算机模拟和实现人类的学习 获取解决问题的知识 自然语言理解是让计算机理解和处理人类进行交流的自然语言 4 1人工智能基本原理 2 智能决策支持系统结构形式1 基本结构智能决策支持系统 IDSS 决策支持系统 DSS 人工智能 AI 技术 4 1人工智能基本原理 人工智能技术可以概括为 推理机 知识库智能决策支持系统的结构可以简化为图4 2 4 2人工智能基本原理 4 2 1逻辑推理4 2 2知识表示与知识推理4 2 3搜索技术 4 2 1逻辑推理 1 形式逻辑 人的思维形式 规律 1 概念 反映事物的特有属性和属性的取值 2 判断 对概念的肯定或否定 判断本身有对有错 判断有全称的肯定 或否定 判断和存在的肯定 或否定 判断 3 推理 从一个或多个判断推出一个新判断的过程 4 2 1逻辑推理 2 推理的种类 演绎推理 归纳推理 类比推理 假言推理 三段论推理 数学归纳法 假言易位推理 枚举归纳推理 1 演绎推理 从一般现象到个别 特殊 现象的推理 2 归纳推理 从个别 特殊 现象到一般现象的推理 3 类比推理 从个别 特殊 现象到个别 特殊 现象的推理 1 演绎推理专家系统的研究基本上属于演绎推理范畴 演绎推理的核心是假言推理 假言推理 以假言判断为前提 对该假言判断的前件或后件的推理 1 假言推理 p q p q2 三段论推理 p q q r p r3 假言易位推理 拒取式 p q q p符号 表示推出 4 2 1逻辑推理 2 归纳推理 个别 一般 1 数学归纳法这种推导是严格的 结论是确实可靠的 2 枚举归纳推理S1是P S2是P Sn是PS1 Sn是S类事物中的部分分子 没有相反事例 所以 S类事物都是P 枚举归纳推理的结论是或然的 并非必然地 它的可靠性和事例数量相关 4 2 1逻辑推理 枚举归纳推理实例 如观察到铁受热膨胀 铜受热膨胀等事实而不知其所以然 由此推出 所有金属受热膨胀 的结论就是简单枚举归纳推理 3 类比推理它是由两个 或两类 事物在某些属性上相同 进而推断它们在另一个属性上也可能相同的推理 A事物有abcd属性 B事物有abc属性 或a b c相似属性 所以 B事物也可能有d属性 或d相似属性 类比推理的结论带有或然性 它的可靠性和相类比事物属性之间的联系程度有关 4 2 1逻辑推理 类比推理实例一 1816年的一天 法国医生雷奈克出诊为一位年轻的女性看病 一见病人 雷奈克犯起愁来 她身体非常肥胖 要诊断她的心脏和肺部是否正常 按当时医生惯用的方法 把耳朵贴近病人的胸部来听 肯定听不清楚 更何况她是一位年轻的女性 雷奈克抬头看了看院子里正在玩耍的小孩 脑子里突然浮现出几年前看到一个孩子们玩的游戏 一个孩子用钉子敲打木板的一头 另外的孩子争先恐后地抱着把耳朵贴近木板的另一头 兴致勃勃地倾听着 为什么木头能够把声音清晰地传过来呢 雷奈克稍微想了想 只见他很很地拍了一下手说 就是这样 就是这样 雷奈克要来一叠纸 紧紧地卷成一个卷 然后把纸卷的一端放在姑娘的胸部 另一端放在自己的耳朵上 侧着脸听了起来 真是一个妙法 雷奈克高兴地喊了一句 回到家里 雷奈克找到一根木棒 造成了历史上第一个 听诊器 类比推理实例一 类比推理实例二 19世纪30年代 英国商人威尔斯以与冯灿的茂隆皮箱商行订购的皮箱中有不是皮的木料为由 向香港法院起诉 蓄意敲诈冯灿 针对这种情况 冯灿的律师罗文锦取出口袋的金怀表 高声问法官 请问这是什么表 法官答道 这是金表 可是这与本案有什么关系 罗文锦高举金表 面对法庭上所有的人说 有关系 这是金表 没有人怀疑是吧 但是 请问 这块金表除表面镀金之外 内部的机制都是金制吗 旁听者同声议论 当然不是 罗文锦继续说 那么人们为什么又叫它金表呢 稍作停顿又高声说 由此可见 茂隆行的皮箱案不过是原告无理取闹 存心敲诈而已 原告理屈词穷 法庭最后以威尔斯诬告 罚款5000元结案 皮箱诉讼案的法庭辩论中 卖方律师在反驳中所使用的就是类比推理 表的外表有金 内部含有不是金的材料 但却是金表 箱的外表有皮 但也含有不是皮的材料 所以 箱仍是皮箱 类比推理实例二 3 总结1 演绎推理的结论没有超出已知的知识范围 而归纳推理和类比推理的结论超出已知的知识范围 演绎推理只能解释一般规律中的个别现象而归纳推理和类比推理创造了新的知识 使科学得到新发展 是一种创造思维方式 2 演绎推理中由于前提和结论有必然联系 只要前提为真 结论一定为真 归纳推理和类比推理中前提和结论 不能保证有必然联系 具有或然性 这样推理的结论未必是可靠的 需要经过严格的验证和证明 使之形成新的理论 4 2 1逻辑推理 4 2 2知识表示与知识推理 4 2 2 1数理逻辑表示法 自学 4 2 2 1产生式规则4 2 2 3语义网络4 2 2 4框架4 2 2 5剧本 自学 4 2 2 2产生式规则 ifAthenB 1 正向推理逐条搜索规则库 对每一条规则的前提条件 检查事实库中是否存在 前提条件中各子项 若在事实库中不是全部存在 放弃该条规则 若在事实库中全部存在 则执行该条规则 把结论放入事实库中 反复循环执行上面过程 直至推出目标 并存入事实库中为止 1 A B G2 C D A3 E D B C E 4 2 2 2产生式规则 事实库的最后状态为 B C E D A G 产生式规则库事实库 产生式规则库和事实库的初始状态为 4 2 2 2产生式规则 逆 反 向推理逆向推理是从目标开始 寻找以此目标为结论的规则对该规则的前提进行判断 若该规则的前提中某个子项是另一规则的结论时 再找以此结论的规则 重复以上过程 直到对某个规则的前提能够进行判断 按此规则前提判断 是 或 否 得出结论的判断 由此回溯到上一个规则的推理 一直回溯到目标的判断 G A D E B C 4 2 2 2产生式规则 逆向推理中 目标改变过程 1 A B G2 C D A3 E D B C E 产生式规则库事实库 4 2 3搜索技术 搜索技术是人工智能的一个重要研究内容 智能技术体现在减少搜索树中的盲目搜索 1 执行时间与 等成正比的算法 称为按多项式时间执行 2 执行时间与 和 等成正比的算法 称为按指数时间执行 按多项式时间执行的算法 计算机是可以实现的 按指数时间执行的算法 计算机是不可能实现的 4 2 3搜索技术 人工智能中发展了一种称为启发式搜索方法 基本思想可用一个实例来说明 一个外地人到某城市出差 他想到书店看看 又不知书店在何处 如果采取盲目搜索 从住地出发沿任一方向走 在分叉路口又任选一分支走 他可能走几天几夜也找不到如果采用启发式方法 他会问路上的人 到书店怎样走 城市中的大部分人对书店不知道 问不出来 4 2 3搜索技术 改一种问法 问该城市最热闹的地方在哪儿 按照这个启发式信息沿着指路人的路线 乘车到达最热闹的地方但书店在哪儿 仍然不知道 如果盲目搜索 可能仍然找不到 如果采用启发式方法 他会问路上的人 卖画的地方在哪儿 他可以通过画店再问书店在哪儿 启发式方法能减少大量盲目无效的搜索 能有效克服按指数时间执行的组合爆炸现象 4 2 3搜索技术 搜索方法分类 1 基本搜索法 1 广度优先搜索法 2 深度优先搜索法 2 生成测试法 3 爬山法 4 启发式搜索 5 博弈算法 1 极小极大搜索法 2 剪枝算法 4 2 3 1广度优先搜索 宽度优先搜索 1 广度优先搜索思想从初始状态S开始 利用规则 生成所有可能的状态 构成树的下一层节点 检查是否出现目标状态G 若未出现 就对该层所有状态节点 分别顺序利用规则 生成再下一层的所有状态节点 对这一层的所有状态节点检查是否出现G 若未出现 继续按上面思想生成再下一层的所有状态节点 这样一层一层往下展开 直到出现目标状态G为止 图4 7广度优先搜索示意图 2 算法 1 把初始节点S0故入OPEN表 2 如果OPEN表为空 则问题无解 退出 3 把OPEN表的第一个节点 记为节点n 取出放入CLOSED表 4 考察节点n是否为目标节点 若是 则求得了问题的解 退出 5 若节点n不可扩展 则转第2 步 6 扩展节点n 将其子节点放入OPEN表的尾部 并为每一个子节点都配置指向父节点的指针 然后转第2 步 广度优先搜索过程 例子1 八数码难题 重排九宫问题 在3x3的方格棋盘上放置分别标有数字1 2 3 4 5 6 7 8共8个棋子 初始状态为S0 目标状态为Sg 如图1所示 可使用的算符有 空格左移 空格上移 空格右移 空格下移 即只允许把位于空格左 上 右 下的邻近棋子移入空格 要求寻找从初始状态到目标状态的路径 该路径使用的算符序列 空格上移 空格左移 空格下移 空格右移 广度优先搜索的盲目性较大 当目标节点距离初始节点较远时将会产生许多无用节点 因此搜索效率低 但是 只要问题有解 用广度优先搜索总可以得到解 而且得到的是路径最短的路径 由图2可以看出 解的路径是 S0 3 8 16 26 广度优先法适合于搜索树的宽度较小的问题 1 深度优先搜索法思想从初始状态S开始 利用规则生成搜索树下一层任一个结点 检查是否出现目标状态G 若未出现 以此状态利用规则生成再下一层任一个结点 再检查是否为目标节点G 若未出现 继续以上操作过程 一直进行到叶节点 即不能再生成新状态节点 当它仍不是目标状态G时 回溯到上一层结果 取另一可能扩展搜索的分支 生成新状态节点 一直进行下去 直到找到目标状态G为止 4 2 3 2深度优先搜索法 图4 8深度优先搜索示意图 2 算法 1 把初始节点S0故入OPEN表 2 如果OPEN表为空 则问题无解 退出 3 把OPEN表的第一个节点 记为节点n 取出放入CLOSED表 4 考察节点n是否为目标节点 若是 则求得了问题的解 退出 5 若节点n不可扩展 则转第2 步 6 扩展节点n 将其全部子节点放入到OPEN表的首部 并为其配置指向父节点的指针 然后转第2 步 深度优先搜索 例子2 对图1所示的重排九宫问题进行深度优先搜索 可得到图3所示的搜索树这只是搜索树的一部分 尚未到达目标节点 仍需继续往下搜索 在深度优先搜索中 搜索一旦进入某个分支 就将沿着该分支一直向下搜索 如果目标节点恰好在此分支上 则可较快地得到解 但是 如果目标节点不在此分支上 而该分支又是一个无穷分支 则就不能得到解 所以深度优先搜索是不完备的 即使问题有解 它也不一定能求得解 显然 用深度优先求得的解 也不一定是路径最短的解 深度优先法适合于搜索树的深度较小的问题 4 2 3 3生成测试法 生成测试法算法是 1 生成一个可能状态节点 2 测试该状态是否为目标状态 3 若是目标状态则结束 否则回到第1步其中 生成可能的状态 可以是有规律的 也可以是无规律的 4 2 3 3生成测试法 1 如果搜索过程中 总是利用刚生成出的状态来生成新状态 这种生成测试法就是深度优先搜索法 2 如果搜索过程中 总是利用旧状态生成所有可能出新状态 而且状态节点以从旧到新的顺序逐个生成的原则 这种生成测试法就是广度优先搜索法 3 如果搜索过程中 有时利用旧状态生成新状态 有时利用新状态生成新状态 这就是无规律的生成测试法 4 2 3 4爬山法 生成测试法的变种 爬山算法 测试函数 1 开始状态作为一个可能状态 2 从一个可能状态 应用规则生成所有新的可能状态集 3 对该状态集中每一状态 进行如下操作 对该状态测试 检查是否为目标 是则停止 计算该状态的好坏 或者比较各状态的好坏 4 取状态集中最好状态 作为下一个可能状态 5 循环到第2步 在爬山法中可能出现以下几种情况 局部极大点 它比周围邻居状态都好 但不是目标 图4 9局部极大点示意图 在爬山法中可能出现以下几种情况 平顶 它与全部邻居状态都有同一个值 构成一个平面 图4 10平顶示意图 在爬山法中可能出现以下几种情况 山脊 它与线状邻居状态有相同值 比其它邻居状态要好 图4 11山脊示意图 4 2 3 4爬山法 为了解决以上问题 需要采用如下策略 1 退回到某一更早状态结点 沿着另一方向 对该结点就不一定是当时最好值的方向 进行爬山 2 朝一个方向前进一大步 按某方向深度优先搜索多次 走出平顶区 按别方向进行爬山 3 同时朝两个或多个方向前进 即按两个或多个方向爬山 4 2 3 5启发式搜索 启发式搜索是对每个在搜索过程中遇到的新状态 用一个估计函数 启发式函数 并计算其值的大小 确定下一步将从哪一个状态开始继续前进 一般以估计值小者为较优的状态 以此实行最优搜索 估计函数值的大小与从初始状态到达目标状态的路径有关 4 2 3 5启发式搜索 具体需要考虑以下问题 1 下一步选择哪个状态结点 2 是部分展开几个状态结点还是全部展开所有可能产生的状态结点 3 使用哪个规则 或算子 来展开新状态结点 4 怎样决定舍弃还是保留新生成的状态结点 5 如何定义启发式函数 估计值函数 6 如何决定搜索方向 7 怎样决定停止或继续搜索 一般启发式函数法用如下公式表示 f x g x h x f x 表示由开始状态到目标状态的总耗费g x 表示开始状态到当前状态的耗费 h x 表示当前状态到目标状态的耗费 4 2 3 5启发式搜索 启发式函数分析 1 当h x 0 即f x g x 取f x 为最小 即取g x 为最小 这要求在已扩展的结点中取最佳路径 g x 能保证找到最好解 但对搜索速度没有太多的帮助 2 当g x 0 即f x h x h x 是从当前状态到目标状态的耗费 取它最小 将会加快搜索速度 但它并不保证得到最优解 4 2 3 5启发式搜索 g x 选取的几种特例 g x 为搜索树的深度 h x 0 则启发式方法为广度优先搜索法 g x 为搜索树的深度的负数 h x 0 则启发式方法为深度优先搜索法 因为深度愈深 负数愈大 搜索法总向深度发展 3 g x 为初始状态到该结点的代价 则启发式方法为代价优选搜索法 f x 一般表示估计值 愈接近精确值 启发式效果愈好 如果是精确值 就不是启发式函数 4 2 3 5启发式搜索 图 4启发式搜索 4 4 5 5 4 5 3 5 4 2 3 0 5 4 5 5 4 5 3 2 0 4 h x 可以定义为节点x中数码位置与目标节点相比不同的个数 4 3专家系统与智能决策支持系统4 3 1专家系统原理4 3 2产生式规则专家系统4 3 3专家系统与DSS的集成4 3 4建模专家系统4 3 4智能决策支持系统 4 3 1专家系统原理 1 专家系统概念1 专家系统定义专家系统是具有大量专门知识 并能运用这些知识解决特定领域中实际问题的计算机程序系统 专家系统是利用大量的专家知识 运用知识推理的方法来解决各特定领域中的实际问题 计算机专家系统这样的软件能够达到人类专家解决问题的水平 4 3 1专家系统原理 2 专家系统的特点专家系统需要大量的知识 这些知识是属于规律性知识 它可以用来解决千变万化的实际问题 4 3 1专家系统原理 例如 求解微积分问题 是利用30 40条微分 积分公式来求解千变万化的微分 积分问题 得出各自的结果 其中微积分公式就是规律性知识 求解微积分问题就是对某函数反复利用微积分公式进行推导 最后得出该问题的结果 这个推理过程是一个不固定形式的推理 即前后用哪个公式 调用多少次这些公式都随问题变化而变化 1 专家系统对比数据库检索数据库中存放的记录可以看成是事实性知识 如果把检索数据库记录看成是推理的话 它也是一种知识推理 它与专家系统的不同在于 A 知识只含事实性知识 不包含规律性知识 B 推理是对已有记录的检索 记录不存在 则检索不到 不能适应变化的事实 推理不出新事实 4 3 1专家系统原理 4 3 1专家系统原理 2 专家系统对比数值计算数值计算是用算法解决实际问题 对不同的数据可以算出不同的结果 如果把数据看成是知识 算法看成推理的话 它也是一种知识推理 它与专家系统的不同在于 A 算法 推理过程 是固定形式的 算法一经确定 推理过程就固定了 而专家系统的推理是不固定形式的 随着问题不同 推理过程也不一样 B 数值计算只能处理数值 不能处理符号 知识处理的特点 从上面分析可见 数值计算 数据处理是知识处理的特定情况 知识处理则是它们的发展 A 知识包括事实和规则 状态转变过程 B 适合于符号处理 如微积分求解 C 推理过程是不固定形式的 推导过程中每次选用的规则知识是变化的 D 能得出未知的事实 如推导出新的微分公式 2 专家系统结构专家系统的核心是知识库和推理机 专家系统可以概括为 专家系统 知识库 推理机 4 3 1专家系统原理 知识获取 人机接口 知识库 推理机 专家 用户 咨询建议 专家系统核心 专家系统结构 3 产生式规则知识的推理机产生式规则的推理机 搜索 匹配 假言推理 在推理过程中 是一边搜索一边匹配 匹配需要找事实 这个事实一是来自于规则库中别的规则 一是来自向用户提问 在匹配时会出现成功或不成功 对于不成功的将引起搜索中的回溯和由一个分枝向另一个分枝的转移 可见在搜索过程中包含了回溯 4 3 1专家系统原理 4 3 1专家系统原理 4 产生式规则推理的解释推理中的搜索和匹配过程 如果进行跟踪和显示就形成了向用户说明的解释机制 好的解释机制不显示那些对于失败路径的跟踪 4 3 2产生式规则专家系统 4 3 2 1产生式规则4 3 2 2推理树 知识树 4 3 2 3逆向推理过程4 3 2 4事实数据和解释机制 4 3 2产生式规则专家系统 产生式规则的优点产生式规则知识表示形式容易被人理解它是基于演绎推理的 保证了推理结果的正确性大量产生式规则所连成的推理树 知识树 可以是多棵树 树的宽度 反映问题的范围树的深度 反映问题的难度 4 3 2 1产生式规则ES 产生式规则知识一般表示为 ifAthenB 或 如果A成立则B成立 或 A B 4 3 2 1产生式规则 产生式规则知识表示允许有如下的特点 相同的条件可以得出不同的结论 如 A BA C 相同的结论可以有不同的条件来得到 如A GB G 条件之间可以是 与 AND 连接和 或 OR 连接如A B GA B G 相当于A G B G 一条规则中的结论 可以是另一条规则中的条件 如F B C F其中F在前一条规则中是条件 在后一条规则中是结论 4 3 2 1产生式规则ES 由于以上特点 规则知识集能做到 能描述和解决各种不同的灵活的实际问题 由前三点特点形成 能把规则知识集中的所有规则连成一棵 与 或 推理树 知识树 即这些规则知识集之间是有关联的 由后二个特点形成 4 3 2 2推理树 知识树 规则库中的各条规则之间一般来说都是有联系的某条规则中的前提是另外一条规则中的结论 按逆向推理思想把知识库所含的总目标 它是某些规则的结论 作为根结点 按规则的前提和结论展开成一棵树的形式 这棵树一般称为推理树或知识树 它把知识库中的所有规则都连结起来由于连结时有 与 关系和 或 关系 从而构成了 与或 推理树 XF G LME C 4 3 2 2推理树 知识树 注 两斜线中间的弧线表示 与 关系 无弧线表示 或 关系 规则知识库的逆向推理树 例 若有知识库为 A B C G I J K AX F JL BM E CW Z MP Q E画出 与或 推理树 A B IJK WZ PQ 用规则的前提和结论形式画出逆向推理树形式为 4 3 2 2推理树 知识树 该 与或 推理树的特点是 每条规则对应的节点分枝有与 AND 关系 或 OR 关系 树的根结点是推理树的总目标 相邻两层之间是一条或多条规则连接 每个结点可以是单值 也可以是多值 若结点是多值时 各值对应的规则将不同 所有的叶结点 都安排向用户提问 或者把它的值直接放在事实数据库中 4 3 2 2推理树 知识树 4 3 2 3逆向推理过程 推理树的深度优先搜索 逆向推理过程在推理树中的反映为推理树的深度优先搜索过程 4 3 2 3逆向推理过程 在计算机中实现时 并不把规则连成推理树 而是利用规则栈来完成 当调用此规则时 把它压入栈内 相当于对树的搜索 当此规则的结论已求出 yes或no 时 需要将此规则退栈 相当于对树的回溯 利用规则栈的压入和退出的过程 相当于完成了推理树的深度优先搜索和回溯过程 4 3 2 3逆向推理过程 结点的否定每个结点有两种可能 即YES和NO 叶结点为NO是由用户回答形成的 中间结点为NO是由叶结点为NO 回溯时引起该结点为NO 若当该结点还有其它 或条件 分枝时 不能立即确定该结点为NO 必须再搜索另一分枝 当另一分枝回溯为YES时 该结点仍为YES 中间结点只有所有 或 分枝的回溯值均为NO时 才能最后确定该中间结点为NO 4 3 2 4事实数据库和解释机制 1 事实数据库 动态数据库 事实栏放入命题 规则号 事实取Y或N的理由 可信度 事实的可信度 2 解释机制解释机制是专家系统中重要内容 它把推理过程显示给用户 让用户知道目标是如何推导出来的 消除用户对目标结论的疑虑 两种实现方法一种是推理过程的全部解释 一种是推理过程中正确路径的解释 4 3 2 4事实数据库和解释机制 4 3 3专家系统与决策支持系统集成 IDSS充分发挥了专家系统以知识推理形式解决定性分析问题的特点 发挥了决策支持系统以模型计算为核心的解决定量分析问题的特点 充分做到定性分析和定量分析的有机结合 图4 16智能决策支持系统集成结构图 综合系统 DSS和ES的总体结合 由集成系统把DSS和ES有机结合起来2 KB和MB的结合 模型库中的数学模型和数据处理模型作为知识的一种形式 即过程性知识 加入到知识推理过程中去 3 DB和动态DB的结合 DSS中的DB可以看成是相对静态的数据库 它为ES中的动态数据库提供初始数据 ES推理结束后 动态DB中的结果再送回到DSS中的DB中去 DSS与ES集成形式一 DSS和ES并重的IDSS结构 4 3 3专家系统与决策支持系统集成 集成特点1 具有综合系统 具有调用和集成DSS和ES的能力 2 扩充DSS的问题与人机交互系统功能 增加对ES的调用组合能力DSS与ES的关系 DSS中DB与ES中的动态DB进行数据交换解决问题的特点体现定性分析和定量分析并重解决问题的特点 DSS与ES集成形式二 DSS为主体的IDSS结构 4 3 3专家系统与决策支持系统集成 集成特点集成系统和DSS控制系统合为一体DSS与ES的关系 ES被DSS控制系统调用解决问题的特点体现以定量分析为主 结果定性分析解决问题的特点 图4 19DSS作为推理形式的IDSS 图4 20模型作为知识的IDSS DSS与ES集成形式三 ES为主体的IDSS结构 4 3 3专家系统与决策支持系统集成 集成特点人机交互系统和ES合为一体 DSS与ES的关系 图4 19DSS作为推理机 受ES的推理机控制 图4 20数据模型作为知识出现 解决问题的特点体现以定量分析为主 结果定性分析解决问题的特点 4 3 4建模专家系统 专家系统实现模型选择的实例进行说明 例如 弹簧振动建模专家系统 该专家系统是解决弹簧在不同受力情况下 包括冲力 摩擦力等 应该满足那种类型的微分方程模型 弹簧振动建模专家系统进行简化说明如下 1 规则20条 R1 A B C M1R2 A1 AR3 A11 A1R4 A12 A1R5 A B E F M2R6 C1 CR7 E1 ER8 A B E F G M3R9 A B C G M4R10 B1 B R11 H1 HR12 A2 AR13 H B C M5R14 H B C G M6R15 H B E F M7R16 H B E F G M8R17 A B E I M9R18 A B I G M10R19 H B E I M11R20 H B E I G M12 4 3 4建模专家系统 A 弹簧满足胡克定律B 弹簧质量可以忽略C 可以忽略摩擦力D 没有冲力A1 弹簧有线性恢复力A11 弹力与位移成正比A12 位移量很小E 要考虑摩擦力F 摩擦力与速度之间为线性关系C1 若振动为自发时振幅为常数 E1 若振动为自发时振幅是递减的G 有冲力F T B1 弹簧具有质量N并且N M远远小于1H1 弹簧势能不是关于平衡位置对称H 弹簧不潢足胡克定律A2 弹簧势能与函数X T 成正比I 摩擦力与速度之间为非线性关系 各项英文字母含义为 M1 X C2 M X 0M2 X C1 M X C2 M X 0M3 X C1 M X C2 M X F T MM4 X C2 M X F T MM5 X F X M 0M6 X F X M F T MM7 X C1 M X F X M 0 M8 X C1 M X F X M F T MM9 X G M X C2 M X 0M10 X G M X C2 M X F T MM11 X G M X F X M 0M12 X G M X F X M F T M其中X 表示X对 的二阶导数 X 表示一阶导数 各模型微分方程为 3 规则库的推理树将20条规则连成的推理树见下图所示 每个叶节点提问的回答为 Y yes N no专家系统将解释为证实某条规则而安排的提问 用户不明白专家系统为什么要提该问题 可以回答 why 4 3 4建模专家系统 图4 21弹簧振动推理树的标准形式 专家系统应用 现有一个弹簧 满足如下特性 H1 弹簧势能不是关于平衡位置对称 B1 弹簧具有质量N并且N M远远小于1 C1 若振动为自发时振幅为常数 G 有冲力F T 通过专家系统推理将得出 该弹簧满足模型6 M6 的微分方程 4 5遗传算法的决策支持 4 5 1遗传算法原理4 5 2优化模型的遗传算法求解4 5 3获取知识的遗传算法4 5 4遗传规划建立模型 4 5 1遗传算法原理 遗传算法 GeneticAlgorithm GA 是模拟生物进化的自然选择和遗传机制的一种寻优算法 适用于复杂的非线性问题 主要应用在组合优化和机器学习两个方面 应用领域 图像识别 图像恢复 自适应控制 优化调度等领域 遗传算法的发展过程大体上可分为以下三个阶段 1 70年代的兴起阶段 1975年美国Michigan大学J Holland首次系统地阐述了遗传算法的基本理论和方法 在这一时期的大部分研究都处于理论研究和建立实验模型阶段 2 80年代的发展阶段 1980年Smith教授将遗传算法应用于机器学习领域 研制出了一个著名的分类器 Classifier 系统 这期间许多学者对遗传算法进行了大量的改进和发展 提出了许多成功的遗传算法模型 使遗传算法应用于更广泛的领域 3 90年代的高潮阶段 进入90年代后 遗传算法作为一种实用 高效的优化技术 得到了极为迅速的发展 4 5 1遗传算法原理 4 5 1遗传算法原理 4 5 1 1遗传算法工作过程4 5 1 2遗传算法的理论基础4 5 1 3遗传算法的基本特征 4 5 1 1遗传算法的工作过程 遗传算法是一种群体型操作 该操作以群体中的所有个体为对象 个体就是模拟生物个体而对问题中的对象 一般就是问题的解 的一种称呼 一个个体也就是搜索空间中的一个点 种群 population 就是模拟生物种群而由若干个体组成的群体 它一般是整个搜索空间的一个很小的子集 遗传算法的三个主要操作算子 选择 selecation 交叉 crossover 和变异 mutation 构成了遗传操作 Geneticoperation 使遗传算法具有了其他传统方法所没有的特性 产生新一代群体 编码和初始群体形成 个体适应值满意否 4 5 1 1遗传算法的工作过程 首先将问题的每个可能的解按某种形式编码 编码后的解称作染色体 个体 随机选取N个染色体构成初始种群 再根据预定的评价函数对每个染色体计算适应值 使得性能较好的染色体具有较高的适应值 选择适应值高的染色体进行复制 通过遗传算子来产生一群新的更适应环境的染色体 形成新的种群 这样一代一代不断繁殖 最后收敛到一个最适应环境的个体上 求得问题的最优解 1 群体中个体的编码如何将问题描述成位串的形式 即问题编码 一般将问题的参数用二进制位 基因 编码构成子串 再将子串拼接起来构成 染色体 位串 4 5 1 1遗传算法的工作过程 例如 个体染色体9 1001 2 5 6 010101110 2 适应值函数的确定遗传算法的执行过程中 每一代有许多不同的染色体 个体 同时存在 这些染色体中哪个保留 生存 哪个淘汰 死亡 是根据它们对环境的适应能力决定的 适应性强的有更多的机会保留下来 适应性强弱是计算个体适应值函数f x 的值来判别的 这个值称为适应值 fitness 适应值函数 即评价函数 是根据目标函数确定的 适应值总是非负的 任何情况下总是希望越大越好 如果目标函数不是取最大值时 需要将它映射成适应值函数 适应值函数f x 的构成与目标函数有密切关系 往往是目标函数的变种 一般是一个实值函数 该函数就是遗传算法中指导搜索的评价函数 4 5 1 1遗传算法的工作过程 3 遗传算法的三个算子 一 选择 Selection 算子 二 交叉 Crossover 算子 三 变异 Mutation 算子 4 5 1 1遗传算法的工作过程 它又称复制 reproduction 繁殖算子 选择是从种群中选择生命力强的染色体产生新种群的过程 依据每个染色体的适应值大小 适应值越大 被选中的概率就越大 其子孙在下一代产生的个数就越多 选择操作是建立在群体中个体的适应值估评基础上的 4 5 1 1遗传算法的工作过程 一 选择 Selection 算子 通常做法是 对于一个规模为N的种群S 按每个染色体xi S的选择概率P xi 所决定的选中机会 分N次从S中随机选定N个染色体 并进行复制 4 5 1 1遗传算法的工作过程 一 选择 Selection 算子 二 交叉 crossover 算子 它又称重组 recombination 配对 breeding 算子 在遗传算法中起着核心作用 染色体重组是分两步骤进行的 首先在新复制的群体中随机选取两个个体然后 沿着这两个个体 字符串 随机地取一个位置 二者互换从该位置起的末尾部分 交叉率 crossoverrate 就是参加交叉运算的染色体个数占全体染色体总数的比例 记为Pc 取值范围一般为0 4 0 99 4 5 1 1遗传算法的工作过程 4 5 1 1遗传算法的工作过程 例1 有两个用二进制编码的个体A和B 长度L 5 A a1a2a3a4a5 B b1b2b3b4b5随机选择一整数k 1 L 1 设k 4 经交叉后变为 A a1a2a3 a4a5 B b1b2b3 b4b5A a1a2a3b4b5 B 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 它保证了遗传算法的有效性 4 5 1 1遗传算法的工作过程 三 变异 Mutation 算子 4 5 1 1遗传算法的工作过程 例如 设染色体s 11001101将其第三位上的0变为1 即s 11001101 11101101 s s 也可以看做是原染色体s的子代染色体 三 变异 Mutation 算子 4 控制参数设定遗传算法中的参数包括群体中个体的数目 交叉概率 变异概率等这些参数的设定随具体问题的不同将有所差别 带有经验性 它会影响遗传算法的迭代收敛过程 4 5 1 1遗传算法的工作过程 1 模式定理遗传算法的理论基础是Holland提出的模式定理 一个模式 Schema 就是一个描述种群中在位串的某些确定位置上具有相似性的位串子集的相似性模板 SimilarityTemplate 二进制串中的模式是如下的形式 a1 a2 ai an ai 0 1 其中 是任意符 或0 或1 模式是串的集合 模式H中确定位的个数 称为H的阶 记为O H 模式H中第一个确定位与最后一个确定位之间的距离称为的定义距 记为 H 4 5 1 2遗传算法的理论基础 例 以长度L 5的串为例 模式 101 描述了在位置2 3 4具有形式 010 的所有字符串 101 11010 01010 01011 11011 其阶为3 定义距为2 1 模式定理模式定理是遗传算法的理论基础它说明高适应值 长度短 阶数低的模式在后代中至少以指数增长包含该模式H的位串的数目 遗传使高适应值的模式复制更多的后代 4 5 1 2遗传算法的理论基础 2 基因块假设高适应值 长度短 低阶的模式叫基因块 基因块假说基因块通过遗传操作繁殖 交换 变异 再繁殖 再交换 再变异的逐渐进化 形成潜在的适应性较高的位串 该假设指出 通过遗传算法能寻找到接近全局最优解的能力 4 5 1 2遗传算法的理论基础 1 遗传算法的处理对象是问题参数的编码个体 位串 遗传算法要求将问题的参数编码成长度有限的位串 遗传算法是在求解问题的编码串上进行操作 从中找出高适应值的位串 而不是对问题目标函数和它们的参数直接操作 遗传算法不受函数限制条件 如导数存在 连续性 单极值等 的约束 4 5 1 3遗传算法的基本特征 2 遗传算法的搜索是从问题解位串集开始搜索 而不是从单个解开始在最优化问题中 传统的方法是从一个点开始搜索 如爬山法 一般复杂问题会在 地形 中出现若干 山峰 传统的方法很容易走入假 山峰 遗传算法同时从种群的每个个体开始搜索 象一张网罩在 地形 上 数量极大的个体同时在很多区域中进行搜索 这样就减少了陷入局部解的可能性 4 5 1 3遗传算法的基本特征 3 遗传算法只使用目标函数 即适应值 来搜索 而不需要导数等其他辅助信息传统搜索算法需要一些辅助信息 如梯度算法需要导数 当这些信息不存在时 这些算法就失效了 而遗传算法只需目标函数和编码串 因此 遗传算法几乎可以处理任何问题 4 遗传算法使用的三种遗传算子是一种随机操作 而不是确定性规则遗传算法使用随机操作 但并不意味着遗传算法是简单的随机搜索 遗传算法是使用随机工具来指导搜索向着一个最优解前进 5 隐含的并行性6 易介入到已有的模型中 并具有扩展性 易于同别的技术结合使用 4 5 1 3遗传算法的基本特征 4 5 2优化模型的遗传算法求解 优化模型的计算是遗传算法最基本的也是最重要的研究和应用领域之一 一般说来 优化计算问题通常带有大量的局部极值点 往往是不可微的 不连续的 多维的 有约束条件的 高度非线性的NP完全问题 精确地求解优化问题的全局最优解一般是不可能的 4 5 2优化模型的遗传算法求解 4 5 2 1优化模型的遗传算法处理4 5 2 2实例 1 适应值函数优化遗传算法在进化搜索中用目标函数即适应值函数为依据 遗传算法的目标原函数不受连续可微的约束且定义域可以为任意集合对目标函数的唯一要求是 对输入个体可计算出能进行比较的非负适应值 这一特点使得遗传算法应用范围很广 遗传算法中 适应值函数要比较排序 并在此基础上计算选择概率 所以适应值函数的值要取正值 适应值函数评估是选择操作的依据 适应值函数设计直接影响到遗传算法的性能 在不少场合 将目标函数映射成求最大值形式且函数值非负的适应值函数是必要的 4 5 2 1优化模型的遗传算法处理 2 约束条件的处理遗传算法是由适应值来评估和引导搜索 而对求解问题的约束条件不能明确地表示出来 用遗传算法求解这些带约束的问题 需要进行一些处理 在等式约束方程中 对P个等式方程中抽出P个变量 经过线性组合变换后 用其余变量表示为该P个变量的等式 并将它代入目标函数中 消去该P个变量 这样 在目标函数中 就包含了这些等式约束条件 4 5 2 1优化模型的遗传算法处理 4 5 2 1优化模型的遗传算法处理 3 遗传算法的迭代终止条件当适应值函数的最大值已知时 一般以发现满足最大值或准最优解作为遗传算法迭代终止条件 但是 在许多优化计算问题中 适应值函数的最大值并不清楚 迭代终止条件一般定为 群体中个体的进化已趋于稳定状态 即发现占群体中一定比例的个体已完全是同一个体 步1在搜索空间U上定义一个适应度函数f x 给定种群规模N 交叉率Pc和变异率Pm 代数T 步2随机产生U中的N个个体s1 s2 sN 组成初始种群S s1 s2 sN 置代数计数器t 1 步3计算S中每个个体的适应度f 步4若终止条件满足 则取S中适应度最大的个体作为所求结果 算法结束 步5按选择概率P xi 所决定的选中机会 每次从S中随机选定1个个体并将其染色体复制 共做N次 然后将复制所得的N个染色体组成群体S1 步6按交叉率Pc所决定的参加交叉的染色体数c 从S1中随机确定c个染色体 配对进行交叉操作 并用产生的新染色体代替原染色体 得群体S2 步7按变异率Pm所决定的变异次数m 从S2中随机确定m个染色体 分别进行变异操作 并用产生的新染色体代替原染色体 得群体S3 步8将群体S3作为新一代种群 即用S3代替S t t 1 转步3 基本遗传算法步聚 例4 1利用遗传算法求解区间 0 31 上的二次函数y x2的最大值 分析原问题可转化为在区间 0 31 中搜索能使y取最大值的点a的问题 那么 0 31 中的点x就是个体 函数值f x 恰好就可以作为x的适应度 区间 0 31 就是一个 解 空间 这样 只要能给出个体x的适当染色体编码 该问题就可以用遗传算法来解决 解 1 设定种群规模 编码染色体 产生初始种群 将种群规模设定为4 用5位二进制数编码染色体 取下列个体组成初始种群S1 s1 13 01101 s2 24 11000 s3 8 01000 s4 19 10011 2 定义适应度函数 取适应度函数 f x x2 3 计算各代种群中的各个体的适应度 并对其染色体进行遗传操作 直到适应度最高的个体 即31 11111 出现为止 首先计算种群S1中各个体s1 13 01101 s2 24 11000 s3 8 01000 s4 19 10011 的适应度f si 容易求得f s1 f 13 132 169f s2 f 24 242 576f s3 f 8 82 64f s4 f 19 192 361 再计算种群S1中各个体的选择概率 选择概率的计算公式为 由此可求得P s1 P 13 0 14P s2 P 24 0 49P s3 P 8 0 06P s4 P 19 0 31 赌轮选择示意 赌轮选择法 在算法中赌轮选择法可用下面的子过程来模拟 在 0 1 区间内产生一个均匀分布的随机数r 若r q1 则染色体x1被选中 若qk 1 r qk 2 k N 则染色体xk被选中 其中的qi称为染色体xi i 1 2 n 的积累概率 其计算公式为 选择 复制 设从区间 0 1 中产生4个随机数如下 r1 0 450126 r2 0 110347r3 0 572496 r4 0 98503 于是 经复制得群体 s1 11000 24 s2 01101 13 s3 11000 24 s4 10011 19 交叉设交叉率pc 100 即S1中的全体染色体都参加交叉运算 设s1 与s2 配对 s3 与s4 配对 分别交换后两位基因 得新染色体 s1 11001 25 s2 01100 12 s3 11011 27 s4 10000 16 变异设变异率pm 0 001 这样 群体S1中共有4 5 0 001 0 02位基因可以变异 0 02位显然不足1位 所以本轮遗传操作不做变异 于是 得到第二代种群S2 s1 11001 25 s2 01100 12 s3 11011 27 s4 10000 16 第二代种群S2中各染色体的情况 假设这一轮选择 复制操作中 种群S2中的4个染色体都被选中 则得到群体 s1 11001 25 s2 01100 12 s3 11011 27 s4 10000 16 做交叉运算 让s1 与s2 s3 与s4 分别交换后三位基因 得 s1 11100 28 s2 01001 9 s3 11000 24 s4 10011 19 这一轮仍然不会发生变异 于是 得第三代种群S3 s1 11100 28 s2 01001 9 s3 11000 24 s4 10011 19 第三代种群S3中各染色体的情况 设这一轮的选择 复制结果为 s1 11100 28 s2 11100 28 s3 11000 24 s4 10011 19 做交叉运算 让s1 与s4 s2 与s3 分别交换后两位基因 得 s1 11111 31 s2 11100 28 s3 11000 24 s4 10000 16 这一轮仍然不会发生变异 于是 得第四代种群S4 s1 11111 31 s2 11100 28 s3 11000 24 s4 10000 16 显然 在这一代种群中已经出现了适应度最高的染色体s1 11111 于是 遗传操作终止 将染色体 11111 作为最终结果输出 然后 将染色体 11111 解码为表现型 即得所求的最优解 31 将31代入函数y x2中 即得原问题的解 即函数y x2的最大值为961 Y 旅行商问题 TSP 的遗传算法求解实例 已知n个城市的地理位置 x y 求经过所有城市 并回到出发城市且每个城市仅经过一次的最短距离 这是一个NP完全问题 其计算量为城市个数的指数量级 现用遗传算法来解决这个问题 1 编码 每条路径对应一个个体 个体形式地表示为R City No City No互不重复 n n为城市数 例如对于n 10的TSP问题 对其中一个个体 它表示一条城市路径 31578910426 其中ni表示个体中第i位的城市编号 n11 n1 适应值为非负 且取值越大越好 表示所有个体的路径长度的总和 2 适应值函数 每个个体代表一条可能的路径 个体n的适应值为 其中N为种群数 Dn为沿个体标示的城市序列的所经过的距离 3 交叉 随机地从种群中选出要交叉的两个不同个体 随机地选取一个交叉段 交叉段中两个个体的对应部分通过匹配换位实现交叉操作 对个体A和B A 984 567 13210B 871 4103 2965交叉段对