Algorytmy genetyczne - rosnący rozmiar populacji

Cześć, nie mogę tego jakoś ogarnąć. Dajmy na to, że jest 20 osobników w populacji. Jeśli teraz dokonuję selekcji za pomocą koła ruletki, to dostanę listę 20-elementową składającą się z osobników (którzy mogą się powtarzać) gotowych do kopulacji. OK, to jest jasne.

Ale teraz załóżmy, że osobnik A jest na tej liście 5 razy. Teraz muszę stworzyć na podstawie tej listy pary do krzyżowania. Rozumiem, że ilość tych par jest parametrem algorytmu, tak?

OK i teraz (dla przykładu) 4 wybrane pary wyglądają tak:
AB
AC
AD
CD

Po każdym krzyżowaniu dzieci zastępują rodziców, ale w takim wypadku zwiększy się liczebność populacji. Po pierwszym krzyżowaniu(AB) usuwam osobników A i B, a dodaję ich dzieci. I tu jest ok. Ale po drugim krzyżowaniu nie mogę już usunąć osobnika A z populacji, bo jego już tam nie ma. Czyli na miejsce osobnika C wskoczą dwa nowe osobniki. Wielkość populacji zwiększa się o 1. Z moich testów wynika, że po kilku tysiącach iteracji, rozmiar populacji wzrasta do około 2000 osobników (początkowy rozmiar to 20). Czy to jest normalne? Czy rozmiar populacji nie powinien być stały? A jeśli tak, to jak zapewnić stały rozmiar w przypadku, gdy jeden osobnik jest krzyżowany kilka razy? Czy powinienem usuwać najsłabsze osobniki, czy jest może jakiś inny sposób?

To co napisałeś w ogóle nie ma sensu i nie rozumiesz jak działa ten algorytm.
Masz populacje X o rozmiarze N
Wybierasz z niej N razy parę osobników do reprodukcji (czyli N razy wybierasz sobie jakieś dwa dobre osobniki).
Z każdej pary wychodzi nowy osobnik, w sumie jest ich N.
Wszystkie te nowe osobniki zastępują poprzednią populacje X.

W twoim algorytmie cały czas w populacji trzymałbyś najgorsze osobniki bo nigdy nie zostałyby rodzicami i nigdy byś ich nie "usunął". Genialne :D

Czyli zaraz. Wg tego, co napisałeś wynika, że jeśli mam populację o rozmiarze 20, to 20 razy wybieram pary do reprodukcji. Co daje mi 20 par. Ale z tych 20 par otrzymam 40 nowych osobników, bo jedna para tworzy dwóch potomków. No to jest coś nie tak. Zgadzam się, że trzymam najgorsze osobniki w populacji. Tak jest i to mi nie pasuje, ale to wszystko, co czytałem na ten temat właśnie zakłada, że osobniki nie biorące udziału w krzyżowaniu, przechodzą do następnego pokolenia.

Na Wikipedii możemy przeczytać:
"Rodzi się drugie (kolejne) pokolenie. Aby utrzymać stałą liczbę osobników w populacji te najlepsze (według funkcji oceniającej fenotyp) są powielane, a najsłabsze usuwane", co by wskazywało, że faktycznie na koniec muszę usunąć najgorsze osobniki.

Ale wg. tego już nie koniecznie:
http://www.michalbereta.pl/dydaktyka/alg_imm/klasyczny_algorytm_genetyczny.pdf
"Kojarzy się w pary i dla każdej pary podejmowana jest decyzja o krzyżowaniu.
Pozytywna: następuje krzyżowanie, a powstałe osobniki potomne zastępują swoich rodziców.
Negatywna: para jest pozostawiana bez zmian."

Jestem zagubiony. Pozostała jeszcze kwestia mutacji. Gdzie w jednym miejscu przeczytałem, że decyzja o mutacji zapada dla każdego genu z osobna, a w innym, że raz w iteracji dla każdego osobnika. Osobiście wydaje mi się bardziej naturalne to drugie rozwiązanie.

@Juhas o_O jak N razy wybiorę sobie parę to będę miał N par a z N par jest N dzieci... Ale rozumiem że u ciebie w rodzinie każdy zawsze ma bliźniaki albo 2 dzieci :D
Taktyk jest wiele, czasem wybiera się najlepsze, czasem losowo wybiera się osobniki z tego "nowego pokolenia" oraz ze starej populacji. Czasem robi sie jeszcze inne optymalizacje. Nie ma "jednego sposobu".
Tak samo zresztą jest z krzyżowaniem i mutacją - nie ma jednej jedynej poprawnej definicji jak i kiedy.

Widzę, że tu algorytmy się uprawia, więc spieszę z pomocą ;)
Wybór kolejnych pokoleń zawsze determinuje strategia, którą sobie wybrałeś. Może ich być kilka:

1. N osobników najlepiej przystosowanych - zawsze będziesz miał do wyboru N osobników do par, więc populacja będzie stała. Niestety przy wybieraniu tychże taka populacja dosyć szybko zbiega do pewnego minimum lokalnego *

2. Zastępujemy starsze pokolenie nowym młodym. Metoda daje spory rozrzut, osobników zawsze będzie N (bo generujesz N par, a zatem N potomków jak napisał @Shalom). Sprawna, szybka do implementacji, tylko czasem można zgubić osobnika, który mógł trafić w lepsze (albo najlepsze) minimum *

3. Miks. Dobrym sposobem jest zawsze zostawić sobie np. najlepszych przodków i całe nowe pokolenie - potem losowanie par. Zawsze jest szansa, że coś dobrego się z tych rozwiązań zachowa.

4. Zawsze możesz ustawić sztywno liczbę M - maksymalną ilość osobników "w grze". I potem wybierać tych , których zachowasz.

5. Wersja losowa, a metoda znana z kar w armiach rzymskich - decymacja. Wybieramy każdego np. dziesiątego osobnika - i wyrzucamy z puli, czyli de facto - zabijamy.

*w celu uniknięcia zbyt szybkiej zbieżności przydaje się operator mutacji (może to być zwykłe losowanie cechy, albo w przypadku wektora kodującego gen - jakaś losowa zmiana). Tylko nie przesadzajmy z prawdopodobieństwem mutacji. Robiłem eksperyment na szeregowaniu zadań - w okolicach prawdopodobieństwa mutacji 0.2 wychodziło mi najlepiej, ale jest to zależne od problemu.

EDIT: No i ważna rzecz - kryterium stop. Też może się różnić - np. ilość pokoleń równa X albo ilość osobników w grze... Czy cokolwiek innego. Naturalny sposób zarówno ograniczenia populacji, jak i czasu działania algorytmu.

Dlaczego mi piszecie, że z jednego krzyżowania powstaje jeden osobnik, skoro wszystko, co czytam jasno stwierdza, że z jednego krzyżowania powstają dwa osobniki? Weźmy najprostszy chromosom - binarny.

Dajmy na to:
Ojciec: 11001100
Matka: 10010010

Teraz krzyżujemy, powiedzmy że miejsce krzyżowania jest za 4tym bitem:
Dziecko 1: 11000010
Dziecko 2: 11001001

Tak mi mówi wszystko, co czytałem do tej pory. Również załączone linki. Więc czemu wg Was z jednego krzyżowania powstaje jeden potomek?

@Juhas ty chyba nadal nie rozumiesz ze algorytmy genetyczne to jest KLASA ALGORYTMÓW a nie jeden konkretny algorytm. To tak jakbyś sie nas pytał czemu countingsort wygląda inaczej niż quicksort skoro oba to algorytmy sortujące. Jedyne co łączy te algorytmy to fakt że glowne kroki są takie same:

• selection
• crossover
• mutation
  Ale samo działanie tych kroków zależy od implementacji i różne mozliwości są opisane na milion sposobów.
  Równie dobrze możesz generować 1 potomka z 4 rodziców albo 10 potomków z 2 rodziców.

Ile algorytmów tyle pomysłów.
Możesz generować dwóch potomków, a możesz z każdego rodzica losowo wybrać pół genów i "wyprodukować jednego".

Nic nie stoi na przeszkodzie, żeby wyprodukować 10 - wszystko zależy od strategii "rozmnażania".

EDIT: @Shalom mnie wyprzedził :)

TL;DR
Przy krzyżowaniu powstaje 1 do n dzieci. Mogą zastąpić lub nie rodziców.

OK, porównanie do algorytmów sortujących do mnie trafia. Więc teraz pytanie. Skoro mamy różne algorytmy sortujące, które są znane i używane, to czy tak samo jest z algorytmami genetycznymi? Tzn. czy są jakieś "ogólnodostępne", generalne algorytmy genetyczne? Czy też każdy taki algorytm powstaje pod kątem konkretnego problemu?

W rzeczywistości te sortowania nie są dobrym porównaniem bo jest ich raptem kilka i są jasno określone, podczas gdy tutaj możliwości doboru parametrów jest nieskończenie wiele ;]
GA zawsze jest dobierany pod konkretny problem choćby dlatego że reprezentacja osobników w populacji zależy od problemu który rozwiązujesz. Podobnie krzyżowanie osobników musi być przemyślane pod kątem problemu, tak żeby faktycznie była szansa że połączenie dwóch dobrych osobników da osobnika lepszego (w problemach które nie są trywialną optymalizacją ciągłej funkcji R->R wcale nie jest oczywiste jak krzyżować osobniki).
Oczywiście istnieją standardowe strategie "kogo wybierać do krzyżowania" i "kogo zostawiać w populacji", niemniej jest ich dość sporo i ludzie doktoraty robią analizujac które podejście dla danego problemu sprawdza sie lepiej ;]