第Ⅱ部分 问题求解 第4章 超越经典搜索 中国科大 计算机学院

本章内容 4.1 局部搜索算法和最优化问题 4.2 连续空间中的局部搜索 4.3 使用不确定动作的搜索 4.4 使用部分可观察信息的搜索 4.5 联机搜索Agent和未知环境

4.1 局部搜索算法和最优化问题 概述 爬山法 模拟退火搜索 局部束搜索 遗传算法 进化算法简介

局部搜索算法 前面讲过的搜索算法都是保留搜索路径的，到达目标的路径就是问题的解。 然而，许多问题中到达目标的路径是无关紧要的。 比如，八皇后问题。 与系统地搜索状态空间(保留各种路径)相对应，不关心路径的搜索算法就是局部搜索算法。 局部搜索从一个单独的当前状态出发，通常只移动到相邻状态。 典型情况下，搜索的路径不保留。

局部搜索算法 2个关键的优点： 它们只用很少的内存——通常容量是个常数。 它们经常能在不适合系统化算法的很大或无限的（连续的）状态空间中找到合理的解。 局部搜索算法对解决纯粹的最优化问题是很有用的，其目标是根据一个目标函数找到最佳状态。

局部搜索算法的应用 旅行商问题 装箱问题 背包问题 作业调度 网络优化 ……

状态空间地形图 Shoulder：山肩 “Flat” local maximum：“平坦”局部最大值

状态空间地形图 在状态图中，既有“位置”(用状态表示)又有“高度”(用耗散值或目标函数值表示)。 如果高度对应于目标函数，则目标是找到全局最大值，即图中最高峰。 如果高度对应于耗散值，则目标是找到全局最小值，即图中最低点。 如果存在解，则完备的局部搜索算法能够找到解；最优的局部搜索算法能够找到全局最大/最小值。

4.1 局部搜索算法和最优化问题 概述 爬山法 模拟退火搜索 局部束搜索 遗传算法 进化算法简介

例、8皇后问题 局部搜索算法通常使用完全状态形式化，即每个状态都在棋盘上放8个皇后，每列一个。 目标：任何一个皇后都不会攻击到其他的皇后（皇后可以攻击和它在同一行、同一列或同一对角线上的皇后）。 后继函数：返回的是移动一个皇后到和它同一列的另一个方格中的所有可能的状态。因此，每个状态有56个后继。 启发式耗散函数h：是可以彼此攻击的皇后对的数目，不管中间是否有障碍。 全局最小值为0，即没有彼此攻击的皇后对。

例、8皇后问题 h＝17的一个状态， 最好的后继的h=12。 h取局部极小值时的一个状态

爬山法搜索 爬山法(hill-climbing)：是一个向值增加的方向持续移动的循环过程，即登高过程。 ；最陡上升方式的爬山搜索算法 ；如果相邻状态中没有比它更高的值，则算法结束于“峰顶” function Hill-Climbing( problem ) inputs: problem, a problem returns a state that is a local maximum current  Make-Node( Initial-Sate[ problem ]) loop do neighbor  a highest-valued successor of current if Value[ neighbor ] <＝ Value[ current ] then return State[ current ] current  neighbor

爬山法搜索的局限 爬山法是一种贪婪局部搜索，不是最优解算法(或是不完备的) 。 面临的问题： 局部极大值：比其邻居状态都高的顶峰，但是小于全局最大值。 高原或山肩：评价函数平坦的一块区域。 山脊：一系列的局部极大值。

爬山法搜索的局限 对于最陡上升的爬山法算法，从一个随机生成的八皇后问题的状态开始： 在86％的情况下会被卡住； 只有14％的问题实例能求到最优解。 但这个算法速度很快，成功得到最优解的平均步数是4步，被卡住的平均步数是3步。 对于包含88≈1千7百万个状态的状态空间是不错的结果。 思考：10万个皇后？100万个皇后？1000万个皇后？

爬山法搜索的局限 如果遇到山肩，允许侧向移动是个好主意。 如果总是允许侧向移动，易形成死循环。 限制侧向移动次数。 例、八皇后问题中，允许最多连续侧向移动100次，将使问题实例的解决率从14％上升到94％。 代价是每个成功搜索实例的平均步长大约为21步，每个失败搜索的平均步长大约为64步。

爬山法搜索的变形 随机爬山法：在上山移动中随机选择地下一步，选择的概率随着上山移动的陡峭程度而变化。 首选爬山法：随机生成后继结点，直到生成一个优于当前节点的后继结点。 随机重新开始爬山法：随机生成初始状态，进行一系列爬山法搜索。这时算法是完备的概率接近1。 如果爬山法每次成功的概率为p，则需要重新开始搜索的期望次数是1/p。 对于300万个皇后问题，该方法用不了1分钟就可以找到解。

爬山法搜索的特点 爬山法搜索成功与否在很大程度上取决于状态空间地形图的形状。 如果图中几乎没有局部最大值和高原，随机重新开始的爬山法将会很快找到好的解。 但是，很多实际问题有很多局部最优解，。

4.1 局部搜索算法和最优化问题 概述 爬山法 模拟退火搜索 局部束搜索 遗传算法 进化算法简介

模拟退火搜索 模拟退火算法来源于固体退火原理。 将固体加温至充分高，再让其徐徐冷却；加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态；最后在常温时达到基态，内能减为最小。 模拟退火算法：允许下山的随机爬山法。 在退火初期，下山移动容易被采纳。 随着时间的推移，下山的次数越来越少。 例，在不平的表面上如何使一个乒乓球掉到最深的裂缝中?

模拟退火搜索 function SIMULATED-ANNEALING(problem, schedule) returns a solution state inputs: problem, a problem schedule, a mapping from time to “temperature” current  MAKE-NODE(problem, INITIAL-STATE) for t=1 to ∞ do T  schedule( t ) if T=0 then return current next  a randomly selected successor of current ∆E  next.VALUE — current.VALUE if ∆E>0 then current  next else current  next only with probability e∆E / T

模拟退火搜索 模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率1收敛于全局最优解的全局优化算法。 模拟退火算法已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。

4.1 局部搜索算法和最优化问题 概述 爬山法 模拟退火搜索 局部束搜索 遗传算法 进化算法简介

局部束搜索 局部束搜索：不是保存一个状态，而是保存k个状态。 首先，随机生成k个状态。 然后，生成k个状态的全部后继。 在随机重新开始搜索中，每个搜索过程是独立的。 在局部束搜索中，有用的信息在k个并行搜索线程中传递。

局部束搜索 局部束搜索的问题： 容易缺乏多样性，即个体很快聚集到某个区域。 缓解办法：随机束搜索。 不是“从后继状态列表中选择k个最好的后继”，而是按概率选择。越好的个体，选择概率越高。

4.1 局部搜索算法和最优化问题 概述 爬山法 模拟退火搜索 局部束搜索 遗传算法 进化算法简介

遗传算法 遗传算法(Generic Algorithm：GA)是随机剪枝的变种，它不是通过修改单一状态而是通过把两个父状态结合以生成后继状态。 遗传算法是从k个随机状态开始。这k个状态称为种群，每个状态称为个体。 个体编码用有限长的字符串（比如0/1串）表示。 每个状态用其评价函数（适应度函数）给出评价值（适应值）。 遗传操作包括：选择，杂交，变异。

遗传算法的基本步骤 (1) 设计个体编码方案，定义问题的目标函数。 (2) 选择候选解作为初始种群，每个解作为个体用二进制串(或字符串)表示(个体相当于染色体，其中的元素相当于基因)。 初始种群通常随机生成。 (3) 根据目标函数，对于每个个体计算适应度函数值。 (4) 为每个个体指定一个与其适应值成正比的被选择概率。 (5) 根据概率选择个体，所选个体通过交叉、变异等操作产生新一代种群。 (6) 如果找到了解或者某种限制已到，则过程结束；否则转(3)。 结束条件：找到解；代数达到预定数目；等等。

遗传算法的操作 选择 按照一定概率随机地选择一对个体进行繁殖(即生成后继状态)。 基本原则：较好的个体有较高的被选择概率。 交叉 杂交点是在表示状态的字符串中随机选择的一个位置； 新个体是父串在杂交点上进行杂交(各取一部分)得来的。 变异 在新生成的串中各个位置都会按照一个独立的小概率随机变异。

用遗传算法求解八皇后问题 例、八皇后问题，其中每个状态用一个长度为8的字符串来表示；适应度函数取作不相互攻击的皇后对数目。 个体编码 对应的候选解

用遗传算法求解八皇后问题 交叉操作生成2个子代个体。 思考：另一子代个体是什么？

用遗传算法求解八皇后问题 遗传算法的步骤及其示意图 适应度函数为：f(i)/sum( f(i) ).

遗传算法的特点 遗传算法结合了“上山”趋势和随机搜索，并通过并行搜索在个体之间交换信息。 遗传算法的主要优势来自于杂交？ 杂交的优势：能够将独立发展的若干个相对固定的字符（能够执行有用的功能—“积木块”）组合起来，提高了搜索的粒度。 所谓有用的积木块，就是几个结合起来可以构造问题的解。 数学上可以证明，如果基因编码的位置在初始时就随机转换的话，杂交就没有优势。

遗传算法的模式 遗传算法的特点可以用模式（schema）来解释。 模式是某些位置上的数字尚未确定的一个状态子串，例如246*****。 能够匹配模式的字符串称为该模式的实例。 如果一个模式的实例的平均适应值超过均值，则种群内这个模式的实例数量会随时间而增长。 遗传算法在模式和解的有意义成分相对应时才会工作得最好。 遗传算法有很多应用，但目前还不清楚在什么情况下使用遗传算法能够达到好的效果，还有很多研究要做。

4.1 局部搜索算法和最优化问题 概述 爬山法 模拟退火搜索 局部束搜索 遗传算法 进化算法简介

进化算法简介 遗传算法是进化算法的一种。 进化算法（EAs：Evolutionary Algorithms）： 借鉴生物进化的规律，通过“繁殖-竞争-再繁殖-再竞争”的方式，实现优胜劣汰，一步一步逼近问题的最优解。 编码方案：或用各种字符（基因）组成的字符串（染色体）表达所研究的问题；或实数编码，等等。 算子：仿效生物的遗传方式，主要采用选择（Selection），重组（Recombination），变异（Mutation）这3种操作，衍生下一代的个体。

进化算法的基本框架 表示父代群体是否参与选择过程。

进化算法的主要优势 在一般情况下，进化算法能否收敛到全局最优解与初始群体无关，而传统优化方法则依赖于初始解； 进化算法具有全局搜索能力，而很多传统优化方法往往会陷入局部最优； 进化算法的适用范围广，能有效地解决不同类型的问题，而传统优化方法在设计时往往就只能解决某一类型的问题。

进化算法的不足 进化算法中的参数，如群体规模、进化代数、重组概率、变异概率等，往往需要根据经验设定，且在一定程度上还与问题相关。 进化算法的收敛问题，尽管在理论研究上已取得一定的成果，但进化算法求解实际问题时的收敛性判定还缺乏理论指导。

进化算法分类—传统分类 进化规划（EP：Evolutionary Programming） L.J. Fogel, A.J. Owens, M.J. Walsh (美国，1966) 完善工作：D.B. Fogel (1991)，等等。 进化策略（ESs：Evolution Strategies） I. Rechenberg, H.-P. Schwefel (德国，1965) 遗传算法（GAs：Genetic Algorithms） J. Holland (美国，1975) 完善工作：K. De Jong (1975), J. Grefenstette (1986), D. Goldberg (1989) ，等等。

进化算法分类—新颖算法 差分进化（DE：Differential Evolution） R. Stone, K. Price （德国、美国，1995） 用于连续空间上的函数优化，等等。 粒子群优化（PSO：Particle Swarm Optimization） J. Kennedy, R.C. Eberhart （美国，1995） 源于对一个简化社会模型的模拟，主要用于连续空间上的问题优化，等等。 蚁群算法（ACO：Ant Colony Optimization） M. Dorigo （意大利，1992） 用来在图中寻找优化路径的几率型技术，等等。

进化计算的主要期刊与会议 主要期刊： 主要会议： IEEE Trans. on Evolutionary Computation Genetic Programming and Evolvable Machines …… 主要会议： PPSN：Parallel Problem Solving from Nature CEC：IEEE Congress on Evolutionary Computation GECCO：Genetic and Evolutionary Computation Conference

本章内容 4.1 局部搜索算法和最优化问题 4.2 连续空间中的局部搜索 4.3 使用不确定动作的搜索 4.4 使用部分可观察信息的搜索 4.5 联机搜索Agent和未知环境

连续空间中的局部搜索 在连续空间上寻找最优解：状态空间是连续的。 例、建3个机场，每个城市离其最近机场的距离平方和最小。 六维状态空间：(x1, y1)，(x2, y2)，(x3, y3)

连续空间中的局部搜索 最简单的方法： 连续空间离散化，x和y方向的移动间隔固定为。 局部搜索算法 梯度方法： 𝛁𝒇 𝒙 =𝟎 𝒙←𝒙+𝜶𝛁𝒇(𝒙)，𝜶是个很小的常数

连续空间中的局部搜索 约束最优化 在满足约束条件的前提下，求最优解。 线性规划 目标函数是线性的。 约束是线性不等式，且能够组成一个凸多边形区域。

课堂练习 （1）设计一个用于解决八数码问题的爬山法搜索算法，给出算法伪代码。（2）对于下图所示的八数码问题的初始状态，请分析您的算法是否能够到达目标状态？ 模拟退火搜索SIMULATED-ANNEALING函数中的参数schedule，是从时间到“温度”的一个映射。请为schedule给出一个合理的例子。