Prírodou inšpirované algoritmy

Global-to-local

Metóda deformačných jadier (Deformation–kernel method)

Účinok jednej rastliny v samo–prerieďovacej metóde na pravdepodobnosť nájdenia ďalšej rastliny v susedstve je znázornený diagramom na obrázku.

Účinok rastliny na pravdepodobnosť nájdenia ďalšej rastliny v susedstve.

V okruhu rastliny o polomeru rt je pravdepodobnosť nájdenia ďalšej rastliny veľmi malá. V oblasti mimo okruhu nie je pravdepodobnosť ovplyvnená jej účinkom.

Funkcia K, znázornená na obrázku hore, je príkladom deformačných jadier. Ak predpokladáme, že tam je pole hodnôt, ktoré charakterizuje pravdepodobnosť umiestnenia novej rastliny na rôznych miestach v tomto poli. Odlišné pôsobenia medzi rastlinami môžu byť opísané použitím deformačných jadier rôznych tvarov, ako je naznačené na obrázku. Kde a) je jadro nemajúce efekt na susednú rastlinu, b) jadro majúce propagačný efekt, c) jadro majúce inhibičný efekt a d) jadro majúce inhibičný efekt krátkeho dosahu a propagačný efekt dlhého dosahu.

Príklady deformačných jadier

Vďaka použitiu metódy deformačných jadier môžeme teraz vyvinúť jednoduchý algoritmus umiestňovania rastlín. Definujeme spojitú funkciu hustoty pravdepodobnosti (joint probability density function) f(x,y), ktorá charakterizuje pravdepodobnosť f(x,y)dxdy umiestňovania nových rastlín do oblasti dxdy so stredom v bode (x,y). Rastliny sú umiestňované po jednej, pretože každá umiestnená rastlina svojím deformačným jadrom upraví pravdepodobnostnú funkciu f, ktorá sa použije na určenie pozície ďalšej rastliny.

Formálne spojitá funkcia hustoty definuje pravdepodobnostné pole, kde pravdepodobnosť novej rastliny rastúcej v štvoruholníku [0,xs]x[0,ys], a platí a , je daná rastúcou pravdepodobnostnou funkciou rozdelenia

Samozrejme pravdepodobnosť, že sa rastlina nájde v poli je rovná jednej, preto funkcia hustoty musí spĺňať normalizačnú rovnicu

Polohu rastliny (xt,yt) vypočítame z normalizačnej rovnice dosadením najprv prvej súradnice y a potom prvej súradnice x. Dostaneme dvojrozmernú funkciu hustoty f(x,y), z ktorej vypočítame marginálnu funkciu rozdelenia FY(ys). Táto distribučná funkcia popisuje pravdepodobnosť, pre ktorú platí yt≤ ys nezávisle od výberu hodnoty xt:

Potom aplikujeme inverznú transformáciu na FX ‌ Y(xs ‌ yt) , z ktorej dostaneme hodnotu xt.

Umiestnením rastliny s veľkosťou rt na pozíciu (xt,yt) deformujeme pravdepodobnostnú funkciu hustoty f(x,y), aby sme mohli simulovať pôsobenie rastliny na umiestnenie susedných rastlín. Urobí sa to tak, že sa najprv vynásobí pravdepodobnostná funkcia hustoty f(x,y) s deformation–kernel K(x,y),

a potom funkciu ftemp(x,y) znormalizujeme, aby vyhovovala rovnici (1). Deformačné jadro je typicky funkcia tvaru

kde funkcia κ(r) meria účinok, aký má jediná rastlina na vytváranie rastlín vo vzdialenosti r od nej.

Lepšia cesta, ako to pochopiť, je reprezentovať hodnoty pravdepodobnostnej funkcie f(x,y) poľom rozmeru nxn položiek fij. Potom na výpočet pozície novej rastliny vytvoríme vektor R parciálnych súčtov riadkov, kde

Súradnicu yt nedávno umiestnenej rastliny určíme použitím metódy inverznej transformácie: vyberieme náhodné číslo u z rovnomerného rozdelenia na intervale [0,Rn-1], potom binárnym vyhľadávaním nájdeme hodnotu Ri, takú že Ri≤u≤Ri+1 . Tak lineárne interpolujeme na intervale (i,Ri) až (i+1,Ri+1) a nájdeme (yt,u).

Teraz vektor C , ktorého hodnoty predstavuje podmienené rozdelenie FX ‌ Y(xs ‌ yt) , vypočítame interpolovaním riadkov i a i+1 poľa fij.

Stanovené hodnoty Ck, pre k=0, 1, ..., n-1, vyberieme hodnotu z rovnomerného náhodného rozdelenia na intervale [0,Cn-1] a nájdeme xt použitím metódy inverznej transformácie.

Jadro je aplikované jednoduchým vypočítaním vzdialenosti d od každého bodu (i,j) od (xt, yt), potom vynásobením hodnoty fij distribučnej funkcie f v tomto bode funkciou .

Ak umiestnime m rastlín a funkcia f je reprezentovaná n2 hodnotami fij, potom vyššie uvedený algoritmus bude potrebovať O(mn2) času na spustenie, pretože pri umiestnení novej rastliny sa musí vždy prepočítať Rk. Keď je v rozdelení použité jadro, rozdiely medzi fij a sú sčítané pre každé (i,j) v rámci dosahu rastliny a rozdiely sú aplikované v poli R. Za predpokladu, že jadro je aplikované iba na malé zlomky buniek v mriežke, tak táto operácia môže byť vykonaná za čas O(n) na jednu rastlinu.

Pôsobenie metódy jadier je ilustrované na obrázku. Je tam použité deformačné jadro d) z ďalšieho obrázku. Počiatočné rozdelenie je rovnomerné, t.j. f(x,y)=c. Na obrázku v prostriedku bola do poľa pridaná jedna rastlina, funkcia hustoty bola zmenená u rastlín v susedstve. Na obrázku dole boli pridané ďalšie štyri rastliny, funkcia hustoty bola zmenená blízko každej z nich. Vľavo: rozdelenie rastlín. Vpravo: s použitím pravdepodobnostnej funkcii hustoty f. Zhora nadol: počiatočný stav, stav po umiestnení jednej rastliny a stav po umiestnení štyroch ďalších rastlín.

Príklad algoritmu deformačných jadier.

Obrázok dole ukazuje bodové šablóny, vygenerované použitím tohto algoritmu pri rôznych deformačných jadrách.Jadrá sú nakreslené vo väčšej mierke ako bodové šablóny. Hopkinsové indexy týchto šablón sú 0.4, 1.0, 1.2 a 2.4, potvrdzujúce vizuálne pozorovania, že metóda deformačných jadier je schopná tvorby dosahu pre rozdelenia (od rozhádzaných k náhodným a zoskupeným do chumáčov).

Príklady deformačných jadier a bodových šablón, ktoré generujú.

Na obrázku dole boli body nahradené jednoduchými modelmi sedmokrások, vytvorené použitím L–systému. Rozhádzaný model na vrchu obrázku vyzerá menej realisticky ako model nižšie, kde sa sedmokrásky zlučujú do chumáčov.

Bodové šablóny odpovedajúce k predchádzajucému obrázku , prevedené ako pole sedmokrások.

Rozdelenia zobrazené na predchádzajucom obrázku boli generované pri konštantnej pravdepodobnostnej funkcii hustoty f . Ak namiesto toho použijeme užívateľom definovanú funkciu f (napríklad vytvoríme ju v nejakom kresliacom programe), môžeme generovať priestorové rozdelenie rastlín, ktoré odpovedá tomuto poľu, ako je znázornené na spodnom obrázku . Hodnoty Hopkins–ových indexov sú H ≈ 1.2 (vľavo) a H ≈ 1.9 (vpravo).

Distribúcia rastlín vytvorená z užívateľom definovanej mapy hustoty, znázornenej hore v obrázku.