Emerging Cooperation through Quantum Entanglement in Multi-Agent Systems
Bachelorarbeit (März 2025)
Autor: Marvin Heinrich
Abstract:
Diese Arbeit untersucht die Machbarkeit der Nutzung von Quantenverschränkung zur Verbesserung der Kooperation im Multi-Agenten-Reinforcement-Learning. Unter Verwendung des iterierten Gefangenendilemmas als Benchmark schlagen wir ein dezentrales Multi-Agenten-Reinforcement-Learning-Framework vor, in dem zwei MARL-Agenten mit Variational Quantum Circuits ausgestattet sind und sich durch Quantenverschränkung gegenseitig beeinflussen können. Im Gegensatz zu bestehenden Ansätzen, die auf spezielle Quantenkommunikationskanäle angewiesen sind, untersucht diese Arbeit, ob Verschränkung allein kooperative Gleichgewichte ermöglichen kann. Daher bewerten wir die Auswirkungen verschiedener Verschränkungsarchitekturen, um gemeinsame Kooperationsstrategien zu entwickeln, die dem Nash-Gleichgewicht entkommen. Die Ergebnisse unserer Experimente zeigen, dass Verschränkung zwar Strategien begünstigen kann, die die Defektionsbasislinie übertreffen, langfristiges kooperatives Verhalten jedoch nicht realisierbar bleibt. Dies deutet darauf hin, dass Quantenkorrelationen allein nicht ausreichen, um kooperative Strategien im Multi-Agenten-Reinforcement-Learning aufrechtzuerhalten.
Betreuer: Michael Kölle, Leo Sünkel, Claudia Linnhoff-Popien
QUBO-Generierung für (MAX-)3SAT mittels generativer KI-Methoden
Masterarbeit (März 2025)
Autor: Philippe Wehr
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 basierte. 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 Durschnitt 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.
Betreuer: Sebastian Zielinski, Michael Kölle, Claudia Linnhoff-Popien
Distributed Quantum Machine Learning – Training and Evaluating a Machine Learning Model on a Distributed Quantum Computing Simulator
Masterarbeit (März 2025)
Autor: Kian Izadi
Abstract:
Die Anzahl der Qubits, die auf einem Quantencomputer zur Verfügung stehen, stellt in der Regel eine Einschränkung für das Training und die Ausführung von Quantum-Machine-Learning-Modellen dar. Eine mögliche Lösung dieses Problems besteht darin, das Modell auf mehrere Quantumcomputer aufzuteilen und verteilt auszuführen. Dieser Ansatz wird als Distributed Quantum Machine Learning (DQML) bezeichnet. Dadurch kann eine größere Anzahl von Qubits verwendet werden, was das Training größerer Modelle ermöglicht oder die Klassifikationsleistung verbessern kann. Allerdings erfordert die Kommunikation zwischen den einzelnen Quantencomputern erhebliche klassische und quantenmechanische Ressourcen, was zu einem hohen Rechenaufwand und verlängerten Trainingszeiten führt. Um diesen Ansatz und seine Grenzen zu untersuchen, wird in dieser Arbeit ein DQML-Modell vorgestellt, das unter Verwendung des verteilten Quanten-Frameworks NetQASM implementiert wurde und dessen Architektur aus einem klassischen Server sowie zwei Quanten-Clients besteht. Das Modell wurde auf Datensätzen mit zwei und vier Merkmalen auf einem Quantennetzwerk-Simulator trainiert und evaluiert. Es erreichte eine vergleichbare Klassifikationsleistung wie ein zentralisiertes Quanten-Baseline-Modell. Um den Kommunikationsaufwand, der zu Trainingszeiten von 50 bis 500 Minuten pro Trainingsepisode führte, zu verringern, wurden Optimierungen an der Schaltungsarchitektur, der Erzeugung verschränkter Zustände und der verteilten Quantengatterausführung implementiert und evaluiert. Dadurch konnte die Laufzeit des Modells bei vergleichbarer Klassifikationsgenauigkeit um bis zu 60% reduziert werden.
Betreuer: Leo Sünkel, Michael Kölle, Thomas Gabor, Claudia Linnhoff-Popien
Multi-Objective Reinforcement Learning using Evolutionary Algorithms for Diverse Policy Selection
Masterarbeit (März 2025)
Autor: Clarissa Kümhof
Abstract:
In den letzten Jahren hat das Reinforcement Learning (RL) als Rahmen für sequentielle Entscheidungsfindung erheblich an Aufmerksamkeit gewonnen. Dabei lernt ein Agent, durch Interaktion mit einer Umgebung kumulative Belohnungen zu maximieren. Eine Unterkategorie von RL, das Multi-Objective Reinforcement Learning (MORL), konzentriert sich darauf, mehrere widersprüchliche Ziele gleichzeitig zu optimieren. In solchen Fällen ist es oft notwendig, ein Gleichgewicht zwischen diesen Zielen zu finden. Allerdings fehlt es traditionellen MORL-Methoden häufig an der Fähigkeit, eine Vielfalt an Lösungen aufrechtzuerhalten, da sie typischerweise nur eine einzelne Strategie als Ergebnis liefern. Besonders in dynamischen Umgebungen können zu unterschiedlichen Zeitpunkten verschiedene Zielabwägungen erforderlich sein. Um diese Herausforderungen zu bewältigen, stellt diese Arbeit EMOS — einen Evolutionary Multi-Objective Selector — vor, der RL mit Evolutionary Algorithms (EAs) kombiniert, um Multi-Objective-Probleme effizienter zu lösen. Durch den Einsatz von EAs zur Evolution einer Population von Strategien zielt die Methode darauf ab, die Pareto Front zu approximieren, indem sie eine Vielfalt an Lösungen bereitstellt, anstatt nur eine einzelne Strategie auszuwählen. Aufbauend auf Konzepten aus dem Evolutionary Reinforcement Learning (ERL) und Prediction-Guided MORL (PGMORL) integriert das vorgeschlagene Framework die Actor-Critic-Methodologie Proximal Policy Optimization, wobei trainierte Strategien in die evolutionäre Population aufgenommen werden, um Exploration durch EAs mit Exploitation durch Policy-Gradient-Updates zu kombinieren. Dieser hybride Ansatz ermöglicht eine flexible Entscheidungsfindung in der Inferenzphase, in der Strategien dynamisch basierend auf verschiedenen Zielen (z.B. Minimierung von Reue und Unsicherheit) zu jedem Zeitpunkt ausgewählt werden können. EMOS wird gegen die aktuellen Algorithmen Concave-Augmented Pareto Q-Learning (CAPQL) und Generalized Policy Improvement (GPI) getestet, um sowohl seine methodischen Stärken als auch seine empirische Leistung zu bewerten. Ein Open-Source-Repository mit MORL-Baselines wird verwendet, um die Reproduzierbarkeit und Kompatibilität mit gängigen MORL-Umgebungen wie MuJoCo sicherzustellen. EMOS übertrifft PGMORL hinsichtlich erwartetem Nutzen und Hypervolumen, insbesondere in mo-halfcheetah-v4, was die Erzeugung vielfältiger Lösungen demonstriert. Aufgrund seiner explorativen Natur weist es jedoch eine höhere Streuung auf. Darüber hinaus erzielt EMOS diese Ergebnisse mit geringerem Rechenaufwand, da es kein Vorhersagemodell erlernt und mit weniger Strategien in der Population arbeitet als PGMORL. Dadurch ist EMOS auch bei begrenzten Ressourcen eine wettbewerbsfähige Option. EMOS zeigt einen stabilen Ansatz zur Evolution von Strategien mit einer gut verteilten Pareto Front in bestimmten Umgebungen, bleibt jedoch hinter CAPQL und GPI zurück, die höhere Hypervolumen und erwartete Nutzwerte erzielen.
Betreuer: Philipp Altmann, Maximilian Zorn, Claudia Linnhoff-Popien
Minimierung der Teleportation und Steigerung der Fidelity in Distributed Quantum Computing mittels eines multiobjektiven evolutionären Algorithmus
Bachelorarbeit (Februar 2025)
Autor: Abasin Omerzai
Abstract:
Quanten Computing gilt als eine vielversprechende Technologie, um Aufgaben zu lösen, die selbst für das klassische Computing nicht zu bewältigen sind. Allerdings stoßen einzelne Quantencomputer aufgrund verschiedener Herausforderungen an ihre Grenzen, wodurch sie nur eine begrenzte Anzahl an frei verfügbaren Qubits bereitstellen können. Diese Einschränkung kann durch die Realisierung des DQC überwunden werden, einem Konzept, das durch die Vernetzung mehrerer Quantencomputer über ein Quantennetzwerk die Anzahl der verfügbaren Qubits erheblich steigert. Innerhalb eines solchen Systems werden die Qubits von einem Quantencomputer zu einem anderen mithilfe der Quanten Teleportation übertragen, einem ressourcenintensiven, aber unverzichtbaren Protokoll für die Kommunikation im DQC. Eine Minimierung der Anzahl der Teleportationen ist daher von essenzieller Bedeutung, birgt jedoch bei einfachen Ansätzen, wie der Minimierung globaler Gates, die auf Teleportation basieren, das Risiko, die Funktionalität eines Circuits zu beeinträchtigen. Um diesen Herausforderungen zu begegnen, wird in dieser Arbeit ein multiobjektiver evolutionärer Algorithmus (EA) vorgestellt, dessen Mechanismen wie Crossover, Mutation und Selektion dazu dienen, die Anzahl der Quanten Teleportationen zu minimieren und gleichzeitig die Fidelity, die ein Maß für die Ähnlichkeit ist, aufrechtzuerhalten. Der EA wurde an einer Reihe von QFT Benchmark Circuits sowie in weiteren Experimenten mit Random Circuits getestet, um seine Effektivität bei der Lösung der vorliegenden Problemstellung zu untersuchen. Die Ergebnisse demonstrieren, dass der Algorithmus die Anzahl der Teleportationen signifikant reduzieren kann, während die Fidelity über dem Schwellenwert von 0.9 gehalten wird. Im Vergleich zum Kernighan-Lin-Algorithmus, der nur lokale Optima liefert, erzielt dieser Ansatz in allen Aspekten bessere Resultate.
Betreuer: Leo Sünkel, Michael Kölle, Claudia Linnhoff-Popien
Evaluating Parameter-Based Training Performance of Neural Networks and Variational Quantum Circuits
Bachelorarbeit (Februar 2025)
Autor: Alexander Feist
Abstract:
In den vergangenen Jahren haben neuronale Netze (NN) bei den bedeutenden Fortschritten im Bereich des maschinellen Lernens eine zentrale Rolle gespielt. Mit zunehmender Komplexität der Aufgaben des maschinellen Lernens steigt die Anzahl an trainierbaren Parametern für NNs, was einen hohen Rechen- und Energiebedarf zur Folge hat. Variational Quantum Circuits (VQC) sind eine vielversprechende Alternative. Sie nutzen quantenmechanische Konzepte, um komplexe Beziehungen zu modellieren und benötigen im Vergleich zu NNs tendenziell weniger trainierbare Parameter. In dieser Arbeit wird die Trainingsleistung von NNs und VQCs anhand von einfachen Supervised Learning und Reinforcement Learning Aufgaben evaluiert und verglichen, wobei jeweils mehrere Modelle mit verschiedenen Parameterzahlen betrachtet werden. Die Experimente mit VQCs werden mit einem Simulator durchgeführt. Um zu ermitteln, wie lange das Trainieren der VQCs mit derzeit verfügbarer echter Quantenhardware dauern würde, werden ausgewählte Teile des Trainings mit einem echten Quantencomputer ausgeführt. Die Ergebnisse bestätigen, dass VQCs vergleichbare Leistung wie NNs erzielen können und dabei deutlich weniger Parameter benötigen. Trotz längerer Trainingszeiten deuten die Ergebnisse darauf hin, dass VQCs für bestimmte Aufgaben des maschinellen Lernens von Vorteil sein können, insbesondere wenn sich Quantentechnologie weiterhin rapide entwickelt, Algorithmen optimiert und VQC-Architekturen verbessert werden.
Betreuer: Michael Kölle, Jonas Stein, Claudia Linnhoff-Popien
Leveraging Preconditioning to Speed Up Quantum Simulation-Based Optimization
Bachelorarbeit (Februar 2025)
Autor: Carlotta von L’Estocq
Abstract:
Simulationsbasierte Optimierung ist rechnerisch sehr aufwendig, da zahlreiche Auswertungen komplexer Simulationen erforderlich sind, um eine Zielfunktion zu optimieren. Quantenalgorithmen können hier eine bessere Laufzeit im Vergleich zu klassischen Methoden erzielen, indem sie gleichzeitig mehrere potenzielle Lösungen bewerten. Wenn die Zielfunktion und/oder die Nebenbedingungen von statistisch zusammenfassenden Informationen abhängen, die aus den Ergebnissen einer Simulation abgeleitet werden, wird das Problem als Quantum Simulation-Based Optimization (QuSO)-Problem klassifiziert. Eine Unterklasse von QuSO ist LinQuSO, bei der die Simulationskomponente als ein System linearer Gleichungen formuliert werden kann. Die Berechnung der Zielfunktion hängt von der Komplexität der Lösung des entsprechenden linearen Gleichungssystems ab, welche linear von der Konditionszahl des Systems beeinflusst wird. Ein kürzlich erschienener Artikel stellte einen Quantenalgorithmus zur Lösung prototypischer linearer elliptischer partieller Differentialgleichungen zweiter Ordnung vor, die mit 𝑑-linearen Finite-Elementen auf kartesischen Gittern innerhalb eines begrenzten 𝑑-dimensionalen Bereichs diskretisiert werden. Durch die Verwendung eines BPX-Vorkonditionierers wird das lineare Gleichungssystem in ein wohlkonditioniertes System transformiert. Funktionale der Lösung können für eine gegebene Toleranz 𝜀 mit einer Komplexität von ˜𝒪(︀ polylog(︀ 𝜀−1)︀)︀ berechnet werden, wobei für 𝑑 > 1 ein Laufzeitvorteil gegenüber klassischen Lösungsverfahren erzielt wird. Diese Arbeit zeigt, wie die Effizienz der Berechnung von optimalen Eingabeparametern für ein LinQuSO-Problem verbessert werden kann, indem der Vorkonditionierungsalgorithmus in den Quantum Approximate Optimization Algorithm (QAOA) integriert wird, was zu einer Laufzeit von ˜𝒪(︀ 𝜀−1 polylog(︀ 𝜀−1)︀)︀ für die Simulationskomponente führt. Der neue Ansatz wird anhand eines Anwendungsfalls aus der Topologieoptimierung für Wärmeleitung demonstriert.
Betreuer: Jonas Stein, David Bucher, Claudia Linnhoff-Popien
Space-Efficient Quantum Optimization for the Traveling Salesman Problem via Binary Encoding of Feasible Solutions
Masterarbeit (Februar 2025)
Autor: Viktoria Patapovich
Abstract:
Das Traveling Salesperson Problem (TSP) ist eine klassische kombinatorische Optimierungsaufgabe mit zahlreichen Anwendungen in Logistik, Planung und Terminbestimmung. Quantenalgorithmen, insbesondere der Quantum Approximate Optimization Algorithm (QAOA), haben bereits Potenzial gezeigt, um solche NP-schweren Probleme zu lösen und könnten gegenüber klassischen Methoden Vorteile bieten. Bestehende Quantenverfahren für das TSP verwenden üblicherweise eine One-Hot-Kodierung, die für ein TSP mit n Städten O(n 2 ) Qubits erfordert und constraintspezifische Mixer wie den XY-Mixer einsetzt, um im gültigen Zustandsraum zu bleiben. Diese Ansätze sind jedoch ressourcenintensiv und stoßen bei steigender Qubit-Zahl schnell an praktische Grenzen. In dieser Masterarbeit wird eine neue Kodierung für das TSP unter Nutzung von QAOA vorgestellt, bei der Permutationen in Binärform abgebildet werden und der Qubit-Bedarf so auf O(n log 2 n) sinkt. Die größte Schwierigkeit dieser Binärkodierung liegt darin, dass kein einfacher constraintspezifischer Mixer verfügbar ist, um während der Optimierung die Gültigkeit der Zustände sicherzustellen. Zur Lösung dieses Problems wird eine effizient realisierbare unitäre Transformation entwickelt, die jedem binär kodierten Rundweg einen eindeutigen Index zuweist. Durch das Hinzufügen von O(log 2 (n!)) zusätzlichen Qubits, welche jede mögliche TSP-Permutation in faktorieller Basis repräsentieren, entsteht eine kanonische Isomorphie zwischen Permutationen und faktoriellel kodierten Zahlen. Dadurch kann in diesem zusätzlichen Qubit-Bereich ein einfacher X-Mixer oder ein Grover-Mixer verwendet werden, sodass sich der Optimierungsprozess automatisch auf gültige Zustände beschränkt und die Nebenbedingungen während der gesamten Optimierung eingehalten werden. Dies ermöglicht eine schnellere Konvergenz in Richtung der optimalen Lösung. In Rahmen dieser Masterarbeit werden es drei Varianten dieser Kodierung untersucht: (1) eine direkte unitäre Transformation mithilfe einer vorberechneten Lookup-Tabelle, (2) ein Verfahren auf Basis von Quantenarithmetik sowie (3) ein reines Index-Verfahren, bei dem sowohl Kosten- als auch Mixer-Hamiltonoperatoren in →log 2 (n!)↑ Qubits kodiert werden, was allerdings zu tieferen Schaltkreisen führt. Numerische Experimente mit kleinen Problemgrößen zeigen die Realisierbarkeit dieser Ansätze und unterstreichen die möglichen Vorteile des platzsparenden Kodierungsschemas für praktische Quantenoptimierungsaufgaben.
Betreuer: Jonas Stein, David Bucher, Claudia Linnhoff-Popien
Warm Starting Variational Quantum Algorithms for Parameterized Combinatorial Optimization
Bachelorarbeit (Dezember 2024)
Autor: Federico Harjes Ruiloba
Abstract:
In der Noisy Intermediate Scale Quantum Computing (NISQ) Ära sind Variationelle Quantenalgorithmen (VQAs) ein Schlüsselparadigma, um trotz Hardwarebeschränkungen nützliche Ergebnisse zu erzielen. Diese Algorithmen können an verschiedene Domänen angepasst werden, z. B. an die Festkörperphysik und die kombinatorische Optimierung. Probleme in diesen Bereichen können als Ising-Hamiltonians modelliert werden. Um physikalische Systeme zu modellieren, enthalten Hamiltonians oft Parameter, die globale Kräfte, wie z. B. Magnetfelder, steuern. Im Gegensatz dazu sind Hamiltonians, die kombinatorische Optimierungsprobleme (COPs) modellieren, in der Literatur in der Regel nicht parametrisiert und beschreiben eine spezifische Probleminstanz. In der Realität beeinflussen jedoch mehrere globale Variablen wie die Tageszeit oder die Marktrichtung Instanzen von COPs. In dieser Arbeit werden parametrisierte Hamiltonians für kombinatorische Optimierung anhand der Maximum-Cut- und Knapsack-Probleme eingeführt und ein Rahmenwerk vorgestellt, das auf andere COPs ausgedehnt werden kann. Der Rahmen erweitert die derzeitigen Ansätze zur Modellierung von COPs, um mehrere Probleminstanzen mit einem einzigen Hamiltonian mit globalen Parametern zu beschreiben. Anschließend wird in dieser Arbeit die Optimierung von parametrisierten COPs unter Verwendung verschiedener VQA-Varianten untersucht, wobei Zielfunktionen, die auf COPs zugeschnitten sind, getestet werden. Schließlich wird die Übertragung optimierter Parameter zwischen Probleminstanzen untersucht, die zu unterschiedlichen Hamiltonian-Parameterwerten entsprechen. Dabei wird bewertet, ob Parameter, die für eine Konfiguration eines Problems gute Lösungen liefern, für andere Konfigurationen ähnliche Ergebnisse liefern können. Für diese Aufgabe werden zwei einfache Modifikationen bestehender Verfahren vorgestellt, die als Adaptive Start und Aggregated Learning bezeichnet werden. In dieser Arbeit wird ein neuer Ansatz für die kombinatorische Optimierung vorgestellt und das Potenzial dieses neuen Rahmens untersucht
Betreuer: Tobias Rohe, Jonas Stein, Claudia Linnhoff-Popien
Emergent Behavior in Self-Evaluating Genetic Programming Based on 𝜆-Expressions
Bachelorarbeit (Dezember 2024)
Autor: Reinhard Bittner
Abstract:
1993 haben Walter Fontana und Leo W. Buss eine Minimaltheorie biologischer Organisation entwickelt, die auf dem untypisierten 𝜆-Kalkül als Modell für eine abstrakte Chemie basiert. Im 𝜆-Kalkül wird mittels einer darin definierten Anwendungsoperation zwischen 𝜆-Ausdrücken ein neuer 𝜆-Ausdruck erzeugt. Wird dieser Mechanismus wiederholt und in zufälliger Verteilung an einer anfangs zufälligen Population von 𝜆-Ausdrücken ausgeführt, entstehen selbsterhaltende und selbstregulierende Organisationen in der Population. Wir greifen dieses Konzept auf und übertragen es in die genetische Programmierung. Genetische Programmierung macht sich die Konzepte natürlichen genetischen Prozesses zunutze, um aus einer Population zufälliger, aber auf eine bestimmte Aufgabe bezogener Programme iterativ ein Programm zu entwickeln, das die gestellte Aufgabe besonders gut löst. Dabei werden die einzelnen Programme der Population in jedem Iterationsschritt verändert, wie zum Beispiel Unterprogramme willkürlich umgeschrieben, oder auch zwischen zwei Programmen ausgetauscht. Um abzuschätzen, wie gut ein Programm eine Aufgabe löst wird ein Fitnessfunktion definiert, die die Programme bewertet. Nur Programme mit guter Bewertung werden dann weiterentwickelt. In unserer Arbeit wenden wir diese Methodik auf 𝜆-Ausdrücke an. Allerdings gibt bei uns keine ausgewiesene Fitnessfuntion, sondern die 𝜆-Ausdrücke der Population bewerten sich gegenseitig, indem der zu bewertende Ausdruck einem zufälligen Ausdruck aus der Population als Argument in einer Anwendungsoperation übergeben wird. Da dies jedoch eine mathematisch abstrakte Operation ist, die einen weiteren 𝜆-Ausdruck erzeugt, stellt das für sich genommen noch keine Bewertung dar. Um eine nutzbare Bewertung abzuleiten, bewerten wir daher das Produkt der Anwendungsoperation nach syntaktischen und semantischen Maßstäben, indem wir bestimmte Elemente, oder Funtionseigenschaften mit einer Bestrafung belegen. Daraus leiten wir ein numerisches Fitnessmaß ab, das dann der Individuum der Population zugeordnet wird, das zur Auswertung ansteht. Diese Methodik legt die Grundlage dafür, dass sich eine entsprechende Population frei entwickelt und organisiert, wobei unsere Voreinstellungen zur Fitnessbestimmung einen globalen Rahmen im Sinne von Umweltbedingungen definieren. Wenn wir dieses Konzept auf eine zufällige Anfangspopulation anwenden, beobachten wir in der Tat die Entwicklung von Organisationsstrukturen in der Population, die invariante, gemeinsame syntaktische Elemente beinhalten. Dieser Effekt hängt stark von den Voreinstellungen ab, mit denen wir die genetische Programmierung ausführen. Wir untersuchen dazu zwei verschiedene, übergeordnete genetische Konfigurationen der von uns verwendeten Plattform für genetische Programmierung mit unterschiedlicher Konfiguration der genetischen Operatoren. Eine Konfiguration führt genetische Operationen ausschließlich mit und an 𝜆-Strukturlementen aus, die bereits in der Startpopulation vorliegen. Die zweite Konfiguration führt zusätzlich in jedem Iterationsschritt neue und zufällige 𝜆-Strukturlemente ein. Für beide übergeordnete Konfigurationen legen wir verschiedene Bestrafungsmuster fest. Beide übergeordneten genetischen Konfigurationen führen zur Ausbildung von Organisationsstrukturen in der Population. Die erste Konfiguration ergibt dynamische Organisationsstrukturen mit Individuen, die aus einheitlichen syntaktischen Strukturelementen bestehen und deren jeweilige Zusammensetzung sich in jedem Iterationsschritt verändert. Um diese Organisationsstrukturen sicher zu erzeugen, muss das Bestrafungsmuster grundsätzlich freie Variablen mit einbeziehen. Ist das nicht der Fall, entwickeln sich die Populationen überwiegend in einen statischen Zustand, der ausschließlich aus einzelnen freien Variablen besteht. Die zweite genetische Konfiguration erweist sich als wesentlich toleranter gegenüber verschiedenen Bestrafungsmustern und wir erhalten verschieden stark ausgeprägte Organisationsstrukturen deren Beteiligte auch eine höhere syntaktische Diversität aufweisen. Bildet sich gar keine erkennbare Organisationsstruktur, zeigen sowohl die Populationen zufällige Erscheinungsmuster, als auch die Individuen willkürlichen syntaktischen Aufbau ohne erkennbare Häufung spezifischer syntaktischer Strukturelemente. Uniforme Populationen, wie für die erste genetische Konfiguration treten nicht auf. Diese Studie könnte man als einen ersten Schritt betrachten, um eine Methodik zu entwickeln, die Entwicklung von Populationen unter vorgegebenen Umweltbedingungen zu beobachten. In Frage kommende Populationen dafür könnten aus mathematischen Modellen abgeleitet sein, die tatsächliche Probleme der erfahrbaren Welt abstrahieren. In diesem Sinne wäre die Plattform zur genetischen Programmierung die Umwelt, deren Bedingungen über die Voreinstellungen festgelegt werden. Zur Ausführung der genetischen Programmierung würde man eine, für eine spezifische Problemstellung entworfene Population übergeben und könnte deren Entwicklung beobachten. Sogar der Einfluss plötzlicher Störungen auf die Entwicklung ließe sich modellieren
Betreuer: Thomas Gabor, Maximilian Zorn, Claudia Linnhoff-Popien
Circuit Partitioning and Genetic Optimization for Efficient Qubit Distribution in Distributed Quantum Computing
Bachelorarbeit (Dezember 2024)
Autor: Simon Schlichting
Abstract:
Quantencomputer sind in der Lage, bestimmte Rechenprobleme in einem kürzeren Zeitrahmen zu lösen als klassischen Computer. Die derzeitigen Quantencomputer sind geprägt durch „Rauschen“. Der Begriff „Rauschen“ beschreibt die Begrenzung und Ungenauigkeit von den Berechnungen auf einem Quantencomputer. Dies stellt eine erhebliche Herausforderung für die Entwicklung von Quantencomputern im großen Maßstab dar. Problemstellungen werden in einem Quantenschaltkreis kodiert, der Quantenbits beinhaltet. Um große Schaltkreise auszuführen, können die Qubits auf verschiedene Quantencomputer verteilt werden. Die Verteilung von Qubits auf mehrere Quantencomputer wird im Rahmen des verteilten Quantencomputings erforscht. Die Verbindung der Quantencomputer erfolgt über ein Quantennetzwerk. Ein weiterer Ansatz zur Vereinfachung von Quantenschaltungen besteht in der Partitionierung von Schaltkreisen, wodurch die Tiefe der Schaltkreise verringert und eine Parallelisierung ermöglicht wird. Allerdings kann bei einer Partitionierung des Schaltkreises eine Berücksichtigung der Eigenheiten des Netzwerks nicht gewährleistet werden. Eine Methode zur Berücksichtigung von Netzeigenschaften im Verteilungsprozess stellt der Einsatz eines evolutionären Algorithmus dar. Der Ansatz wurde bereits angewandt, um die Verteilung von Qubits in einem Quantennetzwerk zu optimieren, bislang allerdings nur in begrenztem Umfang. Das Ziel dieser Arbeit ist die Kodierung der spezifischen Netzwerkstruktur zur Berücksichtigung der spezifischen Kosten jeder Operation. Zur Evaluierung der Effizienz des Algorithmus wurden Experimente mit zwei verschiedenen Netzwerktopologien durchgeführt und die Ergebnisse mit drei Grundlagen verglichen. Die durchgeführten Untersuchungen belegen, dass der Algorithmus im Vergleich zu den alternativen Methoden auf beiden Topologien bessere Ergebnisse aufweist.
Betreuer: Leo Sünkel, Maximilian Zorn, Claudia Linnhoff-Popien
Vergleich verschiedener hybrider Quantum Machine Learning Ansätze zur Klassifikation von Bildern auf Quantencomputern
Bachelorarbeit (Dezember 2024)
Autor: Nicolas Holeczek
Abstract:
Maschinelles Lernen (ML) und die Klassifikation von Bildern werden heutzutage immer wichtiger. So findet ML beispielsweise Einsatz in autonomen Fahrzeugen, um Hindernisse zu bestimmen, oder bei der automatischen Erkennung von Krankheiten in der Medizin. Allerdings steigen die Anforderungen an neuronale Netze, welche für die Klassifikation zum Einsatz kommen, immer weiter, da die Merkmale in den Bildern immer komplexer werden. Eine vielversprechende Lösung auf diesem Gebiet ist Quantencomputing, genauer Quantum Machine Learning (QML). Durch die Vorteile, welche die in Quantencomputern verwendeten Qubits mit sich bringen, könnten QML Ansätze deutlich schnellere und bessere Ergebnisse als herkömmliche ML Methoden erzielen. Derzeit befindet sich Quantencomputing in der sogenannten ’noisy intermediate-scale quantum’ (NISQ) Ära. Der Name besagt, dass Quantencomputer nur wenige und fehleranfällige Qubits besitzen. Dementsprechend ist reines Quantum Machine Learning nicht ohne Weiteres umsetzbar. Die Lösung sind hybride Ansätze, welche auf klassische Strukturen zurückgreifen und diese mit Quantenschaltkreisen verbinden. Diese Arbeit untersucht die hybriden Ansätze Quanvolutional Neural Network (QCNN), Quantum Transfer Learning (QTL) und Variational Quantum Circuit (VQC). Dazu werden diese trainiert die Bilder des MNIST Datensatzes zu klassifizieren. Das Training erfolgt mehrfach mit unterschiedlichen Seeds, um so die Ansätze auf ihre Robustheit zu überprüfen. Anschließend werden sie anhand von Genauigkeit, Verlust und Trainingsdauer miteinander verglichen. Zusätzlich wird ein herkömmliches Convolutional Neural Network (CNN) zum Vergleich herangezogen. Am Schluss kann so die Bestimmung des effizientesten Ansatzes erfolgen. Die Auswertung des Experiments zeigt, dass das QCNN deutlich bessere Ergebnisse als QTL und VQC erzielt. Allerdings schneidet das herkömmliche CNN bei allen Metriken besser ab als das QCNN.
Betreuer: Leo Sünkel, Philipp Altmann, Claudia Linnhoff-Popien
Reinforcement Learning-gestützte State Preparation mithilfe von parametrisierten Quantengattern
Bachelorarbeit (Dezember 2024)
Autor: Isabella Debelic
Abstract:
Diese Arbeit untersucht die Anwendung von Reinforcement Learning (RL) zur Optimierung der State Preparation in parametrisierten Quantenschaltkreisen. Durch den Einsatz von RL-Algorithmen wird ein Agent trainiert, der die optimale Sequenz von Quantengattern findet, um vorgegebene Zielzustände zu rekonstruieren. Besonderes Augenmerk wird auf die Herausforderungen bei der Nutzung parametrischer Gatter gelegt, die im Vergleich zu diskreten Schaltkreisen eine kontinuierliche Optimierung erfordern. Verschiedene Ansätze, darunter ein- und zweistufige Verfahren sowie Hyperparameter-Optimierungen, werden experimentell evaluiert. Die Ergebnisse zeigen, dass RL-basierte Methoden erfolgreich zur Reduzierung der Schaltkreistiefe beitragen können, allerdings vorwiegend bei einfachen Schaltkreisen. Komplexere Schaltkreise erfordern tiefere Anpassungen der Optimierungsstrategie, um ähnliche Erfolge zu erzielen.
Betreuer: Michael Kölle, Philipp Altmann, Claudia Linnhoff-Popien
Evaluating Mutation Techniques in Genetic Algorithm-Based Quantum Circuit Synthesis
Bachelorarbeit (Dezember 2024)
Autor: Tom Bintener
Abstract:
Die Optimierung von quantum circuits ist entscheidend für den Fortschritt des quantum computing, insbesondere für momentane Noisy Intermediate-Scale Quantum (NISQ)-Geräte. Diese Geräte stehen vor erheblichen Herausforderungen aufgrund der begrenzten Anzahl an Qubits und hoher Fehlerraten, was eine effiziente quantum circuit synthesis unerlässlich macht. Genetische Algorithmen (GAs) haben sich als vielversprechende Lösung zur Optimierung von quantum circuits etabliert, indem sie eine Aufgabe automatisieren, die sonst manuell und ineffizient gelöst wird. Diese Arbeit untersucht die Auswirkungen verschiedener Mutationsstrategien innerhalb eines GA-Frameworks zur Synthese von quantum circuits. Mutationen wirken sich auf der fundamentalsten Ebene eines circuits aus und können die Gesamtleistung erheblich beeinflussen. Die Erfassung von Daten darüber, wie diese Mutationen die circuits transformieren und welche Strategien am effizientesten sind, ist ein wichtiger Schritt für die Entwicklung eines robusten GA-Optimierers. Die in dieser Forschung durchgeführten Experimente verwendeten eine Fitnessfunktion, die hauptsächlich auf der fidelity basiert, wobei auch die circuit depth und die Anzahl der T-Operationen berücksichtigt wurden. Die Experimente konzentrierten sich auf die Optimierung von circuits mit vier bis sechs qubits und umfassten umfangreiche Tests von Hyperparametern, um optimale Lösungen für praktisches quantum computing zu identifizieren. Die Ergebnisse zeigen, dass die Kombination von delete- und swap-Strategien ohne die Verwendung von change- oder add-Strategien unter den gegebenen Einschränkungen die beste Leistung erbrachte.
Betreuer: Michael Kölle, Maximilian Zorn, Claudia Linnhoff-Popien
Update Behavior of Neural Networks Trained in Alternation with an Additional Auxiliary Task
Bachelorarbeit (November 2024)
Autor: Sara Sofía Juárez Oropeza
Abstract:
Diese Arbeit untersucht die Auswirkungen einer zusätzlichen Hilfsaufgabe – im Folgenden als Sekundäraufgabe bezeichnet – auf das Verhalten der Gewichtsaktualisierung in einem vollständig verbundenen, mehrschichtigen neuronalen Netzwerk. Konkret zielt die Untersuchung darauf ab, zu verstehen, wie das Training mit einer Sekundäraufgabe die Leistung des Netzwerks bei der Primäraufgabe beeinflusst, wenn es mit unterschiedlichen Eingabeparametern während des Trainings konfrontiert wird. Die Evaluierung umfasst eine klassische überwachtes Lernaufgabe zur Klassifikation von Ziffern unter Verwendung der MNIST-Datenbank, erweitert um eine Sekundäraufgabe. Diese Sekundäraufgabe wechselt zwischen der Berechnung einer einfachen Summe aus zwei Fließkommazahlen und deren Multiplikation. Das Netzwerk unterscheidet zwischen den beiden Aufgaben anhand der Formatierung der Eingabedaten. Die Eingabe- und Ausgabeschichten des Netzwerks werden um zusätzliche Dimensionen erweitert, um die Eingaben und Ausgaben der Sekundäraufgabe zu verarbeiten. Abgesehen davon wird die Netzwerkarchitektur in keiner Weise verändert, um die Sekundäraufgabe zu berücksichtigen. Die verwendete Verlustfunktion wird je nach der zu berechnenden Aufgabe ausgetauscht. Die ursprüngliche MNIST-Ziffernklassifikationsaufgabe ohne Sekundäraufgabe dient als Basislinie zum Vergleich der Ergebnisse. Die im Rahmen dieser Arbeit durchgeführte Evaluierung zielt darauf ab, folgende Forschungsfragen zu beantworten: Welche Auswirkungen hat eine zusätzliche Aufgabe auf die Leistung eines vollständig verbundenen, mehrschichtigen Feedforward-Netzwerks? Darüber hinaus wird untersucht, ob eine zusätzliche Aufgabe die Stabilität und Robustheit eines solchen Netzwerks in Bezug auf seine Fähigkeit, unvorhergesehene Änderungen in den Trainingsdaten zu verarbeiten, positiv beeinflusst. Diese Evaluierung soll dazu beitragen, die Funktionsweise neuronaler Netzwerke besser zu verstehen und mögliche Optimierungsansätze für Retraining-Techniken zu prüfen. Zusätzlich wird das Potenzial des Multitask-Trainings zur Verbesserung der Generalisierungsfähigkeit und Robustheit neuronaler Netzwerke erforscht. Die Ergebnisse dieser Studie zeigen, dass die Einbindung einer Sekundäraufgabe während des Trainings die Leistung des neuronalen Netzwerks bei der Primäraufgabe nicht negativ beeinflusst. Vielmehr deuten die Ergebnisse auf potenziell stabilisierende Effekte hin. Das Modell, das mit einer Sekundäraufgabe trainiert wurde, zeigt eine vergleichbare Leistung zur Basislinie, mit leicht verbesserter Stabilität bei der Bewältigung unvorhergesehener Änderungen in den Trainingsdaten. Falls sich dieses Verhalten allgemein bestätigt, könnten diese Erkenntnisse darauf hindeuten, dass eine zusätzliche Aufgabe als eine Form der impliziten Regularisierung fungieren kann, die die Generalisierungsfähigkeit und Anpassungsfähigkeit des Netzwerks an neue Daten verbessert. Mit dieser Studie hoffen wir, zur Entwicklung effizienterer Retraining-Protokolle beizutragen und das Verständnis des Multitask-Lernens in neuronalen Netzwerken zu vertiefen.
Betreuer: Thomas Gabor, Maximilian Zorn, Claudia Linnhoff-Popien
The Trainability of Quantum Federated Learning
Bachelorarbeit (November 2024)
Autor: Sina Mohammad Rezaei
Abstract:
Diese Arbeit untersucht die Implementierung und Evaluierung von Quantum Federated Learning (QFL), bei dem Variational Quantum Circuits (VQCs) gemeinsam über mehrere Quanten-Clients hinweg trainiert werden. Der Schwerpunkt liegt auf dem Vergleich der Leistung und Trainierbarkeit von QFL mit traditionellen Quanten-Maschinenlernansätzen unter Verwendung des MNIST-Datensatzes. Die Experimente wurden mit 2, 3, 4 und 5 Clients durchgeführt, die jeweils unterschiedliche Datensätze verarbeiteten, sowie mit einer variierenden Anzahl von Schichten (1, 2 und 4) in den Quanten-Schaltungen. Die Trainierbarkeit der Modelle wurde anhand der Bewertung von Genauigkeit, Loss und Gradienten-Normen während des Trainingsprozesses untersucht. Die Ergebnisse zeigen, dass QFL kollaboratives Lernen ermöglicht und während des Trainings signifikante Verbesserungen in diesen Metriken aufweist. Die Basismodelle ohne QFL erzielen jedoch in der Regel eine bessere Endgenauigkeit und geringere Verluste aufgrund des ununterbrochenen Optimierungsprozesses. Darüber hinaus wurde der Einfluss einer erhöhten Schichtenanzahl auf die Trainingsstabilität und Leistung analysiert.
Betreuer: Leo Sünkel, Tobias Rohe, Claudia Linnhoff-Popien
Investigating the Lottery Ticket Hypothesis for Variational Quantum Circuits
Bachelorarbeit (November 2024)
Autor: Leonhard Klingert
Abstract:
Quantencomputing ist ein aufstrebendes Feld in der Informatik, welches in den letzten Jahren große Fortschritte erzielt hat, unteranderem im Bereich des maschinellen Lernens. Durch die Prinzipien der Quantenphysik bietet es die Möglichkeit, die Grenzen von klassischen Algorithmen zu überwinden. Variational Quantum Circuits (VQC), eine spezielle Form von Quantum Circuits, welche variierende Parameter haben, stehen jedoch durch das Barren Plateau-Phänomen vor einer erheblichen Herausforderung, das den Optimierungsprozess in bestimmten Fällen behindern kann. Die Lottery Ticket Hypothesis (LTH) ist ein aktuelles Konzept im klassischen maschinellen Lernen, das zu bemerkenswerten Verbesserungen in neuronalen Netzwerken führen kann. Diese Arbeit untersucht, ob de LTH auf VQCs angewendet werden kann. Die LTH besagt, dass es innerhalb eines großen neuronalen Netzwerks ein kleineres, effizienteres Subnetzwerk, auch Winning Ticket genannt, gibt, das eine vergleichbare Leistung wie das ursprüngliche, vollvernetzte Netzwerk erzielen kann. Die Anwendung dieses Ansatzes auf VQCs könnte helfen, die Auswirkungen des Barren Plateau-Problems zu verringern. Die Ergebnisse dieser Arbeit zeigen, dass die Weak LTH auf VQCs anwendbar ist, wobei Winning Tickets gefunden wurden, die lediglich 26,0% der ursprünglichen Gewichte haben. Für die Strong LTH, bei der das Pruning ohne vorheriges Training durchgeführt wird, wurde ein Winning Ticket für einen Binary VQC gefunden, welcher 100% Accuracy mit 45% der ursprünglichen Gewichte erreicht. Das zeigt, dass die Strong LTH auf VQCs anwendbar ist. Diese Ergebnisse liefern erste Hinweise darauf, dass die LTH ein Ansatz zur Verbesserung der Effizienz und Leistung von VQCs in Quantum Machine Learning Aufgaben sein könnte.
Betreuer: Michael Kölle, Julian Schönberger, Claudia Linnhoff-Popien
Architectural Influence on Variational Quantum Circuits in Multi-Agent Reinforcement Learning: Evolutionary Strategies for Optimization
Bachelorarbeit (November 2024)
Autor: Karola Schneider
Abstract:
Das Forschungsgebiet des Multi-Agenten Reinforcement Learning (MARL) gewinnt zunehmend an Bedeutung, insbesondere in Anwendungsbereichen wie autonomem Fahren und Robotik, in denen mehrere Akteure interagieren. Eine zentrale Herausforderung des MARL ist das exponentielle Wachstum der Dimensionen in den Zustands- und Aktionsräumen. Die Nutzung quantenmechanischer Eigenschaften bietet vielversprechende Lösungen, da sie eine kompakte Verarbeitung hochdimensionaler Daten ermöglicht und die Anzahl der zu optimierenden Parameter reduziert. Ein Nachteil gradientenbasierter Optimierungs-Methoden im Quanten MARL ist das Auftreten von Barren Plateaus, welche die Konvergenz durch ineffektive Parameter-Updates behindern. Evolutionäre Algorithmen umgehen dieses Problem, indem sie ohne Gradienten arbeiten. Aufbauend auf Forschungsergebnissen, die das Potenzial Evolutionärer Algorithmen zur Optimierung Variationaler Quantenschaltkreise für MARL aufzeigen, untersuchen wir, welchen Einfluss die Einführung von Modifikationen der Architektur im Evolutionsprozess auf die Optimierung hat. Drei Architekturkonzepte für Variationale Quantenschaltkreise —Ebenen-Basiert, Gatter-Basiert und Prototyp-Basiert — wurden mithilfe zweier evolutionärer Strategien untersucht: einer Kombination aus Rekombination und Mutation (ReMu) sowie einer nur auf Mutation basierenden Strategie (Mu). Die Effizienz der Ansätze wurde anhand des Coin Games evaluiert, wobei eine Version ohne Anpassungen der Architektur als Vergleichsgrundlage diente. Die Mu-Strategie in Kombination mit dem Gatter-Basierten Ansatz erzielte die besten Ergebnisse, einschließlich der höchsten Punktzahlen, der meisten gesammelten Münzen und der höchsten Eigenmünzenquote, und benötigte dabei die geringste Anzahl an Parametern. Darüber hinaus benötigte eine Variante des Gate-Basierten Ansatzes, welche vergleichbare Ergebnisse wie die der Vergleichsgrundlage erzielte, deutlich weniger Gatter, was zu einer Beschleunigung der Laufzeit um 90,1% führte.
Betreuer: Michael Kölle, Leo Sünkel, Claudia Linnhoff-Popien
Learning Independent Multi-Agent Flocking Behavior With Reinforcement Learning
Bachelorarbeit (Oktober 2024)
Autor: Gregor Reischl
Abstract:
Schwarmverhalten ist ein in der Natur weit verbreitetes Phänomen, das bei zahlreichen Herdentieren als Schutzmechanismus vor potentiellen Feinden dient. Diese Arbeit untersucht die Entstehung von Schwarmverhalten mithilfe zweier verschiedener Ansätze des Reinforcement Learning (RL). In früheren Studien wurden RL-basierte Lernansätze analysiert, bei denen die Technik des Parameter-Sharing (PS) zum Einsatz kam. Dabei wurde festgestellt, dass die Beutetiere Schwarmverhalten entwickeln, um effizienter vor Räubern fliehen zu können. In dieser Arbeit wird der Ansatz erweitert, indem die Auswirkungen und Unterschiede der Verwendung von Independent Learning (IL) mit dem PS-Ansatz verglichen werden. In den durchgeführten Experimenten werden die Beutetiere von RL-Policies gesteuert, die mit den RL-Algorithmen „IPPO“ (IL) und „QMIX“ (PS) trainiert wurden. Die Agenten können sich dabei frei in einer kontinuierlichen, zweidimensionalen Umgebung bewegen, wobei ihr einziges Ziel darin besteht, so lange wie möglich zu überleben. Um den Vergleich zwischen PS und IL detaillierter zu untersuchen, werden verschiedene Sichtfelder sowie unterschiedliche Arten von Raubtierverhalten verwendet, die von einfachen Heuristiken bis hin zu einem RL-basierten Modell reichen. Zur Bewertung des erlernten Schwarm- und Fluchtverhaltens werden außerdem zusätzliche Metriken wie Ausrichtung und Kohäsion für verschiedene Agentenpopulationen analysiert. Die Ergebnisse zeigen, dass die PS-Methode robuste Schwarmbewegungen erzeugt, die auch unter wechselnden äußeren Bedingungen stabil bleiben und häufig sogar die Performance des klassischen Boid-Modells übertreffen, das oft als Vergleichbasis verwendet wird. Zwar zeigt IL ebenfalls deutliche Anzeichen von Schwarmverhalten, erreicht jedoch nicht das gleiche Maß an Koordination wie PS. Zudem sind die Überlebensstrategien der IL-Agenten insgesamt deutlich weniger effizient als bei PS.
Betreuer: Maximilian Zorn, Michael Kölle, Claudia Linnhoff-Popien
Enhancing Object Recognition with Uncertainty-Based Fusion Techniques: A Comparative Analysis of Voting Techniques and Machine Learning Models
Masterarbeit (Oktober 2024)
Autor: Martin Obwexer
Abstract:
Die Objekterkennung in sicherheitskritischen Anwendungen muss in der Lage sein, hochzuverlässige Vorhersagen zu liefern. In dieser Arbeit wird daher ein Ansatz zur Verbesserung der Objekterkennung mithilfe von unsicherheitsbasierten Ensemble-Fusionstechniken untersucht. Allgemein kombiniert eine unsicherheitsbasierte Ensemble-Fusionstechnik die Vorhersagen mehrerer Modelle, wobei diese basierend auf ihrer Unsicherheit gewichtet werden, um die Zuverlässigkeit und Robustheit der Objekterkennung in sicherheitskritischen Anwendungen zu erhöhen. Die Ensemble-Methode besteht darin, verschiedene Objekterkennungsmodelle zu kombinieren, deren Ausgaben fusioniert werden, um eine bessere Leistung zu erzielen als jedes einzelne Modell im Ensemble. Ziel ist es, durch das Zusammenführen der Ausgaben mehrerer Modelle ein robusteres und zuverlässigeres Ergebnis zu erzielen als mit einzelnen Modellen allein. Die Techniken sind in zwei Ansätze unterteilt: programmatisch und maschinelles Lernen. Beide Methoden übertrafen die einzelnen Ensemble-Modelle und zeigten, dass die Ensemble-Methode die Objekterkennung verbessert. Die Untersuchung hat gezeigt, dass ähnlich leistungsfähige Modelle als Eingabe verwendet werden können und die Anzahl der Modelle auf insgesamt drei Ensemble-Mitglieder begrenzt werden kann. Da die Anwendung in einem sicherheitskritischen Umfeld erfolgt, wird der Rückruf (Recall) höher gewichtet als die Genauigkeit (Precision). Daher erzielte die Methode des validierenden maschinellen Lernens das beste Ergebnis. Dieser Ansatz erzielte eine Verbesserung der Rückrufleistung um 7,3 %, jedoch auf Kosten einer Verringerung der Genauigkeit um 4,2 %. Der programmatische Ansatz verbesserte sowohl die Genauigkeit als auch den Rückruf durch affirmatives Voting und unsicherheitsbasierte Fusion und lieferte die beste Leistung unter den getesteten Optionen. Er erreichte eine kleine Leistungsverbesserung der Genauigkeit um etwa 0,8 % und des Rückrufs um etwa 2,2 %. Der programmatische Ansatz umfasste drei verschiedene Voting-Methoden: affirmativ, konsensbasiert und einstimmig, wobei die affirmative Methode die besten Ergebnisse erzielte. Innerhalb dieser Methode wurden drei verschiedene Fusionstechniken implementiert: klassenbasiert, unsicherheitsbasiert und basierend auf der Dempster-Shafer-Theorie, wobei die unsicherheitsbasierte Fusion am besten abschnitt, indem sie Konfidenzwerte zur Entscheidung von Klassenkategorien nutzte und gewichtete Bounding Boxes berechnete. Dieser Ansatz verbesserte die Präzision bei der Erkennung kleiner und mittelgroßer Objekte, verringerte jedoch leicht die Leistung bei großen Objekten. Auch die Verbesserung der Rückrufleistung war bemerkenswert, insbesondere bei der Erkennung kleiner Objekte. Der maschinelle Lernansatz wurde in vier unterschiedliche Ansätze unterteilt, die jeweils zunehmend komplexer wurden: Klassifizierung von Kategorien, Validierung von Vorhersagen, Generierung von Bounding Boxes und Generierung neuer Vorhersagen. Das Klassifizierungsmodell verbesserte die durchschnittliche Präzision, wies jedoch eine geringere Rückrufrate im Vergleich zu einem Einzelmodell auf. Das Validierungsmodell erhöhte den Rückruf bei allen Objektgrößen, hatte jedoch eine geringere Präzision. Das Bounding-Box-Generierungsmodell und das Vorhersagegenerierungsmodell erzielten aufgrund der Komplexität des Problems und der Einschränkungen der Daten keine relevanten Ergebnisse.
Betreuer: Thomas Gabor, Philipp Altmann, Claudia Linnhoff-Popien
An Evolutionary Algorithm with Similarity-Based Variation for Job-Shop Scheduling
Masterarbeit (Oktober 2024)
Autor: Marie Brockschmidt
Abstract:
Das Ziel dieser Arbeit ist, das NP-vollständige Job Shop Scheduling Problem zu untersuchen und hierbei einen evolutionären Algorithmus zur Ermittlung eines optimalen Lösungskandidaten zu verwenden. Das Job Shop Scheduling Problem beschreibt ein Optimierungsproblem, dessen Instanzen sich aus multiplen Jobs – bestehend aus verschiedenen Operationen –zusammensetzen. Jede dieser Operationen muss auf verschiedenen, vorher spezifizierten Maschinen bearbeitet werden. Das Ziel des Optimierungsproblems ist es, die Zeitspanne, in der alle Jobs auf allen Maschinen bearbeitet werden, zu minimieren. Aufgrund der zahlreichen Anwendungen in der Industrie ist dieses Problem von großer Bedeutung und wird dementsprechend weitreichend erforscht. Die Forschung an Lösungsstrategien inkludiert auch evolutionäre Algorithmen. In dieser Arbeit wird ein Ansatz erarbeitet und getestet, der die Rekombination und Mutation des evolutionären Algorithmus anpasst, indem gültige Lösungskandidaten kreiert werden, die ähnlich zu dem zu mutierenden Individuum oder den Eltern des Lösungskandidaten sind. Da die Reihenfolge der Operationen vorher definiert ist, ist es nicht möglich die Lösungskandidaten beliebig zu rekombinieren oder zu mutieren. Der Vorteil dieses Ansatzes ist es, den Fokus bei der Mutation auf die Exploration valider Lösungskandidaten zu lenken und außerdem die Performance der besten Lösungskandidaten auszunutzen, indem diese bei der Rekombination ein neues Individuum ergeben, welches beiden Eltern sehr ähnlich ist. Da die Einschränkungen der Prioritätsreihenfolge der verschiedenen Operationen jedes Jobs zu invaliden Lösungskandidaten führen können, wird dieser Ansatz herangezogen. Durch den hohen Bekanntheitsgrad des Job Shop Scheduling Problems existieren zudem multiple Benchmarkprobleme, so auch das Lawrence Set, welches zur Evaluation der Performanz genutzt werden kann, um den soeben vorgestellten Algorithmus beispielsweise in seiner Konvergenz oder Fähigkeit, eine optimale Lösung zu finden, zu vergleichen. Die Ergebnisse des Ansatzes sind vergleichbar mit anderen in der Literatur verwendeten Methoden und führen in den meisten Fällen zu ähnlich guten Lösungen bei gleicher Anzahl an Evaluationen. Für drei der vier verwendeten Benchmarkprobleme kann die optimale Lösung gefunden werden.
Betreuer: Thomas Gabor, Maximilian Zorn, Claudia Linnhoff-Popien
Neural Networks with a Regulatory Second Task on Neuron Level
Masterarbeit (Oktober 2024)
Autor: Julian Thomas Reff
Abstract:
Einbindung einer regulatorischen Aufgabe auf Neuron-Ebene in das Trainingsschema eines neuronalen Netzwerks neben der Hauptaufgabe ist ein neuartiger Ansatz. Diese Arbeit untersucht die Auswirkungen, wenn ein konstanter Ausgabewert von Null als sekundäre Aufgabe und die Klassifikation von MNIST als primäre Aufgabe trainiert werden. Die Experimente zeigen, dass das Ausmaß, in dem Neuronen die regulatorische Aufgabe erfüllen, als Metrik für das Pruning des neuronalen Netzwerks verwendet werden kann. Während das Pruning am Ende des Trainings ineffektiv ist, gelingt das Pruning in früheren Stadien – selbst bei drastischem Pruning – mit begrenztem Post-Training konsistent und verringert die Qualitätsminderung des Modells. Das Training des neuronalen Netzwerks mit der zusätzlichen regulatorischen Aufgabe auf Neuron-Ebene erhöht die Trainingsstabilität und verbessert die Generalisierungsfähigkeit des Modells auf neue Daten. In diesem Rahmen fungiert die regulatorische Aufgabe als Regularisierungstechnik, die das Netzwerk daran hindert, in lokale Minima zu konvergieren, und ein robustes Modell gewährleistet. Allerdings kann die regulatorische Aufgabe das Modell daran hindern, einen optimalen Zustand zu erreichen, sofern keine Anpassungen, wie beispielsweise die Modifikation der Lernrate der regulatorischen Aufgabe, vorgenommen werden. Obwohl das Training mit der regulatorischen Aufgabe zusätzliche Rechenzeit erfordert, bleibt die Trainingsgeschwindigkeit vergleichbar, während weniger als die Hälfte der Trainingsdaten genutzt wird.
Betreuer: Thomas Gabor, Maximilian Zorn, Claudia Linnhoff-Popien
State Preparation on Quantum Hardware Using an Island Genetic Algorithm
Masterarbeit (Oktober 2024)
Autor: Jonathan Philip Wulf
Abstract:
Da genetische Algorithmen eine bemerkenswerte Vielseitigkeit und ein breites Anwendungsspektrum aufweisen, bleibt ihre Nutzung im Kontext der Quantenschaltungs-Synthese ein bemerkenswertes Interessengebiet. Angesichts der erheblichen Herausforderung, die der riesige Suchraum bei der Erstellung von Quantenschaltungen darstellt, ist die theoretische Eignung genetischer Algorithmen offensichtlich, insbesondere in Anbetracht ihrer inhärenten Erkundungsfähigkeit. Zusätzlich zur Nutzung von Quantenalgorithmen zur Erzielung bis zu exponentieller Laufzeitvorteile erfordert all diese Algorithmen die Vorbereitung spezifischer Zustände, um besagte Vorteile zu gewähren. Daher ist es entscheidend, in der Lage zu sein, spezifische Zustände zu erstellen, selbst wenn das Wissen über die zugrunde liegenden Schaltungen fehlt. Ein bemerkenswerter Zustand ist der Greenberger-Horne-Zeilinger (GHZ)-Zustand, der die Superpositions- und Verschränkungs-Eigenschaften der Quantencomputing vereint. Dementsprechend wird diese Schaltung in dieser Arbeit als Zielzustand zur Reproduktion verwendet, und zwei zusätzliche Schaltungen mit unterschiedlichen Zuständen werden eingesetzt, um die allgemeine Anwendbarkeit dieses Ansatzes zu veranschaulichen. Außerdem wird der genetische Algorithmus nicht nur auf dem Simulator, sondern auch auf der IONQ Aria-1 Quantum Processing Unit (QPU) ausgeführt. Diese Arbeit beleuchtet zudem die Unterschiede zwischen dem populationsbasierten und dem inselbasierten Ansatz. Diese Ansätze unterscheiden sich darin, ob die Individuen Teil einer einzelnen Population sind oder ob sie sich separat in kleinere Gruppen entwickeln, die über mehrere Inseln verteilt sind und ausschließlich durch Migration zwischen den Inseln miteinander interagieren. Diese Arbeit liefert Beweise für die Überlegenheit des inselbasierten Ansatzes im Vergleich zum populationsbasierten Ansatz für den GHZ-Zustand sowie die beiden anderen Schaltungen. Ferner wird demonstriert, dass die Einschränkungen der Hardwareausführung erfüllt werden konnten, indem der inselbasierte Ansatz auf der IONQ Aria-1 QPU verwendet wurde, um einen Lösungskandidaten für den GHZ-Zustand zu erzeugen. Darüber hinaus zeigt die Herkunft der generierten Lösungskandidaten die Wirksamkeit des genetischen Algorithmus selbst und auch die erhöhte Vielfalt der verschiedenen Ansätze.
Betreuer: Jonas Stein, Maximilian Zorn, Claudia Linnhoff-Popien
Quantum Reinforcement Learning via Parameterized Quantum Walks
Masterarbeit (Oktober 2024)
Autor: Sabrina Egger
Abstract:
Random Walks finden in verschiedenen Forschungsbereichen wie der Informatik, der Psychologie, dem Finanzwesen oder der Mathematik Anwendung, da sie ein grundlegendes Konzept der Wahrscheinlichkeitstheorie und Stochastik darstellen. Herkömmliche Computer stoßen jedoch schnell an ihre Grenzen hinsichtlich der Rechenkomplexität, so dass andere Wege zur effizienten Lösung komplexer Probleme wie das Quantencomputing erforderlich sind. Quantum Walks, das Quantenäquivalent zum klassischen Random Walk, nutzen Quanteneffekte wie Überlagerung und Verschränkung, um effizienter zu sein als ihre klassischen Gegenstücke. Dennoch stellt die Ausführung von Programmen auf Quantenrechnern in der nahen Zukunft aufgrund der hohen Fehlerraten, des Rauschens und der Anzahl der verfügbaren Qubits eine gewisse Herausforderung dar. Für eine große Anzahl von Graphproblemen wirkt die Kodierung mit Gray Code Directed Edges (GCDE) diesen Problemen entgegen, indem sie die erforderliche Anzahl von Qubits durch eine effiziente Darstellung von bipartiten Graphen unter Verwendung von Gray Code reduziert. Diese Arbeit untersucht Random Walks in Grid Worlds und Glued Trees unter Verwendung klassischer Reinforcement Learning Strategien wie Proximal Policy Optimization oder Deep Q-learning Networks. In einem weiteren Schritt werden die Umgebungen mit effizienter GCDE-Kodierung neu aufgebaut. Die Umgebungen werden in parametrisierte Quantenschaltkreise übersetzt, deren Parameter durch den Agenten optimiert und gelernt werden. Der Beitrag dieser Arbeit beinhaltet die Anwendung der effizienten GCDE-Kodierung in Quantenumgebungen und einen Vergleich zwischen einem Quanten- und einem Random-Walker hinsichtlich Trainingszeiten und Zieldistanzen. Außerdem werden die Auswirkungen unterschiedlicher Startpositionen beim Training und bei der Auswertung berücksichtigt.
Betreuer: Jonas Stein, Michael Kölle, Claudia Linnhoff-Popien
CUAOA: A Novel CUDA-Accelerated Simulation Framework for the Quantum Approximate Optimization Algorithm
Masterarbeit (September 2024)
Autor: Jonas Felix Blenninger
Abstract:
Der Quantum Approximate Optimization Algorithm (QAOA) ist ein bekannter Quantenalgorithmus, der entwickelt wurde, um Näherungslösungen für kombinatorische Optimierungsprobleme zu finden. In der heutigen Zeit, in der Quanten-Hardware durch Rauschen und begrenzte Verfügbarkeit von Qubits eingeschränkt ist, bleibt die Simulation von QAOA für die Forschung unerlässlich. Bestehenden Simulations-Frameworks auf dem neuesten Stand der Technik weisen lange Ausführungszeiten auf oder es mangelt ihnen an umfassender Funktionalität, Benutzerfreundlichkeit und Vielseitigkeit, so dass die Anwendenden häufig wesentliche Funktionen selbst implementieren müssen. Darüber hinaus sind diese Frameworks auf Python beschränkt, was ihren Einsatz in sichereren und schnelleren Sprachen wie Rust beschränkt, welche unter anderem fortgeschrittene Parallelisierungsmöglichkeiten bieten. In dieser Masterarbeit wird die Entwicklung eines neuen GPU-beschleunigten QAOA-Simulationsframeworks vorgestellt, welches das NVIDIA CUDA-Toolkit nutzt. Dieses Framework bietet eine vollständige Schnittstelle für QAOA-Simulationen, die die Berechnung von (exakten) Erwartungswerten, den direkten Zugriff auf den Zustandsvektor, schnelles Sampling und hochleistungsfähige Optimierungsmethoden unter Verwendung der effizientesten bekannten Methode für die Gradientenberechnungstechnik ermöglicht. Das hier vorgestellte Framework ist für die Verwendung in Python und Rust konzipiert und bietet so Flexibilität für die Integration in eine Vielzahl von Anwendungen, einschließlich solcher, die schnelle Algorithmusimplementierungen erfordern und den QAOA als Kern nutzen. Ein solcher Algorithmus, insbesondere der QAOA 2 , ein Divide-and-Conquer-Algorithmus, wird mit dem neuen QAOA-Simulationsframework implementiert, um dessen Verwendung in einer möglicherweise parallisierten Anwendung zu zeigen. Die Leistung des neuen QAOA-Simulations-Frameworks wird mit Hilfe verschiedener Zufallsgraphen für das MaxCut problem rigoros getestet und mit den aktuellen State-of-the-Art-Quantenschaltungs-Simulations-Frameworks und einem spezialisierten Simulator für den QAOA verglichen. Die Auswertung zeigt, dass der entwickelte Simulator die aktuellen State-of-the-Art-Simulatoren in der Laufzeit mit einer Beschleunigung von bis zu mehreren Größenordnungen übertreffen kann. Darüber hinaus werden die Fähigkeiten des Frameworks im Rahmen des Divide-and-Conquer-Algorithmus evaluiert, der den QAOA als Kernstück verwendet. Diese Implementierung übertrifft die Referenzimplementierung unter Verwendung der aktuellsten Simulatoren für eine große Probleminstanz deutlich.
Betreuer: Jonas Stein, Maximilian Zorn, Claudia Linnhoff-Popien
Explainable Time Series Forecasting using exogenous variables – How weather affects the stock market
Bachelorarbeit (September 2024)
Autor: Het Dave
Abstract:
Der Klimawandel ist real und beeinflusst das Wetter weltweit. Angesichts der sich ändernden Wetterbedingungen zielt diese Arbeit darauf ab, zu verstehen, wie Wetter genutzt werden kann, um langfristige Marktveränderungen zu modellieren. Ziel ist es, zu erfassen, wie die Fähigkeit zur Wettervorhersage dazu beitragen kann, Risiken während akuter Wetterkrisen und -störungen zu mindern und die am stärksten vom Wetter betroffenen Branchen zu arbitrage, um den Markt zu stabilisieren. Moderne Deep-Learning-Methoden wie Temporal Fusion Transformers (TFTs) und Neural Hierarchical Interpolation for Time Series Forecasting (N-HiTS) sind erforderlich, um statische und historische exogene Variablen wie Wetter- und Standortdaten einzubeziehen. Daher nutze ich die bestehende, aktuelle N-HiTS-Architektur, da sie in der Langzeitvorhersage andere Modelle übertrifft, indem sie Hierarchical Interpolation und Multi-Rate-Data Sampling integriert und eine große durchschnittliche Genauigkeitsverbesserung gegenüber den neuesten Transformer-Architekturen bietet, während die Rechenzeit um eine Größenordnung reduziert wird. Ich modifiziere dann diese bestehende Architektur, indem ich einen neuartigen Ansatz entwickle, der Wetterdaten in das Modell integriert, sodass es besser für Aktienkurse und Wetterkovariaten geeignet ist. Diesen neuartigen Ansatz nenne ich WiN-HiTs – Weather induced N-HiTS – und zeige, dass Wetterkovariaten die Marktbewegungen in bestimmten Sektoren wie Versorgungsunternehmen und Materialien über einen langen Vorhersagehorizont besser prognostizieren können. Diese Forschung betont auch die Bedeutung der Vorhersage-Dekomposition in KI-Modellen, insbesondere im finanziellen und Aktienmarkt-Kontext, wo das Verständnis des Entscheidungsprozesses entscheidend ist. Die WiN-HiTS-Architektur ermöglicht die Trennung der Stapelvorhersagekomponenten der Zeitreihenprognose, was uns hilft zu interpretieren, wie verschiedene Wetterfaktoren zu Aktienkursschwankungen beitragen und wie diese Faktoren ausgewählt werden. In dieser Arbeit verwende ich einen vielfältigen Datensatz zur Bewertung, einschließlich historischer Wetter- und Aktienmarktdaten aus mehreren geografischen Regionen und Branchen der S&P500-Aktien. Vergleichsbaselines umfassen traditionelle Modelle wie AutoArima sowie moderne maschinelle Lernansätze wie Transformer-basierte Modelle (TFT) und N-HiTS selbst. Die Ergebnisse zeigen, dass WiN-HiTS in den meisten Sektoren auf Augenhöhe mit diesen Modellen arbeitet und in bestimmten Sektoren besser abschneidet. Zu den Key Performance Indicators (KPIs), die zur Bewertung der Vorhersagegenauigkeit verwendet werden, gehören der mittlere absolute Fehler (MAE), der Root Mean Squared Error (MSE) und der mittlere absolute prozentuale Fehler (MAPE). Die Bewertung dieser Arbeit stellt die Robustheit und Praktikabilität des vorgeschlagenen WiN-HiTS-Modells in realen finanziellen Vorhersageszenarien sicher.
Betreuer: Jonas Stein, Claudia Linnhoff-Popien
A Path Towards Quantum Advantage for the Unit Commitment Problem
Bachelorarbeit (September 2024)
Autor: David Fischer
Abstract:
Diese Arbeit stellt eine Lösung für das Unit-Commitment-Problem (UCP) im Bereich des Energienetzmanagements vor. Dabei handelt es sich um ein Optimierungsproblem, bei dem ein Gleichungssystem gelöst wird, um die Kosten für eine gegebene Lösung zu berechnen. Wir charakterisieren das UCP als ein Mixed-Integer Nonlinear Programming (MINLP)-Problem und lösen es mit Hilfe eines Quantensimulations-basierten Optimierungsansatzes (QuSO), wobei dieser eine Klasse von äquivalenten Problemen definiert, die mit dem vorgeschlagenen Algorithmus lösbar sind. Durch die Modellierung des Energienetzes in einem speziellen Graph erhalten wir hilfreiche Erkenntnisse über die Struktur und die Eigenschaften der Suszeptanzmatrix. Wir nutzen approximative Randbedingungen für den Gleichstrom (DC) in diesem Modell. Die vorgeschlagene Quantenroutine beginnt mit der Invertierung der reduzierten Suszeptanzmatrix mittels Quantum Singular Value Transformation (QSVT) unter Verwendung eines speziellen Matrixinversionspolynoms. Eine Quantum Phase Estimation Routine wird zusammen mit einem zusätzlichen QSVT Verfahren verwendet, um die Kostenfunktion zu konstruieren, die dann mit dem Quantum Approximate Optimization Algorithm (QAOA) optimiert wird. Dieser hybride quantenklassische Ansatz nutzt das Potenzial quantenmechanischer Verfahren, um die Effizienz bei der Lösung komplexer Optimierungsprobleme erheblich zu verbessern. Im Rahmen unserer Analyse bewerten wir die algorithmische Komplexität und demonstrieren das beachtliche Potenzial dieses Ansatzes zur Lösung von QuSO-Problemen. Besonders hervorzuheben ist, dass die QSVT-basierte Matrixinversion die Zeitkomplexität in Fällen exponentiell verringern kann, in denen klassische Methoden schlecht mit der Größe des Problems skalieren. Diese Reduktion der Komplexität könnte die Echtzeitoptimierung großer Energienetze ermöglichen und dadurch sowohl die betriebliche Effizienz als auch die Zuverlässigkeit signifikant steigern.
Betreuer: Jonas Stein, Philipp Altmann, Claudia Linnhoff-Popien
Evolutionäre Operatoren zur Optimierung von Prompts für die Codegenerierung durch Large Language Models
Bachelorarbeit (September 2024)
Autor: Amelie Johanna Trautwein
Abstract:
In dieser Bachelorarbeit soll die Anwendung evolutionärer Algorithmen zur Optimierung der Codegenerierung durch Large Language Models (LLMs) untersucht werden. Die Methodik umfasst die Entwicklung eines evolutionären Algorithmus, der spezifische Strategien für Selektion, Crossover und Mutation einsetzt, sowie die Verwendung verschiedener Prompt-Designs und deren Einfluss auf den Optimierungsprozess. Zur Evaluierung der entwickelten Methodik wird WizardCoder verwendet, ein feingetuntes LLM basierend auf StarCoder. Um die Wirksamkeit der optimierten Prompts zu testen, werden die Benchmark-Datensätze HumanEval, MBPP, sowie der Datensatz PythonSaga genutzt. Diese Datensätze enthalten verschiedene Python Programmieraufgaben, die als Maßstab für die Bewertung der generierten Lösungen dienen. Die in dieser Arbeit entwickelten und getesteten Techniken sollen dazu beitragen, die Fähigkeiten von LLMs weiter zu verbessern und deren Einsatzmöglichkeiten in der Praxis zu erweitern. Besondere Aufmerksamkeit wird dabei auf die Entwicklung und Implementierung der evolutionären Operatoren gelegt, die durch iterative Verbesserungsprozesse die Qualität der generierten Code-Lösungen maximieren sollen. Ziel ist es, evolutionäre Operatoren zu entwickeln, die die Eingabeprompts für LLMs optimieren und somit deren Anwendung zur Codegenerierung verbessern.
Betreuer: Philipp Altmann, Maximilian Zorn, Claudia Linnhoff-Popien
Measuring Relatedness in Evolutionary Algorithms via Superfluous Genes
Bachelorarbeit (August 2024)
Autor: Paulin Anwander
Abstract:
In dieser Arbeit bewerten wir die Nutzung überflüssiger Gene zur Messung der Verwandtschaft in evolutionären Algorithmen (EA). Es ist allgemein anerkannt, dass EA, die nicht nur auf Fitness, sondern auch auf die Vielfalt der Populationen optimieren, in der Regel bessere Leistungen erbringen. Eine mögliche Definition für Vielfalt ist die Verwandtschaft der Individuen im phylogenetischen Baum, die jedoch komplex zu berechnen ist. Dies motiviert die Idee, die Verwandtschaft basierend auf überflüssigen Genen zu schätzen. Diese Gene stellen im Wesentlichen ein zweites Genom dar, das parallel zum Hauptgenom ohne Selektionsdruck evolviert. Sie werden durch Bitstrings (t-Bits) repräsentiert, was Berechnungen darauf günstig macht. Um die Vielfalt einer Population abzuschätzen, werden die t-Bits der Individuen bitweise verglichen: Eine hohe Anzahl unterschiedlicher Bits deutet auf eine geringe Verwandtschaft hin, während viele gleiche Bits auf eine hohe Verwandtschaft hindeuten. Die anfängliche Machbarkeit dieses Ansatzes wurde bereits gezeigt. Zur Bewertung der Schätzgenauigkeit führen wir EA durch, bei denen die tatsächliche und die auf t-Bits basierende Verwandtschaft von Individuenpaaren protokolliert wird. Unsere experimentellen Ergebnisse zeigen, dass die auf t-Bits basierte Verwandtschaftsschätzung signifikant mit der tatsächlichen Verwandtschaft korreliert. Wir bewerteten mehrere auf t-Bits basierende Funktionen zur Verwandtschaftsschätzung und stellten fest, dass die Verwendung der Anzahl gleicher t-Bits ohne Nachbearbeitung in den meisten Bereichen am besten funktionierte. Wir fanden jedoch auch Situationen, in denen andere Funktionen besser abschneiden. Zusätzlich bewerteten wir, wie Faktoren wie Populationsgröße, Anzahl der t-Bits, Mutationsverhalten und der Typ des Optimierungsproblems die Qualität der t-Bit-Schätzung beeinflussen. In den meisten Fällen übertraf die auf t-Bits basierende Verwandtschaftsschätzung nicht die auf dem Genom basierende Schätzung, lieferte jedoch dennoch zuverlässige Ergebnisse.
Betreuer: Thomas Gabor, Maximilian Zorn, Claudia Linnhoff-Popien
Exploring QuGANs for realistic graph generation – an exploratory study
Masterarbeit (Juli 2024)
Autor: Florian Burger
Abstract:
Generative Adversarial Networks (GANs) haben für ihre Fähigkeiten bei der Erzeugung realistischer Bilder große Anerkennung gefunden. Die Anwendung von GANs erstreckt sich jedoch auch auf die Generierung verschiedener Formen von synthetischen Daten, einschließlich eines wachsenden Interesses an der Graphengenerierung. Graphen dienen als vielseitige Darstellungen für zahlreiche Szenarien, wie Computernetzwerke, molekulare Strukturen und Infrastrukturlayouts. Folglich hat sich die Generierung künstlicher, aber realistischer Problemfälle für Tests und Entwicklung zu einem bedeutenden Forschungsgebiet entwickelt. Diese Arbeit zielt darauf ab, Quantum GANs (QuGANs) zu verbessern, um synthetische Netzwerkgraphen zu erzeugen, die reale Karteninstanzen genau imitieren. Diese generierten Graphen können zur Lösung verschiedener Routing-Probleme verwendet werden, darunter das Traveling Salesman Problem (TSP) und das Capacitated Vehicle Routing Problem (CVRP). Unser experimenteller Rahmen nutzt eine GAN-Architektur, um mehrere Szenarien zu erforschen, die in zwei Hauptgruppen eingeteilt sind: eine, die einen konventionellen klassischen Generator und Diskriminator verwendet, und die andere, die einen Quantengenerator mit einem klassischen Diskriminator integriert. Das Hauptziel besteht darin, die Leistung von QuGANs bei der Bewältigung der für diese Probleme relevanten Herausforderungen der Netzwerkgenerierung zu erhöhen. Angetrieben durch die Notwendigkeit von Instanzen, die die Dynamik der realen Welt widerspiegeln, schlägt diese Forschung eine strategische Methodik zur Erzeugung von Instanzen vor, die realistische geografische Konfigurationen und operative Arbeitslasten widerspiegeln. Klassische GANs, die für ihre Fähigkeit bekannt sind, Datenmuster zu replizieren, die die ursprüngliche Verteilung nachahmen, werden als geeignet angesehen. Unser Ansatz geht jedoch über die klassischen Methoden hinaus, indem die QuGANs den Generierungsprozess durch eine quantenmechanische Methode steuern, indem sie die einzigartigen Eigenschaften von Quantensystemen, wie Überlagerung, Interferenz und Verschränkung, nutzen. Diese Forschung zielt darauf ab, das Potenzial von QuGANs bei der Erzeugung realistischer Instanzen zu demonstrieren, die für unseren Problembereich relevant sind. Die dem Quantencomputing innewohnenden Quanteneigenschaften bieten neuartige Möglichkeiten für die Erzeugung synthetischer Netzwerke. Wir versuchen, ihre jeweiligen Vorteile und Grenzen durch eine vergleichende Analyse zwischen klassischen GANs und QuGANs aufzuzeigen. Unsere experimentellen Ergebnisse zeigen, dass klassische GANs eine minimale Verbesserung bei der Erzeugung realistischer Graphen mit niedrigeren Parametern aufweisen, während QuGANs eine deutliche Verbesserung der Lernkurve und der Anzahl der erzeugten realistischen Graphen zeigen. Diese Ergebnisse deuten darauf hin, dass QuGANs das Potenzial haben, klassische Methoden unter bestimmten Bedingungen zu übertreffen, auch wenn weitere Untersuchungen erforderlich sind, um Stabilität und rechnerische Herausforderungen zu bewältigen.
Betreuer: Tobias Rohe, Michael Kölle, Claudia Linnhoff-Popien
