Kodierung
Next: Wahl der Nachbarschaft Up: Verfahren 1: Tabusuche Previous: Tabusuche als allgemeines Optimierungsverfahren
Kodierung
Als Kodierung wird die Zuordnung von Schulstunden zu Zeitstunden gewählt, wobei diese als 0,1 Matrix dargestellt wird.
Eine Kodierung via Listen wäre weniger speicheraufwendig, hätte aber den Nachteil, daß entweder der Zugriff
auf die Tabuliste oder der Zugriff auf kollidierende Stunden verlangsamt würde. Die Ressourcenzuteilung wird - wie
in Abschnitt 5.2.1 angedeutet - jeweils neu berechnet. Im Gegensatz zu bitstringorientierten
Verfahren wie genetischen Algorithmen ist hier die konkrete Kodierung nicht relevant für die ohnehin kaum
quantifizierbare Konvergenzgeschwindigkeit, da sämtliche Operationen auf einer abstrakteren Ebene angesiedelt sind,
d.h. in Notationen von Stunden und Klassen, und die Implementierung diese lediglich umsetzt. Analog werden
in der Tabuliste auch nicht einzelne Bitpositionen vermerkt, sondern Paare von Schulstunden.
Etwas formaler gesprochen: Seien zwei Kodierungen C,C' gegeben, die durch eine Funktion f ineinander
überführt werden können, und eine Übergangsfunktion g, die mit C operiert, so ergäbe sich die entsprechende Übergangsfunktion
für C' einfach als . Insofern ist die Kodierung nur für die Laufzeit relevant, wobei zu berücksichtigen ist, daß das Verfahren
natürlich eine hohe Iterationszahl verlangt.
Eine Umkodierung des
gesamten Problems in eine Form, die es erlaubt hätte, die Tabuliste in Form des Festhaltens einzelner Bits\
zu kodieren, hätte zwar die Möglichkeit eröffnet, die zurückgelegte Strecke im Form der Hamming-Distanz zu
bestimmen und z.B. zur Steuerung der Tabulistenlänge zu verwenden [Bat96], dies scheint aber den damit
verbundenen Aufwand nicht zu rechtfertigen, da dies zudem verlangen würde, wiederkehrende Punkte zu erkennen.
(c) Martin Loehnertz 1999