Eine Hochzeit zu organisieren ist eine große Herausforderung. Wie teilt man beispielsweise 120 Gäste auf Tische zu je sechs Personen auf, sodass Familien und Freundesgruppen möglichst nicht auseinandergerissen werden und niemand unter Fremden sitzt? Was nach einer langen Tüftelei für das Hochzeitspaar mit hoffentlich fundiertem Insiderwissen über die Gästeschar klingt, eignet sich für Sebastian Lehner von der JKU Linz auch gut als Beispiel für eine Aufgabe der kombinatorischen Optimierung. "Problemstellungen dieser Art haben enorm viele Lösungsmöglichkeiten", erklärt der Wissenschafter, der am Institute for Machine Learning & LIT AI Lab tätig ist. "Möchte man die Suche nach einem Optimum einem Computer überantworten, werden sie schnell sehr rechenaufwendig."

Team um Sepp Hochreiter

Künstliche Intelligenz (KI) ermöglicht nun einen neuen vielversprechenden Ansatz, um gute Lösungen für ein Problem dieser Art zu errechnen. "Im Rahmen eines sogenannten nichtüberwachten Lernprozesses können künstliche neuronale Netzwerke aus anfänglich schlechten Ergebnissen lernen, um immer bessere zu erzeugen", sagt Lehner. Gemeinsam mit seinem Kollegen Sebastian Sanokowski und dem Institutsleiter und KI-Pionier Sepp Hochreiter arbeitet er daran, Systeme dieser Art weiterzuentwickeln.

In einer vor kurzem veröffentlichten Publikation konnten die Forschenden relevante Fortschritte vermelden. "Unsere Grundlagenforschung könnte dazu beitragen, die Routenplanung in der Logistik zu verbessern oder Proteinstrukturen vorherzusagen und so bei der Suche nach neuen medizinischen Wirkstoffen zu helfen", gibt Lehner Beispiele.

Die Linzer Forscher nutzen für ihren Ansatz sogenanntes Annealing – eine Vorgangsweise, die Anleihen an der Physik nimmt. "Wenn heißes, geschmolzenes Metall abkühlt und erstarrt, finden die Atome automatisch in ein Kristallgitter zusammen, in dem das Energieniveau zwischen den Teilchen möglichst niedrig ist. Die Atome lösen dabei ein kombinatorisches Optimierungsproblem", erläutert der KI-Experte.

Lehrplan für die KI

"Informatiker beschäftigen sich bereits lange damit, diesen Mechanismus zu simulieren und mit künstlicher Intelligenz möglichst effizient auf Rechnern nachzubilden." Ein Problem dabei ist, dass man anfangs nicht weiß, ob ein zufällig gewählter Lösungsversuch ein unbrauchbares oder ein Ergebnis nahe am Optimum bringen wird. Gute Ansätze, die im Sinne der Metallmetapher ein niedriges Energieniveau zeigen, sind seltener und schwieriger zu finden.

Lehner und sein Team haben nun eine neue Methode gefunden, um mit einer Art Lehrplan für die künstliche Intelligenz die Annäherung ans Optimum zu beschleunigen. Im Zuge eines sogenannten Curriculum-Learning für Annealing-Systeme werden Optimierungsaufgaben in Relation zueinander untersucht, um der KI sukzessive immer schwieriger zu lösende Aufgabenstellungen unterbreiten zu können. "Wir haben einen mathematisch fundierten Weg entwickelt, um gut einschätzen zu können, wie schwer es ist, Lösungsstrategien für diese Probleme zu erlernen", resümiert Lehner.

Von ChatGPT lernen

Gleichzeitig haben die KI-Experten ein Gruppierungssystem eingeführt, um die Kalkulation zu beschleunigen. Um beim Problem mit dem Hochzeitssitzplan zu bleiben: Es gibt wohl immer wieder kleine Gruppen – Paare, beste Freunde, Geschwister –, die man besser auf keinen Fall trennen sollte und die bei der Tischplanerstellung immer gemeinsam von Tisch zu Tisch verschoben werden. Ähnlich ist auch die Methode zu verstehen, die Lehner "Subgraph Tokenization" nennt. "Kombinationen, die als besonders gut erkannt werden, werden wiederverwendet. Mit einem ähnlichen Ansatz arbeiten beispielsweise auch Sprachmodelle à la ChatGPT: Buchstabenfolgen, die oft vorkommen wie etwa die Endung '-ung', werden vorgruppiert und gemeinsam platziert", erläutert der Wissenschafter.

Eine vergleichsweise gute Lösung in kurzer Zeit parat zu haben ist nicht der einzige Vorteil der nichtüberwacht lernenden KI-Modelle, die also keine vorgegebenen Lösungen als Trainingsdaten benötigen. Mit jeder Lösung, die sie in der Lernphase hervorbringt, erhöht sich potenziell die Qualität derselben, sagt Lehner. "Lösungen, die von klassischen Systemen stammen, sind nach 10.000 Anwendungen nicht schlauer oder effizienter geworden. Die KI-Modelle werden dagegen mit jeder Berechnung besser."

Gleichzeitig bieten sie eine bisher ungekannte Flexibilität. Lehner: "Wenn beim Beispiel mit der Hochzeit fünf Leute absagen und dafür fünf andere kommen, müsste ein klassisches System wieder von vorne mit der Optimierungsaufgabe beginnen. Die KI kann für die neue Aufgabe dagegen nutzen, was sie bereits gelernt hat."

Effizientere Computer

Eine Anwendung des Optimierungsverfahrens, die dem KI-Experten für die Zukunft vorschwebt, könnte zu besser geplanter und deshalb effizienterer Computerhardware führen: "Die Gestaltung von Chips und Platinen ist vielfältigen Einschränkungen unterworfen, die etwa aus den Erfordernissen der Konnektivität oder dem Temperaturmanagement resultieren. Die Bauteile dürfen nicht zu heiß werden, weil sonst die Leistung gedrosselt werden muss", erklärt Lehner.

"Man könnte also KI-Modelle schaffen, die ein Computersystem auf möglichst hohe Leistung, besonders gute Energieeffizienz oder geringen Platzbedarf hin optimieren." Natürlich wäre auch eine KI für perfekte Hochzeitssitzpläne locker umsetzbar. Diese Aufgabe wird wohl aber auch in Zukunft den gestressten Brautpaaren vorbehalten bleiben. (Alois Pumhösel, 23.3.2024)