User Tools
Site Tools
vybrane_stochasticke_algoritmy_simulovane_zihani_horolezecky_algoritmus
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
vybrane_stochasticke_algoritmy_simulovane_zihani_horolezecky_algoritmus [2017/01/04 12:44] efox [horolezecký algoritmus] |
vybrane_stochasticke_algoritmy_simulovane_zihani_horolezecky_algoritmus [2017/01/04 15:33] (current) efox [simulované žíhání] |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | prvky nebo vztahy mezi nimi mají charakter náhodných jevů nebo náhodných veličin příp. náhodných procesů. Stochastický model uvažuje jednu nebo více náhodných složek a přibližuje se reálným dějům, ve kterých je nahodilá složka většinou přítomná. Ani stochastický model však neodpovídá reálné situaci zcela přesně, ale s určitou pravděpodobností. Příkladem může být regresní model, který popisuje statistickou závislost mezi veličinami. Z modelu lze usoudit, jakých hodnot bude „v průměru“ (nikoliv v jednotlivých případech) nabývat vysvětlovaná závislá proměnná při určité kombinaci hodnot vysvětlujících nezávislých proměnných. | + | ====== pojmy ====== |
| + | * **optimalizační úloha** | ||
| + | * optimalizace je proces změřený na nalezení určitého vyhovujícího řešení nějaké úlohy | ||
| + | * např. hledání parametrů aproximující funkce, nalezení správných konstant na regulaci výrobního procesu, nalezení optimálního rozložení výrobních strojů v hale tak, aby zabíraly co nejméně místa | ||
| + | * účel: **nalézt extrém** v určitém stavovém prostoru | ||
| + | * **pozn. heurestické metody** | ||
| + | * u těhle metod a algoritmů je potřeba nejprve funkci převést do tvaru, který je bhodný pro spravování heurestickými metodami = vzorkování (__protože tyto metody vyžadují diskrétní reprezentaci vzorové funkce !!!!__) PROČ??? | ||
| + | * **fitness funkce** | ||
| + | * každému řešení jednoznačně přiřadím ohodnocení v podobě nezáporného reálného čísla -> čím vyšší číslo, tím lépe vyhovuje úloze | ||
| + | * __optimalizační úloha se potom definuje jako snaha o maximalizaci funkce vhodnosti__ | ||
| + | * **stochastické algoritmy** | ||
| + | * jsou to iterativně výpočetní metody, které v průběhu činnosti používají náhodné operace | ||
| + | * v průběhu řešení připouštějí dočasné zhoršení řešení za předpokladu budoucího zlepšení | ||
| + | * každý krok stochastického algoritmu je zatížený určitou neurčitostí a může vést jak ke zhoršení, tak ke zlepšení modelu | ||
| + | * tato vlastnost umožňuje metodám překonat lokální extrémy | ||
| + | * prvky nebo vztahy mezi nimi mají charakter náhodných jevů nebo náhodných veličin příp. náhodných procesů. Stochastický model uvažuje jednu nebo více náhodných složek a přibližuje se reálným dějům, ve kterých je nahodilá složka většinou přítomná. Ani stochastický model však neodpovídá reálné situaci zcela přesně, ale s určitou pravděpodobností. Příkladem může být regresní model, který popisuje statistickou závislost mezi veličinami. Z modelu lze usoudit, jakých hodnot bude „v průměru“ (nikoliv v jednotlivých případech) nabývat vysvětlovaná závislá proměnná při určité kombinaci hodnot vysvětlujících nezávislých proměnných. | ||
| Stochastické modelování souvisí s vytvářením a řešením stochastických modelů. Má uplatnění spolu s možnostmi provádět simulace. Pomocí sestaveného stochastického modelu lze simulovat průběhy dějů při různých parametrech modelu a pozorovat očekávané chování systému. Z analýzy chování modelu v simulační úloze lze odvodit informace pro rozhodování. | Stochastické modelování souvisí s vytvářením a řešením stochastických modelů. Má uplatnění spolu s možnostmi provádět simulace. Pomocí sestaveného stochastického modelu lze simulovat průběhy dějů při různých parametrech modelu a pozorovat očekávané chování systému. Z analýzy chování modelu v simulační úloze lze odvodit informace pro rozhodování. | ||
| + | |||
| ====== slepý algoritmus ====== | ====== slepý algoritmus ====== | ||
| + | * je základní stochastický algoritmus | ||
| + | * dochází k opakovanému generování náhodných řešení z oblasti a zapamatuje si ho, pokud je řešení lepší než to řešení v předchozím kroku | ||
| ====== horolezecký algoritmus ====== | ====== horolezecký algoritmus ====== | ||
| * **výstup na Everest v mlze a s amnézií** | * **výstup na Everest v mlze a s amnézií** | ||
| * je to technika výpočtu na hledání extrémní funkce (rozuměj - hledám globální extrémy) | * je to technika výpočtu na hledání extrémní funkce (rozuměj - hledám globální extrémy) | ||
| + | * heurestický | ||
| * **princip** | * **princip** | ||
| - vyber náhodné místo (začátek) | - vyber náhodné místo (začátek) | ||
| Line 14: | Line 33: | ||
| - pokračuj, dokud žádná aktuální funkční hodnota není nižší, než v aktuálním místě | - pokračuj, dokud žádná aktuální funkční hodnota není nižší, než v aktuálním místě | ||
| * takovouto postupnou iterací by měl algoritmus dojít k nalezení globálního minima | * takovouto postupnou iterací by měl algoritmus dojít k nalezení globálního minima | ||
| - | * znároznění postupu na funkci iks na druhou - začátek je v bodě 1,5 a terační krok je nastaven na 0,5 | ||
| + | * znázornění postupu na funkci iks na druhou - začátek je v bodě 1,5 a iterační krok je nastaven na 0,5 | ||
| {{:: | {{:: | ||
| * **problém** - co když mám funkci, která je " | * **problém** - co když mám funkci, která je " | ||
| ====== zakázané hledání ====== | ====== zakázané hledání ====== | ||
| ====== simulované žíhání ====== | ====== simulované žíhání ====== | ||
| + | * algoritmus je založen na analogii mezi žíháním tuhých těles a optimalizačním problémem | ||
| + | * při vysoké teplotě jsou částice tělesa náhodně uspořádané v prostoru, takže těleso je roztopené. Potom se teplota postupně snižuje -> všechny částice mají možnost dostat se to rovnovážné polohy -> energie tělesa se snižuje | ||
| + | * při prohledávání stavového prostoru se může lehko stát, že algoritmus uvízně v lokálním minimu - tomu se dá zabránit tím, že vykonáme změny i k horšímu: velikost změny závisí na teplotě -> čím vyšší teplota, tím větší změna k horšímu | ||
| + | |||
| + | {{:: | ||
| + | {{: | ||
| ====== metoda monte-carlo ====== | ====== metoda monte-carlo ====== | ||
Permalink vybrane_stochasticke_algoritmy_simulovane_zihani_horolezecky_algoritmus.1483530288.txt.gz · Last modified: 2017/01/04 12:44 by efox
oeffentlich
