Konvergenzgarantien für Moderne Evolutionsstrategien

• Antragsteller: Professor Dr. Tobias Glasmachers
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 442436089

Die primäre Rollen von Optimierungsheuristiken ist die Lösung schwieriger Probleme, für die keine effizienten Lösungsmethoden bekannt sind. Für diese Probleme sind Black-Box-Optimierungsmethoden in besonderer Weise relevant, da diese Algorithmen nur schwache Annahmen über die Problemstruktur benötigen. Mathematische Optimierung deckt viele wichtige Problemklassen ab. Für die verbleibenden Probleme kommen oft Black-Box-Heuristiken zum Einsatz.Eine sehr erfolgreiche Klasse von Algorithmen für gradientenfreie Black-Box-Optimierung in kontinuierlichen Räumen sind Evolutionsstrategien (ES), eine Unterklasse der evolutionären Algorithmen. Diese randomisierten direkten Suchverfahren erzeugen Suchpunkte aus einer Verteilung, welche daraufhin basierend auf den Zielfunktionswerten angepasst wird. Für flexible Verteilungsklassen ergeben sich ebenso flexible Algorithmen. Die Covariance Matrix Adaptation Evolution Strategy (CMA-ES), welche Beispielsweise für Problem im industriellen Design und im maschinellen Lernen eingesetzt wird, markiert den Stand der Technik. Sie zeigt hohe praktische Effizienz in Wettbewerben und Vergleichsstudien. Aus theoretischer Sicht fehlen ihr vor allem Konvergenzgarantien, welche bisher nur für sehr simple ES auf eingeschränkten Funktionsklassen zur Verfügung stehen.Durch die Verfügbarkeit neuer Beweistechniken hat sich diese Situation in den letzten Jahren deutlich verbessert. Den wichtigsten Durchbruch stellt die erfolgreiche Anwendung von Drift-Analyse auf ES dar. Auf diese Weise wurde erstmals die Konvergenz einer ES auf einer relativ großen Problemklasse gezeigt, nämlich auf allen strikt konvexen Funktionen. Ähnlich große Fortschritte wurden im Verständnis grundlegender Beschränkungen von ES erzielt, also von pathologischen Fällen, in denen der Algorithmus nicht in ein lokales Optimum konvergiert. Keine dieser Arbeiten adressiert CMA-ES. Das Fehlen einer Analyse des hochrelevanten CMA-Mechanismus stellt für das Verständnis von ES eine zentrale Forschungslücke dar.Das Füllen dieser Lücke ist ein großer Schritt auf dem Weg zu einem umfassenden Verständnis des Konvergenzverhaltens von CMA-ES auf einer großen Problemklasse. Das Projekt strebt den ersten Konvergenzbeweis für eine ES mit CMA an. Beginnend mit der relativ einfachen (1+1)-CMA-ES auf konvex-quadratischen Funktionen soll die Problemkomplexität stückweise bis zu nicht-elitistischen Varianten mit zustandsbehafteter Schrittweitensteuerung und großen Problemklassen erhöht werden. Wir streben Beweise für lineare Konvergenz (das in der Praxis beobachtete Verhalten) mit der korrekten Abhängigkeit der Konvergenzrate von der Problemdimension und der Konditionszahl an. Zusammengenommen stellen diese Schritte einen Meilenstein im Verständnis moderner Optimierungsheuristiken dar.

• DFG-Verfahren: Sachbeihilfen