低自相关二值序列问题中搜索空间区域的优先级排序

# 低自相关二进制序列问题中的搜索空间区域优先级排序
来源: https://arxiv.org/html/2607.09688
[![[无标题图片]](https://arxiv.org/html/2607.09688v1/x1.png)Blaž Pšeničnik](https://orcid.org/0009-0000-1598-8056) 马里博尔大学电气工程与计算机科学学院计算机架构与语言实验室 blaz\.psenicnik1@um\.si &[![[无标题图片]](https://arxiv.org/html/2607.09688v1/x2.png)Borko Bošković](https://orcid.org/0000-0002-7595-2845) 马里博尔大学电气工程与计算机科学学院计算机架构与语言实验室 borko\.boskovic@um\.si &[![[无标题图片]](https://arxiv.org/html/2607.09688v1/x3.png)Jan Popič](https://orcid.org/0000-0002-7156-7050) 马里博尔大学电气工程与计算机科学学院计算机架构与语言实验室 jan\.popic1@um\.si &[![[无标题图片]](https://arxiv.org/html/2607.09688v1/x4.png)Janez Brest](https://orcid.org/0000-0001-5864-3533) 马里博尔大学电气工程与计算机科学学院计算机架构与语言实验室 janez\.brest@um\.si

###### 摘要

低自相关二进制序列问题（LABS）是一个具有重要应用的硬组合优化挑战，涉及通信、信号处理和卫星导航等领域。本文提出了一种混合搜索框架，该框架结合汤普森采样与并行自回避行走，自适应地分配计算资源到LABS搜索空间的不同限制类上。通过将划分建模为多臂老虎机设置中的臂，所提方法动态地将搜索资源转向经验上产生更高优值因子的划分，同时维持对采样较少区域的探索。该方法进一步通过GPU并行执行、共享后验更新、高效邻域评估以及用于循环预防的布隆过滤器来加速。此外，我们采用两阶段优化策略，首先搜索受限的分区斜对称空间，然后在不限空间内优化最佳候选解。在长二进制序列上的实验表明，对于范围450≤L≤527中的35个序列长度以及L=573，所提方法改进了先前已知的最佳结果。特别地，我们报告了新的最长序列，其优值因子超过8.0，在L=451时获得。结果还表明，汤普森采样有效地优先处理具有更好观测性能的划分，证实了在线数据驱动资源分配在LABS优化中的价值。总体而言，所提出的框架为高性能优值因子最大化提供了一种可扩展且有效的策略。

*关键*词LABS，优值因子，强化学习，汤普森采样

## 引言

低自相关二进制序列（LABS）的研究被认为是一个极具挑战性的计算问题，属于硬二进制组合问题类别。该问题由Golay在1972年正式提出[20 (https://arxiv.org/html/2607.09688#bib.bib14)]。早期的基础工作由数学家Littlewood奠定[30 (https://arxiv.org/html/2607.09688#bib.bib15)]，他研究了系数限制为±1的复平面单位圆上的多项式，该问题与LABS密切相关。低自相关序列在许多实际环境中具有价值。在数字通信中，它们能更有效地将信号与背景噪声区分开[26 (https://arxiv.org/html/2607.09688#bib.bib16),28 (https://arxiv.org/html/2607.09688#bib.bib18)]，并且对于数据包检测和比特对齐[43 (https://arxiv.org/html/2607.09688#bib.bib53)]至关重要，特别是对于低功耗物联网接收器。此外，它们的应用还扩展到物理[4 (https://arxiv.org/html/2607.09688#bib.bib17)]、化学和密码学等领域。关于其他应用和理论发展的更广泛概述可参见该主题的综述文献[26 (https://arxiv.org/html/2607.09688#bib.bib16)]。一个特别引人注目的应用是它们在高度精确的行星际雷达实验中的作用，该实验旨在测试时空曲率[41 (https://arxiv.org/html/2607.09688#bib.bib19)]。在全球导航卫星系统（GNSS）中，低自相关序列发挥着关键作用；当与其他理想属性结合时，它们被称为扩频码[47 (https://arxiv.org/html/2607.09688#bib.bib20)]。例如，全球定位系统L1 C/A信号使用一组63个不同的扩频码，每个码长度为1023[47 (https://arxiv.org/html/2607.09688#bib.bib20)]。这类码在低地球轨道（LEO）卫星应用中也具有重要意义[48 (https://arxiv.org/html/2607.09688#bib.bib21)]。近年来，随着量子计算的出现，人们对这个问题的兴趣进一步增长，因为此类组合优化挑战被视为量子算法[40 (https://arxiv.org/html/2607.09688#bib.bib22),42 (https://arxiv.org/html/2607.09688#bib.bib24)]的有前途候选。

在文献中，二进制序列通常使用两种自相关形式进行分析：周期自相关函数和非周期自相关函数[39 (https://arxiv.org/html/2607.09688#bib.bib26)]。非周期自相关通常被视为实际系统中序列行为更现实的描述[29 (https://arxiv.org/html/2607.09688#bib.bib25)]。长度为L的二进制序列定义为S(L)={s1,s2,...,sL}，其中元素满足si∈{+1,−1}。非周期自相关函数由下式给出：

Ck(S)=∑i=1L−ksisi+k,k∈{1,...,L}。(1)
序列能量定义为E(S)=∑k=1L−1Ck2(S)，即所有非零位移k上平方非周期自相关值的总和。文献中的序列搜索和设计方法通常遵循两个主要优化准则。第一个目标是最小化峰值旁瓣电平（PSL），而第二个目标是最大化优值因子（F）[32 (https://arxiv.org/html/2607.09688#bib.bib27)]，定义为：

F(S)=L2/(2E(S))。(2)这两个目标构成一个权衡，使得它们的同步优化通常不可行。因此，实际的序列设计并不试图平衡PSL和MF；而是根据应用和设计要求专注于优化PSL或F[11 (https://arxiv.org/html/2607.09688#bib.bib28)]。LABS问题的目标是找到二进制序列S∗，对于给定长度L，实现可能的最大优值因子F：

S∗=argmaxS∈{−1,1}L F(S)。(3)换句话说，目标是找到一个最大化方程(2)中定义的优值因子的序列，从而最小化相关的自相关能量。

由于LABS是一个二进制组合优化问题，搜索空间的大小随序列长度L呈指数增长，具体为2L。该景观的特征是随着L增加，局部极小值数量呈指数增长，而全局极小值极其罕见、高度孤立且轮廓分明，形状类似高尔夫球洞[14 (https://arxiv.org/html/2607.09688#bib.bib30)]。图1通过搜索空间的二维投影说明了全局和局部最优的分布。该投影通过UMAP（均匀流形逼近与投影）[22 (https://arxiv.org/html/2607.09688#bib.bib29)]（一种降维技术）获得，序列长度L=12,15,17。方程(1)中的Ck(S)值在以下情况下保持不变：如果每个序列元素的符号被翻转（即乘以−1），或者序列被反转。在这些变换下，序列能量保持不变[33 (https://arxiv.org/html/2607.09688#bib.bib31)]。如果序列的交替元素被取补，则奇数索引k的相关性保持不变，而偶数索引的相关性仅改变符号。因此，所有长度为L的序列可以分成八个互等类。因此，不等价序列的数量略大于2(L−3)[33 (https://arxiv.org/html/2607.09688#bib.bib31)]。在图1中，这些对称类对于每个序列长度显示为不同的聚类。

参见说明图1：使用降维方法UMAP[22 (https://arxiv.org/html/2607.09688#bib.bib29)]对序列长度L=12,15,17的搜索空间进行二维投影。红点代表全局最小值，绿点代表局部最小值，蓝点对应所有其他序列。由于问题搜索空间的指数增长，对其进行缩减可能非常有利。奇数长度L=2k+1的二进制序列称为斜对称[20 (https://arxiv.org/html/2607.09688#bib.bib14)]，如果它满足以下条件：

s(k+1)+i=(−1)is(k+1)−i,i=1,2,⋯,k。(4)该约束有效地将搜索空间缩减为2((L+1)/2)，并确保所有奇数位移的旁瓣消失，即对于所有奇数k，Ck=0。其结果是总能量E降低，从而提高了优值因子F。对于序列长度L≤66，只有22个最优序列S∗也是斜对称的[33 (https://arxiv.org/html/2607.09688#bib.bib31)]。

由于对于较大的L值，穷举搜索在计算上变得棘手，所以引入了限制类[15 (https://arxiv.org/html/2607.09688#bib.bib4)]。这种方法可以将搜索空间分解为多个不相交的区域，然后可以并行探索这些区域。通过固定序列的前p个元素，搜索空间又可以缩减为2(L/2−p)。前p个元素根据长度g（加数个数）的划分（限制类）[15 (https://arxiv.org/html/2607.09688#bib.bib4)]的最小或归一化势来确定。接下来的k−p+1个元素是自由的，而最后k个元素使用斜对称规则确定，如方程(5)所示。这有效地将自相关函数中的一些元素分配给较小的值，从而降低了总能量。为了对划分进行排序，文献[15]的作者建议为每个划分使用势和归一化势。这种基于群论的搜索空间缩减提供了一种比考虑所有可能的限制类更有效的方法来寻找具有所需属性的序列。

S(L) = s1 s2 ... sp⏟p sp+1 sp+2 ... s_{k−1} s_k s_{k+1}⏟k−p+1 s_{k+2} s_{k+3} ... s_{L−1} s_L⏟k (5)
在这项工作中，我们解决了在LABS问题中高效探索指数级大的二进制序列搜索空间，同时保持探索与利用的强平衡的挑战。我们提出了一个混合框架，该框架结合了基于汤普森采样的在线决策和并行自回避行走，以动态分配计算资源到不同的限制类。每个限制类被视为多臂老虎机设置中的一个臂，使得能够自适应地聚焦于经验上产生更高优值因子的搜索空间区域，同时仍然对采样不足的划分进行足够的探索。生成的搜索过程通过GPU并行执行独立行走、共享全局后验更新、使用线性时间翻转操作和用于循环预防的布隆过滤器进行高效邻域评估而进一步加速。此外，我们合并了一个两阶段优化策略，首先探索受限的分区对称搜索空间，随后在不限空间中优化高质量候选解，以提高解的质量。这些组件共同形成了一种可扩展的数据驱动搜索策略，利用随机决策和高性能并行计算显著增强了优值因子最大化的有效性。

因此，本文的主要贡献如下：

- •我们提出了一种在线方法，用于在低自相关二进制序列问题中对搜索空间区域进行优先级排序，其中在搜索过程中动态分配计算工作。
- •我们开发了一种新颖的算法，该算法融合了所提出的优先级策略。
- •我们报告了几个序列长度的新的最佳已知解。
- •我们展示了优值因子超过8.0的最长二进制序列。

本文的其余部分组织如下。我们首先回顾相关工作以及低自相关二进制序列的背景。随后介绍所提出的搜索空间区域优先级排序方法和相应的算法。然后报告实验结果，包括改进的最佳已知解和新获得的优值因子超过8.0的序列。本文最后总结研究结果并讨论未来研究方向。

## 相关工作

寻找最优序列S∗仅在较短长度下计算可行；然而，文献中提出了几种方法。在[31 (https://arxiv.org/html/2607.09688#bib.bib32)]中，作者引入了一种分支定界算法，系统地探索解空间。为了减少其大小，他们基于对称规则固定了最左边的m个元素和最右边的m个元素。能量函数的下界通过松弛获得，考虑了固定和自由元素之间的相互作用。这种方法使得能够计算出直到L≤44的最优序列，估计时间复杂度为O(1.85L)。[31]中下界的质量取决于中心L−2m个自由元素的随机赋值。为了解决这个问题，[36 (https://arxiv.org/html/2607.09688#bib.bib34)]引入了自由乘积的概念，其中仅当两个元素都未被固定时才考虑项。这个想法在[35 (https://arxiv.org/html/2607.09688#bib.bib35)]中通过合并固定与自由元素之间的附加相互作用而得到完善，将复杂度降低到O(1.80L)。在[46 (https://arxiv.org/html/2607.09688#bib.bib36)]中，观察到共轭一个序列元素会将能量和改变±4，从而产生更紧的下界。最后，[33 (https://arxiv.org/html/2607.09688#bib.bib31)]引入了组合下界，进一步将效率提高到O(1.729L)。还推导出了精确下界；然而，它并未在