Algorytm genetyczny i jego zastosowanie praktyczne w pythonie

in pl-artykuly •  last year 


Cześć,

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

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!
Sort Order:  

Trudny temat :o Mógłbyś rozwinąć w przyszłości temat wynagradzania i karania algorytmów genetycznych? To jest tutaj chyba najciekawsze.

Generalnie właśnie ta funkcja fitness jest tutaj najtrudniejsza do stworzenia i jest inna dla każdego problemu. Natomiast cały czas przewija się takie pojęcie jak minimum globalne. Czyli dążenie do najlepszego rozwiązania w całym problemie. Jeżeli uda ci się tak ustawić zmienne, żeby wartości dążyły do optimum, gdy DNA się poprawia, to jest sukces. W moim przypadku, musiałem dać duży nacisk na typ jednostki, bo miałem za trudnych przeciwników. Reszta punktów była potrzebna na ustawienie się tych potworów.
Więcej raczej tutaj już nie jestem w stanie napisać. Widziałem też coś, że są jakieś inne typy przedstawiania takich funkcji, ale to trzeba się wkopać głębiej xd

Fajne, tipuvote! 5

Dzięki, staram się dodawać ciekawe rzeczy w miarę możliwości.

This post received 4.93 SBD upvote from @tipU funded by @cardboard | @grzegorz2047 now has a chance to win free @steembasicincome share :) | @tipU voting service quick guide.

Nie będę oryginalny i też powiem, że fajne ;) Kompletnie zapomniałem o istnieniu algorytmów genetycznych. Trzeba by sobie odświeżyć i spróbować się tym pobawić.

Jedna uwaga: nie wiem czy screenshoty kodu to najlepszy sposób jego prezentacji. Z drugiej strony na steemit nie ma kolorowania kodu, więc coś za coś. Może pośrednim rozwiązaniem mogłoby być wrzucanie linku do gista z kodem?

Kiedyś wrzucałem kod do artykułu, ale skończyło się to często nieciekawie, szczególnie z HTML. Jest link do projektu i tam masz cały kod. A co do algorytmów genetycznych, to polecam, bo nie jest to super trudne, a wyniki są spoko.