Podręcznik

Przeszukiwanie Zróżnicowanego Sąsiedztwa (ang. Variable Neighborhood Search, VNS) to metaheurystyczna metoda optymalizacji, która opiera się na idei dynamicznego zmieniania sąsiedztwa w celu unikania pułapek związanych z lokalnymi minimami. VNS zostało zaproponowane przez Mihaia Mladenovicia i Pierre'a Hansena w latach 90., i od tego czasu znalazło szerokie zastosowanie w rozwiązywaniu różnych problemów optymalizacyjnych, w tym zarówno problemów dyskretnych, jak i ciągłych.

Cechą charakterystyczną algorytmu VNS jest jego zdolność do ucieczki z lokalnych minimów poprzez systematyczne i kontrolowane zwiększanie zakresu poszukiwań w różnych obszarach przestrzeni rozwiązań. Kluczowym elementem tego podejścia jest koncepcja wielokrotnego przeszukiwania różnych sąsiedztw, co pozwala na bardziej globalne spojrzenie na problem optymalizacyjny.

Zasada działania algorytmu VNS

Algorytm VNS działa na podstawie sekwencyjnego przeszukiwania różnych sąsiedztw (grup rozwiązań) wokół bieżącego rozwiązania. Proces ten można podzielić na kilka kluczowych kroków:

1. Definiowanie sąsiedztwa:

   • Algorytm rozpoczyna się od wyboru początkowego rozwiązania oraz zdefiniowania różnych struktur sąsiedztwa. Sąsiedztwo to zbiór rozwiązań, które można uzyskać poprzez wprowadzenie niewielkich zmian w bieżącym rozwiązaniu. W zależności od problemu, sąsiedztwo może być definiowane na różne sposoby, np. poprzez zamianę elementów, permutacje lub inne transformacje.

2. Poszukiwanie lokalne (Local Search):

   • W pierwszym kroku algorytm przeprowadza dokładne poszukiwanie w bieżącym sąsiedztwie, próbując znaleźć lokalne minimum. Poszukiwanie lokalne polega na przeszukiwaniu sąsiadujących rozwiązań i akceptowaniu tych, które poprawiają funkcję celu.

3. Zwiększanie sąsiedztwa:

   • Jeśli przeszukiwanie lokalne doprowadzi do lokalnego minimum, algorytm rozszerza rozmiar sąsiedztwa, zwiększając zakres poszukiwań. Zwiększenie sąsiedztwa oznacza, że algorytm zaczyna eksplorować bardziej odległe rozwiązania w nadziei na znalezienie lepszych globalnych minimów. Zbiór sąsiedztwa aktualnego rozwiązania $x$ oznacza się przez $N(k(x)$, gdzie $k$ oznacza rozmiar sąsiedztwa, tzn. im większa wartość $k$ tym potencjalnie większy obszar wokół aktualnego rozwiązania brany jest pod uwagę.  $$
     

4. Wstrząsanie (Shaking):

   • Jednym z kluczowych kroków algorytmu VNS jest tzw. "wstrząsanie" rozwiązania. W momencie, gdy algorytm nie znajduje lepszych rozwiązań w danym sąsiedztwie, wprowadza losowe zmiany w bieżącym rozwiązaniu, aby przesunąć się do nowego obszaru przestrzeni poszukiwań. Dzięki temu unika zablokowania się w lokalnym minimum.

5. Zakończenie:

   • Proces zwiększania sąsiedztwa oraz wstrząsania powtarza się aż do spełnienia określonych warunków zakończenia, np. po osiągnięciu maksymalnej liczby iteracji lub braku poprawy przez określoną liczbę kroków.

Kroki algorytmu VNS

1. Inicjalizacja: Wybierz początkowe rozwiązanie $x_0$oraz ustal różne struktury sąsiedztwa $N_k$dla $k=1,2,\dots ,k_{\max }$
2. Powtarzaj:
   • Wstrząsanie: Losowo wybierz rozwiązanie $x^{\mathrm{\prime }}$ z sąsiedztwa $N_k(x)$.
   • Poszukiwanie lokalne: Wykonaj poszukiwanie lokalne zaczynając od $x^{\mathrm{\prime }}$, aby znaleźć lokalne minimum $x^{\mathrm{\prime }\mathrm{\prime }}$.
   • Akceptacja: Jeśli $x''$ jest lepsze od $x$, ustaw $x=x^{\mathrm{\prime }\mathrm{\prime }}$, a $k = 1$; w przeciwnym razie, zwiększ $k$. Gdy $k$ osiągnie $k_{\text{max}}$, wróć do $k=1$.
     
   • Powtarzaj aż do spełnienia warunków zakończenia.

Zalety VNS

1. Unikanie lokalnych minimów: Dzięki mechanizmowi zmiany sąsiedztwa oraz wstrząsania, VNS jest w stanie unikać utknięcia w lokalnych minimach, co jest częstym problemem w tradycyjnych metodach przeszukiwania lokalnego.

2. Prostota i elastyczność: Algorytm VNS jest stosunkowo prosty do zrozumienia i implementacji. Można go łatwo dostosować do różnych typów problemów, poprzez modyfikację definicji sąsiedztwa oraz mechanizmów wstrząsania.

3. Szerokie zastosowanie: VNS znalazł zastosowanie w wielu dziedzinach, od logistyki i transportu, przez optymalizację trasowania pojazdów, aż po problemy planowania i harmonogramowania.

Ograniczenia VNS

Podobnie jak w symulowanym wyżarzaniu metoda nie gwarantuje zbieżności i jest zależna od parametrów algorytmu. Dodatkowo, często definiowanie sąsiedztwa oraz algorytmów przeszukiwania lokalnego wymaga dostosowania do konkretnych właściwości rozpatrywanego problemu.

Zastosowania

Algorytm VNS jest szeroko stosowany w problemach dyskretnych i kombinatorycznych. Przykłady zastosowań: problem komiwojażera (TSP), harmonogramowanie zadań, problem trasowania pojazdów (VRP).