Nachbarschaftssuche

Nachbarschaftssuchverfahren sind iterative Metaheuristiken. Verwenden Sie solche Verfahren, falls exakte Algorithmen nicht anwendbar sind. Bei geeigneten Einstellungen können in mittlerer Laufzeit sehr gute Lösungen berechnet werden.

Grundlegendes Vorgehen:

Stellen Sie sicher, daß ein Problemtyp und alle Problemparameter definiert sind und bereits ein Plan existiert (den Sie mit einem anderen Algorithmus berechnen können). Wählen Sie den Menüpunkt Algorithmen | Nachbarschaftssuche. Nach Editieren der angezeigten Einstellungen drücken Sie den Start-Button.

Einstellungen

Nachbarschaft:
Definieren Sie, wie eine Plan aus einem anderen erzeugt wird:
API:
Zwei direkt benachbarte Operationen werden vertauscht.
Shift:
Eine Operation wird im Plan verschoben.
Critical-API:
Eine Cmax-kritische Operation wird mit einer direkt benachbarten Operation vertauscht.
Critical-Multi-API:
Eine Cmax-kritische Operation wird mit einer direkt benachbarten Operation vertauscht. Zusätzlich werden jeweils noch Vorgänger und Nachfolger mit anderen Operationen getauscht (3_CR).
Critical-Block-API:
Eine Cmax-kritische Block-End-Operation wird mit einer direkt benachbarten Operation vertauscht (BL_API).
Critical-Shift:
Eine Cmax-kritische Opreation wird im Schedule verschoben (CR_SHIFT).
Critical-Block-Shift:
Eine Cmax-kritische Block-End-Operation wird im Schedule verschoben (BL_SHIFT).
Suchverfahren:
Zur Auswahl stehen plain Iterative Improvement (Übergang zu einer Nachbarlösung erfolg nur, wenn diese besser ist), sowie zur Überwindung lokaler Optima die Erweiterungen Simulated Annealing (Akzeptierung einer schlechteren Lösung wird mit einer gewissen, kleiner werdenden Wahrscheinlichkeit), Threshold Accepting (Akzeptierung kleiner Verschlechterungen) und Tabusuche (nach Abtesten der Nachbarschaft stets Akzeptieren des besten gefundenen Nachbarn, bereits besuchte Lösungen werden ausgeschlossen).
Erzeuge Nachbarn:
In gro$szlig$en Nachbarschaften kann es sinnvoll sein, anstatt alle Nachbarn zu enumerieren, eine gewisse Anzahl von zufälligen Nachbarn zu betrachten (RANDOM, die enumerative Methode ist nicht für jede Nachbarschaft implementiert).
Erzeugte Lösungen:
Anzahl der Lösungen, die betrachtet werden. Danach bricht der Algorithmus ab.
Anfangsparameter:
Für Simulated Annealing die Wahrscheinlichkeit in Prozent, eine um 1 Prozent schlechtere Lösung im ersten Schritt zu akzeptieren. Für Threshold Accepting die maximal zulässige Verschlechterung im ersten Schritt in Promille.
Für die anderen Verfahren wird diese Einstellung ignoriert.
Erhöhung nach:
Um bei zu gering gewordener Temperatur/Threshold ein Stehenbleiben des Algorithmus in einem lokalen Optimum zu verhindern, wird nach sovielen Schritten Stillstand der jeweilige Parameter wieder soweit erhöht wie vor dem Stillstand.
Dieser Wert sollte nicht zu gering sein.
Tabulistenlänge:
Die Anzahl der Lösungen, die gleichzeitig tabu sein können.
Anzahl Nachbarn:
Nach sovieln erzeugten Nachbarn wird die Nachbarschaft der aktuellen Lösung als erschöpft angesehen. Diese Wert ist notwendig, falls die Nachbarn nicht enumeriert sondern zufällig erzeugt werden. Er sollte in angemessenem Verhältnis zur Größ der Nachbarschaft stehen.
Stillstand seit:
Die Suche wird abgebrochen, falls soviele Schritte keine neue Lösung mehr akzeptiert wurde.
ZF höchstens:
Die Nachbarschaftssuche wird abgebrochen, wenn der angegebene Zielfunktionswert erreicht oder unterschritten wurde.

Wenn Sie zu schlechte Ergebnisse erhalten:

Inhaltsverzeichnis
10.02.2000 TAU