Forschende der Universität Klagenfurt haben mit „CheckMate“ ein KI-gestütztes System zur automatisierten Lösung komplexer Kombinatorik- und Optimierungsprobleme entwickelt. Die Technologie generiert eigenständig Algorithmen und liefert laut Forschungsteam bessere Ergebnisse als bisherige Verfahren bei industriellen Problemstellungen.
Foto: KK
CheckMate-Team v.l.n.r.: Francesco Zuccato, Benedetta Strizzolo (auf der Leinwand), Konstantin Schekotihin, Veronika Semmelrock, Patrick Rodler und Gerhard Friedrich
Ein Forschungsteam der Universität Klagenfurt arbeitet an neuen Verfahren zur automatisierten Lösung sogenannter „harter Probleme“ in Industrie und Logistik. Mit dem System „CheckMate“ haben die Forschenden nun eine Technologie vorgestellt, die eigenständig Algorithmen für komplexe Kombinatorik- und Optimierungsaufgaben generieren kann. Für die Entwicklung wurde bereits ein Patent eingereicht.
Zu den möglichen Einsatzfeldern zählen laut Universität unter anderem Eisenbahnsicherungssysteme, die Planung von Industrieanlagen oder Optimierungsfragen in der Logistik. In diesen Bereichen gehe es darum, aus einer sehr großen Zahl möglicher Lösungen eine möglichst optimale Variante zu finden.
Sudokus mit 9 Reihen und 9 Spalten konnten Rechenprogramme bereits vor mehr als zwanzig Jahren problemlos lösen. „Das Kernproblem liegt aber in der gewaltigen Explosion der Lösungsmöglichkeiten, sobald das Spielbrett erweitert wird“, erklärt Gerhard Friedrich, Professor am Institut für Artificial Intelligence und Cybersecurity der Universität Klagenfurt und Mitglied des Boards of Directors im vom FWF geförderten Cluster of Excellence Bilateral AI. Nimmt die Anzahl an Reihen, Spalten und möglichen Zahleneinträgen zu, z. B. auf 100.000 Reihen, Spalten und Zahlen, was das Problem in seiner Größe mit praktischen Anwendungen in der Industrie vergleichbar macht, so sind aktuelle allgemeine Problemlösungsverfahren überfordert. Der Speicherbedarf sprengt alle physikalischen Möglichkeiten und man würde Tausende von Jahren auf eine Antwort warten müssen. Wenn nun zusätzliche Restriktionen dazukommen, beispielsweise erforderliche Muster bei den genutzten Zahlen, vergleichbar mit zusätzlichen Anforderungen in industriellen Problemen, verhärtet sich das Problem noch einmal dramatisch.
Gerhard Friedrich arbeitet mit seinen Kolleg:innen schon seit vielen Jahren an Lösungen dieser so genannten „harten Probleme“, bei denen der Mensch mit seinen heuristischen Problemlösungsfähigkeiten gegenüber der Maschine bis dato als überlegen galt. Anwendungsfelder dafür gibt es viele: Von Eisenbahnsicherungssystemen bis hin zur möglichst optimalen Planung von Industrieanlagen oder Optimierungsfragen in der Logistik – in all diesen Feldern gilt es, aus einer oft unüberschaubar großen Menge von potenziellen Lösungen eine möglichst optimale zu finden.
Einem Team von Forscher:innen an der Universität Klagenfurt – bestehend aus Veronika Semmelrock, Benedetta Strizzolo, Francesco Zuccato, Patrick Rodler, Konstantin Schekotihin und Gerhard Friedrich – ist es nun gelungen, einen wesentlichen Beitrag für die Realisierung des „heiligen Grals des Problemlösens“ zu finden – der Mensch formuliert ein Problem, der Computer löst es. Mit CheckMate stellen sie nun eine automatisierte evolutionäre Codegenerierung für kombinatorische Probleme inklusive Optimierung vor. Für diese neue, für die Industrie hoch relevante Technologie, die auf der prestigeträchtigen International Joint Conference on Artificial Intelligence 2026 dem Fachpublikum vorgestellt wird, wurde kürzlich auch ein Patent eingereicht. Eine Besonderheit im Team kommt hinzu: Veronika Semmelrock und Francesco Zuccato sind Doktoratsstudierende der Universität Klagenfurt und Benedetta Strizzolo ist Masterstudentin der Universität Udine, die im Rahmen einer Projektarbeit in das Team der Universität Klagenfurt integriert wurde.
„In den letzten Jahren mussten wir erkennen, dass es uns Menschen nicht gelingt, Werkzeuge für solche schwierigen Probleme zu entwickeln, die der Vision einer KI, die tatsächlich eigenständig harte Probleme löst, näherkommen“, erklärt Gerhard Friedrich. Er führt weiter aus: „Zuletzt gab es aber entscheidende Durchbrüche in der automatisierten Softwareentwicklung, die den Weg für völlig neue, KI-gestützte Programmierprozesse geebnet haben. Ein vielversprechendes Beispiel ist die Code-Evolution, die Programme auf Basis von LLMs automatisch generiert, welche von Menschen entwickelte Softwarelösungen bereits in einigen Fällen übertreffen konnten. Bei der Anwendung auf komplexe Kombinatorik- und Optimierungsprobleme, wie wir sie aus der Industrie kennen, ist es aber alles andere als trivial, Programme zu generieren, die diese effizient und zuverlässig lösen.“
CheckMate ist ein Tool, das sich in das Open-Source-Framework für Code-Evolution OpenEvolve integrieren lässt. Eine strenge Korrektheitsprüfung von Lösungen auf Basis der Logik, systematische Evaluierung der Programmeffizienz sowie kontinuierliches Feedback führen dazu, dass aus einem initial leeren Programm in einem schrittweisen Verfeinerungsprozess hochqualitative Algorithmen zustande kommen. CheckMate muss nicht vorgegeben werden, wie Lösungen berechnet werden sollen — es braucht dafür lediglich das Was, also eine Beschreibung, was eine Lösung ist, und eine kleine Menge von Beispielinstanzen. Anhand von sehr großen und komplexen Sudokus veranschaulicht, würde dies bedeuten, dass man CheckMate lediglich die Spielregeln beschreibt, woraufhin es automatisch einen Lösungsalgorithmus für beliebige vorgegebene Spielbretter generieren kann. „Unserem Team ist es nun gelungen zu zeigen, dass die mit CheckMate generierten Programme die aktuell führenden Technologien übertreffen und bessere Lösungen für harte Probleme mit direkter Industrierelevanz erzielen, als es bisher möglich war. Insbesondere hat es CheckMate auch ermöglicht, besonders harte, bisher ungelöste Probleme erstmalig zu lösen. Wir scheinen also in das Zeitalter eingetreten zu sein, in dem KI auch im Lösen komplexer Probleme dem Menschen zumindest ebenbürtig ist“, fasst Gerhard Friedrich die Ergebnisse zusammen:
“LLMs + Logic + Evolution = Superhuman Programming.”
