Prioritizing Search Space Regions in the Low Autocorrelation Binary Sequences Problem

Resumo Técnico: Priorização de Regiões do Espaço de Busca no Problema das Sequências Binárias de Baixa Autocorrelação

Definição do Problema
O problema das Sequências Binárias de Baixa Autocorrelação (LABS) é uma tarefa de otimização combinatória desafiadora que visa encontrar sequências binárias $S = \{s_1, \dots, s_L\}$, onde $s_i \in \{+1, -1\}$, que minimizam a soma dos quadrados das autocorrelações aperiódicas. O objetivo é maximizar o fator de mérito $F$, definido como $F(S) = L^2 / 2E(S)$, onde $E(S)$ é a energia da sequência. O espaço de busca cresce exponencialmente ($2^L$), caracterizado por um cenário acidentado com inúmeros mínimos locais e mínimos globais raros e isolados. Embora sequências de simetria óssea (onde $s_{k+1+i} = (-1)^i s_{k+1-i}$) reduzam o espaço de busca e eliminem autocorrelações de deslocamento ímpar, encontrar sequências ótimas para $L$ grandes permanece computacionalmente intratável para métodos exaustivos.

Metodologia
Os autores propõem um framework de busca híbrido, TS-SAW, que integra a tomada de decisão online com busca estocástica paralela para alocar dinamicamente recursos computacionais através do espaço de busca LABS. A metodologia consiste em três componentes principais:

1. Amostragem de Thompson para Priorização de Partições:
   O espaço de busca é decomposto em regiões disjuntas chamadas classes de restrição ou partições, definidas pelo fixamento dos primeiros $p$ elementos da sequência. Essas partições são modeladas como "braços" em um problema de bandit multi-braços (multi-armed bandit). Em vez de depender de heurísticas estáticas (como valores de potencial) para classificar as partições, os autores empregam amostragem de Thompson para selecionar partições de forma adaptativa.

   • Cada partição $k$ está associada a um parâmetro desconhecido $\theta_k$ que representa seu fator de mérito esperado.
   • Uma distribuição Beta $Beta(\alpha_k, \beta_k)$ serve como a priori para $\theta_k$.
   • O algoritmo utiliza Amostragem de Thompson Fracionária para lidar com recompensas contínuas (fatores de mérito normalizados). Após uma busca em uma partição gerar uma recompensa $r_t \in [0, 1]$, os parâmetros são atualizados como $(\alpha_k, \beta_k) \leftarrow (\alpha_k + r_t, \beta_k + 1 - r_t)$.
   • Este mecanismo desloca dinamicamente o esforço computacional para as partições que empiricamente produzem fatores de mérito mais altos, mantendo ao mesmo mesmo tempo a exploração de regiões menos amostradas.

2. Caminhadas Auto-Evitantes (SAW) Paralelas em GPU:
   Uma vez selecionada uma partição, o algoritmo realiza uma caminhada auto-evitante para otimizar a sequência dentro desse espaço restrito.

   • Implementação: As caminhadas são executadas em paralelo em GPUs NVIDIA (CUDA). Cada caminhada opera como um agente independente dentro de um bloco CUDA.
   • Prevenção de Ciclos: Para evitar a revisitação de estados sem uso excessivo de memória, um filtro de Bloom armazena os hashes das sequências visitadas.
   • Eficiência: A avaliação de vizinhança utiliza operações de inversão (flip) de tempo linear para sequências de simetria óssea, garantindo baixa pegada de memória e alto rendimento (throughput).
   • Aprendizado Compartilhado: Embora as caminhadas rodem em paralelo, elas compartilham uma crença posterior global ($\alpha_k, \beta_k$) que é atualizada após cada lote de caminhadas, acelerando o processo de aprendizado.

3. Pipeline de Otimização de Dois Estágios:
   O framework emprega uma estratégia de dois passos para refinar as soluções:

   • Estágio 1 (Restrito): SAWs paralelas exploram o espaço de busca de simetria óssea particionado. Os $m$ melhores candidatos (selecionados via algoritmo quickselect) são passados para o próximo estágio.
   • Estágio 2 (Não Restrito): Esses candidatos passam por um refinamento adicional no espaço de busca não restrito. Este estágio remove a simetria óssea e as restrições de partição, utilizando uma fila de prioridade e operadores de sequência (rotações e inversões) para explorar uma região mais ampla e melhorar a qualidade da solução.
   • Operadores de Sequência: Para lidar com sequências de comprimento par, o método aplica operadores para transformar sequências de comprimento ímpar otimizadas em variantes de comprimento par, que são então alimentadas de volta para o estágio de refinamento.

Principais Contribuições

• Alocação Adaptativa de Recursos: Um novo método online que usa amostragem de Thompson para priorizar regiões do espaço de busca dinamicamente, indo além de classificações heurísticas estáticas.
• Algoritmo Híbrido (TS-SAW): Um novo algoritmo que combina a tomada de decisão de bandit multi-braços com caminhadas auto-evitantes paralelas aceleradas por GPU.
• Arquitetura Escalável: Um pipeline de dois estágios que aproveita o paralelismo massivo para a exploração inicial e o refinamento não restrito para a otimização final.
• Novas Melhores Soluções Conhecidas: A geração de novas sequências recordistas para 35 comprimentos distintos no intervalo $450 \le L \le 527$ e para $L = 573$.

Resultados Experimentais
Os experimentos foram conduzidos no supercomputador Vega usando GPUs NVIDIA A100. O método foi testado em sequências binárias com comprimentos $450 \le L \le 527$ e $L = 573$, executando 100.000 iterações para a fase inicial.

• Melhorias no Fator de Mérito: O método proposto melhorou os fatores de mérito anteriormente conhecidos para todos os 35 comprimentos testados. O aumento médio no fator de mérito entre as sequências melhoradas foi de 0,1967.
• Quebra de Recordes:
  • Para $L = 451$, o método alcançou um fator de mérito de $F = 8,0555$, superando o melhor anterior em 0,8248. Isso é relatado como a sequência mais longa na literatura com um fator de mérito superior a 8,0.
  • Para $L = 573$, o fator de mérito foi melhorado em 0,2564, representando a sequência mais longa conhecida com $F > 7,0$.
• Análise de Partição: Um experimento com $L=461$ demonstrou que a amostragem de Thompson identifica efetivamente partições de alto desempenho. O algoritmo deslocou o foco de partições com alto "potencial normalizado" teórico para aquelas que produziram resultados melhores empiricamente, confirmando o valor da alocação baseada em dados sobre heurísticas estáticas.

Significância e Alegações
O artigo alega que o framework proposto fornece uma estratégia escalável e eficaz para maximizar os fatores de mérito no problema LABS. Ao integrar a tomada de decisão probabilística com computação paralela de alto desempenho, a abordagem equilibra com sucesso a exploração e a explotação em um cenário altamente acidentado. Os autores afirmam que, embora as melhorias tornem-se cada vez mais difíceis conforme o comprimento da sequência cresce, sua otimização estocástica guiada por partições e baseada em dados continua sendo uma direção promissora para o avanço do estado da arte. Os resultados validam que a alocação de recursos online e adaptativa é superior à priorização heurística estática para esta classe de problemas de otimização combinatória. Os autores concluem que este framework oferece um caminho para estratégias de busca adaptativas para outros problemas de otimização combinatória difíceis onde o espaço de busca pode ser significativamente particionado.