Wyszukiwanie lokalne (optymalizacja) - Local search (optimization)

W informatyce , wyszukiwanie lokalne jest heurystyczna metoda rozwiązywania trudnych obliczeniowo optymalizacji problemów. Wyszukiwanie lokalne może być stosowane w przypadku problemów, które można sformułować jako znalezienie rozwiązania maksymalizującego kryterium spośród wielu możliwych rozwiązań . Lokalne algorytmy przeszukiwania przechodzą od rozwiązania do rozwiązania w przestrzeni rozwiązań kandydujących ( przestrzeń poszukiwań ) poprzez stosowanie lokalnych zmian, aż do znalezienia rozwiązania uznanego za optymalne lub upłynięcia ograniczenia czasowego.

Lokalne algorytmy wyszukiwania są szeroko stosowane w wielu trudnych problemach obliczeniowych, w tym w problemach z informatyki (w szczególności sztucznej inteligencji ), matematyki , badań operacyjnych , inżynierii i bioinformatyki . Przykładami lokalnych algorytmów wyszukiwania są WalkSAT , algorytm 2 opcji dla problemu komiwojażera i algorytm Metropolis-Hastings .

Przykłady

Niektóre problemy, w których zastosowano wyszukiwanie lokalne, to:

  1. Problemem pokrywa wierzchołek , w którym roztwór jest pokrywa wierzchołek z wykresu , a celem jest znalezienie rozwiązania, za pomocą minimalnej liczby węzłów
  2. Problem komiwojażera , w którym roztwór jest cykl zawierający wszystkie węzły o wykres i celem jest zminimalizowanie całkowitej długości cyklu
  3. Problem spełnialności , w którym kandydat rozwiązaniem jest przypisanie prawda, a celem jest maksymalizacja liczby klauzul spełnione przez przypisanie; w tym przypadku ostateczne rozwiązanie ma zastosowanie tylko wtedy, gdy spełnia wszystkie klauzule
  4. Problemem pielęgniarka szeregowanie gdzie rozwiązaniem jest przypisanie pielęgniarek do zmian , które spełnia wszystkie ustalone ograniczenia
  5. K-medoid problemem klastrów i innych pokrewnych lokalizacja obiektu problemy, dla których lokalne oferty wyszukiwania najlepsze współczynniki aproksymacji znany z najgorszym perspektywy
  6. Problem sieci neuronowych Hopfielda, dla których znalezienie stabilnych konfiguracji w sieci Hopfielda .

Opis

Większość problemów można sformułować w kategoriach przestrzeni wyszukiwania i celu na kilka różnych sposobów. Na przykład dla problemu komiwojażera rozwiązaniem może być cykl, a kryterium maksymalizacji jest kombinacja liczby węzłów i długości cyklu. Ale rozwiązaniem może być również ścieżka, a bycie cyklem jest częścią celu.

Lokalny algorytm wyszukiwania rozpoczyna się od rozwiązania kandydującego, a następnie iteracyjnie przechodzi do rozwiązania sąsiedniego . Jest to możliwe tylko wtedy, gdy w przestrzeni wyszukiwania zdefiniowana jest relacja sąsiedztwa . Na przykład sąsiedztwo pokrycia wierzchołka jest innym pokryciem wierzchołka różniącym się tylko jednym węzłem. Dla spełnialności logicznej sąsiadami przypisania prawdziwości są zwykle przypisania prawdziwości różniące się od niego jedynie oceną zmiennej. Ten sam problem może mieć zdefiniowane wiele różnych sąsiedztw; optymalizacja lokalna z sąsiedztwami, które wymagają zmiany do k elementów rozwiązania, jest często określana jako k-opt .

Zazwyczaj każde rozwiązanie kandydujące ma więcej niż jedno rozwiązanie sąsiednie; wybór, do którego się przenieść, dokonywany jest na podstawie informacji o rozwiązaniach w sąsiedztwie aktualnego, stąd nazwa local search. Gdy wybór sąsiedniego rozwiązania odbywa się na podstawie lokalnie maksymalizującego kryterium, metaheurystyka przyjmuje nazwę wspinaczka górska . Gdy w okolicy nie ma poprawiających się konfiguracji, wyszukiwanie lokalne utknie w lokalnie optymalnym punkcie . Ten problem optymalizacji lokalnej można wyleczyć za pomocą ponownych uruchomień (powtarzane wyszukiwanie lokalne z różnymi warunkami początkowymi) lub bardziej złożonych schematów opartych na iteracjach, takich jak iterowane wyszukiwanie lokalne , na pamięci, na przykład reaktywna optymalizacja wyszukiwania, na bezpamięciowych modyfikacjach stochastycznych, takich jak symulowane wyżarzanie .

Zakończenie wyszukiwania lokalnego może być oparte na określonym czasie. Innym powszechnym wyborem jest zakończenie, gdy najlepsze rozwiązanie znalezione przez algorytm nie zostało ulepszone w określonej liczbie kroków. Wyszukiwanie lokalne jest algorytmem w dowolnym momencie : może zwrócić prawidłowe rozwiązanie, nawet jeśli zostanie przerwane w dowolnym momencie przed jego zakończeniem. Lokalne algorytmy wyszukiwania są zazwyczaj algorytmami przybliżającymi lub niekompletnymi , ponieważ wyszukiwanie może się zatrzymać, nawet jeśli najlepsze rozwiązanie znalezione przez algorytm nie jest optymalne. Może się to zdarzyć nawet, jeśli terminacja wynika z niemożności ulepszenia rozwiązania, ponieważ optymalne rozwiązanie może leżeć daleko od sąsiedztwa rozwiązań przecinanych przez algorytmy.

W przypadku konkretnych problemów możliwe jest zaprojektowanie bardzo dużych sąsiedztw, prawdopodobnie o wykładniczej wielkości. Jeśli najlepsze rozwiązanie w obrębie sąsiedztwa można skutecznie znaleźć, takie algorytmy są określane jako algorytmy wyszukiwania sąsiedztwa na bardzo dużą skalę .

Zobacz też

Wyszukiwanie lokalne to poddziedzina:

Pola w ramach wyszukiwania lokalnego obejmują:

Przestrzenie wyszukiwania o wartościach rzeczywistych

Istnieje kilka metod wykonywania lokalnego wyszukiwania przestrzeni wyszukiwania o wartościach rzeczywistych :

Bibliografia

Bibliografia