Algoritmi di ottimizzazione della popolazione: Ricerca del Banco di Pesci (FSS)

MetaTrader 5 — Esempi | 3 ottobre 2023, 16:11

329

Andrey Dik

Contenuto

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

1. Introduzione

Un'aggregazione di pesci è il termine generale per qualsiasi insieme di pesci riuniti in una certa località. Le aggregazioni di pesci possono essere strutturate o non strutturate. Un'aggregazione non strutturata potrebbe essere un gruppo di specie e dimensioni miste che si sono radunate casualmente vicino ad alcune risorse locali, come cibo o siti di nidificazione.

Se, inoltre, l'aggregazione, si riunisce in modo interattivo e sociale, vengono detti banchi. La maggior parte di loro si trova nella stessa fase del proprio ciclo vitale, sono in contatto attivo tra loro e in qualsiasi momento può esibire attività biologicamente attive e organizzate utili per i membri del gruppo.
A differenza dell'individuo, lo stile di vita socievole è un compromesso tra il vantaggio di vivere in gruppo in termini di maggiore protezione dai predatori e una maggiore competizione nel procacciarsi il cibo.

I pesci formano banchi in natura in diversi modi. Di regola preferiscono banchi grandi, costituiti solo da individui della propria specie. Qualsiasi membro del branco che si distingue per il suo aspetto o ha qualche tipo di differenza diventa un bersaglio primario per i predatori. Questo fatto spiega perché i pesci preferiscono banchi di individui identici. In questo modo si ottiene l'omogeneità dell'intero banco.

Un banco è organizzato in modo abbastanza rigido quando i pesci nuotano in modo sincrono alla stessa velocità e nella stessa direzione. Ciò accade perché i pesci sono della stessa specie, età e dimensione e si spostano ad una certa distanza l'uno dall'altro. I banchi di pesci sono in grado di eseguire manovre complesse, come se avessero un'intelligenza di gruppo e una mente comune.
Le sottigliezze della formazione del banco sono lungi dall'essere pienamente comprese, soprattutto gli aspetti relativi al movimento e alle modalità di alimentazione.

Sono state avanzate molte ipotesi per spiegare il comportamento socievole, tra cui un migliore orientamento, la sincronizzazione della caccia, la confusione dei predatori e un ridotto rischio di essere catturati. I pesci nei banchi sembrano condividere informazioni controllando il comportamento degli altri a distanza ravvicinata. Il comportamento alimentare di un pesce stimola rapidamente la ricerca attiva di cibo negli altri. I pesci in branco nuotano in sottili falangi, facendo spesso rapide salite e discese e ruotando attorno al proprio asse, mentre cambiano la forma del banco evitando collisioni tra loro. Tali manovre richiedono un sistema di risposta molto veloce. Uno stile di vita da banco implica che i pesci abbiano sistemi sensoriali in grado di rispondere istantaneamente a piccoli cambiamenti nella loro posizione rispetto ai loro vicini.

Per creare un quadro più completo, viene utilizzata la modellazione matematica di tale comportamento. I modelli matematici più comuni presuppongono che i singoli animali in un banco seguano tre regole di base:

Muoversi nella stessa direzione del vicino
Restare vicino ai vicini
Evitare collisioni con individui vicini

La questione su come i pesci del banco scelgano la direzione in cui nuotare rimane irrisolta. Durante le migrazioni, sembra che la maggior parte dei membri del gruppo sappia dove andare, se tutti i membri di un banco sono ugualmente consapevoli della disponibilità di cibo. Ci sono ancora alcuni leader del gruppo che sono più audaci di altri loro simili. Questo comportamento del banco ha spinto molti ricercatori a creare non solo un modello matematico, ma anche un modello algoritmico per risolvere vari problemi di ottimizzazione.

2. Descrizione dell'algoritmo

La Ricerca del Banco di Pesci (FSS) è una sottofamiglia di algoritmi di intelligenza a sciame appartenenti alla classe degli algoritmi metaeuristici. Fu proposto da Bastos Filho e Lima Neto nel 2008 e pubblicato per la prima volta nel 2009. In FSS gli agenti semplici sono chiamati pesci, e ogni pesce ha un peso che rappresenta il "successo" ottenuto durante la ricerca. I valori e le variazioni dei pesi influiscono sui movimenti individuali e collettivi. L’alimentazione integrata e i meccanismi di azione coordinata forzano il banco a muoversi nella direzione di un gradiente positivo per aumentare di peso e trovare i posti migliori a livello locale e globale. FSS è stato sviluppato per problemi di ottimizzazione continua negli spazi di ricerca multimodali. Ciò ha spinto anche altri ricercatori a proporre opzioni per risolvere altri problemi, come l’ottimizzazione nei problemi binari e l’ottimizzazione multiobiettivo.

Nell'algoritmo FSS, è possibile semplificare l'immagine che i pesci nuotano in un acquario condizionale, le cui pareti sono i confini del dominio della definizione della funzione studiata. Il peso del pesce è una misura del successo nella ricerca del cibo (soluzioni). Inoltre, svolge il ruolo della memoria del pesce. La presenza del peso è l'idea principale dell'algoritmo e la differenza da uno sciame di particelle. Questa caratteristica dell’algoritmo FSS elimina la necessità di trovare e fissare le migliori soluzioni globali, come nel caso di uno sciame di particelle.

Gli operatori dell'algoritmo FSS sono divisi in due gruppi:
- l'operatore addetto all'alimentazione formalizza il successo dell'esplorazione dell'area
- gli operatori del nuoto, implementano algoritmi di migrazione per i singoli pesci e per il banco nel suo insieme

L'operatore addetto all’alimentazione è un calcolo del peso del pesce. L'idea di base è far "nuotare" i pesci verso un gradiente positivo in modo da "mangiare" e "aumentare di peso". Collettivamente, i pesci più pesanti hanno un effetto maggiore sull’intero processo di ricerca, che fa sì che il centro della massa del banco di pesci si sposti verso posizioni migliori nello spazio di ricerca nel corso delle iterazioni. L'incremento di peso ad una data iterazione è proporzionale alla differenza normalizzata nei valori della funzione di fitness:

fishes [f].weight = fishes [f].weight + (fishes [f].delta_fitness / max_delta_fitness);

dove:

weight - peso del pesce
delta_fitness - differenza tra i valori della funzione di fitness
max_delta_fitness - valore massimo della differenza nelle funzioni di fitness tra tutti i pesci

Gli operatori flottanti sono divisi in tre tipologie in base al tipo di movimento:

- individuale;

- istintivo-collettivo;

- volitivo-collettivo;

Il nuoto individuale può essere interpretato come una ricerca locale nelle vicinanze della posizione attuale del pesce. Il vettore di movimento di ciascun individuo è direzionato in modo casuale e ha un valore diverso.

fishes [f].new_position [d] = fishes [f].current_position [d] + step_ind [d] * r;

dove:

new_position - nuova posizione alla coordinata corrispondente
current_position - posizione corrente sulla coordinata corrispondente
step_ind - passo del movimento individuale calcolato come

initial_step_ind * (rangeMax [d] - rangeMin [d]);

dove:

initial_step_ind - parametro dell'algoritmo per il movimento individuale
rangeMax e rangeMin: intervalli di valori degli argomenti ottimizzati
r - numero casuale [-1.0;1.0]

Schematicamente, il nuoto individuale è mostrato nella Figura 1.

Individuale

Fig.1. Nuoto individuale. Il vettore di movimento di ciascun pesce è direzionato in una direzione casuale e ha un valore scalare diverso

Dopo il nuoto individuale viene misurata la funzione di fitness. Se la posizione risultante del pesce non è migliorata, allora consideriamo che questo particolare pesce non ha avuto alcun movimento e rimane al suo posto. Solo quei pesci che hanno migliorato le loro funzioni di fitness si sposteranno in una nuova posizione.

Dopo il completamento della nuotata individuale viene eseguito l’operatore del movimento istintivo-collettivo. Diamo prima un'occhiata alla Figura 2.

raccolta

Fig 2. Nuoto istintivo-collettivo Il movimento è caratterizzato per tutti i pesci dallo stesso vettore di direzione e grandezza rispetto al centro di massa G.

Il movimento istintivo-collettivo serve a correggere la posizione generale del banco di pesci tenendo in considerazione il cambiamento nella funzione di fitness di ciascun pesce nell'iterazione precedente. Le nuove coordinate vengono calcolate come segue:

fishes [f].new_position [d] = fishes [f].current_position [d] + collective_instinct [d];

dove:

new_position - nuova posizione del pesce alle coordinate corrispondenti
current_position - posizione corrente sulla coordinata corrispondente
collective_instinct - quantità di movimento lungo la coordinata corrispondente calcolata come:

collective_instinct [d] = fishes [f].delta_position [d] * fishes [f].delta_fitness;

dove:

delta_position - differenza tra le coordinate della posizione attuale e quella precedente ottenuta nella fase del nuoto individuale
delta_fitness - modifica delle funzioni di fitness della posizione attuale e di quella precedente durante il nuoto individuale

Il nuoto istintivo-collettivo formalizza il movimento sincrono di gruppo di un banco di pesci verso un nuovo luogo fornendo la ricerca di nuovi luoghi di cibo, mentre il movimento individuale consente di migliorare la situazione localmente.

Consideriamo ora il nuoto volitivo-collettivo. Si divide in due tipologie:

- dal centro della massa - se non si è verificato il miglioramento della posizione del banco nel suo insieme rispetto alla posizione precedente, mentre i pesci si sono allargati ai lati simboleggiando un'ulteriore ricerca di cibo (Figura 3)

- movimento verso il centro di massa se si è verificato il miglioramento. Quindi il pesce si sposta al centro della massa, stringendo l'anello e simboleggiando l'attacco alla preda. Algoritmicamente, ciò significa affinare la soluzione del problema di ottimizzazione (Figura 4).

col vol fuori

Fig. 3. Nuoto volitivo-collettivo. I vettori di direzione sono diretti dal centro di massa G

col vol dentro

Fig. 4. Nuoto volitivo-collettivo. I vettori di direzione sono diretti verso il centro di massa G

Viene introdotto il concetto di centro di massa per il calcolo del nuoto volitivo-collettivo. Da qui, l’equazione del nuoto volitivo-collettivo sarà simile a questa:

fishes [f].new_position [d] = pos + (((pos - barycenter [d]) * step_vol [d] * r) * search_operator);

dove:

pos è la stessa current_position
search_operator - 1 se la mossa precedente ha portato un miglioramento della posizione e -1 in caso contrario
step_vol [d] - passo del movimento collettivo, calcolato come:

step_vol [d] = initial_step_vol * (rangeMax [d] - rangeMin [d]);

dove:

initial_step_vol - parametro dell'algoritmo per il movimento collettivo
barycenter [d] - centro di massa calcolato come la somma dei pesi dei pesci moltiplicata per le coordinate:

barycenter [d] += fishes [f].weight * fishes [f].current_position [d];

e diviso per il peso totale del banco di pesci:

barycenter [d] /= current_total_weight;

Lo pseudo codice dell'algoritmo è simile al seguente:

1) inizializza le posizioni dei pesci con numeri casuali

2) movimenti individuali

3) calcolo della funzione di fitness

4) ridefinizione dei pesi per ogni pesce

5) movimento istintivo-collettivo

6) movimento volitivo-collettivo

7) ricalcolo del peso totale

8) calcolo della funzione di fitness

9) ripetere dal punto 2) fino a quando non viene soddisfatto il criterio di arresto

Schema FSS

Figura 5. Diagramma a blocchi dell'algoritmo FSS

Iniziamo a descrivere il codice.

Come puoi immaginare, l'unità logica più semplice dell'algoritmo è la struttura che descrive il pesce. Dato che dovremo inizializzare i pesci più volte, è consigliabile “azzerare” questa struttura a causa delle sue dimensioni relativamente grandi nell'apposito metodo Init(), che ci consentirà di ottimizzare leggermente il codice. La struttura include gli array delle coordinate per la posizione corrente, la nuova posizione e la differenza in coordinate dall'ultimo spostamento. Il peso predefinito è pari a 1000 unità standard ma può avere qualsiasi valore. Il pesce è contraddistinto anche dal valore della funzione di fitness attuale, da quella precedente e dalla loro differenza. Nel metodo Init(), la funzione di fitness viene inizializzata con il valore 'double' minimo possibile. Quindi, la differenza di fitness è zero, poiché i pesci non si sono ancora mossi.

//——————————————————————————————————————————————————————————————————————————————
struct S_Fish
{
  void Init (int dimensions)
  {
    ArrayResize (current_position, dimensions);
    ArrayResize (new_position,     dimensions);
    ArrayResize (delta_position,   dimensions);
    weight        = 1000.0;
    fitness       = -DBL_MAX;
    delta_fitness = 0.0;
  }

  double current_position [];
  double new_position     [];
  double delta_position   [];
  double weight;
  double fitness;
  double new_fitness;
  double delta_fitness;
};
//——————————————————————————————————————————————————————————————————————————————

Dichiariamo la classe C_AO_FSS - un banco di pesci che rappresenta matematicamente un naturale modello di comunità. Non c'è niente di insolito qui. Sono inoltre necessari due metodi pubblici per l'interazione con il programma utente - gli intervalli dei valori della funzione ottimizzata necessari per tenere conto delle coordinate dei pesci e dell'interazione in un banco, nonché gli array.

Nel metodo pubblico della classe di inizializzazione Init (), è necessario reimpostare le variabili sui valori originali e allocare la memoria per gli array. Prestare particolare attenzione alle variabili init e swimmingRegime. Secondo lo pseudo codice che abbiamo visto, il calcolo della funzione di fitness viene eseguito due volte: la prima volta - dopo un movimento individuale, la seconda volta - dopo i due tipi di movimento collettivo. Questo contraddice lo schema di collegamento algoritmo-applicazione da noi adottato, il quale prevede che ogni iterazione sia caratterizzata da una sequenza: primo_metodo -> funzioni_calcolo_fitness -> secondo_metodo. Queste due variabili vengono applicate per risolvere questo problema e modificare la sequenza delle azioni nell'algoritmo canonico. La variabile init dovrebbe essere "false" all'inizio dell'algoritmo. Questo è un flag che indica la necessità di inizializzare i pesci, calcolare la funzione di fitness e ripetere il movimento, poiché l'intera logica dell'algoritmo utilizza la differenza tra il valore attuale e quello precedente delle coordinate e della funzione di fitness. Senza ciò, non saremmo stati in grado di ottenere la differenza del valore. La seconda flag importante è il swimmingRegime. Ci consente di ridefinire l'ordine dei metodi di chiamata che descrivono il movimento dei pesci in modo che corrispondano alla nostra struttura. Il valore 1 corrisponde al richiamo del nuoto “individuale”, altrimenti utilizziamo la sequenza di movimenti di gruppo che abbiamo considerato sopra.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::Init (const int    dimensionsP,
                     const int    fishSchSizeP,
                     const double initial_step_indP,
                     const double initial_step_volP)
{
  MathSrand (GetTickCount ());
  init = false;
  swimmingRegime = 1;

  dimensions     = dimensionsP;

  ArrayResize (rangeMax,  dimensions);
  ArrayResize (rangeMin,  dimensions);
  ArrayResize (rangeStep, dimensions);

  num_of_individuos = fishSchSizeP;

  ArrayResize (fishes, num_of_individuos);

  for (int i = 0; i < num_of_individuos; i++)
  {
    fishes [i].Init (dimensions);
  }

  global_best = -DBL_MAX;
  ArrayResize (global_best_position, dimensions);

  total_weight     = num_of_individuos;

  initial_step_ind = initial_step_indP;
  ArrayResize (step_ind, dimensions);

  initial_step_vol = initial_step_volP;
  ArrayResize (step_vol, dimensions);

  ArrayResize (collective_instinct, dimensions);
  ArrayResize (barycenter, dimensions);
}
//——————————————————————————————————————————————————————————————————————————————

Il primo metodo pubblico chiamato in ciascuna iterazione Swimming () determina la sequenza delle chiamate ai movimenti dei pesci individuali e di gruppo. Se il metodo viene richiamato per la prima volta, le fasi di movimento individuali e di gruppo vengono inizializzate come parte dell'intervallo possibile lungo la coordinata corrispondente tramite i due parametri dell'algoritmo initial_step_ind e initial_step_vol. Alcuni autori consigliano di impostare i valori rispettivamente su 0.01 e 0.001. Tuttavia, con questi valori non ho ottenuto buoni risultati. Quindi utilizzo 0.1 e 0.8. Inoltre, alla prima esecuzione dell'algoritmo, il valore corrente delle coordinate di posizione del pesce viene inizializzato con numeri casuali compresi nell'intervallo dei parametri ottimizzati. I tipi di movimento appropriati verranno chiamati durante le successive chiamate di metodo in conformità con il flag swimmingRegime.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::Swimming (int i)
{
  //----------------------------------------------------------------------------
  if (!init)
  {
    global_best    = -DBL_MAX;
    swimmingRegime = 1;

    for (int d = 0; d < dimensions; d++)
    {
      step_ind [d] = initial_step_ind * (rangeMax [d] - rangeMin [d]);
      step_vol [d] = initial_step_vol * (rangeMax [d] - rangeMin [d]);
    }

    for (int f = 0; f < num_of_individuos; f++)
    {
      fishes [f].Init (dimensions);

      for (int d = 0; d < dimensions; d++)
      {
        fishes [f].new_position [d] = RNDfromCI (rangeMin [d], rangeMax [d]);
        fishes [f].new_position [d] = SeInDiSp (fishes [f].new_position [d], rangeMin [d], rangeMax [d], rangeStep [d]);
      }
    }
  }
  //----------------------------------------------------------------------------
  else
  {
    switch (swimmingRegime)
    {
    case 1:
      apply_individual_movement ();            //individual movement
      break;
    default:
      apply_instintive_collective_movement (); //instinctively-collective movement
      apply_collective_volitive_movement ();   //collective-volitional movement
      update_total_weight ();                  //recalculate the total weight
      break;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Il secondo metodo pubblico chiamato ad ogni iterazione Regrouping () è destinato principalmente a determinare l'ordine delle chiamate ai metodi di nuoto - individuale, istintivo-collettivo, volitivo-collettivo. Funzionalità aggiuntive del metodo per garantire l'ordine delle chiamate sono fornite dal flag SwimmingRegime, che assume i valori 1 e 2. Ciò è necessario per ridefinire l'ordine di chiamata dei metodi di movimento dei pesci nella versione classica per la struttura da me adottata: primo_metodo_apertura -> _calcolo_funzione_fitness -> secondo_metodo_apertura. A seconda del flag Init, se l'algoritmo è alla prima iterazione, memorizzeremo la posizione corrente delle coordinate e il valore della funzione di fitness per un ulteriore calcolo delle loro differenze, poiché si presuppone che il metodo venga chiamato dopo il calcolo della funzione di fitness. Se il flag Init indica che l'algoritmo è alla seconda e alle successive iterazioni, allora, dopo un movimento individuale, è necessario ottenere la differenza tra i valori attuali e quelli precedenti della funzione di fitness, nonché la differenza tra le coordinate delle posizioni attuali e quelle precedenti. Le differenze vengono calcolate a condizione che la posizione sia migliorata, altrimenti consideriamo che non c’è stato alcun movimento. Quindi, riportiamo i valori del peso del pesce allo stato iniziale e le differenze nei movimenti e nelle funzioni di fitness vengono prese pari a zero. Aggiorniamo immediatamente la soluzione migliore, se viene raggiunta, chiamando il metodo update_optimal_solution(), nonché applichiamo l'alimentazione dei pesci con il metodo apply_feeding(). Se il flag di swimmingRegime non è uguale a 1, allora sono stati applicati i movimenti istintivi-collettivi e volitivi-collettivi. Dopo la loro esecuzione, impostiamo SwimmingRegime su 1. Il prossimo sarà un movimento individuale.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::Regrouping ()
{
  //----------------------------------------------------------------------------
  if (swimmingRegime == 1
  {
    if (!init)
    {
      for (int f = 0; f < num_of_individuos; f++)
      {
        ArrayCopy (fishes [f].current_position, fishes [f].new_position, 0, 0, WHOLE_ARRAY);
        ArrayInitialize (fishes [f].delta_position, 0.0);

        fishes [f].fitness = fishes [f].new_fitness;
        fishes [f].delta_fitness = 0.0;
      }

      init = true;
      return;
    }

    for (int f = 0; f < num_of_individuos; f++)
    {
      //remember the best position for the fish
      if (fishes [f].new_fitness > fishes [f].fitness)
      {
        fishes [f].delta_fitness = fishes [f].new_fitness - fishes [f].fitness; //fabs
        fishes [f].fitness = fishes [f].new_fitness;

        for (int d = 0; d < dimensions; d++)
        {
          fishes [f].delta_position [d] = fishes [f].new_position [d] - fishes [f].current_position [d];
        }

        ArrayCopy (fishes [f].current_position, fishes [f].new_position, 0, 0, WHOLE_ARRAY);
      }
      else
      {
        ArrayInitialize (fishes [f].delta_position, 0.0);
        fishes [f].delta_fitness = 0.0;
      }
    }

    swimmingRegime = 2;
    updates_optimal_solution ();
    apply_feeding ();
    return;
  }

  //----------------------------------------------------------------------------
  swimmingRegime = 1;
  updates_optimal_solution ();
}
//——————————————————————————————————————————————————————————————————————————————

Il seguente semplice metodo privato viene utilizzato per aggiornare i risultati migliori dell'algoritmo se vengono raggiunti. Per fare ciò, confrontiamo semplicemente i valori della funzione di fitness di ciascun pesce con quelli globali. Se sono migliori, li salviamo.

//——————————————————————————————————————————————————————————————————————————————
// update the best overall solution
void C_AO_FSS::updates_optimal_solution ()
{
  for (int f = 0; f < num_of_individuos; f++)
  {
    if (fishes [f].fitness > global_best)
    {
      global_best = fishes [f].fitness;
      ArrayCopy (global_best_position, fishes [f].current_position, 0, 0, WHOLE_ARRAY);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Abbiamo già considerato sopra l'equazione del metodo privato che prevede il nuoto individuale. Quindi, qui tutto è semplice: alle coordinate attuali di ciascun pesce aggiungiamo un singolo passo moltiplicato per un numero casuale compreso tra -1.0 e 1.0, che dà un incremento sia in direzione positiva che negativa. Se i valori dei parametri ottimizzati vanno oltre l'intervallo, il valore del bordo viene impostato come coordinata.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::apply_individual_movement ()
{
  // move the fish to new places-----------------------------------------------
  double r = 0.0;

  for (int f = 0; f < num_of_individuos; f++)
  {
    for (int d = 0; d < dimensions; d++)
    {
      r = RNDfromCI (-1.0, 1.0);

      fishes [f].new_position [d] = fishes [f].current_position [d] + step_ind [d] * r;
      fishes [f].new_position [d] = SeInDiSp (fishes [f].new_position [d], rangeMin [d], rangeMax [d], rangeStep [d]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Il metodo di alimentazione non dovrebbe causare difficoltà di comprensione. Il peso del pesce, infatti, è determinato come il quoziente tra la differenza nella funzione di fitness del pesce stesso e il valore massimo della differenza tra l'intero banco di pesci. Tuttavia, può accadere che la differenza massima tra tutti i pesci sia pari a zero. La descrizione della versione classica dell'algoritmo dice che il peso del pesce deve essere sempre positivo. Generalmente vengono considerati solo i casi in cui la funzione di fitness assume valori positivi, ma non ho trovato senso pratico in questo requisito. Ammetto che il peso dei pesci può assumere valori negativi, perciò se la differenza massima della funzione di fitness (questo è il valore a cui dobbiamo normalizzare il peso di ciascun pesce) è zero tra tutti i pesci, allora il peso del pesce viene considerato uguale a 1.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::apply_feeding ()
{
  double max_delta_fitness = -DBL_MAX;

  //find the maximum weight among fish
  for (int f = 0; f < num_of_individuos; f++)
  {
    if (fishes [f].delta_fitness > max_delta_fitness) max_delta_fitness = fishes [f].delta_fitness;
  }

  //feed the fish
  for (int f = 0; f < num_of_individuos; f++)
  {
    if (max_delta_fitness != 0.0)
    {
      fishes [f].weight = fishes [f].weight + (fishes [f].delta_fitness / max_delta_fitness);
    }
    else fishes [f].weight = 1;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Il metodo privato del movimento istintivo-collettivo consiste nel modificare le coordinate di ciascun pesce incrementando il valore dell'istinto collettivo, che a sua volta non è altro che il prodotto della differenza della posizione dell'iterazione corrente e di quella precedente per la differenza della funzione di fitness ottenuta nei movimenti precedenti. Qui assegniamo i valori dei limiti quando si oltrepassano i limiti dei parametri ottimizzati.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::apply_instintive_collective_movement ()
{
  double sum_delta_fitness = 0.0;
  for (int f = 0; f < num_of_individuos; f++)
  {
    sum_delta_fitness += fishes [f].delta_fitness;
  }

  for (int f = 0; f < num_of_individuos; f++)
  {
    for (int d = 0; d < dimensions; d++)
    {
      collective_instinct [d] = fishes [f].delta_position [d] * fishes [f].delta_fitness;

      if (sum_delta_fitness != 0.0)
      {
        collective_instinct [d] /= sum_delta_fitness;
      }

      fishes [f].new_position [d] = fishes [f].current_position [d] + collective_instinct [d];
      fishes [f].new_position [d] = SeInDiSp (fishes [f].new_position [d], rangeMin [d], rangeMax [d], rangeStep [d]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Il metodo privato del nuoto volitivo collettivo, in cui viene calcolato il centro di massa di un banco di pesci e il peso totale attuale. Se il peso totale del banco è aumentato, i pesci iniziano a muoversi verso il centro di massa, altrimenti si allontanano dal centro. L'equazione è stata discussa in dettaglio in precedenza. Il peso totale di un banco di pesci viene aggiornato con un metodo speciale discusso di seguito.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::apply_collective_volitive_movement ()
{
  //----------------------------------------------------------------------------
  double current_total_weight = 0.0;

  for (int f = 0; f < num_of_individuos; f++)
  {
    current_total_weight += fishes [f].weight;
  }

  ArrayInitialize (barycenter, 0.0);

  for (int f = 0; f < num_of_individuos; f++)
  {
    for (int d = 0; d < dimensions; d++)
    {
      barycenter [d] += fishes [f].weight * fishes [f].current_position [d];
    }
  }

  for (int d = 0; d < dimensions; d++)
  {
    barycenter [d] /= current_total_weight;
  }

  //----------------------------------------------------------------------------
  double search_operator = current_total_weight > total_weight ? 1.0 : -1.0;
  double r   = 0.0;
  double pos = 0.0;

  for (int f = 0; f < num_of_individuos; f++)
  {
    for (int d = 0; d < dimensions; d++)
    {
      r = RNDfromCI (0.0, 1.0);
      pos = fishes [f].current_position [d];

      fishes [f].new_position [d] = pos + (((pos - barycenter [d]) * step_vol [d] * r) * search_operator);
      fishes [f].new_position [d] = SeInDiSp (fishes [f].new_position [d], rangeMin [d], rangeMax [d], rangeStep [d]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

In realtà, questo è proprio il metodo per aggiornare il peso totale dei pesci. Tutto è semplice qui. Prendiamo il peso di ogni pesce e lo sommiamo.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::update_total_weight ()
{
  total_weight = 0.0;

  for (int f = 0; f < num_of_individuos; f++)
  {
    total_weight += fishes [f].weight;
  }
}
//——————————————————————————————————————————————————————————————————————————————

3. Risultati del test

Passiamo alla parte finale e più interessante - i risultati. L'algoritmo contiene trucchi interessanti, come l'assenza della necessità di tenere conto dell'ottimo globale, l'introduzione dei concetti di centro di massa e movimento istintivo-volitivo, implicando convergenza o dispersione dal centro del banco, a seconda che la posizione nel suo complesso sia stata migliorata. Tutto ciò faceva ben sperare per il comportamento originale dell'algoritmo sulle funzioni studiate.

In generale, c'è originalità nel comportamento nell'area di ricerca dello spazio, cioè ci sono dispersioni di pesci in parti separate dello spazio simili a quanto osservato nell'algoritmo delle api, anche se una considerazione dettagliata delle equazioni e il principio di funzionamento del FSS non implica la dispersione del banco in gruppi separati. In generale, l’algoritmo ha funzionato male, superando solo leggermente l’algoritmo PSO in termini di risultato complessivo.

Se consideriamo i singoli test, FSS è comunque riuscita a eccellere in alcuni di essi. In particolare, sulla funzione Smooth Skin, l'algoritmo FSS si è rivelato migliore dell'algoritmo del lupo, mostrando risultati buoni (ma non i migliori), il che è facile da spiegare. L'algoritmo utilizza il gradiente della superficie della funzione in studio, considerato in incrementi per ciascuna delle coordinate, e la variazione della funzione di fitness ad ogni iterazione. Poiché la funzione Skin è fluida, l'algoritmo "si aggrappa" bene ai cambiamenti superficiali.

Per quanto riguarda la funzione Forest, l'algoritmo ha mostrato risultati inferiori alla media. Cambiamenti graduali nella funzione di test hanno in una certa misura aiutato l’algoritmo a navigare nello spazio, ma non è riuscito a trovare il massimo globale. Quando consideriamo Megacity, le carenze di FSS diventano ancora più evidenti. All'algoritmo “non piace” davvero quando la funzione studiata non cambia in prossimità della posizione attuale dei singoli agenti, e l'algoritmo non è in grado di fare lunghi salti per individuare nuovi posti potenzialmente migliori. Pertanto, si blocca qualsiasi estremo locale che non presenta un incremento nelle vicinanze.

Sebbene il test Megacity sia molto difficile per qualsiasi algoritmo di ottimizzazione e gli altri partecipanti alla tabella comparativa non siano molto più avanti rispetto a FSS in generale, è comunque necessario riconoscere le deboli capacità dell'algoritmo su problemi discreti. In alcuni test, la ricerca casuale ha mostrato il risultato migliore. Come possiamo vedere nell'animazione, non è possibile osservare alcun "clustering" nel funzionamento dell'algoritmo. Potresti ricordare l'algoritmo di ottimizzazione "cristallizzazione" descritto nell'articolo precedente.

Risultati dell'algoritmo FSS:

2022.12.08 13:14:06.033 Test_AO_FSS (EURUSD,M1) =============================
2022.12.08 13:14:08.388 Test_AO_FSS (EURUSD,M1) 1 Skin; Func cicli 10000 risultato: 4.892861444841324
2022.12.08 13:14:08.388 Test_AO_FSS (EURUSD,M1) Punteggio: 0.99391
2022.12.08 13:14:12.557 Test_AO_FSS (EURUSD,M1) 20 Skin; Func cicli 10000 risultato: 3.11410005347766
2022.12.08 13:14:12.557 Test_AO_FSS (EURUSD,M1) Punteggio: 0.56920
2022.12.08 13:14:47.176 Test_AO_FSS (EURUSD,M1) 500 Skin; Func cicli 10000 risultato: 1.20519552002827
2022.12.08 13:14:47.176 Test_AO_FSS (EURUSD,M1) Punteggio: 0.11341
2022.12.08 13:14:47.176 Test_AO_FSS (EURUSD,M1) =============================
2022.12.08 13:14:49.498 Test_AO_FSS (EURUSD,M1) 1 Fores; Func cicli 10000 risultato: 1.5057381856551146
2022.12.08 13:14:49.498 Test_AO_FSS (EURUSD,M1) Punteggio: 0.85172
2022.12.08 13:14:53.825 Test_AO_FSS (EURUSD,M1) 20 Forest; Func cicli 10000 risultato: 0.21468156279781656
2022.12.08 13:14:53.825 Test_AO_FSS (EURUSD,M1) Punteggio: 0.12143
2022.12.08 13:15:31.235 Test_AO_FSS (EURUSD,M1) 500 Forest; Func cicli 10000 risultato: 0.056970068652984526
2022.12.08 13:15:31.235 Test_AO_FSS (EURUSD,M1) Punteggio: 0.03223
2022.12.08 13:15:31.235 Test_AO_FSS (EURUSD,M1) =============================
2022.12.08 13:15:34.066 Test_AO_FSS (EURUSD,M1) 1 Megacity; Func cicli 10000 risultato: 11.0
2022.12.08 13:15:34.066 Test_AO_FSS (EURUSD,M1) Punteggio: 0.91667
2022.12.08 13:15:38.467 Test_AO_FSS (EURUSD,M1) 20 Megacity; Func cicli 10000 risultato: 1.03
2022.12.08 13:15:38.467 Test_AO_FSS (EURUSD,M1) Punteggio: 0.08583
2022.12.08 13:16:16.589 Test_AO_FSS (EURUSD,M1) 500 Megacity; Func cicli 10000 risultato: 0.31
2022.12.08 13:16:16.589 Test_AO_FSS (EURUSD,M1) Punteggio: 0.02583
2022.12.08 13:16:16.589 Test_AO_FSS (EURUSD,M1) =============================
2022.12.08 13:16:16.589 Test_AO_FSS (EURUSD,M1) Tutti i punteggi per C_AO_FSS: 0.4122477188979048

Skin

FSS sulla funzione test Skin .

Forest

FSS sulla funzione test Forest .

Megacity

FSS sulla funzione test Megacity .

Ecco la tabella finale. Presenta colonne aggiuntive per una maggiore comodità nella valutazione degli algoritmi per ciascuna funzione di test separatamente, il che ci consente di discutere in modo più equo sull'applicabilità di ciascun algoritmo per determinate attività.

AO	Descrizione	Skin			Finale Skin	Forest			Finale Forest	Megacity (discreta)			Finale Megacity	Risultato finale
AO	Descrizione	2 parametri (1 F)	40 parametri (20 F)	1000 parametri (500 F)	Finale Skin	2 parametri (1 F)	40 parametri (20 F)	1000 parametri (500 F)	Finale Forest	2 parametri (1 F)	40 parametri (20 F)	1000 parametri (500 F)	Finale Megacity	Risultato finale
COAm	algoritmo di ottimizzazione del cuculo	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	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 dello 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
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

I metodi euristici stocastici (randomizzati) non garantiscono una soluzione precisa, ma, di norma, consentono di trovare soluzioni sufficientemente vicine per l'uso pratico in un tempo accettabile. Tuttavia, la pratica dimostra che alcuni algoritmi sono in grado di dimostrare eccellenti capacità di convergenza, sebbene questo non sia il caso di FSS. In generale, l'algoritmo di ricerca di un banco di pesci è un caso speciale di algoritmi basati su uno sciame di particelle. Perciò, ha ereditato sia vantaggi che svantaggi. Le caratteristiche uniche dell'algoritmo includono la divisione di un banco di pesci (sciame) in gruppi separati, cosa non osservata nello sciame di particelle. L'algoritmo gestisce relativamente bene le funzioni regolari, sebbene non vi sia certezza che FSS gestirà bene le funzioni con più variabili.

Pro:
1. L'algoritmo gestisce abbastanza bene le funzioni regolari.
2. La capacità di un banco di pesci di essere diviso in gruppi separati, che consente all'algoritmo di esplorare ulteriormente altri estremi locali potenzialmente buoni.

Contro:
1. Una grande dispersione di risultati nei singoli test indica l'instabilità dell'algoritmo.
2. Convergenza molto debole su funzioni discrete e su funzioni con interruzioni. Questo non è quasi applicabile per le funzioni discrete.
3. Scalabilità debole.

Tradotto dal russo da MetaQuotes Ltd.
Articolo originale: https://www.mql5.com/ru/articles/11841

File allegati |

Scarica ZIP

7_The_world_of_AO_yFSSa.zip (64.26 KB)

Avvertimento: Tutti i diritti su questi materiali sono riservati a MetaQuotes Ltd. La copia o la ristampa di questi materiali in tutto o in parte sono proibite.

Altri articoli di questo autore

Vai alla discussione

Impara come progettare un sistema di trading tramite Relative Vigor Index

Un nuovo articolo della nostra serie su come progettare un sistema di trading tramite gli indicatori tecnici più popolari. In questo articolo scopriremo come farlo grazie all'indicatore Relative Vigor Index.

Impara come progettare un sistema di trading tramite DeMarker

Ecco un nuovo articolo nella nostra serie su come progettare un sistema di trading tramite gli indicatori tecnici più popolari. In questo articolo presenteremo come creare un sistema di trading tramite l'indicatore DeMarker.

Impara come progettare un sistema di trading tramite Awesome Oscillator

In questo nuovo articolo della nostra serie, impareremo a conoscere un nuovo strumento tecnico che può essere utile per il nostro trading. Si tratta dell'indicatore Awesome Oscillator (AO). Impareremo a progettare un sistema di trading con questo indicatore.

Algoritmi di ottimizzazione della popolazione: Algoritmo di Ottimizzazione del Cuculo (COA)

Il prossimo algoritmo che considererò è l'ottimizzazione della ricerca del cuculo utilizzando i voli di Levy. Si tratta di uno dei più recenti algoritmi di ottimizzazione e di un nuovo leader in classifica.