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

[Roman Zamozhnyy]

Заменил строку 175 на

        NormalizeDouble((double)SumOfCurrentEpoch/MathMax(1,(double)resetCounterFF),2),

 Без этого отчет о работе вылетает с ошибкой.

[Andrey Dik]

Rich:

Заменил строку 175 на

 Без этого отчет о работе вылетает с ошибкой.

Да, возникнет ошибка деления на 0, если не было улучшений на протяжении заданного количества эпох начиная с первого запуска цикла ген. операторов.

Проще всего, и правильнее логически, присвоить переменной resetCounterFF сразу при инициализации 1:

int    resetCounterFF   =1;//счетчик сбросов "Эпох без улучшений"

[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 особей.  Может в таком случае быстрее будет посчитать, чем все это проверить (перебрать)?  Не проверяли?