Линейное масштабирование соответствия в Генетическом алгоритме дает отрицательные значения соответствия - PullRequest
Новая
       32

Линейное масштабирование соответствия в Генетическом алгоритме дает отрицательные значения соответствия

1 голос
/ 12 июля 2011

У меня GA с функцией фитнеса, которая может оценивать как отрицательные, так и положительные значения.Ради этого вопроса давайте предположим, что функция 

u = 5 - (x^2 + y^2)

где 

x in [-5.12 .. 5.12]
y in [-5.12 .. 5.12]

Example fitness function

Теперь в selection phase ГА я использую простое колесо рулетки .Поскольку для использования simple roulette wheel моя функция пригодности должна быть положительной для конкретных случаев в популяции, я начал искать решения для масштабирования.Наиболее естественным кажется linear fitness scaling.Это должно быть довольно просто, например, посмотрите на эту реализацию .Тем не менее, я получаю отрицательные значения даже после линейного масштабирования .

Например, для вышеупомянутой функции и этих значений пригодности: 

-9.734897  -7.479017 -22.834280  -9.868979 -13.180669   4.898595

после линейного масштабирования я получаю эти значения 

-9.6766040 -11.1755111  -0.9727897  -9.5875139  -7.3870793 -19.3997490

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

Я, должно быть, делаю здесь что-то принципиально неправильное.Как мне подойти к этой проблеме?

Ответы [ 3 ]

4 голосов
/ 12 июля 2011

Основная ошибка состояла в том, что вход для линейного масштабирования уже должен быть положительным (по определению), тогда как я выбирал его также отрицательными значениями.

Речь идет об отрицательных значениях не о вводе в алгоритм, а о выводе (масштабированных значениях) из алгоритма.Проверка состоит в том, чтобы обработать этот случай, а затем исправить его, чтобы не создавать отрицательных масштабированных значений. 

  if(p->min > (p->scaleFactor * p->avg - p->max)/
     (p->scaleFactor - 1.0)) { /* if nonnegative smin */
    d = p->max - p->avg;
    p->scaleConstA = (p->scaleFactor - 1.0) * p->avg / d;
    p->scaleConstB = p->avg * (p->max - (p->scaleFactor * p->avg))/d;
  } else {  /* if smin becomes negative on scaling */
    d = p->avg - p->min;
    p->scaleConstA = p->avg/d;
    p->scaleConstB = -p->min * p->avg/d;
  }

На изображении ниже, если f'min отрицательно, перейдите к предложению else и обработайте этот случай.

Хорошо, тогда решение заключается в предварительном масштабировании вышеупомянутой функции, поэтому она дает только положительные значения.Как предположил Гиперборей, это можно сделать, добавив наименьшее возможное значение 

u = 5 - (2*5.12^2)

Лучше всего, если мы отделим реальные значения пригодности , которые мы пытаемся максимизировать от масштабированных значений пригодности значения, которые вводятся в selection phase GA.

enter image description here

1 голос
/ 20 мая 2012

Я согласен с предыдущим ответом. Линейное масштабирование само по себе пытается сохранить среднее значение пригодности, поэтому его необходимо сместить, если функция отрицательная. Для получения более подробной информации, пожалуйста, обратитесь к книге Гольдберга по генетическим алгоритмам (1989), глава 7, стр. 76-79.

1 голос
/ 14 июля 2011

Ваше наименьшее возможное значение для u = 5 - (2 * 5.12 ^ 2).Почему бы просто не добавить это к себе?

...