Fortgeschrittene Verfahren zur Automatischen Optimierung und Modellierung der Empirischen Performanz Hochparameterisierter Heuristischer Algorithmen

• Antragsteller: Professor Frank Hutter, Ph.D.
• Fachliche Zuordnung: Bild- und Sprachverarbeitung, Computergraphik und Visualisierung, Human Computer Interaction, Ubiquitous und Wearable Computing ; Theoretische Informatik
• Förderung: Förderung von 2013 bis 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 222619695

Schwere kombinatorische Probleme spielen eine Schlüsselrolle in vielen für Industrie und Gesellschaft wichtigen Gebieten, z.B. in der formalen Verifikation von Hard- und Software, in Entscheidungshilfesystemen, in der Produktions- und Transportplanung und in Management & Verteilung knapper Ressourcen. Obwohl für viele dieser Probleme die Existenz beweisbar effizienter Algorithmen unwahrscheinlich ist, existieren effektive heuristische Verfahren zur Lösung praktisch auftretender Probleminstanzen.Der traditionelle Designprozess solcher heuristischer Algorithmen ist jedoch nicht optimal. Er beinhaltet typischerweise eine manuelle Phase, in der Kombinationen vieler Algorithmenkomponenten und Parametereinstellungen (sogenannte Konfigurationen des Algorithmus) ausprobiert und empirisch auf einer Instanzmenge evaluiert werden. Die manuelle Erforschung der kombinatorischen Anzahl möglicher Konfigurationen ist kompliziert und zeitraubend, so dass Algorithmendesigner oft nicht das gesamte Potential ihrer hochparameterisierten Algorithmen nutzen.Das Hauptziel dieses Projekts ist, eine Verbesserung gegenüber diesem manuellen Prozess zu erreichen, indem automatisierte Verfahren für die computergestützte Algorithmenkonstruktion und –analyse entwickelt werden, die Algorithmendesignern und Endnutzern helfen, die Flexibilität hochparameterisierter Algorithmen voll auszunutzen. In umfangreichen Vorarbeiten zur Algorithmenkonfiguration (AK) - dem Problem, die beste Konfiguration eines hochparameterisierten Algorithmus zu finden - hat der Antragsteller die besten existierenden AK Verfahren entwickelt. Diese Verfahren haben bereits zu deutlichen Verbesserungen des Stands der Technik für verschiedene schwere kombinatorische Probleme geführt.Teilziele dieses Projektes sind:(1) den Stand der Technik für das AK Problem weiter deutlich zu verbessern;(2) basierend auf automatischen AK Verfahren, leistungsfähige Algorithmenportfolios (aus individuell gefertigten komplementären Konfigurationen hochparameterisierter Algorithmen) zu konstruieren;(3) Algorithmendesignern automatisch Erkenntnisse zu liefern, wie die empirische Schwere ihrer Instanzen und die empirische Leistungsfähigkeit ihrer Algorithmen von Instanzeigenschaften und Algorithmenkomponenten abhängen. Die zu entwickelnden automatisierten Verfahren sind unabhängig von Domäne und Algorithmus und können somit flexibel angewendet werden. Im Rahmen dieses Projektes sollen sie benutzt werden, um gemeinsam mit Domänenexperten(4) den Stand der Technik für viele Probleme von hoher gesellschaftlicher und wirtschaftlicher Relevanz wesentlich zu verbessern.Diese Probleme umfassen die Gebiete formale Softwareverifikation (mit Anwendungen in der Computersicherheit), Answer Set Programming (mit Anwendungen in Entscheidungshilfesystemen), gemischt-ganzzahlige Programmierung (mit Anwendungen in der Optimierung industrieller Prozesse und öffentlicher Verkehrssysteme), automatisches Planen (mit Anwendungen in autonomen Robotern und in Produktions- und Logistikplanung) und Ressourcenmanagement & -verteilung (ein besonders wichtiges Gebiet in einer Ära immer knapperer Rohstoffe).Die zu entwickelnden automatischen Verfahren werden öffentlich verfügbar sein, um Domänenexperten in einem noch breiteren Spektrum von Problemen darin zu unterstützen, den Stand der Forschung auf ihrem Gebiet weiter zu verbessern.

• DFG-Verfahren: Emmy Noether-Nachwuchsgruppen
• Großgeräte: compute cluster