algorytmygenetyczne » informaja o konkursie | test umiejętnoci | kontakt  
Zmiana rozmiaru czcionki  Powiększ czcionkę Zmniejsz czcionkę MathML ON

Selekcja.

Selekcję dzielimy na dwa etapy:

  1. Reprodukcja - czyli wybór rodzica i utworzenie potomstwa.
  2. Sukcesja - zastapienie osobników ze starej populacji osobnikami z nowej.

Reprodukcja deterministyczna :

  1. Dla każdego osobnika obliczamy prawdopodobieństwo reprodukcji:
    $ p_r\left(A\right)=\frac{f\left(A\right)}{\sum f}$
  2. Spodziewana liczba reprezentantów w nowym pokoleniu:
    $n\left(A\right)=E\Big(n(A)\Big)=N\cdot p_r\left(A\right)$
  3. Obliczamy liczbę osobników A jako część całkowitą z n(A)
  4. Dla każdego osobnika obliczamy część ułamkową z n(A).
  5. Sortujemy listę osobników według malejących reszt.
  6. Pozostałe wolne miejsca uzupełniamy z góry listy.

Reprodukcja losowa według reszt z powtórzeniami:

  1. Postępujemy 1-4 jak przy reprodukcji deterministycznej.
  2. Części ułamkowe posłużą nam do wyskalowania ruletki, zatem im część ułamkowa jest większa tym większe są szanse na wylosowanie.

Reprodukcja losowa według reszt z powtórzeniami:

  1. Postępujemy 1-4 jak przy reprodukcji deterministycznej.
  2. Dla brakującej części populacji części ułamkowe stanowią prawdopodobieństwo sukcesu w próbie Bernulliego.

Metoda rangowa (rankingowa):

  1. Sortujemy całą populację według nierosnących współczynników dostosowania.
  2. Każdemu osobnikowi nadajemy rangę: najlepszy - 0, następny itd. Dla osobników o jednakowych współczynnikach dostosowania nadajemy takie same rangi lub według kolejności w tablicy.
  3. Wyliczamy prawdopodobieństwo reprodukcji
    $p_r\left(A\right)=a+k\bigg(l-\frac{r(A)}{r_{max}}\bigg)$
    $ \sum_{i=1}^Np_r\left(A\right)=1$         $ 0 \leq p_r\left(A\right) \leq 1 $
  4. Wyliczamy a i k tak,aby:
    $r(A)\leq r(B) \Rightarrow p_r(A)\geq p_r(B)$
    korzystając z tej metody można wpływać na presję selekcyjną.

Metoda reprodukcji progowej:

Po stworzeniu rankingu powielamy pewną liczbę osobników przekraczających zadany próg, tak aby ich liczba była taka sama jak na początku.

Metoda turniejowa:

  1. Ustalamy liczność turnieju, np. k;
  2. Metodą ruletki losujemy k-osobników;
  3. Następnie spośród wylosowanych reprodukujemy najlepszego;

Metoda pojedynku:

losujemy dwóch osobników, a następnie z pewnym prawdopodobieństwem wygranej reprodukujemy najlepszego.

Metody sukcesji

Sukcesja z całkowitym zastępowaniem:

  1. Tyle samo osobników w nowej populacji co i w starej i żaden osobnik ze starej populacji nie przechodzi do nowej;

Sukcesja z częściowym zastępowaniem;

  1. Parametr G określa jaki % osobników przetrwa ze starej populacji.
  2. Mamy do dyspozycji następujące sposoby wyboru zastąpienia osobników ze starej populacji:
    • losowo
    • usunięcie najgorszych
    • usunięcie najbardziej podobnych (elita ze ściskiem)

Sukcesja czystoelitarna:

Gdy w nowej populacji nie ma lepszych osobników, zatrzymujemy jednego lub dwóch najlepszych ze starej.