Discussione sull’articolo "Algoritmi Genetici - È Facile!" - pagina 9

[Roman Zamozhnyy]

Suggerisco di calcolare la dimensione della popolazione:

  ChromosomeCount=GeneCount*11;                                      /Numero di cromosomi nella colonia

Recuperato da: http: //habrahabr.ru/blogs/algorithm/122222/

[Andrey Miguzov]

Grazie mille per l'articolo! Se non fosse per questo - non avrei mai imparato cosa sono i metodi genetici :)

Ma c'è una domanda! Quando controlliamo i cromosomi dal database - in caso di corrispondenza - una unità sarà sottratta dall'indice del cromosoma dal database. Perché? E cosa succede se l'indice è zero?

//Cerca i cromosomi nel database per trovare lo stesso.
    for (Ch1=0;Ch1<ChrCountInHistory && cnt<GeneCount;Ch1++)
    {
      cnt=0;
      //Controlla i geni finché l'indice genico è inferiore al numero di geni e finché vengono trovati gli stessi geni
      for (Ge=1;Ge<=GeneCount;Ge++)
      {
        if (Colony[Ge][chromos]!=historyHromosomes[Ge][Ch1])
          break;
        cnt++;
      }
    }
    //Se il numero di geni identici è lo stesso, si può prendere una soluzione già pronta dal database
    if (cnt==GeneCount)
      Colony[0][chromos]=historyHromosomes[0][Ch1-1];

Dove sbaglio?

[Andrey Dik]

Rich:

Suggerisco di calcolare la dimensione della popolazione:

Recuperato da: http: //habrahabr.ru/blogs/algorithm/122222/

Non metto in dubbio la competenza della fonte citata, ma devo dissentire.

La fattibilità dell'uso dei GA nei problemi di ottimizzazione sta nel ridurre il numero di esecuzioni di FF necessarie per determinare l'ottimo rispetto alla ricerca diretta.

Se seguiamo la raccomandazione

ChromosomeCount=GeneCount*11;  

il problema con 1000 argomenti richiederà una popolazione di 11000 individui! E si tratta di 11000 esecuzioni di FF su una sola epoca! Si può benissimo usare la generazione casuale di geni e il risultato non sarà molto inferiore nel trovare l'ottimo. La fonte data fa una "scommessa" sul fatto che in una grande popolazione ci sarà abbastanza materiale genetico per sviluppare ulteriormente la popolazione verso il miglioramento ad ogni epoca. Sto cercando di ottenere la stessa cosa, ma giocando sulle probabilità con gli operatori genetici senza aumentare il numero totale di cicli di FF.

[Andrey Dik]

MigVRN:

Grazie mille per l'articolo! Se non fosse per questo - non avrei mai imparato cosa sono i metodi genetici :)

Ma c'è una domanda! Quando controlliamo i cromosomi dal database - in caso di corrispondenza - viene sottratta un'unità dall'indice del cromosoma dal database. Perché? E cosa succede se l'indice è zero?

Dove sbaglio?

  //Se un cromosoma è memorizzato nel database
  if (ChrCountInHistory>0)
  {
    //Cerca i cromosomi nel database per trovare lo stesso.
    for (Ch1=0;Ch1<ChrCountInHistory && cnt<GeneCount;Ch1++)
    {
      cnt=0;
      //Controlla i geni finché l'indice dei geni è inferiore al numero di geni e finché 
      //... ottenere gli stessi geni.
      for (Ge=1;Ge<=GeneCount;Ge++)
      {
        if (Colony[Ge][position]!=HistoryHromosomes[Ge][Ch1])
          break;
        cnt++;
      }
    }
    //Se ci sono tanti geni identici quanti sono, possiamo prendere 
    //... soluzione pronta dal database
    if (cnt==GeneCount)
      Colony[0][position]=HistoryHromosomes[0][Ch1-1];
    //Se non esiste un cromosoma di questo tipo nel database, calcoleremo FF per esso....
    else
    {
      FitnessFunction();
      //... e se c'è spazio nel database, lo salveremo.
      if (ChrCountInHistory<10000)
      {
        for (Ge=0;Ge<=GeneCount;Ge++)
          HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
        ChrCountInHistory++;
      }
    }
  }
  //Se la base è vuota, calcolare FF per il cromosoma e memorizzarlo nella base.
  else
  {
    FitnessFunction();
    for (Ge=0;Ge<=GeneCount;Ge++)
      HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
    ChrCountInHistory++;
  }

Il database viene controllato solo se c'è almeno un cromosoma nel database. Non hai citato l'intera sezione del codice di ricerca del database.

Pertanto, il caso in cui non ci siano cromosomi nel database ma il solco venga controllato è impossibile.

[Andrey Miguzov]

joo:

Il controllo del database viene eseguito solo quando c'è almeno un cromosoma nel database. Non è stata fornita l'intera sezione del codice per la ricerca per base.

Pertanto, il caso in cui non ci siano cromosomi nel database, ma venga eseguito il controllo del solco, è impossibile.

Grazie per la risposta così tempestiva! Non intendevo esattamente quello di cui parli!

1) Supponiamo che ci sia effettivamente un cromosoma nel database (ChrCountInHistory = 1 - cioè la dimensione dell 'array è uguale a uno) - allora il suo indice nel database è zero! (ChrCountInHistory è zero per impostazione predefinita - l'indice di un elemento nell'array è zero).

E sottraiamo uno da questo indice:

Colony[0][position]=HistoryHromosomes[0][Ch1-1]; 

Inoltre, la ricerca inizia da Ch1=0.

2) Confrontiamo con HistoryHromosomes[Ge][Ch1 ] e assegniamo HistoryHromosomes[0][Ch1-1].

[Andrey Dik]

Hai ragione, grazie.

È il modo giusto per farlo:

Colony[0][position]=HistoryHromosomes[0][Ch1]; 

[Andrey Dik]

joo:

Hai ragione, grazie.

È la strada da seguire:

Hmm.

Ora"Array out of range" su HistoryHromosomes[0][Ch1], anche se tutto sembra essere corretto...

[Andrey Miguzov]

joo:

Hai ragione, grazie.

Non c'è di che! L'importante è che ora funzioni ancora meglio di prima :)

joo:

Hmm.

Ora "Array out of range" su HistoryHromosomes[0][Ch1], anche se tutto sembra essere corretto...

È difficile dire perché - abbiamo codici diversi da analizzare. Forse è la variabile "position" - il suo analogo nell'articolo è "chromos". Ho guardato il codice dell'articolo probabilmente 10 volte - non sono riuscito a capire dove sia il bug :( Controllerò più tardi gli esempi dell'articolo - forse qualcosa diventerà più chiaro.

P.S.: è giustificato usare un banco di memoria se una variabile è composta da ~150 valori. E ci sono 100000 individui nella storia. Forse in questo caso sarebbe più veloce calcolare che controllare (cercare) tutto? Non l' hai controllato?

[Andrey Dik]

MigVRN:

P.S.: è giustificato utilizzare un banco di memoria se una variabile è composta da ~150 valori. E ci sono 100000 individui nella storia. Forse in questo caso sarebbe più veloce contare che controllare (ricontrollare) tutto? Non l' avete controllato?

Tutto dipende dal tempo necessario per calcolare il FF. Se il FF è solo una funzione matematica, allora il banco non è ragionevole. Ma se la FF utilizza la cronologia (apprendimento dei neuroni, ecc.) e altri compiti ad alta intensità di risorse, allora il banco è necessario e può ridurre significativamente il tempo di ottimizzazione.

Dipende anche dall'accuratezza dei geni. Più i geni sono "grossolani", più spesso si verificheranno ripetizioni e più è ragionevole utilizzare una banca di cromosomi.

[Andrey Dik]

MigVRN:
....

:)

Comunque non c'è nessun errore, mi hai confuso molto. Qui ho fatto uno script di prova, provalo e capirai tutto.

for (Ge=1;Ge<=GeneCount;Ge++)
      {
        if (Colony[Ge][position]!=HistoryHromosomes[Ge][Ch1])
          break;
        cnt++;
      }

Qui, anche se confronta il cromosoma con la posizione di Ch1, ma nel ciclo superiore gli viene assegnato +1, quindi sottraggo -1 dopo.

Sono d'accordo, è un po' storto, potrebbe essere fatto meglio.

Ecco uno script per verificarlo:

//+------------------------------------------------------------------+
//|Controllare.mq5 |
//|Copyright 2011, JQS aka Joo |
//| https://www.mql5.com/ru/users/joo |
//+------------------------------------------------------------------+
#property copyright "Copyright 2011, JQS aka Joo"
#property link      "https://www.mql5.com/ru/users/joo"
#property version   "1.00"
//+------------------------------------------------------------------+
//| Funzione di avvio del programma di script|
//+------------------------------------------------------------------+

double Colony[][5];
double HistoryHromosomes[][3];

int ChrCountInHistory=5;
int GeneCount=5;
int position=0;

void OnStart()
{
  ArrayResize(Colony,GeneCount+1);            ArrayInitialize(Colony,0.0);
  ArrayResize(HistoryHromosomes,GeneCount+1); ArrayInitialize(HistoryHromosomes,0.0);

  Colony[1][0]=7.0;
  Colony[2][0]=8.0;
  Colony[3][0]=9.0;
  Colony[4][0]=3.0;
  Colony[5][0]=2.0;

  HistoryHromosomes[0][0]=8.0;
  //-------------------------
  HistoryHromosomes[1][0]=7.0;
  HistoryHromosomes[2][0]=8.0;
  HistoryHromosomes[3][0]=9.0;
  HistoryHromosomes[4][0]=3.0;
  HistoryHromosomes[5][0]=1.0;//un altro gene


  HistoryHromosomes[0][1]=7.0;
  //-------------------------
  HistoryHromosomes[1][1]=7.0;
  HistoryHromosomes[2][1]=8.0;
  HistoryHromosomes[3][1]=6.0;//un altro gene
  HistoryHromosomes[4][1]=3.0;
  HistoryHromosomes[5][1]=2.0;

  HistoryHromosomes[0][2]=11.0;
  //-------------------------
  HistoryHromosomes[1][2]=7.0;
  HistoryHromosomes[2][2]=8.0;
  HistoryHromosomes[3][2]=9.0;
  HistoryHromosomes[4][2]=3.0;
  HistoryHromosomes[5][2]=2.0;

  CheckHistoryChromosomes();

  Print(Colony[0][0]);
}
//+------------------------------------------------------------------+

//------------------------------------------------------------------------------
//Controllo di un cromosoma rispetto a un database di cromosomi.
void CheckHistoryChromosomes()
{
  //----------------------------------------------------------------------------
  int   Ch1=0;  /Indice cromosomico dal database
  int   Ge =0;  //Indice genico
  int   cnt=0;  //Contatore dei geni unici. Se un gene differisce 
                //- un cromosoma è riconosciuto come unico
  //----------------------------------------------------------------------------
  //Se un cromosoma è memorizzato nel database
  if (ChrCountInHistory>0)
  {
    //Cerca i cromosomi nel database per trovare lo stesso.
    for (Ch1=0;Ch1<ChrCountInHistory && cnt<GeneCount;Ch1++)
    {
      cnt=0;
      //Controlla i geni finché l'indice dei geni è inferiore al numero di geni e finché 
      //... ottenere gli stessi geni.
      for (Ge=1;Ge<=GeneCount;Ge++)
      {
        if (Colony[Ge][position]!=HistoryHromosomes[Ge][Ch1])
          break;
        cnt++;
      }
    }
    //Se ci sono tanti geni identici quanti sono, possiamo prendere 
    //... soluzione pronta dal database
    if (cnt==GeneCount)
    {
      Colony[0][position]=HistoryHromosomes[0][Ch1-1];
    }
    //Se non esiste un cromosoma di questo tipo nel database, calcoleremo FF per esso....
    else
    {
      FitnessFunction();
      //... e se c'è spazio nel database, lo salveremo.
      if (ChrCountInHistory<5)
      {
        for (Ge=0;Ge<=GeneCount;Ge++)
          HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
        ChrCountInHistory++;
      }
    }
  }
  //Se la base è vuota, calcolare FF per il cromosoma e memorizzarlo nella base.
  else
  {
    FitnessFunction();
    for (Ge=0;Ge<=GeneCount;Ge++)
      HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
    ChrCountInHistory++;
  }
}
//------------------------------------------------------------------------------

void FitnessFunction()
{
  Colony[0][position]=20.0;
}