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:

  1. 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ů
  2. 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
  3. 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
  4. 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í
  5. 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
  6. 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í:

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ů:

Reference

Bibliografie