MODELOVÁNÍ A SIMULACE

11

MODELOVÁNÍ A SIMULACE

při návrhu slidů byly využity materiály Michala Dordy (http://homel.vsb.cz/~dor028/Aplikace_PC.htm) Radka Pelánka (http://www.fi.muni.cz/~xpelanek/IV109/), a Peera-Olafa Sieberse (http://www.cs.nott.ac.uk/~pos/g54sim/index2011.html) © Jiří Jelínek

Modelování a simulace

Úvod

© Jiří Jelínek


Systém ●

množina částí organizovaná za nějakým účelem a s určitými vlastnostmi ● ● ●

●

nutno stanovit hranice množina prvků (příznaků, Q) množina vazeb (relací, R)

vazby vnitřní – mezi jednotlivými prvky systému ● vnější – mezi prvky systému a jeho okolím ●

●

okolí systému ●

© Jiří Jelínek

prostředí, do kterého je systém zasazen a se kterým komunikuje pomocí vstupních a výstupních vazeb Modelování a simulace

14

Typy systémů ●

● ● ● ● ● ●

přírodní systémy (počasí, vesmír) umělé fyzické systémy (dům, auto, továrna) umělé abstraktní systémy (matematika, literatura) systémy lidských aktivit (rodina, město, politické systémy) produkční systémy – nastavení zdrojů pro produkci zboží a výrobků a služeb sociální systémy – systémy jedinců a skupin se vzájemnými vztahy a vzory chování ekonomické systémy

© Jiří Jelínek


15

Struktura systému vnitřní uspořádání systému vyjádřené vzájemnými vazbami ● množina prvků systému Q = {Q1,…, Qm} a množina vazeb R = {R1,…, Rn} mezi jednotlivými prvky systému ● strukturu systému potom lze symbolicky zapsat jako přiřazení: ●

●

S = {Qi, Qj, Rk},

●

Qi je vstupní prvek a Qj výstupní prvek vazby Rk,

kde i, j  1;2;...; m a © Jiří Jelínek

k  1;2;...; n


16

x

Q1

R1 Q2

R2 u

© Jiří Jelínek

Q3

R3

y


17

●

vstupní proměnné ●

●

výstupní proměnné ●

●

y1,…,yl

stavové proměnné ● ●

●

zpravidla u1,…, ur

popisují vnitřní parametry x1 ,…, xn

souhrnně ● ●

© Jiří Jelínek

vektory u, y, x různý počet souřadnic Modelování a simulace

18

●

stav systému ●

●

okamžité hodnoty stavových proměnných x(t), případně stav jednotlivých prvků v daném okamžiku

podmínka separability ●

systém je separabilní, pokud svými výstupy

neovlivňuje přes okolí své vstupy ● vstupní a výstupní proměnné systému zahrnují proměnné, pomocí kterých systém komunikuje přes vstupní a výstupní vazby s okolím systému

© Jiří Jelínek


19

Systémy ●

statické výstup je jednoznačně definován vstupem ● systém je popsán pouze statickou charakteristikou ● závislost výstupu na hodnotách vstupu: y = f(u) ● výstup systému nezávisí na čase t ●

●

dynamické

výstup není jednoznačně určen pouze vstupy, ale závisí také na čase ● vektorová stavová rovnice (změna stavového vektoru v čase): Δx=f(x,u) ● vektorová výstupní rovnice (závislost výstupů na vstupech a stavu): y=g(x,u), x(0)=x0 © Jiří Jelínek Modelování a simulace ●

20

podle definičního oboru proměnných ● diskrétní ●

●

●

spojité ●

●

hodnoty proměnných se mění nespojitě v určitých časových okamžicích (skokově) proměnné mění svoje hodnoty spojitě ve sledovaném čase

příklady?

© Jiří Jelínek


21

podle přítomnosti náhodných proměnných ● deterministický systém ●

● ● ●

●

hodnoty všech proměnných jsou v každém okamžiku přesně definovány při stejných podmínkách jsou výsledky simulace vždy stejné pravidlové systémy

stochastický systém ● ●

© Jiří Jelínek

proměnné (některé nebo všechny) mají charakter náhodné proměnné podmíněné pravděpodobnosti Modelování a simulace

22

Složitost systému daná náročností popisu vzorů či zákonitostí v systému ● zejména pro ně vhodná simulace ●

© Jiří Jelínek


23

Definice KS ●

●

● ● ● ● ●

A system that can be analyzed into many components having relatively many relations among them, so that the behavior of each component depends on the behavior of others. (Herbert Simon) A system that involves numerous interacting agents whose aggregate behaviors are to be understood. Such aggregate activity is nonlinear, hence it cannot simply be derived from summation of individual components behavior. (Jerome Singer) A complex system is a highly structured system, which shows structure with variations. (Goldenfeld and Kadano) A complex system is one that by design or function or both is dicult to understand and verify. (Weng, Bhalla and Iyengar) . . .

© Jiří Jelínek


24

Příklady KS ●

● ● ● ● ● ● ● ●

ekosystémy trhy podnebí organizace mraveniště buňka město imunitní systém nekomplexní systémy ??? ●

© Jiří Jelínek

stroje, termostat, páka, … Modelování a simulace

25

Charakteristika KS ●

dynamické – měnící se v čase ● ● ●

strukturou chováním rovnovážné stavy

těsně svázané – vnitřní vazby a ovlivňování ● řízené zpětnou vazbou – systém ovlivňuje sám sebe ● nelineární – často obtížný analytický popis ● sebeorganizující se – celek je víc než souhrn prvků ● adaptabilní – např. učení ●

© Jiří Jelínek


26

SYSTÉMOVÉ MYŠLENÍ

© Jiří Jelínek


27

Myšlení lidé dokáží rychle najít jednoduchou příčinnou souvislost ● zřetězení událostí výrazně komplikuje odhalení prvotní příčiny ●

●

např. prodeje jsou nízké protože jsou zaměstnanci málo motivovaní, protože …

intuitivní myšlení ● systémové x redukcionistické ● induktivní x deduktivní ● centralizované x decentralizované ●

© Jiří Jelínek


28

Intuitivní myšlení na základě reflexů a tradičních hluboce zakořeněných vzorů daných zkušenostmi a výchovou ● tacit knowledge – implicitní znalosti ● lineární uvažování ●

●

●

trojčlenka, extrapolace trendů

krátkodobý výhled ● ●

© Jiří Jelínek

nevhodné pro komplexní systémy – dlouhodobé zlepšení vyžaduje krátkodobé zhoršení např. ekonomická krize Modelování a simulace

29

●

zjednodušený pohled na kauzalitu ● ● ●

●

ovlivnění paradigmatem ●

●

souhrn domněnek, předpokladů, představ

komplexní systémy neintuitivní ●

●

co bylo čím způsobeno? hledání nejjednoduššího vysvětlení např. zapalovače a rakovina

např. více silnic vede k zácpám, bezpečná auta vedou k nebezpečné jízdě, ….?

x v komplexních systémech je nutné přesně formulovat předpoklady

© Jiří Jelínek


30

Deduktivní a induktivní myšlení ●

deduktivní ● ● ●

●

z předpokladů logické závěry jednoduchý formální popis neodpovídá lidskému myšlení

induktivní ● ● ●

© Jiří Jelínek

odvozování obecného z konkrétních příkladů, odhady vývoje blízké lidskému přístupu obtížně popsatelné


31

Centralizované a decentralizované myšlení ●

centralizované ● ● ●

●

jedna příčina, jeden zdroj význam jevů a objektů (uzlů) v popisu negativní zpětná vazba

decentralizované vhodné pro komplexní systémy ● pozitivní zpětná vazba ● význam vztahů ●

© Jiří Jelínek


32

Systémové myšlení odhlédněme od izolovaných událostí a jejich příčin ● pohlížejme na organizaci jako na systém s vzájemně interagujícími částmi ● vnitřní struktura systému bývá při řešení problému důležitější než externí události, které ho bezprostředně vyvolají ● systémový a globální pohled na předmět zkoumání ●

© Jiří Jelínek


33

© Jiří Jelínek


34

Redukcionismus a holismus Redukcionismus (systém lze Holismus (systém je víc než součet poznat na základě studia jeho částí) částí) Důraz na studium částí

Důraz na vazby a interakci v celku

Lineární uvažování

Nelineární uvažování

Dedukce

Indukce

Příčina - následek

Zpětné vazby

Analytické řešení

Experimenty a simulace

●

reálný svět je šedý

© Jiří Jelínek


55

SIMULACE

© Jiří Jelínek


56

Způsoby zkoumání systému Systém Experimenty se systémem

Experimenty s modelem Fyzikální model

Simulace

© Jiří Jelínek

Matematický model Analytické řešení


57

Simulace ● ●

●

●

více definic Simulace je proces tvorby modelu reálného systému a provádění experimentů s tímto modelem za účelem dosažení lepšího pochopení chování studovaného systému či za účelem posouzení různých variant činnosti systému (Shannon). – dynamická stránka modelu Simulace je technika, která nahrazuje zkoumaný dynamický systém jeho modelem s cílem získat informace o systému pomocí experimentu s modelem (Dahl). obě zahrnují proces tvorby modelu

© Jiří Jelínek


58

Simulace snaha predikovat chování systému za určitých podmínek ● experimentální přístup k poznávání modelovaného systému přes modelující systém (model) ●

●

what-if analýza

důraz na dynamiku ● umožňují reprezentovat (modelem) a zkoumat (experimentem) variabilitu, propojenost a komplexitu systémů ●

© Jiří Jelínek


59

Vztahy systémů a operací s nimi

Reálný systém

Abstrakce, modelování

Simulační běh

Interpretace

Výsledky © Jiří Jelínek

Simulační model

Vyhodnocování

Experimenty Modelování a simulace

60

Proč simulovat? ●

systémy se mohou měnit ● ●

●

systémy jsou propojené ●

●

predikovatelné změny – plánované, známé nepredikovatelné změny – poruchy, příchody zákazníků jeden ovlivňuje druhý

systémy jsou obvykle komplexní ● ●

© Jiří Jelínek

kombinatorická komplexita – počty komponentů a počty jejich vazeb dynamická komplexita – u úzce propojených systémů, systémy se zpětnou vazbou, dopady akcí na jednotlivé části systému Modelování a simulace

61

Výhody simulace ●

● ●

● ●

náklady čas – reálný a simulační řízení experimentů simulace abstraktních systémů simulace umožňuje predikovat výkonnost systémů ● porovnávat různé návrhy systému ● zjišťovat vliv změn v konfiguraci a provozování systémů ●

© Jiří Jelínek


62

Nevýhody simulace ●

● ●

● ●

náklady – nutno vytvořit model časově náročná – počty a průběhy experimentů dostupnost dat expertní přístup při návrhu – více umění než věda zjednodušení reality – abstrakce, předpoklady

© Jiří Jelínek


63

●

rozdíl od jiných modelovacích technik ● ●

●

● ●

© Jiří Jelínek

variabilita – možnost volby způsobu modelování omezení a nároky na popis systému – nutné předpoklady jiných technik - diferenciální rovnice, distribuce pravděpodobností transparentnost – názornost oproti striktně matematickým modelům, srozumitelnost pro širší publikum pochopení a vytváření mentálních modelů – znalostí vizualizace, komunikace, interakce - nad systémy


64

Postup tvorby simulace ●

● ●

● ● ●

stanovení účelu a cíle tvorby modelu a experimentů, které se budou realizovat návrh simulačního modelu podle charakteru systému implementace modelu ve softwarovém prostředí příprava experimentálních údajů pro model s cílem prověřit jeho správnost při implementaci verifikace a validace modelu, stanovení odchylek mezi modelem a modelovaným systémem příprava, realizace a analýza jednotlivých experimentů s ohledem na vytčené cíle

© Jiří Jelínek


65

http://homel.vsb.cz/~dor028/Aplikace_2.pdf © Jiří Jelínek


66

Čas v simulačním modelu ●

reálný čas ●

●

simulární čas ● ● ●

●

čas skutečného děje v reálném systému vnitřní čas simulačního modelu může běžet mnohonásobně rychleji (nebo i pomaleji) než realný čas fiktivní čas, který nemusí běžet plynule a rovnoměrně

strojový čas spotřebovaný na výpočet modelu a experimentů ● podle složitosti modelu, nesouvisí se simulárním časem ●

© Jiří Jelínek


67

Příklady simulací předpovědi počasí ● hry ● robotika ● další? ●

© Jiří Jelínek


78

DISKRÉTNÍ SIMULAČNÍ MODELY

při návrhu slidů byly využity materiály Michala Dordy (http://homel.vsb.cz/~dor028/Aplikace_PC.htm)

© Jiří Jelínek


79

Hlavní problémy ●

● ● ●

● ● ●

zachycení statických vlastností (struktury modelu) zachycení dynamických vlastností modelu problematika generování náhodných proměnných vyskytujících se v modelu realizace sběru potřebných údajů (výstupů) z chodu simulačního modelu návrh a vyhodnocení experimentů s modelem zpracování a výstup simulačních výsledků kontrolní a monitorovací funkce

© Jiří Jelínek


80

Úvod ●

příklady?

●

kdy diskrétní simulace? ● ●

● ●

mění-li se stavové proměnné diskretně (skokově) v určitých okamžicích simulárního času v okamžicích výskytů událostí - přechodové okamžiky

stav systému se mezi dvěma přechodovými okamžiky nemění otázka stanovení časového kroku

© Jiří Jelínek


81

Pevný časový krok Δt = konst. ● byl by nejjednodušší pro organizaci výpočtu ● jak velký časový krok Δt stanovit? ●

●

zachycení všech okamžiků změn v systému s definovanou časovou přesností

příliš malý > zbytečně vyšší objem výpočtů ● příliš velký > více událostí v jednom časovém okamžiku ●

●

●

shlukování nebo i nezaregistrování některých událostí

proto proměnný krok

© Jiří Jelínek


82

Proměnný časový krok Δt ≠ konst. ● okamžik (přechodový okamžik) ●

●

●

interval ●

●

hodnota simulárního času, v níž dochází ke změně alespoň jedné stavové proměnné simulačního modelu (tedy ke změně stavu modelu) časový úsek mezi dvěma po sobě jdoucími okamžiky

časové rozpětí ●

© Jiří Jelínek

několik na sebe navazujících intervalů


83

●

událost ● ● ● ●

●

změna stavu modelu v okamžiku, ve kterém začíná aktivita má obvykle nulovou časovou délku např. příchod do fronty, zahájení zpracování, odchod

aktivita ● ●

© Jiří Jelínek

stav modelu mezi dvěma událostmi popisujícími po sobě jdoucí změny stavu modelu např. čekání, obsluha


84

●

proces ● ●

●

posloupnost stavů modelu v časovém rozpětí např. vše od příchodu do odchodu

při proměnném časovém kroku rozeznáváme algoritmy orientované na události ● algoritmy orientované na aktivity ● algoritmy orientované na procesy ●

© Jiří Jelínek


85

Algoritmy orientované na události zaveďme množinu U jako množinu všech tříd Ui událostí, jejichž výskyt má za následek změnu stavu modelu, U = {U1 ; U2 ;...; Un } ● výskyt události z jedné třídy má za následek stejný charakter změny stavu modelu (lze jej popsat stejným úsekem programu) ●

●

např. všechny příchody do fronty lze popsat stejnou částí algoritmu

TUi = okamžik příštího výskytu události z třídy Ui ● čas je vždy chápán jako simulární čas ●

© Jiří Jelínek


86

M = obecná hodnota času, která je větší, než hodnota času odpovídajícího výskytu libovolné události ● pokud neumíme určit okamžik příštího výskytu události z třídy Ui, pak TUi = M (= odložení na neurčito) ● důsledky výskytu libovolné události z třídy Ui můžeme popsat algoritmem Ai, kde i = 1, 2,…, n ●

© Jiří Jelínek


87

Algoritmy orientované na události S

a) dosazení počátečních podmínek (čas= 0) b) stanovení hodnot TU1, ..., TUn vytvoření kalendáře událostí, TUk může mít hodnotu M c) TUk = min{TU1, ..., TUn}, může být i více, pak nutný výběr (priorita) d) čas = TUk e) Ak (vč. aktualizace kalendáře událostí) ne

konec? ano

zpracování a výstup výsledků © Jiří Jelínek

K Modelování a simulace

89

Příklad Systém hromadné obsluhy s řádným frontovým režimem a nekonečnou délkou fronty. ● Doba mezi příchody po sobě jdoucích požadavků náhodná proměnná X ● Doba obsluhy požadavku náhodná proměnná Y. ●

●

Nakreslete vývojový diagram zachycující modelující algoritmus tohoto systému orientovaný na události.

© Jiří Jelínek


90

●

vnitřní (stavové) proměnné modelu: ● ●

proměnná F - aktuální počet požadavků ve frontě proměnná S - stav obsluhy ●

●

(0 – linka nepracuje, 1 – linka provádí obsluhu požadavku)

třídy událostí ● ● ●

U1 - příchod požadavku do systému U2 - ukončení obsluhy požadavku U3 - zahájení obsluhy požadavku ●

© Jiří Jelínek

pouze pro F>=1 a S=0 > podmíněno stavem systému, neuvažuje se


91

●

pravidla ● ●

●

počáteční podmínky ● ●

● ●

linka může současně obsluhovat jeden požadavek obsluha požadavku aut. začíná pro (F > 0) && (S = 0) systém je v okamžiku čas = 0 prázdný F = 0 a S =0

první požadavek v okamžiku t1 > okamžik prvního výskytu události z třídy událostí U1 bude TU1 = t1 v čas = 0 žádná obsluha neprobíhá > nelze naplánovat první okamžik výskytu události z třídy U2, proto TU2 = M

© Jiří Jelínek


92 čas = 0, F = 0, S = 0

S

TU1 = t1, TU2 = M TUk = min{TU1, TU2} čas = TUk ano

k = 1?

ano

F=F+1 S=0 TU2=M

Generuj x

F = 0? ne F=F-1 Generuj y

TU1 = čas + x S = 0?

ne

ne

TU2 = čas + y

ano

S = 1, F = F - 1 Generuj y

ne konec? ano výstup výsledků

TU2 = čas + y K © Jiří Jelínek


93

Testování vygenerovány náhodné proměnné X a Y ● první požadavek v t1 = 2 ●

●

Čas

TU1

TU2

F

S

0

2

M

0

0

2

4

8

0

1

4

7

8

1

1

7

13

8

2

1

8

13

10

1

1

x

2

3

6

8

2

4

10

13

13

0

1

y

6

2

3

3

10 2

13

21

13

1

1

13

21

16

0

1

16

21

M

0

0

21

23

31

0

1

23

27

31

1

1

27

M

31

0

1

31

M

M

0

0

časová osa?

© Jiří Jelínek


94

Algoritmy orientované na aktivity pro zachycení dynamických vlastností modelovaného systému se využívají aktivity ● nutno definovat ●

● ● ●

soubor aktivit podmínky, které musí být splněny, aby mohla daná aktivita nastat změny, ke kterým dochází působením aktivit

každá aktivita začíná a končí událostí ● výskyty událostí jsou zadány podmínkami, které musí být splněny ●

● © Jiří Jelínek

pak mohou být realizovány změny stavu modelu Modelování a simulace

95 S

dosazení počátečních podmínek (čas= 0)

ne Podmínky 1? ano

aktivita 1

změny stavu modelu

ne

Podmínky K?

ano změny stavu modelu

aktivita K

posun času modelu ne konec? ano K © Jiří Jelínek

zpracování a výstup výsledků Modelování a simulace

96

●

při každé změně simulárního času nutno testovat podmínky pro všechny aktivity ●

●

z hlediska rychlosti výpočtu zpravidla méně efektivní přístup než orientovaný na události

tento přístup vhodnější, pokud výskyt událostí často vázán na splnění určitých podmínek než na dosažení určité hodnoty času

© Jiří Jelínek


97

Příklad ●

nakresleme vývojový diagram zachycující modelující algoritmus orientovaný na aktivity systému hromadné obsluhy z předchozího příkladu

© Jiří Jelínek


98

stavové proměnné - F a S, stejný význam ● proměnné TU1 a TU2 - pořadí významné ● za jak dlouho dojde k dalšímu příchodu, resp. odchodu požadavku ●

●

●

pokud některá z nich záporná > doba, jež uplynula od posledního výskytu příslušné aktivity

okamžik příští změny stavu modelu = minimum z kladných hodnot TU1 a TU2 vybraná hodnota se přičte k hodnotě aktuálního času a současně se odečte od všech časových proměnných ● více aktivit současně > stanovení pořadí ●

© Jiří Jelínek


99 čas = 0, F = 0, S = 0

S

TU1 = 2, TU2 = -1 TUk = min {TU1, TU2}

F=F+1

ano

TU1 = 0? ne

Generuj x TU2 = 0?

TU1 = x

F = F – 1, S = 1

ne

ano S=0 ano

F > 0 && S = 0? ne

Generuj y

konec? ano

TU2 = y

ne

Δt = min {TU1 , TU2 }, TU1 > 0, TU2 > 0 čas = čas + Δt TU1 = TU1 - Δt, TU2 = TU2 - Δt

výstup výsledků

K © Jiří Jelínek


10 0

Algoritmy orientované na procesy ●

kombinace předchozích přístupů

© Jiří Jelínek


10 1

SIMULAČNÍ TECHNIKY

při návrhu slidů byly využity materiály ● Peera-Olafa Sieberse (http://www.cs.nott.ac.uk/~pos/g54sim/index2011.html)

© Jiří Jelínek


10 2

Úroveň abstrakce v simulaci ●

strategická ● ●

●

taktická ●

●

vysoká míra abstrakce, málo detailů, makropohled agregace dat i objektů, zpětná vazba vyvážení míry abstrakce a množství detailů

operační ● ●

© Jiří Jelínek

minimální abstrakce, hodně detailů, mikropohled jednotlivé objekty, přesná a detailní data


10 3

Strategická

dopravní makro modelování

finanční analýzy Taktická

ekonomika zdravotnictví

dynamika populací

SCM

obchod

ekosystémy

dynamika pohybu osob

obranné plánování zdravotnictví

Operační

hromadná obsluha

© Jiří Jelínek

dopravní mikro modelování

skladové operace


10 4

Přístupy k modelování (paradigmata) ●

modelování systémové dynamiky (SDM) a její simulace (SDS) ● ●

●

diagramy toků a zásob deterministická a spojitá simulace

modelování diskrétních událostí (DEM) a jejich simulace (DES) ● ●

© Jiří Jelínek

diagramy toků (zpracování) stochastická diskrétní simulace (tokově orientovaný přístup)


10 5

●

agentové modelování (ABM) a simulace (ABS) ● ●

●

stavové diagramy stochastická diskrétní simulace (objektový přístup)

smíšené (hybridní) modelování (MMM) a simulace (MMS) ●

© Jiří Jelínek

kombinace předchozího např. na různých hierarchických úrovních nebo u různých modelovaných objektů


10 6

Ukázky

DEM

SDM

ABM © Jiří Jelínek


10 7

SD

Strategická

Taktická

AB DE

Operační

© Jiří Jelínek


10 8

SYSTÉMOVÁ DYNAMIKA

při návrhu slidů byly využity materiály Craiga W. Kirkwooda (http://www.public.asu.edu/~kirkwood/sysdyn/SDIntro/SDIntro.htm) a Peera-Olafa Sieberse (http://www.cs.nott.ac.uk/~pos/g54sim/index2011.html)

© Jiří Jelínek


10 9

Systémová dynamika metodika a technika pro ohraničení, pochopení a diskutování komplexních úloh a problémů (Kirkwood) ● základem poznání, že struktura systému je stejně důležitá pro pochopení jeho chování jako jeho jednotlivé komponenty a jejich chování ● zejména pro strategické modely s dlouhou platností a časovým záběrem ●

●

●

vysoká míra agregace dat a struktury modelu

business, sociální systémy, urbanistika, ekosystémy

© Jiří Jelínek


11 0

Historie ●

Norbert Wiener (1940s) ●

●

Jay Forrester (1950s) ●

●

studium regulace a řízení biologických, sociálních technických a ekonomických systémů - Kybernetika uplatnění kybernetických principů na průmyslové systémy – Industrial Dynamics

John Collins (1970s), John Stermann (1980s) ●

© Jiří Jelínek

principy Industrial Dynamics na sociální, urbanistické, obchodní sociální a ekologické systémy – Systémová Dynamika


11 1

Vzory chování generalizace od jednotlivých událostí k obecnému chování, které je charakterizuje - vzor ● po identifikaci vzoru chování můžeme hledat systémovou strukturu a chování, které vzor vyvolávají ● modifikací systémové struktury můžeme problém trvale odstranit ●

© Jiří Jelínek


11 2

Obvyklé vzory chování a reakce ●

vyskytují se samostatně nebo v kombinaci

© Jiří Jelínek

G54SIM (http://www.cs.nott.ac.uk/~pos/g54sim/)


11 3

Zpětnovazební a diagramy příčinných závislostí způsob reprezentace systémových struktur ● prvky = elementy ● vazby = příčinné vlivy mezi elementy ●

●

●

šipka vede od příčiny k následku

Diagram pro výrobní sektor

zachycení kauzality

© Jiří Jelínek


11 4

●

zpětnovazební smyčka – element přes nebo příčinné vazby nepřímo ovlivňuje sám sebe

© Jiří Jelínek


11 5

●

příčinná vazba vazba od elementu A do B je pozitivní (+, s - same), pokud buď A přidává k B nebo změna A vytváří změnu B stejným směrem ● vazba od elementu A do B je negativní (-, o opposite), pokud buď A odečítá od B nebo změna A vytváří změnu B opačným směrem ●

●

zpětná vazba - přes více elementů, vyšší struktura vazba A je pozitivní (+, R - reinforcing), když obsahuje sudý počet negativních příčinných vazeb ● vazba A je negativní (-, B - balancing), když obsahuje lichý počet negativních příčinných vazeb ●

© Jiří Jelínek


11 6

Příklad

požadovaná hladina vody

+

+ +

potřeba

pozice baterie +

-

proud vody

-

hladina vody

●

plnění sklenice vody

© Jiří Jelínek

+

negativní zpětná vazba – ve smyčce je lichý počet negativních vazeb


11 7

Příklad – samoregulující se biosféra sluneční svit

odpařování vody

teplota Země

mraky

© Jiří Jelínek

množství vody na zemi

déšť


11 8

Příklad – samoregulující se biosféra -

sluneční svit

+

+

teplota Země

+

+

odpařování vody

-

množství vody na zemi -

+

mraky

© Jiří Jelínek

+

+

déšť


11 9

Systémové struktury a vzory chování ●

pozitivní (zesilující) zpětná vazba ● ●

●

negativní (vyrovnávající) zpětná vazba ● ●

●

regulační vliv negativní vazby asymptotické přiblížení k požadovanému stavu (shora, zdola)

negativní zpětná vazba se zpožděním ●

●

exponenciální růst navzájem pozitivně se ovlivňující jevy

cykly

kombinace pozitivní a negativní vazby ●

© Jiří Jelínek

S-křivka (sigmoida) Modelování a simulace

12 0

Diagramy toků a zásob ukazují vztahy mezi proměnnými měnícími se v čase ● rozlišují různé typy proměnných ●

●

sklad (zásoba) – obdélník hromadění něčeho v čase - integrační (akumulační) funkce ● materiál, osoby zboží, peníze ●

●

tok (míra, aktivita, pohyb) – ventil ●

●

informace – čára se šipkou ●

© Jiří Jelínek

tok něčeho ze skladu do skladu – hodnota toku se může řídit i množstvím ve skladech mezi skladem a tokem = tok je ovlivněn informací o skladu Modelování a simulace

12 1

●

doplňkové objekty ●

pomocný prvek – kruh ●

●

objeví se pokud popis závislosti toku na skladu vyžaduje další výpočty – pro komplexní modely

zdroj a odpad – obláček reprezentují systémy skladů a toků mimo náš systém ● něco k nám přichází a něco zase odchází pryč ●

●

zpoždění – svislé čárky ●

© Jiří Jelínek

dochází ke zpoždění při přenosu informace


12 2

Příklad - změny v populaci +

narození +

© Jiří Jelínek

děti

-

dospívání

dospělí

úmrtí

-


12 3

inicializace stavů ● exaktní popis toků - vzorec ● analogie s potrubím, zásobníky a ventily ● příklad – Bass diffusion ●

● ● ●

potenciální zákazníci = počáteční stav – suma (integrál) prodejů skuteční zákazníci = suma prodejů prodeje = různé možnosti ●

© Jiří Jelínek

umění zvolit


12 4

Susceptible Infectious Recovered (SIR) Model ●

definice modelu (main) a nastavení simulace (experimentu, simulation view)

© Jiří Jelínek


12 6

Tvorba SD modelů ●

koncepce ● ● ● ●

●

účel modelu hranice modelu a klíčové proměnné chování klíčových proměnných diagram základních mechanizmů a vazeb (příčinných i zpětných) v modelu

formulace ● ● ●

© Jiří Jelínek

diagram zásob a toků včetně vzorců odhad parametrů vytvoření simulačního modelu Modelování a simulace

12 7

●

testování ● ●

●

testy dynamických hypotéz – možného vysvětlení pozorovaného chování testování chování a citlivosti při výkyvech

implementace ● ●

© Jiří Jelínek

testování reakcí na různé nastavení a zacházení interpretace výstupů a jejich transformace do přístupné formy


12 8

Zdroje ● ● ● ● ●

Fishwick P (2011) CAP4800/5805 Computer Simulation: System Dynamics Lecture Slides (http://www.cise.ufl.edu/~fishwick/cap4800/sd1.ppt ) Kirkwood CW (1998) System Dynamics Methods: A Quick Introduction (http://www.public.asu.edu/~kirkwood/sysdyn/SDIntro/SDIntro.htm ) Morecroft JD (2007) Strategic Modelling and Business Dynamics. Wiley, Chichester, UK. Sterman JD (2000) Business Dynamics: Systems Thinking and Modeling for a Complex World. McGraw Hill, Boston, USA. Proceedings of the International System Dynamics Conference (1983-2011) (http://www.systemdynamics.org/society_activities.htm#PastConfs )

© Jiří Jelínek


Cvičení 4 – Systémová dynamika

© Jiří Jelínek


SD diagram modelování chování objektů pomocí zásob, toků a informačních vazeb ● paleta system dynamics ●

●

●

zásoby ● ●

●

některé prvky grafické nebo polofunkční pole – vícedimenzionální hodnoty i vzorce vlastní definice derivace v čase

toky - definice toku

© Jiří Jelínek


32

●

dynamická proměnná ● ● ●

●

pomocný prvek zpřehlednění diagramu konstanta, závislá hodnota

link ●

zobrazení příčinné vazby vč. označení ●

● ● ●

© Jiří Jelínek

doplňovací mechanizmus

plná čára – příčinná vazba čárkovaná čára – počáteční hodnota možnost zavedení zpoždění – jen značení Modelování a simulace

33

●

smyčka (loop) ●

●

stín (shadow) ● ● ●

●

pouze grafický prvek pro označení charakteru zpětnovazební smyčky provázaná kopie skladu, toku, dynamické proměnné zpřehlednění diagramu u hierarchických diagramů – icon – zástupce

možnost užití polí – multidimenzionální data

© Jiří Jelínek


34

Úkol ●

Navrhněte model ekosystému fox-rabbit.

●

Do ekosystému doplňte problém potravy pro králíky

© Jiří Jelínek


35

© Jiří Jelínek


Sběr a analýza dat záložka analysis ● data set ●

●

●

statistics ●

●

základní statistika souboru

data pro histogramy a 2D histogramy ●

●

sběr dat do datového skladu

opět statistika

přímé (odkaz na proměnnou) nebo následné (s využitím datových skladů) zobrazování v grafech ●

© Jiří Jelínek

lze více řad Modelování a simulace

38

Úkol ●

Navrhněte model koloběhu vody v přírodě.

© Jiří Jelínek


Další SD funkce ●

pulse, pulseTrain ●

●

ramp ●

●

jednotkový skok s danou výškou

delay, delayInformation, delayMaterial, ●

●

rostoucí hodnota – náhrada sigmoidy

step ●

●

jednotkový impulz nebo jejich řada

liší se zpracováním situace při změně zpoždění

delay1, delay3 ●

© Jiří Jelínek

exponenciální vyhlazování vstupu a zpoždění Modelování a simulace

44

●

smoth, smoth3 ●

●

forecast, trend ●

●

exponenciální vyhlazování vstupu rozsah vstupního okna (averageTime), horizont

trend předpověď hodnoty s daným počátečním trendem ● podobné forecast ●

●

ekonomické funkce – npv, npve

© Jiří Jelínek


12 9

DISKRÉTNÍ UDÁLOSTI (DES)

při návrhu slidů byly využity materiály Peera-Olafa Sieberse (http://www.cs.nott.ac.uk/~pos/g54sim/index2011.html)

© Jiří Jelínek


13 1

Příklad - kavárna návštěvníci ● obsluha ● dveře ● sklo ●

© Jiří Jelínek


13 2

Terminologie ●

objekty ●

entita individuální elementy, jejichž chování či stav jsou sledovány ● organizovány ve třídách a množinách (osoby v autobusu, typy výrobku) ● odlišitelné pomocí hodnot atributů ●

●

zdroj elementy, které jsou potřebné a modelované pro „zpracování“ entit ● nejsou modelované individuálně (jen počitatelné - lidé na zastávce, dělníci v podniku) ●

© Jiří Jelínek


13 3

●

chování entit ●

entity se vyvíjejí - mění stavy událost – bod v čase, kdy dochází ke změně stavu entity ● aktivita – operace vyvolaná událostí měnící stav entity ●

●

stavy entity aktivní (obdélník) – entita se přímo účastní (zahrnuje i spolupráci různých tříd entit) - trvání lze definovat dopředu vhodným pravděpodobnostním rozložením ● pasivní, dead (kruh) – bez spolupráce, entita čeká na událost - trvání nelze odhadnout v předstihu (vychází z časování událostí) ●

© Jiří Jelínek


13 4

Diagram aktivit ●

zavřít

kroky návrhu identifikace tříd entit ● identifikace aktivit, kterých se účastní ● propojení těchto aktivit ● tvoří se cykly ●

venk u

připr aven

objedná

pije

čeká

zákazník sklenice obsluha dveře čistá

© Jiří Jelínek

příchod

čeká

plná

myje

špina vá


13 5

Příklad DE modelování ●

úloha úředník obsluhuje v bance zákazníky, kteří přijdou nebo zavolají ● dává přednost přítomným zákazníkům ● zákazníci se řadí do front (FIFO) ● volající nikdy nezavěsí ●

●

třídy ● ● ●

© Jiří Jelínek

úředník volající zákazník přítomný zákazník Modelování a simulace

13 6

●

diagram aktivit úředníka

obsluha

© Jiří Jelínek

čeká

telefonuje


13 7

●

diagramy aktivit zákazníků fronta

příchod

obsluhován

mimo

© Jiří Jelínek

fronta

hovoří

volání

mimo


13 8

●

propojené diagramy zákazníků a úředníka

fronta

příchod

obsluha

mimo

© Jiří Jelínek

fronta

čeká

hovoří

volání

mimo


13 9

DE simulace ●

třífázový přístup ●

události rozděleny do dvou skupin ●

B (booked) – události jsou vázány na bod v čase ●

●

C (conditional) – jejich výskyt závisí na podmínkách modelu a jeho běhu ●

© Jiří Jelínek

obvykle příchody (např. zákazníků k úředníkovi) nebo ukončení aktivity

obvykle start aktivity (opuštění pasivního stavu)


14 0

●

propojené diagramy zákazníků a úředníka

B1

fronta

fronta

C1

příchod

obsluha B2 mimo

© Jiří Jelínek

C2

čeká

B3

hovoří

volání

B4 mimo


14 1

S

●

fáze řešení ●

A, B, C

běh simulace řízen B událostmi ● ve fázi B nezačíná obsluha ●

nastavení času – nalézt další nejbližší čas s nějakou událostí, posun do tohoto času, vložit všechny entity s událostí B v tomto čase do seznamu

provedení všech událostí B pro entity v seznamu v daném čase

projít všechna C

+

nějaká aktivita? čas vypršel?

-

+ S © Jiří Jelínek


14 2

© Jiří Jelínek


Cvičení 6 – Modelování pomocí diskrétních událostí

© Jiří Jelínek


49

Process modeling library ●

entita – agent ●

●

síť, kterou entity procházejí ●

●

možnost definice vlastních tříd entit (podtřídy agent) metody on entry, on exit

source, sink generování a likvidace entit ● různé mechanizmy časování ● generování různých objektů ● možnosti animace ●

© Jiří Jelínek


50

●

enter, exit ● ●

●

vkládání a odebírání entit z jiných diagramů (statechart) externí a interní porty

hold – zarážka ●

metoda setBlocked()

split – duplikace entit ● combine - vytvoření nových entit ze starých ●

●

© Jiří Jelínek

spojení dílů na lince


51

●

select Output ● ●

●

pravděpodobnostní směrování – zmetky deterministické směrování

queue – fronta ● ● ● ●

různé algoritmy – FIFO, LIFO, priorita, porovnání entit kapacita možnost preempted (předbíhání) a timeout výstupu různé triggery – onEnter, onAtExit, onExit, onRemove

match – synchronizace dvou proudů ● restricted area start, end ●


omezený počet entit uvnitř – omezené prostory Modelování a simulace

52

Seskupování entit ●

batch, unbatch – shromáždění entit do jedné nové ●

●

pickup, dropoff – přidání, odebrání entit ●

●

balení cestující v autobuse

assembler – sestavení nové entity

© Jiří Jelínek


53

Další ●

delay – zpoždění ●

●

nastavitelné

conveyor – pás ●

© Jiří Jelínek

zachovává pořadí a mezery


54

Prostředky něco, co je v určitém místě potřeba, ale nesleduje se to individuálně ● resource pool – zdroj prostředků ●

●

●

seize, release - přidělení a odejmutí prostředků ●

●

přidělované entitám – lidé na lince včetně fronty (skladu)

service – přidělení prostředku a zpožděné odebrání

© Jiří Jelínek


55

Čas clock – hodiny pro simulační čas ● TimeMeasureStart , End ●

● ●

© Jiří Jelínek

měření času, který stráví entita mezi značkami možno užít pro uložení času k entitě


56

Tvorba vlastní entity ●

vlastní modifikace proměnných i metod

●

nová podtřída třídy Agent ● ●

© Jiří Jelínek

parametry = argumenty konstruktoru proměnné public


61

EXTERNÍ KONEKTIVITA

© Jiří Jelínek


62

Textové soubory ●

soubor x URL ●

setMode, setURL

otevření a uzavření se neřeší ● URL ●

●

●

pouze čtení

soubor ●

read – nastavení separátoru ●

●

write, write-append ●

© Jiří Jelínek

readLine, readString, readInt/Long/Double/Byte

print, println Modelování a simulace

64

Soubor pro excel ●

soubor „xlsx“ musí existovat! ●

●

setFileName

postupné budování struktury a obsahu ● ● ● ● ●

© Jiří Jelínek

info o listech – getNumberOfSheets, getSheetName, getFirst/LastRow/CellNum (index od 1) vytváření buněk - createCell plnění buněk – clearCell, setCellValue, setCellFormula čtení buňek – getCellFormula, getCellNumericValue, getCellDateValue, readTableFunction, … další - evaluateFormulas Modelování a simulace

66

Databáze interně Excel/Access (stejná verze Office – 32/64b) a MS SQL Server – DB musí existovat! ● další přes JDBC driver (např. MySQL) ●

●

●

nutno doinstalovat

dotazy i aktualizace pomocí SQL ● ● ●

getValue – pouze jedna hodnota getResultSet – dále zpracování přes while cyklus getMatrix – 2D pole daného typu ●

String[][] o=(String[][])database.getMatrix("select* from data","String"); ● System.out.println(o[1][1]); © Jiří Jelínek


68

MODELY S PROSTOROVÝM USPOŘÁDÁNÍM © Jiří Jelínek


69

Network based modeling – space markup ●

pro modelování založené na fyzickém uspořádání ● ●

●

network ● ●

●

sklady doprava definovaná síť skupina grafických elementů definující síť

prvky ●

prostory - rectangular Node, polygonal Node, Point ● body – attractor (čekání v prostoru) ● cesty – path ● sklad - palletRack © Jiří Jelínek


70

●

moveTo ●

●

resourceSendTo ●

●

posun do zadaného grafického prvku po čáře odeslání zdroje přímo (skok)

palletRack ●

© Jiří Jelínek

sklad s uličkou


75

Rail library ●

podobnost s Process Modeling Library ● train a rail car ●

● ● ●

● ● ●

spojování a rozpojování vlaků

railway track a railway point automatická správa výhybek akcelerace a brzdění použití prostředků nebo restricted area pro omezení počtu vlaků na úseku railSettings metody – isEmpty()

© Jiří Jelínek


77

Pedestrian library ●

Process Modeling Library ● prvky ● ● ●

●

služby ● ●

●

serviceWithLines serviceWithArea

překážky ●

●

targetLine rectangularArea (attractor) polygonalArea (attractor)

wall, rectangularWall, circularWall

pedSettings

© Jiří Jelínek


15 3

AGENT BASED SIMULACE

© Jiří Jelínek


15 4

AB modelování systém modelován jako množina autonomních a aktivních entit s vlastním řízením a rozhodováním (agentů) ● popis systému v detailu – mikropohled ●

● ●

modelování elementárních objektů decentralizace

interakce agentů vytváří chování celého modelovaného systému ● vhodné např. pro modelování systémů s lidmi jako prvky ●

© Jiří Jelínek


15 5

Historie prostředí a nástroje ● celulární automaty ● agenti ● multiagentní systémy ●

● ●

zapouzdřené (uzavřené) systémy otevřené systémy ●

●

FIPA 2002

DAI

© Jiří Jelínek


Agent


jednotný přístup k různým oblastem UI Modelování a simulace

Agent ●

příklady ●

●

pohybliví roboti, vyhledávače na WWW, software pro finanční předpovědi, osoby

pojmy pro popis ● ●

© Jiří Jelínek

pozorování - to, co agent zjistí o svém okolí akce - to, čím agent ovlivňuje okolí


Prostředí x agent ●

propojení pomocí senzorů a akčních prvků ●

●

může jít i o metody v programu

pojmy pro popis znak, vlastnost - některý z aspektů prostředí (teplota) ● senzor - prvek vytvářející korelace s vlastnostmi prostředí ●

© Jiří Jelínek


●

problémy v interakci prostředí > agent ● ●

●

fyzikální omezení (přesnost měření) správná interpretace získaných dat

problémy v interakci agent > prostředí ● ●

© Jiří Jelínek

správné chování agenta (reakce) odezva v reálném čase


Kvalita agenta racionální agenti jednají racionálně (korektně) ● racionalita (korektnost) ●

výkonnost ● zjištěné podněty (z prostředí) ● uložené znalosti (v agentovi) ● akce, které umí agent vykonat ●

●

nutné míry ● ● ●

© Jiří Jelínek

objektivní x subjektivní kvalitativní x kvantitativní během x po testech Modelování a simulace

Ideální agent pro každý myslitelný řetězec podnětů agent provádí takové akce, které maximalizují jeho schopnost dosahovat zadané cíle a to na základě informací získaných z podnětů a svých vlastních (vestavěných) znalostí. ● agent musí být umístěn v prostředí, ve kterém dokáže detekovat a realizovat změny ● agenti jsou objekty s vlastním postojem a chováním ●

© Jiří Jelínek


Typy agentů ● ● ● ● ● ● ●

dány způsobem realizace vazby mezi vstupem (sledováním okolí) a výstupem (odpovídající akcí) pravidlový reakční agent s vnitřním stavem cílově orientovaný kvalitativně orientovaný učící se volba podle konkrétní potřeby a modelovaného systému

© Jiří Jelínek


Pravidlový reakční agent Senzory

Agent

Okolí Jak nyní vypadá svět

Pravidla

Co bych měl nyní udělat

Akční členy © Jiří Jelínek


●

pravidla ve formě ●

když podmínka tak akce

bezprostřední reakce na podnět ● krátkozrakost ●

© Jiří Jelínek


Reakční agent s vnitřním stavem Senzory

Agent

Jak se svět vyvíjí

+

Okolí

Vnitřní stav Jak nyní vypadá svět

Jak svět ovlivní moje akce

Pravidla




●

vytváří si vnitřní obraz o okolním světě ● ●

●

vychází i z dalších informací o prostředí ● ●

●

i z několika pozorování za sebou - paměť aktualizuje se zákonitosti světa – skryté znalosti důsledky svých zásahů

náročnější na paměť, ale vidí „dále“

© Jiří Jelínek


Cílově orientovaný agent Senzory

Agent


+

Okolí

Vnitřní stav


Cíle

Jak nyní vypadá svět

Co se stane, když udělám X




snaha splnit zadaný cíl ● „předvídá“ ●

● ●

© Jiří Jelínek

prohledávání plánování


Kvalitativně orientovaný agent Senzory

Agent

Okolí

Vnitřní stav Jak nyní vypadá svět


+


Kvalita dosaženého řešení

Co se stane, když udělám X Jak kvalitní je výsledný stav




●

snaha po maximální „užitečnosti“ ●

●

maximální kvalita vybraného řešení

nejsou explicitně vyjádřené cíle

© Jiří Jelínek


Učící se agent Agent

Standardní činnost

Senzory

Okolí

Kritika

+ Učící se element

Výkonový prvek

Generátor úkolů



17 3

●

CBR ● ●

© Jiří Jelínek

case based reasoning odvození znalostí z příkladů


Prostředí ●

dostupná x nedostupná ●

●

deterministická x nedeterministická ●

●

pokud agent může získat všechny atributy, nemusí pracovat s vnitřním stavem je stav okolí přesně dán minulostí a jednáním agenta?

episodní x neepisodní ● ●

© Jiří Jelínek

lze vazbu na interakci s okolím rozdělit na samostatné podcelky? agent nemusí předvídat daleko dopředu Modelování a simulace

17 5

Vlastnosti agenta ●

diskrétní entita ● ●

●

autonomní ● ●

●

vlastní chování, cíle, strategie vlastní linie řízení schopný adaptace na změny v prostředí schopný modifikace chování

proaktivní ●

© Jiří Jelínek

generování akcí na základě vlastní motivace (a vnitřního stavu)


17 6

Klady a rizika ABM ●

klady ● ●

●

přirozený a relativně jednoduchý popis chování elementárních prvků zachycení náhodných jevů

náhodné vlivy ● ● ●

© Jiří Jelínek

celek je více než souhrn částí – interakce mezi prvky náhodný jev může být charakterizován mimo vlastnosti částí (agentů) příklad – dynamika dopravní zácpy


17 7

●

vhodné užití úlohu lze přirozeně popsat jako (dynamicky se měnící) interakci jednotlivých elementárních prvků – např. sociální sítě ● při požadavku na sledování agenta ve zvoleném prostoru – např. klasický 2D geoprostor ● pokud je nutné, aby byl model tvořen z objektů schopných adaptace ● pokud chceme objekty předvídající chování ostatních ●

© Jiří Jelínek


17 8

Typy agentových systémů ●

založené na příkladu ● ●

●

typologické ● ●

●

specificky popsané empirické jevy např. evoluční studie prehistorických společenství specifické třídy empirických jevů např. simulace jevů vztahujících se k managementu užití krajiny

teoretické abstrakce ● ●

© Jiří Jelínek

čistě teoretické modely např. hejna boidů Modelování a simulace

17 9

ABM ●

rozhodovací procesy agentů závisí na účelu modelu pravděpodobnostní – užití pravděpodobnostních rozložení ● pravidlové – modelování procesu tvorby rozhodnutí ●

●

AB model je komplexní systém tvořený množinou agentů naprogramovaných na určitá pravidla chování

© Jiří Jelínek


18 0

AB simulace ●

definice dříve ●

●

proces návrhu AB modelu modelovaného systému a provádění experimentů s ním za účelem pochopení chování modelovaného systému a návrhu vhodných metod a postupů jeho užití a nastavení (Shannon, 1975)

pojem ABS používán v mnoha oborech ● ●

© Jiří Jelínek

různý obsah pojmu agent a multiagentní systém lze tak označit téměř cokoliv, záleží na přístupu


18 1

ABS přístupy ●

multiagentní rozhodovací systémy ● ●

●

obvykle vložení (zabudovaní) agenti nebo jejich simulace důraz na rozhodovací procesy

multiagentní simulační systémy použity pro simulaci nějakého jevu či oblasti z reálného světa a jevů v něm ● např. The Sims – interaktivní organizační ABS ●

© Jiří Jelínek


18 2

ABS - příklady ●

biologie ●

skupinové chování http://ccl.northwestern.edu/netlogo/models/Flocking

●

sociologie ● ●

párty - http://ccl.northwestern.edu/netlogo/models/Party dopravní systém http://ccl.northwestern.edu/netlogo/models/TrafficBasic

●

městská dynamika http://ccl.northwestern.edu/netlogo/models/UrbanSuiteEconomicDisparity

© Jiří Jelínek


18 3

●

sociální vědy ●

●

ekonomika ●

●

burza, samoorganizující se trhy (aukce), obchodní sítě, chování zákazníků, volné komoditní trhy

ekologie ●

●

dynamika sociálních sítí, dynamika bojů, vzestup a pád společenství, skup. učení, epidemie, nepokoje

oběť x predátor, krajinný management, skupinové chování ptáků a ryb, růst deštného pralesa

politika a politologie ●

© Jiří Jelínek

soupeření stran, zdroje a vzory politického násilí, sdílení moci Modelování a simulace

18 4

Tvorba ABS modelu ●

● ● ● ● ●

identifikace aktivních entit – agentů definice jejich stavů a chování (stavové diagramy) vložení do prostředí vytvoření vazeb mezi nimi testování modelu validace modelu ● ● ●

© Jiří Jelínek

sledováno systémové chování jako celku validace na mikroúrovni makropohled v DES/ABS modelech


18 5

Příklad ●

bankovní model v ABS flexibilní chování při velkém počtu volajících ● zapamatování předchozích zkušeností – paměť agenta ● modelování WoM ohledně kvality služeb konkrétního úředníka ●

© Jiří Jelínek


18 6

Užití ABS ●

operační výzkum ●

●

kombinace DES / ABS modelů, postup jako DES, nahrazení pasivní DES entity aktivními agenty, obvykle ve větším počtu (popis pomocí stavových diagramů, může být vzájemná interakce)

reálné aplikace dříve především teoretické věci ● dnes doprava, finance, SCM, energetika, zdravotnictví, sociální politika ●

●

v praxi často kombinace DES / ABS

© Jiří Jelínek


18 7

ABS nástroje ●

SW ● ●

© Jiří Jelínek

free – Swarm, Repast, NetLogo, SeSAm, GreenFoot komerční – AgentSheets, AnyLogic, …


188

Porovnání DES

ABS

Procesně zaměřené, detailní modelování celého systému

Vychází z individuí, modeluje agenty a jejich interakce

Top down přístup

Bottom up přístup

Jedna základní linie řízení

Každý agent má vlastní řízení

Pasivní entity, jsou ovládané systémem, inteligence modelované systémem

Aktivní prvky, proaktivní, vlastní inteligence

Základním prvkem fronta

Nepracuje s frontami

Průchod entit systémem, makromodel

Makrochování není modelováno – vzniká z mikrochování agentů

Vstupní rozložení a distribuce pravděpodobnosti často vycházejí z reálných měření

Vstupní údaje často založeny na teoriích a subjektivních datech a názorech

© Jiří Jelínek


18 9

Zdroje ●

●

● ●

●

Bonabeau (2002). Agent-based modeling: Methods and techniques for simulating human systems. In: Proceedings of the National Academy of Science of the USA. 99:7280-7287. Macal and North (2007). Agent-based modeling and simulation: Desktop ABMS. In: Henderson et al. (Eds.). Proceedings of the 2007 Winter Simulation Conference. Washington DC, Dec. 9-12. Shannon (1975). Systems simulation: The art and science. PrenticeHall: Englewood Cliffs, NJ. Siebers and Aickelin (2008) Introduction to multi-agent simulation. In: Adam and Humphreys (Eds.). Encyclopedia of Decision Making and Decision Support Technologies, Pennsylvania: Idea Group Publishing, pp 554-564. Siebers et al. (2010). Discrete-event simulation is dead, long live

agent-based simulation! Journal of Simulation, 4(3) pp. 204-210. © Jiří Jelínek


Multiagentní modelování

© Jiří Jelínek


80

Úvod ●

vytvoření agentů ● ●

●

aktivní prvek – samostatná třída možnost zobrazení vazeb

import agentů do hlavní třídy Main ● ●

existence a pohyb agentů v prostředí – space and network kolekce – agent population ● ●

●

přenos parametrů – stejný mechanizmus jako mezi simulation main a main replikace v Main a metoda getIndex()

help v API

© Jiří Jelínek


81

Synchronizace časování činnosti agentů ● asynchronní ●

●

●

„spojitý“ čas – možnost časování na libovolný okamžik

synchronní ● ●

kroky - provádění akcí agentů synchronně v krocích cyklická událost v Main ●

for( Person p : people ) p.step(); ● nebo space and network v Main a Enable steps ● události onBeforeStep(Main), onBeforeStep(Agent), onStep(Agent), onAfterStep(Main) © Jiří Jelínek


82

Prostředí ●

různé typy ● ● ●

rozměry, poloha v Main - API layout, network type, connections spojité 2D, diskrétní 2D, spojité 3D, GIS ●

●

celulární automaty

API ●

spaceHeight(), spaceWidth() ● setNetwork…(), applyNetwork(), getNetworkType() ● getRandomAgent(), getAgentCollection() ● getAgentAtCell() – diskrétní 2D © Jiří Jelínek


83

●

kolekce ● ●

size(), iterator(), get(int index) dynamická správa prvků v replikovaných kolekcích ●

© Jiří Jelínek

add_people(), remove_people()


84

Agent ●

odkaz na Main ●

●

get_Main()

pohyb v prostředí ●

© Jiří Jelínek

podle typu prostředí


85

Spojitý 2D ●

poloha (v Agentovi) ●

setLayoutType( type ) ● applyLayout() – relocating ● getX(), getY(), distanceTo( Agent other ) ● setXY(double x, double y) – spojitý 2D ●

pohyb událost OnArrival ● jumpTo(x, y ), moveTo(x, y ), stop(), isMoving() ● getTargetX(), getTargetY(), getVelocity(), getRotation(), timeToArrival ● setVelocity(newVelocity ), setRotation(rotation ) ●

© Jiří Jelínek


86

Spojitý 2D ●

spojení ●

getConnections(), getConnectionsNumber(), getConnectedAgent( int index ) ● connectTo( Agent a ), isConnectedTo( Agent a ), ● disconnectFrom( Agent a ), disconnectFromAll() ●

sítě různé nastavení propojení agentů ● Random, Distance Based (all in range), Ring (ring Lattice), Small world (Ring s výjimkami), Scale Free (hubs and hermits) ● environment.setNetworkRingLattice( 5 ) environment.applyNetwork() – reconnecting ●

© Jiří Jelínek


87

Diskrétní 2D ●

poloha – směry podle světových stran (NORTH, NORTHWEST) ●

●

int getR(), getC()

pohyb ● ●

© Jiří Jelínek

jumpToCell( int r, int c ), moveToNextCell( int direction ), findRandomEmptyCell(), jumpToRandomEmptyCell()


88

Diskrétní 2D ●

modely okolí ● ●

●

Moorův model – 8 sousedů Euklidovský model – 4 sousedi

okolí ●

© Jiří Jelínek

getAgentAtCell( int r, int c ), getAgentNextToMe( int dir ), getNeighbors()


89

Komunikace agentů zprávy ● deliver ●

přímé odeslání ihned ● deliver(), deliverToAllConnected(), deliverToRandomConnected(), … ●

●

send nastavení odeslání do události bezprostředně následující po vykonávané ● send(), sendToAll(), sendToRandom(), sendToAllConnected(), … ●

© Jiří Jelínek


90

●

zprávy ●

send( Object msg, Agent dest ), send( Object msg, int mode ) ●

●

deliver( Object msg, Agent dest ), deliver( Object msg, int mode ), receive( Object msg ) ●

●

po dané akci

v rámci aktuální akce

mode ●

ALL, ALL_CONNECTED, ALL_NEIGHBORS ● RANDOM, RANDOM_CONNECTED (spoj.), RANDOM_NEIGHBOR (disk.) ●

statechart_name.receiveMessage( msg );

© Jiří Jelínek


19 3

Náhodné jevy

© Jiří Jelínek


19 4

Úvod v simulacích velmi často náhodné proměnné ● 2 cesty získání potřebných hodnot ●

●

konkrétní realizace náhodné proměnné získat na reálném systému a tyto realizace pak použít při simulaci ●

●

potřeba velkého množství hodnot při experimentech

pozorováním reálného systému zjistit pravděpodobnostní zákonitosti (tj. stanovit typ rozdělení náhodné proměnné a odhadnout její parametry) generovat hodnoty řídící se daným rozdělením ● prakticky jediná možnost ●

© Jiří Jelínek


19 5

Generátor náhodných čísel ●

požadavky ●

dobré a stabilní vlastnosti ●

●

generátor musí mít dostatečně dlouhou periodu ●

●

© Jiří Jelínek

vytvořená posloupnost generovaných hodnot se musí maximálně přibližovat posloupnosti náhodných čísel posloupnost generovaných hodnot se nesmí opakovat

procedura generování musí být dostatečně rychlá


19 6

●

lze pohlížet i jako na posloupnost k náhodných číslic α1, α2,…, αk a můžeme ho zapsat ve tvaru: r

●

 1  2  2   kk 10 10 10

kde α1, α2,…, αk jsou číslice 0, 1,…, 9 a kde realizace každé číslice má pravděpodobnost 10-1

© Jiří Jelínek


19 7

Generování náhodných čísel ●

mechanický generátor použití osudí, ve kterém je 10 stejných koulí označených čísly 0, 1,…, 9 ● postupně pro i = 1, 2,…, k vyjmeme jednu kouli, číslici zapíšeme na příslušnou pozici a kouli vrátíme do osudí ● pro počítačovou simulaci nevhodné ●

© Jiří Jelínek


19 8

●

fyzikální generátory založené na fyzikálních jevech, které mají náhodný charakter ● např. radioaktivní rozpad, šum elektronky apod. ● problémem nutnost připojení generátoru k počítači ● získaná čísla opravdu nahodná, ale nelze je reprodukovat ●

© Jiří Jelínek


19 9

●

tabulky náhodných čísel zejména při ručních výpočtech ● k jejich tvorbě užity rozsáhlé soubory dat získané k jiným účelům (např. čísla v telefonním seznamu) ● např. Tippetovy tabulky obsahující 40 000 náhodných číslic (1927) nebo tabulky RAND Corp. obsahující 1 000 000 náhodných číslic (1955) ● pro počítačové experimenty většího rozsahu opět nevhodné (opakující se hodnoty) ●

© Jiří Jelínek


20 0

●

aritmetické generátory ● ● ● ●

© Jiří Jelínek

založeny na rekurentním vztahu typu xn+1 = f ( xn , xn-1 ,..., x0 ) další člen posloupnosti generovaných hodnot zavisí na hodnotách předchozích členů nejedná se o opravdová náhodná čísla > pseudonáhodná čísla


20 1

Von Neumannův aritmetický generátor 1946 ● algoritmus ●

vybere se vhodné počáteční číslo x0 o 2k číslicích ● číslo se umocní ● z druhé mocniny se vybere prostředních 2k číslic ● získané číslo se považuje za další prvek posloupnosti ● návrat na krok 2 ●

nevýhodou je malá perioda generátoru, proces generování je pomalejší ● generovaná posloupnost nevyhovuje některým testům náhodnosti ●

© Jiří Jelínek


20 2

Příklad ●

Nechť je dáno počáteční číslo x0 = 2589. Vygenerujte prvních 5 členů posloupnosti pseudonáhodných čísel. x 2589 0

© Jiří Jelínek

x02

06702921

x1

7029

x12

49406841

x2

4068

x22

16548624

x3

5486

x32

30096196

x4

0961

x32

00923521

x5

9235 Modelování a simulace

20 3

Aritmetické generátory ●

nejrozšířenější lineární kongruenční generátory D. H. Lehmer, 1948 ● generátor je založen na vztahu: xn 1  axn  c  mod m ● x0 je počáteční hodnota posloupnosti, a a c jsou vhodně zvolená čísla, číslo m se nazývá modul ● hodnoty posloupnosti jsou celočíselné zbytky po dělení číslem m ● generované hodnoty tedy náleží do množiny {0;1;2;...;m-1} xn ● generování v intervalu (0; 1) (0 vynecháme): rn  ●

m

© Jiří Jelínek


20 4

●

posloupnost generovaných hodnot je konečná a má periodu P ≤ m ●

po uplynutí periody se posloupnost opakuje

výše popsaný lineární kongruenční generátor se nazývá smíšený ● v případě c = 0 dostáváme: xn1  axn  mod m ●

●

●

multiplikativní (Lehmerův) generátor

aditivní (Fibonacciův) generátor xn1  xn  xn1  mod m

© Jiří Jelínek


20 5

Příklady xn1  65539 xn mod 231

●

IBM

●

Millerův a Prenticův generátor xn1  xn2  xn3 mod 3137 ●

© Jiří Jelínek

perioda 9 843 907


Pravděpodobnostní rozložení užití generátoru pseudonáhodných čísel splňujících danou pravděpodobnost výskytu jednotlivých hodnot ● podle charakteru ●

● ●

© Jiří Jelínek

spojitá diskrétní


20 7

Rovnoměrné rozložení ●

nezávislé hodnoty rovnoměrného rozdělení z intervalu (a; b) – hod kostkou ●

spojité

nejčastěji na (0; 1) ● rozdělení můžeme popsat hustotou pravděpodobnosti ●

●

zápis R(a,b) http://cs.wikipedia.org/wiki/Rovnom%C4%9Brn%C3%A9_rozd%C4%9Blen%C3%AD

© Jiří Jelínek


20 8

●

distribuční funkce

●

střední hodnota

●

rozptyl

●

rovnoměrné rozdělení z intervalu (0; 1): R(0; 1), jeho konkrétní realizace r

© Jiří Jelínek


20 9

Normální (Gaussovo) rozdělení ●

spojité rozdělení - neomezeno ●

např. výskyt chyb , doba výroby, cestovní časy

●

rozdělení můžeme popsat hustotou pravděpodobnosti

●

zápis: N(μ; σ2)

http://cs.wikipedia.org/wiki/Norm%C3%A1ln%C3%AD_rozd%C4%9Blen%C3%AD © Jiří Jelínek


21 0

●


●

střední hodnota

●

rozptyl

●

normální rozdělení N(0; 1) je označováno jako normované nebo standardizované

© Jiří Jelínek


21 1

Log-normální rozdělení ●

spojité – pro jevy s převažující hodnotou s exponenciálním rozložením ●

např. ceny, příjmy, populace, délka odbavení

●

rozdělení můžeme popsat hustotou pravděpodobnosti:

●

zápis: LN(μ; σ) http://cs.wikipedia.org/wiki/Logaritmicko-norm%C3%A1ln%C3%AD_rozd%C4%9Blen%C3%AD

© Jiří Jelínek


21 2

●


●

střední hodnota

●

rozptyl

© Jiří Jelínek


21 3

Studentovo (t) rozdělení ●

spojité – pro odhad střední hodnoty za malého počtu příkladů z dané populace ●

např. ceny, příjmy, populace

●

rozdělení můžeme popsat hustotou  pravděpodobnosti:

●

v - stupně volnosti

●

zápis: t(n) http://en.wikipedia.org/wiki/Student%27s_t_distribution

© Jiří Jelínek


21 4

●


●

střední hodnota

●

rozptyl pro n>2

© Jiří Jelínek


21 5

Poisonovo rozdělení ●

diskrétní - rozdělení řídkých jevů ●

např. příchody zákazníků

●


●

zápis: P(λ)

http://cs.wikipedia.org/wiki/Poissonovo_rozd%C4%9Blen%C3%AD © Jiří Jelínek


21 6

●


●

střední hodnota

●

rozptyl

© Jiří Jelínek


21 7

Binomické (Bernouliho) rozdělení ●

diskrétní – výskyt náhodného jevu v n nezávislých pokusech se stejnou pravděpodobností ● ●

např. ano / ne hodnoty s danou pravděpodobností výstupní kontrola, VIP x klasické odbavení

●


●

zápis: B(n; p) http://cs.wikipedia.org/wiki/Alternativn%C3%AD_rozd%C4%9Blen%C3%AD

© Jiří Jelínek


21 8

●


●

střední hodnota

●

rozptyl

© Jiří Jelínek


21 9

Transformace rozdělení ●

někdy nutné pracovat s transformovaným rozdělením ● ●

●

transformace ● ●

●

transformace osy x transformace osy y posunutí změna měřítka

zdroje ●


http://home.ef.jcu.cz/~mrkvicka/vyuka/Pmkn.pdf http://homen.vsb.cz/~oti73/cdpast1/KAP05/PRAV5.HTM Modelování a simulace

22 2

ANALÝZA VSTUPNÍCH DAT

© Jiří Jelínek


22 3

Odhady parametrů základního souboru základní soubor můžeme popsat jeho parametry, např. střední hodnotou μ, rozptylem σ2 atd. ● při praktických úlohách ovšem zpravidla nelze vyšetřit celou populaci ●

●

●

provádíme tzv. náhodný výběr z populace

náhodný výběr popisujeme rovněž jeho parametry, např. výběrový průměr, výběrový rozptyl atd.

© Jiří Jelínek


22 4

parametry populace jsou konstantní, parametry náhodného výběru jsou ovšem náhodné proměnné (provedením jiného náhodného výběru získáme jiné hodnoty parametrů) řídící se výběrovým rozdělením ● známe-li pro konkrétní výběrovou charakteristiku její výběrové rozdělení, jsme schopni odhadnout parametr celé populace ●

© Jiří Jelínek


22 5

Typy odhadů ●

bodový odhad ● ●

●

parametr populace aproximujeme jedním číslem nevíme nic o jeho přesnosti

intervalový odhad ●

© Jiří Jelínek

parametr populace aproximujeme intervalem, ve kterém jeho hodnota leží s určitou pravděpodobností


22 6

Bodový odhad ●

vlastnosti ●

nestrannost (nevychýlenost, nezkreslenost) – asymptotická nestrannost ●

●

vydatnost (eficience) ●

●

s rostoucím rozsahem výběru (počtem příkladů) se zpřesňuje

dostatečnost ●

© Jiří Jelínek

máme-li více nestranných odhadů, potom vybereme ten s nejmenším rozptylem – nejlepší nestranný odhad

konzistence ●

●

odhad je nestranný, pokud se jeho střední hodnota rovná (limitně se blíží s počtem příkladů) hledanému parametru

obsahuje veškerou informaci o sledovaném parametru, kterou výběrový soubor poskytuje Modelování a simulace

22 7

Metody konstrukce bodového odhadu nutno odhadnout typ pravděpodobnostního rozdělení ● exaktní ●

● ●

●

metoda maximální věrohodnosti – věrohodnostní funkce metoda momentů – porovnání výběrových momentů s teoretickými momenty předpokládaného rozdělení pravděpodobnosti

iterativní ●

© Jiří Jelínek

metoda minimalizace chyby – obecnější, nalezení parametrů libovolné funkce (řešitel v Excelu) Modelování a simulace

22 8

Intervalové odhady hledaný parametr aproximujeme intervalem (interval spolehlivosti, konfidenční interval), ve kterém jeho hodnota leží s určitou pravděpodobností (spolehlivost odhadu) ● spolehlivost odhadu ●

označujeme 1 – α, α je hladina významnosti ● zpravidla α = 0,05 nebo 0,01 ● s rostoucí spolehlivostí odhadu roste i šířka intervalu spolehlivosti ● významnost α=0,05 > spolehlivost 95% ●

© Jiří Jelínek


22 9

Typy intervalových odhadů Označme dolní mez konfidenčního intervalu Td a horní mez Th ● Levostranný interval spolehlivosti ●

●

●

Pravostranný interval spolehlivosti ●

●

P(θ >Td ) = 1 – α P(θ
Oboustranný interval spolehlivosti: ● ●

© Jiří Jelínek

P(θ Th )= α / 2 P(Td < θ

23 0

Analýza vstupních dat ●

statistika ● ● ●

© Jiří Jelínek

odhady – odhad střední hodnoty populace ze střední hodnoty vzorku testování hypotéz – zda pozorovaná odchylka byla náhodná statistické modelování – testování jak přesně odpovídá model experimentálním datům


23 1

●

jednoduchá statistika souboru např. pomocí Excelu ● střední hodnota – average(soubor) ● směrodatná odchylka – stdevpa(soubor) ● interval spolehlivosti ●

ve vypočtených mezích (intervalu) od střední hodnoty (průměru) se bude s 95% pravděpodobností pohybovat skutečná střední hodnota (vyšší číslo je horší) ● Confidence.NORM, confidence.T (hladina významnosti; směrodatná odchylka; velikost souboru) ●

© Jiří Jelínek


23 2

Analýza vstupních dat ●

identifikace pravděpodobnostního rozložení ●

●

stanovení rozdílu (chyby)

grafický přístup ●

histogram reálných dat ● ●

● ● ● © Jiří Jelínek

šíře intervalů podle hodnot - počet intervalů cca podle odmocniny z počtu dat šíře intervalů podle pravděpodobností – min. 5 hodnot v intervalu (poč. intervalů = cca počet dat / 5)

histogram předpokládaného rozložení pravděpodobnosti – odhad parametrů vizuální porovnání rozhodnutí o podobnosti subjektivní (lépe kvantitativní) Modelování a simulace

23 3

Chi-square test k intervalů ve vstupních datech ● stanovení nulové a alternativních hypotéz ●

● ●

●

hladina významnosti testu (důvěry – confidence) ●

●

H0: je podle Normal(5,2) Ha: není podle Normal(5,2) významnost α=0,05 > spolehlivost 95%

stanovení kritické hodnoty pro Chi2 rozložení ●

© Jiří Jelínek

pro významnost α=0,05 hodnota, kdy 95% rozložení nalevo a 5% napravo, počet stupňů volnosti při známých parametrech = k-1, za každý neznámý parametr -1 (Excel - CHISQ.INV.RT(0,05;k-1)) Modelování a simulace

23 4

●

výpočet Chi2 z dat: ● ● ●

●

Oi – počet pozorovnání v i-tém intervalu Ei – počet očekávaných pozorování v i-tém intervalu n – počet intervalů

porovnání výsledku s kritickou hodnotou a rozhodnutí o H0 ● ●

chi2
množství dat – min. 20, lépe 30 ● http://ulb.upol.cz/praktikum/statistika3.pdf ●

© Jiří Jelínek


91

NÁHODNÉ JEVY V ANYLOGICU

© Jiří Jelínek


92

Pravděpodobnostní rozložení velmi dobře popsána v helpu vč. příkladů použití ● diskrétní ●

uniform_discr – diskrétní rovnoměrné rozložení, ● poisson - >0, výskyt událostí v čase a prostoru, tel. hovory, defekty ve výrobě, geografické distrubuce výskytu rostlin, fronty, časy mezi poruchami / příchody ● binomial – 0 – n, nezávislé opakované pokusy (házení mincí), hry, genetika, zmetky ve výrobě ● geometric – jako exponenciální, model poptávky, návratnost v průzkumech trhu, meteomodely ●

© Jiří Jelínek


93

●

spojitá ● ● ●

● ● © Jiří Jelínek

uniform – zcela nezávislé a stejně pravděpodobné hodnoty normal – symetrická data, není na koncích mezená (lognormal, beta) lognormal – zespoda omezené, koncentrace prachu, trvání nemocenské, konzultační časy, spolehlivost v průběhu životnosti, příjmy, modelování váhy, délky expomential – čas mezi náhodnými jevy (fronty), doba obsluhy, časové údaje se šumem triangular – omezení z obou stran, málo dat, fuzza logika Modelování a simulace

95

EXPERIMENTY V ANYLOGICU

© Jiří Jelínek


96

Typy experimentů ●

Experiment ●

●

nadstavba nad modelem

Simulace základní (Simulation:Main) ● jednotlivé běhy simulace s definovanými parametry ●

●

Změny hodnot parametrů více běhů s pozměněným nastavením ● parameters ●

●

freeform nastavení - „index“ označuje číslo běhu simulace

default UI – nakonec po nastavení ● model time – doplňkové podmínky ● replikace – více běhů s jedním nastavením – vliv náhody ● advanced - multicore © Jiří Jelínek Modelování a simulace ●

97

●

Optimalizace ● ● ● ● ●

optimalizace cílové proměnné / funkce (objective - max, min) odkaz na hlavní objekt simulace (obvykle Main) = „root“ constraints – podmínka pro parametry nastavení (napr. vzájemné vazby mezi nimi) requirements – doplňkové požadavky na řešení uspokojivé (feasible) řešení – splňuje všechny požadavky ●

© Jiří Jelínek

graf nalezených řešení


98

Další možnosti ●

Porovnání experimentálních běhů ●

●

Monte Carlo ●

●

citlivost na změny daného parametru

Kalibrace ●

●

kolekce výstupů pro stochastické modely

Citlivostní analýza ●

●

interaktivní práce s parametry

nastavení parametrů podle zadaného výstupu

Vlastní – kombinace, vlastní scénář

© Jiří Jelínek


MODELOVÁNÍ A SIMULACE

Recommend Documents