Tabu Search

Tabu Search ist eine deterministische Meta-Strategie zur Steuerung heuristischer Verbesserungsverfahren, die grundsätzlich in jeder Iteration zu einer Nachbarlösung mit dem besten Zielfunktionswert übergeht. D.h., es wird jeweils ein Zug ausgeführt, der die größtmögliche Verbesserung oder, falls dies nicht möglich ist, die kleinstmögliche Verschlechterung des Zielfunktionswertes erzielt. Um nach einer Verschlechterung nicht zu bereits aufgesuchten Lösungen zurückzukehren, müssen diese zeitweilig verboten (tabu gesetzt) werden. Die gegebenenfalls aufwändige Speicherung solcher Lösungen lässt sich vermeiden, indem man bestimmte Lösungseigenschaften (Attribute) tabu setzt und Züge verbietet, die solche früher bestehenden Attribute wiederherstellen. Tabu gesetzte Attribute (oder tabu gesetzte Züge) werden in einer Tabuliste gespeichert. Das Verfahren endet, sobald ein Abbruchkriterium erfüllt ist, z.B. bei Erreichen einer vorgegebenen Iterationsanzahl oder nach Ablauf einer maximalen Rechenzeit.

<< vorhergehender Begriff

nächster Begriff >>

Tablar

TACIS-Programm