# 通过相关性匹配实现约束增强的物理搜索

# 约束增强的物理搜索：基于关联匹配原理

来源：https://arxiv.org/html/2606.03554

###### 摘要

物理系统并非仅仅为搜索过程引入噪声，它们还施加约束，从而产生结构化的关联。我们提出了一种**约束增强物理搜索**原理：探索过程中的时间关联应与更新动力学中约束诱导的空间关联相匹配。通过一个极简的拔河博弈（TOW）多臂老虎机模型，我们证明：守恒定律能将局部观测转化为跨候选方案的差异性证据，而具有时间关联的驱动信号则控制探索顺序。搜索效率的提升既不依赖于更强的随机性，也不依赖于最大化的反关联，而在于将时间关联与将反馈转化为证据的物理更新尺度相匹配。通过量纲估计，我们确定更新噪声与对比度之比是限制时间反关联可用程度的主要参数。研究结果表明，物理搜索存在一个普遍的组织原理：约束与涨落能产生结构化的时空关联，而当这些关联与更新动力学相匹配时，高效探索便自然涌现。

## 1 引言

许多困难的计算问题都需要高效的搜索策略，尽管不同问题的困难根源各异。对于组合优化问题，如可满足性问题（SAT）和路径搜索问题如旅行商问题（TSP），可能的配置数量随系统规模急剧增长，通常呈指数级\[1 (https://arxiv.org/html/2606.03554#biba.bib1)\]。相比之下，多臂老虎机问题的困难主要不在于组合爆炸，而在于探索与利用的两难困境：必须在收集不确定候选方案信息的同时，兼顾对当前最优选项的利用\[2 (https://arxiv.org/html/2606.03554#biba.bib2),3 (https://arxiv.org/html/2606.03554#biba.bib3),4 (https://arxiv.org/html/2606.03554#biba.bib4)\]。尽管存在这些差异，所有这些问题都需要一种能避免冗余探索、并将有限的局部信息转化为有效引导的搜索过程。

物理计算与生物启发计算的核心目标——通常在自然计算的更广框架下讨论——正是利用物理系统的特性来实现此类高效搜索。物理系统不仅仅是抽象算法的实现载体，它们能够并行更新大量自由度、在时间上连续演化、利用涨落，并在变量之间施加守恒定律或约束诱导的耦合。这些特性可以通过传播局部信息、抑制冗余尝试、协调候选方案或变量的运动来重塑搜索动力学。因此，问题不仅仅是物理系统能否表示一个搜索问题，更在于哪些物理特性能够产生搜索的高效性。

这一观点是此前物理方法处理困难搜索与决策问题的基础。拔河博弈（TOW）动力学作为一种资源守恒型搜索原理被引入多臂老虎机问题\[5 (https://arxiv.org/html/2606.03554#biba.bib5),6 (https://arxiv.org/html/2606.03554#biba.bib6)\]，随后在物理决策系统中得到实现\[7 (https://arxiv.org/html/2606.03554#biba.bib7),8 (https://arxiv.org/html/2606.03554#biba.bib8),9 (https://arxiv.org/html/2606.03554#biba.bib9)\]。变形虫启发的TSP搜索方法利用物理或生物基底中的关联形变与资源重分配\[10 (https://arxiv.org/html/2606.03554#biba.bib10),11 (https://arxiv.org/html/2606.03554#biba.bib11)\]。变形虫启发的SAT求解器以及基于棘轮机制的实现进一步表明，受约束的物理动力学能够并行协调大量局部决策\[12 (https://arxiv.org/html/2606.03554#biba.bib12),13 (https://arxiv.org/html/2606.03554#biba.bib13)\]。混沌驱动与关联搜索过程表明，时间结构同样可以减少冗余探索\[14 (https://arxiv.org/html/2606.03554#biba.bib14),9 (https://arxiv.org/html/2606.03554#biba.bib9)\]；附录C中给出了一个纯时间维度的简单示例。这些例子共同引出一个核心问题：**结构化动力学改善搜索的最小物理原理是什么？**

本文的目标是在最简单的情境中提炼出这一原理，使各相关组件得以分离分析。我们聚焦于反复出现在物理搜索系统中的两个要素：具有时间结构的探索和约束诱导的局部信息再分配。时间结构控制候选方案被探索的顺序，并能减少冗余采样。约束诱导的再分配则将局部观测转化为跨候选方案的协调更新。我们的核心论点是：当这两种关联结构相互兼容时，高效的物理搜索便得以涌现。

本文采用极简TOW老虎机模型来研究这一原理。我们并不主张TOW动力学能代表SAT或TSP动力学的全部复杂性，而是将TOW作为一个可控的简化系统，在其中时间关联和守恒诱导的选项间关联可以独立变化并被精确测量。时间分量由一个具有关联性的探索驱动来表示；空间分量由一个守恒型TOW更新来表示，该更新将奖励反馈转化为竞争候选方案之间的反关联更新。通过组合这两个分量，我们探究时间探索何时能被高效转化为差异性证据，并推导出最优时间反关联的量纲估计。

由此得到的原理并非"随机性越强越好"，也非"时间反关联越强越好"。有效的时间结构必须通过物理更新尺度与局部反馈转化为协调证据的过程相调谐。从这个意义上说，本文揭示的是搜索效率的一个物理根源：约束与涨落产生结构化关联，高效搜索正是从二者的相互作用中涌现。

本文有三方面贡献。第一，构建了一个极简TOW老虎机模型，其中时间探索驱动与守恒诱导更新可独立变化。第二，引入了一种交互诊断量，将时间反冗余与TOW诱导的差异性证据形成的独立效应分离开来。第三，推导出一个量纲估计，表明时间反关联的建设性利用受到更新噪声与对比度之比的限制。

## 2 极简TOW老虎机模型

考虑两个候选方案 $A$ 和 $B$，其奖励概率满足 $P_A > P_B$。奖励差距为

$$\Delta P = P_A - P_B. \tag{1}$$

内部价值为 $Q_A, Q_B$，差异性证据为

$$Z = Q_A - Q_B. \tag{2}$$

一个具有时间关联的二元信号 $s_t \in \{-1, +1\}$ 对选择边界进行调制：

$$a_t = \begin{cases} A, & Z_t + \sigma s_t > 0, \\ B, & Z_t + \sigma s_t < 0. \end{cases} \tag{3}$$

在零边界处 $Z_t + \sigma s_t = 0$ 时，选择随机化。该信号服从两态 Markov 动力学：

$$\Pr(s_{t+1} = s_t) = \frac{1+\lambda}{2}, \qquad \Pr(s_{t+1} = -s_t) = \frac{1-\lambda}{2}. \tag{4}$$

因此 $\lambda < 0$ 表示时间反关联。在这一极简信号模型中，我们用

$$\chi = \max(0, -\lambda) \tag{5}$$

作为时间非冗余性的代理指标。对于一般的物理信号，可将其替换为加权关联泛函：

$$\chi = -\sum_{\tau \geq 1} w_\tau C_s(\tau), \tag{6}$$

其中 $C_s(\tau)$ 为与任务相关的自相关函数。

TOW 分量实现为一种广义守恒诱导反关联更新。若被选中的选项收到

$$d_t = \begin{cases} +\eta, & R_t = 1, \\ -\eta\omega_0, & R_t = 0, \end{cases} \tag{7}$$

则竞争选项收到 $-\kappa d_t$。例如，当选中 $A$ 时：

$$Q_A \leftarrow Q_A + d_t, \qquad Q_B \leftarrow Q_B - \kappa d_t. \tag{8}$$

其中 $\kappa = 0$ 对应普通的单侧更新，而 $\kappa = 1$ 给出精确的TOW守恒：

$$Q_A + Q_B = \mathrm{const.} \tag{9}$$

惩罚参数为TOW值：

$$\omega_0 = \frac{\gamma}{2-\gamma}, \qquad \gamma = P_A + P_B, \tag{10}$$

除非另有说明。差异性证据的更新被放大为：

$$\Delta Z = (1+\kappa) d_t. \tag{11}$$

信号 $s_t$ 不直接更新 $Z_t$，而是通过式 (3) 中的选择边界调制来决定哪个候选方案被采样。在早期阶段 $|Z_t| < \sigma$ 时，这种调制改变了对两个候选方案访问的时间分布。由此产生的奖励观测决定 $d_t$，而TOW规则随后将这一局部反馈转化为差异性更新 $\Delta Z = (1+\kappa) d_t$。因此，时间驱动塑造了观测的顺序，而守恒诱导的更新则决定了每次观测如何被累积为差异性证据。

图1 (https://arxiv.org/html/2606.03554#S2.F1) 总结了极简TOW老虎机模型。一次两臂老虎机试验包括：选择一条臂、观测二元奖励、更新内部TOW值。图中还展示了时间关联驱动如何偏移零选择边界，以及奖励反馈如何被转化为内部值的反关联更新。变量 $Q_A$ 和 $Q_B$ 应理解为内部物理证据变量，而非对 $P_A$ 和 $P_B$ 的直接估计。决策基于二者之差 $Z_t = Q_A - Q_B$，而探索驱动 $\sigma s_t$ 则偏移有效选择边界。TOW规则随后将一次局部的奖励或无奖励事件转化为两个内部值的反关联更新。

参见图注**图1：极简TOW老虎机模型。** 一次两臂老虎机试验包括：选择臂 $a_t \in \{A, B\}$，观测二元奖励 $R_t \in \{0, 1\}$，并更新内部TOW值 $Q_A$ 和 $Q_B$。当 $\kappa = 1$ 时，更新满足精确TOW守恒 $Q_A + Q_B = \mathrm{const}$。差异性证据 $Z_t = Q_A - Q_B$ 经时间关联驱动 $\sigma s_t$ 调制后与零选择边界比较。奖励反馈定义更新增量 $d_t$，TOW规则则沿相反方向更新被选臂与竞争臂。从而，局部奖励观测被转化为内部状态的选项间反关联更新。同样的选择–更新循环也可以表示为离散有限状态 Markov 过程，详见附录B (https://arxiv.org/html/2606.03554#A2)。该表述并非用来替代量纲论证，而是表明极简模型具有明确定义的随机动力学，离散化后可直接计算后悔值。

### 时间关联与空间关联之间的交互

在定义选择与更新循环之后，我们接下来量化时间驱动与TOW更新是独立作用还是协同作用。这里，空间分量指由TOW约束产生的选项间反关联，即约束诱导的局部反馈在候选方案间的再分配。设 $R_{\chi\kappa}$ 为时间反关联为 $\chi$、选项间反关联为 $\kappa$ 时系统的后悔值。

以 $R_{00}$ 为无关联基线，定义

$$\mathcal{E}_{\chi\kappa} = \frac{R_{00}}{R_{\chi\kappa}}. \tag{12}$$

为隔离时间关联与空间关联之间的交互，定义

$$I(\chi, \kappa) = \mathcal{E}_{\chi\kappa} - \mathcal{E}_{\chi 0} - \mathcal{E}_{0\kappa} + 1, \tag{13}$$

以及

$$\Lambda(\chi, \kappa) = \frac{I(\chi, \kappa)}{\chi\kappa}. \tag{14}$$

$\Lambda > 0$ 意味着时间反关联不仅仅在独立地增加探索多样性，而是通过TOW守恒定律被转化为有效的差异性证据。

## 3 建设性协同与中间强度反关联

仿真结果在组合系统中展现出鲁棒的效率提升区间，同时协同诊断量量化了时间–空间交互的非加性部分。这一效果并非通过使信号达到最大反关联来获得。在以下代表性参数设置下：

$$P_A = 0.7, \quad P_B = 0.5, \quad \sigma \simeq 1.3, \quad \eta = 0.5, \quad \kappa = 1,$$

这些参数处于一个具有代表性的传导区间：探索性边界偏移足够大，能够影响早期的选择序列，而更新步长又不至于大到使动力学立即锁定在早期的噪声决策上。在这一区间内，时间驱动、奖励反馈和TOW更新均有可测量的贡献，从而使时间反冗余与约束诱导差异性证据形成之间的交互得以被诊断。

数据显示，在中间强度负关联处存在一个宽泛的效率提升区域。因此，我们重点关注组合系统的鲁棒性改善以及协同诊断，而非 $\lambda$ 的局部极值的精确位置。这将关联匹配与简单反关联原理区分开来：完全交替并非最优，因为时间驱动必须与空间更新尺度相匹配。

图2 (https://arxiv.org/html/2606.03554#S3.F2) 展示了相应的效率增益和协同诊断，并附有误差传播的标准误差。组合TOW系统在所测试的负时间关联范围内，相对于无关联基线鲁棒地提升了效率。这一改善无法单独由时间反关联或TOW守恒来解释，而是反映了通过守恒诱导更新将非冗余时间采样转化为差异性证据的过程。协同系数 $\Lambda$ 作为这一非加性交互的诊断指标，而非用于逐点确定 $\lambda$ 的尖锐最优值。

参见图注**图2：时间反关联与TOW守恒相结合的效率增益与协同诊断。** (a) 组合效率 $\mathcal{E}_{\chi\kappa} = R_{00}/R_{\chi\kappa}$ 关于时间关联参数 $\lambda$ 的函数，参数设置为 $P_A = 0.7$，$P_B = 0.5$，$\sigma = 1.3$，$\eta = 0.5$，$\kappa = 1$。高于1的值表示相对于无关联单侧基线的后悔值降低。高统计量数据在所测试的负时间关联范围内显示出鲁棒的效率增益。误差棒为由后悔值估计的标准误差传播所得的标准误差。(b) 协同系数 $\Lambda$，用于隔离时间反关联与守恒诱导选项间