**[[..:05_rozbory_presnosti|Rozbory přesnosti]]**
**<<** [[05_rozbory_presnosti:0507_rozbor_presnosti_modelovanim|7. Apriorní rozbor modelováním úloh s vyrovnáním (i bez)]]
8. Globální optimalizační algoritmy
===== Úvod =====
###
Globální optimalizační algoritmy slouží k nalezení vhodného (optimálního) řešení problému zejména v případech, kdy není znám matematický popis řešení problému. Tyto metody jsou v principu velmi jednoduché, jsou založeny na různých způsobech prohledávání prostoru řešení a prakticky je nelze využít bez počítače.
Na rozdíl od ostatních kapitol této monografie zde nebudou uváděna odvození ani důkazy, naprostá většina metod to ostatně ani neumožňuje, anebo je důkaz a princip fungování dostatečně ilustrativní sám o sobě. Hlavním pramenem informací v této oblasti je monografie Thomase Weise ([(Weise, T.: //Global Optimization Algorithms - Theory and Application//. Elektronická monografie, on-line dostupné z: http://www.it-weise.de/projects/book.pdf.)]), dostupná on-line (v současnosti ve druhém vydání). Pokud není v textu této kapitoly uvedena jiná citace, lze tam nalézt další informace a literaturu. Hlavním účelem zařazení této kapitoly bylo seznámení s těmito algoritmy a jejich hlavními variantami, úplný výčet metod není cílem a ani není možný, metody stále vznikají a jsou zdokonalovány. Mnohé metody jsou také nepoužitelné nebo nevhodné k využití v oblasti inženýrské geodézie a jsou uváděny zejména pro celkový přehled. V českém jazyce lze některé informace nalézt také v [(Tvrdík, J.: //Evoluční algoritmy//. Učební texty doktorského studia, Přírodovědecká fakulta Ostravské univerzity, 2004. 15.8.2011. On-line dostupné z adresy: http://prf.osu.cz/doktorske_studium/dokumenty/Evolutionary_Algorithms.pdf.)].
Společným prvkem všech globálních optimalizačních algoritmů je potřeba znalosti prostoru (resp. jeho ohraničení), kde se nachází hledané řešení (nebo je přípustné), a potřeba znalosti hodnotící funkce (tzv. „fit") funkce, která posuzuje kvalitu řešení. Symbolicky lze hodnotící funkci zapsat:
$$f=f\left(x_1,x_2,\dots ,x_n\right) , $$
kde $x_1,x_2,\dots ,x_n$ jsou optimalizované neznámé hledaného řešení. Lze různými postupy vyhodnocovat a optimalizovat více funkcí současně. Již použité a minimalizované hodnotící funkce jsou např. podmínka metody nejmenších čtverců $\left[pvv\right]=min$, nebo podmínka normy L1 $\left[\left|pv\right|\right]=min$.
Zásadním rozdílem oproti doposud prováděným výpočtům, kde byla také prováděna optimalizace, např. metodou nejmenších čtverců, je v přístupu k řešení. U metody nejmenších čtverců je akceptováno pouze ono nejideálnější globální minimum, zde se za přípustné považuje každé řešení nalézající se v prostoru řešení, a s vynaložením dostupného času (a výpočetního výkonu) se hledá řešení co nejlepší = nejoptimálnější.
Velmi často jsou algoritmy více či méně kopií postupů, které jsou využívány v přírodě živými entitami, kde zcela zřejmě jde o co nejkvalitnější přežití (např. genetické algoritmy, algoritmy založené na kolektivně inteligenci atd.); také jsou napodobovány fyzikální procesy směřující např. k vytvoření optimální krystalické struktury apod.
Pokud může být optimalizace provedena jinou konvenční matematickou optimalizační metodou (opět např. MNČ), bude určena přesněji, spolehlivěji a s vynaložením zlomku výpočetního výkonu. Globální optimalizační algoritmus určí v nejlepším případě stejně kvalitní řešení, ale obecně méně kvalitní řešení za vyšší cenu. Vyplývá to z podstaty dále popsaných metod, neboť se nezkoumá matematická podstata problému, ale zjednodušeně řečeno se z vnějšku hodnotí výsledky, a na podstatu problému se pohlíží jako na černou skříňku. Dále také pokud jsou v prostoru řešení lokální optima (a jedno z nich je optimem globálním), nelze obvykle při nižším nežli nekonečném počtu kroků obecně zaručit nalezení globálního optima.
Jednoduchým příkladem úlohy, kde globální optimalizační metody mohou být úspěšně využity v oblasti geodézie a inženýrské geodézie, je zhuštění existující polohové geodetické sítě jedním bodem č. 5 (odpovídá úloze designu 0. řádu) tak, aby se bod nalézal v přípustné oblasti vymezené např. oblastí využití či vlastnickými vztahy a zároveň byl určen s minimální směrodatnou odchylkou souřadnicovou ${\sigma }_{XY}$. Je dána konfigurace známých bodů 1, 2, 3, 4, měřené veličiny (vodorovné směry $\varphi_1$, $\varphi_2$, $\varphi_3$, $\varphi_4$; vodorovné délky $d_1$, $d_2$, $d_3$, $d_4$) a jejich přesnost (${\sigma }_{\varphi }$, ${\varphi }_d$). Situace je ukázána na [[0508_globalni_optimalizacni_metody#obr050801|Obr. 1]] . Hodnotící funkce v tomto případě má tvar
$$f\left(X_5,Y_5\right)={\sigma }_{XY\ 5}=\sqrt{\frac{1}{2}\cdot \left({\sigma }^2_{X5}+{\sigma }^2_{Y5}\right)} , $$
kde směrodatné odchylky souřadnic ${\sigma }_{X5}$ a ${\sigma }_{Y5}$ se určí jako diagonální prvky kovarianční matice
$$\left( \begin{array}{cc}
{\sigma }^2_{X5} & Cov_{X5Y5} \\
Cov_{X5Y5} & {\sigma }^2_{Y5} \end{array}
\right)={\left({{\mathbf A}}^T\cdot {\mathbf P}\cdot {\mathbf A}\right)}^{-1}, $$
kde matice ${\mathbf A}$ a ${\mathbf P}$ se sestaví známým postupem.
V tomto jednoduchém případě lze prostor přípustných řešení rozdělit pravidelně do čtvercového rastru s krokem např. 10 mm, spočítat kvalitu všech řešení a vybrat to nejkvalitnější s jistotou nalezeného globálního optima. Tento postup je však proveditelný pro malý počet proměnných s malým rozsahem přípustného intervalu řešení. V případě komplexních problémů (např. optimalizace rozmístění třiceti bodů geodetické sítě) již není proveditelné spočítat všechny kombinace, a jak konstatuje T. Weisse ve své knize [(#1)], získat řešení mírně horší nežli to zcela optimální je lepší než čekat ${10}^{100}$ let.
{{ :05_rozbory_presnosti:050801_optimalizacni_uloha.jpg }}
;#;
Obr. 1 //Optimalizační úloha zhuštění existující geodetické sítě//
;#;
###
===== Rozdělení globálních optimalizačních algoritmů =====
###
Jednotlivé algoritmy lze rozdělovat podle vice kritérií, za základní lze považovat dělení podle způsobu práce na metody:
- deterministické (nevyužívají náhodná čísla pro rozhodování),
- pravděpodobnostní (využívají náhodná čísla pro rozhodování),
- kombinované.
Zejména deterministické metody využívají tzv. heuristiku, což je postup rozhodující o směru a velikosti dalšího kroku algoritmu na základě informací získaných v krocích předchozích.
Další rozdělení je podle vlastností algoritmu (toto dělení bude dále využíváno) s uvedenými příklady:
* **a)** **Pravděpodobnostní (Monte-Carlo) metody**
- Horolezecký algoritmus (Hill Climbing),
- Horolezecký algoritmus s náhodnými restarty (Hill Climbing with Random Restarts),
- Náhodná optimalizace (Random Optimization),
- Simulované žíhání (Simulated Annealling).
* **b)** **Evoluční metody**
- Genetické algoritmy,
- Evoluční strategie.
* **c)** **Metody kolektivní inteligence (Swarm Intelligence)**
- Algoritmus SOMA (Self-Organizing Migration Algorithm),
- Optimalizace hejnem částic (Particle Swarm Optimization).
* **d)** **Přímé vyhledávací metody**
* Neinformované vyhledávání (Uninformed Search)
- Prohledávání do šířky (Breadth-First Search),
- Prohledávání do hloubky (Depth-First Search),
- Prohledávání náhodné cesty (Random Walks).
* Informované vyhledávání (Informed Search)
- Hladové vyhledávání (Greedy Best-First Search),
- Adaptivní prohledávání cesty (Adaptive Walks),
- Simplexová metoda (Downhill Simplex).
Pro využití lze doporučit zejména Pravděpodobnostní (Monte-Carlo) metody, Evoluční strategie a Simplexovou metodu (Downhill Simplex).
Dále budou podrobněji uvedeny některé vybrané algoritmy. V mnoha případech není v české literatuře jednotně uváděné pojmenování jednotlivých metod, proto jsou uvedeny i anglické názvy. Mnohé metody spadající do různých oblastí jsou si velmi podobné nebo mají řadu společných prvků, zároveň je možné jednotlivé metody libovolně kombinovat.
###
reference-format : []
note-id-format : []
note-id-base : text
reference-base : text
----
**<<** [[05_rozbory_presnosti:0507_rozbor_presnosti_modelovanim|7. Apriorní rozbor modelováním úloh s vyrovnáním (i bez)]]