Sztuczny malarz fraktalowy

Program realizuje podejście nazywane ewolucją kierowaną przez człowieka. To użytkownik prowadzi proces ewolucji obrazów wywierając presję selekcyjną.

Wybierz język programu:

Założenia

Program generuje pewną liczbę losowych obrazów-fraktali. Głównym założeniem jest interakcja użytkownika z programem. Użytkownik poprzez kliknięcie myszką wybiera jego zdaniem najbardziej interesujący obraz. Następnie program generuje nową serię obrazów z wykorzystaniem algorytmu ewolucyjnego. Liczba wymienionych wyżej kroków może być nieograniczona, przy czym przy dobraniu odpowiednich parametrów algorytm jest zbieżny i prędzej lub później generuje serię identycznych najbardziej preferowanych przez użytkownika obrazów. Algorytm ewolucyjny działa w oparciu o prostą zasadę: każdy obraz jest pojedynczym osobnikiem w populacji i ulega prostej operacji krzyżowania z innymi osobnikami oraz opcjonalnej mutacji. W kolejnej generowanej populacji pozostają tylko te obrazy, które są najbardziej podobne do tego zaznaczonego przez użytkownika.

Program

Po uruchomieniu programu użytkownik może zmienić wartości domyślne parametrów (liczba krzyżowań przypadająca na jednego osobnika oraz prawdopodobieństwo mutacji pojedynczego genu potomka). Można także wybrać rozmiar generowanych obrazów, który będzie niezmienny w kolejnych iteracjach. Przycisk „Start” służy to wygenerowania losowej populacji obrazów o wybranym wcześniej rozmiarze. Od tego momentu użytkownik może wybierać interesujące go obrazy w kolejnych seriach poprzez kliknięcia na nich myszką. Podczas wybierania można na bieżąco modyfikować parametry (liczba krzyżowań przypadająca na jednego osobnika oraz prawdopodobieństwo mutacji pojedynczego genu potomka). Kliknięcie prawym przyciskiem myszki otwiera duży obraz wskazanego fraktala.

Fraktale

Wykorzystano gotowy algorytm generowania fraktali autorstwa Rogera T. Stevensa. Algorytm jako dane wejściowe przyjmuje definicję fraktala w postaci ciągu siedmioelementowych wektorów. Algorytm bazuje na generowaniu iteracyjnych (dla kolejnych n) funkcji postaci:

X(n+1) = AiXn + Bi Yn + Ei
Y(n+1) = Ci Xn + Di Yn + Fi

gdzie [Ai, Bi, Ci, Di, Ei, Fi, Pi] jest i-tym wektorem z ciągu wejściowego, a Pi prawdopodobieństwem wykorzystywanym przy obliczeniach. Przykładowe fraktale to:

trójkąt Sierpińskiego
0,5; 0,0; 0,0; 0,5; 0,0; 0,0; 0,3333;
0,5; 0,0; 0,0; 0,5; 1,0; 0,0; 0,3333;
0,5; 0,0; 0,0; 0,5; 0,5; 0,5; 0,3333;
liść
0,0; 0,0; 0,0; 0,16; 0,0; 0,0; 0,05;
0,2; -0,26; 0,23; 0,22; 0,0; 0,2; 0,15;
-0,15; 0,28; 0,26; 0,24; 0,0; 0,2; 0,14;
0,85; 0,04; -0,04; 0,85; 0,0; 0,2; 0,4;

Przyjęto założenie, że w programie będzie dla uproszczenia stała liczba wektorów wynosząca 4. Daje to zbiór 28 liczb opisujących pojedynczy obraz. Owe 28 liczb stanowi chromosom osobnika w algorytmie ewolucyjnym.

Algorytm ewolucyjny

28 liczb będących parametrami fraktala stanowi jego opis (chromosom). Pojedyncza liczba w chromosomie stanowi gen. Przy tych założeniach algorytm jest następujący:

Wygeneruj losową populację o rozmiarze X taką, że pojedynczy gen przybiera losową wartość w zakresie [-1; 1) za wyjątkiem Pi, które przybiera wartość [0; 1)
Zapamiętaj zaznaczony przez użytkownika obraz.
Generuj nową populację:
- dla każdego osobnika z populacji kilkukrotnie (liczba krzyżowań jest określona jako parametr definiowany przez użytkownika) dokonaj operacji krzyżowania z dowolnym osobnikiem za wyjątkiem jego samego. Operacja krzyżowania polega na rozcięciu chromosomów rodziców w tym samym losowym miejscu i sklejeniu jednaj części jednego rodzica z drugą częścią drugiego rodzica. Wynikiem tej operacji jest jeden potomek Zapamiętaj potomków na osobnej liście.
- dla każdego potomka, dla każdego jego genu dokonaj mutacji polegającej na losowym generowaniu nowego genu (zgodnie z zasadami z p. 1) i zastąpieniu starego z założonym przez użytkownika prawdopodobieństwem.
- dla każdego potomka oblicz odległość między nim a obrazem ostatnio wybranym przez użytkownika. Obliczenie odległości między chromosomami jest dla uproszczenia oparte jest o miarę L₁ (miara Manhattan, czyli suma wartości bezwzględnych różnic).
- usuń z populacji wszystkie stare chromosomy. Dodaj do niej obraz wybrany przez użytkownika oraz X-1 potomków o odległości najbardziej zbliżonej do wybranego.
Wyświetl na ekranie nową populację o rozmiarze X.
Wróć do punktu 2.

Spostrzeżenia i wnioski

W świecie rzeczywistym każda populacja składa się w większości przypadków z osobników przeciętnych, niczym niewyróżniających się z otoczenia. Jednakże w każdej populacji zdarzają się osobniki wyjątkowe, mające pewne szczególne cechy. W przypadku ludzi są to ludzie bardzo inteligentni, silni lub atrakcyjni w jakikolwiek inny sposób. Podobna sytuacja ma miejsce w przypadku fraktali. Obrazy o przypadkowych genotypach są przeciętne i mało atrakcyjne. Jednakże wiadomo, że istnieją fraktale o pewnych parametrach, które są nadzwyczaj ładne. Przykładem mogą być obrazy przedstawiające liście, struktury drzewiaste lub ciekawe spirale.

Program generuje na początku przypadkowe obrazy. Jeżeli użytkownik będzie starannie dobierał kolejne obrazy jako wzorce, to końcowa populacja może zawierać całkiem interesujące fraktale. Jednakże może się okazać, że algorytm osiągnie zbieżność do mało ciekawego obrazka (odpowiednik lokalnego optimum). Wówczas z pomocą może przyjść możliwość zmiany parametrów generacji.

Większa liczba krzyżowań (5 i więcej) przypadająca na jednego osobnika powoduje powstanie dużej liczby potomków, z których tylko najbardziej podobne znajdują się w kolejnej populacji. W tym przypadku jest większe prawdopodobieństwo trafienia do nowej populacji obiektów bardzo podobnych do wzorca i algorytm szybko osiąga zbieżność. I odwrotnie: dla małej wartości (3 i mniej) tego parametru algorytm już nie ma takiego szerokiego wyboru wśród nowego potomstwa i do nowej populacji trafiają także osobniki, które nie mają zbyt wiele wspólnego z obrazem wzorcowym.

Aby zapobiec wpadaniu w „optimum lokalne” (zbieżność wokół mało ciekawego obrazu) można wykorzystać opcję mutacji. Duża wartość prawdopodobieństwa (10% i więcej) zmutowania pojedynczego genu każdego potomka powoduje duże zróżnicowanie osobników w nowej populacji (są oni często niepodobni do rodziców) i nie prowadzi do zbieżności. Z kolei małe lub zerowe prawdopodobieństwo mutacji gwarantuje zbieżność dzięki stosunkowo dużemu podobieństwu potomków do rodziców.

Wydaje się, że dobrymi wartościami parametrów są: liczba krzyżowań równa 3 i prawdopodobieństwo mutacji równe od 1 do 3 dla rozmiaru populacji 16 obrazów. Dzięki temu algorytm gwarantuje pewną zbieżność wokół wybieranych przez użytkownika obrazów oraz możliwość wyjścia z lokalnego optimum i szukanie ciekawszych fraktali. Niezależnie od tego można zawsze modyfikować parametry na bieżąco według własnych upodobań. Wybranie np. prawdopodobieństwa mutacji równego 100% spowoduje otrzymanie w następnej populacji zbioru całkowicie losowych (niezależnych od poprzednich) obrazów.

Ciekawym spostrzeżeniem jest to, że krzyżówki różnych obrazów są czasem niepodobne do rodziców. Taki potomek wygląda często jak jeden z rodziców o bardzo zaburzonej, dziwnej strukturze.