Algorytm Genetyczny

Tekst o użyciu algorytmu genetycznego w prostej aplikacji przybliżania zdjęć przez prymitywy (tu — kółka). Algorytm jest szerszy i ciekawszy, moze być stosowany w różnych kontekstach włączając w to symulacje fizyczne, animację i grafikę komputerową. Ten tekst to taka zajawka, mam nadzieję że się komuś przyda, bomateriałów po polsku jest jak na lekarstwo..

Nagrałem właśnie krótki vlog na temat tego algorytmu, zapraszam na mój youtube.

Rozwiązanie problemu z użyciem algorytmów genetycznych wymaga trzech rzeczy:

• zakodowania cech naszego układu (obiektu) w postaci łańcucha znaków lub symboli (genom) tak, aby z niego można było wygenerować rozwiązanie (osobnik)
• rozwiązanie może być wtedy mutowane przez zmianę symboli w tym łańcuchu znaków (genomie) w sposób losowy
• na koniec potrzebujemy wymyślić sposób na pomiar tzw. fitness, czyli miary określającej jak blisko jesteśmy naszego rozwiązania (osobnika) poprawnego

W skrócie — algorytm genetyczny polega na minimalizacji miary fitness z użyciem mutacji genomu naszego osobnika. Osobnikiem może być zwierzę, człowiek, wirus (?) — to w biologii, ale też… rysunek, animacja, obiekt fizyczny (i to interesuje nas tutaj). Brzmi może trochę zawile, ale w istocie jest to algorytm bardzo prosty. Poszczególne kroki algorytmu (źródło [1]):

1. Wygeneruj genom pierwszego osobnika — matki
2. Zmierz fitness matki
3. Wykonaj losową mutację genomu
4. Wygeneruj nowego osobnika (dziecko) i zmierz fitness dziecka
5. Jeśli fitness dziecka jest większy od fitnessu matki — przepisz genom dziecka do genomu matki
6. Idź do kroku 3.

Studium przypadku, czyli konkrety

Jako przykład praktyczny na tapetę wziąłem słynne zdjęcie A. Einsteina. Poniżej kilka klatek z przybliżeń, które wykonałem dla N=200 kółek. Przybliżenie jest niezłe chociaż mogłoby być lepsze. Można to jeszcze bardzo poprawić np. wybierając inne typy mutacji i być może dodając jakiś mechanizm rekombinacji, ale tutaj zastosowałem najprostsze podejście.

(Proponuję przewijać w dół używając PageDown, wygląda jak animacja.)

Oryginalne zdjęcie

Pierwszy osobnik- na podstawie losowego genotypu.

498

746

iteracja 1104

iteracja 1483

iteracja 1814

2203

iteracja 2682

3194

iteracja 3823

4436

iteracja 5123

5974

6893

7995

9030

10119

11221

12758

14449

16255

18091

20650

23528

26293

28744

32393

35662

39595

43238

46777

Obraz po ok. 64tys. mutacji pojedynczych genów.

Pełne przybliżenie na filmie poniżej

Dokładność można oczywiście doprowadzić do perfekcji na przykład dodając więcej kółek, kontynuując przybliżenie dłużej, dodając więcej trybów mutacji. Część z tych rzeczy może, ale nie musi być wcale zbieżna z tym co się dzieje w naturze. Przecież mamy do czynienia z algorytmem genetycznym, więc siłą rzeczy naturalne staje się, aby zmodyfikować też sam algorytm :)

Zapraszam do obejrzenia materiału video na ww temat [2].

Literatura:
[1] http://www.petercollingridge.co.uk/evolving-images

[2] Algorytm genetyczny (film), https://youtu.be/VDLeY58jEno

Strona domowa: http://panoramix.ift.uni.wroc.pl/~maq/
Praca: http://www.ift.uni.wroc.pl/~maq/

Youtube kodera: https://www.youtube.com/c/KodernaStrychu/
YouTube: https://www.youtube.com/user/maqflp
FB: https://www.facebook.com/ComputerSimulations/
Twitter: https://twitter.com/maqpl