Modellbasierte Konfiguration von Algorithmen zum Lösen berechnunsmäßig schwerer Probleme

• Antragsteller: Professor Dr. Frank Hutter, Ph.D.
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2011 bis 2013
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 193799061

Viele Probleme in der Informatik und ihren Anwendungen sind berechnunsmässig schwer. Fortschritte im effektiven Lösen dieser Probleme haben direkten Nutzen für viele Forschungsgebiete, wie zum Beispiel der Produktionsplanung und -optimierung, rechnergestützten Konstruktion, Softwareverifizierung, und dem nachhaltigen Wirtschaften. Die besten bekannten Algorithmen für viele komputational schwere Probleme haben eine Reihe von Parametern (z.B. numerische Schwellenwerte oder diskrete Entscheidungen zwischen Algorithmenkomponenten). Ein Routineproblem im Umgang mit solchen Algorithmen ist es, eine Parametereinstellung zu finden, die ein empirisches Performanzmaß (z.B. Laufzeit oder Lösungsgüte) für eine gegebene Instanzmenge optimiert. Dieses Algorithmenkonfigurationsproblem (AC Problem) hat in den letzten Jahren -basierend auf Erfolgen für wichtige Problemklassen- stetig an Bedeutung gewonnen. Ein vielversprechender Ansatz für AC basiert auf Modellen zur Vorhersage von Algorithmenperformanz. Sequentielle Modellbasierte Optimierung (SMBO) iteriert zwischen der Konstruktion solcher Modellen und ihrer Benutzung, um vielversprechende Parametereinstellungen auszuwählen; die Modelle können auch die Wichtigkeit von Parametern und deren Interaktion mit Instanzeigenschaften quantifizieren. Dieses Projekt sieht vor, SMBO weiter zu verbessern, um die nächste Generation von AC Algorithmen zu entwickeln. Die Projektziele sind: (1) SMBO zu generalisieren, um damit unbeschränkte AC Probleme lösen zu können; (2) die komputationalen Kosten von AC Algorithmen zu reduzieren; und (3) wichtige Probleme in Angriff zu nehmen, die nicht auf der Grundlage von existierenden (modellfreien) AC Ansätzen gelöst werden können. Wir erwarten, dass diese Forschung die wissenschaftliche Erforschung und Entwicklung hochperformanter Algorithmen zum Lösen komputational schwerer Probleme deutlich erleichtern wird, und damit eine Schlüsselrolle in einer Vielzahl wichtiger Anwendungen spielen wird.

• DFG-Verfahren: Forschungsstipendien
• Internationaler Bezug: Kanada
• Gastgeber: Professor Dr. Holger Hoos