Selbstlernende Verfahren auf Basis von Deep Reinforcement Learning: die Suche nach Zulässigkeit

• Antragsteller: Professor Dr. Kevin Tierney
• Fachliche Zuordnung: Bild- und Sprachverarbeitung, Computergraphik und Visualisierung, Human Computer Interaction, Ubiquitous und Wearable Computing
• Förderung: Förderung seit 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 521243122

Optimierungsprobleme spielen in einer Vielzahl von Branchen und Forschungsbereichen eine wichtige Rolle. Die Fähigkeit, diese Optimierungsprobleme schnell und möglichst optimal zu lösen, ist ein wesentlicher Grundbaustein einer effektiven Entscheidungshilfe für Entscheidungsträger. Jedoch ist die Entwicklung der dafür notwendigen Algorithmen und Solver ein zeitaufwändiger Prozess, der außerdem viel Fachwissen in dem jeweiligen Problembereich und Wissen in Bezug auf Optimierungsverfahren erfordert. Außerdem nutzen Solver nur selten datengetriebene Komponenten, welche es ihnen z.B. erlauben würden, ihre Vorgehensweise dynamisch an die vorliegenden Probleminstanzen anzupassen. In den letzten Jahren wurden eine Reihe von Ansätzen zur automatisieren Generierung von Optimierungsmethoden für spezifische Optimierungsprobleme mittels Deep Reinforcement Learning entwickelt. Bei diesen Ansätzen wird ein Lösungsalgorithmus speziell an ein Problem und eine bestimmte Klasse von Probleminstanzen angepasst. Trotz guter Ergebnisse beim Lösen einfacher Problemen, wie dem Traveling Salesperson Problem und dem Capacitated Vehicle Routing Problem, wurden diese Ansätze noch nicht auf anspruchsvollere Probleme, welche aus zahlreichen Nebenbedingungen und interagierenden Problemkomponenten bestehen, angewandt. Bei vielen anspruchsvolleren Problemen ist es dabei schwierig, überhaupt eine gültige Lösung zu finden, welche die hohe Zahl der Nebenbedingungen erfüllt. In diesem Projekt werden, basierend auf jahrelanger Erfahrung bei der Nutzung von maschinellen Lernen zum Lösen von Optimierungsproblemen, neuartige Such- und Lernmechanismen zur Lösung anspruchsvoller Optimierungsprobleme untersucht. Im Hinblick auf die eingesetzten Suchverfahren wird das Projekt problemunabhängige Methoden, wie Heuristic Backtracking, Monte-Carlo-Rollouts und Efficient Active Search untersuchen. Mit Blick auf die lernenden Komponenten untersucht das Projekt neue Verlustfunktionen, Curriculum-Learning und Methoden zum Determinieren der Feasibility Boundary in Optimierungsproblemen. Außerdem wird das Projekt eine Klasse sehr schwieriger Probleme mit voneinander abhängigen Komponenten, wie z. B. Routing Probleme mit Abholungen und Lieferungen, untersuchen und diese mit neuen Embedding Verfahren und Dekomposition lösen. Das Ergebnis des Projekts werden hocheffektive, problemunabhängige und selbstlernende Methoden sein, die anhand einer breiten Auswahl Optimierungsprobleme sorgfältig getestet wurden.

• DFG-Verfahren: Sachbeihilfen