Slovník | Vyhledávání | Mapa webu
 
Analýza a hodnocení biologických datUmělá inteligence Prohledávání stavového prostoru Metody prohledávání Lokální metody prohledávání

Logo Matematická biologie

Lokální metody prohledávání

Samostatnou oblast metod pro prohledávání stavového prostoru jsou takzvané lokální metody prohledávání. Zmiňme si stručně alespoň dvě z nich a to horolezecké prohledávání (Hill climbing, slézání kopce, gradientní metoda prohledávání) a Simulated annealing (simulované žíhání). Společným znakem je, že tyto metody vyhodnocují jen své nejbližší okolí a vydají se při prohledávání zkrátka některým směrem, který se v tu chvíli zdá metodě lokálně optimální na základě vyhodnocení funkce Chovají se tedy podobně jako GS. Lokální metody ale zcela zapomínají předcházející uzly a postrádají tak možnost návratu.

Algoritmus simulovaného žíhání se oproti jednoduchému gradientnímu prohledávání liší v tom, že zavádí pojem teploty T. Tato teplota je na počátku prohledávání vysoká (umožňuje širší prohledání stavového prostoru v počátku běhu algoritmu) a v jeho průběhu postupně klesá až k nule (algoritmus konverguje k řešení). Při výběru následníka není v každém uzlu vždy zvolen jen následník nejvýhodnější, jako v případě gradientního prohledávání, ale s jistou pravděpodobností, která závisí na teplotě T, je zvolen přechod do uzlu jiného. S klesající teplotou pravděpodobnost volby neoptimálního následníka klesá, algoritmus postupně konverguje do ustáleného stavu. Algoritmus s větší pravděpodobností dosáhne globálního minima (cíle). Zavedením teploty je omezena možnost uváznutí algoritmu v lokálním minimu, protože s jistou pravděpodobností se z něj dokáže algoritmus vymanit a prohledat tak i ty části stavového prostoru, kam by prostá gradientní metoda nevstoupila. Často je tento algoritmus při neúspěchu startován opakovaně z rozdílných počátečních míst stavového prostoru.

Výhodami lokálních algoritmů je zejména jejich snadná implementace a minimální paměťové nároky. Nevýhodou je především jejich suboptimálnost a neúplnost, mohou snadno uváznout v lokálním minimu. Přesto jsou pro řadu problémů úspěšně využívány.

 
vytvořil Institut biostatistiky a analýz Masarykovy univerzity | | zpětné odkazy | validní XHTML 1.0 Strict