Variable Neighborhood Search

Variable Neighborhood Search ist eine Metaheuristik zur Lösung von kombinatorischen Optimierungsproblemen. Sie nutzt systematisch Nachbarschaften sowohl zum Abstieg zu lokal optimalen Lösungen als auch um aus den Einzugsbereichen von lokal optimalen Lösungen zu entkommen.

Funktionsweise

Variable Neighborhood Search [Mladenović/Hansen 1997] ist eine auf lokaler Suche basierende Metaheuristik. Sie nutzt systematisch eine Reihe von Nachbarschaften N₁, …, N_K die typischerweise geschachtelt sind, also N_k+1 enthält N_k. Die einfachste Variante ist das sogenannte Variable Neighborhood Descent (VND) Verfahren. Komplexere Varianten sind reduced, basic, general und skewed VNS.

Variable Neighborhood Descent (VND)

Hier werden die Nachbarschaften der Reihe nach durchlaufen, wobei man beim Auffinden einer neuen besten Lösung wieder mit der kleinsten Nachbarschaft beginnt:

Initialisierung: Finde Startlösung x mit beliebiger konstruktiver

Heuristik

k <-

1

Repeat until k = K

finde beste Lösung x’ aus Nachbarschaft N_k(x)

If x’ besser als x

Then x <- x’, k <- 1

Else k <- k+1

Wichtige Designentscheidungen sind die Anzahl und Größe der Nachbarschaften.

(basic) Variable Neighborhood Search (VNS)

Hier werden die K Nachbarschaften nicht vollständig durchsucht sondern es wird eine zufällige Lösung aus der jeweiligen Nachbarschaft gewählt. Im Unterschied zum VND ist VNS also ein stochastisches Suchverfahren. Zusätzlich wird ein lokales Suchverfahren eingesetzt.

Initialisierung: Finde Startlösung x mit beliebiger konstruktiver

Heuristik

Repeat (Iterationsschritt) until Abbruchbedingung

k <- 1

Repeat (Nachbarschaft k) until k = K

Shaking: wähle zufällige Lösung x’ aus

Nachbarschaft N_k(x)

Lokale Suche: verbessere x’ mittels lokaler

Suche; ergibt x“

If x“ besser als x

Then x <- x“, k <- 1

Else k <- k+1

Als lokale Suche wird üblicherweise ein einfaches und rasches Abstiegsverfahren gewählt. Es können aber auch andere Metaheuristiken eingesetzt werden. Wichtig ist dabei, dass die Nachbarschaften so groß sind, dass sie den Einzugsbereich der lokal optimalen Lösung, die durch die lokale Suche gefunden wurde durchbrechen können. Die Variante „reduced VNS“ verzichtet auf die lokale Suche. Im „general VNS“ wird als lokale Suche ein VND-Verfahren eingesetzt.

Akzeptanz von Verschlechterungen

Da die Tiefe der lokalen Optima a priori unbekannt ist, ist es schwierig die größte Nachbarschaft festzulegen. Typischerweise wird nicht versucht, durch ein sehr großes K sicherzustellen, dass man lokalen Optima immer entkommen kann, sondern es werden unter gewissen Bedingungen auch Verschlechterungen der Zielfunktion akzeptiert. Im „skewed VNS“ [Hansen/Mladenović 2003] werden auch etwas schlechtere Lösungen akzeptiert, sofern sie nur ausreichend unterschiedlich zur amtierenden Lösung x sind. Im obigen VNS-Algorithmus wird die Akzeptanzbedingung „[If x“ besser als x]“ ersetzt durch „wenn der Quotient [Ausmaß der Verschlechterung gegenüber x]/[Maß für die Unterschiedlichkeit von x] kleiner als ein parameter alpha ist“. Die Feineinstellung dieses Parameter alpha ist natürlich wichtig. Falls ein gutes Maß für die Unterschiedlichkeit von Lösungen aufwändig zu bestimmen ist, werden auch andere Ansätze verwendet: In [Polacek et al. 2004] wird z.B. wie bei der Metaheuristik “Threshold Accepting” eine Verschlechterung dann akzeptiert, wenn nach 10.000 Iterationsschritten keine neue amtierende Lösung gefunden wurde und x“ um nicht mehr als 5% schlechter als die bisher beste Lösung ist. In [Hemmelmayr et al. 2008] wird z.B. wie bei der Metaheuristik “Simulated Annealing” eine Verschlechterung nur mit gewisser Wahrscheinlichkeit akzeptiert, die mit dem Ausmaß der Verschlechterung abnimmt.

Literatur

Hansen, Pierre, Mladenović, Nenad: Variable neighborhoodr search. In: F. Glover and G. Kochenberger (Editors), Handbook ofr Metaheuristics, Kluwer Academic Publisher, New York 2003, S. 145-184.

Mladenović, Nenad, Hansen,r Pierre: Variabler neighborhood search. Computers and Operations Research 24 (1997), Nr. 11, S. 1097-1100.

Polacek,r Michael; Hartl, Richard F.; Doerner, Karl F.; Reimann, Marc: A Variable Neighborhood Search for the Multir Depot Vehicle Routing Problem with Time Windows. Journal of Heuristicsr 10 (2004), S. 613-627.

Hemmelmayr,r Vera C.; Doerner, Karl F.; Hartl, Richard F.: A Variable Neighborhood Searchr Heuristic for Periodic Routing Problems. European Journal ofr Operational Research 195 (2009), S. 791-802.