Prioritizing Search Space Regions in the Low Autocorrelation Binary Sequences Problem

Technische Samenvatting: Prioritering van Zoekruimtegebieden in het Low Autocorrelation Binary Sequences Probleem

Probleemdefinitie
Het Low Autocorrelation Binary Sequences (LABS) probleem is een uitdagende combinatorische optimalisatietaak gericht op het vinden van binaire sequenties $S = \{s_1, \dots, s_L\}$ waarbij $s_i \in \{+1, -1\}$ die de som van gekwadrateerde aperiodieke autocorrelaties minimaliseren. Het doel is om de merit factor $F$ te maximaliseren, gedefinieerd als $F(S) = L^2 / 2E(S)$, waarbij $E(S)$ de energie van de sequentie is. De zoekruimte groeit exponentieel ($2^L$) en wordt gekenmerkt door een ruig landschap met talrijke lokale minima en zeldzame, geïsoleerde globale minima. Skew-symmetrische sequenties (waarbij $s_{k+1+i} = (-1)^i s_{k+1-i}$) verminderen de zoekruimte en elimineren oneven verschuivingsautocorrelaties, maar het vinden van optimale sequenties voor grote $L$ blijft computationeel onuitvoerbaar voor exhaustieve methoden.

Methodologie
De auteurs stellen een hybride zoekframework voor, TS-SAW, dat online besluitvorming integreert met parallelle stochastische zoektochten om computationele middelen dynamisch toe te wijzen over de LABS-zoekruimte. De methodologie bestaat uit drie kerncomponenten:

1. Thompson Sampling voor Partitie-prioritering:
   De zoekruimte wordt opgedeeld in disjuncte regio's genaamd "restrictieklassen" of partities, gedefinieerd door de eerste $p$ elementen van de sequentie vast te leggen. Deze partities worden gemodelleerd als "armen" in een multi-armed bandit probleem. In plaats van te vertrouwen op statische heuristieken (zoals potentiewaarden) om partities te rangschikken, gebruiken de auteurs Thompson sampling om partities adaptief te selecteren.

   • Elke partitie $k$ is geassocieerd met een onbekende parameter $\theta_k$ die de verwachte merit factor van de partitie vertegenwoordigt.
   • Een Beta-distributie $Beta(\alpha_k, \beta_k)$ dient als de prior voor $\theta_k$.
   • Het algoritme gebruikt Fractional Thompson Sampling om continue beloningen (genormaliseerde merit factoren) te verwerken. Nadat een zoektocht op een partitie een beloning $r_t \in [0, 1]$ oplevert, worden de parameters bijgewerkt als $(\alpha_k, \beta_k) \leftarrow (\alpha_k + r_t, \beta_k + 1 - r_t)$.
   • Dit mechanisme verschuift de computationele inspanning dynamisch naar partities die empirisch hogere merit factoren opleveren, terwijl de exploratie van minder bemonsterde regio's behouden blijft.

2. Parallelle Self-Avoiding Walks (SAW) op GPU:
   Zodra een partitie is geselecteerd, voert het algoritme een self-avoiding walk uit om de sequentie binnen deze beperkte ruimte te optimaliseren.

   • Implementatie: De walks worden parallel uitgevoerd op NVIDIA GPU's (CUDA). Elke walk opereert als een onafhankelijke agent binnen een CUDA-block.
   • Cycluspreventie: Om te voorkomen dat staten opnieuw worden bezocht zonder excessief geheugengebruik, slaat een Bloom filter hashes van bezochte sequenties op.
   • Efficiëntie: De buurt-evaluatie maakt gebruik van lineaire-tijd flip-operaties voor skew-symmetrische sequenties, wat zorgt voor een laag geheugenvoetafdruk en een hoge doorvoer.
   • Gedeeld Leren: Hoewel de walks parallel draaien, delen ze een globale posterieure overtuiging ($\alpha_k, \beta_k$) die na elke batch walks wordt bijgewerkt, wat het leerproces versnelt.

3. Tweestaps Optimalisatiepipeline:
   Het framework hanteert een tweestapsstrategie om oplossingen te verfijnen:

   • Fase 1 (Beperkt): Parallelle SAWs verkennen de gepartitioneerde skew-symmetrische zoekruimte. De top $m$ kandidaten (geselecteerd via het quickselect-algoritme) worden doorgegeven aan de volgende fase.
   • Fase 2 (Onbeperkt): Deze kandidaten ondergaan verdere verfijning in de onbeperkte zoekruimte. Deze fase verwijdert de skew-symmetrie en de partitiebeperkingen, waarbij een priority queue en sequentie-operatoren (rotaties en flips) worden gebruikt om een breder gebied te verkennen en de kwaliteit van de oplossing te verbeteren.
   • Sequentie-operatoren: Om evenlengte-sequenties te behandelen, past de methode operatoren toe om de geoptimaliseerde oneven-lengte sequenties te transformeren naar even-lengte varianten, die vervolgens terug naar de verfijningsfase worden gevoerd.

Belangrijkste Bijdragen

• Adaptieve Resource Allocatie: Een nieuwe online methode die Thompson sampling gebruikt om zoekruimtegebieden dynamisch te prioriteren, waarmee men verder gaat dan statische heuristische rangschikkingen.
• Hybride Algoritme (TS-SAW): Een nieuw algoritme dat multi-armed bandit besluitvorming combineert met GPU-versnelde parallelle self-avoiding walks.
• Schaalbare Architectuur: Een tweestaps pipeline die massale parallelliteit benut voor initiële exploratie en onbeperkte verfijning voor de uiteindelijke optimalisatie.
• Nieuwe Best-Known Solutions: De generatie van nieuwe record-sequenties voor 35 verschillende lengtes in het bereik $450 \le L \le 527$ en voor $L = 573$.

Experimentele Resultaten
Experimenten werden uitgevoerd op de Vega supercomputer met NVIDIA A100 GPU's. De methode werd getest op binaire sequenties met lengtes $450 \le L \le 527$ en $L = 573$, waarbij 100.000 iteraties werden uitgevoerd voor de initiële fase.

• Verbeteringen in Merit Factor: De voorgestelde methode verbeterde de eerder bekende beste merit factoren voor alle 35 geteste lengtes. De gemiddelde toename in de merit factor over de verbeterde sequenties was 0,1967.
• Recordbrekend:
  • Voor $L = 451$ bereikte de methode een merit factor van $F = 8,0555$, waarmee de vorige beste met 0,8248 werd overtroffen. Dit wordt gerapporteerd als de langste sequentie in de literatuur met een merit factor boven de 8,0.
  • Voor $L = 573$ werd de merit factor met 0,2564 verbeterd, wat de langste bekende sequentie met $F > 7,0$ vertegenwoordigt.
• Partitie-analyse: Een experiment met $L=461$ toonde aan dat Thompson sampling effectief hoogpresterende partities identificeert. Het algoritme verschoof de focus weg van partities met een hoge theoretische "genormaliseerde potentie" naar partities die empirisch betere resultaten produceerden, wat de waarde van data-gestuurde allocatie boven statische heuristieken bevestigt.

Betekenis en Claims
Het artikel claimt dat het voorgestelde framework een schaalbare en effectieve strategie biedt voor het maximaliseren van merit factoren in het LABS-probleem. Door probabilistische besluitvorming te integreren met high-performance parallel computing, slaagt de aanpak erin de balans te vinden tussen exploratie en exploitatie in een zeer ruige zoekruimte. De auteurs stellen dat hoewel verbeteringen steeds moeilijker worden naarmate de sequentielengte groeit, hun data-gestuurde, partitie-gestuurde stochastische optimalisatie een veelbelovende richting blijft voor het verbeteren van de state-of-the-art. De resultaten valideren dat online, adaptieve resource allocatie superieur is aan statische heuristische prioritering voor deze klasse van combinatorische problemen. De auteurs concluderen dat dit framework een pad biedt naar adaptieve zoekstrategieën voor andere complexe combinatorische optimalisatieproblemen waarbij de zoekruimte zinvol kan worden gepartitioneerd.