🤖 machine learning

Prioritizing Search Space Regions in the Low Autocorrelation Binary Sequences Problem

Dieses Paper stellt ein hybrides Suchframework vor, das Thompson-Sampling mit parallelen selbstvermeidenden Random Walks und GPU-Beschleunigung kombiniert, um Rechenressourcen adaptiv über den LABS-Suchraum zu verteilen, wobei erfolgreich die bisher besten Ergebnisse für 35 Sequenzlängen verbessert und eine neue längste Sequenz mit einem Merit-Faktor von über 8,0 entdeckt wurde.

Ursprüngliche Autoren: Blaž Pšeničnik, Borko Bošković, Jan Popić, Janez Brest

Veröffentlicht 2026-07-14

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Blaž Pšeničnik, Borko Bošković, Jan Popić, Janez Brest

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, die einzige, perfekte Kombination für ein riesiges, kosmisches Schloss zu finden. Dieses Schloss besteht aus einer langen Kette von Schaltern, von denen jeder entweder auf „Oben“ (+1) oder „Unten“ (-1) gestellt werden kann. Das Ziel? Die Schalter so anzuordnen, dass das Muster nicht versehentlich wie sich selbst aussieht, wenn man es ein Stück nach links oder rechts verschiebt. In der realen Welt wird dies als das Problem der Low Autocorrelation Binary Sequences (LABS) bezeichnet, und es ist das Geheimrezept hinter Dingen wie Satellitennavigation und klaren Funksignalen.

Das Problem ist, dass die Anzahl der möglichen Schalterkombinationen so schnell wächst, dass sie zu einem Albtraum wird. Wenn man eine Kette von 500 Schaltern hat, ist die Anzahl der Möglichkeiten, diese anzuordnen, eine Zahl, die so gewaltig ist, dass die Sterne am Himmel im Vergleich dazu wie Staubkörner wirken. Die meisten Anordnungen sind schrecklicher „Lärm“, und die perfekten sind wie das Finden eines einzigen, winzigen Golflochs in einer Wüste, die so groß wie ein Kontinent ist.

Der alte Weg: Raten und Prüfen

Früher versuchten Wissenschaftler, dies zu lösen, indem sie die „Form“ der Schlüssellöcher des Schlosses untersuchten. Sie nutzten mathematische Regeln, um zu raten, welche Ausgangsmuster vielversprechend aussah. Es war, als würde man versuchen, eine Nadel im Heuhaufen zu finden, indem man nur nach den Nadeln sucht, die glänzend aussehen. Manchmal funktionierte das, aber oft verschwendete man Zeit mit glänzend aussehenden Nadeln, die sich letztlich als nutzlos herausstellten.

Die neue Strategie: Der schlaue Detektiv

Die Autoren dieser Arbeit, ein Team von der Universität Maribor, beschlossen, auf das Raten zu verzichten und stattdessen zu lernen. Sie bauten eine hybride Suchmaschine, die wie ein super-schlauer Detektiv unter Verwendung eines Tricks namens Thompson-Sampling agiert.

So arbeitet ihr Detektiv:

Teile und Herrsche: Anstatt die ganze Wüste auf einmal zu betrachten, teilen sie den Suchraum in verschiedene „Nachbarschaften“ (Partitionen) auf.
Der Multi-Armed Bandit: Stellen Sie sich eine Reihe von Spielautomaten (Arme) vor. Einige Maschinen zahlen große Jackpots aus (hochwertige Sequenzen), andere geben Ihnen nur ein paar Münzen. Der Detektiv weiß nicht, welche Maschine die Gewinnerin ist.
Lernen im laufenden Betrieb: Der Detektiv zieht einen Hebel (erforscht eine Nachbarschaft). Wenn dies gut bezahlt, wird der Detektiv begeistert und zieht den Hebel erneut. Wenn es ein Reinfall ist, zieht der Detektiv weiter. Aber hier liegt die Magie: Der Detektiv ist auch ein wenig neugierig. Er probiert gelegentlich die „langweiligen“ Maschinen aus, nur für den Fall, dass diese heimlich die besten sind. Dieses Gleichgewicht zwischen Exploitation (dorthin gehen, wo das Geld liegt) und Exploration (das Unbekannte prüfen) ist das Herzstück ihrer Methode.

Die Super-Speed-Engine

Um diesen Detektiv schnell genug nützlich zu machen, gab das Team ihm einen massiven Schub. Sie ließen tausende dieser „Detektiv-Wanderungen“ gleichzeitig auf leistungsstarken GPUs (denselben Chips, die für High-End-Videospiele verwendet werden) laufen. Sie verwendeten auch einen cleveren „Bloom-Filter“, was wie ein super-schneller Gedächtnistrick ist, der es dem Detektiv ermöglicht, sich jede bereits begangene Pfad zu merken, ohne ein riesiges Notizbuch zu benötigen, wodurch verhindert wird, dass er in Schleifen stecken bleibt.

Sie verwendeten auch eine Zweistufen-Strategie:

Stufe 1: Der Detektiv durchsucht eine eingeschränkte, leichter handhabbare Version des Schlosses (unter Verwendung von „schief-symmetrischen“ Regeln), um die besten Kandidaten zu finden.
Stufe 2: Die Top-Kandidaten werden dann in eine „Veredelungswerkstatt“ gebracht, in der die Regeln gelockert werden, was es dem Detektiv ermöglicht, die Sequenz frei zu manipulieren, um noch mehr Perfektion herauszupressen.

Die Ergebnisse: Rekorde brechen

Die Ergebnisse dieses Experiments sind beeindruckend. Das Team testete ihre Methode an binären Sequenzen mit Längen von 450 bis 527 sowie für eine Länge von 573.

Neue Rekorde: Sie fanden bessere Lösungen als je zuvor für 35 verschiedene Sequenzlängen in diesem Bereich.
Der Große Wurf: Die aufregendste Entdeckung war für eine Sequenz der Länge L = 451. Sie fanden eine Sequenz mit einem „Merit Factor“ (einem Wert dafür, wie gut die Sequenz ist) von 8,0555. Dies ist die längste bisher berichtete Sequenz, die einen Merit-Faktor von über 8,0 aufweist. Vorher war die längste solche Sequenz nur 309 lang.
Ein weiterer Meilenstein: Für die Länge L = 573 verbesserten sie den Wert auf 7,2774, was den höchsten jemals gefundenen Merit-Faktor (über 7,0) für eine Sequenz dieser Länge darstellt.

Was sie nicht getan haben (und warum das wichtig ist)

Es ist wichtig anzumerken, was dieses Paper nicht getan hat. Sie haben nicht behauptet, das LABS-Problem für jede mögliche Länge gelöst zu haben. Wie das Paper feststellt, wird die Landschaft mit zunehmender Länge der Sequenzen „immer zerklüfteter“, was bedeutet, dass Verbesserungen kleiner und schwerer zu finden werden. Sie haben keinen Quantencomputer benutzt, um das Problem zu lösen; sie nutzten klassische Computer (GPUs) mit einem intelligenten Algorithmus. Sie haben die Ergebnisse auch nicht nur simuliert; sie haben diese neuen Sequenzen tatsächlich generiert und verifiziert, indem sie die spezifischen binären Muster (im Hexadezimalformat) bereitstellten, damit andere sie überprüfen können.

Das Fazit

Dieses Paper legt nahe, dass, indem wir einen Computer lernen lassen, während er sucht – also dynamisch entscheidet, wo er seine Zeit verbringt, basierend auf dem, was er findet, anstatt einer starren Karte zu folgen –, wir einige der schwierigsten kombinatorischen Rätsel knacken können. Das Team hat gezeigt, dass dieser datengesteuerte, adaptive Ansatz ein mächtiges Werkzeug ist, das eine chaotische Suche in eine fokussierte Jagd nach dem perfekten Signal verwandelt. Obwohl das Problem für sehr lange Sequenzen unglaublich schwierig bleibt, hat diese Methode erfolgreich die Grenzen dessen verschoben, was wir für möglich halten, und neues „Gold“ in der digitalen Wüste gefunden.

Technische Zusammenfassung: Priorisierung von Suchraumregionen im Problem der binären Sequenzen mit niedriger Autokorrelation

Problemdefinition
Das Problem der binären Sequenzen mit niedriger Autokorrelation (Low Autocorrelation Binary Sequences, LABS) ist eine anspruchsvolle kombinatorische Optimierungsaufgabe mit dem Ziel, binäre Sequenzen $S = \{s_1, \dots, s_L\}$ mit $s_i \in \{+1, -1\}$ zu finden, die die Summe der quadrierten aperiodischen Autokorrelationen minimieren. Das Ziel ist die Maximierung des Merit-Faktors $F$ , definiert als $F(S) = L^2 / 2E(S)$ , wobei $E(S)$ die Energie der Sequenz ist. Der Suchraum wächst exponentiell ( $2^L$ ) und ist durch eine zerklüftete Landschaft mit zahlreichen lokalen Minima und seltenen, isolierten globalen Minima gekennzeichnet. Während schiefsymmetrische Sequenzen (wobei $s_{k+1+i} = (-1)^i s_{k+1-i}$ gilt) den Suchraum reduzieren und ungerade Verschiebungsautokorrelationen eliminieren, bleibt das Finden optimaler Sequenzen für große $L$ mittels exakter Methoden rechnerisch unpraktikabel.

Methodik
Die Autoren schlagen ein hybrides Suchframework vor, TS-SAW, das Online-Entscheidungsfindung mit paralleler stochastischer Suche integriert, um Rechenressourcen dynamisch über den LABS-Suchraum zu verteilen. Die Methodik besteht aus drei Kernkomponenten:

Thompson-Sampling zur Partition-Priorisierung:
Der Suchraum wird in disjunkte Regionen, sogenannte „Restriktionsklassen“ oder Partitionen, unterteilt, die durch das Fixieren der ersten $p$ Elemente der Sequenz definiert sind. Diese Partitionen werden als „Arme“ in einem Multi-Armed-Bandit-Problem modelliert. Anstatt sich auf statische Heuristiken (wie Potenzialwerte) zur Rangfolge der Partitionen zu verlassen, verwenden die Autoren Thompson-Sampling, um Partitionen adaptiv auszuwählen.
- Jede Partition $k$ ist mit einem unbekannten Parameter $\theta_k$ verknüpft, der den erwarteten Merit-Faktor repräsentiert.
- Eine Beta-Verteilung $Beta(\alpha_k, \beta_k)$ dient als Prior für $\theta_k$ .
- Der Algorithmus verwendet fraktioniertes Thompson-Sampling, um mit kontinuierlichen Belohnungen (normalisierten Merit-Faktoren) umzugehen. Nachdem eine Suche auf einer Partition eine Belohnung $r_t \in [0, 1]$ liefert, werden die Parameter aktualisiert als $(\alpha_k, \beta_k) \leftarrow (\alpha_k + r_t, \beta_k + 1 - r_t)$ .
- Dieser Mechanismus verschiebt die Rechenleistung dynamisch hin zu Partitionen, die empirisch höhere Merit-Faktoren liefern, während gleichzeitig die Exploration weniger untersuchter Regionen aufrechterhalten wird.
Parallele Self-Avoiding Walks (SAW) auf der GPU:
Sobald eine Partition ausgewählt wurde, führt der Algorithmus einen Self-Avoiding Walk durch, um die Sequenz innerhalb dieses eingeschränkten Raums zu optimieren.
- Implementierung: Die Walks werden parallel auf NVIDIA-GPUs (CUDA) ausgeführt. Jeder Walk operiert als unabhängiger Agent innerhalb eines CUDA-Blocks.
- Zyklusvermeidung: Um das Wiederbesuchen von Zuständen ohne übermäßigen Speicherverbrauch zu verhindern, speichert eine Bloom-Filter die Hashes der besuchten Sequenzen.
- Effizienz: Die Nachbarschaftsbewertung nutzt Linear-Zeit-Flip-Operationen für schiefsymmetrische Sequenzen, was einen geringen Speicherbedarf und hohen Durchsatz gewährleistet.
- Gemeinsames Lernen: Während die Walks parallel laufen, teilen sie eine globale Posterior-Überzeugung ( $\alpha_k, \beta_k$ ), die nach jedem Batch von Walks aktualisiert wird, was den Lernprozess beschleunigt.
Zweistufige Optimierungspipeline:
Das Framework verwendet eine zweistufige Strategie, um Lösungen zu verfeinern:
- Stufe 1 (Beschränkt): Parallele SAWs explorieren den partitionierten, schiefsymmetrischen Suchraum. Die Top- $m$ -Kandidaten (ausgewählt via Quickselect-Algorithmus) werden an die nächste Stufe übergeben.
- Stufe 2 (Unbeschränkt): Diese Kandidaten werden einer weiteren Verfeinerung im unbeschränkten Suchraum unterzogen. Diese Stufe entfernt die Schiefsymmetrie sowie die Partitionsbeschränkungen und nutzt eine Prioritätswarteschlange sowie Sequenzoperatoren (Rotationen und Flips), um eine breitere Region zu explorieren und die Lösungsqualität zu verbessern.
- Sequenzoperatoren: Um geradzahlige Sequenzen zu handhaben, wendet die Methode Operatoren an, die optimierte ungeradzahlige Sequenzen in geradzahlige Varianten transformieren, welche dann in die Verfeinerungsphase zurückgeführt werden.

Wesentliche Beiträge

Adaptive Ressourcenallokation: Eine neuartige Online-Methode, die Thompson-Sampling nutzt, um Suchraumregionen dynamisch zu priorisieren, wodurch statische heuristische Rangfolgen überwunden werden.
Hybrider Algorithmus (TS-SAW): Ein neuer Algorithmus, der Multi-Armed-Bandit-Entscheidungsfindung mit GPU-beschleunigten parallelen Self-Avoiding Walks kombiniert.
Skalierbare Architektur: Eine zweistufige Pipeline, die massive Parallelität für die initiale Exploration und unbeschränkte Verfeinerung für die finale Optimierung nutzt.
Neue Best-Known-Solutions: Die Generierung neuer Rekordsequenzen für 35 verschiedene Längen im Bereich $450 \le L \le 527$ sowie für $L = 573$ .

Experimentelle Ergebnisse
Die Experimente wurden auf dem Vega-Supercomputer mit NVIDIA A100 GPUs durchgeführt. Die Methode wurde für binäre Sequenzen mit Längen $450 \le L \le 527$ und $L = 573$ getestet, wobei 100.000 Iterationen für die Initialphase durchlaufen wurden.

Verbesserungen des Merit-Faktors: Die vorgeschlagene Methode verbesserte die bisher besten bekannten Merit-Faktoren für alle 35 getesteten Längen. Die mittlere Steigerung des Merit-Faktors über alle verbesserten Sequenzen hinweg betrug 0,1967.
Rekorde:
- Für $L = 451$ erreichte die Methode einen Merit-Faktor von $F = 8,0555$ und übertraf damit den bisherigen Bestwert um 0,8248. Dies ist die längste in der Literatur berichtete Sequenz mit einem Merit-Faktor über 8,0.
- Für $L = 573$ wurde der Merit-Faktor um 0,2564 verbessert, was die längste bekannte Sequenz mit $F > 7,0$ darstellt.
Partitionsanalyse: Ein Experiment mit $L=461$ demonstrierte, dass Thompson-Sampling effektiv hochperformante Partitionen identifiziert. Der Algorithmus verlagerte den Fokus weg von Partitionen mit hohem theoretischem „normalisiertem Potenzial“ hin zu jenen, die empirisch bessere Ergebnisse lieferten, was den Wert der datengesteuerten Allokation gegenüber statischen Heuristiken bestätigt.

Bedeutung und Ansprüche
Das Paper behauptet, dass das vorgeschlagene Framework eine skalierbare und effektive Strategie zur Maximierung der Merit-Faktoren im LABS-Problem bietet. Durch die Integration von probabilistischer Entscheidungsfindung mit Hochleistungs-Parallelcomputing balanciert der Ansatz erfolgreich Exploration und Exploitation in einer hochgradig zerklüfteten Suchlandschaft aus. Die Autoren führen an, dass Verbesserungen mit zunehmender Sequenzlänge immer schwieriger werden, ihre datengesteuerte, partitionsgestützte stochastische Optimierung jedoch einen vielversprechenden Weg zur Weiterentwicklung des aktuellen Stands der Technik darstellt. Die Ergebnisse validieren, dass eine Online-adaptive Ressourcenallokation einer statischen Heuristik-Priorisierung für diese Klasse kombinatorischer Probleme überlegen ist. Die Autoren schließen, dass dieses Framework einen Pfad zu adaptiven Suchstrategien für andere schwierige kombinatorische Optimierungsprobleme bietet, bei denen der Suchraum sinnvoll partitioniert werden kann.