• 如果高度对应于目标函数，则目标是找到全 局最大值，即图中最高峰
• 如果存在解，则完备的局部搜索算法能够找 到解
• 而最优的局部搜索算法能够找到全局最大或 最小值
8
第2章 搜索技术
局部搜索算法
• 本节简要介绍以下4种局部搜索算法 / 介绍其算法思想
• 爬山法搜索
• 模拟退火搜索
• 局部剪枝搜索
• 遗传算法
• 从搜索的角度看遗传算法也是搜索假设空间 的一种方法(学习问题归结为搜索问题)—生 成后继假设的方式
9
第2章 搜索技术
2.4.2 爬山法搜索
• 爬山法(hill-climbing)—就是向值增加的方向持 续移动—登高过程 / 如果相邻状态中没有比它 更高的值，则算法结束于顶峰
• 爬山法搜索算法思想：
2.5.5 关于失败变量的启发式
第2章 搜索技术
2.5.1 约束满足问题的定义
• 约束满足问题(Constraint Satisfying Problem, CSP)由一个变量集合{X1~Xn}和一个约束集 合{C1~Cm}定义
• 每个变量都有一个非空可能值域Di • 每个约束指定了包含若干变量的一个子集内各
• CSP问题具有一个性质：可交换性—变量 赋值的顺序对结果没有影响 / 所有CSP搜 索算法生成后继节点时，在搜索树每个 节点上只考虑单个变量的可能赋值
• CSP问题的求解使用深度优先的回溯搜索 • 算法思想：
• 每次给一个变量赋值，当没有合法赋值(不 满足约束时)就要推翻前一个变量的赋值， 重新给其赋值，这就是回溯
(1)令初始状态S0为当前状态
(2)若当前状态已经达标，则算法运行结束，搜索成 功
(3)若存在一个动作可以作用于当前状态以产生一个
新状态，使新状态的估计值优于当前状态的估计
值，则放弃当前状态，并令刚产生的新状态为当
前状态，转(2)
(4)取当前状态为相对最优解，停止执行算法
10
第2章 搜索技术
爬山法搜索的局限
13
第5章 搜索技术
模拟退火的解决思路(1)
• 思路—开始使劲晃动(先高温加热)然后 慢慢降低摇晃的强度(逐渐降温)[退火过 程]
• 算法的核心—移动选择
• 选择随机移动，如果评价值改善，则移动被 接受，否则以某个小于1的概率接受
• 概率按照移动评价值变坏的梯度ΔE而呈指
数级下降 / 同时也会随着作为控制的参 数—“温度”T的降低(数值减小)而降低
• 所谓有用的砖块，就是几个结合起来可以构 造问题的解—参见书中的八皇后问题举例
21
第2章 搜索技术
遗传算法的模式
• 遗传算法上述特点可以用模式(schema)来 解释—模式是某些位置上的数字尚未确 定的一个状态子串
• 能够匹配模式的字符串称为该模式的实例 • 如果一个模式的实例的平均适应值超过均值，
5
第2章 搜索技术
2.4.1 局部搜索与最优化问题
• 局部搜索算法的优点：
• 只使用很少的内存(通常是一个常数) • 经常能在不适合系统化算法的很大或无限的
状态空间中找到合理的解
• 最优化问题—根据一个目标函数找到最佳 状态 / 只有目标函数，而不考虑(没有) “目标测试”和“路径耗散”
• 局部搜索算法适用于最优化问题
• 接受概率=eΔE/T(注意此时ΔE <0)
14
第5章 搜索技术
模拟退火的解决思路(2)
• 温度T是时间的函数，按照模拟退火的思 想，数值应该逐渐减小(降温)
• 因为接受概率=eΔE/T且ΔE <0，所以当温
度高时，接受概率较大(接近1) / 而T越
来越低时，ΔE/T变大，因而接受概率降
低 • 可以证明，如果T下降得足够慢，则算法
6
第2章 搜索技术
状态空间地形图(1)
目标函 数
全局最大 值
山肩
局部最大 值
“平坦”局部最大 值
当前状 态
状态空 间
7
第2章 搜索技术
状态空间地形图(2)
• 在状态图中，既有“位置”(用状态表示) 又有“高度”(用耗散值或目标函数值表 示)
• 如果高度对应于耗散值，则目标是找到全局 最小值，即图中最低点
变量的赋值范围
• CSP的一个状态—对一些或全部变量的赋值 {Xi=vi, Xj=vj, …}
24
第2章 搜索技术
CSP问题的解
• 一个不违反任何约束的对变量的赋值称 为相容赋值或合法赋值
• 对每个变量都进行赋值称为完全赋值 • 一个(一组)既是相容赋值又是完全赋值的
对变量的赋值就是CSP问题的解
• 变异—在新生成的串中各个位置都会按 照一个独立的小概率随机变异
19
第2章 搜索技术
遗传算法简要描述
(1)定义问题和目标函数 (2)选择候选解作为初始种群，每个解作为个体用
二进制串表示(个体相当于染色体，其中的元素 相当于基因) (3)根据目标函数，对于每个个体计算适应函数值 (4)为每个个体指定一个与其适应值成正比的被选 择概率(繁殖概率) (5)根据概率选择个体，所选个体通过交叉/变异 等操作产生新一代种群
• 若CSP问题的任何一个变量的最大值域为 d，那么可能的完全赋值数量为O(dn)
• 有限值域CSP问题包括布尔CSP问题—其 中有一些NP完全问题，如3SAT问题(命 题逻辑语句的可满足性) / 最坏情况下不 会指望低于指数级时间复杂性解决该问 题
32
第2章 搜索技术
2.5.2 CSP的回溯搜索
33
第2章 搜索技术
简单回溯法生成的搜索树
• 澳大利亚地图染色问题的搜索树
WA=red
WA=green
WA=red NT=green
人工智能原理2章搜索技术下
第2章 搜索技术
本章内容
2.1 搜索与问题求解 2.2 无信息搜索策略 2.3 启发式搜索策略 2.4 局部搜索算法 2.5 约束满足问题 2.6 博弈搜索 参考书目
附录 A*算法可采纳性的证明
第2章 搜索技术
局部搜索算法的应用
• 集成电路设计 • 工厂场地布局 • 车间作业调度 • 自动程序设计 • 电信网络优化 • 车辆寻径 • 文件夹管理
塔斯马尼亚
27
第5章 搜索技术
例1：澳大利亚地图染色问题(2)
• 对应于澳大利亚地图的约束图,相互关联的节点 用边连接
•西澳大利亚 – WA
•北领地 – NT
NT Q
•南澳大利亚 – SA
WA
•昆士兰 – Q •新南威尔士 – NSW
SA
NSW
•维多利亚 – V
V
•塔斯马尼亚 – T
•一组满足约束的完全赋值
• 爬山法是一种局部贪婪搜索，不是最优解 算法(或是不完备的) / 其问题是：
• 局部极大值—比其邻居状态都高的顶峰，但是 小于全局最大值(参照状态空间地形图)
• 山脊—一系列的局部极大值 • 高原—评价函数平坦的一块区域(或者山肩)
11
第2章 搜索技术
爬山法搜索的变形
• 爬山法的变形
• 随机爬山法—随机选择下一步 • 首选爬山法—随机选择直到有优于当前节点的
找到全局最优解的概率接近1
15
第2章 搜索技术
2.4.4 局部剪枝搜索
• 基本思想—与只从一个单独的起始状态 出发不同，局部剪枝搜索从k个随机生成 的状态开始，每步生成全部k个状态的所 有后继状态 / 如果其中之一是目标状态， 算法停止；否则从全部后继状态中选择 最佳的k个状态继续搜索
• 在局部剪枝搜索过程中，有用的信息在k 个并行的搜索线程之间传递—算法会很 快放弃没有成果的搜索而把资源放在取 得最大进展的搜索上
• CSP问题常常可以可视化，表示为约束图， 更直观地显示问题，帮助思考问题的答 案
25
第2章 搜索技术
从搜索角度看待CSP问题
• CSP看作搜索问题的形式化
• 初始状态—空赋值集合，所有变量都是未赋 值的
• 后继函数—给未赋值的变量一个赋值，要求 该赋值与先前的变量赋值不冲突
• 目标测试—测试当前的赋值(组)是否是完全 赋值
(线性约束/非线性约束)
• 变量—连续值域
• 如哈勃望远镜实验日程安排 / 线性规划问题
• 约束的类型
• 一元约束—只限制一个变量的取值 • 二元约束与2个变量相关 • 高阶约束—涉及3个或更多变量
31
第2章 搜索技术
CSP问题求解的复杂度
• 搜索相容的完全赋值，最朴素的想法是 依次取变量的赋值组合并检查其是否满 足约束条件指数级计算量
下一步 • 随机重新开始爬山法—随机生成初始状态，进
行一系列爬山法搜索—这时算法是完备的概率 接近1
12
第2章 搜索技术
2.4.3 模拟退火搜索
• 将爬山法(停留在局部山峰)和随机行走 以某种方式结合，以同时获得完备性和 效率
• 模拟退火的思想
• 想象在不平的表面上如何使一个乒乓球掉到 最深的裂缝中—如果只让其在表面滚动，则 它只会停留在局部极小点 / 如果晃动平面， 可以使乒乓球弹出局部极小点 / 技巧是晃 动足够大使乒乓球弹出局部极小点，但又不 能太大把它从全局极小点中赶出
则种群内这个模式的实例数量会随时间而增 长
• 遗传算法在模式和解的有意义成分相对应时 才会工作得最好
• 遗传算法有很多应用，但是在什么情况 下它会达到好效果，还有很多研究要做
22
第2章 搜索技术
2.5 约束满足问题
2.5.1 约束满足问题的定义 2.5.2 CSP的回溯搜索
2.5.3 变量赋值次序的启发式 2.5.4 变量约束的启发式
价值(适应值) • 随后的操作包括—选择/杂交/变异