Algorytm genetyczny i jego zastosowanie praktyczne w pythonie

po dłuższej przerwie spowodowanej pracą i studiami, chciałbym opisać wam działanie prostych algorytmów genetycznych.

Implementowałem algorytmy w większym projekcie zespołowym jako część projektu indywidualnego , który polegał na rozmieszczaniu potworków na mapie oraz dostosowywaniu ich do umiejętności gracza. Na pozór skomplikowany problem, ale możliwy do rozwiązania przez algorytm genetyczny. Kod z projektu posłuży mi do przedstawieniu działania algorytmu.

Ok, na początku przedstawię wam jak działają algorytmy genetyczne i jak je rozumiem. W celu bardziej merytorycznego zrozumienia tego algorytmu, podlinkuję wam poniżej więcej informacji na ten temat. (Oczywiście jak was zainteresuję :D)

To teraz czas na kroki algorytmu:

1. Stwórz początkową losową populację osobników
2. Sprawdź witalność populacji
3. Dopóki nie osiągniesz satysfakcjonującej ilości punktów witalności, bądź nie przejdzie odpowiednia liczba generacji, idź do punktu 4.
4. Wykonaj ewolucję nowej populacji:
5. Stwórz nowe dziecko:
   a) Wybierz dwóch najlepszych z populacji
   b) Skrzyżuj geny wybranych osobników wybierając losową część z pierwszego osobnika i resztę z drugiego osobnika
   c) Wykonaj mutację jak się uda, czyli zmień losowy gen u dziecka
6. Sprawdź witalność dziecka/populacji
7. Wykonuj punkt 5. aż nie wypełnisz populacji
8. Zwróć najlepszy gen

Tak to mniej więcej wygląda, a przynajmniej tak to zrozumiałem.

Jeżeli chodzi o wybór osobników do krzyżowania, to są dwie metody:

1. Metoda rankingu
   Metoda ta polega na wybraniu np. 10 najlepszych osobników i krzyżowaniu ich między sobą

2. Metoda koła
   Metoda ta daję każdemu osobnikowi pewną część prawdopodobieństwa na to, że zostanie on wylosowany do krzyżowania.

W moim algorytmie wykorzystałem metodę 1. bo wydawała mi się prostsza do implementacji.

W mojej implementacji zastosowałem także coś takiego jak elitaryzm. Polega on na tym, że wziąłem najlepszą jednostkę z populacji i przekazałem ją do następnej populacji. To oczywiście wymagało większego poziomu mutacji, żeby nie utknąć z brakiem rozwiązania.

Zajmijmy się teraz praktycznym zastosowaniem algorytmu w projekcie. Jak już pisałem, użyję mojego projektu ze studiów. Nie jest on może jakiś wybitny, szczególnie, że nie jestem pythonowcem, ale do tego artykułu powinno styknąć.

Na początek zdefiniowałem sobie jak chcę przedstawiać DNA osobnika tzw. "Genotyp". Ludzie przedstawiają go w różne sposoby np. binarnie. Mój musiał być trochę bardziej zaawansowany, ale nie aż tak bardzo.
Wygląda on następująco:

Jeżeli chodzi o gen dla DNA, to wygląda on tak:

Jak widać, mój genotyp musi posiadać informacje o mapie, na którą ma coś ustawić oraz musi posiadać jakieś statystyki gracza, żeby mógł obliczyć swój fitness, czyli witalność.
Możemy zauważyć też funkcję, która tworzy nam losowy gen. Gen posiada informacje o położeniu potwora oraz jego statystyki. W tym silniku akurat miałem ustalone statystyki potworów, więc musiałem korzystać z czegoś takiego:

Powyżej zawarte są wszystkie możliwe potwory do ustawienia na mapie.

Każdy gen przechowuje takie informacje jak położenie, zdrowie, atak, obrona i typ. Wszystkie te informacje są potrzebne przy obliczaniu funkcji fitness dla danej jednostki.

Teraz chciałbym wam pokazać klasę odpowiedzialną za jednostkę w naszej populacji:

Jak widać powyżej, osobnik dostaję mapę, DNA, ale jego głównymi funkcjami, to crossover, czyli krzyżowanie się osobników oraz mutate, czyli mutacja.

Ostatnim krokiem jest teraz to wszystko posklejać, tworzyć populację i zwrócić najlepsze geny. A wygląda to tak:

Jeszcze w celu doprecyzowania, mapa, to tablica dwuwymiarowa złożona z literek i znaków. Kropka oznacza miejsce, gdzie potwór może zostać rozmieszczony. A i jeszcze tutaj koordynaty były odwrócone czyli odnosi się do (y,x) zamiast do (x,y)

Odniosę się teraz tylko do funkcji fitness, bo ona tu zajmuje dużo czasu, żeby było gites. Ta funkcja powinna być jak najprostsza obliczeniowo, żeby komputer nie zajmował zbyt dużo czasu na wyliczenie. Dlatego też najczęściej są to operacje dodawania, dodawania i jakiegoś mnożenia. Nic zbytnio skomplikowanego. Generalnie jeżeli zależy nam, żeby algorytm genetyczny szedł w jakąś stronę, to musimy go nagradzać. W moim przypadku nagradzałem go jak ustawiał poprawnie potwora i dawałem mu darmowe punkty ze statystyk gracza. Statystyki gracza mają większe znaczenie, gdy się zmieniają. Tutaj były one stałe. Jeżeli chodzi o karanie osobnika, to było to wtedy gdy standardowo potwór miał jakieś życie, miał jakieś punkty obrony, ataku oraz dałem ciężkie karanie jak potwór był wysokiego typu, bo taki akurat był najsilniejszy. Żeby coś bardziej obciążyć wykonywałem mnożenie o odpowiedniej wartości.

Tworzenie funkcji fitness, to jest jednak metoda prób i błędów aż dojdziemy do sensownego wyniku i zachowania się jednostek.

Pokaże wam teraz jak zachowuje się algorytm w pierwszych generacjach i jak wygląda to w późniejszych:

A tak wygląda po paru generacjach:

A taki mam widok w konsoli:

Jak widzicie, moja funkcja fitness wystarczyła, aby ustawić tak potwory, że da się je zabić.

Jeżeli macie jakiś prosty projekt, gdzie możecie użyć algorytmów genetycznych, to spróbujcie je zastosować. Możecie nawet zrobić mapę jako ASCII ART i pobawić się w coś takiego co ja tu zrobiłem.

Także to byłoby na tyle :)

Cały projekt znajduje się tutaj

Dodatkowe linki:
Akademicki wykład o algorytmach genetycznych PL
Javowy opis algorytmu EN