Wybór koła ruletki w algorytmie genetycznym. Ludność musi być najpierw posortowana?

Question

W algorytmie genetycznym, przy wyborze członków do crossover za pomocą metody wyboru koła ruletki, czy populacja musi być najpierw posortowana według rangi fitness?

możliwości wydają się być:

1. porządek najpierw przez ludność rosnąco Fitness populację
2. Sortuj według malejącej sprawności
3. nie sortować populację & niech upadek ruletka piłkę tam, gdzie może ona ..

Myślę, że sortowanie w obu kierunkach może nie przynieść żadnego efektu - lądowanie na kamieniach losowo na kole o różnych rozmiarach (według kondycji) będzie miał taką samą szansę na wynik, czy większe plasterki są zgrupowane razem, czy nie. Ale nie jestem w 100% przekonany.

Co myślisz?

Potrzeba zrobienia sortowania w każdym pokoleniu wpływa również na szybkość algorytmu, więc wolałbym tego nie robić (zrobiłbym coś w rodzaju elitarności, ale w tym przypadku nie jestem). Dzięki, jeśli wiesz, ponieważ nie mogę znaleźć ostatecznej odpowiedzi za pośrednictwem Google itp.

Answer 1

Nie, w rzeczywistości nie musisz ich sortować. Masz całkowitą rację, że nie przyniesie to skutku, jeśli członkowie wyższej rangi są zgrupowani lub nie (przynajmniej z dobrym generatorem liczb losowych :)).

Twoja intuicja jest tu martwa - statystycznie nie będzie miała żadnego efektu sortowania, a jak wspomniałeś, nie musisz tracić czasu i wysiłku na sortowanie rzeczy!

Answer 2

Nie musisz sortować populacji, jeśli używasz takiego wyboru.

I masz również rację co do złożoności, sortem jest n * log (n), co czyni algorytm genetyczny znacznie wolniejszym (ale nadal złożoność pozostaje wielomianem, krytyczną cechą algorytmów genetycznych).

Oto jak chciałbym to zrobić (i dostać dodatkowe punkty za to w szkole):

1. wdrożyć bardziej ogólne rozwiązanie za pomocą haków - przed mutacją, po selekcji itp itd

2. mierzyć liczbę powtórzeń i szybkość algorytmu/każda iteracja

3. wykonać sortowanie w haku. zmierzyć. teraz niech haczyk będzie pusty i zmierz i tak dalej.

Dostaniesz fajne dane i eksperymentalnie sprawdzisz, co podpowiada ci intuicja.

Answer 3

Nawet jeśli zastosujesz elitaryzm, nie ma potrzeby sortowania populacji.

poszukiwaniu najlepszych osobników N wymaga tylko jednego iteracji przez mieszkańców.