43
Arbeitsbericht Nr. 05/2007 Hrsg.: Matthias Schumann Ole Brodersen, Matthias Schumann Einsatz der Particle Swarm Optimization zur Optimierung universitärer Stundenpläne

Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

  • Upload
    lethuy

  • View
    228

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

Arbeitsbericht Nr. 05/2007 Hrsg.: Matthias Schumann

Ole Brodersen, Matthias Schumann

Einsatz der Particle Swarm Optimization zur Optimierung universitärer Stundenpläne

Page 2: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

[email protected]

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.

Page 3: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 4: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 5: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 6: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 7: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

Abbildungsverzeichnis V

Abbildung 4-10: Optimierter Stundenplan ............................................................................................. 29

Page 8: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 9: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 10: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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.

Page 11: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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).

Page 12: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 13: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 14: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 15: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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.

Page 16: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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.

Page 17: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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:

Page 18: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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)

Page 19: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 20: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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.

Page 21: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 22: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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)

Page 23: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 24: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 25: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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)

Page 26: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 27: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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.

Page 28: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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:

Page 29: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 30: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 31: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 32: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 33: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 34: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 35: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 36: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 37: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 38: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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

Page 39: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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.

Page 40: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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.

Page 41: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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)

Page 42: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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.

Page 43: Einsatz der Particle Swarm Optimization zur Optimierung ...webdoc.sub.gwdg.de/ebook/serien/lm/arbeitsberichte_wi2/2007_05.pdf · Particle Swarm Optimization, Universitäre Stundenplanung,

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.