Upload
lethuy
View
228
Download
0
Embed Size (px)
Citation preview
Arbeitsbericht Nr. 05/2007 Hrsg.: Matthias Schumann
Ole Brodersen, Matthias Schumann
Einsatz der Particle Swarm Optimization zur Optimierung universitärer Stundenpläne
Arbeitsbericht
des Instituts für Wirtschaftsinformatik
Professur für Anwendungssysteme und E-Business
Georg-August-Universität Göttingen
Platz der Göttinger Sieben 5
37073 Göttingen
Working Paper
Institute of Information Systems
Chair of Application Systems and E-Business
University of Goettingen
Platz der Goettinger Sieben 5
37073 Goettingen, Germany
Tel. +49 (0) 551 / 39-4442
Fax +49 (0) 551 / 39-9735
www.as.wiwi.uni-goettingen.de
This work is licensed under the Creative Commons Attribution-Noncommercial-No Derivative Works 2.0 Germany License. To
view a copy of this license, visit http://creativecommons.org/licenses/by-nc-nd/2.0/de/ or send a letter to Creative Commons,
543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.
Abstract I
Abstract
Particle Swarm Optimization (PSO) has proven to be a good metaheuristic for continuous optimization
problems. In this paper we present a solution for applying the PSO to a combinatorial optimization
problem of a real data university course timetabling problem. We first describe the considered
situation of the faculty of philosophy of the University of Goettingen and describe how PSO works in
general. After that the PSO for this combinatorial optimization problem is introduced and the
experiments and results are provided. Different parameter settings show that PSO provides good
results for this university course timetabling problem and is applicable to combinatorial optimization
problems.
Keywords:
Particle Swarm Optimization, Course Timetable Scheduling, Combinatorial Optimization, Swarm
Intelligence
Stichwörter:
Particle Swarm Optimization, Universitäre Stundenplanung, Kombinatorische Optimierung,
Schwarmintelligenz
Inhaltsverzeichnis II
Inhaltsverzeichnis
Abbildungsverzeichnis ........................................................................................................................ IV
Tabellenverzeichnis ............................................................................................................................. VI
Abkürzungs- und Variablenverzeichnis ............................................................................................ VII
1 Einleitung ...........................................................................................................................................1
2 Universitäre Stundenplanung ..........................................................................................................2
2.1 Einordnung ..................................................................................................................................2
2.2 Allgemeine Problembeschreibung...............................................................................................2
2.3 Problem der Philosophischen Fakultät der Universität Göttingen...............................................4
2.3.1 Annahmen...........................................................................................................................7
2.3.2 Formulierung des mathematischen Modells.......................................................................9
2.4 Lösungsverfahren......................................................................................................................10
3 Particle Swarm Optimization..........................................................................................................13
3.1 Idee und Ursprung.....................................................................................................................13
3.1.1 Boids .................................................................................................................................13
3.1.2 Vogelschwärme ................................................................................................................14
3.2 Metaheuristik für kontinuierliche Problemstellungen .................................................................14
3.2.1 Canonical PSO .................................................................................................................14
3.2.2 Restriktionsbehandlung ....................................................................................................16
3.2.3 Nachbarschaftsbeziehungen ............................................................................................17
3.2.4 Geschwindigkeitsupdate...................................................................................................18
3.3 Metaheuristik für kombinatorische Problemstellungen..............................................................19
4 Experimente.....................................................................................................................................21
4.1 Versuchsaufbau.........................................................................................................................21
4.2 Ausgewählte Ergebnisse ...........................................................................................................22
4.2.1 Experiment #3...................................................................................................................22
Inhaltsverzeichnis III
4.2.2 Experiment #6...................................................................................................................23
4.2.3 Experiment #19.................................................................................................................24
4.2.4 Experiment #22.................................................................................................................24
4.2.5 Experiment #24.................................................................................................................25
4.2.6 Experiment #25.................................................................................................................26
4.2.7 Experiment #28.................................................................................................................26
4.2.8 Zusammenfassung und Vergleich ....................................................................................27
5 Zusammenfassung und Ausblick..................................................................................................30
Literaturverzeichnis .............................................................................................................................31
Abbildungsverzeichnis IV
Abbildungsverzeichnis
Abbildung 2-1: Einordnung der universitären Stundenplanung............................................................... 2
Abbildung 2-2: Konzept der Terminplanung im Allgemeinen (links) und speziell für universitäre
Stundenplanung (rechts)............................................................................................................. 3
Abbildung 2-3: Vorgeschlagene Fächerkombinationen der LehrerInnenausbildung für Niedersachsen
(graue Felder).............................................................................................................................. 5
Abbildung 2-4: Manuell erstellter Stundenplan auf Basis der Terminwünsche der Dozierenden ........... 6
Abbildung 2-5: Verteilung der Pflichtveranstaltungen auf die vorhandenen Zeitfenster ......................... 7
Abbildung 3-1: Regeln des Boids-Modells (modifiziert aus Reynolds 2001) ........................................ 13
Abbildung 3-2: Pseudocode für PSO .................................................................................................... 15
Abbildung 3-3: Restriktionsbehandlung................................................................................................. 17
Abbildung 3-4: Nachbarschaftstopologien gBest (global), circle (Größe = 3), wheel, 4 clusters (star),
pyramide (Mendes/Kennedy/Neves 2003a, Kennedy/Eberhart/Shi 2001) ............................... 18
Abbildung 3-5: Ablauf der PSO für die Lösung der kombinatorischen Problemstellung eines
Stundenplanproblems ............................................................................................................... 20
Abbildung 4-1: Verlauf der besten gefundenen Werte und Konvergenzverhalten der Partikel im
Experiment #3 ........................................................................................................................... 22
Abbildung 4-2: Verlauf der besten gefundenen Werte und Konvergenzverhalten der Partikel im
Experiment #6 ........................................................................................................................... 23
Abbildung 4-3:Verlauf der besten gefundenen Werte und Konvergenzverhalten der Partikel im
Experiment #19 ......................................................................................................................... 24
Abbildung 4-4: Verlauf der besten gefundenen Werte und Konvergenzverhalten der Partikel im
Experiment #22 ......................................................................................................................... 24
Abbildung 4-5: Verlauf der besten gefundenen Werte und Konvergenzverhalten der Partikel im
Experiment #24 ......................................................................................................................... 25
Abbildung 4-6: Verlauf der besten gefundenen Werte und Konvergenzverhalten der Partikel im
Experiment #25 ......................................................................................................................... 26
Abbildung 4-7: Verlauf der besten gefundenen Werte und Konvergenzverhalten der Partikel im
Experiment #28 ......................................................................................................................... 26
Abbildung 4-8: Verlauf der einzelnen Constraints bei einem Gesamtfitnesswert von 250 der
Variante #6 für das Positionsupdate der PSO. ......................................................................... 27
Abbildung 4-9: Fitnessmittelwerte der durchgeführten Experimente in Abhängigkeit von der
Schwarmgröße.......................................................................................................................... 28
Abbildungsverzeichnis V
Abbildung 4-10: Optimierter Stundenplan ............................................................................................. 29
Tabellenverzeichnis VI
Tabellenverzeichnis
Tabelle 1: Unterschiede der Stundenplanung an Schulen und Universitäten......................................... 4
Tabelle 2: Bestrafung bei Verletzung der Nebenbedingungen. .............................................................. 9
Tabelle 3: Einsatz von Metaheuristiken für die Stundenplanerstellung ................................................ 12
Tabelle 4: Untersuchte Kombinationen der Einzelschritte für das Positionsupdate.............................. 21
Tabelle 5: Deskriptive Statistik des Experiments #3 ............................................................................. 23
Tabelle 6: Deskriptive Statistik des Experiments #6 ............................................................................. 23
Tabelle 7: Deskriptive Statistik des Experiments #19 ........................................................................... 24
Tabelle 8: Deskriptive Statistik des Experiments #22 ........................................................................... 25
Tabelle 9: Deskriptive Statistik des Experiments #24 ........................................................................... 25
Tabelle 10: Deskriptive Statistik des Experiments #25 ......................................................................... 26
Tabelle 11: Deskriptive Statistik des Experiments #28 ......................................................................... 27
Abkürzungs- und Variablenverzeichnis VII
Abkürzungs- und Variablenverzeichnis
PSO Particle Swarm Optimization
Fi Fach
Gi Gruppen von Fächern
Ti Dozierende
xi aktuelle Position eines Partikels
yi bzw. ypbest persönlich beste Position eines Partikels
ygbest global beste Position innerhalb des Schwarms
ylbest lokal beste Position innerhalb der Nachbarschaft
f(xi) Fitness an der Position xi
vi aktuelle Geschwindigkeit eines Partikels
ci soziale Einflussfaktoren
ri in [0, 1] gleichverteilte Zufallsvariablen
t Zeit
wij Geschwindigkeitsbeschränkung
Vmax maximale Geschwindigkeit
xmax Lösungsraumbeschränkung
w inertia weight
χ constriction factor
1 Einleitung 1
1 Einleitung
Das Problem der Terminplanung findet sich in vielen Bereichen des alltäglichen Lebens wieder. Ob es
sich dabei um die Zuordnung von Fahrern zu Fahrzeugen im öffentlichen Nahverkehr oder die
Erstellung von Stundenplänen an Schulen oder Universitäten handelt, spielt eine untergeordnete Rolle.
Jeder möchte, sobald er von Entscheidungen in diesem Bereich betroffen ist, seine persönlichen Ziele
möglichst zufriedenstellend umgesetzt wissen. Für die Gesamtheit der Ziele der teilnehmenden
Personen ergeben sich daraus Konflikte, die einerseits dazu führen können, dass eine Lösung des sich
ergebenden Problems nicht zulässig und damit nicht umsetzbar ist oder andererseits die Wünsche der
Personen nur unzureichend berücksichtigt.
In dieser Arbeit wird ein solches Problem dargestellt, mit dem sich die Forschung seit den 1960er
Jahren in verschiedenen Varianten auseinandersetzt: Die optimale Gestaltung eines Stundenplanes an
Universitäten. Bei dem hier betrachteten realen Problem handelt es sich um die Gestaltung eines
Stundenplanes für die Lehrerausbildung der Philosophischen Fakultät der Universität Göttingen. Um für
dieses Problem eine möglichst gute Lösung zu finden, wird ein schwarmintelligentes Verfahren, die
Particle Swarm Optimization, angewendet. Diese Metaheuristik wurde entwickelt, um Lösungen für
kontinuierliche Problemstellungen zu finden und zu optimieren und stellte sich innerhalb dieser
Applikationen als ein sehr geeignetes Verfahren zur Erzielung schneller und guter Lösungen heraus. An
dieser Stelle muss dazu das Verfahren aber an die gegebenen Umstände für diese diskrete
Problemstellung angepasst werden.
Im folgenden Kapitel werden dazu die allgemeinen Grundlagen für das Problem der universitären
Stundenplanung gelegt, um darauf aufbauend das untersuchte Problem vorzustellen und das
Optimierungsmodell zu formulieren. Kapitel 3 stellt die ursprüngliche Metaheuristik Particle Swarm
Optimization für kontinuierliche Problemstellungen und allgemeine Eigenschaften des Verfahrens vor
und beschreibt, in welcher Art der Algorithmus angepasst werden kann, um es für das untersuchte
Zuordnungsproblem anwendbar zu machen. Daraufhin werden in Kapitel 4 die verschiedenen
Experimente dargestellt und die erzielten Ergebnisse miteinander verglichen, um diese Arbeit mit einer
Zusammenfassung und einem Ausblick auf weitere Forschungsfragen in Kapitel 5 abzuschließen.
2 Universitäre Stundenplanung 2
2 Universitäre Stundenplanung
2.1 Einordnung
Bei der Stundenplanung (Timetabling) handelt es sich um ein spezielles Zuordnungsproblem (Krins
1981, S. 26). Es gehört der Klasse von Scheduling-Problemen an, die ihrerseits Problemen der linearen
Entscheidungsmodelle bei Sicherheit, dessen Variablen diskreter Natur sind, untergeordnet sind.
Abbildung 2-1 veranschaulicht die Einordnung von Scheduling-Problemen allgemein in die Klassen der
Entscheidungsmodelle und der (universitären) Stundenplanung im Speziellen (in Anlehnung an
Biethahn et al. 2004, S. 22 und Hilbert-Siekmann 2001, S. 16).
Entscheidungsmodelle
Bei Sicherheit Bei Unsicherheit
Lineare Modelle Nichtlineare Modelle
Kontinuierliche Modelle Diskrete Modelle
Scheduling i.w.S.Zuordnung von Ressourcen zu Objekten in Raum und Zeit
unter der Beachtung von Nebenbedingungen, mit oder ohne Verfolgung von Zielsetzungen
Scheduling i.e.S.
Scheduling mit Zielsetzungder Minimierung der Kosten des Ressourcenverbrauchs
(Beispiel: Transportplanung, job shop scheduling)
Timetabling
Scheduling Problem mit vor-gegebenen Ressourcen und
Verfolgung einer Menge anzu-strebender Ziele
(Beispiel: Stundenplaner-stellung für Schulen,
Universitäten)
Rostering
Scheduling-Probleme, die dieEinordnung von Ressourcen
in ein gegebenes Muster beinhalten
(Beispiel: Schichtplanung für Busfahrer)
Sequencing
Scheduling-Probleme, die dieFestlegung einer Aktivitäts-
oder Objektreihenfolgebeinhalten
(Beispiel: flow shopscheduling, travellingsalesman problem)
…
…
……
Abbildung 2-1: Einordnung der universitären Stundenplanung
2.2 Allgemeine Problembeschreibung
Die Stundenplanung befasst sich mit der Terminplanung von Treffen zu einer bestimmten Zeit an einem
bestimmten Ort mit bestimmten Teilnehmern. Die Lösung des Problems ergibt im besten Fall Pläne, die
es allen Beteiligten ermöglicht, an einem gegebenen Zeitpunkt an einem gegebenen Ort an dem
jeweiligen Treffen teilzunehmen (Heppner/Grenander 1990, S. 13).
2 Universitäre Stundenplanung 3
Sowohl für die Raumzuteilung, die Zeiten der Treffen als auch die Teilnehmer existieren gewisse
Einschränkungen. Räume müssen zu einem bestimmten Termin mit gewünschter Ausstattung in
gewünschter Größe verfügbar sein. Die Teilnehmer des Treffens müssen die Möglichkeit besitzen, sich
zu einem Termin an einem bestimmten Ort einzufinden, und ihnen muss für die Dauer des Treffens die
benötigte Zeit zur Verfügung stehen. Zudem darf keine andere Veranstaltung existieren, bei der zur
gleichen Zeit ihre Anwesenheit erforderlich ist. Eine Doppelbelegung von Räumen birgt gleiches
Konfliktpotential. Somit ist das Erzeugen eines zulässigen Stundenplanes selbst schon ein NP-hartes
Problem (Qualizza/Serafini 2005, S. 167), welches noch keine Berücksichtung von Präferenzen
beinhaltet, wie es im Allgemeinen für Terminwünsche der Fall ist. Abbildung 2-2 veranschaulicht die
Konzepte für Terminplanung im Allgemeinen (in Anlehnung an Heppner/Grenander 1990, S. 3) und für
die universitäre Stundenplanung im Speziellen (in Anlehnung an Heppner/Grenander 1990, S. 15).
Person
Ereignis
Ort Zeit Ort Zeit
Veranstaltung
Passiver Handlungsträger
Aktiver Handlungsträger
Abbildung 2-2: Konzept der Terminplanung im Allgemeinen (links) und speziell für universitäre
Stundenplanung (rechts)
Bei der universitären Stundenplanung bedeutet dies also, dass sowohl Dozierende in der Rolle der
aktiven Handlungsträger als auch Studierende in der Rolle der passiven Handlungsträger sich in einem
Hörsaal, Seminarraum etc. entsprechender Größe und Ausstattung zu einer für alle Beteiligten
akzeptablen Zeit für die Dauer der Veranstaltung einfinden können (Hilbert-Siekmann 2001, S. 14),
ohne dass es dabei zu Verletzungen von Nebenbedingungen kommt. Die Termine eines sich
ergebenden Stundenplans entsprechen dabei Belegungen einer zuvor definierten Matrix von möglichen
Zeitfenstern.
Die genannten Bedingungen (engl.: Constraint) lassen sich in Hard und Soft Constraints unterscheiden
(Eiselt/Laporte 1987, Burke et al. 1997, S. 566). Bei Verletzung von Hard Constraints gilt ein
Stundenplan im Allgemeinen als nicht zulässig, weil z.B. bei einer Veranstaltung der Dozierende wegen
der Terminwahrnehmung einer anderen Veranstaltung nicht zur Verfügung steht (Qualizza/Serafini
2005, S. 163). Die Verletzung von Soft Constraints beeinflusst die Zulässigkeit des Stundenplans nicht.
Das Bestrafen der Nichteinhaltung von Soft Constraints wird aber in die Bewertung des Stundenplans
aufgenommen. Soft Constraints treten z.B. dann auf, wenn Terminwünsche für Veranstaltungen nicht
2 Universitäre Stundenplanung 4
eingehalten werden können, weil durch deren Verschiebung von ihren ursprünglichen Wunschterminen
in ein anderes Zeitfenster die Zulässigkeit eines Stundenplanes erreicht werden kann.
Die Besonderheit im Vergleich zu der Stundenplanung an Schulen ergibt sich für die universitäre
Stundenplanung aus den Wahlmöglichkeiten, die die Studierenden im Gegensatz zu Schülern besitzen
(Qualizza/Serafini 2005, S. 162). Sie müssen sich nicht an vorgegebene Fächerkombinationen halten,
sondern können ihr Studienprogramm weitestgehend eigenständig planen. Der Besuch einzelner
Veranstaltungen muss nicht in einem speziellen Semester statt finden, sondern kann meist wahlfrei in
die Studienzeit integriert werden. Ziel der universitären Stundenplanung ist es, aus der sich ergebenden
Vielzahl von Fächerkombinationen einen für alle Personen möglichst überschneidungsfreien
Stundenplan zu erzeugen. Obwohl sich die Probleme der Schulstundenplanung und der universitären
Stundenplanung auf den ersten Blick sehr ähneln, gibt es wesentliche Unterschiede in der
Problemstellung, die in Tabelle 1 (Carter/Laporte 1998, S. 5) zusammengefasst sind.
Tabelle 1: Unterschiede der Stundenplanung an Schulen und Universitäten
Eigenschaft Schule Universität
Zuordnung - der Klassen - der Studierenden
Wahlmöglichkeiten - wenige Wahlmöglichkeiten
- hoch strukturiertes Programm
- viele Wahlmöglichkeiten
- wenig strukturiertes Programm
Verfügbarkeit der Lehrenden - hohe Auslastung der Lehrenden - geringe Auslastung der Lehren-
den
Räume - wenige Räume
- identische Größen
- an zentraler Stelle
- viele Räume
- unterschiedlichste Größen
- dezentralisiert
Arbeitsbelastung der Lernenden
- sehr hoch - eher gering
- tagsüber und abends
Zielkriterium - keine Konflikte - minimale Konflikte
Weitere generelle Charakteristika des Stundenplanproblems sind u.a. in (de Werra 1985) und (de
Werra 1997) beschrieben.
2.3 Problem der Philosophischen Fakultät der Universität Göttingen
Die dem untersuchten Stundenplanproblem zugrunde liegenden Daten entstammen einer realen
Problemstellung des Wintersemesters 2006/2007 für Lehramtsstudierende im ersten Semester der
Philosophischen Fakultät der Universität Göttingen. Diese zeigt sich verantwortlich für die
Lehrerausbildung an der Universität Göttingen. Betrachtet wurden nach der Einführung der Bachelor- /
Master-Studiengänge ausschließlich die für die in Niedersachsen in Frage kommenden Kombinationen
von zwei Fächern, die es den Studierenden ermöglichen, in diesem Bundesland nach erfolgreichem
2 Universitäre Stundenplanung 5
Abschluss des aufbauenden Masterstudiums den Beruf eines Lehrers / einer Lehrerin zu ergreifen. Die
angehenden LehrerInnen besitzen die Möglichkeit, aus allen vorhandenen Fächern zwei auszuwählen,
wobei Personen, die eine der 96 in Abbildung 2-3 grau dargestellten Kombinationen belegen, bevorzugt
in Niedersachsen als LehrerInnen eingestellt werden. Studierende müssen also (Pflicht-)Veranstaltun-
gen beider Fachrichtungen besuchen. So ergeben sich bspw. für Studierende der Fächerkombination
Biologie / Chemie sieben Veranstaltungen für Biologie und vier für Chemie pro Woche.
Biologie
Chem
ie
Deustch
Englisch
Erdkunden
Religion
Französisch
Geschichte
Griechisch
Informatik
Latein
Mathem
atik
Philosophie
Physik
Politik
Russisch
Spansich
Sport
Werte und
Norm
en
Biologie
Chemie
Deustch
Englisch
Erdkunde
Religion
Französisch
Geschichte
Griechisch
Informatik
Latein
Methematik
Philosophie
Physik
Politik
Russisch
Spanisch
Sport
Werte und Normen
Abbildung 2-3: Vorgeschlagene Fächerkombinationen der LehrerInnenausbildung für Niedersachsen
(graue Felder)
Um die Komplexität der Problemstellung von vorn herein etwas zu entschärfen, wurden nur
Pflichtveranstaltungen der Erstsemesterstudierenden berücksichtigt, da angenommen werden kann,
dass es wegen des reichhaltigen Angebots an Wahlveranstaltungen für die Studierenden immer die
Möglichkeit besteht, auf eine andere Veranstaltung auszuweichen, sollte es eine Überschneidung mit
einer Pflichtveranstaltung geben. Das Fach Deutsch bietet aufgrund der hohen Studierendenzahlen von
vorn herein sehr viele Alternativveranstaltungen an, so dass dieses keine Berücksichtigung bei der
Gestaltung eines Stundenplanes finden muss.
Die verbleibenden 18 Fächer bieten insgesamt 71 Pflichtveranstaltungen an, die bisher manuell in
einem Stundenplan vereint werden, der sich aus den Terminwünschen der Dozierenden ergibt und in
Abbildung 2-4 mit den grau markierten Konflikten für Studierende dargestellt ist. Wird ein Fach
2 Universitäre Stundenplanung 6
mehrfach in einem Zeitfenster aufgeführt, bedeutet dies, dass es sich um Wahlmöglichkeiten innerhalb
des Faches handelt, die sich untereinander nicht beeinflussen und dementsprechend keinen Konflikt
innerhalb des Faches darstellen. Montag Dienstag Mittwoch Donnerstag Freitag
08-10 Physik Chemie Physik Sport Spanisch Chemie Physik Religion Biologie Sport Sport Religion
10-12 Mathematik Erdkunde Chemie Sport Biologie Englisch Biologie Englisch Sport Mathematik Religion Englisch Erdkunde Mathematik Mathematik Chemie Mathematik Mathematik Englisch Biologie Englisch Russisch Erdkunde Erdkunde Biologie Werte und Normen Religion
12-14 Erdkunde Politik Französisch Russisch Englisch Geschichte Sport
14-16 Griechisch Biologie Spanisch Sport Biologie Latein Spanisch Spanisch Englisch Latein Religion Französisch Religion Russisch
16-18 Griechisch Latein Englisch Religion Philosophie Französisch Englisch Russisch
18-20 Griechisch Spanisch Spanisch
Abbildung 2-4: Manuell erstellter Stundenplan auf Basis der Terminwünsche der Dozierenden
Eine Zusammenfassung des Stundenplan in Abbildung 2-5 veranschaulicht, wie viele Veranstaltungen
pro Zeitfenster an einem Tag angeboten werden. Allein aus dieser Darstellung lässt sich schon
Optimierungspotenzial ableiten, da offensichtlich allein am Freitag vier Zeitfenster existieren, in denen
keine Veranstaltungen angeboten werden.
2 Universitäre Stundenplanung 7
Montag Dienstag Mittwoch Donnerstag Freitag
08-10 1 1 1 3 6
10-12 5 4 4 11 3
12-14 1 1 1 4 0
14-16 4 4 1 5 0
16-18 2 3 1 2 0
18-20 1 0 2 0 0
Abbildung 2-5: Verteilung der Pflichtveranstaltungen auf die vorhandenen Zeitfenster
Gerade die Fächer Englisch, Französisch, Latein, Mathematik und Spanisch erschweren die Erstellung
eines zulässigen Stundenplanes wesentlich, da sie untereinander und mit allen anderen Fächern
kombiniert werden können. Um einen überschneidungsfreien Stundenplan zu ermöglichen, müssten
also allein diese Fächer in jeweils ein eigenes Zeitfenster gesetzt werden, um miteinander studierbar zu
sein. Die Gesamtheit der zugehörigen Veranstaltungen beansprucht allerdings schon 26 der zur
Verfügung stehenden 30 Zeitfenstern. Die übrigen 14 Fächer müssten also in den verbleibenden 4
Zeitfenstern überschneidungsfrei platziert werden, was wiederum wegen Kombinationsmöglichkeiten
innerhalb dieser Fächer selbst nicht realistisch erscheint und tatsächlich unmöglich ist, da allein schon
für Biologie 7 Veranstaltungen zu besuchen sind.
2.3.1 Annahmen
Die Annahmen, die für das verwendete Stundenplanmodell getroffen werden, lassen sich in fünf
Klassen unterteilen (Schimmelpfeng/Helber 2007, S. 786), die im Folgenden erläutert werden.
Zeit
• Die Zeit ist in diskrete, gleichgroße Zeitfenster unterteilt, die sich aus der Anzahl der
betrachteten Tage einer Woche von Montag bis Freitag und aus den innerhalb eines Tages
betrachteten Zeitperioden mit einer Länge von zwei Stunden von 8 bis 20 Uhr ergeben.
• Übergangszeiten werden insofern berücksichtigt, als dass eine Veranstaltung i.d.R. 90 Minuten
dauert, dafür aber zwei Stunden veranschlagt werden.
Räume
• Raumrestriktionen werden in diesem Modell nicht berücksichtigt.
Veranstaltungen
• Jeder Veranstaltung wird genau ein Dozierender zugewiesen.
• Jeder Veranstaltung wird mindestens eine Studierendengruppe zugewiesen.
• Jede Veranstaltung beansprucht 90 bzw. 120 Minuten. Dies entspricht einem Zeitfenster.
2 Universitäre Stundenplanung 8
• Es existieren keine Blockveranstaltungen.
Studierende
• Studierende besitzen keine Präferenzen bzgl. der Zeit, zu der eine Veranstaltung stattfindet.
• Studierende mit verschiedenen Fächerkombinationen können zu Studierendengruppen
zusammengefasst werden.
• Studierende bzw. Studierendengruppen können nicht an mehreren Veranstaltungen zur
gleichen Zeit teilnehmen.
Dozierende
• Dozierende besitzen Präferenzen bzgl. der Zeit, zu der sie eine Veranstaltung abhalten. Ein
Nichteinhalten dieser Bedingung wird als Soft Constraint und als Hard Constraint abgebildet, je
nachdem, ob der Dozierende evtl. nur zu diesen von ihm genannten Terminen zur Verfügung
stehen kann.
• Dozierende können nicht mehr als eine Veranstaltung zur gleichen Zeit anbieten.
Das Problem der Philosophischen Fakultät umfasst also nur wenige Nebenbedingungen, die bei der
Optimierung des Stundenplans berücksichtigt werden müssen. Die enthaltenen Constraints gliedern
sich in folgende Hard und Soft Constraints:
• hardDozentConstraint: Ein Dozierender muss mehrere Veranstaltungen zur gleichen Zeit
halten.
• hardTeilnehmerConstraint: Ein Studierender muss an mehreren Veranstaltungen zur gleichen
Zeit teilnehmen.
• hardTerminConstraint: Von einem Dozierenden wurde der Termin als Pflichttermin angegeben,
da er nur zu dieser speziellen Zeit die Veranstaltung halten kann.
• softTerminConstraint: Der Termin einer Veranstaltung wird verschoben und entspricht nicht
mehr dem vom Dozierenden angegebenen Wunschtermin.
Jede dieser Nebenbedingungen wird bei der Bewertung des erzeugten Stundenplanes unterschiedlich
hart bestraft. Je wichtiger die Nebenbedingung für einen funktionierenden Stundenplan ist, desto härter
wird das Verletzen dieser mit Punkten bewertet. Tabelle 2 fasst die sog. Penalties zusammen:
2 Universitäre Stundenplanung 9
Tabelle 2: Bestrafung bei Verletzung der Nebenbedingungen.
Restriktion Penalty
hardDozentConstraint 15
hardTeilnehmerConstraint 7
hardTerminConstraint 5
softTerminConstraint 1
2.3.2 Formulierung des mathematischen Modells
Nachdem die Annahmen über das Modell festgelegt wurden, können diese nun in ein mathematisches
Modell überführt werden. Dazu werden zunächst die Nebenbedingungen formuliert, um darauf
aufbauend die Zielfunktion herzuleiten.
Aufgrund der verschiedenen Anforderungen an Stundenpläne ergeben sich unterschiedliche
mathematische Modelle für die Formulierung spezieller Stundenplanprobleme. Definitionen des
allgemeinen Problems der Stundenplanerstellung konkretisieren die Aufgabestellung unzureichend und
dienen aus diesem Grund als Hilfestellung bei der Formulierung spezieller Problemstellungen (Hilbert-
Siekmann 2001, S. 16). An dieser Stelle wird ein Modell vorgestellt, das den Anforderungen für das
untersuchte Problem der Philosophischen Fakultät Göttingen genügt. Aus den in (Hilbert-Siekmann
2001, S. 35), (Cheng et al. 1996, S. 144) und (Schaerf 1999, S. 101) erläuterten Modellen wird das hier
verwendete Modell entwickelt und an dieser Stelle vorgestellt.
Es existieren q Fächer F1, …, Fq. Jedes Fach Fi besteht aus fi Veranstaltungen. Weiterhin gibt es r
Gruppen von Fächern G1, …, Gr, die von gleichen Studierenden besucht werden. Das bedeutet, dass
Fächer bzw. Veranstaltungen in Gl unterschiedlichen Zeitfenstern zugeordnet werden müssen. Darüber
hinaus existieren t Dozierende aus der Gruppe T1, …, Tt. Die Anzahl der zur Verfügung stehenden
Zeitfenster k beträgt p. Daraus ergibt sich:
ijkyfind ( )pkqi KKK 1 t;1j ;1 === (1)
ij
p
kijk fy =∑
=1
( )tjqi KK 1;1 == (2)
1≤∑∈ lGi
ijky ( )pkrl KKK 1 t;1j ;1 === (3)
1≤∑∈ nTj
ijky ( )pkqtn KKK 1 ;1i ;1 === (4)
1 0 oryijk = ( )pkqi KKK 1 t;1j ;1 === (5)
2 Universitäre Stundenplanung 10
Durch Formel (2) wird erreicht, dass alle Veranstaltungen eines Faches zugeordnet werden. Formel (3)
sorgt dafür, dass Veranstaltungen auf unterschiedliche Termine gesetzt werden, die von gleichen
Studierenden besucht werden sollen. Formel (4) sorgt dafür, dass ein Dozierender nur für eine
Veranstaltung an einem bestimmten Termin eingesetzt werden kann. Mit der gegebenen Zielfunktion
(1) handelt es sich bei dieser Darstellung lediglich um ein Suchproblem, das einen zulässigen
Stundenplan erzeugt (Schaerf 1999, S. 93) Dieses Modell wird zu einem Optimierungsproblem
erweitert, indem die Berücksichtigung verletzter Constraints in die Zielfunktion aufgenommen wird (vgl.
Yoshikawa et al. 1996), wobei dijk die Penalties aus Tabelle 2 berücksichtigt.
∑∑∑= = =
q
i
t
j
p
kijkijk yd
1 1 1min
(6)
2.4 Lösungsverfahren
Da sich schon seit vielen Jahren Forscher mit unterschiedlichsten Formen des Problems der
Stundenplanung beschäftigen, sind während dieser Zeit neben der Vielzahl von Publikationen
(Carter/Laporte 1998, S. 3) auch diverse Lösungsverfahren entwickelt bzw. angewendet worden. Diese
sollen an dieser Stelle nicht alle beschrieben werden. Detaillierte Überblicke über die Anwendung
verschiedener Algorithmen auf unterschiedliche Problemstellungen im Bereich des Scheduling geben
u.a. (Carter/Laporte 1998), (Schaerf 1999), (Chiarandini/Stützle 2002), (Colorni/Dorigo/Maniezzo 1998)
und (Rossi-Doria et al. 2003). Da sich die Arbeit mit der Anpassung einer Metaheuristik auf die
Stundenplanung beschäftigt, wird in
2 Universitäre Stundenplanung 11
Tabelle 3 ein Einblick gegeben, welche anderen der bekanntesten Heuristiken bisher verwendet
wurden. Ein Anspruch an Vollständigkeit kann an dieser Stelle aber nicht erhoben werden, da sich die
Forschung schon seit vielen Jahren mit der Problematik und möglichen Lösungsverfahren beschäftigt
und aus diesem Grund eine unüberschaubare Vielfalt von Publikationen existiert.
2 Universitäre Stundenplanung 12
Tabelle 3: Einsatz von Metaheuristiken für die Stundenplanerstellung
Metaheuristik Problemtyp in Examination timetabling Thompson/Dowsland 1996a
Thompson/Dowsland 1996b School Timetabling Abramson 1991 University Timetabling Bai/Burke/Kendall 2006
Simulated Annealing
Timetabling allgemein Ross/Corne 1995 Examination timetabling Boufflet/Nègre 1996
Gaspero/Schaerf 2001 School Timetabling Schaerf 1996 University Timetabling Arntzen/Løkketangen 2003
Costa 1994
Tabu Search
Timetabling allgemein Hertz 1992 Burke/Kendall/Soubeiga 2003
Examination timetabling Ross/Hart/Corne 1998 School Timetabling Caldeira/Rosa 1998 University Timetabling Corne/Ross/Fang 1994
Paechter et al. 1998 Junginger 1995
Evolutionärer / Genetischer Algorithmus
Timetabling allgemein Paechter et al. 1994 Burke/Elliman 1995
Examination timetabling Dowsland/Thompson 2005 School Timetabling Colorni/Dorigo/Maniezzo 1998
Ameisenalgorithmus
University Timetabling Socha/Sampels/Manfrin 2003 Examination timetabling Chu/Chen/Ho 2006 Particle Swarm Optimization University Timetabling An dieser Stelle
3 Particle Swarm Optimization 13
3 Particle Swarm Optimization
Die Particle Swarm Optimization wurde ursprünglich von Kennedy und Eberhard (Kennedy/Eberhart
1995) zur Lösung kontinuierlicher Problemstellungen entwickelt. In diesem Kapitel wird dargestellt, wie
sich die Idee der Simulation von Vogelschwärmen hin zu einer Metaheuristik entwickelt hat und das
Verfahren mit einigen grundlegenden Erweiterungen vorgestellt. Darauf aufbauend wird die Modifikation
vorgestellt, mit der die PSO auch für kombinatorische Problemstellungen angewendet werden kann.
3.1 Idee und Ursprung
3.1.1 Boids
Um Schwarmverhalten für Computergrafiken und Filme zu simulieren und weil er die Choreographie
von Vogelschwärmen ästhetisch fand (Kennedy/Eberhart 1995), entwickelte Reynolds das Boids-
Modell, in dem jeder Boid ein einzelnes Individuum darstellt (Reynolds 1987), das drei implementierten
Regeln gehorcht. Die Ausrichtung sorgt dafür, dass sich einzelne Individuen in der gleichen Richtung
wie ihre Nachbarn bewegen. Ein Zusammenführen mehrerer Boids ermöglicht die Kohäsion, bei der
sich ein einzelner Boid in die Mitte einer definierten Gruppe bewegt, wohingegen die Trennung für ein
Auseinanderstreben von Boids sorgt, deren Abstand zueinander zu klein ist. Die Funktionsweisen
dieser Regeln sind in Abbildung 3-1 graphisch veranschaulicht. Der markierte Boid richtet sich je nach
Regel an den anderen Boids aus, wobei die Spitzen der Dreiecke die aktuelle Richtung anzeigen und
der Pfeil die Richtungsänderung angibt. Die grau hinterlegten Kreise definieren die Zugehörigkeit zu
einer Gruppe.
Ausrichtung Kohäsion Trennung
Abbildung 3-1: Regeln des Boids-Modells (modifiziert aus Reynolds 2001)
3 Particle Swarm Optimization 14
3.1.2 Vogelschwärme
Für die den Bewegungen solcher Schwärme zugrunde liegenden Regeln interessierten sich Heppner
und Grenander, die dem Boids-Modells Rastplätze hinzufügten, auf denen die Vögel landen können.
Neben dem Verlangen der Individuen, auf solchen Rastplätzen zu landen, wird jedes Individuum des
Schwarms mit einer weiteren wesentlichen Eigenschaft ausgestattet, die diesem Ziel entgegenwirkt.
Die Individuen besitzen ebenso das Bedürfnis, innerhalb des Schwarmes zu verbleiben. Je weiter sich
ein Vogel einem Rastplatz nähert, desto größer wird der Wunsch, sich auf diesen zuzubewegen, was
zur Folge hat, dass dieser weitere Vögel mit in diese Richtung zieht (Heppner/Grenander 1990), da der
Verbund des Schwarms erhalten werden soll.
3.2 Metaheuristik für kontinuierliche Problemstellungen
Auf Grundlage der Arbeiten von Reynolds, Heppner und Grenander entwickelten Kennedy und
Eberhart die Partikel Swarm Optimization. Dabei war „fundamental to the development of particle
swarm optimization“ (Kennedy/Eberhart 1995) die Aussage von Wilson: “In theory at least, individual
members of the school can profit from the discoveries and previous experience of all other members of
the school during the search for food. This advantage can become decisive, outweighing the
disadvantages of competition for food items, whenever the resource is unpredictably distributed in
patches”. (Wilson 1975, S. 209). Dieser Hypothese, dass Informationsaustausch zwischen
Gruppenmitgliedern einen evolutionären Vorteil bietet, folgten Kennedy und Eberhart bei dem weiteren
Entwicklungsverlauf der PSO, indem sie den Vögeln soziales Verhalten implementierten und fortan zu
masse- und kollisionsfreien Partikeln machten (Kennedy/Eberhart 1995) Zudem erweiterten sie das
Modell, indem sie nicht nur einen Rastplatz suchen ließen, sondern stattdessen einen „cornfield vector“
(Kennedy/Eberhart 1995) einsetzten, auf dem ein bester Futterplatz existiert. Außerdem besitzen diese
Partikel nun ein Gedächtnis über ihre bisher beste Position in Bezug auf einen solchen Futterplatz und
ein Wissen über die innerhalb des gesamten Schwarms bisher beste Position in Bezug auf ebendiesen.
Aus diesen Überlegungen wurde die klassische PSO bzw. canonical PSO für kontinuierliche
Problemstellungen entwickelt, deren Verfahren im Folgenden dargestellt wird.
3.2.1 Canonical PSO
Ausgehend von zufällig generierten Positionen xi, d.h. einer möglichen Lösungsrepräsentationen einer
Startpopulation berechnet das Verfahren auf Grundlage des Optimierungsproblems mit der Funktion
f(xi) Fitnesswerte für alle Partikel, die jeweils durch ihre aktuelle Position xi, ihre Geschwindigkeit vi
sowie durch die bisher persönlich beste Position yi definiert sind (Van den Bergh 2002, S. 21). Nach
dieser Initialisierung beginnt der iterative Optimierungsprozess, in dem sowohl Aktualisierungen der
persönlich und global besten Positionen ygbest und Fitnesswerte als auch Berechnungen der neuen
Geschwindigkeit und der neuen Position durchgeführt werden. Im Allgemeinen bricht dieser Prozess
3 Particle Swarm Optimization 15
ab, sobald ein bestimmter, vorher definierter Fitnesswert erreicht ist oder wenn der Algorithmus eine
vorgegebene Anzahl an Iterationen absolviert hat (Shi 2004, S. 8). Dieser Ablauf wird an folgendem
Pseudocode vereinfacht dargestellt (Kennedy/Eberhart/Shi 2001, S. 313):
criterion Until Next
then If then If
s sindividual of number to For Loop
Swarm the Initialize
itvtxtx
txytrctxytrctvtv
yyf(yf(yxyf(yf(x
i
iii
igbestiiii
igbestgbesti
iiii
)()1()(
))1()(())1()(()1()(
))))
1
2211
+−=
−−+−−+−=
=<=<
=
Abbildung 3-2: Pseudocode für PSO
Die detaillierten Berechnungen werden im Folgenden näher beschrieben. Sei f die Funktion eines
Minimierungsproblems mit einer zugehörigen Fitnessfunktion, ergibt sich für jeden Partikel die
persönlich beste Position aus
( ) ( ) ( )( ) ( )( )( ) ( )( ) ( )( )⎩
⎨⎧
<++≥+
=+tyftxftxtyftxfty
tyiii
iiii 1 : 1
1 : 1
(7)
Bei einer Größe des gesamten Schwarms s ist eine global beste Position definiert als
( ) ( ) ( ) ( )( ) ( )( ) ( )( ){ }{ }tyftyftyftytyty sgbestsgbest ,...,min | ,...,in 00 = (8)
Die Geschwindigkeit eines Partikels zur Zeit t+1 ergibt sich aus den Einflüssen von der persönlich
besten und der bisherigen global besten Position:
( ) ( ) ( ) ( ) ( )[ ] ( ) ( ) ( )[ ]txtytrctxtytrctvtv jigbestjijijiji ,22,,11,, 1 −+−+=+ (9)
mit den sozialen Einflussfaktoren 2,0 21 ≤≤ cc , zwei gleich verteilten Zufallsvariablen ( )1,0~1 Ur ,
( )1,0~2 Ur und der Geschwindigkeitsbeschränkung ijw in [ ]maxmax , V-V . Die Faktoren c1 und c2
steuern, wie viel Einfluss die bisher im ganzen Schwarm beste Position und die persönlich beste
Position auf die Berechnung der neuen Geschwindigkeit besitzen. Bei c2 > c1 tendiert der gesamte
3 Particle Swarm Optimization 16
Schwarm dazu, sich dem bisher besten Partikel zu nähern, was zu einem schnellen Zusammenziehen
der Partikel in einer bestimmten Region und einer erhöhten Exploitation führt. Eine größere Exploration
des Lösungsraumes hingegen wird durch c1 > c2 erreicht, wodurch eine schnelle Konvergenz verhindert
wird. Bei der klassischen Variante der PSO werden diese beiden Parameter auf jeweils 2 gesetzt
(Kennedy/Eberhart 1995 und Van den Bergh/Engelbrecht 2005).
Hieraus ergibt sich dann mit der Beschränkung des Lösungsraumes durch [ ]maxmax , xx− die neue
Position eines Partikels:
( ) ( ) ( )11 ++=+ tvtxtx iii (10)
3.2.2 Restriktionsbehandlung
Da die Partikel selbst keine Vorstellung von der Größe des Lösungsraumes besitzen, muss der Fall
behandelt werden, in dem eine neu berechnete Position eines Partikels die Dimensionsgrenzen des
Optimierungsproblems verletzt.
Stick
Die Methode stick sorgt dafür, dass bei Überschreiten der Dimensionsgrenze die neue Position des
Partikels genau auf der Dimensionsgrenze liegt:
( ) ( )sonst
x1)(tx
wenn maxi ≤+
⎩⎨⎧ +
=+max
11
xtx
tx ii
(11)
Bounce
Der Partikel prallt um die Differenz zwischen Dimensionsgrenze und neu berechneter Position in den
gültigen Bereich zurück:
( ) ( )( )( ) sonst
x1)(tx
wenn maxi ≤+
⎩⎨⎧
−+−+
=+maxmax 1
11
xtxxtx
txi
ii
(12)
Wrap
Wrap stellt den Lösungsraum als einen Ring dar. Überschreitet ein Partikel die Dimensionsgrenze an
der oberen Schranke, liegt seine neue Position um die Differenz der Überschreitung an der unteren
Dimensionsgrenze:
( ) ( )( )( ) sonst
x1)(tx
wenn maxi ≤+
⎩⎨⎧
−+++
=+maxmin 1
11
xtxxtx
txi
ii
(13)
3 Particle Swarm Optimization 17
Die Funktionsweisen der Restriktionsbehandlungen stick, bounce und wrap sind graphisch in Abbildung
3-3 dargestellt (Paquet/Engelbrecht 2003).
Abbildung 3-3: Restriktionsbehandlung
3.2.3 Nachbarschaftsbeziehungen
Das bisher dargestellte Verfahren verbindet die Schwarmmitglieder derart, dass jedem Partikel zur Zeit
t+1 der global beste Partikel bekannt ist. Diese Art der Nachbarschaft wird als gBest-Topologie
bezeichnet. Aus (3) geht hervor, dass alle Partikel von diesem einen angezogen werden und dies zu
einer relativ schnellen Konvergenz in einem Punkt führen kann, der evtl. nur ein lokales Optimum
darstellt (Mendes/Kennedy/Neves 2003b).
Durch eine lokale Verbindung der Partikel mittels einer lBest-Topologie, bei der ein Partikel nur mit
vorher definierten Nachbarn bekannt ist (Kennedy 2005), soll diese vorzeitige Konvergenz verhindert
werden.
Bei der circle-Topologie mit Größe drei werden jedem Partikel zu Beginn des Verfahrens zufällig zwei
Nachbarn zugeordnet, die untereinander Informationen austauschen. Da diese beiden Nachbarn noch
weitere Verbindungen zu weiteren Partikeln besitzen, wird sukzessive durch mehrere Iterationen
hindurch die global beste Position eines Partikels an alle anderen weitergegeben. Währenddessen
kann sich diese Position natürlich ändern.
Ein Hub existiert bei der wheel-Topologie, welcher mit allen anderen Partikeln verbunden ist, diese aber
nicht untereinander. Hierbei benötigt das Verbreiten der global besten Position genau zwei Iterationen,
bis diese allen Partikeln bekannt ist: Vom Partikel mit dieser Position über den Hub zu allen anderen
Partikeln.
Die star-Topologie verbindet eine vorgegebene Anzahl von Partikeln. Diese Cluster besitzen
Verbindungen zu anderen Clustern, so dass im Falle eines Vierer-Clusters die Verbreitung der global
besten Position drei Iterationen benötigt.
Pyramidenähnlich ist die pyramide-Topologie aufgebaut. Ein Gitter wird zwischen den Partikeln auf
mehreren Ebenen in der Art aufgebaut, dass ein Partikel innerhalb des Gitters einer Ebene zu vier
weiteren, am Rand eines Gitters zu dreien und in einer Ecke des Gitters zu zwei Partikeln
Verbindungen auf einer Ebene besitzt. Darüber hinaus bestehen noch in über- und untergeordneten
3 Particle Swarm Optimization 18
Ebenen Verbindungen, so dass die Verbreitung der global besten Position 2*Höhe der Pyramide – 1
beträgt.
Abbildung 3-4: Nachbarschaftstopologien gBest (global), circle (Größe = 3), wheel, 4 clusters (star),
pyramide (Mendes/Kennedy/Neves 2003a, Kennedy/Eberhart/Shi 2001)
Um die in Abbildung 3-4 dargestellten verschiedenen Nachbarschaftstopologien in den Algorithmus
einzubinden, wird ygbest durch ylbest ersetzt und (3) muss entsprechend angepasst werden:
( ) ( ) ( ) ( ) ( )[ ] ( ) ( ) ( )[ ]txtytrctxtytrctvtv jilbestjijijiji ,22,,11,, 1 −+−+=+ (14)
3.2.4 Geschwindigkeitsupdate
Inertia Weight
Um der Explosion der Geschwindigkeit (Kennedy/Eberhart/Shi 2001) entgegenzuwirken, wird zusätzlich
zu den erwähnten Geschwindigkeitsbeschränkungen das inertia weight w eingesetzt, welches einem
Gewichtungsfaktor für die Geschwindigkeit der Vorperiode entspricht. (5) wird dementsprechend
modifiziert (Shi/Eberhart 1998):
( ) ( ) ( ) ( ) ( )[ ] ( ) ( ) ( )[ ]txtytrctxtytrctwvtv jilbestjijijiji ,22,,11,, 1 −+−+=+ (15)
Dies führt bei einem großen inertia weight zu guter Exploration, erschwert dagegen wegen der hohen
Geschwindigkeit und somit großen Positionswechsel der Partikel die Exploitation. Mit einem zu
geringen inertia weight dagegen tendiert der Schwarm zu einer lokalen Suche, obwohl die Region des
globalen Optimums noch nicht gefunden wurde (Shi/Eberhart 1998, Shi/Eberhart 1999). Ein inertia
weight um 0.8 hat sich dabei als eine gute Einstellung erwiesen (Shi/Eberhart 1998). Wird ein inertia
weight von 1 gewählt, entspricht dies dem in Kapitel 3.2.1 dargestellten Canonical PSO.
Constriction Factor
Während das inertia weight sich nur auf die Beschränkung des Einflusses der alten Geschwindigkeit
auswirkt, beeinflusst der constriction factor zudem den Einfluss der sozialen und persönlichen
Komponente innerhalb beim Bestimmen der neuen Geschwindigkeit. Zu kleine Werte für den
constriction factor führen dementsprechend dazu, dass der Lösungsraum evtl. nicht vollständig
erkundet werden kann, wohingegen zu große Werte einer Konvergenz des Schwarms entgegen wirken,
allerdings eine erhöhte Exploration aufweisen.
3 Particle Swarm Optimization 19
Die veränderte Berechnung der neuen Geschwindigkeit ergibt sich aus (Zhang/Yu/Hu 2005,
Kennedy/Eberhart/Shi 2001):
( ) ( ) ( ) ( ) ( )[ ] ( ) ( ) ( )[ ]( )txtytrctxtytrctvtv jilbestjijijiji ,22,,11,, 1 −+−+=+ χ (16)
Für den constriction factor hat sich ein Wert von 0,73 bewährt, der sich nach der folgenden Formel aus
ϕ = 4,1 und k = 1 ergibt. Dabei ist diese Formel nur für ϕ > 4 anzuwenden (Clerc/Kennedy 2002).
ϕϕϕχ
42
22 −+−
=k (17)
3.3 Metaheuristik für kombinatorische Problemstellungen
Da die PSO ursprünglich für kontinuierliche Problemstellungen entwickelt wurde (Kennedy/Eberhart
1995), kann sie in der zuvor dargestellten Form nicht uneingeschränkt für kombinatorische
Problemstellungen verwendet werden. Dieser Abschnitt stellt die Modifikationen vor, welche die PSO
für solche Arten von Problemstellungen anwendbar macht, basierend auf der Darstellung einer PSO für
Prüfungsorganisation (examination timetabling) (Chu/Chen/Ho 2006).
Die Charakteristika des Verfahrens werden dabei nicht verändert und der Ablauf für kombinatorische
Problemstellungen ist an den Ablauf des Canonical PSO angelehnt. Die nachfolgende Beschreibung
orientiert sich dabei an der Anpassung des PSO für die Suche nach optimalen Lösungen eines
universitären Stundenplanproblems.
Jeder Partikel besitzt eine aktuelle Position xi(t), eine persönlich beste Position ypbest(t) und als
Nachbarschaftstopologie wird global (siehe Kapitel 3.2.3) verwendet, d.h. allen Partikeln ist die global
beste Position ygbest(t-1) aus der vorherigen Iteration bekannt. Die persönlich besten und global besten
Lösungen ergeben sich wie in Formel (7) und (8) angegeben. Das Geschwindigkeitsupdate kann aber
nicht mehr entsprechend Formel (9) ausgeführt werden, sondern muss den Besonderheiten einer
kombinatorischen Problemstellung angepasst werden.
Ausgehend von einer vorgegebenen oder zufälligen Ausgangslösung ergibt sich die neue Position
x(t+1) durch das Ausführen mehrerer Einzelschritte auf Grundlage der aktuellen Position:
3 Particle Swarm Optimization 20
• Zufälliges Vertauschen eines Zeitfensters mit den zugehörigen Veranstaltungen aus der
aktuellen Position.
• Zufälliges Verschieben einer einzelnen Veranstaltung aus der persönlich besten Position.
• Vertauschen eines Zeitfensters mit den zugehörigen Veranstaltungen aus der global besten
Position.
• Zufälliges Verschieben einer einzelnen Veranstaltung aus der global besten Position.
Wie sich in Kapitel 4 noch zeigen wird, können die verschiedenen Schritte auch in unterschiedlicher Art
und Weise miteinander kombiniert werden.
Der Abbruch des Verfahrens erfolgt, sobald ein zuvor definiertes Abbruchkriterium erfüllt wurde,
welches z.B. eine gewisse Anzahl an Iterationen oder eine definierte Lösungsschranke darstellen kann.
Der sich hieraus ergebende Ablauf der PSO ist in Abbildung 3-5 dargestellt.
( )( ) ( )( )txftyf ipbest <
( ) ( )txty ipbest =+1( ) ( )tyty pbestpbest =+1
( )( ) ( )( )txftyf igbest <
( ) ( )txty igbest =+1( ) ( )tyty gbestgbest =+1
Evaluierung
Initialisierung
Erzeuge neue Positiondurch Kombination der Einzelschritte
Evaluierung
Abbruchkriterium erfüllt
janein
janein
Ende
ja
nein
Abbildung 3-5: Ablauf der PSO für die Lösung der kombinatorischen Problemstellung eines
Stundenplanproblems
4 Experimente 21
4 Experimente
4.1 Versuchsaufbau
Zum Bestimmen eines guten Schätzers der erzielten Fitnesswerte werden 31 Replikationen
durchgeführt für jede Kombination der vier in Kapitel 3.3 vorgestellten Schritte für die Bestimmung der
neuen Position der Partikel. Dies ist nach dem zentralen Grenzwertsatz eine ausreichend große
Stichprobe (vgl. Ahlborn/Kricke 1997, S. 183-186). Der daraus entstehende Mittelwert dient im weiteren
Verlauf als Maß der Güte für die Bewertung der verschiedenen Kombinationen. Außerdem wurde in die
Experimente aufgenommen, in wie weit eine zufällige oder schon vorher definierte Ausgangslösung die
Ergebnisse beeinflusst. Aus den sich ergebenden fünf Schritten ergeben sich je nachdem, ob der
Schritt gewählt wurde oder nicht, 25 = 32 verschiedene Kombinationsmöglichkeiten. Aus Vortests ging
hervor, dass sich einige dieser nicht für eine erfolgreiche Problemlösung eignen würden, weil die
Partikel nicht in einer dem global besten Partikel nahen Region konvergierten, weshalb eine Auswahl
von 7 Kombinationen verblieb, die jeweils mit unterschiedlichen Schwarmgrößen (20, 40, … , 100)
untersucht wurden.
Da das globale Optimum für die gegebene Problemstellung nicht bekannt ist und somit dessen
Erreichung nicht als Abbruchkriterium dienen kann, wurde die Anzahl an Iterationen, die der Schwarm
für die Suche verwenden konnte, auf 20.000 begrenzt.
Die untersuchten Kombinationen der einzelnen Schritte für die Bestimmung der neuen Position der
Partikel, deren Ergebnisse im nächsten Kapitel vorgestellt werden, sind in Tabelle 4 zusammenfassend
dargestellt. Das „x“ gibt an, dass dieser Einzelschritt in dem jeweiligen Experiment verwendet wurde.
Tabelle 4: Untersuchte Kombinationen der Einzelschritte für das Positionsupdate
Experiment # Schritt 1: Zufälliger
Ausgangs-stundenplan
Schritt 2: Vertauschen
eines Zeitfensters
Schritt 3: Veranstaltung
aus ygbest
Schritt 4: Zeitfenster aus
ygbest
Schritt 5: Veranstaltung
aus ypbest
#3 x x x #6 x x x #19 x x #22 x x #24 x x x #25 x x #28 x x
Als Bewertung des erzeugten Stundenplans dienen die unterschiedlich stark gewichteten Constraints,
die in Kapitel 2.3.1 vorgestellt wurden. Die hardDozentConstraint erhielt einen Gewichtungsfaktor von
15, hardTerminConstraint von 5 und hardTeilnehmerConstraint von 7. Als einzige Soft Constraint gab
4 Experimente 22
es die Terminwünsche der Dozierenden, sofern diese nicht als Hard Constraint erfasst wurden. Diese
erhielten keine besondere Gewichtung, da sie nicht maßgeblich dafür sind, einen zulässigen
Stundenplan zu erzeugen. Der ursprüngliche, manuell erzeugte (Ausgangs-)Stundenplan erhält unter
Berücksichtigung dieser Constraints eine Bewertung von 1001.
4.2 Ausgewählte Ergebnisse
Dieses Kapitel widmet sich den Ergebnissen, die die einzelnen Kombinationen der Schritte des
Positionsupdates für die Partikel liefern. In den folgenden Kapiteln werden jeweils zwei Abbildungen
dargestellt, die die Ergebnisse für die kleinsten und größten untersuchten Schwarmgrößen von 20 bzw.
100 Partikeln gegenüberstellt. Die Abbildungen zeigen im unteren Teil neben den über 31
Replikationen aggregierten Verläufen der Mittelwerte, der Minima sowie Maxima die mittleren
Fitnesswerte über die Anzahl der Partikel zweier ausgewählter Replikationen im oberen Bereich. In
diesem Bereich ist erkennbar, dass die Streuung der Positionen der Partikel mit zunehmender Größe
des Schwarmes abnimmt und die Gesamtheit des Schwarms über den zeitlichen Verlauf, bzw. über die
Iterationen immer bessere Fitnesswerte erzielt. Die Achsen der Abbildungen wurden für alle
Darstellungen identisch gewählt und für die Fitnesswerte auf 1250 begrenzt, um für die besseren
Ergebnisse einen höheren Detaillierungsgrad zu erhalten und eine bessere Vergleichbarkeit der
Ergebnisse zu ermöglichen.
In den angegebenen Tabellen sind die Ergebnisse eines Experiments für die verschiedenen
Schwarmgrößen zusammengefasst und die darin enthaltenen besten Werte markiert.
4.2.1 Experiment #3
Abbildung 4-1: Verlauf der besten gefundenen Werte und Konvergenzverhalten der Partikel im
Experiment #3
4 Experimente 23
Tabelle 5: Deskriptive Statistik des Experiments #3
Schwarmgröße Mittelwert Standardab-weichung
Standardfehler Minimum Maximum
20 455,55 20,12 3,61 420 49840 445,61 20,19 3,63 389 48260 434,23 20,24 3,64 392 46980 419,03 19,51 3,50 383 461
100 413,52 19,46 3,49 368 454
4.2.2 Experiment #6
Abbildung 4-2: Verlauf der besten gefundenen Werte und Konvergenzverhalten der Partikel im
Experiment #6
Tabelle 6: Deskriptive Statistik des Experiments #6
Schwarmgröße Mittelwert Standardab-weichung
Standardfehler Minimum Maximum
20 296,58 9,27 1,67 275,00 313,00 40 292,52 11,16 2,00 250,00 305,00 60 290,94 8,56 1,54 270,00 305,00 80 292,68 7,67 1,38 273,00 304,00
100 286,65 8,96 1,61 263,00 303,00
4 Experimente 24
4.2.3 Experiment #19
Abbildung 4-3:Verlauf der besten gefundenen Werte und Konvergenzverhalten der Partikel im
Experiment #19
Tabelle 7: Deskriptive Statistik des Experiments #19
Schwarm-größe
Mittelwert Standardab-weichung
Standard-fehler
Minimum Maximum
20 298,87 7,52 1,35 282,00 311,00 40 306,65 10,93 1,96 280,00 326,00 60 288,52 8,50 1,53 262,00 303,00 80 288,55 7,11 1,28 277,00 305,00
100 284,87 7,46 1,34 269,00 299,00
4.2.4 Experiment #22
Abbildung 4-4: Verlauf der besten gefundenen Werte und Konvergenzverhalten der Partikel im
Experiment #22
4 Experimente 25
Tabelle 8: Deskriptive Statistik des Experiments #22
Schwarm-größe
Mittelwert Standardab-weichung
Standard-fehler
Minimum Maximum
20 312,10 11,88 2,13 273,00 333,00 40 317,39 12,00 2,16 295,00 345,00 60 304,52 12,44 2,23 264,00 330,00 80 299,06 7,95 1,43 278,00 312,00
100 295,03 9,56 1,72 270,00 309,00
4.2.5 Experiment #24
Abbildung 4-5: Verlauf der besten gefundenen Werte und Konvergenzverhalten der Partikel im
Experiment #24
Tabelle 9: Deskriptive Statistik des Experiments #24
Schwarm-größe
Mittelwert Standardab-weichung
Standard-fehler
Minimum Maximum
20 398,16 23,16 4,16 365,00 457,00 40 382,48 21,55 3,87 347,00 436,00 60 373,16 17,29 3,11 345,00 408,00 80 363,29 19,09 3,43 328,00 401,00
100 366,13 16,72 3,00 341,00 433,00
4 Experimente 26
4.2.6 Experiment #25
Abbildung 4-6: Verlauf der besten gefundenen Werte und Konvergenzverhalten der Partikel im
Experiment #25
Tabelle 10: Deskriptive Statistik des Experiments #25
Schwarm-größe
Mittelwert Standardab-weichung
Standard-fehler
Minimum Maximum
20 447,74 31,47 5,65 407,00 562,00 40 422,52 20,96 3,77 386,00 475,00 60 407,68 20,88 3,75 375,00 458,00 80 399,81 19,86 3,57 356,00 434,00
100 393,94 19,36 3,48 363,00 433,00
4.2.7 Experiment #28
Abbildung 4-7: Verlauf der besten gefundenen Werte und Konvergenzverhalten der Partikel im
Experiment #28
4 Experimente 27
Tabelle 11: Deskriptive Statistik des Experiments #28
Schwarm-größe
Mittelwert Standardab-weichung
Standard-fehler
Minimum Maximum
20 452,94 41,74 7,50 389 55740 437,90 32,03 5,75 376 48860 425,68 52,06 9,35 377 66080 410,29 32,13 5,77 353 503
100 402,81 23,23 4,17 354 454
4.2.8 Zusammenfassung und Vergleich
Mit keiner der vorgestellten Varianten der PSO konnte ein zulässiger Stundenplan erzeugt werden. Der
Grund dafür liegt in der Vielzahl der möglichen Fächerkombinationen, wie es die Ausführungen in
Kapitel 2.3 zeigen. Die PSO ist allerdings in allen der vorgestellten Varianten in der Lage, die
Bewertung des ursprünglichen manuell erzeugten Stundenplanes wesentlich zu verbessern.
Abbildung 4-8 zeigt einen beispielhaften Verlauf der einzelnen Bewertungen der Soft und Hard
Constraints sowie des sich daraus ergebenden Fitnesswertes des über alle Varianten des
Positionsupdates besten gefundenen Ergebnisses für einen Stundenplan. Diese Variante geht von
einem zufällig erzeugten Stundenplan aus. Es ist zu erkennen, dass weder die hardTerminConstraint
noch die hardDozentConstraint verletzt wird. Der Fitnesswert wird also durch die Bewertung der
hardTeilnehmerConstraint und der softTerminConstraint dominiert. Die Bewertung der Terminwünsche
verbleibt ab der ersten Iteration auf einem Niveau, das sich im weiteren Verlauf wenig ändert,
wohingegen die Bewertung für Studierende, die gleichzeitig an mehreren Veranstaltungen teilnehmen
müssen, stetig sinkt.
Abbildung 4-8: Verlauf der einzelnen Constraints bei einem Gesamtfitnesswert von 250 der Variante #6
für das Positionsupdate der PSO.
Als beste stellt sich Variante #6 heraus, die für alle Schwarmgrößen Bewertungen der Stundenpläne
unter 300 erzielte. Auch das über alle betrachteten Lösungen beste Ergebnis ist mit einer Bewertung
von 250 hier zu finden. Diese Variante ging jeweils von einem zufällig erzeugten Stundenplan aus und
4 Experimente 28
verbesserte die Lösung mit Hilfe der zufälligen Vertauschung eines Zeitfensters und der Übernahme
einzelner Veranstaltungen aus dem Stundenplan des global besten Partikel. Ähnlich gute Ergebnisse
werden von Variante #19 erzielt, welche das gleiche Verfahren zur Verbesserung der Lösung
verwendet, allerdings auf dem ursprünglichen Stundenplan aufbaut.
Bei beiden Verfahren lässt sich erkennen, dass während der ersten 2500 Iterationen eine schnelle
Verbesserung der Anfangsstundenpläne erzielt wird, die Verbesserung im weiteren Verlauf langsamer
von statten geht, aber im Vergleich zu anderen Varianten immer noch ein stetiger Abfall der
Fitnesswerte beobachtet werden kann. Auch die Differenzen der Maxima und Minima zu den
Mittelwerten fällt im Vergleich gering aus, was für eine hohe Homogenität innerhalb des Schwarmes
und eine hohe Robustheit der jeweiligen Verfahren spricht.
Innerhalb der verschiedenen Schwarmgrößen ist bei den Varianten, die Schritt 2, also das zufällige
Vertauschen von Zeitfenstern durchführen, die Standardabweichung auf unterschiedlichen Niveaus
homogen. Die geringsten Abweichungen lassen sich auch hier für die Varianten #6 und #19 finden. Bei
den Varianten, die Schritt 2 nicht ausführen, aber Zeitfenster aus der Lösung des global besten
Partikels verwenden, verringern sich mit steigender Schwarmgröße neben den Standardabweichungen
auch die erzielten Mittelwerte. D.h. diese Verfahren sind stark von der gewählten Populationsgröße
abhängig.
200
250
300
350
400
450
500
3 6 19 22 24 25 28
experiment #
fitne
ss v
alue
20
40
60
80
100
Schwarmgröße
Abbildung 4-9: Fitnessmittelwerte der durchgeführten Experimente in Abhängigkeit von der
Schwarmgröße
Eine Gegenüberstellung der Mittelwerte der erzielten Ergebnisse in Abhängigkeit unterschiedlicher
Schwarmgrößen wird für die verschiedenen Varianten der PSO in Abbildung 4-9 vorgenommen. Es ist
zu erkennen, dass mit steigender Schwarmgröße immer bessere Ergebnisse erzielt werden. Dies ist
4 Experimente 29
auch zu erwarten, da während der 20000 Iterationen insgesamt mehr Partikel nach Lösungen suchen
und damit mehr mögliche Stundenpläne untersucht werden. Während bei den Experimenten #3, #24,
#25 und #28 der Einfluss der Anzahl der Partikel sehr groß ist, ist dieser bei den Experimenten #6, #19
und #22 zwar vorhanden, aber sehr gering ausgeprägt. In Experiment #6 sind die geringsten
Unterschiede auszumachen. Da diese Kombination der Schritte für das Positionsupdate auch für kleine
Schwarmgrößen schon sehr gute Ergebnisse liefert, scheint eine weitere Erhöhung der Partikelanzahl
über 100 hinaus gemessen am erwarteten Aufwand nicht mehr sinnvoll.
Um die Aussage zu bekräftigen, dass kein zulässiger Stundenplan existiert, wird in Abbildung 4-10 der
von allen erzielten Ergebnissen beste Stundenplan dargestellt, in dem man erkennen kann, dass immer
noch eine Vielzahl von Überschneidungen für Studierende verschiedenster Fächerkombinationen gibt,
aber bei weitem nicht mehr so viele wie in dem in Abbildung 2-4 dargestellten. Montag Dienstag Mittwoch Donnerstag Freitag
08-10 Mathematik Religion Englisch Englisch Spanisch Englisch Chemie Religion Religion Biologie
10-12 Mathematik Französisch Englisch Griechisch Biologie Sport Biologie Physik Spanisch Sport Religion Werte und Normen Russisch Biologie
12-14 Russisch Sport Englisch Griechisch Spanisch Chemie Französisch Physik Mathematik Religion Werte und Normen Russisch Latein Informatik
14-16 Griechisch Chemie Latein Politik Sport Erdkunde Englisch Physik Französisch Religion
16-18 Sport Erdkunde Religion Spanisch Spanisch Sport Spanisch Sport Englisch
18-20 Erdkunde Englisch Englisch Chemie Russisch Biologie Mathematik Latein Erdkunde Erdkunde Biologie Mathematik Geschichte Biologie
Abbildung 4-10: Optimierter Stundenplan
5 Zusammenfassung und Ausblick 30
5 Zusammenfassung und Ausblick
In dieser Arbeit wurde ein reales Stundenplanproblem der Philosophischen Fakultät der Universität
Göttingen vorgestellt. Zu dessen Lösungsoptimierung wurde die für kontinuierliche Problemstellungen
entwickelte Particle Swarm Optimization in der Art modifiziert, dass sie sich für die Lösung
kombinatorischer Problemstellungen eignete. Es wurden verschiedene Parameterkombinationen auf
ihre Performanz hin untersucht und es konnte beobachtet werden, dass der Versuch erfolgreich verlief,
die Particle Swarm Optimization in der Form zu modifizieren, dass sie in der Lage ist, ein
kombinatorisches Problem zu lösen, ohne die Charakteristika dieses schwarmintelligenten Verfahrens
zu verändern. Die PSO konnte die Lösungsgüte des gegebenen manuell erstellen Stundenplanes mit
angemessenem Rechenaufwand wesentlich verbessern.
Besonders der Einfluss des Schrittes #3 (einzelne Veranstaltung aus global best) kann dabei in
Kombination mit Schritt #1 (Vertauschen eines zufälligen Zeitfensters der aktuellen Lösung)
hervorgehoben werden. Dies scheint für eine gute Balance zwischen Exploration des Lösungsraumes
und Exploitation einer guten Lösungsumgebung zu sprechen.
Da es sich bei dem vorgestellten Verfahren klassisch um ein Verfahren für kontinuierliche
Problemstellungen handelt, sollte weiterhin untersucht werden, wie sich Verfahren bei der Lösung des
vorgestellten Stundenplanproblems verhalten, die schon erfolgreich andere kombinatorische
Problemstellungen gelöst haben. Als besonders interessant erscheint in diesem Zusammenhang die
Frage, wie die PSO bei Untersuchungen zur Performanz zu weiteren schwarmintelligenten Verfahren,
z.B. der Ameisenalgorithmen abschneidet.
Da die PSO auch schon für die Optimierung einer Lösung für das Travelling Salesman Problem
herangezogen wurde, scheint eine generelle Eignung des Verfahrens für kombinatorische
Problemstellungen gegeben. Dies muss aber an weiteren Problemstellungen untersucht werden.
Literaturverzeichnis 31
Literaturverzeichnis
Abramson 1991: Abramson, A.: Constructing school timetables using simulated annealing: Sequential
and parallel algorithms. In: Management Science 37 (1991), S. 98-113.
Ahlborn/Kricke 1997: Ahlborn, W./Kricke, M.: Hilfsblätter zu den Vorlesungen in Statistik I für
Wirtschaftswissenschaftler, Göttingen 1997.
Arntzen/Løkketangen 2003: Arntzen, H./Løkketangen, A.: A tabu search heuristic for a university
timetabling problem. In: Proceedings of the Fifth Metaheuristics International Conference (2003)
Bai/Burke/Kendall 2006: Bai, R./Burke, E. K./Kendall, G.: A Simulated Annealing Hyper-heurisitc for
University Course Timetabling, In: Burke, E. K./Rudová, H.: PATAT 2006, 2006, S. 345-350.
Biethahn et al. 2004: Biethahn, J./Hönerloh, A./Kuhl, J./Nissen, V.: Methoden der praktischen
Entscheidungsfindung, Göttingen 2004.
Boufflet/Nègre 1996: Boufflet, J. P./Nègre, S.: Three Methods used to solve an Examination
Timetabling Problem, In: Burke, E. K./Ross, P.: The Practice and Theory of Automated
Timetabling, Berlin [u.a.] 1996, S. 327-344.
Burke et al. 1997: Burke, E./Jackson, K./Kingston, J./Weare, R.: Automated University Timetabling: The
State of the Art. In: The Computer Journal. - Oxford: Univ. Press 40 (1997) 9, S. 565-571.
Burke/Elliman 1995: Burke, E. K./Elliman, D. G. W. R. F.: Specialised Recombinative Operators for
Timetabling Problems. In: Proceedings of the AISB (Artificial Intelligence and Simulation of
Behaviour) Workshop on Evolutionary Computing (1995), S. 75-85.
Burke/Kendall/Soubeiga 2003: Burke, E. K./Kendall, G./Soubeiga, E.: A Tabu-Search Hyperheurisitc for
Timetabling and Rostering. In: Journal of Heuristics 9 (2003), S. 451-470.
Caldeira/Rosa 1998: Caldeira, J./Rosa, A.: School Timetabling Using Genetic Search. In: Lecture notes
in computer science. - Berlin: Springer 1408 (1998), S. 115-122.
Carter/Laporte 1998: Carter, M. W./Laporte, G.: Recent Developments in Practical Course Timetabling,
In: Burke, E./Carter M.,: The Practice and Theory of Automated Timetabling II, Berlin [u.a.] 1998,
S. 3-19.
Cheng et al. 1996: Cheng, C./Kang, L./Leung, N./White, G.: Investigations of a Constraint Logic
Programming Approach to University Timetabling. In: Lecture notes in computer science. - Berlin:
Springer (1996) Bd. 1153.1996, S. 112-129.
Chiarandini/Stützle 2002: Chiarandini, M./Stützle, T.: Experimental evaluation of course timetabling
algorithms, Darmstadt 2002.
Chu/Chen/Ho 2006: Chu, S./Chen, Y./Ho, J.: Timetable Scheduling Using Particle Swarm Optimization,
2006.
Clerc/Kennedy 2002: Clerc, M./Kennedy, J.: the particle swarm: explosion, stability and convergence in
multi-dimensional comlex space. In: IEEE Transactions on Evolutionary Computation 6 (2002) 1,
S. 58-73.
Literaturverzeichnis 32
Colorni/Dorigo/Maniezzo 1998: Colorni, A./Dorigo, M./Maniezzo, V.: Metaheuristics for High School
Timetabling. In: Computational Optimization and Applications 9 (1998), S. 275-298.
Corne/Ross/Fang 1994: Corne, D./Ross, P./Fang, H.: Fast Practical Evolutionary Timetabling. In:
Lecture notes in computer science. - Berlin: Springer 865 (1994), S. 251-263.
Costa 1994: Costa, D.: A Tabu Search Algorithm for Computing an Operational Timetable. In: Jornal of
the Operational Research Society 76 (1994), S. 98-110.
Dowsland/Thompson 2005: Dowsland, K. A./Thompson, J. M.: Ant colony optimization for the
examination scheduling problem. In: Jornal of the Operational Research Society 56 (2005),
S. 426-438.
Eiselt/Laporte 1987: Eiselt, H. A./Laporte, G.: Combinatorial Optimization Problems with Soft and Hard
Requirements. In: Jornal of the Operational Research Society 38 (1987) 9, S. 785-795.
Gaspero/Schaerf 2001: Gaspero, L. d./Schaerf, A.: Tabu search techniques for examination timetabling.
In: Lecture notes in computer science. - Berlin: Springer 2079 (2001), S. 104-117.
Heppner/Grenander 1990: Heppner, F./Grenander, U.: A stochastic nonlinear Model for coordinated
Bird Flocks, In: Krasner, S.: The Ubiquity of Chaos, Washington 1990, S. 233-238.
Hertz 1992: Hertz, A.: Tabu search for large scale timetabling problems. In: European Journal of
Operational Research 54 (1992), S. 39-47.
Hilbert-Siekmann 2001: Hilbert-Siekmann, H.: Zur Stundenplansetzung an allgemeinbildenden Schulen:
neue Möglichkeiten der gemischt-ganzzahligen Programmierung, Berlin 2001.
Junginger 1995: Junginger, W.: Course scheduling by genetic algorithms, In: Biethahn, J./Nissen, V.:
Evolutionary Algorithms in Management Applications, Berlin [u.a.] 1995, S. 357-370.
Kennedy 2005: Kennedy, J.: Particle Swarms. Optimization based on Sociocognition, In: De Castro, L.
N./Von Zuben, F. J.: Recent Developments in biologically inspired Computing, Hershey u. a.
2005, S. 235-268.
Kennedy/Eberhart 1995: Kennedy, J./Eberhart, R. C.: Particle Swarm Optimization, Proceedings of the
IEEE international Conference on neural Networks (Perth, Australia), Piscataway 1995, S. 1942-
1948.
Kennedy/Eberhart/Shi 2001: Kennedy, J./Eberhart, R. C./Shi, Y.: Swarm Intelligence, San Francisco u.
a. 2001.
Krins 1981: Krins, H.: Erstellung von Schulstundenplänen mit dem Computer, Düsseldorf 1981.
Mendes/Kennedy/Neves 2003a: Mendes, R./Kennedy, J./Neves, J.: Watch thy Neighbor or how the
Swarm can learn from its Environment, Proceedings of the IEEE Swarm Intelligence Symposium
(SIS-2003). Indianapolis, Indiana, April 24-26, 2003, Washington 2003, S. 88-94. (a)
Mendes/Kennedy/Neves 2003b: Mendes, R./Kennedy, J./Neves, J.: Avoiding the Pitfalls of local
Optima. How Topologies can save the Day, Proceedings of the 12th Conference intelligent
Systems Application to Power Systems (ISAP2003). Lemnos, Greece, August 2003, Washington
2003, (b)
Literaturverzeichnis 33
Paechter et al. 1994: Paechter, B./Cumming, A./Luchian, H./Petriuc, M.: Two Solutions to the General
Timetable Problem using Evolutionary Methods. In: Proceedings of the IEEE Conference on
Evolutionary Computation (1994), S. 300-305.
Paechter et al. 1998: Paechter, B./Rankin, R. C./Cumming, A./Fogarty, T. C.: Timetabling the Classes
of an Entire University with an Evolutionary Algorithm. In: Lecture notes in computer science. -
Berlin: Springer 1498 (1998), S. 865-874.
Paquet/Engelbrecht 2003: Paquet, U./Engelbrecht, A. P.: A new Particle Swarm Optimiser for linearly
constrained Optimisation, In: Sarker, R. u. a.: Proceedings of 2003 IEEE Congress on
evolutionary Computation (CEC- 2003). December 8-12, 2003 Canbella, Australia, Piscataway
2003, S. 227-233.
Qualizza/Serafini 2005: Qualizza, A./Serafini, P.: A Column Generation Scheme for Faculty
Timetabling, In: Burke, E./Trick, M.: Theory and Practice of Automated Timetabling, Berlin [u.a.]
2005, S. 161-173.
Reynolds 1987: Reynolds, C. W.: Flocks, Herds and Schools. A Distributed Behavioral Model, New
York 1987.
Reynolds 2001: Reynolds, C. W.: Background and Update, 2001.
Ross/Corne 1995: Ross, P./Corne, D.: Comparing Genetic Algorithms, Simulated Annealing, and
Stochastic Hillclimbing on Timetabling Problems. In: Lecture notes in computer science. - Berlin:
Springer 993 (1995), S. 94-102.
Ross/Hart/Corne 1998: Ross, P./Hart, E./Corne, D.: Some Observations about GA-based Exam
Timetabling. In: Lecture notes in computer science. - Berlin: Springer 1408 (1998), S. 115-129.
Rossi-Doria et al. 2003: Rossi-Doria, O./Sampels, M./Birattari, M./Chiarandini, M./Dorigo,
M./Gambardella, L. M./Knowles, J./Manfrin, M./Mastrolilli, M./Paechter, B./Paquete, L./Stützle, T.:
A Comparison of the Performance of Different Metaheuristics on the Timetabling Problem. In:
Lecture notes in computer science. - Berlin: Springer 2740 (2003), S. 329-351.
Schaerf 1996: Schaerf, A.: Tabu search techniques for large high-school timetabling problems. In:
Proceedings of the Thirteenth National Conference on Artificial Intelligence (1996), S. 363-368.
Schaerf 1999: Schaerf, A.: A Survey of Automated Timetabling. In: Artificial intelligence review. -
Dordrecht: Kluwer Acad. Publ. Group 13 (1999), S. 87-127.
Schimmelpfeng/Helber 2007: Schimmelpfeng, K./Helber, S.: Application of a real-world university-
course timetabling model solved by integer programming. In: OR Spectrum 29 (2007) 4, S. 783-
803.
Shi 2004: Shi, Y.: Particle Swarm Optimization, In: Yen, G. G.: coNNectionS. The Newsletter of the
IEEE Neural Networks Society, 2004, S. 8-13.
Shi/Eberhart 1998: Shi, Y./Eberhart, R. C.: Parameter Selection in Particle Swarm Optimization, In:
Porto, V. W. u. a.: Evolutionary Programming VII. Proceedings of the seventh annual Conference
on evolutionary Programming. New York (1998), Berlin u. a. 1998, S. 591-600.
Literaturverzeichnis 34
Shi/Eberhart 1999: Shi, Y./Eberhart, R. C.: Empirical Study of Particle Swarm Optimization, In:
Angeline, P. J. u. a.: Proceedings of the IEEE Congress on evolutionary Computation (CEC-
1999). Washington, USA, July 6-9, 1999, Piscataway 1999, S. 1945-1950.
Socha/Sampels/Manfrin 2003: Socha, K./Sampels, M./Manfrin, M.: Ant Algorithms for the University
Course Timetabling Problem with Regard to the State-of-the-Art. In: Lecture notes in computer
science. - Berlin: Springer 2611 (2003), S. 334-345.
Thompson/Dowsland 1996a: Thompson, J./Dowsland, K. A.: Variants of simulated annealing for the
examination timetabling problem. In: Anals of Operations Research 63 (1996) 1, S. 105-128. (a)
Thompson/Dowsland 1996b: Thompson, J./Dowsland, K. A.: General Cooling Schedules for a
Simulated Annealing based Timetabling System, In: Burke, E. K./Ross, P.: The Practice and
Theory of Automated Timetabling, Berlin [u.a.] 1996, S. 345-363. (b)
Van den Bergh 2002: Van den Bergh, F.: An Analysis of Particle Swarm Optimizers, Pretoria 2002.
Van den Bergh/Engelbrecht 2005: Van den Bergh, F./Engelbrecht, A. P.: A study of particle Swarm
optimization particle trajectories. In: Information Sciences Volume 176 (2005) Issue 8, S. 937-
971.
Wilson 1975: Wilson, E.: Sociobiology: The new synthesis, Cambridge 1975.
Yoshikawa et al. 1996: Yoshikawa, M./Kaneko, K./Yamanouchi, T./Watanabe, M.: A Constrained-Based
High School Scheduling System. In: IEEE Expert 11 (1996) 1, S. 63-72.
Zhang/Yu/Hu 2005: Zhang, L./Yu, H./Hu, S.: Optimal choice of parameters for particle swarm
optimization. In: Journal of Zhejiang University SCIENCE 6 (2005) 6, S. 528-534.
de Werra 1985: de Werra: An Introduction to Timetabling. In: European Journal of Operational
Research 19 (1985) 2, S. 151-162.
de Werra 1997: de Werra, D.: The Combinatorics of Timetabling. In: European Journal of Operational
Research 96 (1997) 3, S. 504-513.