Algorytmy genetyczne - mona lisa

Algorytmy genetyczne. Część 1.

Algorytmy genetyczne są odwzorowaniem teorii ewolucji, algorytmami stworzonymi do poszukiwania jak najlepiej przystosowanych rozwiązań do danego problemu. Należy tutaj uwzględnić zwrot „jak najlepiej”, ponieważ algorytmy te nie gwarantują najlepszych rozwiązań problemu, lecz najlepsze w określonym czasie. Prekursorem badań nad algorytmami genetycznymi oraz ich twórcą jest John Henry Holland z Uniwersytetu Michigan; obecnie zalicza się je do grupy algorytmów ewolucyjnych.

 

Dlaczego taką wagę przykłada się do słowa „genetyczne”? Zaskoczeniem nie będzie, jeśli powiem, że rozwiązywanie problemów polega na zasadach ewolucji i dziedziczenia znanych z biologii. Na początku taki algorytm korzysta z potencjalnej populacji rozwiązań, zwykle generowanych losowe. Populacja taka posiada pewną funkcję przystosowania, analogicznie jak w przyrodzie zwierzęta posiadają różne funkcje przystosowania do warunków środowiskowych. Czyli mamy takie stado antylop, które natura wyposażyła w roślinożerność i szybkie nogi, tylko tutaj rozwiązują problem matematyczny. Następnie taka populacja jest poddawana selekcji: wybieramy, które osobniki chcemy skrzyżować i w jakich parach. Prowadzi to do skrzyżowania genów, czasem jednak, z bardzo małym prawdopodobieństwem, występuje mutacja powstałego osobnika. Gdy stworzymy drugie pokolenie, ostatnim etapem będzie utrzymanie stałej populacji stada – musimy niektóre najgorzej przystosowane osobniki usunąć. Jeżeli nie znaleźliśmy w tym czasie zadowalającego wyniku w postaci najlepszego osobnika, algorytm wraca do krzyżowania populacji, by stworzyć kolejne pokolenie.

Schemat takiego algorytmu wygląda następująco:

Schemat algorytmu genetycznego

 


Prosty przykład, by zrozumieć działanie:

Populacja początkowa:

Przypuśćmy, że naszym problemem jest stworzenie potworka ( w przyszłości jakaś funkcja), który będzie wyglądał jak człowiek (w kolejnym przykładzie jakieś minimum lub maksimum). Ustalmy, że:

  1. Zaawansowanie potwora będziemy określać w kategoriach ma lub nie ma danej ludzkiej cechy.
  2. Im więcej potwór będzie miał ludzkich cech, tym większa będzie wartość funkcji celu.
  3. Bierzemy pod uwagę oczy, usta, sylwetkę i nogi. Potwora będziemy określać jako ciąg złożony z kodu dwójkowego (w przyszłym wpisie opiszę różne możliwości zapisu genu), i tak dla potwora, który nie ma ludzkich cech, taki ciąg będzie wyglądał następująco (0,0,0,0), a dla człowieka tak: (1,1,1,1). Dla potwora, który ma sylwetkę człowieka ciąg będzie o taki (0,0,1,0).

Stwórzmy teraz do zakodowania naszych informacji. Jak widzicie, każda wartość ma swoje odwzorowanie w kodzie dwójkowym. Wylosujmy cztery pierwsze osobniki:

Algorytmy gentyczne - tworzenie populacji początkowej

Selekcja:

Wskaźnik przystosowania określiłam na podstawie przeliczenia kodu dwójkowego na system dziesiętny, jednak to od nas zależy jak taka funkcja będzie wyglądać. Suma wskaźników wynosi w tym przykładzie 30, obok określiłam również udział procentowy. Jest to przydatne, ponieważ wybierając osobniki, które będę reprodukować, wykorzystam tzw. ruletkę – jest to etap selekcji.

(Etap ten można przeprowadzić tez na inne sposoby, będzie o nich można przeczytać w następnych wpisach.)

Każdemu osobnikowi będzie odpowiadał odpowiedni procent obwodu koła, za każdym razem, gdy potrzebujemy wybrać osobnika do reprodukcji – kręcimy kołem. Mówiąc kolokwialnie: widzimy, że potwór nr 2 ma więcej cech ludzkich, więc wybierzemy go z większym prawdopodobieństwem niż potwora nr 4.  Trzeba tutaj dodać, że osobnika do reprodukcji KOPIUJEMY i kopię dołączamy do tzw. puli rodzicielskiej, jest zatem możliwe posiadanie w puli rodzicielskiej dwóch takich samych osobników z jednego.

Kręcimy ruletką, by wylosować rodziców. Możemy również obliczyć oczekiwaną liczbę kopii, należy jednak pamiętać, że nie zawsze musi się ona pokrywać z losowaniem.  Liczymy ją dzieląc wskaźnik przystosowania przez średnią wartość tego wskaźnika.

Algorytmy genetyczne - selekcja

Krzyżowanie

Dobraliśmy w taki sposób pulę rodzicielską. Wykorzystujemy w tym przykładzie krzyżowanie proste (ang. simple crossover*), które ma dwa etapy: dobieramy losowo pary z puli rodzicielskiej a następnie losowo wybieramy punkt krzyżowania k z jednakowym prawdopodobieństwem dla wszystkich. Punkt krzyżowania wybieramy spośród wszystkich pozycji mniejszych niż długość ciągu (l-1 zatem nigdy nie ma możliwości, by punkt krzyżowania znalazł się na ostatniej pozycji, oznaczałoby to tylko tyle, że geny zamieniły by się miejscami). Krzyżowanie polega na zamianie znaków od pozycji k+1 aż do l.

 Algorytmy genetyczne - losowanie populacji

Trzeba zauważyć, że ciągi, które miały największy wskaźnik przystosowania przetrwały. W następnych wpisach skupimy się na schematach i wzorcach, które pomogą zrozumieć, że pewne ułożenia genów są bardziej pożądane niż inne.

Mutacja

Teoretycznie przerobiliśmy jeden cykl algorytmu genetycznego, stworzyliśmy nową populację, określiliśmy jej wskaźnik przystosowania, jednak jeszcze nie powiedzieliśmy nic o mutacjach. Odgrywa ona nieco mniejszą rolę niż przedstawione wcześniej selekcja i krzyżowanie. Prawdopodobieństwo mutacji zwykle określa się jako jedną tysięczną (~0,001%), jednak w pewnych przypadkach jest niezbędna. Gdy selekcja i krzyżowanie usuną potencjalnie dobre rozwiązanie, mutacja może sporadycznie przywrócić usuniętą kombinację. Mutacja polega więc na sporadycznej, przypadkowej zamianie wartości w ciągu.

Czym różnią się algorytmy genetyczne od tradycyjnych metod?

Cytując Goldberga, możemy wyróżnić cztery zachodzące różnice, które mogliście uchwycić w trakcie czytania wpisu:

  1. Algorytmy genetyczne nie przetwarzają bezpośrednio parametrów zadania, lecz ich zakodowaną postać. Innymi słowy, algorytmy genetyczne nie działają próbując rozwiązać zadanie, lecz próbują, na podstawie zakodowanych rozwiązań, znaleźć to najlepsze.
  2. Algorytmy genetyczne prowadzą poszukiwania, wychodząc nie z pojedynczego punktu, lecz z pewnej ich populacji. Jak zdążyliśmy pewnie zauważyć, działają na populacji rozwiązań, a nie jednym rozwiązaniu, które, np. liniowo, zmieniają.
  3. Algorytmy genetyczne korzystają tylko z funkcji celu, nie zaś z jej pochodnych lub innych pomocniczych informacji. Określenie funkcji celu stoi już po naszej stronie.
  4. Algorytmy genetyczne stosują probabilistyczne, a nie deterministyczne reguły wyboru. Trudno nie przyznać racji, że losowanie odgrywa w tych algorytmach duże znaczenie. Determinizm, czyli określenie końcowego stanu poprzez dane wejściowe nie ma tutaj zastosowania.

Mona Lisa – Leonardo Da Vinci

Obrazu tego nikomu chyba nie trzeba przedstawiać. Namalowany w okresie renesansu do dzisiaj urzeka delikatnym uśmiechem. Osobiście nie przepadam za tym dziełem, aczkolwiek nie sposób go nie doceniać. Gdybyście chcieli zobaczyć, jak z tym obrazem radzi sobie algorytm genetyczny, zerknijcie do Gynvaela o tutaj.

 

A Sylwek z bloga neatcode tak opisuje wstęp do algorytmów genetycznych. Zajrzyjcie do niego, jeśli chcecie zobaczyć przykład już na konkretnej funkcji 🙂

W tym wpisie chciałam pokazać algorytm genetyczny na trywialnym przykładzie, dlatego nie omówiłam kilku ważnych aspektów. Zostaną one szczegółowo opisane w kolejnych wpisach, a ten wpis będzie aktualizowany w odpowiednich miejscach o bezpośrednie linki do nich.

Dajcie znać, czy taka forma jest dla was zrozumiała, szczególnie jeśli, tak jak ja, spotykacie się z algorytmami genetycznymi po raz pierwszy. Jeśli zabrakło wyjaśnienia zastosowań, konkretnych etapów – dajcie znać, na pewno uzupełnię 🙂

Podziel się!

3 komentarze

Odezwij się, będzie mi bardzo miło :)