Deep Learning für komplexe diskrete Optimierungsprobleme

Doktorand Jonathan Pirnay und Prof. Dr. Dominik Grimm von der Hochschule Weihenstephan-Triesdorf (HSWT) haben neue maschinelle Lernverfahren entwickelt, um komplexe diskrete Optimierungsprobleme mit Hilfe neuronaler Netze zu lösen.

Die Grundidee ist, ein neuronales Netz nicht mit vorgegebenen Lösungen (Supervised Learning) oder Belohnungen (Reinforcement Learning) zu trainieren, sondern das Netz sich mit seinen eigenen Vorhersagen schrittweise selbst in einem iterativen Prozess verbessern zu lassen. Zu Beginn ist das neuronale Netz untrainiert. Indem das Netz kontinuierlich eigene Lösungen generiert und diese Lösungen als “Expertenwissen” betrachtet, lernt es, sich schrittweise selbst zu verbessern. Die Arbeit „Self-Improvement for Neural Combinatorial Optimization“ https://openreview.net/forum?id=agT8ojoH0X wurde im Juni 2024 in der Fachzeitschrift „Transactions on Machine Learning Research“ veröffentlicht und mit einem Featured-Zertifikat für Publikationen höchster Qualität ausgezeichnet.

Die jüngste Arbeit „Take a Step and Reconsider: Sequence Decoding for Self-Improved Neural Combinatorial Optimization“ https://doi.org/10.48550/arXiv.2407.17206 konzentriert sich auf die Verbesserung der Strategie zur Generierung von Lösungskandidaten durch das neuronale Netz. Dabei werden die Lösungen durch wiederholtes Sampling (Ziehen ohne Zurücklegen) verfeinert. Dadurch wird das Netz gezwungen, auch noch nicht untersuchte Lösungen zu betrachten, was zu einer größeren Vielfalt führt. Von jeder guten Lösung wird nur ein Teil übernommen („take a step“), bevor weitere, noch nicht betrachtete Alternativen untersucht werden („reconsider“). Dieser Ansatz ist universell, schnell und skalierbar. Gleichzeitig garantiert er eine hohe Qualität und Vielfalt der Lösungen.

Leistungsfähigkeit bisheriger Ansätze übertroffen

Die Autoren konnten durch experimentelle Ergebnisse an bekannten Benchmark-Problemen wie dem Traveling Salesman Problem, dem Capacitated Vehicle Routing Problem und dem Job Shop Scheduling Problem zeigen, dass die neue Methode nicht nur die Leistungsfähigkeit bisheriger Ansätze erreicht, sondern auch die aktuell besten Methoden bei kritischen Scheduling-Benchmarks übertrifft. Das neue Verfahren wurde auf der European Conference on Artificial Intelligence (ECAI) als Publikation angenommen.

Forschung im GrimmLab

Beide Arbeiten sind an der Professur für Bioinformatik (GrimmLab) https://bit.cs.tum.de/ der Hochschule Weihenstephan-Triesdorf (HSWT) am TUM Campus Straubing unter Leitung von Prof. Dr. Dominik Grimm entstanden. Die Ergebnisse dieser Arbeit stellt Jonathan Pirnay Mitte Oktober in Santiago de Compostela, Spanien, internationalen Expert:innen auf dem Gebiet der künstlichen Intelligenz vor.

Förderung und Unterstützung

Die Forschungsarbeit wurde von der Deutschen Forschungsgemeinschaft (DFG) im Rahmen des Sonderprogrammpunkts SPP 2331 gefördert. Für die Entwicklung der neuen Methoden wurde KI-Infrastruktur des Projekts AI4Life https://www.hswt.de/forschung/projekt/1755-ai4life genutzt, welche durch den Projektträger VDI und den Mittelgeber BMBF gefördert wurde. Das Kompetenzzentrum für Digitale Agrarwirtschaft (KoDA) https://www.hswt.de/forschung/forschungseinrichtungen/kompetenzzentrum-fuer-digi… der Hochschule Weihenstephan-Triesdorf (HSWT) unterstützt Forschende bei der Bereitstellung dieser Infrastruktur. Dort fand unter anderem im September 2024 die Einweihung des KI-Servers der Firma CANCOM statt https://www.hswt.de/news-list/detail/ai4life-neuer-ki-server-am-innovationscampu….

Wissenschaftliche Ansprechpartner:

Prof. Dr. Dominik Grimm
Hochschule Weihenstephan-Triesdorf
Leiter der Professur Bioinformatik (GrimmLab) am HSWT-Standort Straubing für nachhaltige Ressourcennutzung (TUM Campus Straubing)
https://bit.cs.tum.de/team/dominik-grimm/

Originalpublikation:

Self-Improvement for Neural Combinatorial Optimization https://openreview.net/forum?id=agT8ojoH0X
Take a Step and Reconsider: Sequence Decoding for Self-Improved Neural Combinatorial Optimization https://doi.org/10.48550/arXiv.2407.17206

https://www.hswt.de/