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 13:12] efox [horolezecký algoritmus] |
vybrane_stochasticke_algoritmy_simulovane_zihani_horolezecky_algoritmus [2017/01/04 15:33] (current) efox [simulované žíhání] |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== pojmy ====== | ====== pojmy ====== | ||
| - | * **stochastický model** | + | * **optimalizační úloha** |
| - | * 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í. | + | |
| - | | + | |
| * optimalizace je proces změřený na nalezení určitého vyhovujícího řešení nějaké úlohy | * 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 | * 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 | ||
| Line 9: | Line 6: | ||
| * **pozn. heurestické metody** | * **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Č??? | * 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 | * 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__ | * __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 | * 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í | * 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 | * 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 | * 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í. | ||
| Line 22: | Line 21: | ||
| ====== 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í** | ||
| Line 39: | Line 40: | ||
| ====== 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.1483531953.txt.gz · Last modified: 2017/01/04 13:12 by efox
oeffentlich
