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

Question

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

Возможные варианты:

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

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

Что вы думаете?

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

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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

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

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

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

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

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