Обсуждение статьи "Генетические алгоритмы - это просто!" - страница 9

[Roman Zamozhnyy]

Предлагаю размер популяции вычислять:

  ChromosomeCount=GeneCount*11;                                      //Кол-во хромосом в колонии

Взято: http://habrahabr.ru/blogs/algorithm/122222/

[Andrey Miguzov]

Огромное спасибо за статью! Если бы не она - то я никогда не узнал что такое генетические методы :)

Но есть один вопрос! Когда делаем проверку хромосом по базе – в случае совпадения – от индекса хромосомы из базы отнимется единица. Зачем? А что если индекс равен нулю? 

//Переберем хромосомы в базе, чтобы найти такую же
    for (Ch1=0;Ch1<ChrCountInHistory && cnt<GeneCount;Ch1++)
    {
      cnt=0;
      //Сверяем гены, пока индекс гена меньше кол-ва генов и пока попадаются одинаковые гены
      for (Ge=1;Ge<=GeneCount;Ge++)
      {
        if (Colony[Ge][chromos]!=historyHromosomes[Ge][Ch1])
          break;
        cnt++;
      }
    }
    //Если набралось одинаковых генов столько же, можно взять готовое решение из базы
    if (cnt==GeneCount)
      Colony[0][chromos]=historyHromosomes[0][Ch1-1];

Где я ошибаюсь??? 

[Andrey Dik]

Rich:

Предлагаю размер популяции вычислять:

Взято: http://habrahabr.ru/blogs/algorithm/122222/

Не буду оспаривать компетентность приведённого источника, однако вынужден не согласится.

Целесообразность применения ГА в задачах оптимизации заключена в снижении необходимого количества запусков ФФ для определения оптимума в сравнении с прямым перебором.

Если следовать рекомендации 

ChromosomeCount=GeneCount*11;  

то для задачи с 1000 аргументами потребуется размер популяции в 11000 особей! А это 11000 запусков ФФ только на 1 эпохе! С таким же успехом можно использовать случайное генерирование генов и результат не намного уступит в нахождении оптимума. Приведенный источник делает "ставку" на то, что в большой популяции будет достаточно генетического материала для дальнейшего развития популяции в сторону улучшения на каждой эпохе. Я же стараюсь добиться того же самого, но за счет игры вероятностями генетическими операторами без тотального увеличения запусков ФФ.

[Andrey Dik]

MigVRN:

Огромное спасибо за статью! Если бы не она - то я никогда не узнал что такое генетические методы :)

Но есть один вопрос! Когда делаем проверку хромосом по базе – в случае совпадения – от индекса хромосомы из базы отнимется единица. Зачем? А что если индекс равен нулю? 

Где я ошибаюсь??? 

  //Если в базе хранится хоть одна хромосома
  if (ChrCountInHistory>0)
  {
    //Переберем хромосомы в базе, чтобы найти такую же
    for (Ch1=0;Ch1<ChrCountInHistory && cnt<GeneCount;Ch1++)
    {
      cnt=0;
      //Сверяем гены, пока индекс гена меньше кол-ва генов и пока 
      //...попадаются одинаковые гены
      for (Ge=1;Ge<=GeneCount;Ge++)
      {
        if (Colony[Ge][position]!=HistoryHromosomes[Ge][Ch1])
          break;
        cnt++;
      }
    }
    //Если набралось одинаковых генов столько же, можно взять 
    //...готовое решение из базы
    if (cnt==GeneCount)
      Colony[0][position]=HistoryHromosomes[0][Ch1-1];
    //Если нет такой же хромосомы в базе, то рассчитаем для неё FF...
    else
    {
      FitnessFunction();
      //.. и если есть место в базе сохраним
      if (ChrCountInHistory<10000)
      {
        for (Ge=0;Ge<=GeneCount;Ge++)
          HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
        ChrCountInHistory++;
      }
    }
  }
  //Если база пустая, рассчитаем для хромосомы FF и сохраним её в базе
  else
  {
    FitnessFunction();
    for (Ge=0;Ge<=GeneCount;Ge++)
      HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
    ChrCountInHistory++;
  }

Проверка по базе осуществляется только в случае, когда в базе есть хоть одна хромосома. Вы привели не весь участок кода поиска по базе.

Поэтому случай, когда  в базе нет хромосом, но проверка по пазе осуществляется - невозможен.

[Andrey Miguzov]

joo:

Проверка по базе осуществляется только в случае, когда в базе есть хоть одна хромосома. Вы привели не весь участок кода поиска по базе.

Поэтому случай, когда  в базе нет хромосом, но проверка по пазе осуществляется - невозможен.

Спасибо за такой оперативный ответ! Я имел ввиду не совсем то о чем вы говорите!

1) Предположим, что в базе действительно есть одна хромосома (ChrCountInHistory = 1 - т.е. размерность массива равна единице) - тогда её индекс в базе равен нулю! (ChrCountInHistory по умолчанию равен нулю - индекс элемента в массиве равен нулю).

А мы от этого индекса отнимаем единицу:

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

 к тому же перебор начинается с Ch1=0

 2) Мы сравниваем с HistoryHromosomes[Ge][Ch1], а присваиваем HistoryHromosomes[0][Ch1-1]

[Andrey Dik]

Вы правы, спасибо.

Нужно так:

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

[Andrey Dik]

joo:

Вы правы, спасибо.

Нужно так:

Хмм..

Теперь "Array out of range" на HistoryHromosomes[0][Ch1], хотя вроде бы всё правильно...

[Andrey Miguzov]

joo:

Вы правы, спасибо.

 Не за что! Главное чтобы заработало теперь ещё лучше чем раньше :)

 joo:  

 Хмм.. 

Теперь "Array out of range" на HistoryHromosomes[0][Ch1], хотя вроде бы всё правильно...

Трудно сказать почему - у нас разный для анализа код. Может быть дело в переменной "position" - в статье её аналог это "chromos". Код который в статье проглядел наверное раз 10 - так и не смог понять где косяк :(  Позже проверю на тех примерах, которые в статье - может что-то проясниться.

P.S. : а оправдывает себя использования банка памяти, если переменная состоит из ~150 значений. А в истории 100000 особей.  Может в таком случае быстрее будет посчитать, чем все это проверить (перебрать)?  Не проверяли?

[Andrey Dik]

MigVRN:

P.S. : а оправдывает себя использования банка памяти, если переменная состоит из ~150 значений. А в истории 100000 особей.  Может в таком случае быстрее будет посчитать, чем все это проверить (перебрать)?  Не проверяли?

Всё зависит от  времени необходимого для вычисления ФФ. Если ФФ просто какая то математическая функция - то банк не целесообразен. Но если же в ФФ используются прогоны по истории (обучение нейронки и др.) и другие ресурсопрожорливые задачи, то банк необходим и способен существенно снизить время оптимизации.

Ну и от точности генов зависит. Чем "грубее" гены, тем чаще будут попадаться повторы, и тем целесообразнее использование банка хромосом.

[Andrey Dik]

MigVRN:
....

:)

Всё же, ошибки нет, Вы меня здорово сбили с толку. Вот, накидал скрипт проверочный, побалуйтесь с ним, станет всё понятно.

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

здесь хоть и сравнивается хромосома с положением Ch1, но на верхнем цикле присваиваться +1, поэтому и вычитаю потом -1.

Согласен, кривовато, можно и красивше заделать.

Вот, собственно, скриптик для проверки:

//+------------------------------------------------------------------+
//|                                                         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 program 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;//другой ген


  HistoryHromosomes[0][1]=7.0;
  //-------------------------
  HistoryHromosomes[1][1]=7.0;
  HistoryHromosomes[2][1]=8.0;
  HistoryHromosomes[3][1]=6.0;//другой ген
  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]);
}
//+------------------------------------------------------------------+

//——————————————————————————————————————————————————————————————————————————————
//Проверка хромосомы по базе хромосом.
void CheckHistoryChromosomes()
{
  //----------------------------------------------------------------------------
  int   Ch1=0;  //Индекс хромосомы из базы
  int   Ge =0;  //Индекс гена
  int   cnt=0;  //Счетчик уникальных генов. Если хоть один ген отличается 
                //- хромосома признается уникальной
  //----------------------------------------------------------------------------
  //Если в базе хранится хоть одна хромосома
  if (ChrCountInHistory>0)
  {
    //Переберем хромосомы в базе, чтобы найти такую же
    for (Ch1=0;Ch1<ChrCountInHistory && cnt<GeneCount;Ch1++)
    {
      cnt=0;
      //Сверяем гены, пока индекс гена меньше кол-ва генов и пока 
      //...попадаются одинаковые гены
      for (Ge=1;Ge<=GeneCount;Ge++)
      {
        if (Colony[Ge][position]!=HistoryHromosomes[Ge][Ch1])
          break;
        cnt++;
      }
    }
    //Если набралось одинаковых генов столько же, можно взять 
    //...готовое решение из базы
    if (cnt==GeneCount)
    {
      Colony[0][position]=HistoryHromosomes[0][Ch1-1];
    }
    //Если нет такой же хромосомы в базе, то рассчитаем для неё FF...
    else
    {
      FitnessFunction();
      //.. и если есть место в базе сохраним
      if (ChrCountInHistory<5)
      {
        for (Ge=0;Ge<=GeneCount;Ge++)
          HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
        ChrCountInHistory++;
      }
    }
  }
  //Если база пустая, рассчитаем для хромосомы FF и сохраним её в базе
  else
  {
    FitnessFunction();
    for (Ge=0;Ge<=GeneCount;Ge++)
      HistoryHromosomes[Ge][ChrCountInHistory]=Colony[Ge][position];
    ChrCountInHistory++;
  }
}
//——————————————————————————————————————————————————————————————————————————————

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