Prírodou inšpirované algoritmy

Multi-úrovňové L-systémy

Modelom L–systém generujeme rastliny reprezentované reťazcami symbolov s voliteľnými parametrami. Tieto reťazce definujú topológiu a geometriu(tvar) výsledných štruktúr. Špecifikácia L–systémom sa skladá z troch častí: abeceda, t.j. sada symbolov, ktorá reprezentuje jednotlivé časti rastlín. Ďalšou zložkou L–systému je axióm reprezentujúci počiatočný stav a posledná zložka je množina pravidiel, ktorá definuje rozvoj častí rastlín po krokoch v čase (napr. rast, vetvenie, tvorba listov atď.). Abeceda môže byť definovaná aj implicitne ako množina znakov, ktoré sa prejavujú v pravidlách(každý symbol je reprezentovaný pravidlom). Vývoj rastliny je simulovaný v derivačných krokoch (tzv. derivation steps). V každom kroku, každý symbol je prepísaný novým nasledujúcim symbolom prislúchajúci pravidlu, alebo je prepísaný sám sebou ak nenastalo pravidlo. Pseudo–L–systém je rozšírenie L–systému a umožňuje prepísať dva alebo viac symbolov využitím jedného pravidla. Ďalším rozšírením systému je otvorený L–systém(open L–system), umožňujúci vyjadrenia vzájomného pôsobenia rastlín a pôsobenia s ich prostredím.

Multi–úrovňové L–systémy zjednocujú a rozširujú skôr definované notácie teórie L–systémov o vetviace štruktúry: t.j. o vývojové systémy s konečným súborom axióm a L–systémy s fragmentáciou. V multi–úrovňových L–systémoch množina pravidiel pracuje nad multi–množinou reťazcov, ktorá predstavuje mnoho rastlín, a nie nad jedným reťazcom t.j. nad jednou rastlinou. Nový reťazec môže byť dynamicky pridaný alebo odstránený z multi–množiny, reprezentujúcej organizmy, ktoré sú pridané alebo odstránené z populácie.

Bezkontextový neparametrický multi–úrovňový L–systém G je štvorica, t.j. G=(V, %, Ω, P), kde V je abeceda (konečná množina symbolov), je rezervovaný symbol rozdelenia, je konečná množina slov nad V nazývaná axióm a je konečná množina pravidiel. Abeceda V obsahuje aj zátvorky, [ a ], ktoré sa používajú na ohraničenie vetiev (konárov) vo výrazoch stromových štruktúr.

Derivačný krok multi–úrovňového L–systému pozostáva z dvoch podkrokov. Najprv použitím pravidiel z množiny P sú všetke slová x_i v súčasnej multi–množine dočasne nahradené slovami y_i. Jednotlivé odvodenia sa vykonávajú ako v bežných L–systémoch. V druhom kroku sú slova yi, ktoré obsahujú jeden alebo viac symbolov rozdelenia %, rozdelené na menšie časti. V tomto procese, symbol % vystupuje ako značka pozícií, v ktorých sú vetvy (konáre) yik oddelené od stromu yi. Zostavajúca časť stromu a yi a jeho odrezané časti yik sa stávajú prvkami novej nastupujúcej multi–množiny.

Príklad takéhoto multi–úrovňového L–systému:

Nasledujúca tabuľka zobrazuje prvé dva derivačné kroky. Nultým krokom (začiatkom) je axióm.