Prioritizing Search Space Regions in the Low Autocorrelation Binary Sequences Problem

Résumé Technique : Priorisation des Régions de l'Espace de Recherche dans le Problème des Séquences Binaires à Faible Autocorrélation

Définition du Problème
Le problème des séquences binaires à faible autocorrélation (LABS) est une tâche d'optimisation combinatoire complexe visant à trouver des séquences binaires $S = \{s_1, \dots, s_L\}$ où $s_i \in \{+1, -1\}$ qui minimisent la somme des carrés des autocorrélations apériodiques. L'objectif est de maximiser le facteur de mérite $F$, défini par $F(S) = L^2 / 2E(S)$, où $E(S)$ est l'énergie de la séquence. L'espace de recherche croît de manière exponentielle ($2^L$), caractérisé par un paysage accidenté comportant de nombreux minima locaux et des minima globaux rares et isolés. Les séquences antisymétriques (où $s_{k+1+i} = (-1)^i s_{k+1-i}$) réduisent l'espace de recherche et éliminent les autocorrélations de décalage impair, mais la recherche de séquences optimales pour de grandes valeurs de $L$ reste informatiquement intraitable pour les méthodes exhaustives.

Méthodologie
Les auteurs proposent un cadre de recherche hybride, TS-SAW, qui intègre la prise de décision en ligne avec une recherche stochastique parallèle pour allouer dynamiquement les ressources de calcul à travers l'espace de recherche LABS. La méthodologie se compose de trois composantes centrales :

1. Échantillonnage de Thompson pour la Priorisation des Partitions :
   L'espace de recherche est décomposé en régions disjointes appelées « classes de restriction » ou partitions, définies en fixant les $p$ premiers éléments de la séquence. Ces partitions sont modélisées comme des « bras » d'un problème de bandit multi-bras. Au lieu de s'appuyer sur des heuristiques statiques (comme les valeurs de potentiel) pour classer les partitions, les auteurs utilisent l'échantillonnage de Thompson pour sélectionner de manière adaptative les partitions.

   • Chaque partition $k$ est associée à un paramètre inconnu $\theta_k$ représentant son facteur de mérite attendu.
   • Une distribution Beta $Beta(\alpha_k, \beta_k)$ sert de priorité pour $\theta_k$.
   • L'algorithme utilise l'échantillonnage de Thompson fractionnaire pour gérer les récompenses continues (facteurs de mérite normalisés). Après qu'une recherche sur une partition produit une récompense $r_t \in [0, 1]$, les paramètres sont mis à jour selon $(\alpha_k, \beta_k) \leftarrow (\alpha_k + r_t, \beta_k + 1 - r_t)$.
   • Ce mécanisme déplace dynamiquement l'effort de calcul vers les partitions qui produisent empiriquement des facteurs de mérite plus élevés, tout en maintenant l'exploration des régions moins échantillonnées.

2. Marches Aléatoires Auto-Évitantes (SAW) Parallèles sur GPU :
   Une fois une partition sélectionnée, l'algorithme effectue une marche aléatoire auto-évitante pour optimiser la séquence au sein de cet espace restreint.

   • Implémentation : Les marches sont exécutées en parallèle sur des GPU NVIDIA (CUDA). Chaque marche opère comme un agent indépendant au sein d'un bloc CUDA.
   • Prévention des Cycles : Pour éviter de revisiter des états sans consommation excessive de mémoire, un filtre de Bloom stocke les empreintes (hashes) des séquences visitées.
   • Efficacité : L'évaluation du voisinage utilise des opérations de basculement (flip) en temps linéaire pour les séquences antisymétriques, garantissant une faible empreinte mémoire et un débit élevé.
   • Apprentissage Partagé : Bien que les marches s'exécutent en parallèle, elles partagent une croyance postérieure globale ($\alpha_k, \beta_k$) qui est mise à jour après chaque lot de marches, accélérant ainsi le processus d'apprentissage.

3. Pipeline d'Optimisation en Deux Étapes :
   Le cadre emploie une stratégie en deux étapes pour affiner les solutions :

   • Étape 1 (Contrainte) : Des SAWs parallèles explorent l'espace de recherche antisymétrique partitionné. Les $m$ meilleurs candidats (sélectionnés via l'algorithme quickselect) sont transmis à l'étape suivante.
   • Étape 2 (Non Contrainte) : Ces candidats subissent un affinement supplémentaire dans l'espace de recherche non restreint. Cette étape supprime l'antisymétrie et les contraintes de partition, utilisant une file de priorité et des opérateurs de séquence (rotations et basculements) pour explorer une région plus large et améliorer la qualité de la solution.
   • Opérateurs de Séquence : Pour gérer les séquences de longueur paire, la méthode applique des opérateurs pour transformer les séquences optimisées de longueur impaire en variantes de longueur paire, qui sont ensuite réinjectées dans l'étape d'affinement.

Contributions Clés

• Allocation Adaptative des Ressources : Une nouvelle méthode en ligne qui utilise l'échantillonnage de Thompson pour prioriser dynamiquement les régions de l'espace de recherche, dépassant les classements heuristiques statiques.
• Algorithme Hybride (TS-SAW) : Un nouvel algorithme combinant la prise de décision de type bandit multi-bras avec des marches aléatoires auto-évitantes parallèles accélérées par GPU.
• Architecture Évolutive : Un pipeline en deux étapes qui exploite le parallélisme massif pour l'exploration initiale et l'affinement non contraint pour l'optimisation finale.
• Nouveaux Records de Solutions : La génération de nouvelles séquences records pour 35 longueurs distinctes dans la plage $450 \le L \le 527$ et pour $L = 573$.

Résultats Expérimentaux
Les expériences ont été menées sur le supercalculateur Vega utilisant des GPU NVIDIA A100. La méthode a été testée sur des séquences binaires de longueurs $450 \le L \le 527$ et $L = 573$, avec 100 000 itérations pour la phase initiale.

• Améliorations du Facteur de Mérite : La méthode proposée a amélioré les facteurs de mérite précédemment connus pour les 35 longueurs testées. L'augmentation moyenne du facteur de mérite sur les séquences améliorées est de 0,1967.
• Records :
  • Pour $L = 451$, la méthode a atteint un facteur de mérite de $F = 8,0555$, dépassant le précédent record de 0,8248. C'est la séquence la plus longue rapportée dans la littérature avec un facteur de mérite supérieur à 8,0.
  • Pour $L = 573$, le facteur de mérite a été amélioré de 0,2564, représentant la plus longue séquence connue avec $F > 7,0$.
• Analyse des Partitions : Une expérience avec $L=461$ a démontré que l'échantillonnage de Thompson identifie efficacement les partitions performantes. L'algorithme a détourné l'attention des partitions ayant un haut « potentiel normalisé » théorique vers celles qui produisaient empiriquement de meilleurs résultats, confirmant la valeur de l'allocation basée sur les données par rapport aux heuristiques statiques.

Signification et Revendications
L'article affirme que le cadre proposé constitue une stratégie évolutive et efficace pour maximiser les facteurs de mérite dans le problème LABS. En intégrant la prise de décision probabiliste à l'informatique parallèle de haute performance, l'approche parvient à équilibrer l'exploration et l'exploitation dans un espace de recherche hautement accidenté. Les auteurs soutiennent que, bien que les améliorations deviennent de plus en plus difficiles à mesure que la longueur de la séquence augmente, l'optimisation stochastique guidée par les partitions et les données est une direction prometteuse pour faire progresser l'état de l'art. Les résultats valident qu'une allocation de ressources adaptative en ligne est supérieure à la priorisation heuristique statique pour cette classe de problèmes d'optimisation combinatoire. Les auteurs concluent que ce cadre offre une voie vers des stratégies de recherche adaptatives pour d'autres problèmes d'optimisation combinatoire difficiles où l'espace de recherche peut être meaningfulement partitionné.