Prioritizing Search Space Regions in the Low Autocorrelation Binary Sequences Problem

Resumen Técnico: Priorización de Regiones del Espacio de Búsqueda en el Problema de las Secuencias Binarias de Baja Autocorrelación

Definición del Problema
El problema de las Secuencias Binarias de Baja Autocorrelación (LABS) es una tarea de optimización combinatoria desafiante que busca encontrar secuencias binarias $S = \{s_1, \dots, s_L\}$ donde $s_i \in \{+1, -1\}$ que minimicen la suma de los cuadrados de las autocorrelaciones aperiódicas. El objetivo es maximizar el factor de mérito $F$, definido como $F(S) = L^2 / 2E(S)$, donde $E(S)$ es la energía de la secuencia. El espacio de búsqueda crece exponencialmente ($2^L$), caracterizado por un paisaje accidentado con numerosos mínimos locales y mínimos globales raros y aislados. Las secuencias de simetría sesgada (donde $s_{k+1+i} = (-1)^i s_{k+1-i}$) reducen el espacio de búsqueda y eliminan las autocorrelaciones de desplazamiento impar, pero encontrar secuencias óptimas para valores grandes de $L$ sigue siendo computacionalmente intratable para los métodos exhaustivos.

Metodología
Los autores proponen un marco de búsqueda híbrido, TS-SAW, que integra la toma de decisiones en línea con la búsqueda estocástica paralela para asignar dinámicamente los recursos computacionales a través del espacio de búsqueda de LABS. La metodología consta de tres componentes principales:

1. Muestreo de Thompson para la Priorización de Particiones:
   El espacio de búsqueda se descompone en regiones disjuntas llamadas "clases de restricción" o particiones, definidas por fijar los primeros $p$ elementos de la secuencia. Estas particiones se modelan como "brazos" en un problema de bandidos multibrazo (multi-armed bandit). En lugar de depender de heurísticas estáticas (como los valores de potencial) para clasificar las particiones, los autores emplean muestreo de Thompson para seleccionar particiones de forma adaptativa.

   • Cada partición $k$ está asociada con un parámetro desconocido $\theta_k$ que representa su factor de mérito esperado.
   • Una distribución Beta $Beta(\alpha_k, \beta_k)$ sirve como la distribución a priori para $\theta_k$.
   • El algoritmo utiliza Muestreo de Thompson Fraccionario para manejar recompensas continuas (factores de mérito normalizados). Después de que una búsqueda en una partición produce una recompensa $r_t \in [0, 1]$, los parámetros se actualizan como $(\alpha_k, \beta_k) \leftarrow (\alpha_k + r_t, \beta_k + 1 - r_t)$.
   • Este mecanismo desplaza dinámicamente el esfuerzo computacional hacia las particiones que empíricamente producen mayores factores de mérito, manteniendo al mismo tiempo la exploración de las regiones menos muestreadas.

2. Caminatas Autoevitantes (SAW) Paralelas en GPU:
   Una vez seleccionada una partición, el algoritmo realiza una caminata autoevitante para optimizar la secuencia dentro de ese espacio restringido.

   • Implementación: Las caminatas se ejecutan en paralelo en GPUs NVIDIA (CUDA). Cada caminata opera como un agente independiente dentro de un bloque CUDA.
   • Prevención de Ciclos: Para evitar la revisión de estados sin un uso excesivo de memoria, un filtro de Bloom almacena los hashes de las secuencias visitadas.
   • Eficiencia: La evaluación del vecindario utiliza operaciones de inversión (flip) de tiempo lineal para secuencias de simetría sesgada, asegurando una baja huella de memoria y un alto rendimiento.
   • Aprendizaje Compartido: Aunque las caminatas se ejecutan en paralelo, comparten una creencia posterior global ($\alpha_k, \beta_k$), la cual se actualiza después de cada lote de caminatas, acelerando el proceso de aprendizaje.

3. Pipeline de Optimización de Dos Etapas:
   El marco emplea una estrategia de dos pasos para refinar las soluciones:

   • Etapa 1 (Restringida): Las SAWs paralelas exploran el espacio de búsqueda de simetría sesgada particionado. Los $m$ mejores candidatos (seleccionados mediante el algoritmo quickselect) se pasan a la siguiente etapa.
   • Etapa 2 (No Restringida): Estos candidatos se someten a un mayor refinamiento en el espacio de búsqueda no restringido. Esta etapa elimina la simetría sesgada y las restricciones de partición, utilizando una cola de prioridad y operadores de secuencia (rotaciones e inversiones) para explorar una región más amplia y mejorar la calidad de la solución.
   • Operadores de Secuencia: Para manejar secuencias de longitud par, el método aplica operadores para transformar secuencias optimizadas de longitud impar en variantes de longitud par, las cuales son enviadas de vuelta a la etapa de refinamiento.

Contribuciones Clave

• Asignación Adaptativa de Recursos: Un nuevo método en línea que utiliza el muestreo de Thompson para priorizar las regiones del espacio de búsqueda de forma dinámica, yendo más allá de las clasificaciones heurísticas estáticas.
• Algoritmo Híbrido (TS-SAW): Un nuevo algoritmo que combina la toma de decisiones de bandidos multibrazo con caminatas autoevitantes paralelas aceleradas por GPU.
• Arquitectura Escalable: Un pipeline de dos etapas que aprovecha el paralelismo masivo para la exploración inicial y el refinamiento no restringido para la optimización final.
• Nuevas Mejores Soluciones Conocidas: La generación de nuevas secuencias récord para 35 longitudes distintas en el rango $450 \le L \le 527$ y para $L = 573$.

Resultados Experimentales
Los experimentos se realizaron en la supercomputadora Vega utilizando GPUs NVIDIA A100. El método se probó con secuencias binarias de longitudes $450 \le L \le 527$ y $L = 573$, ejecutando 100,000 iteraciones para la fase inicial.

• Mejoras en el Factor de Mérito: El método propuesto mejoró los factores de mérito previamente conocidos para todas las 35 longitudes probadas. El incremento medio del factor de mérito en las secuencias mejoradas fue de 0.1967.
• Récords:
  • Para $L = 451$, el método alcanzó un factor de mérito de $F = 8.0555$, superando el mejor anterior por 0.8248. Esto se reporta como la secuencia más larga en la literatura con un factor de mérito superior a 8.0.
  • Para $L = 573$, el factor de mérito se mejoró en 0.2564, representando la secuencia más larga conocida con $F > 7.0$.
• Análisis de Particiones: Un experimento con $L=461$ demostró que el muestreo de Thompson identifica eficazmente las particiones de alto rendimiento. El algoritmo desplazó el enfoque de las particiones con un alto "potencial normalizado" teórico hacia aquellas que produjeron mejores resultados empíricos, confirmando el valor de la asignación basada en datos sobre las heurísticas estáticas.

Significancia y Reivindicaciones
El artículo afirma que el marco propuesto proporciona una estrategia escalable y efectiva para maximizar los factores de mérito en el problema LABS. Al integrar la toma de decisiones probabilística con la computación paralela de alto rendimiento, el enfoque equilibra con éxito la exploración y la explotación en un espacio de búsqueda altamente accidentado. Los autores sostienen que, si bien las mejoras se vuelven cada vez más difíciles a medida que aumenta la longitud de la secuencia, su optimización estocástica guiada por particiones y basada en datos sigue siendo una dirección prometedora para avanzar en el estado del arte. Los resultados validan que la asignación de recursos en línea y adaptativa es superior a la priorización heurística estática para esta clase de problemas de optimización combinatoria. Los autores concluyen que este marco ofrece una vía hacia estrategias de búsqueda adaptativas para otros problemas de optimización combinatoria difíciles donde el espacio de búsqueda puede ser significativamente particionado.