Diskussion zum Artikel "Genetische Algorithmen - Leicht gemacht!" - Seite 9

[Roman Zamozhnyy]

Ich schlage vor, dass die Bevölkerungsgröße berechnet werden sollte:

  ChromosomeCount=GeneCount*11;                                      //Anzahl der Chromosomen in der Kolonie

Abgerufen von: http: //habrahabr.ru/blogs/algorithm/122222/

[Andrey Miguzov]

Vielen Dank für diesen Artikel! Wenn nicht für sie - ich habe nie gelernt, was genetische Methoden sind :)

Aber es gibt eine Frage! Wenn wir Chromosomen aus der Datenbank überprüfen - im Falle einer Übereinstimmung - wird eine Einheit vom Chromosomenindex aus der Datenbank abgezogen. Und warum? Und was ist, wenn der Index Null ist?

//Suche die Chromosomen in der Datenbank, um das gleiche zu finden.
    for (Ch1=0;Ch1<ChrCountInHistory && cnt<GeneCount;Ch1++)
    {
      cnt=0;
      / /Gene prüfen, solange der Genindex kleiner ist als die Anzahl der Gene und solange die gleichen Gene gefunden werden
      for (Ge=1;Ge<=GeneCount;Ge++)
      {
        if (Colony[Ge][chromos]!=historyHromosomes[Ge][Ch1])
          break;
        cnt++;
      }
    }
    //Wenn die Anzahl der identischen Gene gleich ist, kann man eine fertige Lösung aus der Datenbank nehmen
    if (cnt==GeneCount)
      Colony[0][chromos]=historyHromosomes[0][Ch1-1];

Wo liege ich falsch?

[Andrey Dik]

Rich:

Ich schlage vor, dass die Bevölkerungsgröße berechnet werden sollte:

Abgerufen von: http: //habrahabr.ru/blogs/algorithm/122222/

Ich will die Kompetenz der zitierten Quelle nicht bestreiten, aber ich muss ihr widersprechen.

Die Durchführbarkeit des Einsatzes von GA bei Optimierungsproblemen liegt in der Verringerung der Anzahl von FF-Durchläufen, die zur Bestimmung des Optimums erforderlich sind, im Vergleich zur direkten Suche.

Wenn wir der Empfehlung folgen

ChromosomeCount=GeneCount*11;  

wird das Problem mit 1000 Argumenten eine Populationsgröße von 11000 Individuen erfordern! Und das sind 11000 FF-Läufe in nur 1 Epoche! Man kann genauso gut die zufällige Generierung von Genen verwenden, und das Ergebnis wird beim Finden des Optimums nicht viel schlechter sein. Die angegebene Quelle geht die "Wette" ein, dass in einer großen Population genügend genetisches Material vorhanden ist, um die Population in jeder Epoche in Richtung Verbesserung weiterzuentwickeln. Ich versuche, dasselbe zu erreichen, indem ich mit Wahrscheinlichkeiten mit genetischen Operatoren spiele, ohne die Gesamtzahl der FF-Läufe zu erhöhen.

[Andrey Dik]

MigVRN:

Vielen Dank für diesen Artikel! Wenn nicht für sie - ich habe nie gelernt, was genetische Methoden sind :)

Aber es gibt eine Frage! Wenn wir Chromosomen aus der Datenbank überprüfen - im Falle einer Übereinstimmung - wird eine Einheit vom Chromosomenindex aus der Datenbank abgezogen. Und warum? Und was ist, wenn der Index Null ist?

Wo liege ich falsch?

  //Wenn ein Chromosom in der Datenbank gespeichert ist
  if (ChrCountInHistory>0)
  {
    //Suche die Chromosomen in der Datenbank, um das gleiche zu finden.
    for (Ch1=0;Ch1<ChrCountInHistory && cnt<GeneCount;Ch1++)
    {
      cnt=0;
      //Gene prüfen, solange der Genindex kleiner ist als die Anzahl der Gene und solange 
      //...erhalten die gleichen Gene.
      for (Ge=1;Ge<=GeneCount;Ge++)
      {
        if (Colony[Ge][position]!=HistoryHromosomes[Ge][Ch1])
          break;
        cnt++;
      }
    }
    //Wenn es so viele identische Gene gibt, wie es gibt, können wir die 
    //...fertige Lösung aus der Datenbank
    if (cnt==GeneCount)
      Colony[0][position]=HistoryHromosomes[0][Ch1-1];
    //Wenn es kein solches Chromosom in der Datenbank gibt, berechnen wir FF für es....
    else
    {
      FitnessFunction();
      //... und wenn in der Datenbank noch Platz ist, speichern wir es.
      if (ChrCountInHistory<10000)
      {
        for (Ge=0;Ge<=GeneCount;Ge++)
          HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
        ChrCountInHistory++;
      }
    }
  }
  //Wenn die Basis leer ist, wird FF für das Chromosom berechnet und in der Basis gespeichert
  else
  {
    FitnessFunction();
    for (Ge=0;Ge<=GeneCount;Ge++)
      HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
    ChrCountInHistory++;
  }

Die Datenbank wird nur überprüft, wenn mindestens ein Chromosom in der Datenbank vorhanden ist. Sie haben nicht den gesamten Abschnitt des Codes für die Datenbanksuche zitiert.

Daher ist der Fall, dass keine Chromosomen in der Datenbank vorhanden sind, die Nut aber geprüft wird, unmöglich.

[Andrey Miguzov]

joo:

Die Datenbankprüfung wird nur durchgeführt, wenn mindestens ein Chromosom in der Datenbank vorhanden ist. Sie haben nicht den gesamten Abschnitt des Codes für die Suche nach Basen angegeben.

Daher ist der Fall, dass keine Chromosomen in der Datenbank vorhanden sind, aber die Rillenprüfung durchgeführt wird, unmöglich.

Vielen Dank für die schnelle Antwort! Ich habe nicht genau das gemeint, was Sie meinen!

1) Angenommen, es gibt tatsächlich ein Chromosom in der Datenbank (ChrCountInHistory = 1 - d.h. die Array-Dimension ist gleich eins) - dann ist sein Index in der Datenbank Null! (ChrCountInHistory ist standardmäßig Null - der Index eines Elements im Array ist Null).

Und wir subtrahieren eins von diesem Index:

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

Außerdem beginnt die Suche bei Ch1=0.

2) Wir vergleichen mit HistoryHromosomes[Ge][Ch1 ], und weisen HistoryHromosomes[0][Ch1-1] zu.

[Andrey Dik]

Sie haben Recht, vielen Dank.

Das ist der richtige Weg:

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

[Andrey Dik]

joo:

Sie haben Recht, vielen Dank.

Das ist der richtige Weg:

Hmm.

Jetzt"Array out of range" auf HistoryHromosomes[0][Ch1], obwohl alles korrekt zu sein scheint...

[Andrey Miguzov]

joo:

Sie haben Recht, vielen Dank.

Gern geschehen! Die Hauptsache ist, dass es jetzt noch besser funktioniert als vorher :)

joo:

Hmm.

Jetzt "Array out of range" bei HistoryHromosomes[0][Ch1], obwohl alles korrekt zu sein scheint...

Es ist schwer zu sagen, warum - wir haben unterschiedlichen Code zu analysieren. Vielleicht liegt es an der "position"-Variablen - ihr Analogon im Artikel ist "chromos". Ich habe mir den Code im Artikel bestimmt 10 Mal angesehen - ich konnte nicht verstehen, wo der Fehler liegt :( Ich werde mir später die Beispiele im Artikel ansehen - vielleicht wird dann etwas klarer.

P.S.: Es ist gerechtfertigt, eine Speicherbank zu verwenden, wenn eine Variable aus ~150 Werten besteht. Und es gibt 100000 Individuen in der Historie. Vielleicht wäre es in einem solchen Fall schneller zu berechnen, als alles zu überprüfen (zu suchen)? Sie haben es nicht überprüft?

[Andrey Dik]

MigVRN:

P.S.: Es ist gerechtfertigt, eine Speicherbank zu verwenden, wenn eine Variable aus ~150 Werten besteht. Und es gibt 100000 Individuen in der Historie. Vielleicht wäre es in einem solchen Fall schneller, zu zählen, als alles zu überprüfen (erneut zu überprüfen)? Sie haben es nicht überprüft?

Es hängt alles von der Zeit ab, die für die Berechnung der FF benötigt wird. Wenn die FF nur eine mathematische Funktion ist, dann ist die Bank nicht sinnvoll. Aber wenn die FF historische Läufe (Neuronenlernen usw.) und andere ressourcenintensive Aufgaben verwendet, dann ist die Bank notwendig und kann die Optimierungszeit erheblich reduzieren.

Nun, das hängt auch von der Genauigkeit der Gene ab. Je "gröber" die Gene sind, desto häufiger treten Wiederholungen auf, und desto sinnvoller ist die Verwendung einer Chromosomenbank.

[Andrey Dik]

MigVRN:
....

:)

Trotzdem, es gibt keinen Fehler, du hast mich sehr verwirrt. Hier habe ich ein Testskript gemacht, probier es aus, dann verstehst du alles.

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

Hier vergleicht es zwar das Chromosom mit der Position von Ch1, aber in der oberen Schleife wird ihm +1 zugewiesen, also ziehe ich danach -1 ab.

Ich stimme zu, es ist ein bisschen schief, das könnte man besser machen.

Hier ist ein Skript, um es zu überprüfen:

//+------------------------------------------------------------------+
//|Prüfen.mq5 |
//|Copyright 2011, JQS alias 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"
//+------------------------------------------------------------------+
//| Skript-Programmstartfunktion|
//+------------------------------------------------------------------+

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;//ein anderes Gen


  HistoryHromosomes[0][1]=7.0;
  //-------------------------
  HistoryHromosomes[1][1]=7.0;
  HistoryHromosomes[2][1]=8.0;
  HistoryHromosomes[3][1]=6.0;//ein anderes Gen
  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]);
}
//+------------------------------------------------------------------+

//------------------------------------------------------------------------------
//Abgleich eines Chromosoms mit einer Chromosomendatenbank.
void CheckHistoryChromosomes()
{
  //----------------------------------------------------------------------------
  int   Ch1=0;  //Chromosomenindex aus der Datenbank
  int   Ge =0;  //Gen-Index
  int   cnt=0;  //Zähler der eindeutigen Gene. Wenn ein Gen abweicht 
                //- ein Chromosom wird als einzigartig erkannt
  //----------------------------------------------------------------------------
  //Wenn ein Chromosom in der Datenbank gespeichert ist
  if (ChrCountInHistory>0)
  {
    //Suche die Chromosomen in der Datenbank, um das gleiche zu finden.
    for (Ch1=0;Ch1<ChrCountInHistory && cnt<GeneCount;Ch1++)
    {
      cnt=0;
      //Gene prüfen, solange der Genindex kleiner ist als die Anzahl der Gene und solange 
      //...erhalten die gleichen Gene.
      for (Ge=1;Ge<=GeneCount;Ge++)
      {
        if (Colony[Ge][position]!=HistoryHromosomes[Ge][Ch1])
          break;
        cnt++;
      }
    }
    //Wenn es so viele identische Gene gibt, wie es gibt, können wir die 
    //...fertige Lösung aus der Datenbank
    if (cnt==GeneCount)
    {
      Colony[0][position]=HistoryHromosomes[0][Ch1-1];
    }
    //Wenn es kein solches Chromosom in der Datenbank gibt, berechnen wir FF für es....
    else
    {
      FitnessFunction();
      //... und wenn in der Datenbank noch Platz ist, speichern wir es.
      if (ChrCountInHistory<5)
      {
        for (Ge=0;Ge<=GeneCount;Ge++)
          HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
        ChrCountInHistory++;
      }
    }
  }
  //Wenn die Basis leer ist, wird FF für das Chromosom berechnet und in der Basis gespeichert
  else
  {
    FitnessFunction();
    for (Ge=0;Ge<=GeneCount;Ge++)
      HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
    ChrCountInHistory++;
  }
}
//------------------------------------------------------------------------------

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