逐步修改候选解
假设一份时间表已满足所有限制,但仍可改善其评分。局部搜索每次修改一个候选解,不必建立从起点到目标的完整路径。方法是否有效取决于容许的操作:交换两个安排可能带来改善,单独修改一个安排却未必能做到。评分、表示方式和邻域都是算法的一部分。
定义 19.1.1
(邻域与局部极大值)
令 是非空有限可行状态集合, 是要最大化的评分, 是从 容许到达的邻居。邻域不必对称。若对每个 都有 ,称 为严格局部极大值点;若只有 ,则称为弱局部极大值点。若 为空,两个条件都自然成立。全局极大值则要与整个 比较。弱局部极大值点未必是全局极大值点;存在相同评分时,全局极大值点也未必是严格局部极大值点。
定义 19.1.2
(爬山法的变体)
严格改善的爬山法反复把 换成任意满足 的邻居 ,找不到便停止。最陡上升法选择评分最高的邻居,若并列则按指定规则处理。首次改善法则按指定顺序检查邻居,选第一个改善者。选法不同可能到达不同终点。此处因 ,每次移动仍可行;实现时必须确保产生邻居的程序确实满足此条件。
定理 19.1.3
(终止性及停机的含义)
在有限 上,不论如何选择改善邻居,每次严格改善的执行都会在最多 次移动后停止。终点是所指定邻域下的弱局部极大值点,但未必是 上的全局极大值点。
证明与界限
证明
(没有状态会被重访)
每一步评分均严格上升,故不可能重访某状态:若重访,其评分应与之前相同,却与中间每步严格上升矛盾。执行最多经过 个不同状态,故最多移动 次。停止时没有评分更高的邻居,正是弱局部极大值的条件。这个证明既不保证 指数庞大时运算快速,也不提供全局最优证明;评估邻居本身亦可能昂贵。
证明透视
有限性和严格性的作用
有限性限制不同状态的数目;严格改善防止重访。缺少任何一项都不能沿用此论证。例如非负整数 只有邻居 ,而 ,则严格改善永不停止。
完整计算吸引域
例题 19.1.4
(五状态链上的最陡上升)
考虑无向链 ––––,各状态评分依次为 。从 或 出发,最陡上升停在 。从 出发,邻居 得 分,高于 的 分,所以路径经 走到 。完整路径为 、、、、。 是评分为 的严格局部极大值点, 才是唯一的全局极大值点,得 分。此确定性算法中,两个吸引域分别为 和 。在其他图上,不同移动规则可能产生不同吸引域;吸引域属于一个算法,而不单由评分函数决定。
反例模式
局部最优是关于邻域的陈述
的相邻状态都没有较高评分,虽然 评分更高。若新增容许边 –,最陡上升就可立即离开 。即使每个候选解的评分不变,改变容许移动也会改变搜索问题。
同分和平移
即使沿同分状态前进后可以改善,严格改善法仍会在平台停止。平移是移到评分相同的邻居,我们只在没有邻居能改善评分时才容许。
命题 19.1.5
(平移上限恢复终止性)
设 有限,一次执行在有改善时作严格改善,否则作平移,连续平移最多 次,每次严格改善后重新计数。则该执行最多有 次严格改善及 次平移,所以最多在 次移动后停止。
证明
(计算严格移动与平移)
严格移动令评分严格上升,平移则评分不变,所以评分沿执行不会下降。严格移动之后不可能重访某状态,否则评分得回落。因此严格移动依序经过评分递增的不同状态,最多 次。第一次严格移动之前、相邻两次严格移动之间,以及最终停止之前,共至多有 段平移,每段长度至多 ,所以平移至多 次,相加即得总数。
例题 19.1.6
(藏有出口的平台与没有出口的平台)
链 –– 的评分是 。由 出发,严格规则会立即停止,因为 与 同分,没有邻居能改善。取 ,容许从 平移到 ,然后 有严格更佳的邻居 ,于是经一次平移和一次严格移动到达 。
再看只有两个同分状态的链 –。没有限制的平移规则可以无限交替 。取 ,则从 移到 后已用完唯一容许的连续平移,便在 停止。达到上限时的终点仍可能有未试过的同分出口;它不代表整个平台已被探索。
另一方法是系统地搜索可到达的同分区域,寻找改善出口,但这需要存储已访问的状态,内存可能远多于只保留当前候选解。若邻域有方向,就要使用有向可达性:可从 到 的同分边未必可反向走。
独立重启及其成本
固定一个单次执行方法,包括停止规则、成功判据及其中可能的随机选择。若返回全局极大值点便称成功;对指定的起点分布及执行内的所有随机选择,令成功概率为 。
定理 19.1.7
(独立重启下的成功概率)
若各次执行独立且同分布, 次内至少成功一次的概率是
当 , 趋大时此概率趋近一,而直到首次成功(包括成功的一次)所需执行次数 的期望为 。若 ,重启永不成功;若 ,有限的 不能保证成功。
证明
(补事件与等比级数)
由独立性, 次均失败的概率为 ,而“全部失败”的补事件就是“至少成功一次”。单单把方法称为“随机重启”并不足以推出公式:若重用有依赖的随机选择,或改变起点分布,公式可能失效。
至于期望,对 有 ,因为前 次都必须失败。把这些尾概率相加,等比级数给出 。这计算的是执行次数而非邻居评估次数;各次执行成本可以不同。
例题 19.1.8
(五状态链上的重启)
在上述五状态例子中,均匀随机选起点,并用确定性最陡上升,执行恰在起点属于 时成功,所以 。三次独立起点至少成功一次的概率为 ,直到首次成功的期望执行次数为 。极端情况也与定理一致:若起点永远是 ,则 ,重启多少次都没有用;若起点永远是 ,则 ,一次执行便足够。
概念视角结构
优化评分与达成目标
局部极大值只证明没有容许的改善步骤,不能证明没有更好的状态。重启概率量化固定分布下的重复执行,不能证明某个特定输出是全局最优。两者均取决于移动和成功的精确定义。
常见错误
常见错误
(以为先前的失败会提高下一次的成功概率)
在五状态例子中,前两次独立失败后,第三次成功概率仍是 ;过往失败不会提高这概率。至少成功一次的概率随 上升,只是因为给了更多独立机会,并不是前面的执行“欠”一次成功。
常见错误
(靠检查终点是否全局最优来度量 )
真实问题的全局最优值可能未知,因此一般无法靠检查终点是否全局最优来度量 。已知目标分数可以定义另一个可观察的成功事件,但其概率须重新定义。
练习
练习 19.1.9
(链 ––– 的评分依次为 。列出由各状态出发的严格最陡上升终点,并分辨弱与严格局部极大值点。)
核心
解答(3)
- 1
追踪各状态的严格最陡上升
由 出发,唯一邻居 得 ,所以移到 。在 ,邻居评分为 和 ,都不严格大于 ,所以停止。由 出发,邻居 得 ,所以移到 并停止。终点为 、、、。
- 2
分类局部极大值点
关键一步
的邻居评分为 和 ,所以 与 均成立:它是弱局部极大值点,但因 与它同分,不是严格的。 有邻居 得 ,所以不是局部极大值点。 胜过唯一的邻居,是严格局部极大值点。
依据: 弱局部极大值要求对每个邻居都有 ,严格者要求 。
- 3
写出结论
弱局部极大值点为 和 ;严格局部极大值点只有 。尽管平台 有出口,从 无法只靠严格改善到达更好的 。
练习 19.1.10
(同一链上,规定没有改善邻居时可平移一次,然后恢复严格上升;最多容许连续一次平移。由 出发写出一条可行路径,并解释 的同分处理为何重要。)
核心
解答(2)
- 1
追踪这次执行
是严格移动。在 没有邻居能改善,所以适用平移规则,并取唯一的同分邻居 。由 出发,邻居 能改善,所以 是严格移动。路径为 。
- 2
解释同分处理
此链中 只有一个同分邻居 ,但规则仍须说明是选它还是停止。较大的平台中,选择哪个同分邻居可以影响结果。平移上限避免无限连续平移,却不保证找出所有出口。
依据: 规则必须说明是否作平移,以及选哪个同分邻居。
练习 19.1.11
(单次执行成功概率是 。求四次独立执行至少一次成功的概率,以及截至首次成功(包括成功的那一次)所需执行次数的期望。若所有起点都重用同一次随机抽样,还能应用相同公式吗?)
核心
解答(2)
- 1
应用重启公式
至少成功一次的概率为 。首次成功的平均等待次数为 。
- 2
检视重用同一次随机抽样
若重用同一随机起点,结果可完全相互依赖。例如确定性方法恰好在同一组四分之一的起点成功,则四次同时成功或同时失败,至少一次成功的概率仍为 ,公式并不适用。
依据: 公式需要各次执行相互独立。
练习 19.1.12
(有限有向图有评分 、、,及边 、、。求由 开始的严格上升终点,并说明为何不违反终止定理。)
基础
解答(2)
- 1
追踪由 开始的执行
由 出发,唯一的出邻居是 ,且 ,所以移到 。 唯一的出邻居 评分为 ,没有改善移动,于是在 停止。
- 2
与定理比较
评分更高的 不是 的出邻居,因此无法到达。有限性及严格上升仍保证终止,而且 是此有向邻域下的弱局部极大值点。定理从未保证全局最优或边的对称性。