Populacja w algorytmach genetycznych

Poznaliśmy już najważniejsze etapy funkcjonowania algorytmów genetycznych, a także przeanalizowaliśmy dokładnie, jak działają operatory krzyżowania oraz mutacji. Przyjrzyjmy się teraz bliżej samemu doborowi początkowej puli populacji. Jest to pierwszy, a zarazem dość istotny krok w przebiegu całego algorytmu i może wpłynąć między innymi na jakość finalnych rezultatów.

Zazwyczaj wybór populacji początkowej jest całkowicie losowy. Jednak bywają sytuacje, gdy wykorzystujemy inicjalizację heurystyczną. Polega ona na doborze konkretnej puli populacji, zazwyczaj mało różnorodnej. Tego typu rozwiązanie wykorzystuje się najczęściej, gdy wiemy, w jakich obszarach pragniemy szukać rozwiązań naszego problemu. Jednocześnie gwarantuje ono znacznie większą szybkość i niezawodność przeprowadzanych operacji.

Należy pamiętać jednak, że mniejsza różnorodność wiąże się również z uzyskaniem nieoptymalnego rozwiązania. Co ciekawe, istnieje możliwość połączenia obu typów inicjalizacji. Wybieramy gotową populację, a następnie dodajemy do niej grupę losowych rozwiązań. W ten sposób możemy zapewnić większą różnorodność w populacji niż w przypadku podejścia heurystycznego oraz większą szybkość i niezawodność przeprowadzanych operacji niż w przypadku inicjalizacji losowej. Teoretycznie można byłoby nazwać to rozwiązanie złotym środkiem, jednak należy pamiętać, że typ doboru początkowej populacji powinien być dostosowany do sytuacji.

Gdy wiemy już, jak wygląda wstępna inicjalizacja, warto poruszyć temat modeli populacji. Różne modele umożliwiają większe lub mniejsze dostosowanie przebiegu wykonywania algorytmu do naszych potrzeb i oczekiwań. Istnieje szereg różnych klasyfikacji modeli, jednakże my skupimy się na ich podziale na lokalne, regionalne i globalne. Podział ten bazuje na strategii wyboru rodziców, a także doboru obszaru selekcji. W przypadku modelu globalnego proces selekcji odbywa się na całej populacji, nie ograniczając w żaden sposób doboru rodziców. Jest to wręcz klasyczny wariant algorytmu genetycznego.

Model regionalny bazuje na podziale pełnej populacji na określoną ilość podgrup zwanych subpopulacjami. Rodziców możemy dobrać tylko z obszaru tej samej subpopulacji. Po pewnym czasie nastąpić może proces migracji, w ramach którego część rozwiązań jest przenoszona do innych grup. Ma on na celu zwiększenie różnorodności pomiędzy osobnikami w tej samej populacji. Dużym plusem modelu regionalnego jest znaczne przyspieszenie czasu przeprowadzania obliczeń.

Ostatnim rozpatrywanym modelem będzie model lokalny. Ogranicza on wybór rodziców jedynie do sąsiadujących ze sobą rozwiązań. W ten sposób wraz z każdym kolejnym pokoleniem następować będzie przekazanie części genów przodków do coraz dalej ulokowanych osobników.

Podsumowując, zarówno dobór początkowej populacji, jak i obrany jej model w znaczny sposób wpłynąć mogą na sam przebieg wykonywania naszego algorytmu oraz jego rezultat. Szereg przedstawionych możliwości pozwala nam uzyskiwać ciekawe wyniki oraz testować algorytmy genetyczne pod przeróżnymi kątami. Warto o tym pamiętać, nawet jeżeli zazwyczaj korzystać będziemy z klasycznej inicjalizacji losowej i modelu globalnego.