Wahl der Algorithmen

Bei den im vorangegangenen Kapitel dargestellten Algorithmen neueren Datums wurde überwiegend nur das Suchproblem, nicht aber das Optimierungsproblem betrachtet.
Von einer optimalen Lösung des Suchproblems aus könnte zwar versucht werden, durch den Wechsel zu anderen optimalen Lösungen die schwachen Nebenbedingungen zu optimieren, aber dies scheitert zumeist daran, daß diese Algorithmen nicht gezielt zu einer anderen Lösung geführt werden können bzw. das beständige Reevaluieren zu aufwendig wäre. Zudem entspricht bereits die einfachste Form derartiger Veränderungen, das Vertauschen von Zeitstunden, einer beweisbar nichtapproximierbaren Variante des Problems des Handlungsreisenden.

Schon nach Implementierung der ersten Versuche stellte sich heraus, daß die Betrachtung eines einzelnen Verfahrens nicht ausreichend ist, da kein zuverlässiges Maß für die Schwierigkeit der Probleme gegeben ist, und dessen Funktionsfähigkeit daher nicht unabhängig bewertet werden kann. Das in Kapitel 7 beschriebene Verfahren lieferte, nachdem es auf einem kleinen Testfall annehmbar funktioniert hatte, erstmals auf ein reales Problem angewendet überwiegend schlechtere Ergebnisse, was im scheinbaren Widerspruch zu den Beobachtungen des vorangegangenen Praktikums stand, bei dem für größere, realistisch scheinende Testfälle stets funktionierende Pläne erzielt werden konnten.
Um diesen Effekt näher zu untersuchen, wurde das in Kapitel 6 beschriebene Verfahren implementiert, das, wenn man die Iterationszahl auf 1 beschränkt und das Verfahren auf ein reines STP anwendet, das gleiche Verhalten zeigen würde wie der im Praktikum betrachtete Algorithmus, durch zahlreiche Modifikationen dennoch aber auch in der Lage ist, die komplizierteren Problemstellungen des RSTP zu verarbeiten.
Da dieses zunächst das gleiche Verhalten zeigte, war hier ein prinzipielles Umdenken notwendig, da somit nicht mehr wie beim STP die Optimierung im Vordergrund stehen konnte, sondern zunächst nach einer einfachen Lösung gesucht werden mußte.

Der erste hier genauer untersuchte Algorithmus verbindet daher - wie zur Zeit im Timetabling-bereich häufiger versucht - zwei ältere Methoden miteinander, da diese in der Lage sind, relativ komplexe Nebenbedingungen zu berücksichtigen. Als grundlegendes Verfahren wird die von GLOVER 1989 eingeführte Tabusuche [Sch96] verwendet, da sie unter allen lokalen Suchverfahren am ehesten für das Problem der automatischen Stundenplanerstellung geeignet scheint. Um einen geschickteren Wechsel zwischen lokalen Optima zu erlauben, wird die Tabusuche dann mit einer gewichteten Variante des Algorithmus nach K¨ONIG hybridisiert, wobei diese von einem Reparaturschema unterstützt wird.

Der zweite Algorithmus stellt eine völlige Neuentwicklung dar, die die Vorteile von Metaheuristiken mit denen genetischer Algorithmen zu verbinden sucht. Ausgehend von der Beobachtung, daß bei einer Kodierung des UTP als GA zur Beschreibung einer Species bei einer mittleren Schule mindestens ca. 600 Kilobyte benötigt werden, erscheint es unrealistisch, mehrere hundert dieser Specimen effektiv verwalten und insbesondere auch gezielt mutieren zu wollen, auch wenn ein Speicheraufwand von 1 Mbyte heute natürlich keine Grenze mehr darstellt.

Daher wird hier jeweils nur mit einem Stundenplanmodell gearbeitet, dessen Kodierung aber auf viele Einzelentitäten verteilt. Jedes dieser Objekte - im weiteren als Agenten bezeichnet - versucht, das ihm zugeteilte Problem optimal zu lösen. Da sich die jeweils benötigten Ressourcen aber überschneiden, kommt es zu Konflikten zwischen den Optimierungsbestrebungen der einzelnen Agenten. Diese sollen durch ein Handels - und Auktionssystem bereinigt werden. Dabei wird insbesondere einen frei handelbaren Wert (Geld) mit einbezogen, was es nach [SS66] ermöglicht, gewisse lokale Minima zu verlassen. Neben dem Suchen brauchbarer Voraussetzungen für eine solidere theoretische Grundlage als sie BACHEM [BHM96] bietet, wurde eine erste Implementierung vorgenommen und deren Performanz im Vergleich mit dem obigen Verfahren bewertet.