Algorytmy genetyczne - wybór rodziców
Wybór rodziców to proces selekcji rodziców, którzy łączą się w pary i ponownie łączą, aby stworzyć potomstwo dla następnego pokolenia. Wybór rodziców jest bardzo istotny dla stopnia konwergencji AH, ponieważ dobrzy rodzice kierują poszczególne osoby do lepszych i bardziej dopasowanych rozwiązań.
Należy jednak uważać, aby nie dopuścić do tego, aby jedno wyjątkowo odpowiednie rozwiązanie przejęło całą populację w ciągu kilku pokoleń, ponieważ prowadzi to do bliskości rozwiązań w przestrzeni rozwiązań, co prowadzi do utraty różnorodności. Maintaining good diversityw populacji jest niezwykle istotne dla sukcesu AH. To pochłanianie całej populacji jednym niezwykle odpowiednim rozwiązaniem jest znane jakopremature convergence i jest stanem niepożądanym w AH.
Wybór proporcjonalny do sprawności
Selekcja proporcjonalna do sprawności to jeden z najpopularniejszych sposobów selekcji rodziców. W tym przypadku każdy może zostać rodzicem z prawdopodobieństwem proporcjonalnym do jego sprawności. Dlatego bardziej sprawne osobniki mają większe szanse na krycie i rozmnażanie swoich cech na następne pokolenie. Dlatego taka strategia selekcji nakłada presję selekcyjną na bardziej sprawne osobniki w populacji, z czasem ewoluując lepiej.
Rozważmy okrągłe koło. Koło jest podzielone nan pies, gdzie n to liczba osobników w populacji. Każda osoba otrzymuje część koła, która jest proporcjonalna do jej wartości sprawności.
Możliwe są dwie implementacje selekcji proporcjonalnej do dopasowania -
Wybór koła ruletki
W wyborze koła ruletki koło jest podzielone tak, jak opisano wcześniej. Na obwodzie koła wybiera się stały punkt, jak pokazano, i koło jest obracane. Region koła, który znajduje się przed punktem stałym, jest wybierany jako rodzic. W przypadku drugiego rodzica ten sam proces się powtarza.
Oczywiste jest, że osoba montująca ma większy placek na kole, a tym samym większą szansę na wylądowanie przed punktem stałym, gdy koło jest obracane. Dlatego prawdopodobieństwo wyboru osoby zależy bezpośrednio od jej sprawności.
Mądrze wdrażamy, wykonujemy następujące kroki -
Oblicz S = suma finezji.
Wygeneruj liczbę losową z zakresu od 0 do S.
Zaczynając od góry populacji, dodawaj finezji do częściowej sumy P, aż P <S.
Osoba, dla której P przewyższa S, jest wybraną osobą.
Stochastic Universal Sampling (SUS)
Stochastic Universal Sampling jest dość podobny do wyboru koła ruletki, jednak zamiast mieć tylko jeden stały punkt, mamy wiele stałych punktów, jak pokazano na poniższym obrazku. Dlatego wszyscy rodzice są wybierani za jednym zamachem. Taka konfiguracja zachęca również wysoce sprawne osoby do wybrania przynajmniej raz.
Należy zauważyć, że metody selekcji proporcjonalnej do sprawności nie sprawdzają się w przypadkach, w których dopasowanie może mieć wartość ujemną.
Wybór turnieju
W selekcji turniejów K-Way wybieramy losowo K osób z populacji i wybieramy najlepsze z nich, aby zostać rodzicami. Ten sam proces jest powtarzany w celu wyboru następnego rodzica. Selekcja turniejowa jest również niezwykle popularna w literaturze, ponieważ może działać nawet z ujemnymi wartościami sprawności.
Wybór rangi
Wybór rang działa również z ujemnymi wartościami sprawności i jest stosowany głównie, gdy osobniki w populacji mają bardzo zbliżone wartości sprawności (dzieje się to zwykle pod koniec biegu). Prowadzi to do tego, że każda osoba ma prawie równy udział w tortu (jak w przypadku doboru proporcjonalnego przystosowania), jak pokazano na poniższym obrazku, a zatem każda osoba, bez względu na to, jak pasuje do siebie, ma w przybliżeniu takie samo prawdopodobieństwo, że zostanie wybrana jako rodzic. To z kolei prowadzi do utraty presji selekcyjnej na osoby bardziej sprawne, co sprawia, że AH w takich sytuacjach źle wybiera rodziców.
W tym przypadku usuwamy pojęcie wartości sprawności podczas wyboru rodzica. Jednak każda osoba w populacji jest uszeregowana według jej sprawności. Wybór rodziców zależy od rangi każdej osoby, a nie od sprawności. Osoby o wyższej randze są preferowane bardziej niż osoby o niższej randze.
| Chromosom | Wartość sprawności | Ranga |
|---|---|---|
| ZA | 8.1 | 1 |
| b | 8.0 | 4 |
| do | 8.05 | 2 |
| re | 7.95 | 6 |
| mi | 8.02 | 3 |
| fa | 7,99 | 5 |
Losowy wybór
W tej strategii losowo wybieramy rodziców z istniejącej populacji. Nie ma presji selekcyjnej na osoby sprawne fizycznie, dlatego zazwyczaj unika się tej strategii.