Życie w RAM-ie

Termin 'algorytmy genetyczne' oznacza fascynujące zastosowanie technik programistycznych, których podstawą są procesy podpatrzone w świecie form żywych. Algorytmy genetyczne dają nadzieję na efektywne rozwiązywanie problemów, których na razie nie potrafimy rozwiązać.

Ewolucja form żywych jest nieprawdopodobnie złożonym procesem, przebiegającym według trzech prostych reguł. Spróbujmy je od razu wyartykułować, używając niejasnego pojęcia "stworek", które za chwilę zdefiniujemy ściślej:

1. Wszystkie stworki zmieniają się przypadkowo (jest to proces mutacji).

2. Wszystkie stworki podlegają presji otoczenia, w wyniku czego możemy wskazać najlepiej i najgorzej przystosowane (jest to proces oceny).

3. Stworki najlepiej przystosowane przekazują swoje cechy następnym stworkom, które w populacji zajmują miejsce najgorzej przystosowanych (jest to proces narodzin i śmierci).

W tym schemacie ewolucyjnej trójcy mutacja - ocena - rozmnażanie ukrytych jest wiele subtelnych szczegółów. Przede wszystkim jest tutaj mowa o konkurencji, czyli stworków musi być dużo, nie jeden. Ponadto stworki rodzą się i umierają, zatem mamy ciągłą wymianę poszczególnych egzemplarzy - jedne giną, ale na ich miejsce wchodzą inne. Ponadto mutacja - ta bezlitosna, ślepa i nieukierunkowana zmienność - jest procesem, w którym najczęściej ustrój stworka zostaje uszkodzony, ale niekiedy może pojawić się nowa jakość, nowe przystosowanie, nowa bezcenna cecha.

Mechanizm ten to właśnie metoda prób i błędów, ale z utrwalaniem rozwiązań dobrych i z eliminowaniem błędów. Daje on nadzieję znalezienia rozwiązań w tych dziedzinach, w których nie potrafimy znaleźć ich inaczej.

Naszym celem będzie zbudowanie małego świata dla cyfrowych stworków i zaimplementowanie trzech powyższych mechanizmów, warunkujących ich rozwój i doskonalenie. Stworki już mamy w swojej programistycznej szufladzie - będą to grafiki, generowane przekształceniami afinicznymi. Na początek zajmijmy się stworkiem, którym jest opracowany miesiąc temu trójkąt Sierpińskiego (porównaj rysunek 1).

Zapewne jeszcze pamiętacie, że najważniejszym elementem dywanu afinicznego jest długa pętla, przesuwająca współrzędne punktu za pomocą zestawu przekształceń liniowych. Bieżące, akurat aktywne przekształcenie było po prostu losowane. Losowanie powinno być niesprawiedliwe, czyli niektóre przekształcenia powinny wchodzić do gry częściej niż inne, jeśli chcemy otrzymać grafikę równomiernie nasyconą. O niesprawiedliwości losowania decyduje dodatkowa tablica wag.

Nie będziemy ponownie analizować różnych subtelności dywanów afinicznych - zainteresowanych czytelników odsyłamy do poprzedniego numeru PCWK - i od razu wplećmy tamte algorytmy w obecnie rozważane zagadnienie.

Każdy konkretny dywan afiniczny będziemy nazywać stworkiem, a zestaw jego parametrów zapiszemy w formie łańcucha genetycznego, to znaczy tablicy parametrów. Nie ma powodu, aby nie wykorzystać do tego zwyczajnego mechanizmu tablic, ale postarajmy się to zrobić porządniej, wprowadzając do gry rekordy, struktury, klasy - zależnie od języka, w którym pracujemy.

Afiniczny stworek musi zawierać informację o tym, z ilu przekształceń się składa (na przykład trójkąt Sierpińskiego składa się z trzech przekształceń). Ponadto każde z tych przekształceń składa się z sześciu parametrów (poprzednio była to tablica M i dwa parametry T). Stworek powinien też mieć tablicę wag, określającą, jak istotne jest każde z przekształceń.

Oto proponowany genotyp stworka, wyartykułowany jako rekord w języku C:

const int MAX_IL_PRZEKSZT = 10;

struct Stworek

{

int il_przekszt;

double G[ MAX_IL_PRZEKSZT][ 6];

int P[ MAX_IL_PRZEKSZT];

};

Genotyp stworka otwiera parametr il_przekszt, który informuje o liczbie wykorzystywanych przekształceń z dziesięciu możliwych w tym przykładzie. Tablica G przechowuje zestawy sześciu współczynników przekształceń, tablica P - ich wagi do niesprawiedliwego losowania bieżącego przekształcenia. Oczywiście il_przekszt zawsze musi być mniejsze od MAX_IL_PRZEKSZT lub mu równe. Tak zadeklarowanego stworka musimy utworzyć i zainicjować - np. wartościami prowadzącymi do grafiki zwanej trójkątem Sierpińskiego:

Stworek S; //tak nazwijmy stworka...

S.il_przekszt = 3; //trójkąt Sierpińskiego

S.G[ 0][ 0] = 0.5;

S.G[ 0][ 1] = 0.0;

S.G[ 0][ 2] = 0.0;

S.G[ 0][ 3] = 0.5;

S.G[ 0][ 4] = 0.0;

S.G[ 0][ 5] = 0.0;

S.P[ 0] = 33;

S.G[ 1][ 0] = 0.5;

S.G[ 1][ 1] = 0.0;

S.G[ 1][ 2] = 0.0;

S.G[ 1][ 3] = 0.5;

S.G[ 1][ 4] = 2.0;

S.G[ 1][ 5] = 0.0;

S.P[ 1] = 33;

S.G[ 2][ 0] = 0.5;

S.G[ 2][ 1] = 0.0;

S.G[ 2][ 2] = 0.0;

S.G[ 2][ 3] = 0.5;

S.G[ 2][ 4] = 1.0;

S.G[ 2][ 5] = 1.73;

S.P[ 2] = 33;

Algorytm wykreślania tego pojedynczego afinicznego stworka w nowym, "genetycznym" zapisie powinien wyglądać mniej więcej tak:

x = y = 0.0; //początkowa pozycja punktu

for( i = 0; i < 1000000; ++i)

{

nr = losuj_niesprawiedliwie(S.P,S.il_przekszt);

xx = S.G[nr][0]*x +S.G[nr][1]*y +S.G[nr][4];

y = S.G[nr][2]*x +S.G[nr][3]*y +S.G[nr][5];

x = xx;

putpixel( x, y, BLUE);

}

W powyższym algorytmie realizujemy obraz stworka za pomocą znanej konstrukcji z długotrwałym iterowaniem położenia punktu. Algorytm ten zaczerpnęliśmy z programu przygotowanego przed miesiącem.