Grey Wolf Optimizer — GWO
- Introdotto da
- Seyedali Mirjalili, Seyed Mohammad Mirjalili, Andrew Lewis
- Anno
- 2014
- Tipo
- Swarm-intelligence metaheuristic
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
Il Grey Wolf Optimizer (GWO) è una meta-euristica di intelligenza di sciame introdotta da Mirjalili, Mirjalili e Lewis nel 2014, che modella la gerarchia sociale e il comportamento di caccia cooperativa dei lupi grigi.
Una popolazione di soluzioni candidate è divisa in quattro ranghi di leadership — alpha, beta, delta e omega — e le tre migliori soluzioni in ogni iterazione guidano l'intero sciame verso regioni sempre migliori dello spazio di ricerca.
L’intuizione alla base del metodo
Immaginate un branco di lupi grigi che bracca una preda attraverso un terreno fitto. Il lupo alpha prende la decisione finale, i lupi beta e delta consigliano, e il resto del branco si riposiziona in risposta a tutti e tre i leader. Il GWO copia esattamente questo comportamento: le tre soluzioni più adatte trovate finora agiscono come fari di navigazione, e ogni altro candidato aggiusta la propria posizione come una combinazione pesata delle direzioni indicate da quei tre fari. Un singolo parametro, a, viene gradualmente ridotto da 2 a 0 man mano che le iterazioni progrediscono, in modo che il branco prima si espanda ampiamente per esplorare e poi stringa il cerchio per sfruttare la regione migliore trovata.
Storia
Il GWO è stato proposto da Seyedali Mirjalili, Seyed Mohammad Mirjalili e Andrew Lewis nel 2014 nella rivista Advances in Engineering Software. L'algoritmo ha tratto ispirazione da osservazioni ecologiche della struttura dei branchi di lupi grigi: una rigida gerarchia sociale (alpha, beta, delta, omega) e la strategia di caccia in tre fasi di accerchiamento, molestia e attacco della preda. Mirjalili et al. hanno confrontato il GWO con Particle Swarm Optimization, Gravitational Search Algorithm e Differential Evolution su 29 funzioni di test e diversi problemi di progettazione ingegneristica, riportando risultati competitivi o superiori. Dal 2014 l'algoritmo ha generato una letteratura di follow-up sostanziale: Faris et al. (2018) hanno esaminato più di un decennio di varianti — estensioni binarie, multi-obiettivo, caotiche e ibride — e documentato applicazioni nella selezione delle caratteristiche, nei sistemi di potenza, nella segmentazione delle immagini e nella pianificazione.
Quando usarlo
Il GWO è adatto a problemi di ottimizzazione continua in cui la funzione obiettivo è costosa da valutare analiticamente o è una scatola nera. Non richiede informazioni sul gradiente né assunzioni distribuzionali sui dati. Il metodo è adatto per la progettazione ingegneristica, la messa a punto dei parametri e i compiti di selezione delle caratteristiche. Poiché è basato su popolazione, si consiglia una dimensione minima della popolazione di circa 10–30 agenti; popolazioni molto piccole riducono la diversità e aumentano il rischio di convergenza prematura. Il GWO non è appropriato per problemi discreti o combinatori senza modifiche, né per problemi per i quali esiste una soluzione matematica esatta.
Limiti e considerazioni
- La convergenza non è garantita all'ottimo globale; la qualità dipende dalla diversità della popolazione e dal numero di iterazioni.
- Non adatto nativamente a spazi di ricerca discreti, binari o combinatori senza codifica personalizzata.
- Come la maggior parte dei metodi di sciame, può stagnare se i tre leader si raggruppano prematuramente in una regione subottimale.
- Scala male in spazi di ricerca ad altissima dimensionalità rispetto ai risolutori basati su gradiente quando l'obiettivo è liscio.
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Privo di gradiente: funziona su qualsiasi funzione obiettivo che restituisca uno scalare, inclusi simulazioni e modelli a scatola nera.
- Parametrizzazione minima: è necessario impostare solo la dimensione della popolazione e il numero di iterazioni; a diminuisce automaticamente.
- Bilancia esplorazione e sfruttamento attraverso un singolo parametro a decadimento lineare, rendendo il meccanismo di bilanciamento trasparente.
- Prestazioni competitive su benchmark di progettazione ingegneristica con bassa complessità di implementazione (livello di difficoltà 2 su 5).
Applicazioni
- Ottimizzazione della progettazione ingegneristica: minimizzazione del peso strutturale, progettazione di antenne, stima dei parametri dei sistemi di potenza.
- Messa a punto degli iperparametri di machine learning e selezione delle caratteristiche per compiti di classificazione.
- Sistemi energetici: dispacciamento ottimale nelle reti elettriche e posizionamento delle unità di energia rinnovabile.
- Segmentazione delle immagini e analisi di immagini mediche tramite ottimizzazione della soglia.
- Problemi di pianificazione e allocazione delle risorse con rilassamento continuo.
Come funziona
Come funziona
Una popolazione di soluzioni candidate viene generata uniformemente a caso all'interno dei limiti inferiore e superiore definiti dello spazio di ricerca. La dimensione della popolazione e il numero massimo di iterazioni sono gli unici due parametri che devono essere impostati prima dell'inizio dell'esecuzione.
Ogni soluzione candidata viene valutata dalla funzione obiettivo. Poiché il GWO è privo di gradiente, la funzione può essere una scatola nera — deve solo restituire un valore scalare di fitness per ogni posizione candidata.
I candidati vengono ordinati per fitness. La migliore soluzione è designata alpha (α), la seconda migliore beta (β), e la terza migliore delta (δ). Tutti i candidati rimanenti sono lupi omega (ω). Questi ruoli vengono riassegnati ad ogni iterazione in modo che le etichette seguano sempre le tre posizioni migliori attuali.
Ogni lupo omega aggiorna la propria posizione calcolando tre vettori di distanza — uno verso ciascuno di α, β e δ — e spostandosi verso il centroide delle tre posizioni target risultanti. Il parametro di controllo a diminuisce linearmente da 2 a 0 durante l'esecuzione: valori elevati di a guidano l'esplorazione (i candidati possono superare il bersaglio e cercare lontano dai leader), valori bassi guidano lo sfruttamento (i candidati convergono strettamente attorno ai leader).
Il passo di caccia viene ripetuto fino a quando non viene raggiunto il numero massimo di iterazioni o non viene soddisfatto un criterio di arresto. La posizione del lupo alpha al termine viene restituita come la migliore soluzione trovata.
Errori comuni
- Impostare una dimensione della popolazione troppo piccola (inferiore a circa 10) collassa prematuramente la diversità; i tre leader convergono prematuramente e l'esecuzione esplora solo una piccola regione.
- Eseguire poche iterazioni fornisce un ciclo di caccia insufficiente; un'esecuzione che termina mentre a è ancora elevato non è entrata nella fase di sfruttamento.
- Applicare il GWO a problemi con variabili intere o categoriche senza uno schema di discretizzazione produce aggiornamenti di posizione senza significato.
- Ignorare la scala dei limiti dello spazio di ricerca — limiti molto ampi combinati con una piccola popolazione lasciano la maggior parte dello spazio non campionato nelle iterazioni iniziali.
Domande frequenti
Come scelgo la dimensione della popolazione e il numero di iterazioni?
Un punto di partenza comune è 30 agenti e 200–500 iterazioni per problemi di dimensionalità moderata (fino a circa 30 variabili). Aumentare la dimensione della popolazione e le iterazioni all'aumentare della dimensionalità del problema. Poiché il GWO è stocastico, eseguirlo almeno 20–30 volte con diversi semi casuali e riportare la media e la deviazione standard del miglior fitness.
Il GWO può gestire variabili discrete o binarie?
Non nativamente. Le equazioni standard di aggiornamento della posizione sono definite per spazi continui a valori reali. Varianti binarie o discrete esistono in letteratura — tipicamente utilizzando una funzione di trasferimento per mappare posizioni continue a decisioni binarie — ma queste sono estensioni piuttosto che l'algoritmo originale.
Come si confronta il GWO con Particle Swarm Optimization?
Entrambi sono metodi di intelligenza di sciame con costo computazionale simile. Il GWO utilizza tre leader (alpha, beta, delta) piuttosto che un singolo miglior globale e il miglior personale di ogni particella, il che tende a preservare la diversità più a lungo. Mirjalili et al. (2014) hanno trovato il GWO competitivo o superiore al PSO sul loro set di benchmark, ma le prestazioni dipendono dal problema; nessun metodo domina universalmente.
Cosa controlla il parametro a, e devo regolarlo?
Il parametro a diminuisce linearmente da 2 a 0 nel corso dell'esecuzione e controlla se i lupi esplorano (a elevato) o sfruttano (a basso). Questa schedulazione è fissa dall'algoritmo — non si regola a direttamente. Le uniche leve che si controllano sono la dimensione della popolazione e il numero totale di iterazioni, che insieme determinano quanto lentamente o rapidamente a diminuisce.
Metodi correlati
Fonti
Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey Wolf Optimizer. Advances in Engineering Software, 69, 46-61.
Apri il riferimento DOICopiato.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.
Apri il riferimento DOICopiato.