Prírodou inšpirované algoritmy
študijné materiály pre projekt mobilnej triedy umelej inteligencie
Algoritmy
Fraktály
Jedným zo spôsobov, ako sa jednoduchým spôsobom zostavia komplikované štruktúry, je vytváranie geometrických útvarov iterovaním. Takto vygenerované útvary nazývame fraktály. Ako prvý ich obsiahlo popísal B. Mandelbrot. Ich výpočet (matematická "spätná väzba" (Pickover,1986)) spočíva v skladaní funkcie samej so sebou:
f(x) o f(x) o ... o f(x), čiže: f( f( ... f(x) ... )).
Gaston Julia ako jeden z prvých zistil, že za určitých podmienok takáto iterácia dáva zaujímavé, až prekvapujúce výsledky. Prvou podmienkou je definovať iteračnú funkciu na množine komplexných čísel. Pre každý bod z komplexnej roviny je možné vytvoriť postupnosť čísel
z(0),z(1), z(2), ...; kde z(N) = f( z(N-1) ); N = 1, 2, ...
Táto postupnosť môže buď konvergovať alebo divergovať v závislosti od konkrétneho bodu roviny. Ak oblasti konvergencie a divergencie odlišne zobrazíme, prekvapí nás komplexnosť a krása obrazcov, ktoré získame.
Algoritmus
Jedným zo spôsobov, ako tento výpočet implementovať na počítači, je vziať počiatočnú hodnotu (súradnice bodu z určitého výrezu komplexnej roviny) a vykonávať iteráciu, pokým funkčná hodnota nepresiahne stanovený prah T. Ak hodnota funkcie nevyrastie nad prahovú hodnotu, za určený dostatočne vysoký počet krokov N, postupnosť považujeme za konvergentnú. Bod považujeme za "ohraničený" (bounded (Pickover,1990)) a zobrazíme ho čiernou farbou. V opačnom prípade považujeme postupnosť za divergentnú a bod zobrazíme bielou. "Neohraničeným" bodom však môžeme priradiť aj iné farby - podľa toho, v ktorom kroku funkčná hodnota dosiahla prah.
Keď C. A. Pickover so svojim spolupracovníkom pripravoval program na preskúmanie iteračných metód získali obrázky podivne odlišné od tých, ktoré už boli publikované. Čoskoro zistili, že urobili v algoritme malú chybu, konkrétne v teste konvergencie (ohraničenosti) skúmaného bodu. Iterácia síce skončila, keď absolútna hodnota funkčnej hodnoty prekročila prah. No bod sa vykreslil bielou farbou len vtedy, keď veľkosť jeho reálnej a zároveň imaginárnej zložky presiahla daný prah.
Zápis algoritmu: (podľa (Pickover,1990) a (Pickover ,1987))
for IM = IM0 to IM1 step IM_STEP // imaginárna os
{
for RE = RE0 to RE1 step RE_STEP // reálna os
{
z = complex(RE,IM); // počiatočná hodnota
for K = 1 to N // iteračná slučka (max. N krokov)
{
z = f(z); // iteračná funkcia (napr.: z -> z^2 + u)
if |z| > T then break; // T - prahová hodnota
}
if |Re{z}| < T or |Im{z}| < T // test konvergencie (*)
then point(RE,IM,black); // konvergencia
else point(RE,IM,white); // divergencia
}
}
(*) pre "klasické" fraktály by bol test konvergencie "|z| < T"
Podľa tohoto algoritmu som naprogramoval jednoduchý Java applet (zdrojový kód) a program PBIO v C++ pod MS-DOS-om. Algoritmus vlastne generuje modifikované Juliove množiny (pretože u je konštantou počas výpočtu celého obrázku a počiatočná hodnota premennej z sa pred každou iteráciou nastaví na komplexne vyjadrenú hodnotu súradníc práve skúmaného bodu).
Vďaka spomínanej chybe v algoritme boli vygenerované obrázky zobrazené s množstvom detailov už pri malom počte iterácií N (narozdiel od "klasických" mandelbrotovských fraktálov), vo veľkej miere sa v nich vyskytovali zakrivené trojuholníkové tvary. Ukázalo sa, že ďalšie spestrenie generoaných tvarov prináša použitie ďalších komplexných funkcií, zložitejších, obsahujúcich polynomiálne a transcendentné výrazy.
Príklady iteračných funkcií:
- f: z -> z^2 + u;
- f: z -> z^3 + u;
- f: z -> z^5 + u;
- f: z -> z^z + z^6 + u;
- f: z -> z^2 + sin(z) + u;
- f: z -> sin(z) + exp(z) + u;
u je komplexná konštanta. Jej zmenou sa mení tvar biomorfu. V literatúre (aj v nasledujúcom obrázku) sa používa namiesto písmena u grécke mí, prípadne aj iný znak.
História sa opakuje ...
O pravdivosti tohoto výroku asi nemusím nikoho presviedčať, i keď zároveň platí: "Nevstúpiš dvakrát do tej istej rieky". Mne sa pri tvorbe programu na generovanie biomorfov podarilo históriu zopakovať ... Aj mne sa totiž podarilo urobiť v algoritme chybu. Môj program sa od Pickoverovho odlišoval tiež v teste konvergencie - namiesto logickej spojky OR som do podmienky dal operátor AND.
| Pickoverova podmienka: | if |Re{z}| < T or |Im{z}| < T |
| moja chyba: | if |Re{z}| < T and |Im{z}| < T |
Výsledky programu síce neboli až také prekvapivé ako v prípade pána Pickovera, ale obrazce sa od očakávania odlišovali. Najvýraznejším rozdielom sú oveľa kratšie "brvy". Dá sa tiež pozorovať väčšia detailnosť. Zopár obrázkov, ktoré som vytvoril, je v galérii modifikovaných biomorfov.