Direkt zum Inhalt | Direkt zur Navigation

Benutzerspezifische Werkzeuge

Sektionen
Sie sind hier: Startseite / Publikationen / Informatik / Theorie und Praxis der automatischen Stundenplanerstellung / Diplomarbeit / html / Tabusuche als allgemeines Optimierungsverfahren

Tabusuche als allgemeines Optimierungsverfahren

next up previous contents
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 tex2html_wrap_inline6656 der Tabusuche für ein Minimierungsproblem mit Zielfunktion f wie folgt charakterisieren:

equation1784

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
Typische Implementierungen der Tabusuche im Bereich der automatischen Stundenplanerstellung verwenden als Übergangsoperationen einfache Tausch- oder Verschiebungsoperationen ([Sch96]). Die meisten Formen von Tabulisten umfassen einen oder mehrere der folgenden Ereignistypen ([Dow97],[Cos94]):
  • Veränderung einer Stunde
  • Veränderung einer Zeitstunde
  • Verschieben einer bestimmten Stunde aus oder in eine Zeitstunde
Die Anwendung anspruchsvollerer Methoden der Tabusuche scheint mehr durch empirische Ergebnisse und individuelle Entscheidungen geleitet zu werden als durch tiefere Kenntnis der Problemstruktur.
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 up previous contents
Next: Kodierung Up: Verfahren 1: Tabusuche Previous: Wahl der Heuristik: Die

(c) Martin Loehnertz 1999