《搜索技术》PPT课件.pptVIP

第三章搜索技术 第一节引言一 搜索对于无成熟方法可用的问题求解 必须一步步地摸索求解 这种问题求解过程就是搜索 注 搜索技术是人工智能的核心技术之一 二 研究和选用搜索算法的原则1 有限搜索还是无限搜索 若搜索空间有限 则任何一种穷举算法均能完成任务 第三章搜索技术 第一节引言二 研究和选用搜索算法的原则2 搜索空间是静态的还是动态生成的 在人工智能中 搜索的对象 常称状态 是在搜索过程中逐步生成的 需将搜索对象的生成和评估的代价计算在内 对于一般搜索 搜索空间基本是静态的 或表或数组或数据库 3 已知目标还是未知目标 4 只要目标还是也要路径 路径是解题过程中应用的操作序列 第三章搜索技术 第一节引言二 研究和选用搜索算法的原则5 状态空间搜索还是问题空间搜索 在解题过程中的每一时刻 所要解决的问题均处于一定的状态 搜索过程只是将一个状态变成另一个状态 如 一盘棋局变成另一盘棋局 则称为状态空间搜索 若搜索的对象是问题 搜索的原则是把一个复杂的问题化为一组比较简单的子问题 如把一个复杂的下棋策略分为几个子策略 则称为问题空间搜索 注 问题空间搜索常常比状态空间搜索有效 但算法要复杂些 第三章搜索技术 第一节引言二 研究和选用搜索算法的原则6 有约束还是无约束 问题空间搜索时 若子问题间互相无约束关系 则求接比较简单 否则 一般需要回溯 即 放弃已解决的子问题 走回头路 寻找新的解法 7 数据驱动还是目标驱动 数据驱动是向前搜索 目标驱动是向后搜索 8 单向搜索还是双向搜索 第三章搜索技术 第一节引言二 研究和选用搜索算法的原则9 盲目搜索还是启发式搜索 按照预定的控制策略实行搜索 在搜索过程中获取的中间信息不用来改进控制策略 称为盲目搜索 反之 称为启发式搜索 注 关于 启发式 可有两种看法 1 任何有助于找到问题的解 但不能保证找到解的方法均是启发式方法 2 有助于加速求解过程和找到较优解的方法是启发式方法 第三章搜索技术 第一节引言二 研究和选用搜索算法的原则10 有对手搜索还是无对手搜索 若有两个控制源均能改变同一状态空间 并且任何一方向目标前进时 另一方均试图将它从目标拉开 则称为有对手搜索 通常称为博弈搜索 注 博弈搜索算法可以看成是一种特殊的问题空间搜索 第三章搜索技术 第一节引言三 一般搜索方法分类1 盲目搜索1 无变量的盲目搜索状态空间 问题空间的盲目搜索深度优先 广度优先 代价优先 混合向前 向后 双向2 有变量的盲目搜索通代2 启发式搜索 第三章搜索技术 第二节启发式搜索一 启发式搜索把要求解的问题的具体领域的知识加进搜索算法中 控制搜索过程 以提高算法效率的搜索方法 称为启发式搜索 注 1 这里 搜索的对象 常称状态 往往是边搜索边生成 因此在考虑这种搜索的复杂性时 必须将搜索对象的生成和评估的代价计算在内 第三章搜索技术 第二节启发式搜索一 启发式搜索注 2 根据启发性信息 特定领域的知识信息 在生成搜索树时可考虑种种可能的选择 a 下一步展开哪个节点 b 是部分展开还是全部展开 c 使用哪个规则 算子 d 怎样决定舍弃还是保留新生成的节点 e 怎样决定舍弃还是保留一棵子树 f 怎样决定停止或继续搜索 g 如何定义启发函数 估值函数 h 如何决定搜索方向 第三章搜索技术 第二节启发式搜索二 有序搜索算法1 基本思想a 对于每个在搜索过程中遇到的新状态 计算一个估计值 根据估计值的大小 确定下一步将从哪一个状态开始继续前进 b 一般以估计值小者作为较优的状态 以此实现最佳优先搜索 c 计算状态估计值的函数是确定的 但每个状态的估计值的大小与初始状态到该路径有关 第三章搜索技术 第二节启发式搜索二 有序搜索算法2 算法1 建立一个空的状态序列SS2 建立一个空的状态库SB3 定义一个估值函数f4 若初始状态为S0 则定义初始状态S0 0 f 0 为当前新状态5 将当前新状态按估计值从小到大的顺序插入到SS中 若新状态为目标状态 则将相应状态插入到具有相同估计值的状态的最前面 否则将相应状态插入到具有相同估计值的状态的最后面 第三章搜索技术 第二节启发式搜索二 有序搜索算法2 算法6 若在SS或SB中原有一个状态与当前新状态共一个状态 则删去原有状态7 若新状态在SS的最前面 则转11 8 若某种状态极限已达到 则搜索失败 算法运行结束 无解 第三章搜索技术 第二节启发式搜索二 有序搜索算法2 算法9 若任何规则均不能应用于状态序列SS中的第一个状态 或者虽能应用 但不能产生合适的新状态 在SS或SB中均没有者 称为新 或虽能产生合适的新状态S path2 f path2 但不是改进型的 若SS和SB中已有状态S path1 f path1 它与新状态共一个状态S 且f path2 f path1 则称新状态不是改进型的 则将此第一个状态从SS中除去 送入SB中 否则转12 第三章搜索技术 第二节启发式搜索二 有序搜索算法2 算法10 若SS成为空序列 则搜索失败 算法运行结束 无解11 若SS中第一个状态已是目标状态 则搜索成功 算法运行结束 若该状态形如S path f path 则解就是 path 否则转9 12 取一个可应用于SS的第一个状态S path f path 并产生改进型的合适新状态的规则Rn 产生新状态T path n f path 定义它为当前新状态 转5 算法完 第三章搜索技术 第二节启发式搜索二 有序搜索算法2 算法注 1 状态是带路径和估计值的状态 而状态只是一个状态2 对当前生成的新状态是否是目标状态的判断需要两次3 这里每次只生成一个后代4 给定估计值函数f的意义 则有序搜索就可归结为已知的搜索 如令f为状态节点的深度 则有序搜索就成为广度优先搜索 第三章搜索技术 第二节启发式搜索二 有序搜索算法2 算法注 5 有序搜索算法不一定找到解 即使有解6 有序搜索算法的特点是使用启发式信息 表现在估计值函数f上 可是启发式信息也会骗人 会引人误入歧途7 有序搜索即使能找到解 也未必一定是最优的 第三章搜索技术 第二节启发式搜索二 有序搜索算法3 算法改进1 用多个估计值函数来 层层设卡 2 对估计值函数的形式加以限制 以保证它一定能找到解 甚至一定能找到最优解 第三章搜索技术 第二节启发式搜索三 估计值函数的改进令S为初始节点 ti为一组目标节点 n ni nj为任意节点k ni nj 为从ni到nj的最小代价g n k S n 为从初始节点S到节点n的最小代价h n mink n ti 为从节点n到一个目标节点ti的最小代价f n g n h n 为从初始节点出发 经过节点n 到达一个目标节点的最小代价 ti 第三章搜索技术 第二节启发式搜索三 估计值函数的改进g n 为对g n 的估计 g n 0h n 为对h n 的估计 h n 0f n g n h n 为每个节点n处的估计值函数 第三章搜索技术 第二节启发式搜索四 H算法使用上述改进的估计值函数f的有序搜索算法就是H算法 注 1 g n 是容易找到的 如将从初始节点到节点n实际上走过的路径的代价作为g n 且永远有g n g n g n 不断改进 随着更多的搜索信息的获取 g n 的值呈下降趋势 2 h n 的选取要与具体问题领域的启发信息相关 3 由于h n 的选择仍有很大的随意性 因此 H算法并不能保证找到一个解 更不能保证找到最优解 从而需要改进 第三章搜索技术 第二节启发式搜索五 H 算法1 在H算法中规定h n h n 2 推广k ni nj 的定义 令k n1 n2 nm 为从n1出发 经过n2 到达nm的最小代价 规定存在一个正整数e 0 使得对任意的ni nj nm nj nm 均有k ni nj nm k ni nj e3 经过如此限制以后的H算法就是H 算法 注 1 可以证明 只要目标状态存在 并且从初始状态到目标状态有一条通路 则H 算法一定在有限步内终止 并找到一个最优解 即代价为最低的解 第三章搜索技术 第二节启发式搜索五 H 算法注 2 H 算法的搜索效率在很大程度上取决于函数h n 的选择 它要求h n h n 但若h n 太小 则启发信息就很少 3 若h n 0 g n 为搜索深度或代价 则H 算法将退化为广度优先搜索或代价优先搜索 4 h n 的值在满足小于或等于h n 的前提下越大越好 启发式信息多 即h值大 的H 算法展开的节点是启发式信息少 即h值小 的H 算法展开的节点的子集 第三章搜索技术 第二节启发式搜索五 H 算法注 5 若估计值函数h n 满足单调条件 h ni h nj k ni nj 其中k ni nj 是从ni到nj的最小代价 nj是ni的后续节点 则H 算法是循着从初始状态通向该节点的最优路径到达该节点的 6 在H 算法中 每次只生成一个后续节点 第三章搜索技术 第二节启发式搜索六 完全展开的有序搜索算法1 建立一个空的状态序列SS2 建立一个空的状态库SB3 定义一个估值函数f4 若初始状态为S0 则定义初始状态S0 0 f 0 为当前新状态5 将所有当前新状态按估计值从小到大的顺序插入到SS中 第三章搜索技术 第二节启发式搜索六 完全展开的有序搜索算法6 若在SS或SB中原有一个状态与当前某个新状态共一个状态 则删去原有状态7 若SS的第一项是一个新状态 则转11 8 若某种状态极限已达到 则搜索失败 算法运行结束 无解 第三章搜索技术 第二节启发式搜索六 完全展开的有序搜索算法9 若任何规则均不能应用于状态序列SS中的第一个状态 或者虽能应用 但不能产生改进型的合适新状态 则将此第一个状态从SS中除去 送入SB中 否则转12 10 若SS成为空序列 则搜索失败 算法运行结束 无解11 若SS中第一个状态已是目标状态 则搜索成功 算法运行结束 若该状态形如S path f path 则解就是 path 否则转9 第三章搜索技术 第二节启发式搜索六 完全展开的有序搜索算法12 取所有可应用于SS的第一个状态S path f path 并产生各不相同的改进型的合适新状态的规则Ri i I 产生新状态集T path i f path 其中对属于同一状态的各个状态只取一个最优者 转5 算法完 第三章搜索技术 第二节启发式搜索七 A算法使用估计值函数f n g n h n 的完全展开的有序搜索算法 第三章搜索技术 第二节启发式搜索八 A 算法在A算法规定 h n h n k ni nj nm k ni nj e 则A算法成为A 算法注 1 A 算法与H 算法的主要区别有a 在H 算法中每次只生成一个后继节点 而在A 算法中每次生成一个节点的所有节点b 在H 算法中 每生成一个新节点 就询问它是否是目标节点 而在A 算法中 只询问栈顶节点是否是目标节点2 在A 算法中 估计值函数f n g n h n 的选择是一个关键 第三章搜索技术 第二节启发式搜索八 A 算法注 3 A 算法一定能保证找到最优解4 若按展开的节点个数来估计它的效率 则当启发式函数h的值单调上升时 它的效率只会上升 不会下降 且有较合理的渐近性质5 若不是考虑被展开的节点个数 而是考虑各节点被展开的次数 则A 算法在最坏情况下表示出很高的复杂性6 为了避免不正常的h值对解题路径的影响 Martelli提出了B算法 基本思想是h n 可动态修改 在h值不正常时 只根据g的值来选择展开的节点 第三章搜索技术 第二节启发式搜索八 A 算法注 7 在f x g x h x 中 g x 是 经验 项 起着稳定形势的作用 而h x 是 冒险 项 九 双向启发式搜索十 几种特殊的启发式搜索1 生成与测试方法穷举 仍需要经验知识的指导2 并行搜索法3 爬山法4 黄金分割法十一 与或树的启发式搜索AO 算法 第二节启发式搜索十二 遗传算法1 基本概念模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法 第三章搜索技术 第三章搜索技术 第二节启发式搜索十二 遗传算法2 基本思想对于一个求函数最大值的优化问题 一般可描述为下述数学规划模型 第三章搜索技术 第二节启发式搜索十二 遗传算法2 基本思想式中 为决策变量 f X 为目标函数 U是基本空间 R是U的一个子集 遗传算法中 将n维决策向量用n个记号所组成的符号串X来表示 第三章搜索技术 第二节启发式搜索十二 遗传算法2 基本思想把每一个看作一个遗传基因 它的所有可能取值称为等位基因 这样 X就可看作是由n个遗传基因所组成的一个染色体 染色体的长度可以是固定的 也可以是变化的 等位基因可以是一组整数 也可以是某一范围内的实数值 或者是记号 最简单的等位基因是由0和1这两个整数组成的 相应的染色体就可表示为一个二进制符号串 第三章搜索技术 第二节启发式搜索十二 遗传算法2 基本思想这种编码所形成的排列形式X是个体的基因型 与它对应的X值是个体的表现型 染色体X也称为个体X 对于每一个个体X 要按照一定的规则确定出其适应度 个体的适应度与其对应的个体表现型X的目标函数值相关联 X越接近于目标函数的最优点 其适应度越大 反之 其适应度越小 第三章搜索技术 第二节启发式搜索十二 遗传算法2 基本思想遗传算法中 决策变量X组成了问题的解空间 对问题最优解的搜索是通过对染色体X的搜索过程来进行的 从而由所有的染色体X就组成了问题的搜索空间 生物的进化是以集团为主体的 与此相对应 遗传算法的运算对象是由M个个体所组成的集合 称为群体 第三章搜索技术 第二节启发式搜索十二 遗传算法2 基本思想与生物一代一代的自然进化过程相似 遗传算法的运算过程也是一个反复迭代过程 第t代群体记做P t 经过一代遗传和进化后 得到第t 1代群体 它们也是由多个个体组成的集合 记做P t 1 这个群体不断地经过遗传和进化操作 并且每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代 这样最终在群体中将会得到一个优良的个体X 它所对应的表现型X将达到或接近于问题的最优解 第三章搜索技术 第二节启发式搜索十二 遗传算法2 基本思想生物的进化过程主要是通过染色体之间的交叉和染色体的变异来完成的 遗传算法中最优解的搜索过程也模仿生物的这个进化过程 使用所谓的遗传算子 geneticoperators 作用于群体P t 中 进行下述遗传操作 从而得到新一代群体P t 1 第三章搜索技术 第二节启发式搜索十二 遗传算法2 基本思想选择 selection 根据各个个体的适应度 按照一定的规则或方法 从第t代群体P t 中选择出一些优良的个体遗传到下一代群体P t 1 中 交叉 crossover 将群体P t 内的各个个体随机搭配成对 对每一个个体 以某个概率 称为交叉概率 crossoverrate 交换它们之间的部分染色体 第三章搜索技术 第二节启发式搜索十二 遗传算法2 基本思想变异 mutation 对群体P t 中的每一个个体 以某一概率 称为变异概率 mutationrate 改变某一个或一些基因座上基因值为其它的等位基因 第三章搜索技术 第二节启发式搜索十二 遗传算法3 特点遗传算法是一类可用于复杂系统优化计算的鲁棒搜索算法 与其他一些优化算法相比 主要有下述几个特点 遗传算法以决策变量的编码作为运算对象 传统的优化算法往往直接利用决策变量的实际值本身进行优化计算 但遗传算法不是直接以决策变量的值 而是以决策变量的某种形式的编码为运算对象 从而可以很方便地引入和应用遗传操作算子 第三章搜索技术 第二节启发式搜索十二 遗传算法3 特点遗传算法直接以目标函数值作为搜索信息 传统的优化算法往往不只需要目标函数值 还需要目标函数的导数等其它信息 这样对许多目标函数无法求导或很难求导的函数 遗传算法就比较方便 第三章搜索技术 第二节启发式搜索十二 遗传算法3 特点遗传算法同时进行解空间的多点搜索 传统的优化算法往往从解空间的一个初始点开始搜索 这样容易陷入局部极值点 遗传算法进行群体搜索 而且在搜索的过程中引入遗传运算 使群体又可以不断进化 这些是遗传算法所特有的一种隐含并行性 第三章搜索技术 第二节启发式搜索十二 遗传算法3 特点遗传算法使用概率搜索技术 遗传算法属于一种自适应概率搜索技术 其选择 交叉 变异等运算都是以一种概率的方式来进行的 从而增加了其搜索过程的灵活性 实践和理论都已证明了在一定条件下遗传算法总是以概率1收敛于问题的最优解 第三章搜索技术 第二节启发式搜索十二 遗传算法3 应用遗传算法提供了一种求解复杂系统优化问题的通用框架 它不依赖于问题的具体领域 对问题的种类有很强的鲁棒性 所以广泛应用于很多学科 下面列举一些遗传算法的主要应用领域 第三章搜索技术 第二节启发式搜索十二 遗传算法3 应用组合优化 遗传算法是寻求组合优化问题满意解的最佳工具之一 实践证明 遗传算法对于组合优化问题中的NP完全问题非常有效 第三章搜索技术 第二节启发式搜索十二 遗传算法3 应用生产调度问题 生产调度问题在很多情况下所建立起来的数学模型难以精确求解 即使经过一些简化之后可以进行求解也会因简化得太多而使求解结果与实际相差太远 现在遗传算法已经成为解决复杂调度问题的有效工具 第三章搜索技术 第二节启发式搜索十二 遗传算法3 应用自动控制 遗传算法已经在自动控制领域中得到了很好的应用 例如基于遗传算法的模糊控制器的优化设计 基于遗传算法的参数辨识 基于遗传算法的模糊控制规则的学习 利用遗传算法进行人工神经网络的结构优化设计和权值学习等 第三章搜索技术 第二节启发式搜索十二 遗传算法3 应用机器人学 机器人是一类复杂的难以精确建模的人工系统 而遗传算法的起源就来自于对人工自适应系统的研究 所以机器人学自然成为遗传算法的一个重要应用领域 第三章搜索技术 第二节启发式搜索十二 遗传算法3 应用图象处理 图像处理是计算机视觉中的一个重要研究领域 在图像处理过程中 如扫描 特征提取 图像分割等不可避免地存在一些误差 这些误差会影响图像处理的效果 如何使这些误差最小是使计算机视觉达到实用化的重要要求 遗传算法在这些图像处理中的优化计算方面得到了很好的应用 第三章搜索技术 第二节启发式搜索十二 遗传算法3 应用人工生命 人工生命是用计算机 机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统 自组织能力和自学习能力是人工生命的两大重要特征 人工生命与遗传算法有着密切的关系 基于遗传算法的进化模型是研究人工生命现象的重要理论基础 第三章搜索技术 第二节启发式搜索十二 遗传算法3 应用机器学习 基于遗传算法的机器学习 在很多领域中都得到了应用 例如基于遗传算法的机器学习可用来调整人工神经网络的连接权 也可以用于人工神经网络的网络结构优化设计 第三章搜索技术 第二节启发式搜索十二 遗传算法4 基本遗传算法基本遗传算法 SimpleGeneticAlgorithms 简称SGA 是一种统一的最基本的遗传算法 它只使用选择 交叉 变异这三种基本遗传算子 其遗传进化操作过程简单 容易理解 是其他一些遗传算法的雏形和基础 它不仅给各种遗传算法提供了一个基本框架 同时也具有一定的应用价值 第三章搜索技术 第二节启发式搜索十二 遗传算法4 基本遗传算法 基本遗传算法的构成要素 染色体编码方法 基本遗传算法使用固定长度的二进制符号串来表示群体中的个体 其等位基因是由二值符号集 0 1 所组成的 初始群体中各个个体的基因值可用均匀分布的随机数来生成 第三章搜索技术 第二节启发式搜索十二 遗传算法4 基本遗传算法 基本遗传算法的构成要素 个体适应度评价 基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少 为正确计算这个概率 这里要求所有个体的适应度必须为正数或零 遗传算子 基本遗传算法使用下述三种遗传算子 选择运算使用比例选择算子 交叉运算使用单点交叉算子 变异运算使用基本位变异算子或均匀变异算子 第三章搜索技术 第二节启发式搜索十二 遗传算法4 基本遗传算法 基本遗传算法的构成要素 基本遗传算法的运行参数 基本遗传算法有下述4个运行参数需要提前设定 群体大小M 即群体中所含个体数目 一般取为20 100 遗传运算的终止进化代数T 一般取为100 500 交叉概率Pc 一般取为0 4 0 99 变异概率Pm 一般取为0 0001 0 1 第三章搜索技术 第二节启发式搜索十二 遗传算法4 基本遗传算法 基本遗传算法的构成要素 基本遗传算法的形式化定义基本遗传算法可定义为一个8元组 第三章搜索技术 第二节启发式搜索十二 遗传算法4 基本遗传算法 基本遗传算法的构成要素 基本遗传算法的形式化定义式中 C 个体的编码方法 E 个体适应度评价函数 P0 初始群体 M 群体大小 选择算子 交叉算子 T 遗传运算终止条件 第三章搜索技术 第二节启发式搜索十二 遗传算法4 基本遗传算法 基本遗传算法的实现 个体适应度评价在遗传算法中 以个体适应度的大小来确定该个体被遗传到下一代群体中的概率 个体适应度越大 该个体被遗传到下一代的概率也越大 反之 个体的适应度越小 该个体被遗传到下一代的概率也越小 基本遗传算法使用比例选择算子来确定群体中各个个体遗传到下一代群体中的数量 为正确计算不同情况下各个个体的遗传概率 要求所有个体的适应度必须为正数或零 不能是负数 第三章搜索技术 第二节启发式搜索十二 遗传算法4 基本遗传算法 基本遗传算法的实现为满足适应度取非负值的要求 基本遗传算法一般采用下面两种方法之一将目标函数值变换为个体的适应度 方法一 对于目标函数是求极大化 方法为 第三章搜索技术 第二节启发式搜索十二 遗传算法4 基本遗传算法 基本遗传算法的实现式中 为一个适当地相对比较小的数 它可用下面几种方法之一来选取 预先指定的一个较小的数 进化到当前代为止的最小目标函数值 当前代或最近几代群体中的最小目标值 第三章搜索技术 第二节启发式搜索十二 遗传算法4 基本遗传算法 基本遗传算法的实现 比例选择算子比例选择实际上是一种有退还随机选择 也叫做赌盘 RouletteWheel 选择 因为这种选择方式与赌博中的赌盘操作原理非常相似 比例选择算子的具体执行过程是 先计算出群体中所有个体的适应度之和 其次计算出每个个体的相对适应度的大小 此值即为各个个体被遗传到下一代群体中的概率 最后再使用模拟赌盘操作 即0到1之间的随机数 来确定各个个体被选中的次数 第三章搜索技术 第二节启发式搜索十二 遗传算法4 基本遗传算法 基本遗传算法的实现 单点交叉算子单点交叉算子是最常用和最基本的交叉操作算子 单点交叉算子的具体执行过程如下 对群体中的个体进行两两随机配对 对每一对相互配对的个体 随机设置某一基因座之后的位置为交叉点 对每一对相互配对的个体 依设定的交叉概率在其交叉点处相互交换两个个体的部分染色体 从而产生出两个新个体 第三章搜索技术 第二节启发式搜索十二 遗传算法4 基本遗传算法 基本遗传算法的实现 基本位变异算子基本位变异算子的具体执行过程为 对个体的每一个基因座 依变异概率指定其为变异点 对每一个指定的变异点 对其基因值做取反运算或用其他等位基因值来代替 从而产生出一个新的个体 第三章搜索技术 第二节启发式搜索十二 遗传算法4 基本遗传算法 遗传算法的应用步骤遗传算法提供了一种求解复杂系统优化问题的通用框架 对于具体问题 可按下述步骤来构造 确定决策变量及其各种约束条件 即确定出个体的表现型X和问题的解空间 建立优化模型 即描述出目标函数的类型及其数学描述形式或量化方法 第三章搜索技术 第二节启发式搜索十二 遗传算法4 基本遗传算法 遗传算法的应用步骤 确定表示可行解的染色体编码方法 即确定出个体的基因型X及遗传算法的搜索空间 确定解码方法 即确定出由个体基因型X到个体表现型X的对应关系或转换方法 确定个体适应度的量化评价方法 即确定出由目标函数值到个体适应度的转换规则 第三章搜索技术 第二节启发式搜索十二 遗传算法4 基本遗传算法 遗传算法的应用步骤 设计遗传算子 即确定出选择运算 交叉运算 变异运算等遗传算子的具体操作方法 确定遗传算法的有关运行参数 即确定出遗传算法的等参数 第三章搜索技术 第二节启发式搜索十二 遗传算法5 免疫遗传算法基于免疫的改进遗传算法 是免疫原理与传统遗传算法的结合 算法的核心在于免疫算子的构造 而免疫算子又是通过接种疫苗和免疫选择两个步骤完成的 在理论上 免疫算法是概率1收敛的 第三章搜索技术 第二节启发式搜索十三 模拟退火算法 SimulatedAnnealing 1 基本思想 1 是基于MonteCarlo迭代求解策略的一种随机寻优算法 其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性 2 结合爬山法和随机行走注 SA算法最早是由Metropolis等 1953 提出 第三章搜索技术 第二节启发式搜索十三 模拟退火算法 SimulatedAnnealing 1 基本思想 3 模拟退火算法在某一初温下 伴随温度参数的不断下降 结合概率突跳特性在解空间中随机寻找目标函数的全局最优解 即在局部优解能概率性地跳出并最终趋于全局最优解 模拟退火算法是一种通用的优化算法 目前已在工程中得到了广泛应用 第三章搜索技术 第二节启发式搜索十三 模拟退火算法 SimulatedAnnealing 2 物理退火过程和Metropolis准则简单而言 物理退火过程由以下三部分组成 加温过程 其目的是增强粒子的热运动 使其偏离平衡位置 当温度足够高时 固体将溶解为液体 从而消除系统原先可能存在的非均匀态 使随后进行的冷却过程以某一平衡态为起点 溶解过程与系统的熵增过程联系 系统能量也随温度的升高而增大 第三章搜索技术 第二节启发式搜索十三 模拟退火算法 SimulatedAnnealing 2 物理退火过程和Metropolis准则 等温过程 物理学的知识告诉我们 对于与周围环境交换热量而温度不变的封闭系统 系统状态的自发变化总是朝自由能减少的方向进行 当自由能达到最小时 系统达到平衡态 冷却过程 目的是使粒子的热运动减弱并渐趋有序 系统能量逐渐下降 从而得到低能的晶体结构 第三章搜索技术 第二节启发式搜索十三 模拟退火算法 SimulatedAnnealing 2 物理退火过程和Metropolis准则Metropolis等在1953年提出了重要性采样法 即以概率接受新状态 具体而言 在温度t 由当前状态i产生新状态j 两者的能量分别为 若则接受新状态j为当前状态 否则 若概率大于区间内的随机数则仍旧接受新状态j为当前状态 若不成立则保留i为当前状态 其中k为Boltzmann常数 第三章搜索技术 第二节启发式搜索十三 模拟退火算法 SimulatedAnnealing 2 物理退火过程和Metropolis准则这种重要性采样过程在高温下可接受与当前状态能量差较大的新状态 而在低温下基本只接受与当前能量差较小的新状态 而且当温度趋于零时 就不能接受比当前状态能量高的新状态 这种接受准则通常称为Metropolis准则 第三章搜索技术 第二节启发式搜索十三 模拟退火算法 SimulatedAnnealing 2 算法步骤标准模拟退火算法的一般步骤可描述如下 给定初温 随机产生初始状态 令 Repeat Repeat产生新状态 第三章搜索技术 第二节启发式搜索十三 模拟退火算法 SimulatedAnnealing 2 算法步骤Until抽样稳定准则满足 退温 并令 Until算法终止准则满足 输出算法搜索结果 第三章搜索技术 第二节启发式搜索十三 模拟退火算法 SimulatedAnnealing 3 算法关键参数和操作的设定从算法流程上看 模拟退火算法包括三函数两准则 即状态产生函数 状态接受函数 温度更新函数 内循环终止准则和外循环终止准则 这些环节的设计将决定SA算法的优化性能 此外 初温的选择对SA算法性能也有很大影响 第三章搜索技术 第二节启发式搜索十三 模拟退火算法 SimulatedAnnealing 3 算法关键参数和操作的设定 状态产生函数设计状态产生函数 邻域函数 的出发点应该是尽可能保证产生的候选解遍布全部的解空间 通常 状态产生函数由两部分组成 即产生候选解的方式和候选解产生的概率分布 第三章搜索技术 第二节启发式搜索十三 模拟退火算法 SimulatedAnnealing 3 算法关键参数和操作的设定 状态接受函数状态接受函数一般以概率的方式给出 不同接受函数的差别主要在于接受概率的形式不同 设计状态接受概率 应该遵循以下原则 在固定温度下 接受使目标函数值下降的候选解的概率要大于使目标值上升的候选解的概率 第三章搜索技术 第二节启发式搜索十三 模拟退火算法 SimulatedAnnealing 3 算法关键参数和操作的设定 状态接受函数 随温度的下降 接受使目标函数值上升的解的概率要逐渐减小 当温度趋于零时 只能接受目标函数值下降的解 状态接受函数的引入是SA算法实现全局搜索的最关键的因素 SA算法中通常采用min 1 exp C t 作为状态接受函数 第三章搜索技术 第二节启发式搜索十三 模拟退火算法 SimulatedAnnealing 3 算法关键参数和操作的设定 初温初始温度 温度更新函数 内循环终止准则和外循环终止准则通常被称为退火历程 annealingschedule 实验表明 初温越大 获得高质量解的几率越大 但花费的计算时间将增加 因此 初温的确定应折衷考虑优化质量和优化效率 常用方法包括 第三章搜索技术 第二节启发式搜索十三 模拟退火算法 SimulatedAnnealing 3 算法关键参数和操作的设定 初温 均匀抽样一组状态 以各状态目标值的方差为初温 随机产生一组状态 确定两两状态间的最大目标值差 然后依据差值 利用一定的函数确定初温 譬如 其中为初始接受概率 利用经验公式给出 第三章搜索技术 第二节启发式搜索十三 模拟退火算法 SimulatedAnnealing 3 算法关键参数和操作的设定 温度更新函数温度更新函数 即温度的下降方式 用于在外循环中修改温度值 目前 最常用的温度更新函数为指数退温函数 即 其中且其大小可以不断变化 第三章搜索技术 第二节启发式搜索十三 模拟退火算法 SimulatedAnnealing 3 算法关键参数和操作的设定 内循环终止准则内循环终止准则 或称Metropolis抽样稳定准则 用于决定在各温度下产生候选解的数目 在非时齐SA算法理论中 由于在每个温度下只产生一个或少量候选解 所以不存在选择内循环终止准则的问题 第三章搜索技术 第二节启发式搜索十三 模拟退火算法 SimulatedAnnealing 3 算法关键参数和操作的设定 内循环终止准则而在时齐SA算法理论中 收敛条件要求在每个温度下产生候选解的数目趋于无穷大 以使相应的马氏链达到平稳概率分布 显然在实际应用算法时这是无法实现的 常用的抽样准则包括 检验目标函数的均值是否稳定 连续若干步的目标值变化较小 按一定的步数抽样 第三章搜索技术 第二节启发式搜索十三 模拟退火算法 SimulatedAnnealing 3 算法关键参数和操作的设定 外循环终止准则外循环终止准则 即算法终止准则 用于决定算法何时结束 设置温度终值是一种简单的方法 SA算法的收敛性理论中要求温度终值趋于零 这显然不合实际 通常的做法是 第三章搜索技术 第二节启发式搜索十四 禁忌搜索算法 TabuSearch 1 基本思想是对局部邻域搜索的一种扩展 是一种全局逐步寻优算法 其最重要的思想是标记对应已搜索到的局部最优解的一些对象 并在进一步的迭代搜索中尽量避开这些对象 而不是绝对禁止循环 从而保证对不同的有效搜索途径的探索 第三章搜索技术 第二节启发式搜索十四 禁忌搜索算法 TabuSearch 2 算法步骤 1 给定算法参数 随机产生初始解x 置禁忌表为空 2 判断算法终止条件是否满足 若是 则结束算法并输出优化结果 否则 继续以下步骤 3 利用当前解x的邻域函数产生其所有 或若干 邻域解 并从中确定若干个候选解 4 对候选解判断藐视准则是否满足 若成立 则用满足藐视准则的最佳状态y代替x成为新的当前解 即x y 并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象 同时用y替换 bestsofar 状态 然后转步骤2 否则 继续以下步骤 第三章搜索技术 第二节启发式搜索十四 禁忌搜索算法 TabuSearch 2 算法步骤 5 判断候选解对应的各对象的禁忌属性 选择候选解集合中非禁忌对象对应的最佳状态为新的当前解 同时 用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素 6 转步骤 2 注 1 其中 邻域函数 禁忌对象 禁忌表和藐视准则构成了禁忌搜索算法的关键 2 对于邻域函数 沿用局部邻域搜索的思想 用于实现邻域搜索 3 禁忌表和禁忌对象的设置 体现了算法避免迂回搜索的特点 4 藐视准则 则是对优良状态的奖励 它是对禁忌策略的一种放松 第三章搜索技术 第二节启发式搜索十五 蚂蚁算法1 基本原理 1 蚂蚁觅食时 在它走过的路上 留下外激素 这些外激素就象留下路标一样 留给后来 蚁 一个路径的标志 2 后面的蚂蚁 就会沿着有外激素的路径行走 外激素越多引诱蚂蚁的能力就越强 第三章搜索技术 第二节启发式搜索十五 蚂蚁算法2 算法 1 一群蚂蚁随机从出发点出发 遇到食物 衔住食物 沿原路返回 2 蚂蚁在往返途中 在路上留下外激素标志 3 外激素将随时间逐渐蒸发 一般可用负指数函数来描述 即乘上因子e at 4 由蚁穴出发的蚂蚁 其选择路径的概率与各路径上的外激素浓度成正比注 利用同样原理可以描述蚁群进行多食物源的寻食情况 第三章搜索技术 第二节启发式搜索十五 蚂蚁算法3 算法应用 1 用于重建通讯路由 2 用于求解TSP 流动货郎问题 一群蚂蚁由A点同时出发 进行漫游 倾向选较近的城市 把所有城市都游过后 返回 并留下外激素 其量与路程长度成反比 所有蚂蚁都返回后 图上留下外激素的标志进行第二轮的漫游 倾向选激素多的路径 第三章搜索技术 第二节启发式搜索十五 蚂蚁算法3 算法应用 3 蚂蚁清除垃圾蚂蚁能将巢里的垃圾或死蚂蚁 打扫成几大堆给以清除 一群蚂蚁随机出发 遇到垃圾 就将其拉走 方向也是随机的 拉垃圾时 若碰到某一堆垃圾时 就放下 放下垃圾后 再随时机进行打扫工作 第三章搜索技术 第三节博弈树搜索一 博弈树若参加搜索的不只有一个主体 而是对抗性的敌我双方 则搜索的进程不仅取决于一方 而且取决于对方应付的策略 由此产生的搜索树 称为博弈树 注 博弈树很象与或树 第三章搜索技术 第三节博弈树搜索二 博弈树评价原则1 假定对手不会犯错误2 对手总是选择对他最有利的步子走3 自己不采取任何冒险行动4 在最坏的可能中选择最好的注 博弈树评价原则也称为极小极大原则 即在极小中取极大 因此 博弈树也称为极小极大树 第三章搜索技术 第三节博弈树搜索三 极小极大算法1 以甲为博弈树的树根和或节点 并把甲送入待展开节点库TB2 若TB为空 则对博弈树处理如下 1 若某个或节点的所有子与节点的值均为已知 则此或节点的值定义为所有子与结点的值中之最大者 注 赢最大 平次之 输最小 2 若某个与节点的所有子或节点的值均为已知 则此与节点的值定义为所有子或结点的值中之最小者3 反复执行步骤1 2 直至根节点被赋值 算法运行结束 第三章搜索技术 第三节博弈树搜索三 极小极大算法3 若TB不为空 则从TB任取节点n 删去n 并1 若n已直接表现出甲之赢 输或平 则对博弈树的n节点赋以相应的值 赢 输或平 转2 2 否则 若n为或节点 则生成n的所有子与节点 长在博弈树上 也送入TB之中 转2 3 否则 若n为与节点 则生成n的所有子或节点 长在博弈树上 也送入TB之中 转2 算法完 第三章搜索技术 第三节博弈树搜索三 极小极大算法注 1 博弈的结局可能不是简单的输赢 而是有几种可能的得分 但原理一样2 该算法并不保证一定结束 事实上 若想穷尽博弈的所有可能性 则在许多情况下不会结束3 博弈树中的每一分叉 必须有意义 该意义是根据具体领域情况而定4 博弈树体积可能会达到计算机根本无法处理地步 穷举战术行不通5 对博弈树的穷举搜索到一定深度就不再向下走 第三章搜索技术 第三节博弈树搜索三 极小极大算法注 6 不根据最后实际计算出的输赢来评分 而是根据在一定深度处的节点的估计值来评分 即用估计值代替实际的搜索7 计算这种估计值的函数 称为静态估值函数f 它相当于A 算法中的函数h8 对于表示输 赢 平的叶结点 其估计值可定义为 f 赢 f 输 f 平 0 第三章搜索技术 第三节博弈树搜索三 极小极大算法注 9 一般情况下 f可定义为一个多项式 甚至线性函数 但若要取得较好的效果 则f往往定义为非线性的 此时 计算复杂性就增加了 10 除了确定静态估值函数外 还应尽量避免生成无用处的后代 消除冗余 第三章搜索技术 第三节博弈树搜索三 博弈树优化1 优化方法通过剪枝去除冗余现象2