Wahl der Heuristik: Die Tabuliste als notwendiges Element
Next: Tabusuche als allgemeines Optimierungsverfahren Up: Verfahren 1: Tabusuche Previous: Allgemeine Betrachtungen zum Lösungsraum
Wahl der Heuristik: Die Tabuliste als notwendiges Element
Wie obige Überlegungen und auch die in Abschnitt 4.6 zeigen, stellt die hohe Symmetrie der harten Nebenbedingung,
die aber wegen der weichen Nebenbedingungen nicht durch Wahl einer anderen Kodierung beseitigt werden darf, ein
wesentliches Problem dar. Die einzige gängige und auch im Timetabling-Bereich eingesetzte Metaheuristik, die in
der Lage ist, dieses Problem zu bewältigen, ist die Tabusuche, da die Tabuliste so gestaltet werden kann, daß sie
permutierte Wiederholungen genauso ausschließt wie vollständige. ST¨UBER[St97] bezeichnet Tabusuche ebenfalls
als das einzig geeignete Verfahren für größere Probleme, zieht aber direkte Heuristiken noch vor.
Die meisten Implementierungen der Tabusuche (vgl. [Dow97]) ignorieren diesen Symmetriezusammenhang
dennoch und verwenden überwiegend direkte Kriterien, z.B. daß eine bestimmte Schulstunde zu einem bestimmten Zeitpunkt stattfindet.
In dieser Arbeit wurde bei der Konstruktion der Tabuliste dementsprechend ein anderes System verwandt: Sobald eine
Schulstunde aus einer konkreten Zeitstunde entfernt wird, wird ein Paar, bestehend aus einem Verweis auf sie und
eine zufällig gewählte andere Schulstunde, die in derselben Zeitstunde liegt, in die Tabuliste eingetragen. Die Tabubedingung ist nun, daß keine Stunden der beiden
zugehörigen Kurse mehr zusammengelegt werden dürfen. Diese Orientierung nach Kursen und nicht nach Stunden fördert
ein gleichartiges Verhalten zu einem Kurs gehöriger Stunden, was prinzipiell Blockungen (time-coherence
citecooper1993), d.h.
das Parallellegen mehrerer Stunden zweier Kurse fördert, ohne es allerdings hart zu erzwingen.
Des weiteren wird in [KMSV94] gezeigt, daß mittels direkter Abstiegsverfahren für k-Sat Probleme eine Approximationsgüte von 
erreicht werden kann.
Da bei geeigneter Wahl der Aspirationsfunktion (s. unten) die Tabusuche zu Beginn mit dieser einfachen Form der lokalen Suche identisch ist, könnte
diese Schranke somit erzwungen werden, wenn man die Zielfunktion analog zu [KMSV94] modifiziert. Wenn man aber annimmt, daß die Differenzierungsgröße in 
wächst, erreicht man damit also
bereits kein besseres Ergebnis als der triviale Algorithmus.
Next: Tabusuche als allgemeines Optimierungsverfahren Up: Verfahren 1: Tabusuche Previous: Allgemeine Betrachtungen zum Lösungsraum (c) Martin Loehnertz 1999