Prírodou inšpirované algoritmy

Úvod

Existuje množstvo zložitých úloh pri riešení, ktorých je nutné ešte pred ich implementáciou do praxe použiť simulácie možných stavov navrhovaného systému. Medzi takto zložité úlohy patria napríklad vývoj prírodných katastrôf, vývoj dopravnej situácie apod. Jedným z možných prostriedkov na simuláciu sú aj celulárne automaty.

Celulárny automat je diskrétny dynamický systém. Každý bod v geometrickej mriežke sa nazýva bunkou a môže nadobúdať jeden z k- možných stavov. Teória CA nachádza svoju inšpiráciu v biologických systémoch. Bunky sa na základe vopred určených pravidiel a vzájomnej interakcie nachádzajú v niektorom z k-možných stavou. Stav jednotlivých buniek v mriežke sa mení na základe lokálnych pravidiel, čo znamená, že stav danej bunky sa mení len v závislosti na jej stave v predchádzajúcom časovom okamihu a na stave susedných buniek v predchádzajúcom okamihu. Všetky bunky mriežky sa menia synchrónne v jednom okamihu. Stav mriežky sa teda mení v diskrétnom čase. Dynamika systému spočíva v aplikácii rôznych pravidiel, ktoré ovplyvňujú správanie sa buniek ( entít ) v danom priestore a určujú ich stav v nasledujúcom okamihu.

Existuje viacero druhov okolí bodu (susednosti), na základe čoho sa určuje stav daného bodu (za predpokladu 2D CA)

V tejto práci sa budem podrobnejšie venovať aplikácii celulárnych automatov v doprave.

Modely cestnej premávky sa delia do dvoch hlavných kategórií:

• mikroskopický
• makroskopický

Tieto kategórie sa ďalej rozdeľujú a vytvárajú viacero rôznych modelov. Parametre, ktoré ich najviac špecifikujú sú:

• rozmer (dimenzia) CA ( najčastejšie je to 1D resp. 2D )
• počet smerov, ktorými sa automobily (entity) pohybujú
• počet jazdných pruhov
• množstvo parametrov ovplyvňujúcich jednotlivé entity

Najjednoduchším z nich je model v ktorom je implementovaný len jeden jazdný pruh. Zložitosť narastá so stúpajúcim počtom jazdných pruhov. Ďalším faktorom zvyšujúcim zložitosť modelu je smer akým sa jednotlivé entity pohybujú. Pri modeli s obojsmernou prevádzkou tak vznikajú nové možnosti simulácie napr. obiehanie a s ním spojená otázka bezpečnosti. Jednotlivé pravidlá môžu byť odvodené od viacerých faktorov, akými sú napr. rýchlosť automobilov, zrýchlenie, brzdenie, vzájomná vzdialenosť prvkov apod. Rôzne druhy modelov budú podrobnejšie prebraté v ďalších častiach.