Druckansicht

Vorlesung Evolutionäre Algorithmen

Sommersemester 2014

Neuigkeiten

Die Ergebnisse der Klausir sind ab sofort im HISQIS abrufbar. Die Klausureinsicht findet am Do. den 21.08. von 13-14 Uhr in Raum G29-015 statt

Übersicht

• Allgemeines
• Termine und Räume
• Dozenten
• Schein- und Prüfungskriterien
• Voraussetzungen
• Folien aus der Vorlesung
• Übungsblätter
• Zusätzliche Unterlagen
• Literatur
• Verweise

Allgemeines

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

Evolutionäre Algorithmen orientieren sich an der biologischen Evolution. Anhand zufälliger Mutationen, Verschmelzungen (die die sexuelle Reproduktion nachbilden) und gezielter 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 der verschiedenen Arten evolutionärer Algorithmen. Vor- und Nachteile dieser Algorithmen werden untersucht und an Beispielen erläutert. Außerdem werden verwandte Verfahren und Metaheuristiken, wie z.B. das simulierte Ausglühen, behandelt.

Termine und Räume

Jede(r) Studierende, die/der an einer der Übungen teilnehmen will, muss sich über den FIN Registration Service zu einer der Übungen anmelden. Die Anmeldung wird nach dem offiziellen Ende der ersten Vorlesung bis 10 Uhr am Tag der ersten Übung freigeschaltet. Es wird darum gebeten, bei der Registrierung eine E-Mail-Adresse anzugeben, in dessen Posteingang man auch regelmäßig hineinschaut.

Dozenten

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

• Sanaz Mostaghim, sanaz.mostaghimovgu.de
• Pascal Held, pheld@ovgu.de
• Marco Dankel, marco.dankel@farafin.de

Schein- und Prüfungskriterien

Ein neues Aufgabenblatt mit schriftlichen und Programmieraufgaben wird jede Woche auf dieser Internetseite veröffentlicht. Die schriftlichen Aufgaben müssen am Beginn einer jeden Übung votiert werden. Durch das Votieren erklärt man sich bereit, dass man in der Lage ist, die Aufgabe und einen Lösungsvorschlag zu erklären und präsentieren. (Der Vorschlag muss nicht vollständig richtig sein. Es muss allerdings klar werden, dass man sich gewissenhaft mit der Aufgabe auseinandergesetzt hat.)

Studierende, die den Kurs mit einer Prüfung oder einem benoteten Schein beenden wollen, müssen

• regelmäßig und gut in den Übungen mitarbeiten,
• mindestens zwei Drittel der schriftlichen Aufgaben votieren,
• mindestens zweimal eine Lösung zu einer schriftlichen Aufgabe während der Übung präsentieren,
• schließlich eine schriftliche Prüfung nach dem Kurs bestehen.

Das Bestehen der schriftlichen Prüfung ermöglicht ebenfalls den Erhalt eines unbenoteten Scheines falls ein solcher von einer/einem Studierenden anstatt der Prüfung erwünscht wird.

Voraussetzungen

Sie müssen nicht, aber Sie sollten Hintergrundwissen verfügen über

• Algorithmen und Datenstrukturen,
• Programmierung und Modellierung,
• Mathematik I bis IV.

Folien aus der Vorlesung

Die Folien der Vorlesung werden rechtzeitig hochgeladen so wie der Kurs fortschreitet.

• 10.04.2014: Vorlesungsteil 00 (Organisatorisches)
• 17.04.2014: Vorlesungsteil 01 (Einführung)
• 24.04.2014: Vorlesungsteil 02 (Metaheuristiken und verwandte Optimierungsverfahren I/II)
• 08.-15.05.2014: Vorlesungsteil 03 (Kodierung, Fitness, Selektion)
• 22.05.2014: Vorlesungsteil 04 (Variation und genetische Operatoren)
• 05.06.2014: Vorlesungsteil 05 (Metaheuristiken und verwandte Optimierungsverfahren II/II)
• 05.06.2014: Vorlesungsteil 06 (Das Schematheorem, No Free Lunch Theorem)
• 12.06.2014: Vorlesungsteil 07 (Genetische Programmierung)
• 19.06.2014: Vorlesungsteil 08 (Mehrkriterienoptimierung)
• 26.06.2014: Vorlesungsteil 09 (Parallelisierung und Verhaltenssimulation)

Übungsblätter

Die Sammlung von Übungsblättern wird hier wöchentlich erweitert.

• 01. Übungsblatt zum 15.04.2014 (Evolutionstheorie, Genetik, Optimierungsproblem)
• 02. Übungsblatt zum 22.04.2014 (Evolutionstheorie, n-Damen-Problem)
• 03. Übungsblatt zum 29.04.2014 (Lokale Suchverfahren, Problem des Handlungsreisenden, Scatter Search)
• 04. Übungsblatt zum 20.05.2014 (Gray-Kodes, Glücksradauswahl, Selektionsintensität, Selektionsdruck)
• 05. Übungsblatt zum 27.05.2014 (Fitnessfunktion, Selektionsverfahren)
• 06. Übungsblatt zum 03.06.2014 (Rekombinationsverfahren)
• 07. Übungsblatt zum 10.06.2014 (Differentialevolution, Springerproblem, Ameisenkolonieoptimierung)
• 08. Übungsblatt zum 17.06.2014 (Das Schematheorem)
• 09. Übungsblatt zum 10.06.2014 (Genetische Programmierung, n-Damen-Problem, Packprobleme)
• 10. Übungsblatt zum 02.07.2014 (Iteriertes Gefangenendilemma, Pareto-Front)

Zusätzliche Unterlagen

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

• C-Programm zum Lösen des n-Damen-Problems mithilfe von Backtracking: queens.c (Version 1.4, 09.01.2002)
• C-Programm zum Lösen des n-Damen-Problems mithilfe eines evolutionären Algorithmus: qga.c (Version 1.2, 23.10.2001)
• Codefragment zum Stochastic Universal Sampling: sus.c
• Shellskript zur Turnierauswahl beim n-Damen-Problem: qga.txt (danach umbenennen in qga.sh)
• C-Programm zum Lösen des Springerproblems mithilfe verschiedener Algorithmen: knight.c (Version 1.5, 17.11.2001)
• Zwei kleine Demo-Applets: PSOpt Demo und ACOpt Demo

Literatur

• Kruse, Borgelt, Klawonn, Moewes, Ruß, Steinbrecher (2011). Computational Intelligence, Vieweg+Teubner, Wiesbaden.
• Ines Gerdes, Frank Klawonn, Rudolf Kruse (2004). Evolutionäre Algorithmen. Vieweg, Wiesbaden.
• Karsten Weicker (2007). Evolutionäre Algorithmen. 2., überarb. u. erw. Auflage, Teubner, Wiesbaden.
• Volker Nissen (1997). Einführung in evolutionäre Algorithmen. Optimierung nach dem Vorbild der Evolution. Vieweg, Braunschweig/Wiesbaden.
• Zbigniew Michalewicz (1998). Genetic Algorithms + Data Structures = Evolution Programs. Springer, Berlin.
• Richard Dawkins (1990). The Selfish Gene. Oxford University Press, Oxford, UK. (deutsche Ausgabe: Das egoistische Gen. Rowohlt, Hamburg, 1996)
• Richard Dawkins (1996). The Blind Watchmaker. Penguin Books, London, UK. (deutsche Ausgabe: Der blinde Uhrmacher. dtv, München, 1996)
• E. K. Burke, M. R. Hyde and G. Kendall (2006), "Evolving Bin Packing Heuristics with Genetic Programming" in Lecture Notes in Computer Science, Vol. 4193, Springer Verlag, Berlin / Heidelberg, Seiten 860-869 (Artikel zur Lösung des Packproblems in Aufgabe 40 mittels GP)

Verweise auf andere Webseiten

• Otto-von-Guericke-Universität Magdeburg
• Fakultät für Informatik
• Institut für Wissens- und Sprachverarbeitung
• Arbeitsgruppe Computational Intelligence
• Andere Lehrveranstaltungen unserer Arbeitsgruppe