低自相关二进制序列（LABS）问题是一项极具挑战性的组合优化难题，在通信、信号处理和卫星导航等领域有着重要的应用。该问题的目标是寻找具有最小自相关值的二进制序列，但搜索空间随着序列长度呈指数增长，使得精确求解变得极为困难。近日，一支研究团队提出了一种新颖的混合搜索框架，将汤普森采样（Thompson sampling）与并行自回避行走（parallel self-avoiding walks）相结合，旨在自适应地分配计算资源，从而更高效地探索LABS问题的解空间。
该方法的核心思想是将搜索空间划分为多个分区（restriction classes），并将每个分区视为多臂老虎机问题中的一个“臂”。通过汤普森采样，算法动态地根据各分区历史上产生的品质因子（merit factor）来调整搜索资源的分配，优先投资于那些能够带来更高品质因子的分区，同时保留对较少探索区域的随机性。这种在线、数据驱动的资源分配策略确保了探索与利用之间的平衡。
为了进一步提升算法效率，研究团队采用了多项加速技术。首先，利用GPU并行执行搜索任务，同时对多个分区进行自回避行走，大幅缩短了搜索时间。其次，通过共享后验更新机制，各个并行进程能够及时分享彼此的发现，加快收敛速度。此外，高效的邻域评估方法减少了计算量，而布隆过滤器（Bloom filter）有效防止了搜索过程中的循环，避免了重复计算。
在优化策略上，该框架采用了两阶段方法：第一阶段在受约束的偏斜对称（skew-symmetric）空间中进行搜索，利用对称性质缩减搜索范围；第二阶段则将第一阶段得到的最佳候选序列放入无约束空间中进一步精炼，以获得更优的解。这种两阶段设计充分利用了问题结构的特性，提高了搜索的针对性和效率。
实验结果表明，该框架在多个长二进制序列上取得了突破性进展。在序列长度L从450到527的范围内，以及L=573时，该方法共改进了35个长度下的已知最佳结果。特别值得一提的是，在L=451时，研究团队发现了一条品质因子超过8.0的新最长序列，这是该领域的一个重要里程碑。这些结果充分验证了汤普森采样在LABS优化中有效识别高性能分区的潜力，也证明了在线数据驱动资源分配策略的价值。
总体而言，该混合搜索框架为LABS问题提供了一种可扩展且高效的最大化品质因子的策略。通过将经典的自回避行走与现代机器学习方法（如汤普森采样）相结合，该工作展示了如何将组合优化与自适应决策融为一体，有望推动相关应用领域的发展。