Discussion of article "Genetic Algorithms - It's Easy!" - page 9

[Roman Zamozhnyy]

I suggest that population size should be calculated:

  ChromosomeCount=GeneCount*11;                                      //Number of chromosomes in the colony

Retrieved from: http: //habrahabr.ru/blogs/algorithm/122222/

[Andrey Miguzov]

Thank you so much for the article! If not for it - I never learnt what genetic methods are :)

But there is one question! When we check chromosomes from the database - in case of a match - one unit will be subtracted from the chromosome index from the database. Why? And what if the index is zero?

//Search the chromosomes in the database to find the same one.
    for (Ch1=0;Ch1<ChrCountInHistory && cnt<GeneCount;Ch1++)
    {
      cnt=0;
      //Check genes as long as the gene index is less than the number of genes and as long as the same genes are found
      for (Ge=1;Ge<=GeneCount;Ge++)
      {
        if (Colony[Ge][chromos]!=historyHromosomes[Ge][Ch1])
          break;
        cnt++;
      }
    }
    //If the number of identical genes is the same, you can take a ready-made solution from the database
    if (cnt==GeneCount)
      Colony[0][chromos]=historyHromosomes[0][Ch1-1];

Where am I wrong?

[Andrey Dik]

Rich:

I suggest that population size should be calculated:

Retrieved from: http: //habrahabr.ru/blogs/algorithm/122222/

I will not dispute the competence of the cited source, but I have to disagree.

The feasibility of using GA in optimisation problems lies in reducing the number of FF runs required to determine the optimum compared to direct search.

If we follow the recommendation

ChromosomeCount=GeneCount*11;  

the problem with 1000 arguments will require a population size of 11000 individuals! And that's 11000 FF runs on only 1 epoch! You can just as well use random gene generation and the result will not be much inferior in finding the optimum. The given source makes a "bet" that in a large population there will be enough genetic material to further develop the population towards improvement at each epoch. I am trying to achieve the same thing, but by playing probabilities with genetic operators without total increase of FF runs.

[Andrey Dik]

MigVRN:

Thank you so much for the article! If not for it - I never learnt what genetic methods are :)

But there is one question! When we check chromosomes from the database - in case of a match - one unit will be subtracted from the chromosome index from the database. Why? And what if the index is zero?

Where am I wrong???

  //If any chromosome is stored in the database
  if (ChrCountInHistory>0)
  {
    //Search the chromosomes in the database to find the same one.
    for (Ch1=0;Ch1<ChrCountInHistory && cnt<GeneCount;Ch1++)
    {
      cnt=0;
      //Check genes as long as the gene index is less than the number of genes and as long as 
      //...get the same genes.
      for (Ge=1;Ge<=GeneCount;Ge++)
      {
        if (Colony[Ge][position]!=HistoryHromosomes[Ge][Ch1])
          break;
        cnt++;
      }
    }
    //If there are as many identical genes as there are, we can take 
    //...ready-made solution from the database
    if (cnt==GeneCount)
      Colony[0][position]=HistoryHromosomes[0][Ch1-1];
    //If there is no such chromosome in the database, we will calculate FF for it....
    else
    {
      FitnessFunction();
      //... and if there's room in the database, we'll save it.
      if (ChrCountInHistory<10000)
      {
        for (Ge=0;Ge<=GeneCount;Ge++)
          HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
        ChrCountInHistory++;
      }
    }
  }
  //If the base is empty, calculate FF for the chromosome and store it in the base
  else
  {
    FitnessFunction();
    for (Ge=0;Ge<=GeneCount;Ge++)
      HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
    ChrCountInHistory++;
  }

The database is only checked if there is at least one chromosome in the database. You didn't cite the entire section of the database search code.

Therefore, the case when there are no chromosomes in the database but the groove is checked is impossible.

[Andrey Miguzov]

joo:

The database check is performed only when there is at least one chromosome in the database. You have not given the whole section of the code for searching by base.

Therefore, the case when there are no chromosomes in the database, but the groove check is performed is impossible.

Thank you for such a prompt reply! I didn't mean exactly what you are talking about!

1) Suppose that there is indeed one chromosome in the database (ChrCountInHistory = 1 - i.e. the array dimension is equal to one) - then its index in the database is zero! (ChrCountInHistory is zero by default - the index of an element in the array is zero).

And we subtract one from this index:

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

besides, the search starts from Ch1=0.

2) We compare with HistoryHromosomes[Ge][Ch1 ], and assign HistoryHromosomes[0][Ch1-1].

[Andrey Dik]

You're right, thank you.

That's the way to do it:

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

[Andrey Dik]

joo:

You're right, thank you.

That's the way to go:

Hmm.

Now"Array out of range" on HistoryHromosomes[0][Ch1], although everything seems to be correct...

[Andrey Miguzov]

joo:

You're right, thank you.

You're welcome! The main thing is that it works even better now than before :)

joo:

Hmm.

Now "Array out of range" on HistoryHromosomes[0][Ch1], though everything seems to be correct...

It's hard to say why - we have different code to analyse. Maybe it's the "position" variable - its analogue in the article is "chromos". I've looked through the code in the article probably 10 times - I couldn't understand where the bug is :( I'll check later on the examples in the article - maybe something will become clearer.

P.S. : it is justified to use a memory bank if a variable consists of ~150 values. And there are 100000 individuals in the history. Maybe in such a case it would be faster to calculate than to check (search) it all? You haven't checked it?

[Andrey Dik]

MigVRN:

P.S. : it is justified to use a memory bank if a variable consists of ~150 values. And there are 100000 individuals in the history. Maybe in such a case it would be faster to count than to check (re-check) it all? You haven't checked it?

It all depends on the time required to calculate the FF. If the FF is just some mathematical function, then the bank is not reasonable. But if the FF uses history runs (neuron learning, etc.) and other resource-intensive tasks, then the bank is necessary and can significantly reduce the optimisation time.

Well, it also depends on the accuracy of genes. The "coarser" the genes are, the more often repetitions will occur, and the more reasonable it is to use a chromosome bank.

[Andrey Dik]

MigVRN:
....

:)

Still, there is no error, you confused me a lot. Here, I've made a test script, try it out, you'll understand everything.

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

Here, although it compares the chromosome with the position of Ch1, but on the upper loop it is assigned +1, so I subtract -1 afterwards.

I agree, it's a bit crooked, it could be done better.

Here is a script to check it:

//+------------------------------------------------------------------+
//|Check.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"
//+------------------------------------------------------------------+
//| Script programme start function|
//+------------------------------------------------------------------+

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;//another gene


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

//------------------------------------------------------------------------------
//Checking a chromosome against a chromosome database.
void CheckHistoryChromosomes()
{
  //----------------------------------------------------------------------------
  int   Ch1=0;  //Chromosome index from the database
  int   Ge =0;  //Gene Index
  int   cnt=0;  //Counter of unique genes. If any gene differs 
                //- a chromosome is recognised as unique
  //----------------------------------------------------------------------------
  //If any chromosome is stored in the database
  if (ChrCountInHistory>0)
  {
    //Search the chromosomes in the database to find the same one.
    for (Ch1=0;Ch1<ChrCountInHistory && cnt<GeneCount;Ch1++)
    {
      cnt=0;
      //Check genes as long as the gene index is less than the number of genes and as long as 
      //...get the same genes.
      for (Ge=1;Ge<=GeneCount;Ge++)
      {
        if (Colony[Ge][position]!=HistoryHromosomes[Ge][Ch1])
          break;
        cnt++;
      }
    }
    //If there are as many identical genes as there are, we can take 
    //...ready-made solution from the database
    if (cnt==GeneCount)
    {
      Colony[0][position]=HistoryHromosomes[0][Ch1-1];
    }
    //If there is no such chromosome in the database, we will calculate FF for it....
    else
    {
      FitnessFunction();
      //... and if there's room in the database, we'll save it.
      if (ChrCountInHistory<5)
      {
        for (Ge=0;Ge<=GeneCount;Ge++)
          HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
        ChrCountInHistory++;
      }
    }
  }
  //If the base is empty, calculate FF for the chromosome and store it in the base
  else
  {
    FitnessFunction();
    for (Ge=0;Ge<=GeneCount;Ge++)
      HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
    ChrCountInHistory++;
  }
}
//------------------------------------------------------------------------------

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