Vorlesung Evolutionäre Algorithmen

Sommersemester 2008

Aktuelles

Die Anmeldung zur schriftlichen Prüfung kann bis zum 08.07.2008 im Prüfungsamt der FIN erfolgen.

Die Anmeldung zu einem mündlichen Scheingespräch kann ab jetzt erfolgen.

Seit dem 14.04. findet die Vorlesung im Hörsaal G29-307 statt

Übersicht

• Allgemeines
• Termine und Räume
• Lehrende
• Übungsblätter
• Zusätzliche Unterlagen
• Literatur
• Verweise

Allgemeines

Auf dieser Seite finden Sie verschiedene Informationen zu der Vorlesung "Evolutionäre Algorithmen", die im Sommersemester 2008 von Prof. Rudolf Kruse an der Otto-von-Guericke-Universität Magdeburg gehalten wird. Diese Seite wird im Laufe des Semesters aktualisiert.

Genetische und evolutionäre Algorithmen orientieren sich an der biologischen Evolution. Durch zufällige Mutationen, Verschmelzungen (die die sexuelle Reproduktion nachbilden) und gezielte Selektion wird versucht, Funktionen zu optimieren und (kombinatorische) Optimierungsprobleme zu lösen. Die Vorlesung gibt, ausgehend von einer kurzen Einführung in die biologischen Grundlagen, einen Überblick über verschiedene Arten genetischer und evolutionärer Algorithmen und die genetische Programmierung. Vor- und Nachteile dieser Algorithmen werden untersucht und an Beispielen erläutert. Außerdem werden verwandte Verfahren, wie z.B. das simulierte Ausglühen, behandelt.

Termine und Räume

Die Prüfung findet am Dienstag, den 22.07.2008 von 13:00 bis 15:00 Uhr in G29-307 (FIN-Horsaal) statt. Es wird gebeten, dass sich jeder Prüfling beim Prüfungsamt in die dort ausliegende Prüfungsliste einträgt. Auch Studenten, die sich bereits elektronisch eingetragen haben, werden gebeten dies per Hand im Prüfungsamt zu wiederholen.

Die Scheingespräche finden im Besprechungsraum G29-018 vom 16. bis 18. Juli und am 23. Juli zu verschiedenen Uhrzeiten statt. Es wird halbstündige Gespräche zu dritt geben. Die Anmeldung zu einem Scheingespräch erfolgt bis zum 15.07.2008 in Raum G29-019 bei Herrn Moewes.

Lehrende

Wenn Sie Fragen zur Vorlesung oder zu den Übungen haben, wenden Sie sich bitte (wenn möglich, per E-mail) an:

• Prof. Rudolf Kruse, kruse@iws.cs.uni-magdeburg.de
• Frank Rügheimer, ruegheim@iws.cs.uni-magdeburg.de
• Christian Moewes, cmoewes@iws.cs.uni-magdeburg.de

Übungsblätter

Zu den Übungen gibt es Übungsblätter. Die Übungsaufgaben werden votiert. Durch eine Votierung erklärt man sich bereit, zu einer Aufgabe vorzutragen. (Lösungsvorschläge werden diskutiert, sie müssen nicht gleich richtig sein. Man sollte sich aber gründlich mit der Aufgabe beschäftigt haben.) Den Übungsschein bekommt, wer

• mindestens die Hälfte der Übungsaufgaben votiert,
• mindestens zweimal in den Übungen vorgetragen, und
• am Ende des Semesters ein kurzes Kolloquium (ca. 10 Min./Person; auch in Gruppe mit bis zu 4 Personen möglich) bestanden hat.

An dieser Stelle finden Sie alle bisher bearbeiteten Übungsblätter sowie das jeweils aktuelle Übungsblatt als PDF-Datei.

• 1. Übungsblatt: ea01.pdf
• 2. Übungsblatt: ea02.pdf
• 3. Übungsblatt: ea03.pdf
• 4. Übungsblatt: ea04.pdf
• 5. Übungsblatt: ea05.pdf
• 6. Übungsblatt: ea06.pdf
• 7. Übungsblatt: ea07.pdf
• 8. Übungsblatt: ea08.pdf
• 9. Übungsblatt: ea09.pdf
• 10. Übungsblatt: ea10.pdf
• 11. Übungsblatt: ea11.pdf

Zusätzliche Unterlagen

An dieser Stelle finden Sie zusätzliche Unterlagen zur Vorlesung und zu den Übungen.

• Folien der Vorlesung:
  ea08t1.pdf (1. Teil)
  ea08t2.pdf (2. Teil)
  ea08t3.pdf (3. Teil)
  ea08t4.pdf (4. Teil)
  ea08t5.pdf (5. Teil) (neue Fassung mit Korrekturen für Folien 19 und 21)
  ea08t6.pdf (6. Teil)
  ea08t7.pdf (7. Teil)
  ea08t8.pdf (8. Teil)
  ea08t9.pdf (9. Teil) (neue Fassung mit Korrekturen für Folien 66 und 67)
  ea08t10.pdf (10. und letzter Teil)
  
• Ein C-Programm, das das n-Damen-Problem mit Hilfe von Backtracking löst:
  queens.c (Version 1.4, 09.01.2002)
• Ein C-Programm, das das n-Damen-Problem mit Hilfe eines genetischen Algorithmus löst:
  qga.c (Version 1.2, 23.10.2001)
• Ein C-Programm, das das Springerproblem mit verschiedenen Algorithmen löst:
  knight.c (Version 1.5, 17.11.2001)
• Ein Programm zur Berechnung und Dekodierung von Gray-Kodes (Aufgabe 8):
  gray.c
• Ein Kodefragment zum Stochastic Universal Sampling:
  sus.c
• Shellskript zur Turnierauswahl beim n-Damen-Problem:
  qga.sh

Literatur

• I. Gerdes, F. Klawonn, R. Kruse.
  Evolutionäre Algorithmen.
  Vieweg, Wiesbaden, 2004
• Volker Nissen.
  Einführung in evolutionäre Algorithmen. Optimierung nach dem Vorbild der Evolution.
  Vieweg, Braunschweig/Wiesbaden 1997
• Zbigniew Michalewicz.
  Genetic Algorithms + Data Structures = Evolution Programs.
  Springer, Berlin 1998
• Zu den biologischen Grundlagen:
  Richard Dawkins.
  The Selfish Gene.
  Oxford University Press, Oxford, UK, 1990.
  deutsche Ausgabe: Das egoistische Gen.
  Rowohlt, Hamburg 1996
• Richard Dawkins.
  The Blind Watchmaker.
  Penguin Books, London, UK, 2000
  deutsche Ausgabe: Der blinde Uhrmacher.
  dtv, München, 1996.

Verweise auf andere Webseiten

• Otto-von-Guericke-Universität Magdeburg
• Fakultät für Informatik
• Institut für Wissens- und Sprachverarbeitung
• Arbeitsgruppe Neuronale Netze und Fuzzy-Systeme
• andere Lehrveranstaltungen der Arbeitsgruppe