Zum Inhalt springen
Zurück zu den Suchergebnissen

Differential Evolution — Globaler stochastischer Optimierer

Eingeführt von
Rainer Storn & Kenneth Price
Jahr
1997
Typ
Population-based stochastic metaheuristic

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

Schriftgröße

Was leistet sie?

Differential Evolution (DE), eingeführt von Rainer Storn und Kenneth Price im Jahr 1997, ist ein populationsbasierter stochastischer Optimierungsalgorithmus, der für kontinuierliche Parameteräume entwickelt wurde.

Er generiert Kandidatenlösungen durch Kombination von Vektordifferenzen zwischen bestehenden Populationsmitgliedern, was ihn zu einer leistungsstarken und parameterarmen Alternative zu genetischen Algorithmen und Partikelschwarmoptimierung macht, wenn die Suchlandschaft nicht-konvex, multimodal oder für gradientenbasierte Methoden schlecht geeignet ist.

Die Intuition hinter der Methode

Stellen Sie sich eine Gruppe von Entdeckern vor, die sich über eine unbekannte Landschaft verteilen und nach dem tiefsten Tal suchen. In jedem Schritt beobachtet jeder Entdecker drei zufällig ausgewählte Kollegen, bewegt sich in die Richtung, die durch die Differenz zwischen zweien von ihnen, skaliert mit einem Schrittgrößenfaktor, vorgegeben wird, und entscheidet dann, ob die neue Position oder die alte eine bessere Geländebeschaffenheit aufweist. Über viele Runden hinweg konzentriert sich die gesamte Gruppe allmählich um das tiefste Tal, das sie gemeinsam gefunden hat. Differential Evolution funktioniert genau so: Die 'Differenz' zwischen zwei Populationsvektoren dient als Suchrichtung, und der Skalierungsfaktor F steuert, wie kühn jeder Schritt ist.

Geschichte

Differential Evolution wurde von Rainer Storn und Kenneth Price in ihrer wegweisenden Arbeit von 1997 im Journal of Global Optimization vorgestellt. Der Algorithmus entwickelte sich aus Prices früherer Arbeit über genetische Annealing-Verfahren und Storns Experimenten mit Floating-Point-Crossover. Die ursprüngliche Variante, heute DE/best/1/bin genannt, erwies sich auf Standard-Benchmarks als wettbewerbsfähig mit — und oft überlegen gegenüber — zeitgenössischen evolutionären Strategien und genetischen Algorithmen. Eine umfassende Überprüfung von Das, Mullick und Suganthan (2016) katalogisierte über zwei Jahrzehnte an Varianten, adaptiven Schemata und Anwendungen und etablierte DE als eine der grundlegenden Methoden in der Metaheuristik-Literatur.

Wann wird sie eingesetzt?

Differential Evolution ist geeignet, wenn die Zielfunktion kontinuierlich, möglicherweise nicht differenzierbar oder multimodal ist und die Suchgrenzen für alle Parameter im Voraus bekannt sind. Sie benötigt keine Gradienteninformationen und keine Normalitätsannahme, daher eignet sie sich für Ingenieurdesign, Hyperparameter-Tuning, Kalibrierung von Simulationsmodellen und jede Black-Box-Optimierungsaufgabe. Eine Populationsgröße von etwa dem 10-fachen der Parameteranzahl ist ein üblicher Ausgangspunkt. DE sollte nicht für rein diskrete oder kombinatorische Probleme angewendet werden; sie benötigt auch mindestens 1.000 Iterationen, um zuverlässig zu konvergieren — wenn das Budget für Funktionsauswertungen sehr knapp ist, ist die Bayes'sche Optimierung eine stichprobeneffizientere Alternative.

Grenzen und Hinweise

  • Die Konvergenz kann langsam sein, wenn die Anzahl der Iterationen unzureichend ist; weniger als 1.000 Generationen führen oft zu einem suboptimalen Ergebnis.
  • Die Leistung ist empfindlich gegenüber der Wahl von F und CR — schlecht abgestimmte Parameter können zu vorzeitiger Konvergenz oder übermäßig langsamen Fortschritten führen.
  • Nicht für rein diskrete oder kombinatorische Suchräume konzipiert; diskrete Erweiterungen existieren, sind aber weniger verbreitet.
  • Jede Iteration erfordert die Auswertung der Zielfunktion NP Mal, was kostspielig sein kann, wenn jede Auswertung rechenintensiv ist.

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 Black-Box-Zielfunktion, einschließlich nicht differenzierbarer und verrauschter Funktionen.
  • Sehr wenige Kontrollparameter (F, CR, NP) im Verhältnis zu ihrer Suchleistung, was die Konfiguration vergleichsweise einfach macht.
  • Behandelt multimodale Landschaften auf natürliche Weise, in denen gradientenbasierte Optimierer zu lokalen Optima konvergieren.
  • Populationsauswertungen sind unabhängig und können unkompliziert parallelisiert werden, wodurch die Wandzeit auf Multi-Core-Systemen reduziert wird.
  • Wettbewerbsfähig mit genetischen Algorithmen und Partikelschwarmoptimierung auf vielen Benchmarks bei gleichzeitig einfacherer Update-Regel.

Anwendungen

  • Kalibrierung von Simulations- und agentenbasierten Modellen, deren Zielfunktionen nicht-analytisch sind.
  • Hyperparameter-Optimierung für Machine-Learning-Pipelines, wenn der Suchraum kontinuierlich und begrenzt ist.
  • Ingenieurdesign-Probleme wie Antennendesign, Strukturoptimierung und Reglerabstimmung.
  • Training von neuronalen Netzen und Anpassung nichtlinearer Modelle in Ingenieur- und Naturwissenschaften.
  • Portfolio-Gewichtungsoptimierung und Parameterschätzung in Finanzzeitreihenmodellen.

So funktioniert es

So funktioniert es

1

Eine Population von NP Kandidatenlösungsvektoren wird für jeden Parameter gleichmäßig zufällig innerhalb der vordefinierten Suchgrenzen gezogen. Die Suchgrenzen müssen vom Benutzer festgelegt werden, bevor der Algorithmus startet; DE kann sie nicht aus dem Problem ableiten. Eine gute Anfangspopulation deckt den gesamten zulässigen Raum ab, damit der Algorithmus vielversprechende Regionen von Anfang an nicht verpasst.

2

Für jeden Zielvektor in der Population werden drei verschiedene Vektoren zufällig ausgewählt. Ein Mutationsvektor wird gebildet, indem die skalierte Differenz zweier Vektoren zum dritten addiert wird: v = x_r1 + F*(x_r2 - x_r3), wobei F der Skalierungsfaktor ist (typischerweise 0,4–1,0). Dieser differenzbasierte Schritt unterscheidet DE von anderen evolutionären Algorithmen und liefert ihm selbstanpassende gerichtete Informationen, ohne dass eine Gradientenberechnung erforderlich ist.

3

Ein Testvektor wird gebildet, indem der Mutationsvektor und der ursprüngliche Zielvektor elementweise gemischt werden. Jedes Element wird mit der Wahrscheinlichkeit CR (der Crossover-Rate, typischerweise 0,5–1,0) aus dem Mutationsvektor und andernfalls aus dem Zielvektor übernommen; mindestens ein Element wird immer aus dem Mutationsvektor übernommen. Dieser Schritt steuert das Gleichgewicht zwischen Exploration und Exploitation: Ein hohes CR begünstigt den Mutationsvektor, ein niedriges CR bewahrt mehr von der aktuellen Lösung.

4

Der Testvektor wird anhand der Zielfunktion ausgewertet und mit dem Zielvektor verglichen. Wenn der Testvektor einen gleichwertigen oder besseren Zielfunktionswert erzielt, ersetzt er den Zielvektor in der nächsten Generation; andernfalls wird der Zielvektor unverändert beibehalten. Diese gierige Eins-zu-Eins-Auswahl verhindert, dass die Population verfällt und stellt eine monotone Verbesserung der besten gefundenen Lösung sicher.

5

Mutation, Crossover und Selektion werden für eine ausreichende Anzahl von Generationen (üblicherweise 1.000 oder mehr) wiederholt, bis ein Konvergenzkriterium erfüllt ist — zum Beispiel, wenn die Änderung des besten Zielfunktionswerts unter einen Toleranzschwellenwert fällt oder die maximale Iterationszahl erreicht ist. Der beste Vektor in der Endpopulation ist die Lösung des Algorithmus.

Häufige Fallstricke

  • Die Ausführung von DE mit zu wenigen Iterationen (weniger als ca. 1.000) ist der häufigste Fehler — der Algorithmus hatte nicht genügend Generationen zur Konvergenz, und das Ergebnis sollte als vorläufig betrachtet werden; wechseln Sie zur Bayes'schen Optimierung, wenn das Auswertungsbudget knapp ist.
  • Die Einstellung des Skalierungsfaktors F zu niedrig führt zu einem vorzeitigen Verlust der Diversität; die Einstellung zu hoch verhindert die Konvergenz. Beginnen Sie mit F in [0,4, 1,0] und stimmen Sie empirisch ab.
  • Das Weglassen oder fehlerhafte Festlegen der Suchgrenzen ist ein kritischer Fehler — DE verwendet Grenzen zur Initialisierung der Population und liefert sinnlose Ergebnisse, wenn die Grenzen zu eng sind oder fehlen.
  • Die Behandlung von DE als einmaliger Lauf ist auf multimodalen Landschaften riskant — führen Sie mehrere unabhängige Durchläufe mit unterschiedlichen Zufallsseeds durch und berichten Sie die beste gefundene Lösung über die Läufe hinweg.

Häufig gestellte Fragen

Wie wähle ich den Skalierungsfaktor F und die Crossover-Rate CR?

Die am weitesten verbreiteten Standardwerte sind F = 0,8 und CR = 0,9 für die Strategie DE/best/1/bin. In der Praxis steuert F die Schrittgröße — Werte um 0,4–1,0 sind typisch — und CR steuert, wie stark der Mutationsvektor den Zielvektor ersetzt. Wenn die Population zu schnell konvergiert, erhöhen Sie F oder verringern Sie CR. Adaptive DE-Varianten (jDE, JADE) passen diese Parameter während des Laufs automatisch an, was eine sinnvolle Wahl ist, wenn eine manuelle Abstimmung unpraktisch ist.

Wie viele Generationen werden benötigt?

Als Faustregel werden mindestens 1.000 Generationen empfohlen. Bei hochdimensionalen Problemen (viele Parameter) oder komplexen Landschaften können mehr Iterationen erforderlich sein. Beobachten Sie den Zielfunktionswert der besten Lösung über die Generationen hinweg: Wenn er sich über Hunderte von Iterationen nicht geändert hat, hat DE wahrscheinlich konvergiert — oder stagniert, in welchem Fall ein erneuter Lauf mit einem neuen Zufallsseed ratsam ist.

Wie schneidet DE im Vergleich zu genetischen Algorithmen und Partikelschwarmoptimierung ab?

Alle drei sind populationsbasierte Metaheuristiken für die kontinuierliche Optimierung. DE verwendet typischerweise weniger Kontrollparameter als GAs und hat eine einfachere, deterministischere Update-Regel im Vergleich zu PSO. Auf vielen Standard-Benchmarks ist DE wettbewerbsfähig mit oder übertrifft beide, aber die Leistung ist problemabhängig. Die Wahl beruht oft auf Vertrautheit und verfügbaren Implementierungen anstelle einer universellen Rangliste.

Kann DE ganzzahlige oder kategoriale Parameter verarbeiten?

DE ist für kontinuierliche Räume konzipiert. Ganzzahlige Parameter können durch Runden der kontinuierlichen Lösung auf die nächste ganze Zahl nach jeder Aktualisierung berücksichtigt werden, dies ist jedoch eine Annäherung. Rein kategoriale oder kombinatorische Probleme — wie Terminplanung oder Routenplanung — werden besser mit Methoden für diskrete Räume bedient, wie z. B. Ant Colony Optimization oder Tabu Search.

Verwandte Methoden

Quellen

  1. Storn, R. & Price, K. (1997). Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization, 11(4), 341–359.

    DOI-Referenz öffnen
    Kopiert.
  2. Das, S., Mullick, S. S., & Suganthan, P. N. (2016). Recent advances in differential evolution – An updated survey. Swarm and Evolutionary Computation, 27, 1–30.

    DOI-Referenz öffnen
    Kopiert.