Direkt zum Inhalt | Direkt zur Navigation

Benutzerspezifische Werkzeuge

Sektionen
Sie sind hier: Startseite / Publikationen / Informatik / Theorie und Praxis der automatischen Stundenplanerstellung / Diplomarbeit / html / Hybridisierung mit einer Variante des Algorithmus nach K¨ONIG

Hybridisierung mit einer Variante des Algorithmus nach K¨ONIG

next up previous contents
Next: Implementierung dieses Verfahrens Up: Verfahren 1: Tabusuche Previous: Wahl der Nachbarschaft

Hybridisierung mit einer Variante des Algorithmus nach K¨ONIG

 

Anwendungsvoraussetzungen

Da dieses Verfahren dem Algorithmus von K¨ONIG folgt, verlangt es die Vorgabe eines bipartiten Graphen. Dieser ist im RSTP im allgemeinen nicht gegeben, die Abweichungen sind aber insbesondere im Bereich der Sekundarstufe I häufig auf wenige Differenzierungsstunden beschränkt. Voraussetzung ist somit in erster Linie die folgende Bedingung:

Bem1863

Bei der konkreten Umwandlung des UTP wird aus jeder Gruppe je ein Element aus jeder Teilmenge ausgewählt. Eine Lösung nach dem Satz von K¨ONIG garantiert also somit, daß bezüglich dieser Elemente keine Widersprüche auftreten können.
Im folgenden sei n die größere der beiden Knotenzahlen in dem so gewonnenen bipartiten Graphen und k die Zahl der Farben. Des weiteren sei basierend auf obiger Bemerkung vereinbart:

Def1870

 

Def1873

Die hiermit im Zusammenhang stehenden Überlegungen entspringen allerdings vollständig dem schulischen Kontext, da hier angenommen werden kann, daß Kollisionen in der im allgemeinen dritten Ressource Raum seltener sind und im Bereich von Schülern und Lehrern selten die Wahl zwischen verschiedenen Objekten möglich ist. Dies muß bei einer Universität oder Fachhochschule nicht mehr der Fall sein.

Gewichtetes Matching

  Beim Algorithmus nach K¨ONIG (Satz 4.3) spielen Matchings, die alle Knoten maximalen Grades überdecken, eine entscheidende Rolle (vgl. dort). Wie die Matchings abgesehen von dieser Eigenschaft aussehen, ist für das Funktionieren des Algorithmus nicht von Bedeutung.
Es ist daher möglich, andere Kanten nach Belieben hinzuzunehmen. Ersetzt man nun das im Algorithmus nach K¨ONIG auftretende einfache Matching durch gewichtetes Matching, so muß man lediglich dafür sorgen, daß stets alle Knoten maximalen Grades im zugehörigen Multigraphen von den jeweiligen Matchings überdeckt werden. Sei hierzu im Graphen G=(V,E) von einer Gewichtung tex2html_wrap_inline6732 des Graphen ausgegangen, die in irgendeiner Weise gewünschte Eigenschaften des Matchings kodiert. Sei A die Menge der Knoten mit maximalem Grad und tex2html_wrap_inline6736 . Dann definiere tex2html_wrap_inline6738 .

Lem1886

Beweis:
1. Satz 4.2 zeigt, daß es ein Matching gibt, das alle Knoten maximalen Grades überdeckt. Es genügt also zu zeigen, daß jedes Matching mit dieser Eigenschaft gemäß w' schwerer ist als jedes andere, da damit das schwerste Matching ingesamt eines von diesen sein muß. Ein Matching mit k<|A| überdeckten Knoten maximalen Grades hat aber offenbar ein Gewicht von höchstens tex2html_wrap_inline6748 , während ein Matching mit |A| überdeckten Kanten mindestens das Gewicht tex2html_wrap_inline6752 hat.
2. Da alle Matchings, die alle Knoten maximalen Grades überdecken, gleichviele dieser Knoten überdecken, gilt für ein derartiges Matching stets w'(M)=w(M)+c*|A| und somit ist für diese tex2html_wrap_inline6756 .

Eine ähnliche Idee findet sich in [CdW89], wobei diese Autoren die Gewichtungsmöglichkeit ausschließlich zur Erzwingung der gewünschten Überdeckung von Knoten maximalen Grades verwendengif, aber nicht explizit auf die Garantien eingehen. Des weiteren finden sich ähnliche Überlegungen in [dW71]. Eine Frage, die sich an dieser Stelle ebenfalls stellt, ist, ob alle Kanten um einen solchen, die übrige Bewertung dominierenden Betrag vergrößert werden sollten, um stets maximale Matchings maximalen Gewichts zu erhalten. Auch wenn dies im Sinne der harten Nebenbedingungen sinnvoll wäre, wurde hier davon abgesehen, da hiervon insbesondere die Nichtverfügbarkeiten betroffen würden, die zumeist ähnlich wichtig sind.
Zur Gewichtung können nun mehrere Kriterien herangezogen werden:  

  • Die Tatsache, ob für ein Objekt die Zahl der noch zu setzenden Stunden gleich der Zahl der noch verbleibenden Stunden ist. Dieses Kriterium ist nicht hinreichend für eine Lösbarkeit des RSTP, da nicht berücksichtigt wird, ob sich diese Stunden auch tatsächlich plazieren lassen.
  • Analog bei flexiblen Ressourcen, ob die Zahl der noch zu benutzenden Objekte gleich der Objektzahl multipliziert mit der Zahl der verbleibenden Zeitstunden ist.
Die folgenden Varianten könnten sinnvolle Erweiterungen darstellen:
  • Die Tatsache, daß die entsprechende Stunde tight nach den Kriterien von GOTTLIEB ist, was eine Verbesserung im obigen Sinne darstellt, aber auch nicht hinreichend ist.
  • Werte, die repräsentieren, wie weit die Stunde noch von den gerade beschriebenen Tatsachen entfernt ist, das heißt zum Beispiel, um wieviel die Zahl der verbleibenden Stunden größer ist, als die der benötigten. Dies führt zu einer Art Lookahead.
  • Die zeitbezogenen Anforderungen bzw. Wünsche der Objekte.
  • Relative Nebenbedingungen, sofern bereits andere Stunden gesetzt wurden.
In der bisherigen Implementierung wurden die Gewichtungen der übrigen Parameter noch unmittelbar aus den von Benutzer gewählten Werten bezogen. Hierbei ist aber zu beachten, daß diese zumeist relativ sind. Gibt der Anwender z.B. an, daß zwei Stunden gleichermaßen am Montag liegen können, die eine aber besonders für Dienstage geeignet ist, während die andere möglichst nicht an diesem Tag liegen sollte, so können diese beiden bei der Betrachtung des Montags nicht mehr die gleiche Bewertung erhalten, da die Auswahl somit zufällig wäre. Daher wäre es vermutlich sinnvoll, die absoluten Parameter durch ihren relativen Anteil an der Summe der Parameter zu ersetzen.

Für die Hybridisierung günstige Eigenschaften

Auch mit einigen Modifikationen läßt sich dieses Verfahren, das lange Zeit das einzige polynomielle des gesamten Gebietes war, nicht dazu verwenden, kompliziertere Zielfunktionen zu verfolgen bzw. Differenzierungen und Raumzuteilungen zufriedenstellend zu lösen. Es hat aber, und aus diesem Grunde wurde es dem Verfahren nach GALVIN vorgezogen, die Eigenschaft, eine in der Bewertungsmatrix kodierte gültige Färbung zu erhalten: Die Lehrer-Klassen-Kanten (oder eine Auswahl derselben beim RSTP) müssen bei einer gültigen Lösung zu jeder Zeitstunde ein Matching bilden, das alle Knoten kritischen Grades überdeckt. Versieht man also in einem entsprechenden gewichteten Graphen diese Kanten mit dem Gewicht 1 und wertet die andern mit 0, so wird der obige Algorithmus ein Matching finden, das diese Kanten verwendet. Faßt man also den Algorithmus als eine Funktion tex2html_wrap_inline6656 auf, die aus dem tex2html_wrap_inline6766 in die Menge S der KL-geeigneten Stundenpläne über G führt, so ist diese surjektiv, da man jeden Zielpunkt erreichen kann, indem man ihn in die Eingabe 0,1-kodiert. Sei tex2html_wrap_inline6774 . Damit könnte der Algorithmus also als Postoptimizer für beliebige andere Verfahren verwandt werden.

tex2html_wrap6790

Andererseits erlaubt es dies aber auch, diesen Algorithmus als Bestandteil einer komplexeren Zielfunktion zu sehen. Mit einer gegebenen Bewertung tex2html_wrap_inline6776 erhält man durch tex2html_wrap_inline6778 eine Abbildung von tex2html_wrap_inline6780 nach tex2html_wrap_inline6782 . Nimmt man G als fest an, so erhält man also eine Optimierungsaufgabe der Form:
Finde tex2html_wrap_inline6786 , so daß tex2html_wrap_inline6788 maximal wird. Im folgenden sollen die Auswirkungen dieser Veränderung diskutiert werden.

Auswirkungen der Hybridisierung

Häufig wird in der Literatur zum Timetabling angegeben [Dow97], daß die Oberfläche der Zielfunktionen durch steile, schmale Täler bzw. Löcher geprägt sein kann. Zudem verrät die Struktur der umliegenden Funktionswerte, die von Springstundenminimierung o.ä. geprägt wird, selten die günstigste Richtung zu einem solchen Tal, da es z.B. ungültige Lösungen mit wenigen Springstunden geben kann.
Durch das oben beschriebene Zwischenschalten des Kantenfärbungsalgorithmus werden diese Täler künstlich verbreitert, da nun die benachbarten Lösungen zu KL-geeigneten Lösungen umgeformt werden.
Es bleiben insbesondere beim RSTP natürlich auch Täler erhalten, die durch die nichtbeachteten Gruppenmitglieder (s. Abschnitt 6.6.1) erzeugt werden; diese sind aber nicht so tief. Dies wirkt sich allerdings andererseits auch so aus, daß nun große Gebiete mit gleichem Funktionswert entstehen, da für viele Punkte bereits die Eingabe der Zielfunktion identisch ist. Gerade auf der Traversierung solcher Flächen beruhten aber die Fortschritte moderner Metaheuristiken gegenüber klassischen Minimierungsverfahren.
Zudem muß man sich - im Gegensatz zum Problem der Täler - hiermit nicht abfinden, da man diesen Flächen eine zusätzliche Struktur aufprägen kann:

  • Die weichen Bedingungen können z.T. über der Eingabe des Graphenalgorithmus ausgewertet werden.
  • Der Kontrast zwischen einzelnen Werten kann reduziert werden, so daß ein schnellerer Wechsel bei der Ausgabe des Graphenalgorithmus erfolgt.
  • Der Abstand zu der Lösung eines relaxierten Problems, z.B. eines LPs, kann hinzugenommen werden, so daß vornehmlich in dessen Nähe gesucht wird.

Innerhalb der Tabusuche gibt es zwei Stellen, die es erlauben, diesen Filterprozess zu integrieren, abgesehen von einer Verwendung als Pre- oder Postprocessor:

tex2html_wrap6796

Den oben geäußerten Ideen würde es am besten gerecht, wenn das Filterverfahren in der inneren Schleife (1) integriert würde, also zu jeder Berechnung der Zielfunktion herangezogen würde. Dies würde aber, um noch eine ausreichende Geschwindigkeit gewährleisten zu können, verlangen, die Nachbarschaft ausreichend klein zu wählen, so daß die Zahl der Iterationen entsprechend gedrückt würde.
Eine Möglichkeit dies zu realisieren, wäre eine Form von Metropolis-Verfahren mit Tabuliste, da hier aus der Nachbarschaft jeweils nur ein Element ausgewählt würde. Hier träte allerdings das Problem auf, daß dieses Verfahren insgesamt mehr Einzelschritte vollziehen muß als die Tabusuche.
In dieser Arbeit wurde der andere Weg beschritten und das Suchverfahren als nachträglicher Filterschritt vorgesehen, was wesentlich weniger laufzeitaufwendig ist, aber eher einem memetischen Algorithmus entspricht (vgl. [BNW95]). Dies wiederum kann dazu führen, daß diese Nachbearbeitung die Veränderungen, die durch das Suchverfahren vorgenommen werden, revidiert.gif Um diesem entgegenzuwirken, werden die Zeitstunden vor Anwendung des Filterschritts zufällig permutiert. Die Wahrscheinlichkeit, ob dies funktioniert, ist allerdings vom jeweiligen Problem abhängig, da es durchaus vorkommen kann, daß eine bestimmte Schulstunde nur in einer bestimmten Zeitstunde liegen darf.
Geht man allerdings davon aus, daß keine Zeitwünsche gegeben sind, und daß die entsprechende Stunde nicht mehr von der Wahl der übrigen Stunden beeinflußt wird, so sinkt sie unter tex2html_wrap_inline6794 , da der Filter sie unabhängig von der gewählten Permutation stets im gleichen Bearbeitungsschritt setzt. Die Wahrscheinlichkeit, daß eine Stellung vollständig rekonstruiert wird, ist entsprechend geringer, aber nicht das Produkt dieser Wahrscheinlichkeiten, da die Ereignisse nicht unabhängig sind.

Nachbearbeitung

   Offenbar hat das obige Verfahren den Nachteil, daß bezüglich der nichtbeachteten Gruppenobjekte Widersprüche auftreten können. Ließe man nun einfach die entsprechenden Kanten weg, so würde dies nur dazu führen, daß diese entweder nicht gesetzt werden oder irgendwann zu unbedingt notwendigen Kanten würden, so daß diese dann trotz ihrer Kollisionen eingesetzt werden müßten.

Gestaffelte Ressourcenoptimierung

  Wurde nach obigem Verfahren eine Menge von Stunden ermittelt, die in die momentan betrachtete Zeitstunde gelegt werden sollen, so ist noch zu überprüfen, daß diese nicht wegen nicht im Graphen repräsentierter Gruppenmitglieder kollidieren. Im Gegensatz zur Vorgehensweise in Abschnitt 8.4.3 reicht es hier allerdings nicht, nicht setzbare Stunden nur zu markieren, sondern es sollen möglichst viele Stunden gesetzt werden. Dies entspricht aber dem Set-Packing Problem, welches selbst wieder tex2html_wrap_inline5146 -schwer ist. Standardansatz wäre hier eine LP-Relaxation mit anschließendem Runden (vgl. [Hoc97]), aber der zeitliche Aufwand wäre für eine Subroutine einer Metaheuristik zu hoch. Glücklicherweise liegt aber ein zusätzliches Kriterium vor, nämlich die Wichtigkeit der Stunden. Sei also angenommen, es existiere eine vollständige Ordnung O auf den m Stunden, die ausgewählt wurden, und seien diese so angeordnet, daß tex2html_wrap_inline6804 . Dann kann im Abschnitt 8.4.3 analog zu und mit demselben Beweis wie in Abschnitt 6.6.2 eine Bewertung der Kanten vorgenommen werden, bei der alle Kanten, die in bezug zur Gruppe tex2html_wrap_inline6253 stehen, den Wert tex2html_wrap_inline6808 erhalten. Bestimmt man nun ein maximal gewichtetes Matching in diesem Graphen, so werden zunächst die Gruppen mit hohem Index befriedigt, bevor eine mit niedrigem Index überhaupt eine einzige Kante erhält. Dieses Verfahren ist natürlich nicht optimal - es wäre es nur, wenn die Gruppen mit den größten Indices ein maximales Packing bilden würden, aber es ist dennoch dem Greedy-Verfahren, das Gruppen wählt solange sie passen, überlegen, da dieses auch dann, wenn eines existiert, kein Matching der bevorzugten Komponenten garantieren kann.
Auch wenn nur tex2html_wrap_inline6810 , also polynomiell viele Bits zur Kodierung dieser Gewichtungen benötigt würden, scheint es im Rahmen dieser konkreten Anwendung sinnvoller, sich mit den zur Verfügung stehenden Zahldarstellungen zu beschränken, und stattdessen die Gruppen in mehrere Mengen aufzuteilen.

Tritt eine Ressource stets im Zusammenhang mit den gleichen dynamischen Ressourcen auf, so könnte wenn man das Matching- durch das analoge Flußproblem ersetzt, diese Ressource den dynamischen vorgeschaltet werden, was die Kollisionszahl vermindern würde, da diese Ressourcen nur noch gleichzeitig oder gar nicht benutzt werden können, wobei die selbe Konstruktion entstehen würde, wie in Abbildung b) in Kapitel 3.6.1. Verzichtet man darauf, die optimale Zuordnung zu wählen, so kann die Existenz auch mit Hilfe des nichtgewichteten Algorithmus geprüft werden (s. Abschnitt 6.7).

Alternierende Kreise

  Wird festgestellt, daß eine der gewählten Stunden die vorhandenen Ressourcen überschreitet, so wird versucht, diese zu entfernen. Das hier eigentlich notwendige Konzept wäre das von Matchings mit Ressourcenbeschränkungen, die aber, wie schon in Abschnitt 4.10.7 erwähnt für den gegebenen Fall nicht effizient bestimmt werden können.
Wie in Abschnitt 4.3.3.1 dargestellt, ist es bei der Untersuchung verschiedener Matchings in Graphen interessant, deren symmetrische Differenz zu betrachten. Vergleicht man nun zwei maximale Matchings miteinander, so besteht ihre symmetrische Differenz aus Pfaden gerader Länge und Kreisen, da es keine augmentierenden Wege mehr geben darf und somit ein Pfad ungerader Länge immer fortgesetzt werden kann. Wird das Matching über einen alternierenden Kreis modifiziert, bleibt, im Gegensatz zu der Verwendung von Pfaden, die Menge der vom Matching überdeckten Knoten gleich. Insbesondere erhält eine Veränderung nach diesem Schema also die Eigenschaft eines Matchings, Knoten kritischen Grades zu überdecken. Somit bietet sich das Suchen solcher Kreise an, um Matchings nachträglich zu verbessern.
Hierbei muß dafür gesorgt werden, daß die neu hinzugekommenen Kanten nicht andere Ressourcenüberschreitungen verursachen. Daher werden hierfür nur Kanten zugelassen, die nicht mit einer Differenzierungsstunde korrespondieren. Dieses Vorgehen folgt der Überlegung, daß im Bereich des RSTP damit zu rechnen ist, daß sich räumliche Probleme relativ leicht beheben lassen, da es häufig möglich ist, Unterricht auch in Nicht-Fachräumen durchzuführen. Diese Annahme muß bei anderen Planungsaufgaben natürlich nicht gegeben sein.
Betrachtet man den Gesamtwert eines solchen Matchings, so verringert sich dieser bei Alternieren über einen solchen Kreis um das Gewicht der beteiligten Matchingkanten und es vergrößert sich um das der Nicht-Matching-Kanten. Da es tex2html_wrap_inline5146 -vollständig ist, in einem Graphen den längstmöglichen Weg zu suchen, kürzeste Wege auf Netzwerken mit positiven Kantengewichten schneller bestimmt werden können als auf allgemeinen und es insgesamt wünschenswert ist, den Graphen so wenig wie möglich zu verändern, werden die Kantengewichte wie folgt modifiziert und als Entfernungen interpretiert, damit der Algorithmus von DIJKSTRA [Jun90] anwendbar wird: Sei tex2html_wrap_inline6814 . Dann setze

displaymath6816

Danach wird solange noch Widersprüche auftreten, aber nur nmal (es muß nicht notwendigerweise möglich sein, alle Kollisionen zu beseitigen) die folgende Routine durchgeführt, wobei die Partitionen des Graphen im folgenden mit links und rechts bezeichnet seien.

  • Bestimme eine Kante e=(l,r), die maximal viele Kollisionen auslöst.
  • Bestimme den alternierenden Kürzeste-Wege-Baum [Blu98] von r zu allen anderen Knoten auf der rechten Seite (s.u.)
  • Bestimme denjenigen Knoten tex2html_wrap_inline6824 auf der rechten Seite, bei dem die Summe von Entfernung im Baum und Abstand zu l minimal sind.
  • Vertausche entlang des durch (l,p), den kürzesten Weg von p zu r und (l,r) gegebenen Kreises Matching - und Nicht-Matching - Kanten.
Einer genaueren Erläuterung bedarf noch die Konstruktion des alternierenden Baumes. Die ausgewählte Kante sei wie oben (l,r). Hierzu betrachte man das gerichtete Netzwerk H=(R,E,w), wobei R die Knoten der rechten Seite im bipartiten Graphen sein sollen (analog L) und

displaymath6844

Da dieses z eindeutig bestimmt ist, sei tex2html_wrap_inline6848 .

displaymath6850

Lem2005

Beweis
Hierzu genügt es, zu zeigen, daß es zu jedem einfachen alternierenden Pfad von R nach R in G einen Pfad gleichen Gewichtes in H gibt und umgekehrt.
tex2html_wrap_inline6168 : Jeder von r ausgehende alternierende Pfad muß mit einer Nicht-Matching-Kante beginnen, da tex2html_wrap_inline6872 entfernt wurde. Damit erfolgt der Übergang zu einem anderen tex2html_wrap_inline6874 stets über eine Abfolge von Nicht-Matching-Kante und Matching-Kante und somit muß man, um einen Weg in H zu erhalten, einfach jeden zweiten Knoten des Weges in G' entfernen. Das Gewicht des Pfades ist nach Definition die selbe.

tex2html_wrap_inline6170 : Sei ein einfacher Pfad in H tex2html_wrap_inline6884 gegeben. Dann wähle den Pfad tex2html_wrap_inline6886 in G. Dieser hat offenbar die selbe Länge wie P und ist alternierend. Es bleibt nur zu zeigen, daß er einfach ist. Keines der tex2html_wrap_inline5172 kann doppelt auftreten, da dann P nicht einfach wäre. Sei also angenommen, daß ein tex2html_wrap_inline6896 mehrfach auftritt z.B. als tex2html_wrap_inline6898 . Da aber die Kante tex2html_wrap_inline6900 sein muß und tex2html_wrap_inline6902 gilt, da jede Matching-Kante nur zu je einem Knoten in L und R inzident ist, folgt daraus unmittelbar tex2html_wrap_inline6908 , was wiederum implizieren würde, daß P nicht einfach war.
Das Entfernen von l bzw. (l,r) ist notwendig, da diese benötigt werden, um den Weg zu einem Kreis zu schließen.

tex2html_wrap6918

Die Abbildung zeigt einen Alternierungsvorgang, wobei als Kreis in H die grau unterlegten Kanten gewählt wurden.

Gruppen, die nun immer noch nicht mit Ressourcen versehen wurden, werden entfernt bzw. sollte die zugehörige Kante im Graphen kritisch sein, als Kollision in Kauf genommen. Eventuell könnte hier noch versucht werden, weitere Gruppen greedy hinzuzufügen.


next up previous contents
Next: Implementierung dieses Verfahrens Up: Verfahren 1: Tabusuche Previous: Wahl der Nachbarschaft

(c) Martin Loehnertz 1999