Zmienne wyszukiwanie sąsiedztwa

Zmienne przeszukiwanie sąsiedztwa (VNS), zaproponowane przez Mladenovića i Hansena w 1997 r., Jest metaheurystyczną metodą rozwiązywania zestawu problemów optymalizacji kombinatorycznej i optymalizacji globalnej. Bada odległe sąsiedztwo obecnego istniejącego rozwiązania i przenosi się stamtąd do nowego wtedy i tylko wtedy, gdy dokonano ulepszenia. Lokalna metoda wyszukiwania jest stosowana wielokrotnie, aby przejść od rozwiązań w sąsiedztwie do lokalnych optimów. VNS został zaprojektowany do aproksymacji rozwiązań dyskretnych i ciągłych problemów optymalizacyjnych i zgodnie z nimi ma na celu rozwiązywanie problemów programów liniowych , z programami całkowitoliczbowymi , mieszane problemy z programami całkowitymi, problemy z programami nieliniowymi itp.

Wstęp

VNS systematycznie zmienia sąsiedztwo w dwóch fazach: po pierwsze, zejście w celu znalezienia lokalnego optimum , a na koniec faza perturbacji, aby wydostać się z odpowiedniej doliny.

Liczba zastosowań szybko rośnie i dotyczy wielu dziedzin: teorii lokalizacji , analizy klastrów , planowania , wyznaczania tras pojazdów , projektowania sieci , określania wielkości partii, sztucznej inteligencji , inżynierii, problemów łączenia, biologii, filogenezy , niezawodności , geometrii, projektowania telekomunikacyjnego itp. .

Istnieje kilka książek ważnych dla zrozumienia VNS, takich jak: Handbook of Metaheuristics , 2010, Handbook of Metaheuristics, 2003 i Search metodologie, 2005. Wcześniejsze prace motywujące to podejście można znaleźć w

Davidon, toaleta
Fletcher, R., Powell, MJD
Mladenović, N. and
Brimberg J., Mladenović N.

Najnowsze badania metodologii VNS oraz liczne zastosowania można znaleźć w 4OR, 2008 i Annals of OR, 2010.

Definicja problemu

Zdefiniuj jeden deterministyczny problem optymalizacyjny za pomocą

${\ Displaystyle \ min {\ {f (x) | x \ w X, X \ subseteq S \}}}$ , (1)

gdzie S , X , x i f to odpowiednio przestrzeń rozwiązań, zbiór wykonalny, rozwiązanie wykonalne i funkcja celu o wartościach rzeczywistych . Jeśli S jest skończonym, ale dużym zbiorem, zdefiniowany jest kombinatoryczny problem optymalizacji. Jeśli ${\ displaystyle {S = R ^ {n}}}$ istnieje model ciągłej optymalizacji.

Rozwiązanie jest optymalne, jeśli ${\ Displaystyle {x ^ {*} \ in X}}$

${\ Displaystyle {f (x ^ {*}) \ równoważnik f (x), \ qquad \ forall {x} \ \ w X}}$ .

Dokładny algorytm dla problemu (1) należy znaleźć optymalne rozwiązanie x* , sprawdzając jego optymalną strukturę, lub jeśli jest to niewykonalne, w procedurze należy wykazać, że nie ma osiągalnego rozwiązania, tj. $X=\varnothing$ lub rozwiązanie jest nieograniczone. Czas procesora musi być ograniczony i krótki. znaleziono wykonalne rozwiązanie takie, że ${\ Displaystyle x ^ {*}}$

${\ Displaystyle {f (x ^ {*}) \ równoważnik f (x) + \ epsilon, \ qquad \ forall {x} \ \ w X}}$ lub ${\ Displaystyle {(f (x ^ {*}) -f (x)} / f (x ^ {*}) <\ epsilon, \ qquad \ forall {x} \, \ w X}}$

Niektóre heurystyki szybko akceptują rozwiązanie przybliżone lub rozwiązanie optymalne, ale bez potwierdzenia jego optymalności. Niektóre z nich mają nieprawidłowy certyfikat, tj. otrzymane rozwiązanie spełnia ${\ displaystyle x_ {h}}$

$qquad \ forall {x} \, \ in X}}$ ${\ Displaystyle {(f (x_ {h}) -f (x)) / f (x_ {h} ) \ leq \ epsilon ,$ $\$ przez jakiś czas chociaż rzadko jest to małe.

Heurystyki napotykają na problem lokalnych optimów w wyniku unikania nieograniczonego czasu obliczeniowego. Lokalne optimum problemu jest takie, że ${\ displaystyle x_ {L}}$

${\ Displaystyle {f (x_ {L}) \ równoważnik f (x), \ qquad \ forall {x} \ \ w N(x_{L})\cap X}}$

gdzie ${\ Displaystyle N (x_ {L})}$ oznacza sąsiedztwo ${\ Displaystyle x_ {L}}$

Opis

Według (Mladenović, 1995) VNS jest metaheurystyką, która systematycznie wykonuje procedurę zmiany sąsiedztwa, zarówno w zejściu do lokalnych minimów, jak iw ucieczce z dolin, które je zawierają.

VNS opiera się na następujących spostrzeżeniach:

Lokalne minimum w odniesieniu do jednej struktury sąsiedztwa niekoniecznie jest lokalnym minimum dla innej struktury sąsiedztwa.
Minimum globalne to minimum lokalne w odniesieniu do wszystkich możliwych struktur sąsiedztwa.
Dla wielu problemów minima lokalne w odniesieniu do jednego lub kilku sąsiedztw są stosunkowo blisko siebie.

W przeciwieństwie do wielu innych metaheurystyk, podstawowe schematy VNS i jego rozszerzeń są proste i wymagają niewielu parametrów, a czasem nie wymagają ich wcale. Dlatego oprócz dostarczania bardzo dobrych rozwiązań, często prostszych niż inne metody, VNS daje wgląd w przyczyny takiej wydajności, co z kolei może prowadzić do bardziej wydajnych i wyrafinowanych wdrożeń.

Istnieje kilka prac, w których można by to zbadać, wśród ostatnio wymienionych, takich jak (Hansen i Mladenović 1999, 2001a, 2003, 2005; Moreno-Pérez et al.;)

Wyszukiwanie lokalne

Lokalna heurystyka przeszukiwania jest wykonywana poprzez wybranie rozwiązania początkowego x, odkrycie kierunku zejścia od x w sąsiedztwie N(x) i przejście do minimum f(x) w obrębie N(x) w tym samym kierunku. Jeśli nie ma kierunku opadania, heurystyka zatrzymuje się; w przeciwnym razie jest powtarzany. Zwykle stosuje się najwyższy kierunek opadania, również związany z najlepszą poprawą. Ten zestaw reguł podsumowano w Algorytmie 1, w którym zakładamy, że dane jest rozwiązanie początkowe x . Wyjście składa się z lokalnego minimum, oznaczonego przez x' i jego wartość. Zauważ, że struktura sąsiedztwa N(x) jest zdefiniowana dla wszystkich x ∈ X . Na każdym kroku sąsiedztwo N(x) z x jest całkowicie badane. Ponieważ może to być czasochłonne, alternatywą jest użycie heurystyki pierwszego zejścia. Wektory $wyliczane i$ , gdy tylko zostanie Jest to podsumowane w Algorytmie 2.

Algorytm 1: Heurystyka najlepszego ulepszenia (najwyższego spadku).

Funkcja BestImprovement(x) 1: powtórz 2: x' ← x 3: x ← argmin_{ f(y) }, y ∈ N(x) 4: aż ( f(x) ≥ f(x') ) 5: powrót X'

Algorytm 2: Heurystyka pierwszego ulepszenia (pierwszego zejścia).

Funkcja FirstImprovement(x) 1: powtórz 2: x' ← x; i ← 0 3: powtórz 4: i ← i + 1 5: x ← argmin{ f(x), f(x^i)}, x^i ∈ N(x) 6: aż ( f(x) < f (x^i) lub i = |N(x)| ) 7: dopóki ( f(x) ≥ f(x') ) 8: zwróć x'

${\ Displaystyle {\ mathcal {N}} _ {k} (k = 1, ..., k_ {max})$ , za $-$ wstępnie wybranych struktur sąsiedztwa i ze rozwiązań w tym x

Użyjemy również notacji $.$ przy opisywaniu lokalnego N ${\ Displaystyle {\ mathcal {N}} _ {k} (x)$ lub ${\ Displaystyle {\ mathcal {N'}} _ {k} (x)}$ można wyprowadzić z jednej lub więcej funkcji metrycznych (lub quasi-metrycznych) wprowadzonych do przestrzeni rozwiązań S . Optymalne rozwiązanie $lub$ minimum ) to wykonalne rozwiązanie w osiągnięto minimum problemu. Nazywamy x ' ∈ X lokalnym minimum problemu względem ${\ Displaystyle {\ mathcal {N}} _ {k} (x)}$ , jeśli nie ma rozwiązania ${\ Displaystyle x \ w {\ mathcal {N'}} _ {k} (x) \ subseteq X}$ takie, że ${\ Displaystyle f (x)<f(x')}$ .

Aby rozwiązać problem za pomocą kilku sąsiedztw, fakty 1–3 można wykorzystać na trzy różne sposoby: (i) deterministyczny; (ii) stochastyczny ; (iii) zarówno deterministyczne, jak i stochastyczne. Najpierw podajemy w Algorytmie 3 kroki funkcji zmiany sąsiedztwa, które zostaną użyte później. Funkcja NeighborhoodChange() porównuje nową wartość f(x') z obecną wartością f(x) uzyskaną w sąsiedztwie k (wiersz 1). W przypadku uzyskania poprawy k powraca do wartości początkowej, a nowy operator aktualizuje się (wiersz 2). W przeciwnym razie brane jest pod uwagę następne sąsiedztwo (wiersz 3).

Algorytm 3: – Zmiana sąsiedztwa

Funkcja NeighborhoodChange (x, x', k) 1: if (x') < f(x) then 2: x ← x' // Wykonaj ruch 3: k ← 1 // Początkowe sąsiedztwo 4: else 5: k ← k+1 // Następne sąsiedztwo

Gdy VNS nie zapewnia dobrego rozwiązania, można pomóc w kilku krokach, takich jak porównanie pierwszej i najlepszej strategii poprawy w wyszukiwaniu lokalnym, zmniejszenie sąsiedztwa, intensyfikacja wstrząsów, przyjęcie VND, przyjęcie FSS i eksperymentowanie z ustawieniami parametrów.

Metoda Basic VNS (BVNS) ( Handbook of Metaheuristics , 2010) łączy deterministyczne i stochastyczne zmiany sąsiedztwa. $Jego$ kroki podano w Algorytmie 4. Często kolejne sąsiedztwa zagnieżdżone Zwróć uwagę, że punkt x' jest generowany losowo w kroku 4, aby uniknąć cykliczności, która mogłaby wystąpić, gdyby zastosowano regułę deterministyczną. W kroku 5 zwykle przyjmuje się najlepsze wyszukiwanie lokalne (algorytm 1). Można go jednak zastąpić pierwszym ulepszeniem (algorytm 2).

Algorytm 4: Podstawowy VNS

Funkcja VNS (x, kmax, tmax) 1: powtórzenie 2: k ← 1 3: powtórzenie 4: x' ← Wstrząsnięcie(x, k) // Wstrząsnięcie 5: x'' ← BestImprovement(x' ) // Wyszukiwanie lokalne 6 : x ← NeighbourhoodChange(x, x'', k) // Zmień otoczenie 7: do k = kmax 8: t ← CpuTime() 9: do t > tmax

Warianty VNS

Podstawowy VNS to najlepsza metoda zejścia do poprawy z randomizacją. Bez większego wysiłku można to przekształcić w metodę zejście-wzniesienie: w funkcji NeighbourhoodChange() zamień również x na x" z pewnym prawdopodobieństwem, nawet jeśli rozwiązanie jest gorsze od rozwiązania zasiedziałego. Można to również zamienić na pierwsze Metoda doskonalenia Innym wariantem podstawowego VNS może być znalezienie rozwiązania x' w kroku 'Wstrząsanie' jako najlepszego spośród b (parametr a) losowo generowanych rozwiązań z k okolica. Możliwe są dwa warianty tego rozszerzenia: (1) wykonanie tylko jednego wyszukiwania lokalnego spośród najlepszych spośród b punktów; (2) przeprowadzić wszystkie b wyszukiwania lokalne, a następnie wybrać najlepsze. W pracy (Fleszar i Hindi) można było znaleźć algorytm.

Rozszerzenia

VND

Metodę zmiennego sąsiedztwa (VND) uzyskuje się, jeśli zmiana sąsiedztwa jest dokonywana w sposób deterministyczny. W opisach jego algorytmów zakładamy, że dane jest rozwiązanie początkowe x . Większość lokalnych heurystyk wyszukiwania w fazie początkowej wykorzystuje bardzo niewiele sąsiedztw. Ostatecznym rozwiązaniem powinno być lokalne minimum w odniesieniu do wszystkich okolic;

{\ displaystyle k_ {max}} ;

stąd szanse na osiągnięcie globalnego są większe przy użyciu VND niż przy pojedynczej strukturze sąsiedztwa.

RVNS

,

jeśli wybiera się losowe punkty spośród wykonuje się żadnego Zamiast tego wartości tych nowych punktów są porównywane z wartościami obecnego operatora, aw przypadku poprawy następuje aktualizacja. Zakłada się,

dozwolony

wybrano warunek zatrzymania, taki jak maksymalny lub maksymalna liczba iteracji między dwoma ulepszeniami

jest

opis algorytmów, . Dlatego RVNS używa dwóch parametrów:

{\ displaystyle t_ {max}}

i

{\ displaystyle k_ {max}}

. RVNS jest przydatny w bardzo dużych przypadkach, w przypadku których wyszukiwanie lokalne jest kosztowne. Zaobserwowano, że najlepszą wartością parametru jest

{\ displaystyle k_ {max}}

często wynosi 2. Ponadto maksymalna liczba iteracji między dwoma ulepszeniami jest zwykle używana jako warunek zatrzymania. RVNS jest podobny do metody Monte-Carlo , ale jest bardziej systematyczny.

Przekrzywiony VNS

Metoda skośnego VNS (SVNS) (Hansen i in.) rozwiązuje problem eksploracji dolin daleko od istniejącego rozwiązania. Rzeczywiście, po znalezieniu najlepszego rozwiązania w dużym regionie konieczne jest przejście pewnej drogi w celu uzyskania ulepszonego rozwiązania. Rozwiązania narysowane losowo w odległych dzielnicach mogą znacznie różnić się od istniejących, a VNS może następnie zdegenerować się w pewnym stopniu do heurystyki Multistart (w której zejścia są wykonywane iteracyjnie z rozwiązań generowanych losowo, heurystyka, o której wiadomo, że nie jest bardzo wydajna ). W związku z tym należy dokonać pewnej rekompensaty za odległość od urzędującego.

Wyszukiwanie zmiennego rozkładu sąsiedztwa

Metoda wyszukiwania rozkładu sąsiedztwa zmiennych (VNDS) (Hansen i in.) rozszerza podstawowy VNS do dwupoziomowego schematu VNS opartego na dekompozycji problemu. Dla ułatwienia prezentacji, ale bez utraty ogólności, zakłada się, że rozwiązanie x reprezentuje zbiór pewnych elementów.

Równoległy VNS

Ostatnio zaproponowano kilka sposobów zrównoleglenia VNS w celu rozwiązania problemu p-mediany. W García-López i in. testowane są trzy z nich: (i) równoległe wyszukiwanie lokalne; (ii) zwiększyć liczbę rozwiązań wylosowanych z bieżącego sąsiedztwa i równolegle przeprowadzić lokalne wyszukiwanie w każdym z nich oraz (iii) zrobić to samo, co w punkcie (ii), ale zaktualizować informacje o najlepszym znalezionym rozwiązaniu. Trzy równoległe strategie VNS są również sugerowane w celu rozwiązania problemu podróżującego nabywcy w Ochi et al.

Podstawowy podwójny VNS

Dla większości współczesnych heurystyk różnica wartości pomiędzy rozwiązaniem optymalnym a otrzymanym jest zupełnie nieznana. Gwarantowane działanie heurystyki pierwotnej można określić, jeśli znana jest dolna granica wartości funkcji celu. W tym celu standardowym podejściem jest rozluźnienie warunku integralności zmiennych pierwotnych w oparciu o matematyczne sformułowanie problemu.

Jednakże, gdy rozmiar problemu jest duży, nawet zrelaksowany problem może być niemożliwy do dokładnego rozwiązania za pomocą standardowych komercyjnych rozwiązań. Dlatego dobrym pomysłem wydaje się rozwiązywanie problemów dualnych zrelaksowanych również heurystycznie. Uzyskano gwarantowane granice wydajności pierwotnej heurystyki. W Primal-dual VNS (PD-VNS) (Hansen i in.) zaproponowano jeden możliwy ogólny sposób osiągnięcia zarówno gwarantowanych granic, jak i dokładnego rozwiązania.

Zmienne rozgałęzienia sąsiedztwa

Problem programowania liniowego mieszanych liczb całkowitych (MILP) polega na maksymalizowaniu lub minimalizowaniu funkcji liniowej, podlegającej ograniczeniom równości lub nierówności oraz ograniczeniom integralności niektórych zmiennych.

Przeszukiwanie przestrzeni formułowania zmiennego sąsiedztwa

FSS jest metodą bardzo przydatną, ponieważ jeden problem można zdefiniować w dodatkowych sformułowaniach, a poruszanie się po sformułowaniach jest uzasadnione. Udowodniono, że wyszukiwanie lokalne działa w ramach sformułowań, implikując ostateczne rozwiązanie, gdy rozpoczęto od rozwiązania początkowego w pierwszym sformułowaniu. Wyszukiwanie lokalne systematycznie zmienia różne sformułowania, które były badane pakowania okręgu (CPP), w którym punkt stacjonarny dla formuły programowania nieliniowego CPP we współrzędnych kartezjańskich nie jest ściśle punktem stacjonarnym we współrzędnych biegunowych .

Aplikacje

Zastosowania VNS lub odmian VNS są bardzo obfite i liczne. Niektóre dziedziny, w których można było znaleźć zbiory prac naukowych:

Zastosowania przemysłowe
Problemy projektowe w komunikacji
Problemy z lokalizacją
Eksploracja danych
Problemy z wykresami
Problemy z plecakiem i pakowaniem
Mieszane problemy całkowitoliczbowe
Planowanie czasu
Planowanie
Problemy z wyznaczaniem tras pojazdów
Prowadzenie łuku i zbiórka odpadów
Problemy z kartą floty
Rozszerzone problemy z wyznaczaniem tras pojazdów
Problemy w naukach biologicznych i chemii
Ciągła optymalizacja
Inne problemy z optymalizacją
Nauka odkrywcza

Wniosek

VNS implikuje kilka funkcji przedstawionych przez Hansena i Mladenovicia, a niektóre z nich przedstawiono tutaj:

Prostota: VNS jest prosty, przejrzysty i ma uniwersalne zastosowanie
Precyzja: VNS jest sformułowany w precyzyjnych definicjach matematycznych
Spójność: wszystkie działania heurystyk do rozwiązywania problemów wynikają z zasad VNS
Skuteczność: VNS dostarcza optymalne lub prawie optymalne rozwiązania dla wszystkich lub przynajmniej najbardziej realistycznych przypadków
Wydajność: VNS potrzebuje umiarkowanego czasu obliczeniowego, aby wygenerować optymalne lub prawie optymalne rozwiązania
Solidność: funkcjonowanie VNS jest spójne w różnych przypadkach
Przyjazność dla użytkownika: VNS nie ma parametrów, więc jest łatwy do zrozumienia, wyrażenia i użycia
Innowacja: VNS generuje nowe typy aplikacji
Ogólność: VNS prowadzi do dobrych wyników dla szerokiej gamy problemów
Interaktywność: VNS pozwala użytkownikowi wykorzystać swoją wiedzę w celu usprawnienia procesu rozwiązywania problemów
Wielość: VNS jest w stanie wyprodukować pewne niemal optymalne rozwiązania, spośród których użytkownik może wybierać;

Zainteresowanie VNS szybko rośnie, o czym świadczy rosnąca liczba artykułów publikowanych każdego roku na ten temat (10 lat temu zaledwie kilka, 5 lat temu kilkanaście, a w 2007 r. około 50). Ponadto 18. mini-konferencja EURO, która odbyła się na Teneryfie w listopadzie 2005 r., była w całości poświęcona VNS. Doprowadziło to do wydania specjalnych wydań IMA Journal of Management Mathematics w 2007 r., European Journal of Operational Research ( http://www.journals.elsevier.com/european-journal-of-operational-research/ ) oraz Journal of Heuristics ( https ://www.springer.com/mathematics/applications/journal/10732/ ) w 2008 roku.

Linki zewnętrzne