User Tools

Site Tools

vybrane_stochasticke_algoritmy_simulovane_zihani_horolezecky_algoritmus

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í.

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

  • 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)
  • heurestický
  • princip
    1. vyber náhodné místo (začátek)
    2. pokud hledám minimum, tak vyber sousední místa a vypočítej, které z daných míst je optimálnější (tudíž - má nejnižší hodnotu)
    3. pokud je funkční hodnota v nejlepším sousedícím místě nižší- označ toto místo za “nový začátek” a pokračuj od kroku 2
    4. 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
  • 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 “vlnka”? algoritmus začne na nevhodném místě (a teď hádám, ale to asi bude záviset i na velikosti toho iteračního kroku, jestli bude schopen z toho lokálního minima “vyskočit” ?) - a pokud začne algoritmus vyhledávat na nesprávném místě, uvízne v lokálním minimu. Stejně tak, pokud bude fce konstatní, tak za extrémní funkci označí počáteční místo.

zakázané hledá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

Permalink vybrane_stochasticke_algoritmy_simulovane_zihani_horolezecky_algoritmus.txt · Last modified: 2017/01/04 15:33 by efox

oeffentlich