Algoritmi di ottimizzazione della popolazione: Ottimizzazione Grey Wolf (GWO)

Contenuto

1. Introduzione
2. Descrizione dell'algoritmo
3. Funzioni di test
4. Risultati del test

1. Introduzione

L'algoritmo grey wolf è un algoritmo metaeuristico di intelligenza stocastica a sciame sviluppato nel 2014. L'idea si basa sul modello di caccia del branco di lupi grigi. Esistono quattro tipi di lupi: alfa, beta, delta e omega. L'alfa ha il maggior "peso" nel processo decisionale e nella gestione del branco. Seguono i beta e i delta, che obbediscono all'alfa e hanno potere sul resto dei lupi. Il lupo omega obbedisce sempre al resto dei lupi dominanti.

Nel modello matematico della gerarchia dei lupi, il lupo alfa è considerato il lupo dominante del branco e i suoi ordini devono essere eseguiti dai membri del branco. I lupi beta-β-subordinati assistono l'alfa nel processo decisionale e sono considerati i migliori candidati al ruolo di alfa. I lupi delta δ dovrebbero obbedire ad alfa e beta, ma dominano gli omega. I lupi Omega ω sono considerati i capri espiatori del branco e gli individui meno importanti. Possono mangiare solo alla fine. Alpha è considerata la soluzione più favorevole.

La seconda e la terza soluzione migliore sono rispettivamente beta e delta. Le altre soluzioni sono considerate omega. Si presume che i lupi più adatti (alfa, beta e delta), cioè quelli più vicini alla preda, saranno avvicinati dal resto dei lupi. Dopo ogni approccio, si determina chi è l'alfa, il beta e il delta in questa fase e poi i lupi vengono riorganizzati di nuovo. La formazione avviene fino a quando i lupi si riuniscono in un branco, che sarà la direzione ottimale per un attacco con una distanza minima.

Durante l'algoritmo vengono eseguite 3 fasi principali, in cui i lupi cercano la preda, la circondano e la attaccano. La ricerca rivela gli alfa, i beta e i delta - ovvero i lupi più vicini alla preda. Gli altri, obbedendo a quelli dominanti, possono iniziare a circondare la preda o continuare a muoversi a caso alla ricerca dell'opzione migliore.

2. Descrizione dell'algoritmo

La gerarchia nel branco è schematizzata nella Figura 1.  L'alfa ha un ruolo dominante.

Fig. 1. La gerarchia sociale in un branco di lupi

Modello matematico e algoritmo
Gerarchia sociale:

• La soluzione migliore è rappresentata da un lupo alfa (α).
• La seconda migliore soluzione da un lupo beta (β).
• La terza soluzione migliore è un lupo delta(δ).
• Altre possibili soluzioni da lupi omega (ω).

Circondare la preda: quando esistono già le migliori soluzioni alfa, beta e delta, le azioni successive dipendono dall'omega.

Figura 2. Fasi di caccia: ricerca, accerchiamento, attacco.

Tutte le iterazioni dell'algoritmo sono rappresentate da tre fasi: ricerca, accerchiamento e caccia. La versione canonica dell'algoritmo presenta il rapporto calcolato а introdotto per migliorare la convergenza dell'algoritmo. Il rapporto decresce fino a zero a ogni iterazione. Finché il rapporto è superiore a 1, l'inizializzazione dei lupi è in corso. In questa fase, la posizione della preda è completamente sconosciuta, quindi i lupi devono essere distribuiti in modo casuale.

Dopo la fase di "ricerca", viene determinato il valore della funzione di fitness, e solo dopo è possibile procedere alla fase di "accerchiamento". In questa fase, il rapporto a è superiore a 1. Ciò significa che alfa, beta e delta si allontanano dalle loro posizioni precedenti, consentendo così di affinare la posizione stimata della preda. Quando il rapporto а diventa uguale a 1, inizia la fase di "attacco", mentre il rapporto tende a 0 prima della fine delle iterazioni. Questo fa sì che i lupi si avvicinino alla preda, suggerendo che la posizione migliore è già stata trovata. Tuttavia, se in questa fase, uno dei lupi trova una soluzione migliore, la posizione della preda e la gerarchia dei lupi saranno aggiornate, ma il rapporto tenderà ancora a 0. Il processo di variazione di a è rappresentato da una funzione non lineare. Le fasi sono illustrate in modo schematico nella Figura 2.

Il comportamento dei lupi omega è invariato in tutti i periodi e consiste nel seguire il centro geometrico tra le posizioni degli individui attualmente dominanti. Nella Figura 3, alfa, beta e delta deviano dalla loro posizione precedente in una direzione casuale con un raggio dato dai coefficienti, e gli omega si spostano verso il centro tra di loro ma con un certo grado di probabilità deviando da esso entro il raggio. I raggi determinano il rapporto а che, come ricordiamo, cambia facendo diminuire proporzionalmente i raggi.

Fig. 3. Diagramma del movimento omega in relazione ad alfa, beta e delta

Lo pseudocodice dell'algoritmo GWO è il seguente:

1) Inizializzare casualmente la popolazione di lupi grigi.
2) Calcolare la fitness di ciascun membro della popolazione.
3) Capi branco:
-α = membro con il miglior valore di fitness
-β = secondo miglior membro (in termini di fitness)
-δ = terzo miglior membro (in termini di valore di fitness)
Aggiornare la posizione di tutti i lupi omega secondo le equazioni dipendenti da α, β, δ
4) Calcolare la fitness di ciascun membro della popolazione.
5) ripetere il passaggio 3.

Passiamo al codice dell'algoritmo. L'unica aggiunta che ho fatto alla versione originale è la possibilità di impostare il numero di lupi leader del branco. Ora è possibile impostare un numero qualsiasi di leader, fino all'intero branco. Può essere utile per compiti specifici.

Cominciamo, come al solito, con l'unità elementare dell'algoritmo - il lupo, che è una soluzione al problema. Si tratta di una struttura che include un array di coordinate e un valore per la preda (funzioni di fitness). La struttura è la stessa per i capi e i membri minori del branco. Questo semplifica l'algoritmo e ci permette di utilizzare le stesse strutture nelle operazioni di loop. Inoltre, durante tutte le iterazioni, i ruoli dei lupi cambiano più volte. I ruoli sono determinati in modo univoco dalla posizione nell'array dopo l'ordinamento. I leader si trovano all'inizio dell’array.

//——————————————————————————————————————————————————————————————————————————————
struct S_Wolf
{
  double c []; //coordinates
  double p;    //prey
};
//——————————————————————————————————————————————————————————————————————————————

Il branco di lupi è rappresentato da una classe compatta e comprensibile. Qui si dichiarano gli intervalli e i passi dei parametri da ottimizzare, la migliore posizione di produzione, il miglior valore di soluzione e le funzioni ausiliarie.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_GWO //wolfpack
{
  //============================================================================
  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search
  public: S_Wolf wolves    []; //wolves of the pack
  public: double cB        []; //best prey coordinates
  public: double pB;           //best prey

  public: void InitPack (const int    coordinatesP,   //number of opt. parameters
                         const int    wolvesNumberP,  //wolves number
                         const int    alphaNumberP,   //alpha beta delta number
                         const int    epochCountP);   //epochs number

  public: void TasksForWolves      (int epochNow);
  public: void RevisionAlphaStatus ();


  //============================================================================
  private: void   ReturnToRange (S_Wolf &wolf);
  private: void   SortingWolves ();
  private: double SeInDiSp      (double In, double InMin, double InMax, double Step);
  private: double RNDfromCI     (double Min, double Max);

  private: int    coordinates;     //coordinates number
  private: int    wolvesNumber;    //the number of all wolves
  private: int    alphaNumber;     //Alpha beta delta number of all wolves
  private: int    epochCount;

  private: S_Wolf wolvesT    [];   //temporary, for sorting
  private: int    ind        [];   //array for indexes when sorting
  private: double val        [];   //array for sorting

  private: bool   searching;       //searching flag
};
//——————————————————————————————————————————————————————————————————————————————

Tradizionalmente, la dichiarazione della classe è seguita dall'inizializzazione. In questo caso, ripristiniamo il valore minimo 'double' della fitness dei lupi e distribuiamo le dimensioni degli array.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_GWO::InitPack (const int    coordinatesP,   //number of opt. parameters
                         const int    wolvesNumberP,  //wolves number
                         const int    alphaNumberP,   //alpha beta delta number
                         const int    epochCountP)    //epochs number
{
  MathSrand (GetTickCount ());
  searching = false;
  pB        = -DBL_MAX;

  coordinates  = coordinatesP;
  wolvesNumber = wolvesNumberP;
  alphaNumber  = alphaNumberP;
  epochCount   = epochCountP;

  ArrayResize (rangeMax,  coordinates);
  ArrayResize (rangeMin,  coordinates);
  ArrayResize (rangeStep, coordinates);
  ArrayResize (cB,        coordinates);

  ArrayResize (ind, wolvesNumber);
  ArrayResize (val, wolvesNumber);

  ArrayResize (wolves,  wolvesNumber);
  ArrayResize (wolvesT, wolvesNumber);

  for (int i = 0; i < wolvesNumber; i++)
  {
    ArrayResize (wolves  [i].c, coordinates);
    ArrayResize (wolvesT [i].c, coordinates);
    wolves  [i].p = -DBL_MAX;
    wolvesT [i].p = -DBL_MAX;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Il primo metodo pubblico chiamato a ogni iterazione è il più difficile da comprendere e il più voluminoso. Ecco la logica principale dell'algoritmo. In effetti, le prestazioni dell'algoritmo sono fornite da un meccanismo probabilistico strettamente descritto da equazioni. Consideriamo questo metodo passo per passo. Alla prima iterazione, quando la posizione della preda prevista è sconosciuta, dopo aver controllato il flag, inviamo i lupi in una direzione casuale semplicemente generando i valori massimi e minimi dei parametri ottimizzati.

//----------------------------------------------------------------------------
//space has not been explored yet, then send the wolf in a random direction
if (!searching)
{
  for (int w = 0; w < wolvesNumber; w++)
  {
    for (int c = 0; c < coordinates; c++)
    {
      wolves [w].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]);
      wolves [w].c [c] = SeInDiSp  (wolves [w].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
   
  searching = true;
  return;
}

Nella versione canonica della descrizione dell'algoritmo, ci sono equazioni che operano sui vettori. Tuttavia, sono molto più chiari sotto forma di codice. Il calcolo dei lupi omega viene eseguito prima del calcolo dei lupi alfa, beta e delta, perché è necessario utilizzare i valori del leader precedente.

Il componente principale che prevede tre fasi di caccia (ricerca, accerchiamento e attacco) è il rapporto a. Rappresenta una dipendenza non lineare dall'iterazione corrente e dal numero totale di iterazioni, e tende a 0.
Le componenti successive dell'equazione sono Ai e Сi:

• Ai = 2,0 * a * r1 - a;
• Ci = 2,0 * r2;

dove r1 e r2 sono numeri casuali nell'intervallo [0,0;1,0].
Nell'espressione le coordinate dei lupi vengono regolate in base ai valori medi dei lupi leader. Poiché nell'algoritmo si può specificare un numero qualsiasi di leader, la somma delle coordinate viene eseguita in un ciclo. Successivamente, la cifra risultante viene divisa per il numero di leader. Eseguiamo questa operazione separatamente per ogni coordinata, generando ogni volta nuovi valori di r1 e r2. Come si può notare, la nuova posizione dei lupi omega viene regolata in base alle posizioni dei leader, tenendo conto della loro posizione attuale.

//----------------------------------------------------------------------------
double a  = sqrt (2.0 * (1.0 - (epochNow / epochCount)));
double r1 = 0.0;
double r2 = 0.0;

double Ai = 0.0;
double Ci = 0.0;
double Xn = 0.0;

double min = 0.0;
double max = 1.0;

//omega-----------------------------------------------------------------------
for (int w = alphaNumber; w < wolvesNumber; w++)
{
  Xn = 0.0;

  for (int c = 0; c < coordinates; c++)
  {
    for (int abd = 0; abd < alphaNumber; abd++)
    {
      r1 = RNDfromCI (min, max);
      r2 = RNDfromCI (min, max);
      Ai = 2.0 * a * r1 - a;
      Ci = 2.0 * r2;
      Xn += wolves [abd].c [c] - Ai * (Ci * wolves [abd].c [c] - wolves [w].c [c]);
    }

    wolves [w].c [c] = Xn /= (double)alphaNumber;
  }

  ReturnToRange (wolves [w]);
}

Ecco il calcolo dei leader. Per loro vengono calcolati i rapporti a, Ai e Ci per ciascuna coordinata. L'unica differenza è che la posizione dei leader cambia in relazione alle coordinate della preda migliore in quel momento e alle proprie posizioni. I leader girano intorno alla preda, entrando e uscendo, e controllano i lupi minori nell'attacco.

//alpha, beta, delta----------------------------------------------------------
for (int w = 0; w < alphaNumber; w++)
{
  for (int c = 0; c < coordinates; c++)
  {
    r1 = RNDfromCI (min, max);
    r2 = RNDfromCI (min, max);

    Ai = 2.0 * a * r1 - a;
    Ci = 2.0 * r2;

    wolves [w].c [c] = cB [c] - Ai * (Ci * cB [c] - wolves [w].c [c]);
  }

  ReturnToRange (wolves [w]);
}

Questo è il secondo metodo pubblico richiamato a ogni iterazione. Lo stato dei leader del branco è aggiornato qui. Infatti, i lupi sono ordinati per valore di fitness. Se vengono trovate coordinate di prede migliori di quelle memorizzate nello sciame, aggiorniamo i valori.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_GWO::RevisionAlphaStatus ()
{
  SortingWolves ();

  if (wolves [0].p > pB)
  {
    pB = wolves [0].p;
    ArrayCopy (cB, wolves [0].c, 0, 0, WHOLE_ARRAY);
  }
}
//——————————————————————————————————————————————————————————————————————————————

3. Funzioni di test

Conoscete già le funzioni Skin, Forest e Megacity. Queste funzioni di prova soddisfano tutti i criteri di complessità per la verifica degli algoritmi di ottimizzazione. Tuttavia, c'è una caratteristica che non è stata presa in considerazione. Dovrebbe essere implementata per aumentare l'obiettività del test. I requisiti sono i seguenti:

1. L'estremo globale non dovrebbe trovarsi ai confini dell'intervallo. Se l'algoritmo non dispone di un controllo out-of-range , è possibile che si verifichino situazioni in cui l'algoritmo mostri risultati eccellenti. Ciò è dovuto al fatto che i valori si troveranno sui bordi a causa di un difetto interno.
2. L'estremo globale non deve trovarsi al centro dell'intervallo delle coordinate. In questo caso, si tiene conto dell'algoritmo che genera valori mediati in un intervallo.
3. Il minimo globale deve essere situato al centro delle coordinate. Questo è necessario per escludere deliberatamente le situazioni descritte in p. 2.
4. Il calcolo dei risultati della funzione di test deve tenere conto del caso in cui i numeri generati a caso sull'intero dominio della funzione (quando la funzione è multivariabile) daranno un risultato medio di circa il 50% del massimo, anche se in realtà questi risultati sono stati ottenuti per caso.
   

Tenendo conto di questi requisiti, i confini delle funzioni di test sono stati rivisti e i centri dell'intervallo sono stati spostati verso i minimi dei valori delle funzioni. Permettetemi di riassumere ancora una volta. Questo è stato necessario per ottenere la massima plausibilità e oggettività dei risultati dei test degli algoritmi di ottimizzazione. Pertanto, sulle nuove funzioni test, l'algoritmo di ottimizzazione basato sulla generazione di numeri casuali ha mostrato un risultato complessivo naturalmente basso. La tabella di valutazione aggiornata si trova alla fine dell'articolo.

Funzione Skin. Una funzione regolare che presenta diversi estremi locali che possono confondere l'algoritmo di ottimizzazione che può bloccarsi in uno di essi. L'unico estremo globale è caratterizzato da valori che cambiano debolmente nelle vicinanze. Questa funzione mostra chiaramente la capacità dell'algoritmo di essere suddiviso in aree di studio, piuttosto che concentrarsi su una sola. In particolare, l'algoritmo della colonia di api (ABC) si comporta in questo modo.

Fig. 4. Test funzione Skin

Funzione Forest. Una funzione con diversi estremi regolari e diversi estremi non differenziabili. Si tratta di un valido test per gli algoritmi di ottimizzazione per la capacità di trovare un "ago in un pagliaio". Trovare un singolo punto di massimo globale è un compito molto difficile, soprattutto se la funzione contiene molte variabili. L'algoritmo della colonia di formiche (ACO) si è distinto in questo compito per il suo comportamento caratteristico, che traccia i percorsi verso l'obiettivo in modo incredibile.

Figura 5 Test funzione Forest

Funzione Megacity. La funzione è un problema di ottimizzazione discreta con un estremo globale e diversi estremi locali. La superficie estremamente complessa da studiare fornisce un buon test per gli algoritmi che richiedono un gradiente. Un'ulteriore complessità è data da un "piano" completamente uniforme, che è anche un minimo, che non fornisce alcuna informazione sulla possibile direzione verso il massimo globale.

Figura 6 Test funzione Megacity

Nel codice delle funzioni di test sono stati aggiunti controlli sugli argomenti in entrata per verificare la presenza di valori out-of-range. Nelle versioni precedenti delle funzioni, gli algoritmi di ottimizzazione potevano ottenere ingiustamente valori della funzione più grandi di quelli che la funzione ha effettivamente nell'intervallo della sua definizione.

4. Risultati del test

A causa delle modifiche apportate alle funzioni di test, anche il banco di prova è stato aggiornato. Sul lato destro della schermata del banco, è ancora possibile vedere i grafici di convergenza degli algoritmi di ottimizzazione. La linea verde indica i risultati della convergenza su funzioni a due variabili. La linea blu rappresenta le funzioni con 40 variabili. Quella rossa indica funzioni con 1000 variabili. Il cerchio nero più grande indica la posizione del massimo globale della funzione. Il cerchio nero più piccolo indica la posizione dell'attuale valore della soluzione dell'algoritmo di ottimizzazione. Il crocino di linee bianche indica il centro geometrico delle funzioni di test e corrisponde al minimo globale. Questo è stato introdotto per una migliore percezione visiva del comportamento degli algoritmi testati. I punti bianchi indicano le soluzioni intermedie mediate. I puntini colorati indicano le coppie di coordinate della dimensione corrispondente. Il colore indica la posizione ordinale della dimensione della funzione di test.

I risultati aggiornati dei test degli algoritmi di ottimizzazione discussi negli articoli precedenti sul nuovo banco sono visibili nella tabella aggiornata. Per una maggiore chiarezza visiva, la linea relativa alla velocità di convergenza è stata rimossa dalla tabella - può essere determinata visivamente sull'animazione del banco. Aggiunta la colonna con la descrizione dell'algoritmo.

Risultati del test ACOm (Ant Colony Optimization):

Risultato dei test (Colonia di api artificiali):

Risultati del test ABC (Colonia Artificiale di Api):

Risultati del test PSO (Particle Swarm Optimization)

Risultati del test RND (casuale):

  GWO sulla funzione di test Skin

GWO sulla funzione di test Forest

  GWO sulla funzione di test Megacity

Risultati del test GWO.

Il Gray Wolves Optimization Algorithm (GWO) è uno dei recenti algoritmi di ottimizzazione bioispirati, basato sulla simulazione della caccia di un branco di lupi grigi. In media, l'algoritmo si è dimostrato abbastanza efficiente su vari tipi di funzioni, sia in termini di accuratezza nel trovare un estremo sia in termini di velocità di convergenza. In alcuni test si è rivelato il migliore. I principali indicatori prestazionali dell'algoritmo di ottimizzazione "Gray Wolves" sono migliori di quelli dell'algoritmo di ottimizzazione sciame di particelle, ritenuto "convenzionale" nella classe degli algoritmi di ottimizzazione bioispirati.

Allo stesso tempo, la complessità computazionale dell'algoritmo di ottimizzazione Gray Wolves è paragonabile a quella dell'algoritmo di ottimizzazione sciame di particelle. Grazie ai numerosi vantaggi dell'algoritmo di ottimizzazione GWO, in breve tempo sono apparsi molti lavori sulla sua modifica da quando l'algoritmo è stato pubblicato. L'unico inconveniente dell'algoritmo è la scarsa precisione delle coordinate trovate della funzione sharp-maximum di Forest.

La scarsa accuratezza dell'estremo trovato si è manifestata in tutte le dimensioni della funzione di Forest, e i risultati sono i peggiori tra tutti i partecipanti alla tabella. L'algoritmo si è dimostrato efficiente sulla funzione regolare Skin, soprattutto nel caso di funzioni Skin di dimensioni maggiori. Il GWO è anche terzo nella classifica per aver raggiunto il 100% di successo nel massimo globale sulla funzione Megacity.

AO	Descrizione	Skin			Forest			Megacity (discreta)			Risultato finale
		2 parametri (1 F)	40 parametri (20 F)	1000 parametri (500 F)	2 parametri (1 F)	40 parametri (20 F)	1000 parametri (500 F)	2 parametri (1 F)	40 parametri (20 F)	1000 parametri (500 F)
ACOm	ottimizzazione della colonia di formiche	0.98229	0.79108	0.12602	1.00000	0.62077	0.11521	0.38333	0.44000	0.02377	0.49805222
ABCm	colonia di api artificiale M	1.00000	0.63922	0.08076	0.99908	0.20112	0.03785	1.00000	0.16333	0.02823	0.46106556
ABC	colonia di api artificiale	0.99339	0.73381	0.11118	0.99934	0.21437	0.04215	0.85000	0.16833	0.03130	0.46043000
GWO	ottimizzatore lupo grigio	0.99900	0.48033	0.18924	0.83844	0.08755	0.02555	1.00000	0.10000	0.02187	0.41577556
PSO	ottimizzazione sciame di particelle	0.99627	0.38080	0.05089	0.93772	0.14540	0.04856	1.00000	0.09333	0.02233	0.40836667
RND	casuale	0.99932	0.44276	0.06827	0.83126	0.11524	0.03048	0.83333	0.09000	0.02403	0.38163222

Conclusioni: