Prioritizing Search Space Regions in the Low Autocorrelation Binary Sequences Problem

Technical Summary: Prioritizing Search Space Regions in the Low Autocorrelation Binary Sequences Problem

Problem Definition
The Low Autocorrelation Binary Sequences (LABS) problem is a challenging combinatorial optimization task aimed at finding binary sequences $S = \{s_1, \dots, s_L\}$ where $s_i \in \{+1, -1\}$ that minimize the sum of squared aperiodic autocorrelations. The objective is to maximize the merit factor $F$, defined as $F(S) = L^2 / 2E(S)$, where $E(S)$ is the sequence energy. The search space grows exponentially ($2^L$), characterized by a rugged landscape with numerous local minima and rare, isolated global minima. While skew-symmetric sequences (where $s_{k+1+i} = (-1)^i s_{k+1-i}$) reduce the search space and eliminate odd-shift autocorrelations, finding optimal sequences for large $L$ remains computationally intractable for exhaustive methods.

Methodology
The authors propose a hybrid search framework, TS-SAW, which integrates online decision-making with parallel stochastic search to dynamically allocate computational resources across the LABS search space. The methodology consists of three core components:

1. Thompson Sampling for Partition Prioritization:
   The search space is decomposed into disjoint regions called "restriction classes" or partitions, defined by fixing the first $p$ elements of the sequence. These partitions are modeled as "arms" in a multi-armed bandit problem. Instead of relying on static heuristics (like potential values) to rank partitions, the authors employ Thompson sampling to adaptively select partitions.

   • Each partition $k$ is associated with an unknown parameter $\theta_k$ representing its expected merit factor.
   • A Beta distribution $Beta(\alpha_k, \beta_k)$ serves as the prior for $\theta_k$.
   • The algorithm uses Fractional Thompson Sampling to handle continuous rewards (normalized merit factors). After a search on a partition yields a reward $r_t \in [0, 1]$, the parameters are updated as $(\alpha_k, \beta_k) \leftarrow (\alpha_k + r_t, \beta_k + 1 - r_t)$.
   • This mechanism dynamically shifts computational effort toward partitions that empirically yield higher merit factors while maintaining exploration of less-sampled regions.

2. Parallel Self-Avoiding Walks (SAW) on GPU:
   Once a partition is selected, the algorithm performs a self-avoiding walk to optimize the sequence within that restricted space.

   • Implementation: The walks are executed in parallel on NVIDIA GPUs (CUDA). Each walk operates as an independent agent within a CUDA block.
   • Cycle Prevention: To prevent revisiting states without excessive memory usage, a Bloom filter stores hashes of visited sequences.
   • Efficiency: The neighborhood evaluation uses linear-time flip operations for skew-symmetric sequences, ensuring low memory footprint and high throughput.
   • Shared Learning: While walks run in parallel, they share a global posterior belief ($\alpha_k, \beta_k$) which is updated after each batch of walks, accelerating the learning process.

3. Two-Stage Optimization Pipeline:
   The framework employs a two-step strategy to refine solutions:

   • Stage 1 (Constrained): Parallel SAWs explore the partitioned skew-symmetric search space. The top $m$ candidates (selected via the quickselect algorithm) are passed to the next stage.
   • Stage 2 (Unconstrained): These candidates undergo further refinement in the unrestricted search space. This stage removes skew-symmetry and partition constraints, utilizing a priority queue and sequence operators (rotations and flips) to explore a broader region and improve solution quality.
   • Sequence Operators: To handle even-length sequences, the method applies operators to transform optimized odd-length sequences into even-length variants, which are then fed back into the refinement stage.

Key Contributions

• Adaptive Resource Allocation: A novel online method that uses Thompson sampling to prioritize search space regions dynamically, moving beyond static heuristic rankings.
• Hybrid Algorithm (TS-SAW): A new algorithm combining multi-armed bandit decision-making with GPU-accelerated parallel self-avoiding walks.
• Scalable Architecture: A two-stage pipeline that leverages massive parallelism for initial exploration and unconstrained refinement for final optimization.
• New Best-Known Solutions: The generation of new record sequences for 35 distinct lengths in the range $450 \le L \le 527$ and for $L = 573$.

Experimental Results
Experiments were conducted on the Vega supercomputer using NVIDIA A100 GPUs. The method was tested on binary sequences with lengths $450 \le L \le 527$ and $L = 573$, running 100,000 iterations for the initial phase.

• Merit Factor Improvements: The proposed method improved the previously best-known merit factors for all 35 tested lengths. The mean increase in merit factor across improved sequences was 0.1967.
• Record Breaking:
  • For $L = 451$, the method achieved a merit factor of $F = 8.0555$, surpassing the previous best by 0.8248. This is reported as the longest sequence in the literature with a merit factor exceeding 8.0.
  • For $L = 573$, the merit factor was improved by 0.2564, representing the longest known sequence with $F > 7.0$.
• Partition Analysis: An experiment with $L=461$ demonstrated that Thompson sampling effectively identifies high-performing partitions. The algorithm shifted focus away from partitions with high theoretical "normalized potential" toward those that empirically produced better results, confirming the value of data-driven allocation over static heuristics.

Significance and Claims
The paper claims that the proposed framework provides a scalable and effective strategy for maximizing merit factors in the LABS problem. By integrating probabilistic decision-making with high-performance parallel computing, the approach successfully balances exploration and exploitation in a highly rugged search space. The authors assert that while improvements become increasingly difficult as sequence length grows, their data-driven, partition-guided stochastic optimization remains a promising direction for advancing the state-of-the-art. The results validate that online, adaptive resource allocation is superior to static heuristic prioritization for this class of combinatorial problems. The authors conclude that this framework offers a pathway toward adaptive search strategies for other difficult combinatorial optimization problems where the search space can be meaningfully partitioned.