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 ([1]), 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 [2].

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 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 [3], získat řešení mírně horší nežli to zcela optimální je lepší než čekat ${10}^{100}$ let.

;#; Obr. 1 Optimalizační úloha zhuštění existující geodetické sítě ;#;

Jednotlivé algoritmy lze rozdělovat podle vice kritérií, za základní lze považovat dělení podle způsobu práce na metody:

1. deterministické (nevyužívají náhodná čísla pro rozhodování),
2. pravděpodobnostní (využívají náhodná čísla pro rozhodování),
3. 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
  1. Horolezecký algoritmus (Hill Climbing),
  2. Horolezecký algoritmus s náhodnými restarty (Hill Climbing with Random Restarts),
  3. Náhodná optimalizace (Random Optimization),
  4. Simulované žíhání (Simulated Annealling).
• b) Evoluční metody
  1. Genetické algoritmy,
  2. Evoluční strategie.
• c) Metody kolektivní inteligence (Swarm Intelligence)
  1. Algoritmus SOMA (Self-Organizing Migration Algorithm),
  2. Optimalizace hejnem částic (Particle Swarm Optimization).
• d) Přímé vyhledávací metody
  • Neinformované vyhledávání (Uninformed Search)
    1. Prohledávání do šířky (Breadth-First Search),
    2. Prohledávání do hloubky (Depth-First Search),
    3. Prohledávání náhodné cesty (Random Walks).
  • Informované vyhledávání (Informed Search)
    1. Hladové vyhledávání (Greedy Best-First Search),
    2. Adaptivní prohledávání cesty (Adaptive Walks),
    3. 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.

« 7. Apriorní rozbor modelováním úloh s vyrovnáním (i bez)