Místní vyhledávání (optimalizace) - Local search (optimization)
Ve vědě o počítačích , místní vyhledávání je heuristické metody pro řešení výpočetně tvrdých optimalizačních problémů. Místní vyhledávání lze použít na problémy, které lze formulovat jako nalezení řešení maximalizujícího kritérium mezi řadou kandidátských řešení . Místní vyhledávací algoritmy přecházejí z řešení do řešení v prostoru kandidátských řešení ( vyhledávací prostor ) pomocí lokálních změn, dokud není nalezeno řešení, které je považováno za optimální, nebo dokud neuplyne časová hranice.
Místní vyhledávací algoritmy jsou široce aplikovány na řadu náročných výpočetních problémů, včetně problémů z počítačové vědy (zejména umělé inteligence ), matematiky , operačního výzkumu , strojírenství a bioinformatiky . Příklady místních vyhledávacích algoritmů jsou WalkSAT , 2- optický algoritmus pro problém obchodního cestujícího a algoritmus Metropolis – Hastings .
Příklady
Některé problémy s použitím místního vyhledávání jsou:
- Problém vrchol krytu , ve kterém roztok je vrchol kryt z grafu , a cílem je najít řešení s minimálním počtem uzlů
- Problém obchodního cestujícího , ve kterém je řešením cyklus obsahující všechny uzly grafu a cílem je minimalizovat celkovou délku cyklu
- Boolean satisfiability problém , ve kterém kandidát řešení je přiřazení pravda, a cílem je maximalizovat počet doložek uspokojována prostřednictvím postoupení; v tomto případě je konečné řešení užitečné pouze tehdy, pokud splňuje všechny klauzule
- Problém s plánováním sestry, kde je řešením přiřazení sester na směny, které splňuje všechna stanovená omezení
- K- medoid clustering problém a další související umístění zařízení problémy, na které místní vyhledávání nabízí nejlepší poměry známá aproximace z nejhoršího možného pohledu
- Problém s neuronovými sítěmi Hopfield, pro který je nalezení stabilních konfigurací v síti Hopfield .
Popis
Většina problémů může být formulována z hlediska vyhledávacího prostoru a cíle několika různými způsoby. Například pro problém obchodního cestujícího může být řešením cyklus a kritériem maximalizace je kombinace počtu uzlů a délky cyklu. Ale řešením může být také cesta a být cyklem je součástí cíle.
Algoritmus místního vyhledávání začíná od kandidátského řešení a poté iterativně přechází k sousednímu řešení. To je možné pouze tehdy, je -li ve vyhledávacím prostoru definován sousedský vztah . Například sousedství vrcholového krytu je jiný vrcholový kryt, který se liší pouze o jeden uzel. Pro booleovskou uspokojitelnost jsou sousedy přiřazení pravdy obvykle přiřazení pravdy, která se od něj liší pouze vyhodnocením proměnné. Stejný problém může mít definováno více různých čtvrtí; místní optimalizace se čtvrtěmi, které zahrnují změnu až na K komponent řešení, se často označuje jako k-opt .
Každé kandidátské řešení má obvykle více než jedno sousední řešení; volba, ke které se přestěhovat, se provádí pouze pomocí informací o řešeních v sousedství aktuálního, odtud název místní vyhledávání. Když je volba sousedního řešení provedena tak, že vezmeme lokálně maximalizující kritérium, metaheuristika má název horolezectví . Pokud v okolí nejsou žádné zlepšující se konfigurace, místní vyhledávání se zasekne v místně optimálním bodě . Tento problém s lokální optimalizací lze vyléčit pomocí restartů (opakované místní vyhledávání s různými počátečními podmínkami) nebo složitějších schémat založených na iteracích, jako je iterované místní vyhledávání , na paměti, jako je optimalizace reaktivního vyhledávání, na stochastických úpravách bez paměti, jako je simulované žíhání .
Ukončení místního vyhledávání může být založeno na časovém limitu. Další běžnou volbou je ukončení, pokud v daném počtu kroků nebylo vylepšeno nejlepší řešení nalezené algoritmem. Místní vyhledávání je algoritmus kdykoli : může vrátit platné řešení, i když je přerušeno kdykoli před jeho ukončením. Místní vyhledávací algoritmy jsou obvykle aproximační nebo neúplné algoritmy , protože hledání se může zastavit, i když nejlepší řešení nalezené algoritmem není optimální. K tomu může dojít, i když je ukončení způsobeno nemožností vylepšit řešení, protože optimální řešení může ležet daleko od sousedství řešení překračovaných algoritmy.
Pro specifické problémy je možné navrhnout sousedství, která jsou velmi velká, případně exponenciálně velká. Pokud lze efektivně nalézt nejlepší řešení v okolí, jsou tyto algoritmy označovány jako velmi rozsáhlé algoritmy pro vyhledávání v sousedství .
Viz také
Místní vyhledávání je dílčí pole:
Pole v místním vyhledávání zahrnují:
- horolezectví
- Simulované žíhání (vhodné pro místní i globální vyhledávání)
- Hledání tabu
- Pozdní přijetí horolezectví
- Reaktivní optimalizace vyhledávání (kombinace strojového učení a místní heuristiky vyhledávání)
Prostory pro vyhledávání se skutečnou hodnotou
Existuje několik metod pro provádění místního vyhledávání skutečných vyhledávacích prostorů:
- Luus – Jaakola vyhledává lokálně pomocí rovnoměrného rozdělení a exponenciálně se snižujícího rozsahu vyhledávání.
- Náhodná optimalizace vyhledává lokálně pomocí normální distribuce .
- Náhodné vyhledávání vyhledává lokálně vzorkováním hypersféry obklopující aktuální polohu.
- Hledání vzoru provádí kroky podél os vyhledávacího prostoru pomocí exponenciálně se zmenšujících velikostí kroků.
Reference
Bibliografie
- Battiti, Roberto; Mauro Brunato; Franco Mascia (2008). Reaktivní vyhledávání a inteligentní optimalizace . Springer Verlag . ISBN 978-0-387-09623-0. Archivováno od originálu dne 2012-03-16.
- Hoos, HH a Stutzle, T. (2005) Stochastic Local Search: Foundations and Applications, Morgan Kaufmann.
- Vijay Arya and Naveen Garg and Rohit Khandekar and Adam Meyerson and Kamesh Munagala and Vinayaka Pandit, (2004): Local Search Heuristics for k -Median and Facility Location Problems , SIAM Journal of Computing 33 (3).
- Juraj Hromkovič : Algoritmika pro těžké problémy: Úvod do kombinatorické optimalizace, randomizace, aproximace a heuristiky (Springer)
- Wil Michiels, Emile Aarts, Jan Korst: Theoretical Aspects of Local Search (Springer)