5.局部搜索算法.ppt

5局部搜索算法 2 局部搜索算法 前面的搜索算法都是保留搜索路径的 到达目标的路径就是问题的解 然而许多问题中到达目标的路径是无关紧要的与系统地搜索状态空间 保留各种路径 相对 不关心路径的搜索算法就是局部搜索算法局部搜索从一个单独的当前状态出发 通常只移动到相邻状态典型情况下搜索的路径不保留 3 局部搜索与最优化问题 局部搜索算法的优点 只使用很少的内存 通常是一个常数 经常能在不适合系统化算法的很大或无限的状态空间中找到合理的解最优化问题 根据一个目标函数找到最佳状态 只有目标函数 而不考虑 没有 目标测试 和 路径耗散 局部搜索算法适用于最优化问题 4 状态空间地形图 1 5 状态空间地形图 2 在状态图中 既有 位置 用状态表示 又有 高度 用耗散值或目标函数值表示 如果高度对应于耗散值 则目标是找到全局最小值 即图中最低点如果高度对应于目标函数 则目标是找到全局最大值 即图中最高峰如果存在解 则完备的局部搜索算法能够找到解而最优的局部搜索算法能够找到全局最大或最小值 6 局部搜索算法 本节简要介绍以下4种局部搜索算法 介绍其算法思想爬山法搜索模拟退火搜索局部剪枝搜索遗传算法从学习的角度看遗传算法也是搜索假设空间的一种方法 学习问题归结为搜索问题 生成后继假设的方式 7 爬山法搜索 爬山法 hill climbing 就是向值增加的方向持续移动 登高过程 如果相邻状态中没有比它更高的值 则算法结束于顶峰爬山法搜索算法思想 1 令初始状态S0为当前状态 2 若当前状态已经达标 则算法运行结束 搜索成功 3 若存在一个动作可以作用于当前状态以产生一个新状态 使新状态的估计值优于当前状态的估计值 则放弃当前状态 并令刚产生的新状态为当前状态 转 2 4 取当前状态为相对最优解 停止执行算法 例子 8皇后问题 目标 任何一个皇后都不会攻击到其他的皇后 皇后可以攻击和它在同一行 同一列或同一对角线上的皇后 h取作可以彼此攻击的皇后对的数目 忽略障碍 h 17的一个状态 h取局部极小值时的一个状态 5步 10 爬山法搜索的局限 爬山法是一种局部贪婪搜索 不是最优解算法 或是不完备的 其问题是 局部极大值 比其邻居状态都高的顶峰 但是小于全局最大值 参照状态空间地形图 山脊 一系列的局部极大值高原 评价函数平坦的一块区域 或者山肩 11 爬山法搜索的变形 爬山法的变形随机爬山法 随机选择下一步首选爬山法 随机选择直到有优于当前节点的下一步随机重新开始爬山法 随机生成初始状态 进行一系列爬山法搜索 这时算法是完备的概率接近1 12 模拟退火搜索 将爬山法 停留在局部山峰 和随机行走以某种方式结合 以同时获得完备性和效率模拟退火的思想想象在不平的表面上如何使一个乒乓球掉到最深的裂缝中 如果只让其在表面滚动 则它只会停留在局部极小点 如果晃动平面 可以使乒乓球弹出局部极小点 技巧是晃动足够大使乒乓球弹出局部极小点 但又不能太大把它从全局极小点中赶出 13 模拟退火的解决思路 1 思路 开始使劲晃动 先高温加热 然后慢慢降低摇晃的强度 逐渐降温 退火过程 算法的核心 移动选择选择随机移动 如果评价值改善 则移动被接受 否则以某个小于1的概率接受概率按照移动评价值变坏的梯度 E而呈指数级下降 同时也会随着作为控制的参数 温度 T的降低 数值减小 而降低接受概率 e E T 注意此时 E 0 14 模拟退火的解决思路 2 温度T是时间的函数 按照模拟退火的思想 数值应该逐渐减小 降温 因为接受概率 e E T且 E 0 所以当温度高时 接受概率较大 接近1 而T越来越低时 E T变大 因而接受概率降低可以证明 如果T下降得足够慢 则算法找到全局最优解的概率接近1 15 局部剪枝搜索 基本思想 与只从一个单独的起始状态出发不同 局部剪枝搜索从k个随机生成的状态开始 每步生成全部k个状态的所有后继状态 如果其中之一是目标状态 算法停止 否则从全部后继状态中选择最佳的k个状态继续搜索在局部剪枝搜索过程中 有用的信息在k个并行的搜索线程之间传递 算法会很快放弃没有成果的搜索而把资源放在取得最大进展的搜索上 16 随机剪枝搜索 如果k个状态缺乏多样性 则局部剪枝搜索会受其影响 性能变差算法的变种 随机剪枝搜索帮助缓解这一问题 随机剪枝搜索不是选择最好的k个后代 而是按照一定概率随机地选择k个后继状态 选择给定后继状态的概率是状态值的递增函数类似于自然选择过程 状态对应生物体 其值对应于适应性 后代就是后继状态 17 遗传算法 遗传算法 genericalgorithm GA 是随机剪枝的变种 不是通过修改单一状态而是通过把两个父状态结合以生成后继状态与剪枝搜索一样 遗传算法也是从k个随机状态开始 这k个状态称为种群 每个状态称为个体个体用有限长的字符串 通常为0 1串 表示每个状态用其评价函数 适应度函数 给出评价值 适应值 随后的操作包括 选择 杂交 变异 18 遗传算法的操作 选择 或者称繁殖 按照一定概率随机地选择两对个体进行繁殖 即生成后继状态 杂交 或者称交叉 杂交点是在表示状态的字符串中随机选择的一个位置 以此形成新状态 后代是父串在杂交点上进行杂交 各取一部分 得来的变异 在新生成的串中各个位置都会按照一个独立的小概率随机变异 19 遗传算法简要描述 1 定义问题和目标函数 2 选择候选解作为初始种群 每个解作为个体用二进制串表示 个体相当于染色体 其中的元素相当于基因 3 根据目标函数 对于每个个体计算适应函数值 4 为每个个体指定一个与其适应值成正比的被选择概率 繁殖概率 5 根据概率选择个体 所选个体通过交叉 变异等操作产生新一代种群 6 如果找到了解或者某种限制已到 则过程结束 否则转 3 20 遗传算法的特点 遗传算法也结合了 上山 趋势和随机搜索 并在并行搜索线程之间交换信息遗传算法的主要优势来自于杂交数学上可以证明 如果基因编码的位置在初始时就随机转换的话 杂交就没有优势杂交的优势在于它能够将独立发展的若干个相对固定的字符 能够执行有用的功能 砖块 组合起来 提高了搜索的粒度所谓有用的砖块 就是几个结合起来可以构造问题的解 参见书中的八皇后问题举例 21 遗传算法的模式 遗传算法上述特点可以用模式 schema 来解释 模式是某些位置上的数字尚未确定的一个状态子串能够匹配模式的字符串称为该模式的实例如果一个模式的实例的平均适应值超过均值 则种群内这个模式的实例数量会随时间而增长遗传算法在模式和解的有意义成分相对应时才会工作得最好遗传算法有很多应用 但是在什么情况下它会达到好效果 还有很多研究要做 遗传算法 通过把两个父状态结合来生成后继 8皇后的例子 其中每个状态用一个长度为8的字符串来表示 适应度函数取作不相互攻击的皇后对数目 前一页图中 c 1和2生成 d 1 与或图搜索超图 由节点集和若干连接符组成的图 K 连接符 从一个父节点指向一组K个后继节点的K条连线 n1 n2 a b c d 3 连接 1 连接 1 连接 n0 n1 n3 n6 n7 n2 n5 n4 n8 超图 问题 如何在超图中找出一个解图 求解图的方法 从节点n到目标节点集N的解图 从节点n开始 正确选择一个外向连接符 从该连接符指向的每个后继节点出发 继续选择一个外向连接符 依次类推 直到由此产生的每个后继节点都是N中的一个元素为止 n0 n3 n6 n7 n5 n4 n8 解图1 n1 n5 n0 n8 n7 解图2 上面是两个从节点n0到目标节点集N的解图 N n7 n8 无环解图的递归定义 一个与或图G中 从节点n到节点集N的解图记为G 如果节点n是N中一个元素 则G 由单一元素组成 如果节点n有一个指向节点集 n1 n2 nk 的外向连接符K 使得从每个ni到N有一个解图 i 1 2 k 则G 由节点n 连接符K及 n1 n2 nk 中的每个节点到N的解图组成 否则从n到N不存在解图 解图的耗散值计算 设K 连接符的耗散值为K G 的耗散值为K n N 若n是N的一个元素 则K n N 0 若n有一个到解图中后继节点集 n1 n2 ni 的外向连接符 设该连接符的耗散值为Cn 则K n N Cn K n1 N K n2 N K ni N n0 n3 n6 n7 n5 n8 n1 n4 n5 n0 n8 n7 左图耗散值 K n0 N 1 K n1 N 1 1 K n3 N 1 1 2 K n5 N K n6 N 1 1 2 2 K n7 N K n8 N 2 K n7 N K n8 N 1 1 2 2 0 0 2 0 0 8 右图耗散值 K n0 N 2 K n4 N K n5 N 2 1 K n5N 2 K n7 N K n8 N 2 1 2 K n7 N K n8 N 2 K n7 N K n8 N 2 1 2 0 0 2 0 0 7 能解节点定义 终节点是能解节点 如果非终节点有 或 子节点 当且仅当其子节点至少有一个能解 则该非终节点是能解节点 如果非终节点有 与 子节点 当且仅当其子节点都能解 则该非终节点是能解节点 不能解节点定义 没有后裔的非终节点是不能解节点 该节点是叶节点但不在N中 如果非终节点有 或 子节点 当且仅当所有子节点都不能解 则该非终节点是不能解节点 如果非终节点有 与 子节点 至少有一个子节点不能解 则该非终节点是不能解节点 AO 算法 建立一个搜索图G 仅包含初始节点s s的耗散值为q s h s 如果s是终节点 则标记s为SOLVED Untils已标记SOLVEDdo begin 从s出发沿着有标记的连接符找出一个G的待扩充的局部解图G 任取G 中一个非终节点n作为当前节点 扩充节点n 生成n的全部子节点并将其加入到G中 对于未在G中出现过的子节点nj 计算其耗散值q nj h nj 对于子节点中属于终节点者 标记SOLVED并赋值为0 建立一个仅包含节点n的单一节点集S UntilS为空do CONTINUE begin 从S中移出这样节点m 该m节点的子节点不在S中 计算修改m耗散值q m 对指向节点集 n1i n2i nki 的每个连接符i 分别计算qi m Ci q n1i q n2i q nKi 令 q m minqi m 即 取耗散值最小的连接符的耗散值作为q m 标记该具有最小耗散值的连接符 如果原来对m的某个连接符所做的标记与新标记的连接符不同 则保留新标记 去掉原来标记 如果该连接符的所有后继节点都已标记SOLVED 则此m节点标记SOLVED 如果m已标记SOLVED或者m修正后的耗散值与原来的耗散值不同 则将m的所有父节点加入到S中 这些父节点必须通过有标记的连接符与节点m相连 end end 例题 预先给出了各节点h值的估计值 实际的h值在搜索中计算得出 h n0 0 h n1 2 h n2 h n3 4 h n4 h n5 1 h n6 2 h n7 h n8 0N n7 n8 循环1 n0 n5 n4 n1 外循环 初始状态G S 取当前节点n n0 扩充节点n0 得到n1 n5 n4并加入G中 计算各节点耗散值得 h n1 2 h n5 1 h n4 1 组成单一节点集S n0 内循环 取出节点n0 n0有2个外向连接符 分别计算 h n0 C0 h n1 1 2 3 1 连接符 h n0 C0 h n5 h n4 2 1 1 4 2 连接符 取q n0 min 3 4 3 标记选定的1 连接符 节点n1无标记 节点n0不能标记 内循环结束 标记 循环2 n0 n5 n4 n1 外循环 沿标记取当前节点n n1 扩充节点n1 得到n2 n3并加入G中 计算耗散值得 h n2 4 h n3 4组成单一节点集S n1 内循环 取出节点n1 n1有2个外向连接符 分别计算 h n1 C1 h n2 1 4 5 左1 连接符 h n1 C1 h n3 1 4 5 右1 连接符 取q n1 min 5 5 5 按照自然排序 标记选定的左1 连接符 节点n3无标记 节点n1不能标记 节点n1的h值由原来的2修改为5 将n1的父节点n0加入到单一节点集S中重新计算h n0 h n0 C0 h n1 1 5 6 1 连接符 h n0 C0 h n5 h n4 2 1 1 4 2 连接符 取q n0 min 6 4 4 取消原来n0 n1标记 重新标记2 连接符 节点n4 n5无标记 节点n0不能标记 内循环结束 n2 n3 循环3 n0 n5 n4 n1 外循环 沿标记取当前节点n n5 扩充节点n5 得到n6 n7 n8并加入G中 计算耗散值得 h n6 2 h n7 0 h n8 0组成单一节点集S n5 n7 n8是终节点 标记节点n7 n8内循环 取出节点n5 n5有2个外向连接符 分别计算 h n5 C5 h n6 1 2 3 1 连接符 h n5 C5 h n7 h n8 2 0 0 2 2 连接符 取q n5 min 3 2 2 记选定的2 连接符 节点n7 n8有标记 标记节点n5并将n5的父节点n0加入到S中内循环 取n0 计算h n0 C0 h n1 1 5 6 1 连接符 h n0 C0 h n5 h n4 2 2 1 5 2 连接符 取q n0 min 6 5 5 原来连接不变 节点n5有标记但是n4无标记 节点n0不能标记 内循环结束 n2 n3 n6 n7 n8 循环4 n0 n5 n4 n1 外循环 沿标记取当前节点n n54扩充节点n4 得n5 n8 计算耗散值得 h n5 2