Zakázané prohledávání
Zakázané prohledávání (Tabu search) je heuristická optimalizační metoda využívající metody lokálního prohledávání. Vytvořil ji Fred W. Glover v roce 1986[1] a formalizoval v roce 1989[2][3].
Lokální prohledávání vezme potenciální řešení problému a kontroluje jeho bezprostřední sousedy (tj. řešení, která jsou si až na několik málo drobností podobná) v naději, že najde lepší řešení. Metody lokálního prohledávání mají tendenci uvíznout v oblastech lokálních minim nebo na plošinách, kde je mnoho řešení stejně vhodných.
Zakázané prohledávání zvyšuje efektivitu lokálního prohledávání tím, že v prováděném kroku lze přijmout i horší návrh, pokud není k dispozici žádný lepší návrh, tj. když se hledání zasekne v lokálním minimu, tj. umožňuje přeskočení lokálního minima. Navíc jsou zavedeny zákazy (odtud termín tabu), zakazující návrat k dříve navštíveným řešením.
Implementace zakázaného prohledávání používá paměťové struktury, které popisují navštívená řešení nebo uživatelem zadané množiny pravidel, tj. pokud bylo potenciální řešení v určitém krátkodobém období již dříve navštíveno nebo pokud porušilo nějaké pravidlo, je označeno jako „tabu“ (zakázané), aby algoritmus tuto možnost opakovaně nezvažoval.
Reference
V tomto článku byl použit překlad textu z článku Tabu search na anglické Wikipedii.
- ↑ Fred Glover. Future Paths for Integer Programming and Links to Artificial Intelligence. Computers and Operations Research. 1986, s. 533–549. doi:10.1016/0305-0548(86)90048-1.
- ↑ Fred Glover. Tabu Search – Part 1. ORSA Journal on Computing. 1989, s. 190–206. doi:10.1287/ijoc.1.3.190.
- ↑ Fred Glover. Tabu Search – Part 2. ORSA Journal on Computing. 1990, s. 4–32. doi:10.1287/ijoc.2.1.4.
