Podręcznik

Schemat działania algorytmu genetycznego

Działanie klasycznego algorytmu genetycznego przebiega w pętli, w której każda iteracja odpowiada kolejnemu pokoleniu osobników. Schemat zamieszczony poniżej prezentuje pętlę, w której nastepują po sobie kolejno: reprodukcja, operacje genetyczne, ocena i sukcesja. Czasami reprodukcje i sukcesje określa się łącznym mianem selekcji. Reprodukcja w połączeniu z operacjami genetycznymi modeluje rozmnażanie, podczas którego materiał  genetyczny rodziców przekazywany jest potomkom.

Najprostszy algorytm genetyczny operuje na dwóch populacjach: bazowej oraz potomnej. Dodatkowo wykorzystywane jest również pojęcie populacji  tymczasowej. W każdej populacji zawarta jest jednakowa liczba osobników.  

Typowy schemat działania algorytmu genetycznego rozpisany bardziej dokładnie wygląda następująco: 

1. Inicjalizacja populacji

   • Tworzymy początkową populację osobników. Zazwyczaj są one generowane losowo. Populacja powinna być zróżnicowana, aby dobrze pokryć przestrzeń poszukiwań. 
2. Dekodowanie genotypów do fenotypów
   • Każdy osobnik jest dekodowany z formy genotypowej (czyli zapisanej w chromosomie) do fenotypu, czyli rzeczywistego rozwiązania problemu.
3. Ocena przystosowania
   • Na podstawie fenotypu obliczana jest wartość funkcji celu, która pełni rolę miary przystosowania osobnika. Lepsze rozwiązania mają wyższą wartość przystosowania (lub niższą – w zależności od problemu).
4. Selekcja
   • Wybieramy osobniki do rozrodu. Lepsze osobniki mają większą szansę na wybór, co odzwierciedla mechanizm doboru naturalnego. Najczęściej używane metody to selekcja ruletkowa, rankingowa oraz turniejowa.
5. Krzyżowanie (rekombinacja)
   • Łączymy pary wybranych osobników, tworząc nowe osobniki-potomków. Krzyżowanie pozwala mieszać cechy rodziców i eksplorować nowe fragmenty przestrzeni rozwiązań.
6. Mutacja
   • W genomie potomków losowo modyfikujemy niektóre geny. To wprowadza dodatkową zmienność i pozwala uniknąć zbyt szybkiego zbiegania do lokalnego optimum.
7. Tworzenie nowej populacji (sukcesja)
   • Nowa generacja może całkowicie zastąpić poprzednią, albo współistnieć z nią przez kilka pokoleń. Istnieją różne strategie: np. elitaryzm (najlepsi osobnicy są automatycznie przenoszeni dalej), sukcesja częściowa itd.
8. Ocena nowego pokolenia
   • Osobniki z nowej populacji, którzy jeszcze nie zostali ocenieni, są dekodowani do fenotypu, i poddawani ocenie. 
9. Sprawdzenie warunku zakończenia
   • Algorytm kończy działanie, gdy spełniony jest określony warunek: osiągnięto maksymalną liczbę pokoleń, rozwiązania nie poprawiają się od kilku iteracji, lub osiągnięto wystarczające przystosowanie. Jeśli nie - wracamy do kroku 4. 

Ten schemat jest podstawą działania większości wariantów algorytmów genetycznych. W bardziej zaawansowanych wersjach mogą pojawić się dodatkowe elementy, jak presja selekcyjna, adaptacja parametrów, koewolucja czy wielokrotne populacje działające równolegle. Jednak fundament pozostaje taki sam – inspirowany działaniem ewolucji w naturze.