Theorie der Estimation-of-Distribution-Algorithmen (TEDA)

• Antragsteller: Professor Tobias Friedrich, Ph.D.
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 440936840

Große Optimierungsprobleme können häufig deswegen nicht effizient von Standardoptimierungsverfahren gelöst werden, weil die Zielfunktion nur indirekt vorliegt. In solchen Black-Box-Szenarien kommen üblicherweise Heuristiken zum Einsatz. Beliebte Ansätze sind dabei von der Natur inspirierte "General-Purpose"-Optimierungsverfahren wie Evolutionäre Suchheuristiken. Dort gibt es zwei grundlegende Repräsentationen des evolutionären Suchstatus: Multimengen von Lösungen, die mittels Mutation, Kreuzung und Selektion entwickelt werden, sowie probabilistische Modelle, die von Beispielen lernen. Dies entspricht klassischen evolutionären Algorithmen (EAs) beziehungsweise Estimation-of-Distribution-Algorithmen (EDAs). Während EAs schon seit über drei Jahrzehnten theoretisch untersucht werden, widmet man sich der theoretischen Analyse von EDAs erst seit kurzem intensiver.Unser Ziel ist es, das formale Verständnis von EDAs weiterzuentwickeln. Vor allem möchten wir die Diskrepanz zwischen der Menge an theoretischen Ergebnissen von EAs und EDAs verringern und dadurch ein umfangreiches Gesamtbild der Tragweite von Evolutionärer Suchheuristiken erstellen. Obwohl sich EAs und EDAs strukturell unterscheiden, korrelieren ihre Effizienzen in der Optimierung stärker als erwartet. Nichtsdestoweniger haben beide Ansätze ihre individuellen Stärken, die wir herausarbeiten möchten.Der erste Schritt dieses wissenschaftlichen Unterfangens wird die Entwicklung neuer stochastischer Hilfsmittel sein, die besser für die Analyse von EDAs geeignet sind - die meisten derzeitigen Hilfsmittel wurden speziell für EAs entwickelt. Speziell planen wir, neue Drifttheoreme zu entwickeln, die für Situationen geeignet sind, die zwar häufig für EDAs, aber selten für EAs auftreten. Diese neu entwickelten Hilfsmittel werden dazu beitragen, Klassen von EDAs zu analysieren, die zuvor nicht theoretisch betrachtet wurden. Weiterhin planen wir, EDAs in Szenarien zu untersuchen, für die sie besser geeignet sein könnten als EAs. Ein Beispiel dafür sind verrauschte Szenarien, für die es zwar empirische Belege für den Vorteil von EDAs gibt, aber keine mathematisch fundierten. Des Weiteren wurden EDAs bisher kaum in Szenarien mit mehreren lokalen Optima untersucht. Da sie eine globalere Sichtweise auf den Suchraum haben, gehen wir davon aus, dass EDAs lokale Optima besser überwinden können als EAs. Gegen Ende soll das Projekt genügend Einsichten in EDAs geliefert haben, sodass wir neue hybride Algorithmen entwerfen können, die die Vorteile von EAs und EDAs vereinen.

• DFG-Verfahren: Sachbeihilfen
• Mitverantwortlich: Dr. Timo Kötzing