Zum Inhalt springen
Zurück zu den Suchergebnissen

Evolutionary Strategy (CMA-ES) — Anpassung der Kovarianzmatrix

Eingeführt von
Nikolaus Hansen & Andreas Ostermeier
Jahr
2001
Typ
Derivative-free continuous black-box optimizer

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

CMA-ES, kurz für Covariance Matrix Adaptation Evolution Strategy, ist ein moderner, derivatfreier Optimierer für kontinuierliche Black-Box-Funktionen, der 2001 von Hansen und Ostermeier eingeführt wurde.

Er unterhält eine Population von Kandidatenlösungen, die aus einer multivariaten Normalverteilung gezogen werden, und aktualisiert iterativ den Mittelwert, die Schrittweite und die vollständige Kovarianzmatrix der Verteilung, um die Suche in bessere Bereiche des Parameterraums zu lenken. Er ist zum De-facto-Standard für die kontinuierliche Black-Box-Optimierung geworden und wird häufig bei der Suche nach neuronalen Architekturen und der Optimierung von Policy-Parametern im Reinforcement Learning eingesetzt.

Die Intuition hinter der Methode

Stellen Sie sich vor, Sie suchen den tiefsten Punkt in einer hügeligen Landschaft, können aber das Gelände nicht sehen – Sie können nur einzelne Orte prüfen und deren Höhen erfahren. CMA-ES funktioniert wie ein gesteuerter Schwarm: Er setzt eine Wolke von Prüfpunkten um eine aktuelle beste Schätzung ab, misst, wie gut jeder Prüfpunkt ist, und formt dann die Wolke für die nächste Runde neu. Die Wolke ist keine einfache Kugel – sie lernt die gestreckte, geneigte Form des Tals, in das sie hinabsteigt, indem sie sich merkt, welche Richtungen zu Verbesserungen geführt haben. Über aufeinanderfolgende Generationen hinweg verengt und neigt sich die Wolke, um sich an die Krümmung der Verlustoberfläche anzupassen, was es dem Algorithmus ermöglicht, lange, schmale Täler zu durchqueren, die einfachere Methoden in die Irre führen würden.

Geschichte

Evolution Strategies wurden in den 1960er und 1970er Jahren als eine Familie populationsbasierter Optimierer eingeführt, die von der biologischen Evolution inspiriert sind. Der Mechanismus zur Anpassung der Kovarianzmatrix wurde von Hansen und Ostermeier entwickelt und in ihrer Arbeit über Evolutionary Computation von 2001 vollständig beschrieben. Diese zeigte, dass die vollständige Derandomisierung der Selbstadaption – das Erlernen der vollständigen Geometrie zweiter Ordnung der Suchlandschaft aus der Historie erfolgreicher Schritte – frühere Evolution Strategies bei schlecht konditionierten und nicht-separierbaren Problemen dramatisch übertraf. Hansens Tutorial von 2016 fasste den Algorithmus und seine theoretischen Eigenschaften zusammen, wodurch CMA-ES zur Standardreferenzmethode für das Benchmarking der kontinuierlichen Black-Box-Optimierung wurde.

Wann wird sie eingesetzt?

CMA-ES ist geeignet, wenn die Zielfunktion kontinuierlich, möglicherweise nicht-konvex, multimodal oder verrauscht ist und wenn Gradienteninformationen nicht verfügbar oder zu teuer zu berechnen sind. Der ideale Dimensionalitätsbereich liegt bei etwa 10 bis 1000 Parametern; unter 10 Dimensionen sind einfachere Methoden oft ausreichend, und über 1000 kann der quadratische Speicherbedarf der Kovarianzmatrix prohibitiv werden. Es gibt keine Mindeststichprobengröße im statistischen Sinne – der Algorithmus generiert selbst seine Auswertungspunkte. CMA-ES eignet sich gut für die Hyperparameter-Optimierung, die Suche nach neuronalen Architekturen, die Optimierung von Policy-Parametern im Reinforcement Learning und technische Designprobleme, bei denen der Simulator nur Black-Box-Ausgaben liefert.

Grenzen und Hinweise

  • Der quadratische Speicher- und Rechenaufwand pro Generation in Bezug auf die Anzahl der Dimensionen begrenzt die Anwendbarkeit über etwa 1000 Parameter hinaus ohne Varianten zur Dimensionsreduktion.
  • Konvergiert ohne Neustarts zu einem lokalen Optimum; für stark multimodale Landschaften sind mehrere Neustarts (IPOP-CMA-ES oder BIPOP-CMA-ES) erforderlich.
  • Nicht geeignet für diskrete oder kombinatorische Suchräume – die Methode ist inhärent für kontinuierliche reellwertige Vektoren definiert.

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Benötigt keine Gradienteninformationen – funktioniert mit jeder aufrufbaren Zielfunktion, einschließlich verrauschter oder simulationsbasierter Funktionen.
  • Lernt die lokale Krümmung der Suchlandschaft durch Kovarianzanpassung, was es ihm ermöglicht, gestreckte und schlecht konditionierte Suchräume zu durchqueren, die gradientenfreie Methoden mit festen Suchverteilungen besiegen.
  • Invariant gegenüber ordnungserhaltenden Transformationen der Zielfunktion und Rotationen des Suchraums, was ihn robust für eine Vielzahl von Problemgeometrien macht.
  • Gut geeignet für kontinuierliche Probleme mittlerer bis hoher Dimensionalität (10–1000 Parameter) mit einem einzigen abstimmbaren Hyperparameter – der anfänglichen Schrittweite.

Anwendungen

  • Hyperparameter-Optimierung für Machine-Learning-Modelle, einschließlich neuronaler Netzwerkarchitekturen und Reinforcement-Learning-Agenten.
  • Suche nach neuronalen Architekturen – Optimierung von diskret kodierten Architekturparametern durch kontinuierliche Relaxation.
  • Optimierung von Policy-Parametern im Reinforcement Learning, wenn die Policy durch einen kontinuierlichen Vektor parametrisiert ist.
  • Optimierung technischer Designs, wie z. B. aerodynamische Formoptimierung und Anpassung von Strukturparametern, bei denen nur Simulatorausgaben verfügbar sind.
  • Kalibrierung wissenschaftlicher Modelle – Anpassung von Simulationsmodellen an experimentelle Daten, wenn die Likelihood nicht-differenzierbar oder rechenintensiv ist.

So funktioniert es

So funktioniert es

1

Der Algorithmus wird mit einem anfänglichen Lösungsvektor und einer anfänglichen Schrittweite (sigma) initialisiert. Die Kovarianzmatrix beginnt als Einheitsmatrix – eine perfekt kugelförmige Suchwolke. Die Populationsgröße wird festgelegt, typischerweise um 4 + floor(3 * ln(dimension)).

2

In jeder Generation wird eine Population von Kandidatenlösungen aus der aktuellen multivariaten Normalverteilung, die durch den Mittelwertsvektor, die Schrittweite und die Kovarianzmatrix definiert ist, gezogen. Da die Verteilung multivariat normal ist, spiegeln die Stichproben sowohl die aktuelle beste Schätzung als auch die gelernte Form des Suchraums wider.

3

Jede Kandidatenlösung wird an die Zielfunktion übergeben und erhält eine Fitnessbewertung. Es sind keine Gradienteninformationen erforderlich – nur der skalare Zielwert an jedem Stichprobenpunkt wird benötigt. Dies macht CMA-ES für verrauschte, nicht-differenzierbare und simulationsbasierte Ziele geeignet.

4

Der Mittelwert wird in Richtung der besser bewerteten Lösungen verschoben. Die Kovarianzmatrix und die Schrittweite werden über zwei komplementäre Anpassungswege – Rang-Eins- und Rang-Mu-Updates – aktualisiert, sodass Richtungen, die gute Verbesserungen ergaben, in der nächsten Generation wahrscheinlicher werden. Dies ist der Kernmechanismus, mit dem CMA-ES die lokale Geometrie der Landschaft lernt.

5

Der Algorithmus wiederholt den Stichproben-Auswertungs-Aktualisierungs-Zyklus, bis ein Abbruchkriterium erfüllt ist: eine maximale Anzahl von Funktionsauswertungen, eine Toleranz für die Änderung des Mittelwerts oder der Schrittweite oder eine erkannte Degeneration der Kovarianzmatrix. Die beste gefundene Lösung über alle Generationen hinweg wird zurückgegeben.

Häufige Fallstricke

  • Das Festlegen einer zu kleinen anfänglichen Schrittweite fängt die Suche in einer engen Nachbarschaft ein und verhindert die Exploration; eine zu große Schrittweite führt dazu, dass frühe Generationen Auswertungen weit vom Optimum entfernt verschwenden. Eine gängige Faustregel ist, sigma so zu wählen, dass das erwartete Optimum innerhalb von etwa drei Sigma vom Startpunkt liegt.
  • Die Anwendung von CMA-ES auf Probleme mit sehr geringer Dimensionalität (weniger als fünf Parameter) ist normalerweise verschwenderisch – einfachere Methoden wie Grid Search oder Nelder-Mead reichen aus, und der Populationsaufwand von CMA-ES bringt keinen Vorteil.
  • Das Ausführen nur einer einzigen CMA-ES-Instanz auf einer multimodalen Landschaft birgt das Risiko, das globale Optimum zu verfehlen; verwenden Sie Multi-Start- oder populationsbasierte Neustartstrategien (IPOP/BIPOP), wenn bekannt ist, dass die Landschaft stark multimodal ist.
  • Die zurückgegebene beste Lösung ohne Neustartüberprüfung als das wahre globale Optimum zu behandeln, ist ein häufiger Fehler – überprüfen Sie bei stark nicht-konvexen Zielen immer mit mehreren unabhängigen Läufen.

Häufig gestellte Fragen

Wie unterscheidet sich CMA-ES von einem einfachen genetischen Algorithmus?

Ein klassischer genetischer Algorithmus unterhält eine Population und wendet Crossover und Mutation mit festen Operatoren an. CMA-ES modelliert stattdessen die Population als Stichproben aus einer multivariaten Normalverteilung und passt diese Verteilung – ihren Mittelwert, ihre Schrittweite und ihre vollständige Kovarianzmatrix – kontinuierlich an, basierend darauf, welche Lösungen erfolgreich waren. Dies ermöglicht es CMA-ES, die Form der Verlustlandschaft zu lernen und korrelierte, schlecht konditionierte Räume weitaus effizienter zu durchqueren als ein genetischer Algorithmus mit festen Operatoren.

Garantiert CMA-ES das Finden des globalen Optimums?

Nein. CMA-ES ist eine lokale Suchmethode in dem Sinne, dass ein einzelner Lauf zu einem lokalen Optimum konvergieren kann. Für multimodale Landschaften werden mehrere unabhängige Neustarts – möglicherweise mit zunehmenden Populationsgrößen (IPOP-CMA-ES) – empfohlen, um die Abdeckung des Suchraums zu verbessern.

Was ist der wichtigste Hyperparameter, der eingestellt werden muss?

Die anfängliche Schrittweite sigma ist der einflussreichste Hyperparameter. Eine gute Heuristik ist, sie so zu wählen, dass das erwartete Optimum innerhalb von etwa drei Sigma vom Startpunkt liegt. Die Populationsgröße und die maximale Anzahl von Auswertungen sind sekundäre Steuerungen; die Standardformel für die Populationsgröße (4 + floor(3 * ln(dimension))) funktioniert in der Praxis gut.

Kann CMA-ES verrauschte Zielfunktionen verarbeiten?

Ja. Da CMA-ES nur Ranginformationsinformationen aus der Population verwendet – nicht absolute Funktionswerte –, ist es relativ robust gegenüber Rauschen. Bei stark verrauschten Auswertungen kann die Erhöhung der Populationsgröße oder die Mittelung mehrerer Auswertungen pro Kandidat die Robustheit weiter verbessern.

Verwandte Methoden

Quellen

  1. Hansen, N. & Ostermeier, A. (2001). Completely Derandomized Self-Adaptation in Evolutionary Strategies. Evolutionary Computation, 9(2), 159-195.

    DOI-Referenz öffnen
    Kopiert.
  2. Hansen, N. (2016). The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772.

    Publikationsreferenz öffnen
    Kopiert.