Discussão do artigo "Algoritmos genéticos - é fácil!" - página 9

[Roman Zamozhnyy]

Sugiro que o tamanho da população seja calculado:

  ChromosomeCount=GeneCount*11;                                      /Número de cromossomos na colônia

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

[Andrey Miguzov]

Muito obrigado pelo artigo! Se não fosse por ele, eu nunca teria aprendido o que são métodos genéticos :)

Mas há uma pergunta! Quando verificamos os cromossomos do banco de dados, no caso de uma correspondência, uma unidade será subtraída do índice do cromossomo do banco de dados. Por quê? E se o índice for zero?

/Pesquise os cromossomos no banco de dados para encontrar o mesmo.
    for (Ch1=0;Ch1<ChrCountInHistory && cnt<GeneCount;Ch1++)
    {
      cnt=0;
      /Verificar genes desde que o índice de genes seja menor que o número de genes e desde que os mesmos genes sejam encontrados
      for (Ge=1;Ge<=GeneCount;Ge++)
      {
        if (Colony[Ge][chromos]!=historyHromosomes[Ge][Ch1])
          break;
        cnt++;
      }
    }
    //Se o número de genes idênticos for o mesmo, você poderá obter uma solução pronta no banco de dados
    if (cnt==GeneCount)
      Colony[0][chromos]=historyHromosomes[0][Ch1-1];

Onde estou errando?

[Andrey Dik]

Rich:

Sugiro que o tamanho da população seja calculado:

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

Não vou contestar a competência da fonte citada, mas tenho que discordar.

A viabilidade do uso de AG em problemas de otimização está na redução do número de execuções de FF necessárias para determinar o ótimo em comparação com a pesquisa direta.

Se seguirmos a recomendação

ChromosomeCount=GeneCount*11;  

o problema com 1.000 argumentos exigirá um tamanho de população de 11.000 indivíduos! E isso significa 11.000 execuções de FF em apenas uma época! Você também pode usar a geração aleatória de genes e o resultado não será muito inferior para encontrar o melhor. A fonte fornecida faz uma "aposta" de que, em uma população grande, haverá material genético suficiente para desenvolver ainda mais a população em direção ao aprimoramento a cada época. Estou tentando obter o mesmo resultado, mas jogando probabilidades com operadores genéticos sem o aumento total de execuções de FF.

[Andrey Dik]

MigVRN:

Muito obrigado pelo artigo! Se não fosse por ele, eu nunca teria aprendido o que são métodos genéticos :)

Mas há uma pergunta! Quando verificamos os cromossomos do banco de dados, no caso de uma correspondência, uma unidade será subtraída do índice do cromossomo do banco de dados. Por quê? E se o índice for zero?

Onde estou errando???

  //Se algum cromossomo estiver armazenado no banco de dados
  if (ChrCountInHistory>0)
  {
    /Pesquise os cromossomos no banco de dados para encontrar o mesmo.
    for (Ch1=0;Ch1<ChrCountInHistory && cnt<GeneCount;Ch1++)
    {
      cnt=0;
      /Verificar genes desde que o índice de genes seja menor que o número de genes e desde que 
      //... obter os mesmos genes.
      for (Ge=1;Ge<=GeneCount;Ge++)
      {
        if (Colony[Ge][position]!=HistoryHromosomes[Ge][Ch1])
          break;
        cnt++;
      }
    }
    //Se houver tantos genes idênticos quanto o número de genes, podemos pegar 
    //...solução pronta do banco de dados
    if (cnt==GeneCount)
      Colony[0][position]=HistoryHromosomes[0][Ch1-1];
    //Se não houver tal cromossomo no banco de dados, calcularemos o FF para ele....
    else
    {
      FitnessFunction();
      //... e se houver espaço no banco de dados, nós o salvaremos.
      if (ChrCountInHistory<10000)
      {
        for (Ge=0;Ge<=GeneCount;Ge++)
          HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
        ChrCountInHistory++;
      }
    }
  }
  //Se a base estiver vazia, calcule o FF para o cromossomo e armazene-o na base
  else
  {
    FitnessFunction();
    for (Ge=0;Ge<=GeneCount;Ge++)
      HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
    ChrCountInHistory++;
  }

O banco de dados só é verificado se houver pelo menos um cromossomo no banco de dados. Você não citou a seção inteira do código de pesquisa do banco de dados.

Portanto, o caso em que não há cromossomos na base, mas a ranhura é verificada, é impossível.

[Andrey Miguzov]

joo:

A verificação do banco de dados é realizada somente quando há pelo menos um cromossomo no banco de dados. Você não forneceu a seção inteira do código para a pesquisa por base.

Portanto, o caso em que não há cromossomos no banco de dados, mas a verificação do sulco é realizada, é impossível.

Obrigado por sua resposta tão rápida! Eu não quis dizer exatamente o que você está falando!

1) Suponha que haja de fato um cromossomo no banco de dados (ChrCountInHistory = 1 - ou seja, a dimensão da matriz é igual a um) - então seu índice no banco de dados é zero! (ChrCountInHistory é zero por padrão - o índice de um elemento na matriz é zero).

E subtraímos um desse índice:

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

Além disso, a pesquisa começa em Ch1=0.

2) Comparamos com HistoryHromosomes[Ge][Ch1 ] e atribuímos HistoryHromosomes[0][Ch1-1].

[Andrey Dik]

Você está certo, obrigado.

Essa é a maneira de fazer isso:

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

[Andrey Dik]

joo:

Você está certo, obrigado.

Esse é o caminho a seguir:

Hmm.

Agora"Array out of range" em HistoryHromosomes[0][Ch1], embora tudo pareça estar correto...

[Andrey Miguzov]

joo:

Você está certo, obrigado.

Não tem de quê! O principal é que ele funciona ainda melhor agora do que antes :)

joo:

Hmm.

Agora "Array out of range" em HistoryHromosomes[0][Ch1], embora tudo pareça estar correto...

É difícil dizer o motivo - temos códigos diferentes para analisar. Talvez seja a variável "position" - seu análogo no artigo é "chromos". Dei uma olhada no código do artigo provavelmente 10 vezes - não consegui entender onde está o erro :( Vou verificar mais tarde os exemplos do artigo - talvez algo fique mais claro.

P.S.: justifica-se o uso de um banco de memória se uma variável consistir em ~150 valores. E houver 100.000 indivíduos no histórico. Talvez , nesse caso, seja mais rápido calcular do que verificar (pesquisar) tudo? Você não verificou?

[Andrey Dik]

MigVRN:

P.S.: justifica-se o uso de um banco de memória se uma variável consistir em ~150 valores. E houver 100.000 indivíduos no histórico. Talvez , nesse caso, seja mais rápido contar do que verificar (verificar novamente) tudo? Você não verificou?

Tudo depende do tempo necessário para calcular o FF. Se o FF for apenas uma função matemática, então o banco não é razoável. Mas se o FF usar execuções de histórico (aprendizado de neurônios, etc.) e outras tarefas que exigem muitos recursos, o banco será necessário e poderá reduzir significativamente o tempo de otimização.

Bem, isso também depende da precisão dos genes. Quanto mais "grosseiros" forem os genes, mais repetições ocorrerão e mais razoável será usar um banco de cromossomos.

[Andrey Dik]

MigVRN:
....

:)

Ainda assim, não há erro, você me confundiu muito. Aqui, criei um script de teste, experimente-o e você entenderá tudo.

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

Aqui, embora ele compare o cromossomo com a posição de Ch1, mas no loop superior é atribuído +1, então eu subtraio -1 depois.

Concordo, está um pouco torto, poderia ser feito melhor.

Aqui está um script para verificar isso:

//+------------------------------------------------------------------+
//|Verificar.mq5 |
//|Direitos autorais 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"
//+------------------------------------------------------------------+
//| Função de início do programa 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;//outro gene


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

//------------------------------------------------------------------------------
/Verificação de um cromossomo em relação a um banco de dados de cromossomos.
void CheckHistoryChromosomes()
{
  //----------------------------------------------------------------------------
  int   Ch1=0;  /Índice de cromossomos do banco de dados
  int   Ge =0;  /Índice de genes
  int   cnt=0;  //Contador de genes exclusivos. Se algum gene for diferente 
                //- um cromossomo é reconhecido como único
  //----------------------------------------------------------------------------
  //Se algum cromossomo estiver armazenado no banco de dados
  if (ChrCountInHistory>0)
  {
    /Pesquise os cromossomos no banco de dados para encontrar o mesmo.
    for (Ch1=0;Ch1<ChrCountInHistory && cnt<GeneCount;Ch1++)
    {
      cnt=0;
      /Verificar genes desde que o índice de genes seja menor que o número de genes e desde que 
      //... obter os mesmos genes.
      for (Ge=1;Ge<=GeneCount;Ge++)
      {
        if (Colony[Ge][position]!=HistoryHromosomes[Ge][Ch1])
          break;
        cnt++;
      }
    }
    //Se houver tantos genes idênticos quanto o número de genes, podemos tomar 
    //...solução pronta do banco de dados
    if (cnt==GeneCount)
    {
      Colony[0][position]=HistoryHromosomes[0][Ch1-1];
    }
    //Se não houver tal cromossomo no banco de dados, calcularemos o FF para ele....
    else
    {
      FitnessFunction();
      //... e se houver espaço no banco de dados, nós o salvaremos.
      if (ChrCountInHistory<5)
      {
        for (Ge=0;Ge<=GeneCount;Ge++)
          HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
        ChrCountInHistory++;
      }
    }
  }
  //Se a base estiver vazia, calcule o FF para o cromossomo e armazene-o na base
  else
  {
    FitnessFunction();
    for (Ge=0;Ge<=GeneCount;Ge++)
      HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
    ChrCountInHistory++;
  }
}
//------------------------------------------------------------------------------

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