Prírodou inšpirované algoritmy

Slovník

Altenbergove pravidlo
je také pravidlo, pre ktoré platí, že výstup bude pri hustote jednotiek na vstupe h nastavený s pravdepodobnosťou h na jednotku. Táto podmnožina pravidiel vytvára zaujímavú, výrazne štruktúrovanú dynamiku siete.

atraktor
z angl. attractor
stavový cyklus, v ktorom sa DDS usadí po konečnom počte krokov. DDS má zvyčajne viacero atraktorov. V ktorom z nich sa napokon usadí, záleží na tom, v oblasti atrakcie ktorého sa nachádza jej počiatočný stav.

celulárny automat (CA)
z angl. cellurar automaton
je DDS s rovnakým pravidlom a štruktúrou prepojení pre všetky prvky.

diskrétna dynamická sieť (DDS)
je diskrétna dynamická sústava, ktorá sa skladá zo vzájomne poprepájaných prvkov, ktoré môžu nadobúdať diskrétne stavy. Stav konkrétneho prvku DDS závisí na stave prvkov, s ktorými je prepojený, podľa pravidla, ktoré musí byť pre každý prvok určené. Stav každého prvku sa nastavuje (paralelne alebo sekvenčne) v diskrétnych časových okamihoch. Dynamika siete spočíva v postupnom prechádzaní rôznymi stavmi. Príkladmi DDS sú ľubovoľné boolovské siete a celulárne automaty.

G-hustota
z angl. Garden-of-Eden states
je hustota rajských stavov, používa sa ako miera konvergencie siete k usporiadanosti alebo chaotickosti.

graf stavových prechodov
prípadne aj graf oblastí atrakcie, oblasti atrakcie, pole oblastí atrakcie
orientovaný graf znázorňujúci časovú náväznosť stavov DDS a ich usporiadanie do oblastí atrakcie. Uzly grafu predstavujú jednotlivé stavy, hrany predstavujú časovú náväznosť.

histogram atraktorov
znázorňuje početnosť rôznych druhov atraktorov nájdených počas dopredného behu z mnohých náhodne generovaných počiatočných stavov.

histogram predchodcov
príp. histogram vstupných stupňov grafu stavových prechodov
zobrazuje početnosť rôznych hodnôt vstupných stupňov grafu stavových prechodov (čo odpovedá počtu predchodcov stavov predstavovaných uzlami grafu).

kanalizujúce vstupy
z angl. canalyzing inputs
vstupy, ktorých určitá hodnota (0 alebo 1) určuje hodnotu výstupu bez ohľadu na hodnoty ostatných vstupov. Zvyšujúci sa počet pravidiel s kanalizujúcimi má za následok usporiadanejšie správanie DDS. Pravidlo obsahujúce kanalizujúce vstupy sa nazýva kanalizujúcim pravidlom.

klzák
je taká postupnosť stavov DDS, ktorá v ich grafickej reprezentácii pri doprednom behu vyvoláva dojem posuvného pohybu obrazcov.
[viď LIFE]

klzákové pravidlo
je také pravidlo DDS, ktoré má za následok častý vznik klzákov v sieti.

ľubovoľná boolovská sieť (RBN)
z angl. random boolean network
je DDS ktorej prvky môžu nadobúdať iba dve diskrétne hodnoty, nastavované podľa pravidiel v tvare boolovských funkcií. RBN môžu mať ľubovoľné prepojenia prvkov a ľubovoľné boolovské pravidlá pre každý prvok.

ľubovoľné zobrazenie (RM)
z angl. random map
je orientovaný graf s výstupnými stupňami prvkov rovnými jednej, predstavujúci úplný zoznam predchodcov. Je dokázané, že ľubovoľné zobrazenie je najvšeobecnejšia diskrétna sústava. RBN sú podmnožinou všetkých ľubovoľných zobrazení.

matica preskokov
alebo aj tabuľka preskokov
je matica pravdepodobností preskokov medzi jednotlivými oblasťami atrakcie siete pri jednobitových poruchách. Alternatívou ku matici preskokov je metagraf atraktorov.

matica stavového priestoru
je diagram rozptylu (scatter plot) stavov v stavovom priestore. Zobrazuje jednotlivé stavy siete na mriežke o rozmeroch 2n/2x 2n/2 v prípade párneho n a 2(n-1)/2x 2(n-1)/2 v prípade nepárneho n, pričom sa kvôli zvyšnému bitu vykreslí ešte jedna matica. Riadky matice predstavujú ľavú polovicu stavu (pri dvojkovej reprezentácii) a stĺpce pravú polovicu. DDLab a mvDDLab sa dajú nastaviť tak, aby v matici stavového priestoru farebne rozlišovali stavy z rôznych oblastí atrakcie, prípadne stavy atraktorov.

metagraf atraktorov
prípadne metagraf oblastí atrakcie
reprezentuje pravdepodobnosti preskokov medzi jednotlivými oblasťami atrakcie pri jednobitových poruchách stavov, poskytuje tým určitý náhľad na stálosť a prispôsobivosť dynamiky siete. Je to graf s váženými vrcholmi a hranami (podľa častosti vstupu do príslušnej oblasti atrakcie), ktorý je grafickou reprezentáciou matice preskokov. Metagraf atraktorov je vhodný pri študovaní modelov pamäte v neurónových sietiach a modelov diferenciácie buniek v genetických sietiach.

okolie
okolie prvku DDS sú prvky prepojené s jeho vstupmi. Od stavu okolia závisí stav prvku v ďalšom časovom okamihu.

oblasť atrakcie
množina všetkých stavov siete, z ktorých sa sieť po určitom počte krokov dostane do toho istého atraktora.

parameter lambda
pomer počtu jednotiek v tabuľke pravidiel k celkovému počtu jej riadkov lambda=c/2k, kde c je počet jednotiek a k je počet susedov prvku. Rovnocenným k parametru lambda je parameter P (P = 1 - lambda).

parameter Z
udáva pravdepodobnosť toho, že nasledujúci bit pri určovaní predchodcov určitého stavu a pri znalostí predchádzajúcich k bitov bude jednoznačne určený. Počíta sa z pravidla ako max {Zzľava,Zsprava}. Veľké hodnoty parametra Z vytvárajú v sieti chaotické správanie, nízke hodnoty Z majú za následok usporiadanosť.
[ viac informácií v (Wuensche, 1999) na strane 9 ]

parameter Zzľava
Zzľava sa počíta z pravidla ako zjednotenie pravdepodobností toho, že pri výpočte predchodcu nejakého stavu za určitých podmienok, bude nasledujúci bit jednoznačne určený. Postupuje sa pri tom zľava do prava, od najvyššieho bitu po najnižší. Pozrite aj parameter Z.
[ viac informácií v (Wuensche, 1999) na strane 9 ]

parameter Zsprava
počíta sa opačným postupom ako parameter Zzľava. Pozrite aj parameter Z.

parameter P
je pomer počtu núl v tabuľke pravidiel k celkovému počtu jej riadkov. P=c/2k, kde c je počet núl a k je počet susedov prvku. Rovnocenným k parametru P je parameter lambda (lambda=1-P)

pomerová lambda
z angl. lambda ratio
je normovaná verzia parametra lambda. Počíta sa ako 2.lambda pre lambda<=0.5 a 2.(1-lambda) pre lambda>0.5.

pravdepodobnostné siete
angl. probabilistic networks
DDS, ktorých stavy sa aktualizujú s určitou pravdepodobnosťou. Klasické DDS odpovedajú pravdepodobnostným sietiam so 100% pravdepodobnosťou aktualizácie.

pravidlo
angl. rule
pravidlom prvku DDS s dvojhodnotovými stavmi prvkov je logická funkcia vstupov tohto prvku daná tabuľkou. Podľa pravidla sa určuje stav daného prvku v nasledujúcom časovom kroku v závislosti od stavov jeho vstupných prvkov.

prepojenia
z angl. wiring
prepojenia prvkov DDS vyjadrujú ich vzájomnú závislosť. Prepojenia sú orientované, môžeme ich teda rozdeliť na vstupné a výstupné. Stav určitého prvku v nasledujúcom okamihu závisí od stavu prvkov, ktoré sú prepojené s jeho vstupmi, v predchádzajúcom okamihu.

priestoročasové obrazce
z angl. space-time patterns
grafické znázornenie stavovDDS v čase.
[viď dopredný beh simulácie]

prvok
je základná zložka DDS. Z oblasti celulárnych automatov je zaužívaný aj názov bunka.

rajský stav
z angl. garden-of-Eden state
je stav bez predchodcov.

reťazcové pravidlo
chaotické pravidlo so Zzľava alebo Zsprava rovným jednej, nie však obomi. Zároveň musia byť obidve Z väčšie ako 0.5. Typickou dynamikou reťazcových pravidiel je veľmi nízka konvergencia, stavy majú zväčša iba jedného predchodcu, čím vytvárajú "reťaz" v grafe stavových prechodov, hustota rajských stavov je nízka.

spätné zobrazenie
v prípade DDLabu ide o dvojrozmerný graf, v ktorom sa na x-ovú os vynáša hodnota stavu siete v kroku t a na y-ovú hodnota v kroku t+1. Hodnota stavu sa normuje z dvojkovej reprezentácie na desiatkové číslo z intervalu <0,2> podľa vzorca B0-B1/2+B2/4+...+Bn/2n-1, kde Bi sú jednotlivé bity stavu siete.

stav siete
stavom DDS rozumieme súbor stavov (hodnôt) jej jednotlivých prvkov.

vstupná entropia
je entrópia distribúcie vstupnej frekvencie. V DDLabe sa zobrazuje ako zvislý graf, buď výsledná entrópia pre všetky kombinácie hodnôt vstupov, alebo zvlášť pre každú kombináciu s farebným rozlíšením.

vstupná frekvencia
je frekvencia (častosť) kombinácií hodnôt vstupných prvkov. V DDLabe je zobrazovaná ako histogram s osobitným prúžkom pre každý prvok.

zamrznutá kostra
angl. frozen skeleton
Ak je časť siete (pri veľkých chaotických sietiach) schopná sa ustáliť, ako napríklad pri modeloch génových regulačných sietí, môžeme určiť iný druh akéhosi kvázi atraktora, ktorý sa nazýva zamrznutá kostra. Je treba určiť časť siete, ktorá sa má ustáliť alebo zamrznúť (nezmeniť sa počas daného počtu časových krokov) a keď sa dosiahne tento stav, príslušná časť obrazcov (stavov) sa definuje ako druh kostry.