Algorytmy genetyczne – podstawy

Witajcie

Tym wpisem zamierzam udowodnić że algorytmy genetyczne są nie tylko fajną dziedziną programowania, ale również mogą być proste. W dalszej części wpisu znajdziecie opis implementacji prostego algorytmu i  link do wklejki z programem wykonanym w języku C#. Na teraz zaserwuje wam ciekawy dla oka projekt genetics cars 2, projekt przy użyciu algorytmu genetycznego szuka najlepszego projektu bicykla, który będzie w stanie przejechać jak najdalej.

Algorytmy genetyczne służą do optymalizacji i poszukiwań najlepszego wyniku w zbiorze danych, z racji że są to algorytmy heurystyczne nie dostajemy najlepszej możliwej odpowiedzi, ale wystarczająco dobrą. Co oznacza wystarczająco, o tym będzie niżej. Inspiracją dla algorytmów genetycznych jest proces ewolucji i genetyka, wiele terminów w tym zagadnieniu pochodzi właśnie z tej dziedziny nauki. Zanim przejdziemy dalej do opisu algorytmu wyjaśnijmy kilka podstawowych pojęć.

Genotyp – zbiór cech opisujący osobnika.

Funkcja przystosowania – funkcja służąca do oceniania danego genotypu, na jej podstawie określa się, które osobniki są lepsze i jakie mają prawdopodobieństwo przekazać swój genotyp dla kolejnej generacji.

Generacja/Pokolenie – zbiór osobników biorący udział w selekcji i rekombinacji.

Rekombinacja/Krzyżowanie – generowanie nowego osobnika na podstawie genotypów dwóch innych osobników.

Mutacja – losowe zmiany w genotypie. Dzięki mutacjom algorytm potrafi wyjść znaleźć rozwiązanie poza dostępną pulą genów.

Algorytm składa się z kilku kroków.

  1. Losowana jest pewna populacja początkowa.
  2. Populacja poddawana jest ocenie (selekcja). Najlepiej przystosowane osobniki biorą udział w procesie reprodukcji.
  3. Genotypy wybranych osobników poddawane są operatorom ewolucyjnym:
    1. są ze sobą kojarzone poprzez złączanie genotypów rodziców (krzyżowanie),
    2. przeprowadzana jest mutacja, czyli wprowadzenie drobnych losowych zmian.
  4. Rodzi się drugie (kolejne) pokolenie. Aby utrzymać stałą liczbę osobników w populacji te najlepsze (według funkcji oceniającej fenotyp) są powielane, a najsłabsze usuwane. Jeżeli nie znaleziono dostatecznie dobrego rozwiązania, algorytm powraca do kroku drugiego. W przeciwnym wypadku wybieramy najlepszego osobnika z populacji – jego genotyp to uzyskany wynik.

~Wikipedia

Przykładowy program

W przykładzie użyjemy algorytmu genetycznego do szukania maksimum funkcji. Podczas czytania artykułu możecie na bieżąco śledzić kod programu https://gist.github.com/Sylwekqaz/9a1b60f8595fb002899fa123e7dcb688

Tak więc do maksymalizacji przygotowałem specjalną funkcję:

-\left ( \frac{\left ( x-100 \right )}{10} \right )^{2} + 50Sin(x) + 10

pierwszy człon to parabola wygięta bokami w dół (smutna parabolka), lekko rozciągnięta w osi X i przesunięta o 100 jednostek w prawo. Drugi człon równania dodaje pofalowanie funkcji, które ma utrudniać znalezienie maksimum funkcji standardowymi metodami,a dzięki ostatniemu członowi całość jest podniesiona do góry o 10 jednostek. Wykres tej funkcji wygląda mniej więcej tak.

 

Następnie trzeba określamy jak reprezentujemy genotyp, tutaj wybiorę najprostszy typ czyli jako liczbę binarną, ze względu na łatwą rekombinację. Aby nie robić problemu z kodowanie m liczb ujemnych problem zawężamy do liczb dodatnich, a aby ograniczyć ilość bitów ograniczymy liczbę binarną do 8 bitów, więc genom będzie reprezentowany poprzez zmienną typu byte.

Genotypy reprezentowane przez liczby binarne są łatwe do krzyżowania. Obie liczby dzielimy w losowym miejscu pomiędzy bitami i sklejamy nową liczbę z dwóch polówek pochodzących od rodziców. Poniżej przykład krzyżowania liczb 166 i 94 z podziałem pomiędzy piątym a szóstym bitem. Mutacje można rozwiązać poprzez inwersję losowego bitu. Implementację można zobaczyć tutaj.

Dec Bin
166 101|00110 Przodek
94 010|11110 Przodek
190 101|11110 Potomek
182 101|10110 Potomek – mutant

Nowa populacja składa się z kilku najlepszych osobników z poprzedniej populacji i osobników wygenerowanych poprzez krzyżowanie osobników z poprzedniej populacji osobników z prawdopodobieństwem zależnym od ich przystosowania, w przykładowym programie dla każdego osobnika obliczam różnicę pomiędzy jego przystosowaniem a przystosowaniem najgorszego osobnika z populacji, mając te wartości obliczam stosunek tej różnicy do sumy różnic, które jest prawdopodobieństwem wylosowania osobnika X jako rodzica. Czyli dla dla osobników z wartościami przystosowania 1,3,4,6 obliczanie prawdopodobieństwa wyglądać będzie tak

wartość przystosowania różnica prawdopodobieństwo
Populacja 1 0 0
3 2 0,2
4 3 0,3
6 5 0,5
minimalna wartość: 1 suma: 10

Powstaje jeden problem, o ile generacja 1,2,3...n powstają poprzez krzyżowanie poprzedniej generacji, to zostaje jeszcze generacja zerowa, która nie może powstać w wyniku krzyżowania. Najprostszym sposobem jest wylosowanie takiej populacji i jest to sposób używany nawet przy zaawansowanych algorytmach genetycznych.

Jak długo powtarzać proces selekcji i krzyżowania? Jest tu kilka rozwiązań, które są używane zależnie od problemu. Najprostszym sposobem jest wykonanie X obrotów pętli, gdzie X jest określone z góry, to właśnie podejście zostało zaimplementowane w przykładowym programie. Drugim podejściem jest wykonywanie pętli do czasu aż program przez X kroków nie poprawi wyniku (lub poprawi go nieznacznie). Trzecie podejście stosowane jest w przypadku kiedy działanie algorytmu jest długie i głównie ogranicza nas czas, wtedy wykonujemy pętlę do wyczerpania limitu czasu.

 

Dajcie znać w komentarzach co myślicie o algorytmach genetycznych i takich dłuższych technicznych postach. Każdy konstruktywny feedback i ciekawe dyskusję dają mi motywację do pisania kolejnych ciekawych postów, więc do dzieła, textbox do wpisywania komentarzy jest wasz, podobno nie gryzie, czasami tylko dyskusja wciąga w całości ;).

 

3 Pingbacks/Trackbacks

  • Łukasz Biedak

    Przykład książkowy, co nie jest złe, gdy nigdy nie miałeś takiej książki w ręku. Z pewnością bardziej zachęciłoby, gdybyś pokazał, że jakiś realny problem może być w prosty sposób zamodelowany i rozwiazany metodami algorytmów genetycznych.

    Np. Wybór roweru. Wyobraź sobie, że rower ma 6 komponentów {A1,….A6}, rama, przerzutki itd. Każdy komponent ma 4 warianty (2 bity danych) cenowo-jakościowe. Należy znaleźć propozycje konfiguracji osprzętu rowere, który mieści się w naszym budżecie i ma relatywnie dobry osprzęt.

    Zapraszam do mnie lubiedak.wordpress.com

  • Pingback: dotnetomaniak.pl()

  • Dawid Loranc

    Mogłeś jeszcze napisać jaki jest przebieg i wynik tego przykładowego algorytmu. Ciekawa sprawa ogólnie, ale do tej pory nie miałem z tego typu algorytmami do czynienia.

    • Sylwekqaz

      Racja, brakuje screenów z programu, aczkolwiek nie chciałem wchodzić w temat wyników i wniosków, bo jest to rozległy temat i jeszcze będzie o tym w innym wpisie, albo u mnie, albo u Weroniki ma http://codekillers.yum.pl

    • Sylwekqaz

      Racja, brakuje screenów z programu, aczkolwiek nie chciałem wchodzić w temat wyników i wniosków, bo jest to rozległy temat i jeszcze będzie o tym w innym wpisie, albo u mnie, albo u Weroniki ma http://codekillers.yum.pl

  • Pingback: Algorytmy genetyczne. Część 1. | CODE KILLERS()

  • Pingback: #5 Buying a motorocycle – how to create rationalization for irrational decisions? Use genetic algorithms! – Algorithmic Thinking()