Direkt zum Inhalt | Direkt zur Navigation

Benutzerspezifische Werkzeuge

Sektionen

Kodierung

next up previous contents
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 tex2html_wrap_inline6672 . 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