Probabilistic Focal Search：通过下界推进加速有界次优搜索

# 概率焦点搜索：通过下界推进加速有界次优搜索
来源：https://arxiv.org/html/2609.10584
作者：Trung Le Huu, Hà Minh Hoàng, Trung Thanh Nguyen, Phương Khanh Nguyen, Huynh Thi Thanh Binh
###### 摘要
有界次优搜索旨在寻找一个成本不超过最优解 w 倍的解，同时减少搜索工作量。焦点搜索 (Focal Search, FS) 在 FOCAL 集内（即阈值 wf_min 下符合条件的前沿节点）使用启发式引导，但其确定性策略可能导致许多扩张操作后 f_min 保持不变。我们引入了概率焦点搜索 (Probabilistic Focal Search, PFS)，它以概率 p 遵循 FS 的引导选择，并以概率 1-p 扩张一个最小 f 的 OPEN 节点。后一分支鼓励下界推进，扩大 FOCAL 集，并接纳可能导向可行解的节点。通过平衡引导和下界推进，当进展受限于延迟的 FOCAL 准入时，此机制可以减少达到有界解所需的时间。作为二次迁移实验，我们将相同的调度器应用于动态势能搜索 (Dynamic Potential Search)，得到了概率动态势能搜索 (Probabilistic Dynamic Potential Search, PDPS)。我们使用多个 w 和 p 值，在 N-拼图、煎饼排序和旅行商问题 (TSP) 上对 PFS 和 FS 进行了基准测试，并评估了其随时算法扩展在广义覆盖 TSP (GCTSP) 上的表现。在这些基准测试中，当长期的 f_min 平台期延迟了有用的 FOCAL 准入时，收益最大；在这种情况下，概率因子可以将节点扩张减少约 90% 或更多（例如，在 N-拼图和 TSP 上）。对于随时算法系列，随时概率焦点搜索 (Anytime Probabilistic Focal Search, APFS) 在评估 GCTSP 上的随时方法时优于所有测试算法。我们还观察到，当确定性搜索已经高效推进时（例如煎饼排序），收益较小，这表明当 FOCAL 准入是搜索瓶颈时，概率因子最有用。PDPS 迁移实验表明，该机制也能迁移到势能引导策略中，尽管其通用成功效果仍然取决于具体领域和边界。

1 国家经济大学 SLSCM 实验室
2 华威大学
3 国家经济大学 DataOpt 实验室
4 国家经济大学 CADA 实验室
5 河内科技大学

## 引言
有界次优启发式搜索用一个保证换取最优性：给定因子 w≥1，它寻求一个成本至多为 wC* 的解，同时使用的搜索量远少于 A*。焦点搜索 (FS) 通过一个可接受的主要启发式和一个次要优先级实现了这个想法。它维护 FOCAL = {n ∈ OPEN: f(n) ≤ wf_min}，并重复扩张在该次要优先级下最佳的合格节点 (Pearl and Kim 1982)。动态势能搜索 (DPS) 则根据随相同下界 f_min 变化的势能对 OPEN 进行排序 (Gilon et al. 2016)。这种认证与引导之间的分离很强大，但它创造了一个反馈循环。引导的扩张可能停留在一个最小 f 的平台期上；只要 f_min 不变，合格阈值 wf_min 也就不会变。一个刚好在阈值之外的良好节点，在下界前沿推进之前，无法从次要策略中受益。确定性策略没有明确的控制来使之发生。
我们研究对 FS 的一个最小干预：以概率 p 保留其引导的 FOCAL 选择；以概率 1-p 扩张一个最小 f 的 OPEN 节点。这产生了概率焦点搜索 (PFS)。该干预并不放松解的包络线。相反，它将一小部分选择预算用于定义该包络线的前沿。这个问题既是经验性的也是理论性的：强制进行 OPEN 头部工作可能会缩短有害的平台期，但当 FS 已经有效推进时，这就是开销。
作为二次迁移实验，我们将相同的调度器应用于 DPS，得到了概率动态势能搜索 (PDPS)。这种比较测试了该机制是否能迁移到不同的引导策略上。
我们在 N-拼图、煎饼排序和旅行商问题 (TSP) 上评估了这个想法，并在度量型广义覆盖 TSP (GCTSP) 上评估了其随时算法扩展。结果表明，当概率下界推进能够接纳引导策略可以利用的有效节点时，它可以提高成功率并显著减少搜索工作量；APFS 在 GCTSP 上也领先于其他评估的随时方法。我们进一步分析了该干预提供很少或没有收益的情况，解释了已经足够大的 FOCAL 或对新接纳节点的引导无效如何限制了该机制。PDPS 和 APDPS 作为二次迁移实验，验证了其对引导策略的这种依赖性。
本文贡献包括：
- • PFS，一个可调节的伯努利调度器，它交替进行引导的 FOCAL 选择和最小 f 的 OPEN 选择，以及一个有界次优性证明；
- • 一个机制分析，识别调度器何时有帮助以及何时增加开销：当最小 f 选择能够推进下界并接纳引导策略可以利用的节点时是有帮助的，但当 FOCAL 已经足够大或新接纳的节点不能改善引导选择时则不然；
- • 一个跨领域评估，既支持调度器的有效性，也支持所提出的机制。
在 N-拼图上，PFS 将成功率从 44.3% 提高到 83.6%，同时将带惩罚的平均扩张节点数减少了 60.7%，将封顶的平均运行时间减少了 69.8%。在两个 TSP 数据集上，它达到了至少 96.4% 的成功率，并将这些指标分别降低了至少 87.2% 和 89.0%。在 FOCAL 已经足够大的煎饼排序问题上，其收益较小，连同 DPS 系列中观察到的收益和残留的回归现象，与已识别的边界条件是一致的。在随时 GCTSP 上，APFS 解决了 189/234 个中等实例，而 AFS 只解决了 82/234 个。

## 背景与相关工作
每个搜索节点 n 代表一个连同其当前路径信息的问题状态。令 g(n) 为其已知的最佳路径成本，h(n) 为剩余成本的可接受估计，令 f(n) = g(n) + h(n)。A* 在标准图搜索假设下扩张一个最小 f 节点并返回最优解 (Hart et al. 1968)。加权 A* (WA*) 则按 q_w(n) = g(n) + wh(n) 排序，以更快获得 w 次优解 (Pohl 1970)。

#### 焦点搜索。
FS 维护下界 f_min = min_{n ∈ OPEN} f(n) 和合格集 FOCAL = {n ∈ OPEN: f(n) ≤ wf_min}。(1) FOCAL 也可以使用显式合格阈值 C 定义为 FOCAL(C) = {n ∈ OPEN: f(n) ≤ C}。在本文中，我们使用方程 (1) 中的乘法定义。它使用一个次要优先级 d(n) 选择一个合格节点，该优先级本身不一定可接受。这种解耦将焦点搜索与那些排序和认证使用相同启发式的算法区分开来。随时焦点搜索 (Anytime Focal Search) 复用了这种结构，同时在找到可行解后收紧边界 (Cohen et al. 2018)；我们的主要研究关注第一个有界解。

#### 动态势能搜索。
DPS 可以视为 FS 的一个特例，其次要优先级是负动态势能，d(n) = -u_w(n) (Gilon et al. 2016)，其中 u_w(n) = (wf_min - g(n)) / h(n)。(2) 对于 h(n) > 0，当 f(n) ≤ wf_min 时，u_w(n) ≥ 1 恰好成立。在精确势能排序下，OPEN 中的最大势能节点因此属于 FOCAL，因此 DPS 可以在不显式维护 FOCAL 的情况下，在 OPEN 上最大化 u_w(n)。然而，与具有固定次要优先级的 FS 不同，u_w(n) 依赖于 f_min。f_min 的每一次变化因此要求在下一次选择之前刷新势能及其排序。遵循加权图上的 DPS 处理 (Gilon et al. 2017)，我们定义一个 h=0 的节点，只有当 g(n) ≤ wf_min 时势能为 +∞，否则为 -∞。这个端点惯例对于安全的目标测试至关重要。

## 概率焦点搜索
算法 1 呈现了 PFS。它保留了 FS 的 OPEN 和 FOCAL 组织，但使用概率 p 在两个选择策略之间进行选择。在迭代 t，它抽取 Z_t ~ Bernoulli(p)，其中 Pr(Z_t=1)=p，Pr(Z_t=0)=1-p。当 Z_t=1 时，PFS 遵循 FS 策略并选择 FOCAL 中的最小 d 节点。当 Z_t=0 时，它从 OPEN 中选择一个最小 f 节点。因此 p=1 恢复 FS，而 p=0 使用 A* 的主要排序。

算法 1 概率焦点搜索 (PFS)
1: 输入：起始节点 s₀，w ≥ 1，p ∈ [0,1]
2: g(s₀) ← 0；OPEN ← {s₀}；CLOSED ← ∅
3: f_min ← f(s₀)；FOCAL ← {s₀}
4: while OPEN ≠ ∅ do
5:   抽取 Z ~ Bernoulli(p)
6:   if Z=1 then
7:     n ← arg min_{u ∈ FOCAL} d(u)
8:   else
9:     n ← arg min_{u ∈ OPEN} f(u)
10:  end if
11:  if Goal(n) then
12:    return n
13:  end if
14:  从 OPEN 和 FOCAL 中移除 n；将 n 加入 CLOSED
15:  扩展后继节点；将改进的后继节点插入/重新打开到 OPEN 中，并在当前合格时加入 FOCAL
16:  if OPEN ≠ ∅ then
17:    f_min' ← min_{u ∈ OPEN} f(u)
18:    if f_min' > f_min then
19:      将新合格的节点添加到 FOCAL
20:    else if f_min' < f_min then
21:      从 FOCAL 中移除所有 f(n) > wf_min' 的节点 n
22:    end if
23:    f_min ← f_min'
24:  end if
25: end while

#### 算法与分析
算法 1 的结构与 FS 类似，但选择函数是概率性的。关键区别在于，PFS 以概率 1-p 强制执行 OPEN 头部的选择，即使该节点不在 FOCAL 中。这可能会更快地更新 f_min，从而扩大 FOCAL 并可能允许更好的节点进入。

PFS 的有界次优性证明很简单：由于 PFS 以正概率执行标准 FS 选择（Z_t=1），且每一步的选择集（OPEN ∪ FOCAL）包含所有可能用于证明有界次优性的节点（特别是最小 f 节点），因此它保留了 FS 的有界次优保证。形式化地说，考虑任何将 PFS 与 FS 的差异视为“噪声”的路径。由于在任何状态下选择 FOCAL 中节点的概率为 p > 0，并且算法会继续运行直到满足终止条件（这几乎必然发生），根据概率修正定理（或更直接地，考虑一个以概率 1 包含标准 FS 轨迹的概率空间），PFS 将以概率 1 找到一个满足 f(n) ≤ wf_min 的解，从而满足 f(n) ≤ wC*。

### 动态势能搜索
DPS 通常维护 OPEN 列表，并根据势能 u_w(n) 对其进行排序，如 (2) 所定义。对于 h(n) > 0，u_w(n) = [w(g(n) + h(n)) - g(n)] / h(n) = w + (w-1)g(n)/h(n) ≥ 1。因此，最大势能节点 n 满足 u_w(n) ≥ 1，等价于 f(n) ≤ wf_min。因此，精确 DPS 只需考虑 FOCAL，只要 OPEN 非空且 w ≥ 1，FOCAL 就包含一个最小 f 节点。

### 可接受的配额-Kruskal 森林下界
对于状态 n，令 x 为其当前顶点，d 为仓库，U(n) 为已覆盖客户，R(n) = max{0, Q - |U(n)|} 为剩余配额。令 C_v(n) 为被 v ∉ {x, d} 覆盖的未覆盖客户数量，并将正容量排序为 C_(1) ≥ ... ≥ C_(m)。令 k(n) = min{j: Σ_{i=1}^j C_(i)(n) ≥ R(n)}；每个可行完成路径必须访问至少 k(n) 个这样的顶点。对于 R(n) > 0，在 {x, d} ∪ {v: C_v(n) > 0} 上构造完全无向图；QKF 是其最便宜的 e(n) = k(n) + 1[x ≠ d] 条无环边的代价，由 Kruskal 算法选择 (Kruskal 1956)。如果 R(n) = 0，则在 d 处为 0，否则为 c(x, d)。每个可行完成路径都包含这样一个无环子集，其代价不大于自身；因此 h_QKF(n) ≤ h*(n)，QKF 是可接受的。

## 参考文献
- Cohen et al. (2018) L. Cohen, M. Greco, H. Ma, C. Hernández, A. Felner, T. K. S. Kumar, and S. Koenig. Anytime focal search with applications. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, pp. 1434–1441. External Links: Document (https://dx.doi.org/10.24963/ijcai.2018/199) Cited by: Focal Search, Experimental Setup.
- Gilon et al. (2016) D. Gilon, A. Felner, and R. Stern. Dynamic potential search—a new bounded suboptimal search. In Proceedings of the Ninth Annual Symposium on Combinatorial Search, Vol. 7, pp. 36–44. External Links: Document (https://dx.doi.org/10.1609/socs.v7i1.18392) Cited by: Introduction, Dynamic Potential Search.
- Gilon et al. (2017) D. Gilon, A. Felner, and R. Stern. Dynamic potential search on weighted graphs. In Proceedings of the Tenth Annual Symposium on Combinatorial Search, Vol. 8, pp. 119–123. External Links: Document (https://dx.doi.org/10.1609/socs.v8i1.18436) Cited by: Dynamic Potential Search, Experimental Setup.
- Hansson et al. (1992) O. Hansson, A. Mayer, and M. Yung. Criticizing solutions to relaxed models yields powerful admissible heuristics. Information Sciences 63(3), pp. 207–227. External Links: Document (https://dx.doi.org/10.1016/0020-0255(92)90070-O) Cited by: Experimental Setup.
- Hart et al. (1968) P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics 4(2), pp. 100–107. External Links: Document (https://dx.doi.org/10.1109/TSSC.1968.300136) Cited by: Background and Related Work.
- Helmert (2010) M. Helmert. Landmark heuristics for the pancake problem. In Proceedings of the Third Annual Symposium on Combinatorial Search, Vol. 1, pp. 109–110. External Links: Document (https://dx.doi.org/10.1609/socs.v1i1.18176) Cited by: Experimental Setup.
- Korf (1985) R. E. Korf. Depth-first iterative-deepening: an optimal admissible tree search. Artificial Intelligence 27(1), pp. 97–109. External Links: Document (https://dx.doi.org/10.1016/0004-3702(85)90084-0) Cited by: Experimental Setup.
- Kruskal (1956) J. B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society 7(1), pp. 48–50. External Links: Document (https://dx.doi.org/10.1090/S0002-9939-1956-0078686-7) Cited by: Appendix A.
- Pearl and Kim (1982) J. Pearl and J. H. Kim. Studies in semi-admissible heuristics. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-4(4), pp. 392–399. External Links: Document (https://dx.doi.org/10.1109/TPAMI.1982.4767270) Cited by: Introduction.
- Pohl (1970) I. Pohl. Heuristic search viewed as path finding in a graph. Artificial Intelligence 1(3–4), pp. 193–204. External Links: Document (https://dx.doi.org/10.1016/0004-3702(70)90007-X) Cited by: Background and Related Work.
- Reinelt (1991) G. Reinelt. TSPLIB—a traveling salesman problem library. ORSA Journal on Computing 3(4), pp. 376–384. External Links: Document (https://dx.doi.org/10.1287/ijoc.3.4.376) Cited by: Experimental Setup.
- Shaelaie et al. (2014) M. H. Shaelaie, ...