Genetische Algorithmen / Evolutionsstrategien
Next: Lokale Suchverfahren: Simulated Annealing Up: Lösungsansätze Previous: Constraintbasierte Verfahren
Genetische Algorithmen / Evolutionsstrategien
Die natürliche Evolution war das Vorbild für dieses Verfahren. Ausgehend von einer Modellierung verschiedener Stundenpläne als Lebewesen (Chromosomen, Bitstränge u.s.w.) werden drei Typen von Operationen auf diese angewandt:- 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.
Next: Lokale Suchverfahren: Simulated Annealing Up: Lösungsansätze Previous: Constraintbasierte Verfahren (c) Martin Loehnertz 1999