Выбор колеса рулетки в генетическом алгоритме. Население должно быть отсортировано в первую очередь?

В генетическом алгоритме, при выборе членов для кроссовера с использованием метода выбора колеса рулетки, нужно ли сначала сортировать популяцию по уровню пригодности?

Возможности кажутся следующими:

  1. сортировка населения по возрастанию
  2. сортировка населения по убыванию
  3. не сортируйте население и не позволяйте шарику рулетки упасть туда, где он может..

Я думаю, что сортировка в любом случае может не иметь никакого эффекта - случайная посадка гальки на колесо, содержащее срезы разного размера (по пригодности), будет иметь одинаковую вероятность результата, независимо от того, сгруппированы ли большие срезы или нет. Но я не уверен на 100%.

Как вы думаете?

Необходимость выполнять сортировку каждого поколения также влияет на скорость алгоритма, поэтому я бы предпочел не делать этого (я бы сделал сортировку, если бы использовал элитарность, но я не в этом случае). Спасибо, если вы знаете, как я не могу найти окончательный ответ через Google и т. Д..

Источник

3 ответа

Решение

Нет, вам не нужно их сортировать. Вы совершенно правы, что это не будет иметь никакого эффекта, если члены с более высоким рейтингом сгруппированы вместе или нет (по крайней мере, с хорошим генератором случайных чисел:)).

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

Источник

Даже если вы применяете элитарность, нет необходимости сортировать население.

Поиск лучших N индивидов требует только одной итерации по совокупности.

Источник

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

И вы также правы в отношении сложности, своего рода n*log(n), что делает генетический алгоритм значительно медленнее (но, тем не менее, сложность остается полиномиальной, критическая особенность генетических алгоритмов).

Вот как я бы это сделал (и получил за это дополнительные очки в школе):

  1. реализовать более общее решение с использованием хуков - до мутации, после выбора и т. д. и т. д.

  2. измерять количество итераций и скорость алгоритма / каждую итерацию

  3. сделай свою сортировку в крючке. измерения. теперь пусть крючок будет пустым и мерным и так далее.

Вы получите хорошие данные и экспериментально подтвердите то, что говорит вам ваша интуиция.

Источник
Другие вопросы по тегам