Zum Inhalt springen
Zurück zu den Suchergebnissen

Grey Wolf Optimizer — GWO

Eingeführt von
Seyedali Mirjalili, Seyed Mohammad Mirjalili, Andrew Lewis
Jahr
2014
Typ
Swarm-intelligence metaheuristic

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

Schriftgröße

Was leistet sie?

Der Grey Wolf Optimizer (GWO) ist eine Metaheuristik der Schwarmintelligenz, die 2014 von Mirjalili, Mirjalili und Lewis eingeführt wurde und die soziale Hierarchie und das kooperative Jagdverhalten von Grauwölfen modelliert.

Eine Population von Kandidatenlösungen wird in vier Führungsränge unterteilt – Alpha, Beta, Delta und Omega – und die drei besten Lösungen jeder Iteration führen den gesamten Schwarm zu immer besseren Regionen des Suchraums.

Die Intuition hinter der Methode

Stellen Sie sich eine Grauwolf-Rudel vor, das Beute durch dichtes Gelände verfolgt. Der Alpha-Wolf trifft die endgültige Entscheidung, die Beta- und Delta-Wölfe beraten, und der Rest des Rudels positioniert sich als Reaktion auf alle drei Anführer neu. GWO kopiert dies exakt: Die drei bisher besten gefundenen Lösungen dienen als Navigationsleuchtfeuer, und jeder andere Kandidat passt seine Position als gewichtete Mischung der Richtungen an, in die diese drei Leuchtfeuer zeigen. Ein einzelner Parameter, a, wird im Laufe der Iterationen allmählich von 2 auf 0 reduziert, sodass sich das Rudel zunächst weit ausbreitet, um zu explorieren, und dann seinen Kreis verengt, um die beste gefundene Region zu exploitieren.

Geschichte

GWO wurde 2014 von Seyedali Mirjalili, Seyed Mohammad Mirjalili und Andrew Lewis im Journal Advances in Engineering Software vorgeschlagen. Der Algorithmus wurde von ökologischen Beobachtungen der Grauwolf-Rudelstruktur inspiriert: eine strenge soziale Hierarchie (Alpha, Beta, Delta, Omega) und die dreiphasige Jagdstrategie des Einkreisens, Belästigens und Angreifens der Beute. Mirjalili et al. verglichen GWO mit Particle Swarm Optimization, Gravitational Search Algorithm und Differential Evolution auf 29 Testfunktionen und mehreren technischen Designproblemen und berichteten über wettbewerbsfähige oder überlegene Ergebnisse. Seit 2014 hat der Algorithmus eine beträchtliche Folge-Literatur hervorgebracht: Faris et al. (2018) untersuchten mehr als ein Jahrzehnt an Varianten – binäre, multiobjektive, chaotische und hybride Erweiterungen – und dokumentierten Anwendungen in den Bereichen Feature Selection, Energiesysteme, Bildsegmentierung und Zeitplanung.

Wann wird sie eingesetzt?

GWO eignet sich für kontinuierliche Optimierungsprobleme, bei denen die Zielfunktion analytisch teuer zu bewerten ist oder eine Black Box darstellt. Es sind keine Gradienteninformationen oder Verteilungsannahmen über die Daten erforderlich. Die Methode eignet sich für technische Design-, Parameter-Tuning- und Feature-Selection-Aufgaben. Da sie populationsbasiert ist, wird eine Mindestpopulationsgröße von etwa 10–30 Agenten empfohlen; sehr kleine Populationen reduzieren die Diversität und erhöhen das Risiko einer vorzeitigen Konvergenz. GWO ist ohne Modifikation nicht für diskrete oder kombinatorische Probleme geeignet, ebenso wenig für Probleme, bei denen eine exakte mathematische Lösung existiert.

Grenzen und Hinweise

  • Die Konvergenz zum globalen Optimum ist nicht garantiert; die Qualität hängt von der Populationsdiversität und der Iterationsanzahl ab.
  • Nicht nativ für diskrete, binäre oder kombinatorische Suchräume ohne benutzerdefinierte Kodierung geeignet.
  • Wie die meisten Schwarmmethoden kann sie stagnieren, wenn sich die drei Führer vorzeitig in einer suboptimalen Region konzentrieren.
  • Skaliert schlecht auf sehr hochdimensionale Suchräume im Vergleich zu gradientenbasierten Lösern, wenn die Zielfunktion glatt ist.

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

Stärken

  • Gradientenfrei: Funktioniert mit jeder Zielfunktion, die einen Skalar zurückgibt, einschließlich Simulationen und Black-Box-Modellen.
  • Minimale Parametrisierung: Nur Populationsgröße und Iterationsanzahl müssen festgelegt werden; a nimmt automatisch ab.
  • Balanciert Exploration und Exploitation durch einen einzigen linear abfallenden Parameter, was den Balance-Mechanismus transparent macht.
  • Wettbewerbsfähige Leistung bei Benchmarks für technisches Design mit geringer Implementierungskomplexität (Schwierigkeitsgrad 2 von 5).

Anwendungen

  • Optimierung von technischen Designs: Minimierung von Struktur-Gewicht, Antennendesign, Parameterschätzung von Energiesystemen.
  • Hyperparameter-Tuning und Feature Selection für Klassifikationsaufgaben im maschinellen Lernen.
  • Energiesysteme: Optimale Einspeisung in Stromnetzen und Platzierung von erneuerbaren Energieeinheiten.
  • Bildsegmentierung und medizinische Bildanalyse mittels Optimierung der Schwellenwerte.
  • Zeitplanungs- und Ressourcenallokationsprobleme mit kontinuierlicher Relaxation.

So funktioniert es

So funktioniert es

1

Eine Population von Kandidatenlösungen wird gleichmäßig zufällig innerhalb der definierten unteren und oberen Grenzen des Suchraums generiert. Die Populationsgröße und die maximale Anzahl von Iterationen sind die einzigen beiden Parameter, die vor Beginn des Laufs festgelegt werden müssen.

2

Jede Kandidatenlösung wird von der Zielfunktion bewertet. Da GWO gradientenfrei ist, kann die Funktion eine Black Box sein – sie muss nur einen skalaren Fitnesswert für jede Kandidatenposition zurückgeben.

3

Kandidaten werden nach Fitness sortiert. Die beste Lösung wird als Alpha (α), die zweitbeste als Beta (β) und die drittbeste als Delta (δ) bezeichnet. Alle verbleibenden Kandidaten sind Omega (ω) Wölfe. Diese Rollen werden jede Iteration neu zugewiesen, sodass die Bezeichnungen immer die drei aktuell besten Positionen verfolgen.

4

Jeder Omega-Wolf aktualisiert seine Position, indem er drei Abstandsvektoren berechnet – einen zu jedem der α, β und δ – und sich zum Schwerpunkt der drei resultierenden Zielpositionen bewegt. Der Kontrollparameter a nimmt im Laufe des Laufs linear von 2 auf 0 ab: Große Werte von a treiben die Exploration an (Kandidaten können überschießen und weit von den Führern entfernt suchen), kleine Werte treiben die Exploitation an (Kandidaten konvergieren eng um die Führer).

5

Der Jagdschritt wird wiederholt, bis die maximale Anzahl von Iterationen erreicht ist oder ein Abbruchkriterium erfüllt ist. Die Position des Alpha-Wolfs zum Zeitpunkt der Beendigung wird als beste gefundene Lösung zurückgegeben.

Häufige Fallstricke

  • Die Einstellung einer zu kleinen Populationsgröße (unter etwa 10) führt zu einem frühen Kollaps der Diversität; die drei Führer konvergieren vorzeitig und der Lauf erkundet nur einen kleinen Bereich.
  • Zu wenige Iterationen führen zu einem unzureichenden Jagdzyklus; ein Lauf, der abbricht, während a noch groß ist, ist nicht in die Exploitationsphase eingetreten.
  • Die Anwendung von GWO auf Probleme mit ganzzahligen oder kategorialen Variablen ohne Diskretisierungsschema führt zu bedeutungslosen Positionsaktualisierungen.
  • Ignorieren der Skalierung der Suchgrenzen – sehr weite Grenzen in Kombination mit einer kleinen Population lassen die meisten Bereiche in frühen Iterationen ununtersucht.

Häufig gestellte Fragen

Wie wähle ich Populationsgröße und Iterationsanzahl?

Ein üblicher Ausgangspunkt sind 30 Agenten und 200–500 Iterationen für moderat dimensionale Probleme (bis etwa 30 Variablen). Erhöhen Sie die Populationsgröße und die Iterationen mit zunehmender Dimensionalität des Problems. Da GWO stochastisch ist, führen Sie es mindestens 20–30 Mal mit unterschiedlichen Zufallssamen aus und berichten Sie den Mittelwert und die Standardabweichung der besten Fitness.

Kann GWO diskrete oder binäre Variablen verarbeiten?

Nicht nativ. Die Standard-Positionsaktualisierungsgleichungen sind für kontinuierliche reellwertige Räume definiert. Binäre oder diskrete Varianten existieren in der Literatur – typischerweise unter Verwendung einer Transferfunktion, um kontinuierliche Positionen auf binäre Entscheidungen abzubilden – aber dies sind Erweiterungen und nicht der ursprüngliche Algorithmus.

Wie schneidet GWO im Vergleich zu Particle Swarm Optimization ab?

Beide sind Methoden der Schwarmintelligenz mit ähnlichen Rechenkosten. GWO verwendet drei Führer (Alpha, Beta, Delta) anstelle eines einzelnen globalen Besten und des persönlichen Besten jedes Teilchens, was dazu neigt, die Diversität länger zu erhalten. Mirjalili et al. (2014) fanden GWO auf ihrem Benchmark-Set wettbewerbsfähig oder überlegen gegenüber PSO, aber die Leistung ist problemabhängig; keine Methode dominiert universell.

Was steuert der Parameter a und muss ich ihn abstimmen?

Der Parameter a nimmt im Laufe des Laufs linear von 2 auf 0 ab und steuert, ob Wölfe explorieren (hohes a) oder exploitieren (niedriges a). Dieser Zeitplan ist durch den Algorithmus festgelegt – Sie stimmen a nicht direkt ab. Die einzigen Hebel, die Sie kontrollieren, sind die Populationsgröße und die Gesamtzahl der Iterationen, die zusammen bestimmen, wie langsam oder schnell a abfällt.

Verwandte Methoden

Quellen

  1. Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey Wolf Optimizer. Advances in Engineering Software, 69, 46-61.

    DOI-Referenz öffnen
    Kopiert.
  2. Faris, H., Aljarah, I., Al-Betar, M. A., & Mirjalili, S. (2018). Grey Wolf Optimizer: A Review of Recent Variants and Applications. Neural Computing and Applications, 30(2), 413-435.

    DOI-Referenz öffnen
    Kopiert.