QUBO-Generierung für (MAX-)3SAT mittels generativer KI-Methoden

QUBO-Generierung für (MAX-)3SAT mittels generativer KI-Methoden

Abstract:

Das Erstellen von QUBOs für 3-SAT Formeln mittels Pattern QUBOs bringt einige Herausforderungen. Das generieren der Pattern QUBOs und die Erstellung der QUBO ist aufgrund des Brute-Force Ansatzes technisch aufwendig. In dieser Arbeit werden zwei Machine Learning Ansätze für die QUBO Generierung gegeben einer 3-SAT Formel getestet. Für das Encoden der Formeln und Matrizen wurden verschiedene Encodings untersucht. Zu den Formel Encodings zählen Vektor, Word2Vec und BERT. Auf QUBOs wurden latent Repräsentationen getestet. Als Startmodell dient ein conditional Autoencoder. Variationen wie 2-Encoder, vortrainierte Encoder basierend auf einem RESNET18 wurden ebenso getestet. Für 1 Klausel Formeln konnten akkurate QUBOs generiert werden, für untersuchte Formeln mit bis zu 4 Klauseln überschneiden sich die Energien der Lösung- und Restzustände. Letztens wurde ein conditional Diffusion Modell aufgesetzt und mit Vektor, Word2Vec und BERT Formel Embeddings auf 5 und 7 random Klauseln trainiert. Mit BERT Formel Embeddings konnten mit den erstellten QUBOs durchschnittlich die meisten Klauseln einer Formel erfüllt werden. Die Formeln blieben aber zum Großteil ungelöst. Mit maskierten Training für Diffusion kann das Training noch verbessert werden. Es konnte im Durchschnitt mit Masken generierten QUBOs eine Klausel mehr erfüllt werden. Dies verlangt als Input eine vordefinierte Maske in der Datengeneration. Als Hauptgrund für die Ergebnisse kann die spärliche QUBO Datenstruktur und die Schwierigkeit für das Erstellen einer 3-SAT Formel Kodierung verantwortlich gemacht werden.

Autor/in:

Philippe Wehr

Betreuer:

Studentische Abschlussarbeit | Veröffentlicht März 2025 | Copyright © QAR-Lab
Anfragen zu dieser Arbeit an die Betreuer