Algoritmi di ottimizzazione della popolazione: Algoritmo della Lucciola (Firefly FA)

Contenuto

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

1. Introduzione

La natura è sempre stata fonte di ispirazione per molti algoritmi meta-euristici. È riuscita a trovare soluzioni ai problemi senza chiedere conferma, basandosi sull'esperienza individuale. La selezione naturale e la sopravvivenza del più adatto sono state la motivazione principale per la creazione dei primi algoritmi meta-euristici. In natura, gli animali comunicano tra loro in molti modi. Le lucciole usano la loro capacità di lampeggiare per comunicare. Esistono circa 2.000 specie di lucciole con i loro particolari modelli di lampi. Di solito producono un breve lampo con uno schema specifico. La luce e la sua intensità diventano il risultato di processi biochimici chiamati bioluminescenze. Si ritiene che la funzione principale di questi lampi sia quella di attirare gli accoppiamenti e le potenziali vittime. Alcune lucciole tropicali possono sincronizzare i loro lampi, dimostrando così un esempio di auto-organizzazione biologica. L'intensità della luce, in funzione della distanza dalla sorgente, obbedisce a una legge quadratica inversa, per cui la luce tremolante proveniente da una lucciola provoca la reazione delle lucciole intorno ad essa nel raggio d'azione del lampo.

Esistono due varianti di algoritmi di ottimizzazione delle popolazioni ispirate al comportamento delle lucciole: l'algoritmo Firefly e l'algoritmo Glowworm Swarm Optimization (GSO). La differenza principale tra firefly e glowworms è che queste ultime sono prive di ali. In questo articolo considereremo il primo tipo di algoritmo di ottimizzazione.

2. Descrizione dell'algoritmo

L'algoritmo firefly (F-algorithm) è stato proposto da X-Sh. Yang all'Università di Cambridge (Regno Unito) nel 2007 e ha immediatamente attirato l'attenzione dei ricercatori di ottimizzazione. L'algoritmo firefly fa parte di una famiglia di algoritmi di intelligenza a sciame che hanno recentemente mostrato risultati impressionanti nella risoluzione di problemi di ottimizzazione. L'algoritmo firefly, in particolare, viene utilizzato per risolvere problemi di ottimizzazione continua e discreta.

L'algoritmo firefly ha tre regole basate sulle caratteristiche di sfarfallio delle lucciole reali. Le regole sono le seguenti:

1. Tutte le lucciole si orienteranno verso controparti più attraenti e luminose.
2. Il grado di attrazione di una lucciola è proporzionale alla sua luminosità, che diminuisce all'aumentare della distanza da un'altra lucciola a causa del fatto che l'aria assorbe la luce. Pertanto, tra due lucciole tremolanti, quella meno luminosa si muoverà verso quella più luminosa. Se non c'è una controparte più luminosa o più attraente, una lucciola si muove in modo casuale.
3. La luminosità o l'intensità luminosa della lucciola è determinata dal valore della funzione obiettivo del problema.

Inizialmente, all'inizio dell'algoritmo, tutte le lucciole sono disperse a caso nello spazio di ricerca. L'algoritmo determina quindi le partizioni ottimali in base a due fasi:

1. Variazione dell'intensità luminosa - la luminosità della lucciola nella sua posizione attuale si riflette nel valore del suo fitness, spostandosi verso una lucciola attraente.
2. La lucciola cambia la sua posizione osservando l'intensità luminosa delle lucciole vicine.

Ora possiamo approfondire la complessità dell'ottimizzazione firefly. L'essenza dell'algoritmo è mostrata chiaramente nella Figura 1.

Fig. 1. Lucciole nello spazio di ricerca. La visibilità diminuisce con l'aumentare della distanza

L'idea principale alla base del principio di ricerca è una diminuzione non lineare della visibilità all'aumentare della distanza tra le lucciole. Senza questa relazione non lineare, ogni lucciola si sposterebbe in modo deterministico verso una sorgente di luce più luminosa. Tuttavia, come si vede nella Figura 1, la lucciola non sceglie il suo simile più luminoso, poiché la sua luce è meno evidente a causa dell'assorbimento della luce da parte dell'ambiente. Sceglie invece una controparte meno luminosa (anche se la più luminosa del suo ambiente). Questa caratteristica spiega la buona capacità dell'algoritmo di dividere in sciami più piccoli. Ciò si verifica naturalmente solo a causa della funzione non lineare di assorbimento della luce da parte della distanza. Nella Figura 2 qui sotto, possiamo vedere la funzione della visibilità rispetto alla distanza per l'algoritmo con diversi valori del coefficiente di assorbimento del gamma medio, che è uno dei parametri dell'algoritmo.

Fig. 2. La funzione della trasparenza del medio dalla distanza f(x), dove il coefficiente di trasparenza gamma è pari rispettivamente a 1.0, 0.2, 0.05, 0.01.

Quando gamma tende all'infinito, l'ambiente diventa opaco, mentre quando gamma è zero, l'ambiente è completamente trasparente e ogni lucciola vede l'altra a qualsiasi distanza nello spazio di ricerca. Cosa succede se gamma = 0.0? Tutte le lucciole voleranno verso il simile più luminoso convergendo verso un punto non ottimale. Pertanto, l'algoritmo non convergerà rimanendo bloccato in uno degli estremi locali. Cosa succede se l'ambiente è completamente opaco? Le lucciole non vedranno nessuno più attraente di loro. Secondo il concetto proposto dall'autore dell'algoritmo, il fatto di non vedere nessuno migliore di sé fa sì che la lucciola si muova in modo casuale. L'algoritmo degenera in una ricerca casuale. Nella nostra tabella di classificazione degli algoritmi, l'algoritmo di ricerca casuale occupa l'ultimo posto.  

Approfondiamo l'analisi dell'algoritmo e consideriamo le equazioni che descrivono i movimenti delle lucciole. La funzione di visibilità rispetto alla distanza è alla base del calcolo del cosiddetto indice di attrattività:

attractiveness = fireflies [k].f / (1.0 + gamma * distance * distance);

dove:
attractiveness - si spiega da sé
gamma - coefficiente di opacità dell'ambiente
distance - Distanza euclidea tra le lucciole
fireflies [k].f - intensità luminosa della k-esima lucciola

L'equazione chiarisce che la funzione di attrattività dipende direttamente dalla dimensione del problema e dai limiti del valore della distanza, pertanto l'autore dell'algoritmo raccomanda di selezionare il coefficiente di trasparenza per uno specifico problema di ottimizzazione. Ritengo che sia scomodo e dispendioso in termini di tempo, farlo senza sapere in anticipo come si comporterà l'algoritmo, quindi penso che sia necessario normalizzare i valori della distanza nell'intervallo da 0 a 20. Per ottenere questo risultato, applicare la funzione Scale () che abbiamo ripetutamente utilizzato in altri algoritmi. La conversione della "distanza" prima del calcolo dell'attrattività si presenta come segue:

distance = Scale (distance, 0.0, maxDist, 0.0, 20.0, false);

dove:

maxDist - massima distanza Euclidea tra una coppia di lucciole e tutte le altre

In questo caso, l'attrattiva delle lucciole non dipenderà dalla dimensione del problema e non sarà necessario selezionare il coefficiente gamma per uno specifico problema di ottimizzazione. La funzione di attrattività determina il tipo di scelta di accoppiamento che ogni lucciola farà. Questa scelta è strettamente determinata. L'influenza dell'attrattiva reciproca delle lucciole determina il coefficiente beta (il secondo parametro dell'algoritmo). Come vengono garantite le capacità di ricerca dell'algoritmo se la scelta delle lucciole è già determinata in anticipo ad ogni iterazione corrispondente? A tal fine, vengono introdotti un componente vettoriale casuale e il terzo parametro dell'algoritmo (alfa). Le complesse relazioni comportamentali delle lucciole si presentano così:

fireflies [i].c [c] = Xj + beta * (Xi - Xj) + alpha * r * v [c];

dove:
fireflies [i].c [c] - coordinata c-esima della lucciola i-esima
beta - coefficiente di influenza dell'attrazione delle lucciole
alfa - coefficiente che influisce sulla componente casuale durante lo spostamento delle lucciole, fornendo deviazioni dall'obiettivo di movimento
r - numero casuale nell'intervallo [-1.0;1.0].
v[c] - componente del vettore che caratterizza la distanza tra i punti estremi dell'intervallo di ricerca per la coordinata c-esima
Хj - coordinata corrispondente della lucciola nella coppia, verso la quale ci sarà il movimento
Xi - coordinata corrispondente della lucciola per la quale viene calcolato il movimento

Ora è il momento di descrivere il codice dell'algoritmo. È relativamente semplice. Consideriamolo in modo più dettagliato.

Una lucciola sarà descritta con una semplice struttura S_Firefly caratterizzata da due componenti, ovvero [] - coordinate, f - luminosità della lucciola (funzione di fitness). Poiché per ogni lucciola c”è solo un individuo all'iterazione corrispondente, verso il quale si muoverà formando una coppia, non rischiamo di sovrascrivere le coordinate quando calcoliamo il movimento successivo. A questo scopo, introdurrò una struttura speciale considerata di seguito.

//——————————————————————————————————————————————————————————————————————————————
struct S_Firefly
{
  double c  []; //coordinates
  double f;     //the value of the fitness function
};
//——————————————————————————————————————————————————————————————————————————————

La struttura S_Attractiveness serve a memorizzare il valore di attrazione e il numero della lucciola corrispondente come coppia. Ogni lucciola non si muove verso le coordinate di quella più attraente, ma verso le coordinate in cui si è già mossa la sua compagna. C'è qualche discrepanza con la versione dell'algoritmo descritta dall'autore, ma lavora meglio.

//——————————————————————————————————————————————————————————————————————————————
struct S_Attractiveness
{
  double a; //attractiveness
  int    i; //index of the most attractive firefly
};
//——————————————————————————————————————————————————————————————————————————————

L'algoritmo della lucciola è descritto utilizzando la classe C_AO_FA. Ci sono tre metodi pubblici, uno dei quali è Init() per l'inizializzazione iniziale e due metodi pubblici necessari per essere richiamati ad ogni iterazione - Flight() and Luminosity(), metodi di aiuto privati e membri per memorizzare i parametri delle costanti.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_FA
{
  //----------------------------------------------------------------------------
  public: S_Firefly fireflies []; //fireflies
  public: double    rangeMax  []; //maximum search range
  public: double    rangeMin  []; //minimum search range
  public: double    rangeStep []; //step search
  public: double    cB        []; //best coordinates
  public: double    fB;           //FF of the best coordinates

  public: void Init (const int    paramsP,  //number of opt. parameters
                     const int    sizeP,    //swarm size
                     const double alphaP,   //alpha, randomness in motion
                     const double betaP,    //beta, effect of attractiveness
                     const double gammaP);  //gamma, transparency of the environment

  public: void Flight ();
  public: void Luminosity ();

  //----------------------------------------------------------------------------
  private: S_Attractiveness att [];
  private: int    swarmSize;
  private: int    params;
  private: double maxDist;
  private: double v [];

  private: double alpha;      //randomness in motion
  private: double beta;       //effect of attractiveness
  private: double gamma;      //transparency of the environment
  private: bool   luminosity;

  private: double SeInDiSp  (double In, double inMin, double inMax, double step);
  private: double RNDfromCI (double min, double max);
  protected: double Scale   (double In, double InMIN, double InMAX, double OutMIN, double OutMAX,  bool revers);
};
//——————————————————————————————————————————————————————————————————————————————

Il metodo aperto Init() viene utilizzato per l'inizializzazione e deve essere richiamato prima dell'inizio di ogni ottimizzazione. I suoi parametri sono parametri di sovrastruttura per l'algoritmo. Il metodo allocherà memoria per gli array e reimposta il valore di luminosità globale e di ogni singola lucciola.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FA::Init (const int    paramsP, //number of opt. parameters
                    const int    sizeP,   //swarm size
                    const double alphaP,  //alpha, randomness in motion
                    const double betaP,   //beta, effect of attractiveness
                    const double gammaP)  //gamma, transparency of the environment
{
  fB = -DBL_MAX;

  params    = paramsP;
  swarmSize = sizeP;
  alpha     = alphaP;
  beta      = betaP;
  gamma     = gammaP;

  ArrayResize (rangeMax,  params);
  ArrayResize (rangeMin,  params);
  ArrayResize (rangeStep, params);
  ArrayResize (v,         params);
  ArrayResize (att,       swarmSize);

  luminosity = false;

  ArrayResize (fireflies, swarmSize);

  for (int i = 0; i < swarmSize; i++)
  {
    ArrayResize (fireflies [i].c,  params);
    fireflies [i].f = -DBL_MAX;
  }

  ArrayResize (cB, params);
}
//——————————————————————————————————————————————————————————————————————————————

Consideriamo il primo metodo pubblico chiamato a ogni iterazione: Flight(). La logica principale dell'algoritmo è concentrata in questo metodo, quindi è necessario considerarlo in modo più dettagliato. La variabile "luminosity" è un indicatore che ci permette di determinare se l'algoritmo viene eseguito alla prima iterazione o alle successive. Se il flag non è impostato, è necessario distribuire le lucciole in modo casuale nello spazio delle coordinate, secondo la distribuzione uniforme. Insieme a questa azione, impostiamo il vettore di spostamento per ogni coordinata e calcoliamo immediatamente la massima distanza Euclidea possibile tra le lucciole (come già detto, questo è necessario per normalizzare le distanze tra le lucciole al fine di evitare la dipendenza del coefficiente di trasparenza dell'ambiente dalla dimensione del problema). Dopo queste operazioni, attivare il flag "luminosity".

if (!luminosity)
{
  fB = -DBL_MAX;

  //--------------------------------------------------------------------------
  double summCoordinates = 0.0;
  for (int c = 0; c < params; c++)
  {
    v [c] = rangeMax [c] - rangeMin [c];
    summCoordinates += pow (v [c], 2.0);
  }
  maxDist = pow (summCoordinates, 0.5);

  //--------------------------------------------------------------------------
  for (int s = 0; s < swarmSize; s++)
  {
    for (int k = 0; k < params; k++)
    {
      fireflies [s].c  [k] = RNDfromCI (rangeMin [k], rangeMax [k]);
      fireflies [s].c  [k] = SeInDiSp (fireflies [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
    }
  }

  luminosity = true;
}

Dalla seconda e dalle successive iterazioni, dopo che le lucciole sono state distribuite in modo casuale alla prima iterazione e hanno iniziato a brillare (la funzione di fitness è stata calcolata per loro), è possibile calcolare il grado di attrattività per ogni lucciola. Per farlo, dobbiamo calcolare la distanza euclidea tra tutte le possibili coppie di lucciole. E’ sufficiente sommare i quadrati delle differenze di coordinate e trovare la radice dalla loro somma. La distanza calcolata sarà utilizzata nell'equazione per il calcolo dell'attrattività. In questo modo si ottiene l'unica coppia possibile per ogni lucciola. Determinare la luminosità massima di tutte le lucciole. Questo sarà necessario per determinare la lucciola più luminosa, per la quale non sarà possibile trovare una coppia e che vagherà nello spazio da sola. Forse sarà più fortunato durante la prossima iterazione.

//measure the distance between all------------------------------------------
for (int i = 0; i < swarmSize; i++)
{
  att [i].a = -DBL_MAX;

  for (int k = 0; k < swarmSize; k++)
  {
    if (i == k) continue;

    summCoordinates = 0.0;
    for (int c = 0; c < params; c++) summCoordinates += pow (fireflies [i].c [c] - fireflies [k].c [c], 2.0);

    distance = pow (summCoordinates, 0.5);
    distance = Scale (distance, 0.0, maxDist, 0.0, 20.0, false);
    attractiveness = fireflies [k].f / (1.0 + gamma * distance * distance);

    if (attractiveness > att [i].a)
    {
      att [i].a = attractiveness;
      att [i].i = k;
    }

    if (fireflies [i].f > maxF) maxF = fireflies [i].f;
  }
}

Questa parte del codice del metodo Flight() è responsabile del volo delle lucciole. Per la sfortunata lucciola, la cui luminosità è maggiore di tutte le altre, il calcolo viene eseguito in modo diverso. Aggiungiamo il vettore di movimento alla sua posizione attuale attraverso il coefficiente alfa moltiplicato per un numero casuale [-1,0;1,0]. Teoricamente, nell'algoritmo, questo agisce come un ulteriore studio della soluzione migliore, con l'aspettativa che sia ancora migliore; tuttavia, come vedremo in seguito, questa tecnica si rivelerà inutile. In questa fase, consideriamo la versione classica dell'algoritmo.

Per tutte le altre lucciole, per le quali è già stata trovata una coppia, il calcolo del movimento consisterà nel dirigersi verso la coppia appropriata con l'aggiunta di una componente casuale (ne ho parlato prima).

//flight--------------------------------------------------------------------
for (int i = 0; i < swarmSize; i++)
{
  if (fireflies [i].f >= maxF)
  {
    for (int c = 0; c < params; c++)
    {
      r  = RNDfromCI (-1.0, 1.0);
      fireflies [i].c [c] = fireflies [i].c [c] + alpha * r * v [c];
      fireflies [i].c [c] = SeInDiSp (fireflies [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); 
    }
  }
  else
  {
    for (int c = 0; c < params; c++)
    {
      r  = RNDfromCI (-1.0, 1.0);
      Xi = fireflies [i].c [c];
      Xj = fireflies [att [i].i].c [c];
      fireflies [i].c [c] = Xj + beta * (Xi - Xj) + alpha * r * v [c];
      fireflies [i].c [c] = SeInDiSp (fireflies [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}

Un semplice metodo aperto chiamato a ogni iterazione. Qui aggiorneremo la soluzione migliore.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FA::Luminosity ()
{
  for (int i = 0; i < swarmSize; i++)
  {
    if (fireflies [i].f > fB)
    {
      fB = fireflies [i].f;
      ArrayCopy (cB, fireflies [i].c, 0, 0, WHOLE_ARRAY);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Passiamo ai test. Vediamo i risultati dell'algoritmo sulle funzioni di test:

2022.12.16 13:39:00.102 Test_AO_FA (EURUSD,M1) =============================
2022.12.16 13:39:05.930 Test_AO_FA (EURUSD,M1) 1 Skin's; Func cicli 10000 risultati: 4.901742065217812
2022.12.16 13:39:05.930 Test_AO_FA (EURUSD,M1) Punteggio: 0.99603
2022.12.16 13:39:13.579 Test_AO_FA (EURUSD,M1) 20 Skin's; Func cicli 10000 risultati: 3.2208359936020665
2022.12.16 13:39:13.579 Test_AO_FA (EURUSD,M1) Punteggio: 0.59468
2022.12.16 13:39:53.607 Test_AO_FA (EURUSD,M1) 500 Skin's; Func cicli 10000 risultati: 0.98491319842575
2022.12.16 13:39:53.607 Test_AO_FA (EURUSD,M1) Punteggio: 0.06082
2022.12.16 13:39:53.607 Test_AO_FA (EURUSD,M1) =============================
2022.12.16 13:39:59.313 Test_AO_FA (EURUSD,M1) 1 Forest's; Func cicli 10000 risultati: 1.578196881663454
2022.12.16 13:39:59.313 Test_AO_FA (EURUSD,M1) Punteggio: 0.89271
2022.12.16 13:40:07.274 Test_AO_FA (EURUSD,M1) 20 Forest's; Func cicli 10000 risultati: 0.3101994341994826
2022.12.16 13:40:07.274 Test_AO_FA (EURUSD,M1) Punteggio: 0.17546
2022.12.16 13:40:49.159 Test_AO_FA (EURUSD,M1) 500 Forest's; Func cicli 10000 risultati: 0.06829102669136165
2022.12.16 13:40:49.159 Test_AO_FA (EURUSD,M1) Punteggio: 0.03863
2022.12.16 13:40:49.159 Test_AO_FA (EURUSD,M1) =============================
2022.12.16 13:40:54.895 Test_AO_FA (EURUSD,M1) 1 Megacity's; Func cicli 10000 risultati: 8.2
2022.12.16 13:40:54.895 Test_AO_FA (EURUSD,M1) Punteggio: 0.68333
2022.12.16 13:41:02.777 Test_AO_FA (EURUSD,M1) 20 Megacity's; Func cicli 10000 risultati: 1.5900000000000003
2022.12.16 13:41:02.777 Test_AO_FA (EURUSD,M1) Punteggio: 0.13250
2022.12.16 13:41:43.901 Test_AO_FA (EURUSD,M1) 500 Megacity's; Func cicli 10000 risultati: 0.2892
2022.12.16 13:41:43.901 Test_AO_FA (EURUSD,M1) Punteggio: 0.02410
2022.12.16 13:41:43.901 Test_AO_FA (EURUSD,M1) =============================
2022.12.16 13:41:43.901 Test_AO_FA (EURUSD,M1) Tutti i punteggi per C_AO_FA: 0.39980648892951776

I risultati sono poco impressionanti, per usare un eufemismo. L'algoritmo è solo leggermente migliore di PSO, FSS e GWO nei singoli test. Tuttavia, nell'indicatore di valutazione totale, si trova in seconda posizione dal basso, lasciando indietro solo l'algoritmo di ricerca casuale. Alla luce di tutto ciò, è nata l'idea di rivedere il calcolo degli indicatori stimati nei test. Nei prossimi articoli passerò a uno schema di calcolo del punteggio più conveniente, mentre in questo articolo aggiungerò l'istogramma dei risultati finali. Mostrerà chiaramente il rapporto di prestazioni tra i singoli algoritmi.

Il classico algoritmo Firefly è facile da implementare. Tuttavia, gli studi dimostrano che converge lentamente e cade facilmente nella trappola degli estremi locali per problemi multimodali. Inoltre, manca di coefficienti che dipendono parametricamente dall'iterazione corrente. Pertanto, uno degli obiettivi dello studio è stato quello di modificare l'algoritmo Firefly standard per migliorarne le prestazioni.

L'idea stessa dell'algoritmo è piuttosto originale e sarebbe un peccato lasciare tutto com'è e non cercare di migliorarne le caratteristiche. Pertanto, ho cercato di modificare l'algoritmo sostituendo la componente casuale con un volo Levy. Il volo di Levy non può migliorare la capacità di ricerca di ogni algoritmo. Dopo aver preso in considerazione l”algoritmo di ricerca a cucù, ho cercato di migliorare altri algoritmi utilizzando questo metodo, ma ciò non ha portato ai risultati attesi. A quanto pare, questo dovrebbe essere coerente in qualche modo con la strategia di ricerca interna all'algoritmo che la completa. In questo caso particolare, l'applicazione del Volo di Levy ha prodotto un effetto sorprendente - le capacità dell'algoritmo sono aumentate drasticamente. Ne parleremo nella parte dell'articolo dedicata ai risultati dei test.

Ecco la parte del codice in cui è stata apportata la modifica. Innanzitutto, nella versione classica, la lucciola con la migliore luminosità si muove in una direzione casuale dalla sua posizione attuale. Quindi la nostra migliore lucciola si muove dalla migliore posizione globale cercando di migliorare non la sua posizione attuale, ma la soluzione nel suo complesso. Aggiungere alle coordinate della soluzione migliore un numero casuale della distribuzione del volo di Levy (distribuzione con code pesanti) con lo stesso coefficiente alfa, tenendo conto del vettore di movimento. In questo modo è stato possibile migliorare le coordinate della soluzione globale affinando l'area vicina.

Come si può vedere, il comportamento del resto delle lucciole obbedisce ora alle stesse classiche regole, sebbene aggiustate per la componente casuale del volo di Levy. Questa è l'intera modifica apportata all'algoritmo.

//flight--------------------------------------------------------------------
for (int i = 0; i < swarmSize; i++)
{
  if (fireflies [i].f >= maxF)
  {
    for (int c = 0; c < params; c++)
    {
      r1 = RNDfromCI (0.0, 1.0);
      r1 = r1 > 0.5 ? 1.0 : -1.0;
      r2 = RNDfromCI (1.0, 20.0);

      fireflies [i].c [c] = cB [c] + alpha * r1 * pow (r2, -2.0) * v [c];
      fireflies [i].c [c] = SeInDiSp (fireflies [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
  else
  {
    for (int c = 0; c < params; c++)
    {
      r1 = RNDfromCI (0.0, 1.0);
      r1 = r1 > 0.5 ? 1.0 : -1.0;
      r2 = RNDfromCI (1.0, 20.0);

      Xi = fireflies [i].c [c];
      Xj = fireflies [att [i].i].c [c];

      fireflies [i].c [c] = Xj + beta * (Xi - Xj) + alpha * r1 * pow (r2, -2.0) * v [c];
      fireflies [i].c [c] = SeInDiSp (fireflies [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}

Grafico della funzione del volo di Levy in Fig. 3. In che modo l'esponente nell'equazione della funzione influisce sul comportamento dell'algoritmo? Secondo le mie ricerche, all'aumentare del grado, il numero di salti lunghi (code pesanti) diminuisce rispetto a quelli brevi, mentre migliora la capacità dell'algoritmo di affinare le coordinate in prossimità della soluzione migliore. A causa del fatto che ci sono pochi salti lunghi, la probabilità di rimanere bloccati in estremi locali aumenta. Questo effetto sarà più evidente quando si studiano funzioni discrete, mentre non sarà così pronunciato per quelle regolari. Al contrario, con una diminuzione dell'esponente, il numero di salti lunghi aumenta, le capacità di ricerca dell'algoritmo migliorano, ma l'accuratezza della convergenza peggiora, quindi abbiamo bisogno di una via di mezzo tra accuratezza e ricerca. Inoltre, può essere diverso a seconda del problema di ottimizzazione.

Fig. 3. Funzione di volo di Levy, gradi 0,5...3,0 

Passiamo quindi ai risultati della versione modificata dell'algoritmo sul banco di prova. Qui di seguito potete vedere quanto sono migliorate le prestazioni della versione originale rispetto a quella classica.

2022.12.16 13:07:15.925 Test_AO_FAm (EURUSD,M1) =============================
2022.12.16 13:07:21.544 Test_AO_FAm (EURUSD,M1) 1 Skin's; Func cicli 10000 risultati: 4.854437214435259
2022.12.16 13:07:21.544 Test_AO_FAm (EURUSD,M1) Punteggio: 0.98473
2022.12.16 13:07:29.518 Test_AO_FAm (EURUSD,M1) 20 Skin; Func cicli 10000 risultati: 4.588539001298423
2022.12.16 13:07:29.518 Test_AO_FAm (EURUSD,M1) Punteggio: 0.92124
2022.12.16 13:08:12.587 Test_AO_FAm (EURUSD,M1) 500 Skin; Func cicli 10000 risultati: 1.981278990090829
2022.12.16 13:08:12.587 Test_AO_FAm (EURUSD,M1) Punteggio: 0.29872
2022.12.16 13:08:12.587 Test_AO_FAm (EURUSD,M1) =============================
2022.12.16 13:08:18.336 Test_AO_FAm (EURUSD,M1) 1 Forest's; Func cicli 10000 risultati: 1.7665409595127233
2022.12.16 13:08:18.336 Test_AO_FAm (EURUSD,M1) Punteggio: 0.99924
2022.12.16 13:08:26.432 Test_AO_FAm (EURUSD,M1) 20 Forest”s; Func cicli 10000 risultati: 0.6261364994589462
2022.12.16 13:08:26.432 Test_AO_FAm (EURUSD,M1) Punteggio: 0.35417
2022.12.16 13:09:10.587 Test_AO_FAm (EURUSD,M1) 500 Forests; Func cicli 10000 risultati: 0.14269062630878
2022.12.16 13:09:10.587 Test_AO_FAm (EURUSD,M1) Punteggio: 0.08071
2022.12.16 13:09:10.587 Test_AO_FAm (EURUSD,M1) =============================
2022.12.16 13:09:16.393 Test_AO_FAm (EURUSD,M1) 1 Megacity's; Func cicli 10000 risultati: 10.0
2022.12.16 13:09:16.393 Test_AO_FAm (EURUSD,M1) Punteggio: 0.83333
2022.12.16 13:09:24.373 Test_AO_FAm (EURUSD,M1) 20 Megacity's; Func cicli 10000 risultati: 1.7899999999999998
2022.12.16 13:09:24.373 Test_AO_FAm (EURUSD,M1) Punteggio: 0.14917
2022.12.16 13:10:09.298 Test_AO_FAm (EURUSD,M1) 500 Megacity's; Func cicli 10000 risultati: 0.5076
2022.12.16 13:10:09.298 Test_AO_FAm (EURUSD,M1) Punteggio: 0.04230
2022.12.16 13:10:09.298 Test_AO_FAm (EURUSD,M1) =============================
2022.12.16 13:10:09.298 Test_AO_FAm (EURUSD,M1) Tutti i punteggi per C_AO_FAm: 0.5181804234713119

Come si può vedere, l'algoritmo modificato non solo mostra risultati migliori, ma occupa una posizione di primo piano nella tabella di valutazione. Analizziamo più da vicino i risultati nella prossima sezione. Di seguito è riportata un'animazione della versione modificata dell'algoritmo sul banco di prova.

  FAm sulla funzione test Skin .

  FAm sulla funzione di test Forest .

  FAm sulla funzione di test Megacity.

3. Risultati del test

L'algoritmo firefly modificato (FAm) ha ottenuto risultati eccellenti in tutti i test. In generale, i risultati dipendono dalle impostazioni dell'algoritmo. In alcune impostazioni è stato raggiunto il 100% di convergenza su tutte e tre le funzioni a due variabili. L'elevata scalabilità dell'algoritmo garantisce la leadership nei test con 40 e 1000 parametri. I parametri beta e gamma esercitano una forte influenza, consentendo di ottenere sia un'elevata convergenza sia la resistenza a rimanere bloccati negli estremi locali. I risultati variano molto, che in generale possono essere attribuiti agli svantaggi dell'algoritmo. A parità di condizioni, l'algoritmo è il più forte tra quelli considerati in precedenza. Può essere raccomandato per l'uso in un'ampia gamma di attività, tra cui l'apprendimento automatico e l'intelligenza artificiale, in particolare per l'addestramento delle reti neurali.

Di seguito è riportata la tabella di valutazione finale, in cui l'algoritmo firefly modificato è in testa. Purtroppo, l'algoritmo classico, nonostante la sua originalità, non è riuscito a ottenere buoni risultati. Anche la selezione dei parametri di regolazione non ha portato al successo.

AO	Descrizione	Skin			Finale Skin	Forest			Finale Forest	Megacity (discreta)			Finale Megacity	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)
FAm	algoritmo firefly M	0.98473	0.92124	0.29872	0.73490	0.99924	0.35417	0.08071	0.47804	0.83333	0.14917	0.04230	0.34160	0.51817889
COAm	algoritmo di ottimizzazione a cucù M	1.00000	0.85911	0.14316	0.66742	0.99283	0.28787	0.04551	0.44207	1.00000	0.24917	0.03537	0.42818	0.51255778
ACOm	ottimizzazione della colonia di formiche M	0.98229	0.79108	0.12602	0.63313	1.00000	0.62077	0.11521	0.57866	0.38333	0.44000	0.02377	0.28237	0.49805222
ABCm	colonia di api artificiali M	1.00000	0.63922	0.08076	0.57333	0.99908	0.20112	0.03785	0.41268	1.00000	0.16333	0.02823	0.39719	0.46106556
ABC	colonia di api artificiali	0.99339	0.73381	0.11118	0.61279	0.99934	0.21437	0.04215	0.41862	0.85000	0.16833	0.03130	0.34988	0.46043000
GWO	ottimizzazione del lupo grigio	0.99900	0.48033	0.18924	0.55619	0.83844	0.08755	0.02555	0.31718	1.00000	0.10000	0.02187	0.37396	0.41577556
FSS	ricerca del banco di pesci	0.99391	0.5692	0.11341	0.55884	0.85172	0.12143	0.03223	0.33513	0.91667	0.08583	0.02583	0.34278	0.41224778
PSO	ottimizzazione sciame di particelle	0.99627	0.38080	0.05089	0.47599	0.93772	0.14540	0.04856	0.37723	1.00000	0.09333	0.02233	0.37189	0.40836667
FA	algoritmo firefly	0.99603	0.59468	0.06082	0.55051	0.89271	0.17546	0.03863	0.36893	0.68333	0.13250	0.02410	0.27998	0.39980649
RND	casuale	0.99932	0.44276	0.06827	0.50345	0.83126	0.11524	0.03048	0.32566	0.83333	0.09000	0.02403	0.31579	0.38163222

A partire da questo articolo, pubblicherò un istogramma, sul quale il miglior algoritmo al momento del test avrà 100 punti condizionali, mentre il peggiore avrà 1 punto. Ritengo che questo sia il metodo di visualizzazione più conveniente in termini di percezione visiva, poiché possiamo chiaramente vedere la scala dei risultati finali della tabella di valutazione degli algoritmi. Ora possiamo vedere quanto l'algoritmo casuale sia in ritardo rispetto al leader.

Fig. 4. Istogramma dei risultati finali degli algoritmi di test

Come forse ricorderete, gli algoritmi meta-euristici sono metodi approssimativi per la risoluzione di problemi di ottimizzazione che utilizzano la proprietà della casualità con un'assunzione ragionevole nel loro motore di ricerca e provano a migliorare la qualità delle soluzioni disponibili attraverso iterazioni da un insieme di valide soluzioni generate casualmente, esaminando e utilizzando lo spazio delle soluzioni. Sebbene questi algoritmi non sono garantiti come ottimali, sono testati per fornire una soluzione ragionevole e accettabile. Inoltre, hanno il vantaggio del fatto di non essere influenzati dal comportamento del problema e questo li rende utili in molti compiti. La presenza della disponibilità di molti algoritmi consente di scegliere quello appropriato per la risoluzione di un problema, a seconda del suo comportamento.

Dopo l'avvento degli algoritmi evolutivi, sono state condotte numerose ricerche sugli algoritmi euristici. L'implementazione di nuovi algoritmi è stata una delle principali aree di ricerca. Attualmente esistono più di 40 algoritmi meta-euristici. La maggior parte di essi viene creata simulando scenari naturali.

I pro e i contro si riferiscono a una versione modificata dell'algoritmo Firefly (FAm).

Pro:

• Implementazione semplice. Facile da modificare.
• Elevata scalabilità.
• Alta convergenza (può variare in base alle impostazioni dell'algoritmo).
• La capacità di raggruppare la regione dello spazio di ricerca in gruppi separati intorno agli estremi locali.

Contro:

• Forte influenza delle impostazioni sui risultati dell'ottimizzazione.
• Con alcune impostazioni, l'algoritmo è incline a bloccarsi negli estremi locali.

Ogni articolo presenta un archivio che contiene le versioni aggiornate dei codici degli algoritmi per tutti gli articoli precedenti. Ogni nuovo articolo è frutto dell'esperienza personale accumulata dall'autore e le conclusioni e i giudizi si basano su esperimenti effettuati su uno speciale banco di prova sviluppato a questo scopo.