GENEROVÁNÍ NÁHODNÝCH ČÍSEL PSEUDONÁHODNÁ ČÍSLA
Oblasti využití generátorů náhodných čísel 9 Statistika 9 Loterie 9 Kryptografie (kryptologie) 9 Simulace
Simulační modely 9 DETERMINISTICKÉ 9 STOCHASTICKÉ (činnost systému ovlivňovaná náhodnými faktory)
9 KOMBINOVANÉ
Význam variability Podnikové procesy (činnosti) nejsou obvykle deterministické - obsahují různé prvky variability (rozdílná délka jejich trvání)
K provedení simulace je potřeba získat náhodná čísla tj. numerickou realizaci náhodných veličin
ŘEŠENÍ A
B
Přímé zakomponování náhodných jevů (do simulačního modelu), jenž byly stanoveny na základě údajů napozorovaných na real. modelu
1. Stanovení pravděpodobnostních zákonitostí (typ rozdělení náhodné veličiny a její parametry) na základě údajů napozorovaných na reálním modelu
!!! PROBLÉM !!! simulační experimenty běžného rozsahu = několik set tisíc hodnot
2. Generování hodnot náhodných jevů na základě zjištěných pravděpodobnostních zákonitostí v průběhu chodu simulačního modelu
Náhoda „Nic není náhoda“ aneb „Existuje náhoda nebo je vše předurčeno?“ „Náhoda je blbec“, „Nehoda není náhoda“
Náhoda - něco, co může ale nemusí nastat, přičemž existenci či neexistenci daného jevu „nelze“ ovlivnit.
Náhodný pokus, náhodný jev, náhodná veličina, rozdělení z
Náhodný pokus – pokus, jehož výsledek se od jednoho provedení
z
Náhodný veličina – je veličina, jejíž hodnota je dána výsledkem
z
pokusu k druhému (při stejných výchozích podmínkách) obecně mění (hod kostkou, mincí, …)
náhodného pokusu (např. „jednička“ na kostce). Náhodná veličina je určena rozdělením pravděpodobnosti
Rozdělení pravděpodobnosti náhodné veličiny – pravidlo, kterým
každému jevu popisovanému touto veličinou přiřazujeme určitou pravděpodobnost. Rozdělení pravděpodobnosti náhodné veličiny získáme, pokud každé hodnotě diskrétní náhodné veličiny, popř. intervalu hodnot spojité náhodné veličiny, přiřadíme pravděpodobnost.
Distribuční funkce z
Distribuční funkce F(x) – popisuje rozložení pravděpodobnosti mezi náhodné jevy, F(x) je rovno pravděpodobnosti, že náhodná veličina X nabude hodnoty menší nebo rovno x
Pro každé reálné x je distribuční funkce neklesající Pro každé reálné x platí
Hustota pravděpodobnosti, pravděpodobnostní funkce z
Hustota pravděpodobnosti f(x) – derivace spojité distribuční funkce F(x)
z
pro všechna reálná x je
Pravděpodobnostní funkce P(x) – pro diskrétní veličiny
pro všechna reálná xi platí celkový součet f(xi) je roven 1
Hustota pravděpodobnosti, distribuční funkce Normální normované rozdělení N(0,1)
Rovnoměrné rozdělení R(0,1)
F(x) … příklad – hod kostkou
1 5/6 2/3 1/2 1/3 1/6
1
2
3
4
5
6
Střední hodnota, rozptyl, směrodatná odchylka z
Střední hodnota E(x) – charakteristika polohy
z
Rozptyl D(x) – je střední hodnota čtverců odchylek hodnot náhodné veličiny od její střední hodnoty E(x). Charakterizuje variabilitu náhodné veličiny.
z
Směrodatná odchylka – odmocnina rozptylu
Základní druhy rozdělení DISKRÉTNÍ ROZDĚLENÍ
SPOJITÁ ROZDĚLENÍ
Rovnoměrné rozdělení Binomické rozdělení Poissonovo rozdělení Negativně binomické rozdělení Pascalovo rozdělení Geometrické rozdělení Hypergeometrické rozdělení Logaritmické rozdělení
Rovnoměrné rozdělení Normální rozdělení Exponenciální rozdělení Laplaceovo rozdělení Logistické rozdělení Maxwellovo rozdělení Studentovo rozdělení Fischer-Snedecorovo rozdělení Χ² rozdělení (Chí kvadrát)
Exponenciální rozdělení z z z z
nejčastěji používané rozdělení v simulaci generování intervalů mezi po sobě následujícími příchody požadavků, délka trvání činností, výskyty poruch λ – intenzita příchodů, tj.počet příchodů za jednotku času 1/ λ – interval mezi po sobě následujícími příchody
Hustota pravděpodobnosti
Distribuční funkce
Střední hodnota Rozptyl Hustota pravděpodobnosti pro parametry λ = 2
Rovnoměrné rozdělení z z
R(0,1) – základ pro generování dalších náhodných veličin simulace délky trvání činností
Hustota pravděpodobnosti
Distribuční funkce
Střední hodnota
Hustota pravděpodobnosti rovnoměrného rozdělení R(4,8)
Rozptyl
Normální rozdělení z z
zachycení chyby při fyzikálních měřeních a ekonomických pozorováních generování dob trvání činností (! správná volba střední hodnoty, jinak záporné a vybočující hodnoty!)
Hustota pravděpodobnosti
Střední hodnota
Rozptyl Hustota pravděpodobnosti pro parametry μ = 5, σ2 = 1
Poissonovo rozdělení z z
generování počtu příchozích entit do systému, počtu vadných výrobků, počtu vad na jeden výrobek, počet přerušení provozu za danou časovou jednotku λ – intenzita příchodů, tj. průměrný počet příchodů za jednotku času
Pravděpodobnostní funkce
Střední hodnota Rozptyl
Pravděpodobnostní funkce pro λ = 3 a λ = 8
Binomické rozdělení z z
náhodná veličina X popisuje rozdělení počtu nastoupení jevu příznivého v n nezávislých realizacích náhodného pokusu dva parametry: n a p – pravděpodobnost nastoupení příznivého jevu Pravděpodobnostní funkce
Střední hodnota Rozptyl Pravděpodobnostní funkce s parametry n = 10 a p = 0,2
Jaký typ rozdělení vůbec generovat? data známé z reálného systému z stanovení jaké hodnoty proces generuje: spojité nebo diskrétní z stanovení jestli je proces stacionární nebo nestacionární z „oční testy“ – analýza základních charakteristik rozdělení z aplikace statistických testů – testy dobré shody
data neznámé z hledání analogie s jinými procesy z odhady expertů na daný problém
Postup generování náhodných čísel PRIMÁRNÍ GENERÁTORY
generování posloupnosti náhodných čísel s rovnoměrným rozdělením
SEKUNDÁRNÍ GENERÁTORY
transformace rovnoměrně rozdělených veličin na veličiny s libovolným rozdělením
Generování náhodných čísel Nezávislé hodnoty rovnoměrného rozdělení na intervalu (0,1) … R(0,1) R(0,1):
f(x) = 1 pro x ∈(0,1) jinak f(x) = 0
F(x) = 0 pro x ≤ 0 F(x) = x pro x ∈(0,1) F(x) = 1 pro x ≥ 1
Jak generovat náhodná čísla 1. 2. 3. 4.
Tabulky náhodných čísel Mechanické generátory Fyzikální generátory Aritmetické generátory
Tabulky náhodných čísel z z
pro výpočty malého rozsahu (Tippetove tabulky – 40 000 čísel, atd ). po převedení do elektronické podoby počítač z ní načítá náhodná čísla. Příklad tabulky náhodných čísel: 44 48 87 57 84 79 95 32 47 26 35 19 87 30 96 19 86 59 32 00 81 73 70 91 58 76 73 83 31 55 63 53 66 64 55 20 19 46 61 57 86 93 35 27 28 29 68 00
50 14 75 73 92 67 34 75 53 67 76 03 47 47 98 96
Výhoda: kvalitní data Nevýhoda: i nejrozsáhlejší tabulky jsou již malé
Mechanické generátory (TRN generátory) z z z
nejvíce známé hrací kostka při hře, nebo házení mincí. tam, kde na výsledku hodně záleží, jsou pro účely losování zhotoveny speciální přístroje (např. pro sázkové hry podniku SAZKA).
Nevýhoda: pro simulaci na počítači nepoužitelné
Fyzikální generátory (TRN generátory) z
využití jistých fyzikálních pochodů, které mají náhodný charakter, např. počítání intervalů mezi rádioaktivními rozpady jednotlivých atomů, šumové generátory využívající vlastnosti polovodičového přechodu, atd.
z
princip – připojení zařízení, které registruje určité fyzikální pochody k počítači
Výhoda: jsou náhodné Nevýhoda: nelze je reprodukovat, opakovat simulaci za stejných podmínek
Fyzikální generátory (TRN generátory) z
lávové lampy – 60. a 70. léta, obrazy probublávajících barevných kuliček kapaliny v osvětlené zúžené žárovce snímány několika kamerami, tzv. „lavarand“.
z
SG100 – 1999, komerční hardwarový generátor, generování na základě tepelného šumu připojeného rezistoru
z
HotBit – server, kde lze objednat náhodná čísla, generování na základě časového průběhu radioaktivního rozpadu částic, jak je zaznamenáván Geiger- Müllerovou trubicí.
Aritmetické generátory (PRN generátory) z z
z z
nejpoužívanějšími generátory pro účely počítačové simulace, náhodná čísla tvořena aritmetickými procedurami pomocí rekurentních výpočtů v nichž následující číslo deterministicky závisí na jednom či více předchozích číslech. čísla takto získaná označujeme jako čísla pseudonáhodná (jde o výpočet, nikoliv o náhodu) vlastnosti odpovídající RN: nezávislost a rovnoměrné rozložení na požadovaném intervalu
Generování náhodných čísel spočívá v paradoxu, že náhoda může být vypočtena!
Kongruenční generátory Lineární kongruenční generátory (Lehmer, 1948) A) Smíšený B) Multiplikativní C) Aditivní, např.
xn+1 = a xn + c xn+1 = a xn xn+1 = xn + xn-1
(mod m) (mod m) (mod m)
x0, a, c, m – vhodně zvolená čísla x0 – násada, semínko, tzv. seed modulo m (celé číslo, m≠0, zbytek po celočíselném dělení) Proměnná x může nabývat pouze konečného počtu hodnot P (perioda generátoru), platí že
Smíšený lineární kongruenční generátor
n
xn
11xn+9
(11xn+9)(mod 13)
1
7
86
8
2
8
97
6
3
6
75
10
4
10
119
2
5
2
31
5
6
5
64
12
7
12
141
11
8
11
130
0
9
0
9
9
10
9
108
4
11
4
53
1
12
1
20
7
13
7
86
8
Výpočet x2
Vliv nastaveni konstant x, c, a, m na periodu P xn+1 = a xn + c 1,4,0,3,6,2,5, 1,4,0,3,6,2,5, 1,4,0,3,6,2,5,
Vliv nastaveni konstant x, c, a, m na periodu P xn+1 = a xn + c
Vliv nastaveni konstant x, c, a, m na periodu P xn+1 = a xn + c
Testování náhodných čísel Ověření, zda generátor poskytuje hodnoty, které lze považovat za nezávislé hodnoty rozdělení R(0,1). z
z z z
tzv. empirické testy náhodnosti (hodnocení na základě statistik získaných z generovaných posloupnosti a jejich porovnání s hodnotami statistik vypočtenými za předpokladu náhodnosti) testy teoretické, vycházející z teorie čísel, zkoumání parametrů generátoru. žádný test nedává definitivní jistotu, úspěšnost v několika testech zvyšuje důvěru v náhodnost čísel. čísla generovaná počítačem jsou prohlášena za náhodná, jestliže testy nemohou odhalit rozdíl mezi čísly získané aritmetickým generátorem a skutečně náhodnou posloupností.
Metody transformace náhodných čísel na hodnoty náhodných veličin Vygenerujeme náhodné číslo z intervalu R (0,1), to pak transformujeme pomocí vhodné metody na náhodnou veličinu zvoleného rozdělení ( exponenciálního, …)
• • •
Metoda inverzní transformace Zamítací metoda Kompoziční metoda
Metoda inverzní transformace Předpoklad: Existuje rostoucí distribuční funkce F(x) pro náhodnou veličinu X a také funkce k ní inverzní F-1(x) z Nalezne se inverzní funkce k distribuční funkci požadovaného rozdělení. Generuji hodnoty R(0,1) a pomocí inverzní funkce získám požadované hodnoty. Příklad: z
Pokud má požadovaná náhodná veličina distribuční funkci F(x) a máme-li generátor spojitého rozdělení U na intervalu (0,1) lze veličinu X s požadovaným rozdělením získat jako X=F-1(U) ( kvantilová funkce) b F-1 X a
0
1 U
Požadavky na generátory náhodných čísel • dlouhá perioda – generování "dobré" pseudonáhodné posloupnosti (PP) = délka PP by měla být zlomkem délky periody generátoru lineární kongruenční generátor - délka periody minimálně 260, nejlépe volit periodu alespoň o rád vetší, než je druhá mocnina počtu generovaných čísel, někteří autoři doporučují 2131086 • efektivita – uspokojující rychlost, využívání paměti počítače v co nejmenší možné míře
• opakovatelnost – vlastnost důležitá především pro simulační úlohy, existence možnosti generovat shodné pseudonáhodné posloupnosti
• přenositelnost – snadná implementace a plná funkčnost generátoru na různých platformách, hardwarových i softwarových
• „nevypočitatelnost“
– z vygenerované posloupnosti by nemělo být možné v
rozumném čase určit, jaké číslo bude následovat (kasina, internet)
• úspěšnost v empirických testech – ověřování hypotézy H0: "vygenerované hodnoty jsou nezávislá náhodná čísla z rovnoměrného rozdělení na intervalu (0,1)".
• skok dopředu – je schopnost genetátoru spočítat xn+v na základě znalosti xn popřípadě x0 aníž bychom počítali hodnoty mezi
Literatura z z z z z z z z z z z z z z
Hušek, R., Lauber,J. Simulační modely, SNTL/Alfa Praha 1987 Kuneš, J., Vavroch, O., Franta,V. Základy modelování, SNTL Praha 1989 Rábová, Z., Češka, M., Zendulka, J. Modelování a simulace, SNTL Praha 1982 Dlouhý, M., Fábry, J., Kuncová, M., Hladík, T. Simulace podnikových procesů, Computer Press, a.s. Brno, 2007 Keřkovský, M., Moderní přístupy k řízení výroby, C. H. Beck Praha 2001 Havrila, M., Počítačové projektovanie, Prešov, 2008, ISBN 978-80-553-0047-4 Havrila, M., Trendy v počítačovom projektovaní výrobných systémov, online cit. [201303-30], dostupné z http://www.fvt.tuke.sk/journal/pdf09/1-str-88-91.pdf Havrila, M., Tendencie v rozvoji počítačovej simulácie výrobných systémov. Manufacturing Engineering/Výrobné inžinierstvo, FVT TU Prešov, č. 3, 2008, VII, str. 21-23, ISSN 1335-7972 Geta Centrum s.r.o, Optimalizace pracoviště v digitální továrně, Baumbruk, M., Výhody integrace komponent digitální továrny: od PLM až k virtuálnímu ověřování, Siemens PLM software Lacko, B., Navrhování systémů řízení, Studijní text, Brno, 2006 Leeder, E., Digitální továrna – mocný nástroj pro průmyslovou výrobu, AUTOMA 7/2008, s.56-58, Mareček, P., Virtuální simulace výroby aneb Digitální továrna, IT SYSTEMS 9/2006, on-line cit. [2013-12-4], dostupné z http://www.systemonline.cz/rizeni-vyroby/virtualni-simulace-vyroby-aneb-digitalni-tovarna.htm PLM Siemens, online cit. [2014-02-28], https://www.plm.automation.siemens.com/en_us/academic/resources/tecnomatix/index.shtml
