Stochastické a deterministické simulace

Esej, kterou jsem na poslední chvíli musel roztáhnout na 10k znaků. ChatGPT je v češtině lobotomizované poleno na úrovni 2. stupně základní školy, takže toto je výplod mého mozku v jeho vrcholném stádiu, s menšími korekcemi tu a tam. Některé druhy textových prací se měly objevit na simulace.info, tahle ne, tak ji dávám sem, už jenom proto, že jsou to dobrá trénovací data. Dovednosti v tabulkových procesorech nabyté při simulační práci jsou kvalitně využity na umělém jazyku budhót'nu. GeSeL používá skutečnou databázi.

=Stochastické a deterministické simulace=

~~~~ (Jan Getmančuk)

==Úvod==

Simulace společenských systémů, jak se tento předmět nazývá v anglické verzi, zahrnuje simulování chování lidí. Lidské chování ale není zcela racionální, tudíž ho nelze popsat a priori deterministickými pravidly. Jenom stroje pracují podle přednastaveného algoritmu a při rozhodování vždy dodržují pravidla. Důležitou roli v lidském rozhodování hrají emoce, což se odráží ve specifických vzorcích vývoje trhu.

Někdy je ale teoreticky deterministický model tak složitý, že jej nelze simulovat v jeho celistvosti, pročež musí být náhodně vybrána jeho podmnožina.

Proto je potřeba v některých typech simulací pracovat s určitou pravděpodobností na fundamentální úrovni, ne nepodobně kvantové mechanice.

==Vyjasnění==

Rozdělení stochastických a deterministických simulací se upatňuje zejména v simulacích pracujících se stavovými přechody.

Deterministická simulace nepoužívá žádné náhodné veličiny. Za stejných podmínek nastane v daném stavu vždy přechod do určitého jiného stavu, jako například v Turingově stroji. Všechny simulace provozované na deterministických strojích založených na pricipu Turingova stroje, jako osobní počítače, jsou striktně vzato deterministické, neboť neumožňují generovat čistě náhodná čísla ex nihilo bez externích vstupů, které jsou považované za náhodné, například prodlevy interakce uživatatele s periferními zařízeními nebo data ze sensorů různých fluktuujících fyzikálních veličin. Určitou podmnožinu deterministických modelů lze vyjádřit analyticky. Mezi deterministické simulace patří i systémová dynamika.

Stochastická simulace pracuje s náhodnými přechody mezi stavy na základě pravděpodobností. S tím se pojí zejména Markovovy řetězce a teorie front. Mezi stochastické simulace patří i Monte Carlo, které je místo na stavových přechodech založeno na konvergenci vyhodnocování náhodných vzorků. Stochastické jevy se vyskytují v přírodě jako Brownův pohyb, kvantová nejistota nebo rozpad radioaktivních částic. Tyto jevy poskytují náhodná data pro generování čistě náhodných čísel fundamentálně deterministickými stroji zmiňovanými výše.

Agentní simulace mohou být obojího druhu, v závislosti na implementaci chování jednotlivých agentů a způsobu určování vlastností prostředí.

Turingův stroj je abstraktní model, který má z některé strany nekonečný pás, po kterém se může pohybovat hlavice. Na pásu jsou pole, z nichž hlavice čte i na ně zapisuje symboly. Tato hlavice má v sobě scénáře, které určují, co má udělat, když narazí na ten či onen symbol, včetně toho, co má zapsat za symbol na místě, kde se nachází, a kam se má potom posunout. Z tohoto popisu plyne, že se jedná o disktréní a deterministický aparát. Jazyky, které k vyjádření potřebují výpočetní sílu Turingova stroje, se nazývají turingovsky kompletní. Turingův stroj používá Hejného metoda výuky takzvané předmatematické výchovy, kdy je Turingův stroj hravě zabalen do jakéhosi číselného pásu, po němž se děti pohybují a přemisťují na něj, na něm, nebo z něj různé objekty. V konvenčích vzdělávacích osnovách se děti učí být kalkulačkami, a počty jsou jim vydávány za matematiku.

Markovovy řetězce jsou definovány množinou stavů, pravděpodobností počátečních stavů, což je vektor, a pravěpodobnostmi přechodu mezi stavy v jednom časovém kroku, což je matice přechodu, v homogenních řetězcích nezávisle na čase uplynulém od začátku. Čas je indexovaný v diskrétních krocích. Tedy se jedná o kombinaci simulace jak stochastické, tak diskrétní. Varianta se spojitým časem se nazývá Markovův proces. Matice přechodu má součet řádků roven jedné, čemuž se právě říká, že je stochastická. Jelikož je jen dvourozměrná, pravděpodobnost dalšího stavu není ovlivněna stavy minulými. Na základě konkrétní podoby přechodové matice lze identifikovat stavy dosažitelné, znovunastávající, absorpční, přechodné, periodické, neperiodické a ergodické. Vhodným seřazením stavů lze dosáhnout blokové rozložitelnosti přechodové matice na komponenty absorpčních stavů do blokově diagonální levé horní části, pravděpodobnosti přechodů z přechodných do znovunastávajících stavů v levé dolní části, a pravděpodobnosti přechodů mezi přechodnými stavy v pravé dolní části, kdy pravá horní část je nulová. Při zkoumání asymptotického chování lze analyticky řešit jen speciální případy spočívající v konvergenci mocnin přechodové matice, kdy pravděpodobnost přechodných stavů konverguje k nule nebo určitému stacionárnímu rozdělení pravděpodobností, v obecných případech je třeba použít metodu Markov Chain Monte Carlo. Reversibilita markovova řetězce je možná, je-li celý ergodický a jeho matice přechodu je symetrická. Toho využívá metropolisův algoritmus pro luštění jednoduchých substitučních šifer, tedy permutací abecedy, kdy v každém kroku prohazuje korespondenci dvou písmenek otevřeného a šifrového textu s nenulovou pravděpodobností i při nižší věrohodnosti výsledné permutace. Jsou-li místo písmena dosazena slova nebo morfémy, vzniká jednoduchý jazykový model podobný našeptávači slov. V markovových řetězcích s nekonečně mnoha stavy lze setrvat v potenciálně nekonečně mnoha přechodných stavech, což znemožňuje naivní modelování polysyntetických jazyků pouze na základě slov oddělených mezerami. Například obdoba slavné německé dlouhé složeniny die Donau-Dampf-Schiff-Farhts-Gesellschafts-Kapitäns-Tochter-Wochen-End-Haus-Elektrizitäts-Ausrechnung (účet za elektřinu v chatě dcery kapitána dunajské paroplavební společnosti) se skládá ze čtrnácti jednoduchých slov.

Teorie front neboli model hromadné obsluhy je o poznání uzemněnější, než Markovovy řetězce popsané v předchozím odstavci. Skládá se ze zdrojů požadavků, front požadavků, obslužných linek paralelně či sériově zapojených, a odchodů ze systému. Zdroj požadavků může být konečný nebo nekonečný, příchod požadavků do fronty a doba trvání obsluhy můžou být stochastické, kde příchod požadavků má proměnné intervaly typicky odpovídající exponenciálnímu rozdělení, a doba trvání obsluhy může mít rovněž proměnné intervaly typicky odpovídající logaritmicko-normálnímu rozdělení. U paralelně zapojených obslužných linek se můžou tvořit oddělené fronty, nebo může být jediná společná. Toto je důležité rozlišovat, neboť nepochopení struktury fronty například v KFC oproti Lidlu může mít za následek dojem, že lidé předbíhají. V programování se frontou myslí FIFO (First In, First Out) datová struktura, v teorii front se pracuje i s LIFO (Last In, First Out) zásobníky nebo SIRO (Selection In Random Order) podobající se výběru sirky z krabičky. Fronta může být prioritní, kdy se nejdříve obsluhují požadavky s nejvyšší prioritou podle nadřazeného typu fronty. Může mít také omezenou kapacitu, kdy při naplnění kapacity je další požadavek odmítnut (drop), včetné nulové kapacity, kdy je požadavek zamítnut vždy při obsazení všech paralelních obslužných linek. Pokud požadavek čeká na odbavení příliš dlouhou dobu, může být z fronty odstraněn (aging parametr). Požadavky můžou být odbavovány také ve skupinách najednou. Při analýze systému hromadné obsluhy se zkoumají průměrné doby odbavení, doby v systému, délky fronty, počty požadavků v systému, jakož i pravděpodobnosti obsazenosti linek, odbavení v určitém čase, konkrétního počtu požadavků v systému a nemožnosti obsloužení požadavku z důvodu naplnění kapacity fronty. Převrácenými hodnotami střední doby mezi příchody požadavků a doby obsluhy jsou intenzita příchodu a obsluhy. Specifické jednoduché případy lze vyřešit analyticky, zatímco obecnější složité případy je nutné řešit simulačně. Při ohodnocení nákladů na provoz obslužných linek a udržování požadavků ve frontách je možné provést jejich optimalizaci, případně adekvátně upravovat cenu služby.

==Užití==

Autorova semestrální práce na simulaci vydavatelství slovníku je Šmakova hora, tedy kombinace Monte Carlo a Dračího doupěte. Jak v některých hazardních hrách jako Alea, tak v dračácích, se provádí házení kostkami, které má vliv na hráčův další osud ve hře. Jelikož zde hraje roli náhoda, jedná se o stochastickou simulaci. Klasické Monte Carlo je založeno na konvergenci výsledků mnoha iterací, kdežto Šmakova hora je založena na divergenci výsledků několika málo iterací vedoucích k různým cestám přechodů mezi stavy. Zdrojem inspirace pro semestrální práci byly soutěžní zadání Financial Modeling World Cup, které jsou avšak z důvodu snadnějšího vyhodnocování zadané deterministicky. Stav se zde mění jen podle zadaných pravidel.

Simulace deskových her, kde se nehází kostkami, jsou zpravidla deterministické. Je-li algoritmus rozhodování hráče deterministický, uplatňuje se prohledávání stavového prostoru dané hry do určité hloubky, tedy několik tahů dopředu. Algoritmus minimax funguje tak, že hráč počítá s nejhorším, co protihráč může provést. Jedná se proto o prohledávání do hloubky. Co je "to nejhorší", záleží na způsobu ohodnocení stavu hry, které slouží jako heuristika.

Pseudonáhodné generátory a hashovací funkce jsou ze své podstaty běhu na deterministickém stroji rovněž deterministické, ačkoliv se snaží být obtížně předvídatelné, typicky na bázi modulo aritmetiky. Hlavní jejich užití je v kryptografii pro generování klíčů, v kontextu simulací simulují stochastičnost simulace. Primitivním příkladem pseudonáhodného generátoru je lineární kongruentní generátor.

Dopravní simulace musí zohledňovat chování lidí, je tedy na místě zapojit náhodu, tudíž jsou to simulace stochastické. Na semaforech se uplatňuje teorie front, v nesignalizovaných úsecích se jedná o modelování materiálového toku. Dalšími oblíbenými příklady aplikace teorie front jsou stravovací zařízení, přepážky na úřadech a teorii spolehlivosti s dimenzováním skladů náhradních dílů.

V předmětu Lineární programování se probírá řízení zásob, které nemusí ubývat vždy rovnoměrně. Zejména v iterativním přístupu se jedná o stochastickou simulaci. Smyslem optimalizace řízení zásob je minimalizovat náklady na skladování za současného včasného vyhovění zákazníkům, což rozpracovává metoda Just-In-Time původně navržena v Toyotě, jejíž excesivně naivní aplikování jinými automobilkami vedlo k nedostatku mikročipů během pandemie.

Path tracing se liší od ray tracingu tím, že se jedná o Monte Carlo metodu na rozdíl od analytického výpočtu. Proto obrazy vykreslené pomocí path tracingu jsou zrnité a musí se dodatečně vyhlazovat v postprocessingu, zatímco obrazy vykreslené pomocí ray tracingu typicky obsahují velmi lesklé až zrcadlovité objekty. Ray tracing jakožto čistě analytický výpočet je také výpočetně velmi náročný s možností dynamického kontrolování kvality omezené na snížení vykreslovacího rozlišení a maximálního počtu odrazů, kdežto u stochastického path tracingu lze také volně měnit počet vzorků na pixel podle dostupných hardwarových prostředků, složitosti vykreslovaného objektu nebo anticipace potřeby rychleji aktualizovat stíny v určité oblasti obrazu. Oboje metody ray tracingu i path tracingu jsou z implementačního hlediska jednodušší metody vykreslování než dodatečné světelné triky v rasterizaci jako krychlové mapy odrazů, Phongův model osvětlení, odrazy v obrazovém prostoru, zapečené osvětlení nebo stínové mapy. Jednodušší paprskové metody vykreslování jsou raymarching na základě Newtonovské iterace a raycasting používaný například v Computer-Aided Design nástrojích nebo ve zjednodušené dvourozměrné podobě v historických a retro počítačových hrách. Raymarching může být stochastický v závislosti na způsobu iterování, kdežto raycasting je striktně deterministický. Ve všech případech je důležitá rychlá indexace objektů ve třech dimenzích, k čemuž se v případě voxelů neboli bodových mraků používají řídké oktantové stromy.

V jazykových modelech umělé intelingence se uplatňuje přechodová matice, která určuje, s jakou pravděpodobností bude který symbol následovat po určitých předchozích symbolech, tedy kontextu. Tento stochastický přístup je v souladu se spontánní podstatou jazyka, ale neřeší jeho syntaxi. Někteří lidé jsou v souvislosti se svými projevy označovány za generátory náhodných slov, jako například jeden nejmenovaný politik v souvislosti se svou impromptu básní o přicházení s matematickým modelem, který měl simulovat promořování populace netopýří chřipkou. Avšak ani přístup na bázi formální gramatiky nemusí nutně generovat smysluplné věty, například Chomského zuřivě spící bezbarvé zelené nápady. Interpretace podobných konvenčně sémanticky nesmyslných sekvencí slov se potom pohybuje v rozmezí literárních figur a trop, případně se jedná o Delfskou věštírnu. Na uměleckou podstatu zdánlivého nesmyslu navazovali avantgardisté a dadaisté.

==Další pojednání==

Zakomponování prvků náhody do hry zvyšuje její opakovanou hratelnost z hlediska kazuálního osobního zážitku. Nicméně přemíra náhodných veličin znesnadňuje zpětné ověřování průběhu her v kompetitivních prostředích (například speedrunning) a umenšuje vliv dovedností hráčů ve prospěch pouhého štěstí. Dovednost znamená v tomto případě deterministické rozhodování, které usměrňuje náhodný simulovaný svět. Některé herní společnosti jako Electronic Arts zašly ve svých pokusech o monetizaci tak daleko, že hry jsou v podstatě on-line kasína, což se nevyhlo pozornosti regulačních orgánů Evropské unie.

Stochastický prvek je zpravidla na spodní vrstvě simulačního modelu, který jej transformuje převážně deterministickými způsoby za účelem smysluplného vyhodnocení chování simulovaného systému.

Skutečnost, že je simulace deterministická, neznamená, že je lineárně předvídatelná. Existují algebraicky složitější rovnice jako exponenciální a goniometrické, a také analyticky irreversibilní operace jako již zmíněné modulo. Nepředvídatelné se snaží být pseudonáhodné a procedurální generátory, v souvislosti se zvýšením kvality herního zážitku popsaném výše.

Simulace jsou zpravidla spouštěny opakovaně a jejich jednotlivé běhy jsou statisticky vyhodnocovány, což je příhodné pro stochastické simulace, neboť průběh deterministických simulací bude v každém běhu pro stejné počáteční podmínky stejný, ledaže výpočetní zařízení má vadnou operační paměť.

==Zdroje a literatura==

* NAVARA, Mirko. "Markovovy řetězce". Verze 9.1.2018. Scriptum FEL ČVUT. <http://cmp.felk.cvut.cz/~navara/psi>

* JABLONSKÝ, Josef. "Operační výzkum". 3. vydání. Praha: Professional Publishing, 2007. ISBN 978-80-86946-44-3.

* ŽÁRA, Jiří - LIMPOUCH, Aleš - BENEŠ, Bedřich - WERNER, Tomáš. "Počítačová grafika - principy a algoritmy". 1. vydání. Praha: Grada, 1992. ISBN 80-85623-00-5.