Genetische Algorithmen / Evolutionsstrategien

Selektion:

Aus der Menge der Pläne wird ein bestimmter Prozentsatz ausgewählt, der sich durch besondere Qualität auszeichnet. Alle anderen werden entfernt.

Mutation:

Ein Plan wird geringfügig verändert (ggf. vorher kopiert).

Kreuzung:

Aus zwei Stundenplänen wird ein neuer generiert.

Es hat zahlreiche Versuche gegeben, GAs auf das Timetabling-Problem anzuwenden. Zur Codierung werden zumeist nicht klassische Bitstrings, sondern ganzzahlige Repräsentationen verwendet [CR97], auf denen dann Tauschoperationen durchgeführt werden. Die Ergebnisse sind, wie z.Zt. im Timetabling-Bereich noch häufig üblich, nicht vergleichbar. Es gibt seit Mitte 1997 Bestrebungen, ein einheitliches Datenformat für Probleme im Kontext der Automatischen Stundenplanerstellung zu schaffen [BKP97]; diese scheinen aber noch keine Wirkung zu zeigen.

Wie von ROSS, HART und CORNE [RHC97] beobachtet, zeigen sich bei Timetablingund Graphenfärbungsproblemen Schwierigkeiten bei der Anwendung dieser Verfahren. Ein Grund hierfür dürfte in der starken Trennung zwischen harten und weichen Constraints und in dem Widerspruch zwischen der großen Symmetrie der harten Constraints und deren Fehlen bei den weichen Nebenbedingungen liegen: Die Befriedigung der harten Bedingungen, insbesondere dabei der, daß kein Objekt zur selben Zeit an verschiedenen Orten sein kann, ist unter Permutationen der Zeitstunden invariant. D.h. ausgehend davon, daß es nur eine gute Lösung für das harte Suchproblem gibt, tritt dies bei einer die schwachen Nebenbedingungen ebenfalls beachtenden Darstellung und bei 40 zur Verfügung stehenden Wochenstunden 40! mal auf. Gerade wenn das Verfahren also schnell zu guten Lösungen konvergiert, wird dies also dazu führen, daß die selbe Lösung in jeweils anderer Erscheinungsform mehrfach auftritt. Eine Kreuzung kann also entweder nur zu einer weiteren Repräsentation desselben harten Typs oder zu einem ungültigen Plan führen, da die einkopierten Gene bei dem Zielchromosom an anderer Stelle vollkommen gleichartig auftreten.
Allgemeine Untersuchungen zur Funktion genetischer Algorithmen postulieren, daß sich bestimmte Schemata, d.h. bestimmte Abschnitte des genetischen Codes anderen gegenüber mit exponentiell wachsender Wahrscheinlichkeit durchsetzen, sofern sie diesen von der Zielfunktion her überlegen sind [Mic92]. Bei der oben angedeuteten großen Zahl guter Lösungen dürfte es aber zu jeder ausreichend kurzen Sequenz - die Wahrscheinlichkeit des Auftretens einer bestimmten langen Sequenz nimmt mit ihrer Länge exponentiell ab - eine Lösung geben, deren Teil sie ist. Die somit erfolgende Nivellierung der Schemata\ dürfte die Qualität des Verfahrens bis in die Nähe rein randomisierten Suchens reduzieren [RHC97]. Versuche, eine spezialisierte Form Genetischer Codes\ für Probleme dieses Typs zu schaffen, wurden unternommen, zeigten sich aber den herkömmlichen Verfahren unterlegen [EdHH98]. Außerdem kann keine wesentlich andere die verschiedenen Permutationen zusammenfassende Kodierung gewählt werden, da ansonsten eine Berücksichtigung der weichen Bedingungen nicht mehr möglich ist. Beobachtet wurde dieser Effekt z.B. von [MR97], die angeben, daß nach einer gewissen Zeit die Population aus lauter gleichguten Spezies bestehe.

Der größte Teil der Literatur zu genetischen Algorithmen im Timetabling (s. z.B. [CR97]) befaßt sich neben der Bestimmung von Zielfunktionen mit der Konstruktion von lokalen Reparaturverfahren, die ein durch Kreuzung entstandenes ungültiges Chromosom wieder im Sinne einiger Nebenbedingungen gültig machen sollen. Aufgrund der hohen Laufzeitanforderungen - es sollen zumeist mehrere tausend Kreuzungen vorgenommen werden - kommen hier allerdings nur die einfachsten Heuristiken in Frage, wie z.B. das Suchen einer beliebigen freien Stelle etc.