Discussion de l'article "Algorithmes Génétiques - C'est Facile !" - page 9

[Roman Zamozhnyy]

Je suggère que la taille de la population soit calculée :

  ChromosomeCount=GeneCount*11;                                      //Nombre de chromosomes dans la colonie

Récupérée de : http://habrahabr.ru/blogs/algorithm/122222/

[Andrey Miguzov]

Merci beaucoup pour cet article ! Sans lui, je n'aurais jamais appris ce que sont les méthodes génétiques :)

Mais j'ai une question ! Lorsque nous vérifions les chromosomes de la base de données - en cas de correspondance - une unité sera soustraite de l'index du chromosome de la base de données. Pourquoi ? Et que se passe-t-il si l'index est nul ?

/Recherche des chromosomes dans la base de données pour trouver le même.
    for (Ch1=0;Ch1<ChrCountInHistory && cnt<GeneCount;Ch1++)
    {
      cnt=0;
      /Vérifier les gènes tant que l'index des gènes est inférieur au nombre de gènes et tant que les mêmes gènes sont trouvés
      for (Ge=1;Ge<=GeneCount;Ge++)
      {
        if (Colony[Ge][chromos]!=historyHromosomes[Ge][Ch1])
          break;
        cnt++;
      }
    }
    //Si le nombre de gènes identiques est le même, vous pouvez prendre une solution prête à l'emploi dans la base de données.
    if (cnt==GeneCount)
      Colony[0][chromos]=historyHromosomes[0][Ch1-1];

Où est-ce que je me trompe ?

[Andrey Dik]

Rich:

Je suggère que la taille de la population soit calculée :

Extrait de : http://habrahabr.ru/blogs/algorithm/122222/

Je ne contesterai pas la compétence de la source citée, mais je ne suis pas d'accord.

La faisabilité de l'utilisation de l'AG dans les problèmes d'optimisation réside dans la réduction du nombre d'exécutions FF nécessaires pour déterminer l'optimum par rapport à la recherche directe.

Si nous suivons la recommandation

ChromosomeCount=GeneCount*11;  

le problème avec 1000 arguments nécessitera une population de 11000 individus ! Et il s'agit de 11 000 exécutions de FF à une seule époque ! Vous pouvez tout aussi bien utiliser la génération aléatoire de gènes et le résultat ne sera pas beaucoup moins bon pour trouver l'optimum. La source donnée fait le "pari" que dans une grande population, il y aura suffisamment de matériel génétique pour faire évoluer la population vers l'amélioration à chaque époque. J'essaie d'obtenir le même résultat, mais en jouant sur les probabilités avec les opérateurs génétiques sans augmenter le nombre total d'exécutions FF.

[Andrey Dik]

MigVRN:

Merci beaucoup pour cet article ! Sans lui, je n'aurais jamais appris ce que sont les méthodes génétiques :)

Mais j'ai une question ! Lorsque nous vérifions les chromosomes de la base de données - en cas de correspondance - une unité sera soustraite de l'index du chromosome de la base de données. Pourquoi ? Et que se passe-t-il si l'index est nul ?

Où est-ce que je me trompe ?

  //Si un chromosome est stocké dans la base de données
  if (ChrCountInHistory>0)
  {
    /Recherche des chromosomes dans la base de données pour trouver le même.
    for (Ch1=0;Ch1<ChrCountInHistory && cnt<GeneCount;Ch1++)
    {
      cnt=0;
      /Vérifier les gènes tant que l'index des gènes est inférieur au nombre de gènes et tant que 
      //... obtiennent les mêmes gènes.
      for (Ge=1;Ge<=GeneCount;Ge++)
      {
        if (Colony[Ge][position]!=HistoryHromosomes[Ge][Ch1])
          break;
        cnt++;
      }
    }
    //S'il y a autant de gènes identiques qu'il y a de gènes, on peut prendre 
    //...solution toute faite à partir de la base de données
    if (cnt==GeneCount)
      Colony[0][position]=HistoryHromosomes[0][Ch1-1];
    //S'il n'y a pas de chromosome de ce type dans la base de données, nous calculerons FF pour lui....
    else
    {
      FitnessFunction();
      //... et s'il y a de la place dans la base de données, nous l'enregistrerons.
      if (ChrCountInHistory<10000)
      {
        for (Ge=0;Ge<=GeneCount;Ge++)
          HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
        ChrCountInHistory++;
      }
    }
  }
  //Si la base est vide, calculer FF pour le chromosome et le stocker dans la base.
  else
  {
    FitnessFunction();
    for (Ge=0;Ge<=GeneCount;Ge++)
      HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
    ChrCountInHistory++;
  }

La base de données n'est vérifiée que s'il y a au moins un chromosome dans la base de données. Vous n'avez pas cité toute la section du code de recherche de la base de données.

Par conséquent, le cas où il n'y a pas de chromosomes dans la base de données mais où le sillon est vérifié est impossible.

[Andrey Miguzov]

joo:

La vérification de la base de données n'est effectuée que lorsqu'il y a au moins un chromosome dans la base de données. Vous n'avez pas indiqué la section complète du code pour la recherche par base.

Par conséquent, le cas où il n'y a pas de chromosomes dans la base de données, mais où la vérification du sillon est effectuée est impossible.

Merci pour cette réponse si rapide ! Je ne voulais pas dire exactement ce que vous voulez dire !

1) Supposons qu'il y ait effectivement un chromosome dans la base de données (ChrCountInHistory = 1 - c'est-à-dire que la dimension du tableau est égale à un) - alors son index dans la base de données est zéro ! (ChrCountInHistory est égal à zéro par défaut - l'indice d'un élément du tableau est égal à zéro).

Et nous soustrayons un à cet indice :

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

en outre, la recherche commence à partir de Ch1=0.

2) On compare avec HistoryHromosomes[Ge][Ch1 ], et on affecte HistoryHromosomes[0][Ch1-1].

[Andrey Dik]

Vous avez raison, merci.

C'est ainsi qu'il faut procéder :

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

[Andrey Dik]

joo:

Vous avez raison, merci.

C'est la voie à suivre :

Hmm.

Maintenant"Array out of range" sur HistoryHromosomes[0][Ch1], bien que tout semble correct...

[Andrey Miguzov]

joo:

Vous avez raison, merci.

Il n'y a pas de quoi ! L'essentiel est que cela fonctionne encore mieux maintenant qu'avant :)

joo:

Hmm.

Maintenant "Array out of range" sur HistoryHromosomes[0][Ch1], bien que tout semble correct...

Il est difficile de dire pourquoi - nous avons des codes différents à analyser. Il s'agit peut-être de la variable "position" - son analogue dans l'article est "chromos". J'ai regardé le code de l'article probablement 10 fois - je n'ai pas pu comprendre où se trouve le bug :( Je vérifierai plus tard les exemples de l'article - peut-être que quelque chose deviendra plus clair.

P.S. : il est justifié d'utiliser une banque de mémoire si une variable est composée de ~150 valeurs. Et qu'il y a 100000 individus dans l'historique. Peut-être que dans ce cas, il serait plus rapide de calculer que de tout vérifier (rechercher) ? Vous n'avez pas vérifié?

[Andrey Dik]

MigVRN:

P.S. : il est justifié d'utiliser une banque de mémoire si une variable comporte ~150 valeurs. Et qu'il y a 100000 individus dans l'historique. Peut-être que dans ce cas, il serait plus rapide de compter que de tout vérifier (re-vérifier) ? Vous n'avez pas vérifié?

Tout dépend du temps nécessaire pour calculer le FF. Si le FF n'est qu'une fonction mathématique, la banque n'est pas raisonnable. Mais si le FF utilise des historiques (apprentissage par neurones, etc.) et d'autres tâches à forte intensité de ressources, alors la banque est nécessaire et peut réduire de manière significative le temps d'optimisation.

Cela dépend également de la précision des gènes. Plus les gènes sont "grossiers", plus les répétitions sont fréquentes, et plus il est raisonnable d'utiliser une banque de chromosomes.

[Andrey Dik]

MigVRN:
....

:)

Pourtant, il n'y a pas d'erreur, vous m'avez beaucoup embrouillé. Ici, j'ai fait un script de test, essayez-le, il deviendra plus clair.

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

Ici, bien que le chromosome soit comparé à la position de Ch1, mais sur la boucle supérieure il est assigné +1, donc je soustrais -1 après.

Je suis d'accord, c'est un peu tordu, ça pourrait être mieux fait.

Voici un script pour le vérifier :

//+------------------------------------------------------------------+
//|Vérifier.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"
//+------------------------------------------------------------------+
//| Fonction de démarrage du programme de 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 autre gène


  HistoryHromosomes[0][1]=7.0;
  //-------------------------
  HistoryHromosomes[1][1]=7.0;
  HistoryHromosomes[2][1]=8.0;
  HistoryHromosomes[3][1]=6.0;//un autre gène
  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]);
}
//+------------------------------------------------------------------+

//------------------------------------------------------------------------------
/Vérification d'un chromosome par rapport à une base de données de chromosomes.
void CheckHistoryChromosomes()
{
  //----------------------------------------------------------------------------
  int   Ch1=0;  /Index des chromosomes de la base de données
  int   Ge =0;  //Index des gènes
  int   cnt=0;  //Compteur de gènes uniques. Si un gène est différent 
                //- un chromosome est reconnu comme unique
  //----------------------------------------------------------------------------
  //Si un chromosome est stocké dans la base de données
  if (ChrCountInHistory>0)
  {
    /Recherche des chromosomes dans la base de données pour trouver le même.
    for (Ch1=0;Ch1<ChrCountInHistory && cnt<GeneCount;Ch1++)
    {
      cnt=0;
      /Vérifier les gènes tant que l'index des gènes est inférieur au nombre de gènes et tant que 
      //... obtiennent les mêmes gènes.
      for (Ge=1;Ge<=GeneCount;Ge++)
      {
        if (Colony[Ge][position]!=HistoryHromosomes[Ge][Ch1])
          break;
        cnt++;
      }
    }
    //S'il y a autant de gènes identiques qu'il y a de gènes, on peut prendre 
    //...solution toute faite à partir de la base de données
    if (cnt==GeneCount)
    {
      Colony[0][position]=HistoryHromosomes[0][Ch1-1];
    }
    //S'il n'y a pas de chromosome de ce type dans la base de données, nous calculerons FF pour lui....
    else
    {
      FitnessFunction();
      //... et s'il y a de la place dans la base de données, nous l'enregistrerons.
      if (ChrCountInHistory<5)
      {
        for (Ge=0;Ge<=GeneCount;Ge++)
          HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
        ChrCountInHistory++;
      }
    }
  }
  //Si la base est vide, calculer FF pour le chromosome et le stocker dans la base.
  else
  {
    FitnessFunction();
    for (Ge=0;Ge<=GeneCount;Ge++)
      HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
    ChrCountInHistory++;
  }
}
//------------------------------------------------------------------------------

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