🤖 machine learning

Prioritizing Search Space Regions in the Low Autocorrelation Binary Sequences Problem

本文介绍了一种结合了汤普森采样（Thompson sampling）与并行自回避行走（parallel self-avoiding walks）以及 GPU 加速的混合搜索框架，用于在 LABS 搜索空间内自适应地分配计算资源，成功改进了 35 个序列长度的最佳已知结果，并发现了一个优值因子（merit factor）超过 8.0 的新最长序列。

原作者： Blaž Pšeničnik, Borko Bošković, Jan Popić, Janez Brest

发布于 2026-07-14

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Blaž Pšeničnik, Borko Bošković, Jan Popić, Janez Brest

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图为一个巨大的宇宙锁寻找那唯一的、完美的组合。这个锁由一长串开关组成，每个开关只能被拨到“向上”（+1）或“向下”（-1）。目标是什么？是安排这些开关，使得这个模式在向左或向右稍微滑动时，不会意外地看起来像它自己。在现实世界中，这被称为**低自相关二进制序列（LABS）**问题，它是卫星导航和清晰无线电信号背后的秘密武器。

麻烦在于，可能性的开关组合数量增长得极快，简直是一场噩梦。如果你有 500 个开关，排列组合的方式就会变成一个天文数字，大到让天上的星星看起来都像尘埃一样渺小。大多数排列都是糟糕的“噪声”，而完美的那些则像是要在有一整个大陆那么大的沙漠中寻找一个微小的高尔夫球洞。

旧方法：猜想与检查

以前，科学家们尝试通过观察锁孔的“形状”来解决这个问题。他们利用数学规则来猜测哪些初始模式看起来更有希望。这就像是在草堆里找针，但只通过寻找那些看起来“闪闪发光”的针来寻找。有时这很奏效，但通常他们会把时间浪费在那些看起来闪亮却最终毫无用处的针上。

新策略：聪明的侦探

来自马里博大学（University of Maribor）的一个团队，决定不再仅仅靠猜想，而是开始学习。他们构建了一个混合搜索引擎，这个引擎就像一个使用名为 Thompson 采样（Thompson sampling） 技巧的超级聪明侦探。

这位侦探是如何工作的：

分而治之： 他们没有试图一次性观察整个沙漠，而是将搜索空间划分为不同的“邻里”（称为划分）。
多臂老虎机： 想象一排老虎机（摇杆）。有些机器会支付巨额奖金（高质量序列），而有些则只给你几枚硬币。侦探并不知道哪台机器是赢家。
边走边学： 侦探拉动一个摇杆（探索一个邻里）。如果回报丰厚，侦探就会变得兴奋，并再次拉动该摇杆。如果是个哑炮，侦探就会转向下一个。但神奇之处在于：侦探也带有一点好奇心。它偶尔也会尝试那些“无聊”的机器，以防它们其实是最好的。这种利用（去有钱的地方）与探索（检查未知领域）之间的平衡，正是其方法的内核。

超高速引擎

为了让这位侦探足够快且实用，团队为它提供了巨大的助力。他们在强大的 GPU（用于高端游戏的游戏芯片）上同时运行了数千个这样的“侦探漫步”。他们还使用了一种巧妙的“布隆过滤器（Bloom filter）”，这是一种超快速的记忆技巧，让侦探无需巨大的笔记本就能记住自己走过的每一条路径，从而防止陷入循环。

他们还采用了两阶段策略：

第一阶段： 侦探在一个受限的、更容易处理的版本（使用“斜对称”规则）的锁中进行搜索，以找到最佳候选者。
第二阶段： 顶尖的候选者会被带到“精炼车间”，在那里规则被放宽，允许侦探自由微调序列，以榨取更多的完美度。

结果：打破纪录

这次实验的结果令人印象深刻。团队测试了长度在 450 到 527 之间以及长度为 573 的二进制序列。

新纪录： 在该范围内，他们为 35 种不同的序列长度 找到了比以往任何人看到的都更好的解决方案。
重大发现： 最令人兴奋的发现是针对长度 L = 451 的序列。他们发现了一个“品质因子”（衡量序列优劣的分数）为 8.0555 的序列。这是目前报道过的最长的品质因子超过 8.0 的序列。在此之前，最长的此类序列长度仅为 309。
另一个里程碑： 对于长度 L = 573，他们将分数提升到了 7.2774，这是在该长度下发现的最高品质因子（高于 7.0）。

他们没做的事（以及为什么这很重要）

需要注意的是，这篇论文并没有声称解决了所有可能长度的 LABS 问题。正如论文所提到的，随着序列变长，景观会变得“日益崎岖”，这意味着改进变得越来越微小且难以寻找。他们没有使用量子计算机来解决这个问题，而是使用了带有聪明算法的经典计算机（GPU）。他们也没有仅仅模拟结果；他们实际上生成并验证了这些新序列，提供了具体的二进制模式（以十六进制格式呈现），供他人核查。

总结

这篇论文表明，通过让计算机在搜索的同时进行学习——即根据发现的内容动态决定在哪里投入时间，而不是遵循死板的地图——我们可以破解一些最难的组合数学谜题。该团队展示了这种数据驱动、自适应的方法是一种强大的工具，它将混乱的搜索转变为一场专注的狩猎，寻找完美的信号。虽然对于极长的序列来说，这个问题仍然极其困难，但这种方法已成功推向了我们认知边界的极限，在数字沙漠中找到了新的“黄金”。

技术摘要：低自相关二进制序列问题中的搜索空间区域优先级排序

问题定义
低自相关二进制序列（LABS）问题是一个具有挑战性的组合优化任务，旨在寻找二进制序列 $S = \{s_1, \dots, s_L\}$ （其中 $s_i \in \{+1, -1\}$ ），以最小化平方非周期自相关之和。其目标是最大化优值因子（Merit Factor） $F$ ，定义为 $F(S) = L^2 / 2E(S)$ ，其中 $E(S)$ 是序列能量。搜索空间呈指数级增长（ $2^L$ ），其特征是具有高度崎岖的景观，存在大量局部极小值和稀少且孤立的全局极小值。虽然偏斜对称序列（skew-symmetric sequences，即满足 $s_{k+1+i} = (-1)^i s_{k+1-i}$ ）可以缩小搜索空间并消除奇数位移自相关，但对于较大的 $L$ ，寻找最优序列在计算上仍然是难以处理的。

方法论
作者提出了一种混合搜索框架 TS-SAW，该框架通过集成在线决策与并行随机搜索，动态地在 LABS 搜索空间中分配计算资源。该方法由三个核心部分组成：

用于分区优先级排序的汤普森采样（Thompson Sampling for Partition Prioritization）：
将搜索空间分解为不相交的区域，称为“限制类”（restriction classes）或分区，这些分区由固定序列的前 $p$ 个元素来定义。这些分区被建模为多臂老虎机问题中的“臂”（arms）。作者没有依赖静态启发式方法（如势能值）来对分区进行排名，而是采用 汤普森采样 来自适应地选择分区。
- 每个分区 $k$ 都关联一个未知参数 $\theta_k$ ，代表其预期的优值因子。
- Beta 分布 $Beta(\alpha_k, \beta_k)$ 作为 $\theta_k$ 的先验分布。
- 算法使用 分数汤普森采样（Fractional Thompson Sampling） 来处理连续奖励（归一化后的优值因子）。在对一个分区进行搜索并产生奖励 $r_t \in [0, 1]$ 后，参数更新为 $(\alpha_k, \beta_k) \leftarrow (\alpha_k + r_t, \beta_k + 1 - r_t)$ 。
- 这种机制能够动态地将计算精力转向那些经验上产生更高优值因子的分区，同时保持对采样较少区域的探索。
在 GPU 上进行的并行自回避行走（Parallel Self-Avoiding Walks, SAW）：
一旦选定一个分区，算法就会在该受限空间内执行自回避行走以优化序列。
- 实现： 这些行走在 NVIDIA GPU（CUDA）上并行执行。每次行走作为一个独立的智能体运行在 CUDA 块中。
- 循环预防： 为了在不消耗过多内存的情况下防止重复访问状态，算法使用 布隆过滤器（Bloom filter） 来存储已访问序列的哈希值。
- 效率： 对于偏斜对称序列，邻域评估使用线性时间复杂度的翻转操作（flip operations），确保了低内存占用和高吞吐量。
- 共享学习： 虽然行走是并行运行的，但它们共享一个全局后验信念（ $\alpha_k, \beta_k$ ），该信念在每批次行走结束后进行更新，从而加速学习过程。
两阶段优化流水线：
该框架采用两阶段策略来精炼解：
- 第一阶段（受限）： 并行 SAW 在分区的偏斜对称搜索空间中进行探索。前 $m$ 个候选解（通过快速选择算法选取）将被传递到下一阶段。
- 第二阶段（无约束）： 这些候选解在不受限制的搜索空间中进行进一步精炼。此阶段移除偏斜对称性和分区约束，利用优先队列和序列算子（旋转与翻转）来探索更广泛的区域并提升解的质量。
- 序列算子： 为了处理偶数长度的序列，该方法应用算子将优化后的奇数长度序列转换为偶数长度变体，随后将其反馈至精炼阶段。

主要贡献

自适应资源分配： 一种新型在线方法，利用汤普森采样动态优先排序搜索空间区域，超越了静态启发式排名。
混合算法 (TS-SAW)： 一种结合了多臂老虎机决策与 GPU 加速并行自回避行走的全新算法。
可扩展架构： 一个两阶段流水线，利用大规模并行化进行初步探索，并利用无约束精炼进行最终优化。
新的最佳已知解： 生成了针对 35 种不同长度（范围在 $450 \le L \le 527$ 之间）以及 $L = 573$ 的新纪录序列。

实验结果
实验在配备 NVIDIA A100 GPU 的 Vega 超级计算机上进行。该方法针对长度为 $450 \le L \le 527$ 和 $L = 573$ 的二进制序列进行了测试，初始阶段运行了 100,000 次迭代。

优值因子改进： 所提方法改进了所有 35 个测试长度的原有最佳已知优值因子。改进序列的平均优值因子增幅为 0.1967。
打破纪录：
- 对于 $L = 451$ ，该方法实现了优值因子 $F = 8.0555$ ，比之前的最佳结果高出 0.8248。据报道，这是文献中优值因子超过 8.0 的最长序列。
- 对于 $L = 573$ ，优值因子提升了 0.2564，代表了目前已知的最长 $F > 7.0$ 的序列。
分区分析： 针对 $L=461$ 的实验表明，汤普森采样能有效识别高性能分区。算法将重心从具有高理论“归一化势能”的分区转移到了经验上产生更好结果的分区，证实了数据驱动分配优于静态启发式方法的价值。

意义与主张
论文声称，所提出的框架为最大化 LABS 问题中的优值因子提供了一种 可扩展且有效的策略。通过将概率决策与高性能并行计算相结合，该方法成功平衡了在高度崎岖的搜索空间中的探索与开发。作者断言，尽管随着序列长度的增加，改进难度日益增大，但其数据驱动、分区引导的随机优化方法仍是推进该领域前沿技术的一个极具前景的方向。结果验证了在线自适应资源分配在处理此类组合优化问题时，优于静态启发式优先级排序。作者总结道，该框架为其他可以将搜索空间进行有效分区的困难组合优化问题提供了自适应搜索策略的路径。