新上线今天0 投票
低自相关二进制序列问题新突破：汤普森采样与并行自回避行走混合框架
低自相关二进制序列问题（LABS）是一类极具挑战性的组合优化问题，在通信、信号处理和卫星导航等领域具有重要应用。近日，来自斯洛文尼亚的研究团队提出了一种混合搜索框架，通过结合汤普森采样与并行自回避行走，在LABS搜索空间中自适应地分配计算资源，显著提升了长序列的优值因子。
核心方法：多臂老虎机视角下的搜索空间分区
LABS问题的搜索空间随序列长度呈指数增长，传统方法难以高效探索。研究团队将搜索空间划分为若干限制类，并将每个类视为多臂老虎机问题中的一个“臂”。通过汤普森采样，算法能够动态地将更多计算资源分配给历史上产生较高优值因子的分区，同时保持对采样不足区域的探索。这种在线、数据驱动的资源分配策略避免了盲目均匀搜索，大幅提升了效率。
并行自回避行走则用于在每个分区内进行局部搜索，通过GPU并行执行和共享后验更新进一步加速。此外，研究引入了布隆过滤器防止循环重复探索，并采用两阶段优化策略：首先在约束的偏斜对称空间中搜索，再对最优候选解在无限制空间中进行精细化调优。
实验结果：打破35项序列长度纪录
在长二进制序列上的实验显示，该方法在450≤L≤527范围内的35个序列长度以及L=573上，均改进了此前已知的最优结果。特别地，研究团队报告了优值因子超过8.0的最长序列，在L=451时取得。这一成果标志着LABS问题在中等长度区间内的显著进步。
行业意义与未来方向
LABS问题在雷达波形设计、CDMA通信和GPS信号编码中至关重要。更高的优值因子意味着更低的干扰和更好的信噪比。本研究的混合框架不仅为组合优化提供了新工具，其“在线分配-局部搜索-精细化”的范式也可推广至其他NP难问题。未来，结合更先进的强化学习算法或更大规模GPU集群，有望进一步突破序列长度限制。