Załóżmy, że mamy dany obraz wejściowy i chcemy wygenerować obraz jak najbardziej do niego podobny składający się z zadanej liczby elementów o określonym kształcie. Do rozwiązania tego problemu posłużymy się algorytmem genetycznym. Na początek przyjrzymy się wersji, w której elementy składowe są trójkątami. A więc do roboty...

Obraz wejściowy oznaczymy jako O_org
Obraz wyjściowy ma taki sam rozmiar jak obraz wejściowy i opisany jest przez n elementów składowych element₁, element₂, ... element_n. Z kolei każdy element opisany jest przez jego kształt i kolor. Dla trójkąta będą to trzy współrzędne jego wierzchołków oraz kolor.
W algorytmach genetycznych posługujemy się pokoleniami. W każdym pokoleniu znajduje się grupa p osobników (populacja). W przypadku naszego problemu osobnikami będą obrazy wyjściowe. Zatem pokolenie t zdefiniowane jest przez zbiór obrazów wyjściowych O₁^t, O₂^t, ..., O_p^t

W naszym zadaniu chodzi o wygenerowanie obrazu jak najbardziej podobnego do oryginału. Musimy więc wprowadzić funkcję, która oceni stopień podobieństwa pomiędzy obrazem oryginalnym a obrazem wyjściowym. Wynik będzie tym lepszy im wyższa wartość tej funkcji. A więc żeby ocenić jak bardzo obraz wyjściowy jest podobny do oryginału musimy narysować wszystkie jego elementy składowe, a następnie każdy punkt wygenerowanego obrazu porównać z punktem obrazu oryginalnego. Każdy punkt naszych obrazów opisany jest przez trzy składowe r, g, b odpowiadające trzem kolorom podstawowym - czerwony (red), zielony (green), niebieski (blue). Różnicę pomiędzy punktem obrazu oryginalnego Porg a punktem obrazu wyjściowego Pwyj zdefiniujemy jako:

\sqrt{(Porg_{r}-Pwyj_{r})^{2} + (Porg_{g}-Pwyj_{g})^{2} + (Porg_{b}-Pwyj_{b})^{2}}

Niech suma różnic wszystkich punktów składających się na obraz wynosi d. Wówczas stopień podobieństwa zdefiniujemy jako: (d_max - d) / d_max, gdzie:
d_max jest maksymalną różnicą pomiędzy obrazami zdefniowaną jako (zakładamy, że składowe kolorów mają wartości od 0 do 255):

wysokoscObrazu * szerokoscObrazu * \sqrt{255^{2}*3}

Mamy zatem zdefiniowaną funkcję dzięki, której możemy ocenić każdy osobnik (obraz) w populacji. Jak wspomniałem wcześniej pokolenie składa się z p osobników, ale kandydatami do następnego pokolenia jest tylko e osobników (e < p) o największej wartości funkcji podobieństwa (elita). Pozostałe osobniki odrzucane są przez ewolucję jako "nieprzystosowane".

Najlepsze osobniki (obrazy), krzyżują się ze sobą tworząc nowe pokolenie. Proces krzyżowania polega na wzięciu dwóch osobników (hipotetycznego "ojca" i "matki") i wyprodukowaniu na ich podstawie potomka. W naszym przypadku proces ten będzie przebiegał następująco:
Wylosuj liczbę od 0 do 1, jeżeli wylosowana liczba jest mniejsza od 0.5 weź element₁ z "ojca" w przeciwnym wypadku weź go z "matki".
Wylosuj liczbę od 0 do 1, jeżeli wylosowana liczba jest mniejsza od 0.5 weź element₂ z "ojca" w przeciwnym wypadku weź go z "matki".
...
Wylosuj liczbę od 0 do 1, jeżeli wylosowana liczba jest mniejsza od 0.5 weź element_n z "ojca" w przeciwnym wypadku weź go z "matki".

Dodatkowo w trakcie procesu kopiowania elementów z rodziców, z pewnym zadanym prawdopodobieństwem m może nastąpić mutacja. A więc podczas kopiowania elementu z jednego z rodziców losuję się liczbę od 0 do 1. Jeżeli jest ona mniejsza od m wówczas element zostaje skopiowany bez wprowadzania żadnych zmian, w przeciwnym razie element zostaje skopiowany ale jego parametry zostają zmienione o jakąś losową wartość. W przypadku trójkątów mutacja polega na zmianie jednego z trzech wierzchołków bądź koloru (założyłem też że wartość zmiany ma rozkład Gaussa).

Tak więc mamy już omówione wszystkie składowe potrzebne do uruchomienia algorytmu genetycznego generującego obraz z trójkątów. Pozostaje tylko kwestia wartości początkowej. Ja założyłem, że początkowa wartość obrazów to losowe rozłożone elementy o niewielkich rozmiarach (długość boku trójkąta nie przekracza dwóch punktów) i losowym kolorze.

Tak więc algorytm przebiega następująco:
Pokolenie pierwsze t = 1
Utwórz zbiór p obrazów składających się z losowo ułożonych elementów. Te obrazy to: O₁¹, O₂¹, ..., O_p¹.
Oceń podobieństwo każdego z tych obrazów, do obrazu O_org.
Wybierz e najlepszych obrazów. Krzyżuj obrazy z elity uzyskując nowe pokolenie t = 2. Ja krzyżuje obraz 1 z 2, 1 z 3, 1, z 4, ... 1 z e, 2 z 1, 2, z 3, 2 z 4, ..., 2 z e, tak długo aż uzyskam p nowych obrazów.
Nowe obrazy po krzyżowaniu to: O₁², O₂², ..., O_p².
Oceń podobieństwo każdego z tych obrazów, do obrazu O_org.
Wybierz e najlepszych obrazów. Krzyżuj obrazy z elity uzyskując nowe pokolenie t = 3.
...

Poniżej wynik generowania przykładowego rozwiązania. Początkowo prawdopodobieństwo mutacji elementu wynosiło 0.1, po pokoleniu 350-tym zostało zmniejszone do 0.05, po 700-tym do 0.02, po 1000-ym do 0.01. Większe prawdopodobieństwo i wielkość mutacji z początku przyśpiesza poprawianie wartości podobieństwa w kolejnych pokoleniach, ale po dojściu do pewnej wartości zaczyna je hamować - kolejne pokolenia są tak samo podobne bądź nawet gorsze od poprzednich. Należy wówczas zmniejszyć prawdopodobieństwo i wielkość mutacji tak by pomagała a nie przeszkadzała w dochodzeniu do optymalnego rozwiązania. Obraz oryginalny:

pokolenie 5 czas generowania ~5 sekund podobieństwo ~44%	pokolenie 100 czas generowania ~2 minuty podobieństwo ~73%	pokolenie 250 czas generowania ~3 minuty podobieństwo ~88%
pokolenie 350 czas generowania ~4 minuty podobieństwo ~90%	pokolenie 1000 czas generowania ~15 minut podobieństwo ~93%	pokolenie 6000 czas generowania ~1.5 godziny podobieństwo ~94.5%

Utworzyłem również wersję, w której elementami składowymi są koła - opisane przez współrzędne środka, promień oraz kolor.


Ustaw ścieżkę do pliku (lub pozostaw tą domyślną), wczytaj plik a następnie użyj przycisku "Start" w celu sprawdzenia działania metody.
Ze względu na zabezpieczenia w przeglądarkach, skrypt otwiera wyłącznie pliki graficzne w obrębie naszego serwisu, np:
http://www.algorytm.org/images/stories/po/anaglif_lewy.jpg
http://www.algorytm.org/images/stories/po/orig.gif
http://www.algorytm.org/images/stories/mb/hsv.jpg

Plik:
Liczebność populacji:
Liczebność elity:
Liczba elementów:
Rodzaj elementów:	tójkąty koła
Prawdopodobieństwo mutacji elementu:
Wielkość mutacji (1-100):

Oryginał	Najlepszy	Bieżący