Variable Neighborhood SearchVariable 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ć ist eine auf lokaler Suche basierende Metaheuristik. Sie nutzt systematisch eine Reihe von Nachbarschaften N1, ..., NK die typischerweise geschachtelt sind, also Nk+1 enthält Nk. Die einfachste Variante ist das sogenannte Variable Descent (VND) Verfahren. Komplexere Varianten sind reduced, basic, general und skewed VNS. Variable
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:
Wichtige Designentscheidungen sind die Anzahl und Größe der Nachbarschaften. (basic) Variable
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.
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 VerschlechterungenDa 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. LiteraturHansen, Pierre, Mladenović, Nenad: Variable neighborhood search. In: F. Glover and G. Kochenberger (Editors), Handbook of Metaheuristics, Kluwer Academic Publisher, New York 2003, S. 145-184. Mladenović, Nenad, Hansen, Pierre: Variable neighborhood search. Computers and Operations Research 24 (1997), Nr. 11, S. 1097-1100. Polacek, Michael; Hartl, Richard F.; Doerner, Karl F.; Reimann, Marc: A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows. Journal of Heuristics 10 (2004), S. 613-627. Hemmelmayr, Vera C.; Doerner, Karl F.; Hartl, Richard F.: A Variable Neighborhood Search Heuristic for Periodic Routing Problems. European Journal of Operational Research 195 (2009), S. 791-802.
AutorO.Univ.Prof. Dr. Richard Hartl, Universität Wien, Lehrstuhl f. Produktion u. Logistik, Bruennerstr. 72, A - 1210 Wien |