Weniger gierige Quanten-Ansätze zur Generierung von Koalitionsstrukturen in Induzierten Subgraph-Spielen

Weniger gierige Quanten-Ansätze zur Generierung von Koalitionsstrukturen in Induzierten Subgraph-Spielen

Abstract:

Die Energiewende ist einer der wichtigsten Schritte im Kampf gegen den Klimawandel, den viele Nationen aktuell angehen. Jedoch stellt uns diese Umstellung auf 100 % erneuerbare Energien vor Herausforderungen bezüglich der erfolgreichen Steuerung von Stromnetzen. Ein Lösungsansatz ist hier das sinnvolle Zerlegen dieser Netze in Kleingruppen sogenannter Prosumenten, die Microgrids. Diese sinnvolle Zerlegung stellt jedoch ein schwieriges Optimierungsproblem da, das in etwas vereinfachter Form formalisiert werden kann als ein Problem der Koalitionsstrukturengenerierung in Induzierten Subgraph-Spielen. Hierbei versucht man einen vollvermaschten, ungerichteten, gewichteten Graphen so in Subgraphen zu zerlegen, dass die Summe über die Gewichte der in diesen Subgraphen enthaltenen Kanten maximiert wird. Zur Lösung dieses Problems wurden in den letzten Jahren auch einige Quanten-Algorithmen publiziert, wovon der Neueste ein effizienter, aber gieriger Ansatz namens GCS-Q ist. In dieser Arbeit werden diverse weitere, weniger gierige Quantum Annealing (QA)-basierte Algorithmen zur Lösung des Problems entworfen und mit GCS-Q verglichen, um festzustellen, ob einer dieser Ansätze eine bessere Lösungsqualität erzielen kann. Experimente auf drei verschiedenen Solvern – der QBSolv- Software, dem D-Wave Advantage 4.1 Quantum Annealer, und dem Algorithmus QAOA auf dem Qiskit Quantensimulator – ergeben, dass dies auf der aktuellen echten Quanten- Hardware nicht möglich ist. Mit der QBSolv-Software findet jedoch ein Großteil der neu entwickelten Ansätze bessere Lösungen, insbesondere der 4-split iterative R-QUBO Algorithmus, der auf dem verwendeten Datensatz alle Optima findet. Da seine Laufzeit zudem gut mit der Graphgröße skaliert, scheint dies ein vielversprechender Ansatz für zukünftige Forschung an der Problemstellung zu sein.

Autor/in:

Daniëlle Schuman

Betreuer:

Studentische Abschlussarbeit | Veröffentlicht Mai 2024 | Copyright © QAR-Lab
Anfragen zu dieser Arbeit an die Betreuer