Die neue KI-gestützte Technologie entwickelt eigenständig Algorithmen für komplexe Kombinatorik- und Optimierungsprobleme, wie sie beispielsweise bei der optimalen Planung von Industrieanlagen und Produktionsabläufen auftreten und erzielt dabei deutlich bessere Ergebnisse als bisherige Verfahren für „harte Probleme“ der industriellen Praxis. Für die Erfindung, die einen wesentlichen Vorwärtsschritt auf dem Weg zum „heiligen Gral des Problemlösens“ ermöglicht, wurde bereits ein Patent eingereicht.
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össe 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 Kolleginnen und Kollegen 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 grossen 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.“
Check Mate ist ein Tool, das sich in das Open-Source-Framework für Code-Evolution Open Evolve 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. Check Mate 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 Check Mate 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 Check Mate 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.”