13. Princip lokálních heuristik, pojem globálního a lokálního minima, obrana před uváznutím v lokálním minimu. (NI-KOP)¶

Základní definice¶

Základní komponenty¶

Proměnné:

$X = \{x_1, \ldots, x_n\}$ - konfigurační proměnné problému $\Pi$
$Z = \{z_1, \ldots, z_m\}$ - vnitřní proměnné algoritmu $A$

Stav algoritmu: Ohodnocení $s$ proměnných $X \cup Z$

Definice¶

$S = \{s_i\}$ - množina stavů algoritmu
$Q = \{q_j\}$ - množina operátorů $S \to S$
Stavový prostor: Dvojice $(S, Q)$
Lidsky: stav a hrany – operace přechodu do sousedního stavu. Tah je aplikace operace na stav.

Klíčové koncepty¶

Akce: Aplikace operátoru $q \in Q$ na stav $s \in S$

Graf stavového prostoru $H = (S, E)$ : - Hrany reprezentují přechody mezi stavy - $(s_i, s_j) \in E$ odpovídá akci $s_j = q(s_i)$

Okolí a dostupnost¶

Okolí stavu $s$ : Množina stavů dosažitelných operacemi $q \in Q$

k-okolí: Stavy dosažitelné $1 \leq k$ operacemi

Vzdálenost stavů: Délka nejkratší orientované cesty v grafu $H$

Heuristické požadavky¶

Dostupnost: Silně souvislý graf
Symetrie: Přibližně symetrické vzdálenosti mezi stavy

Strategie pohybu ve stavovém prostoru¶

Úplná strategie: navštíví všechny stavy kromě těch, o kterých víme, že nedávají (optimální) řešení. Systematická strategie: úplná strategie, která navštíví každý stav nejvýše jednou.

Princip lokálních heuristik¶

Heuristika je přistup k řešení problému používající metody, které negarantují nalezení optimálního řešení.

počáteční stav→state;
Ø→best;
while (state != Ø and !stop()) {
    if (state.solution() and state.better(best))
        state→best;
    state = try(state);
}
return best;

Metoda prohledávání SP, která (primárně) chodí po hranách a dle určitých pravidel se snaží najít konfiguraci, která nejlépe vyhovuje popisu finálního řešení.
Na rozdíl od úplného průchodu redukuje stavový prostor a prochází část dle heuristiky, postupně konverguje.
V jednoduché formě vyžaduje stromový stavový prostor
Fitness funkce – absolutně hodnotí každý stav z hlediska kvality splnění kritéria. Měřitelná hodnota.

Jednoduché heuristiky¶

Pouze Nejlepší
- Postup na souseda s nejlepší cenou
- Pořadí procházení množiny Q neovlivní výsledek, pokud nejlepších stavů není více
- Vrátí prázdný stav, pokud neexistuje lepší soused
Prvé zlepšení
- Postup na souseda s lepší cenou
- Vrátí prázdný stav, pokud neexistuje lepší soused
Kernighan-Lin
- První budu vyhledávat do hloubky bez ohledu na optimalizační kritérium. Tedy náhodně vybírám sousedy.
- Při prohledáváni si ukládám všechny sousedy na které narazím
- Vyberu souseda z množiny všech uložených sousedu s nejlepší cenou

Globální a lokální minima¶

Globální minimum¶

Definice: Nejnižší bod v celém prohledávaném prostoru

Absolutně nejlepší možné řešení
Nachází se v globálním měřítku problému
Často obtížně dosažitelné

Lokální minimum¶

Definice: Nejlepší řešení v omezené oblasti stavového prostoru

Nejnižší bod v bezprostředním okolí
Nemusí reprezentovat optimální řešení celého problému
Riziko uvíznutí v suboptimálním řešení

Obrana před uvíznutím v lokálním minimu¶

Diverzifikace¶

Velká ochota připustit akci, které vede k horšímu řešení.
Rozšíření prohledávacího prostoru
Podpora explorace různých oblastí řešení
Zamezení předčasné konvergence

Intenzifikace¶

Malá ochota připustit akci, které vede k horšímu řešení.
Zaměření se na perspektivné oblasti řešení
Detailní prohledávání slibných podprostorů
Využití dosavadních znalostí o problému

Metody úniku z lokálního minima¶

Backtracking
- Systematický návrat a změna rozhodnutí
- Opuštění aktuální cesty řešení
Simulované ochlazování
- Probabilistický přístup k přijímání horších řešení
- Postupné snižování pravděpodobnosti přijetí
Genetické algoritmy
- Populační metoda
- Náhodné mutace a křížení řešení

Kontrola kvality řešení¶

Ověřovací kritérium:

Více nezávislých běhů heuristiky
Kontrola konvergence k podobným globálním minimům
Statistické vyhodnocení stability řešení