Tabusuche als allgemeines Optimierungsverfahren
Next: Kodierung Up: Verfahren 1: Tabusuche Previous: Wahl der Heuristik: Die
Tabusuche als allgemeines Optimierungsverfahren
Auch wenn im vorangegangenen Kapitel und in Abschnitt 4.7 bereits einige Aspekte vorweggenommen wurden, soll in diesem
Kapitel ein kurzer Überblick über die Prinzipien der Tabusuche gegeben werden.
Im Gegensatz zu anderen lokalen Suchverfahren untersucht die Tabusuche nicht einen zufällig gewählten Punkt der
Nachbarschaft, sondern die gesamte bzw. eine ausgewählte Teilmenge der Nachbarschaft und geht dann zu deren
günstigsten Punkt über. Auf diesem Wege werden sehr schnell lokale Minima gefunden, aber das Verlassen eines
solchen wird nahezu unmöglich. Um dieses Kreisen zu verhindern, wird eine sog. Tabuliste geführt, in der
verbotene Operationen vermerkt werden. Im allgemeinen werden dort Charakteristika der letzten Operationen
gespeichert und ein Vorgang wird genau dann als nicht zulässig gewertet, wenn sein Inverses in der Tabuliste
auftritt. Sind diese Charakteristika allgemeiner gefaßt, was bei größeren Suchräumen sinnvoll ist, kann es
vorkommen, daß ein Nachbar als verboten gewertet wird, obwohl er noch nicht besucht wurde. Damit
er dennoch betrachtet wird, falls er eine deutliche Verbesserung erlaubt, wird eine sogenannte Aspiration-Funktion
hinzugefügt, die bei deutlichen Verbesserungen einem Wechsel zustimmt. Insgesamt läßt sich das Übergangsverhalten 
der Tabusuche für ein Minimierungsproblem mit Zielfunktion f wie folgt charakterisieren:
Beliebte Modifikationen der Tabusuche sind ([Dow97]):
- Verwendung wechselnder Zielfunktionen
- Variation der Tabulistenlänge
- Die Auswahl von Teilmengen der Nachbarschaft
- Ketten: Die Nachbarschaft entsteht nicht als Bild einfacher Operationen, sondern als Ergebnis iterierter Anwendung dieser Übergänge
- Veränderung einer Stunde
- Veränderung einer Zeitstunde
- Verschieben einer bestimmten Stunde aus oder in eine Zeitstunde
Ein effektiver Vergleich der Verfahren ist kaum möglich, es sei denn man entschiede sich, die Zielfunktion eines anderen Autors vollständig zu übernehmen, da als Bewertung eines Verfahrens zumeist auf den Vergleich des erreichten Zielfunktionswertes mit dem nachberechneten Funktionswert eines handerstellten Stundenplans zurückgegriffen wird [Sch96].
Next: Kodierung Up: Verfahren 1: Tabusuche Previous: Wahl der Heuristik: Die (c) Martin Loehnertz 1999