Computational-Intelligence

News-Archiv

Druckansicht

Vorlesung Evolutionäre Algorithmen

Sommersemester 2011

Neuigkeiten

Die Ergebnisse der Klausur vom 3. August 2011 sind verfügbar. Einsichtnahme in die Klausur kann am Montag, den 26. September 2011 von 13 bis 15 Uhr in G29-019 oder nach Absprache mit Christian Moewes genommen werden.

Übersicht

zurück zum Seitenanfang

Allgemeines

Auf dieser Seite finden Sie verschiedene Informationen zu der Vorlesung "Evolutionäre Algorithmen", die im Sommersemester 2011 von Prof. Dr. Rudolf Kurse 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.

Der Höhepunkt dieser Lehrveranstaltung wird ein Programmierwettbewerb sein, an dem alle Studierende fakultativ teilnehmen können. Ziel wird es sein, einen evolutionären Algorithmus zur Lösung des Brettspiels Mühle zu entwickeln. Die erfolgreiche Abnahme der KI wird als Prüfungszulassung gelten.

zurück zum Seitenanfang

Termine und Räume

 DozentWochentagZeitRaumDatum
VorlesungProf. R. Krusemontags13:15 - 14:45 UhrG29-307ab 04.04.2011
ExperimentJ. FeigenspanMittwoch11:15 - 12:45 UhrG29-144am 06.04.2011
ExperimentJ. FeigenspanMittwoch13:15 - 14:45 UhrG29-144am 06.04.2011
ÜbungC. Moewesmittwochs11:00 - 12:30 UhrG29-E037ab 13.04.2011
ÜbungC. Moewesmittwochs13:15 - 14:45 UhrG22A-218ab 13.04.2011

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.

Die schriftliche Prüfung findet am Mittwoch, den 3. August 2011 in der Zeit von 10:00 bis 12:00 Uhr s.t. in G29-307 statt. Wir bitten darum, mindestens 10 Minuten vor der eigentlichen Prüfung zu erscheinen. Es werden keine Hilfsmittel zugelassen! Schreibpapier wird gestellt. Mitzubringen sind lediglich

  • ein Lichtbildausweis (Personalausweis oder Studierendenausweis mit Foto),
  • Schreibmaterial (Stifte/Füller, die entweder blau oder schwarz schreiben).

Auch Studierende, die einen Leistungsnachweis in Form eines (un)benoteten Scheins benötigen, müssen an dieser Prüfung teilnehmen. Nach der Klausur wird auf dieser Webseite dann auch bekanntgegeben, an welchem Tag Studierenden die Einsicht in die Klausuren gestattet ist.

zurück zum Seitenanfang

Dozenten

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

zurück zum Seitenanfang

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.

Anstatt der Übungsteilnahme kann auch der Programmierwettbewerb als Prüfungszulassung gelten, falls es eine erfolgreiche Abnahme der Studierenden entwickelten KI gibt.

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.

zurück zum Seitenanfang

Voraussetzungen

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

  • Algorithmen und Datenstrukturen,
  • Programmierung und Modellierung,
  • Mathematik I bis IV.
zurück zum Seitenanfang

Folien aus der Vorlesung

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

zurück zum Seitenanfang

Übungsblätter

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

zurück zum Seitenanfang

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)
zurück zum Seitenanfang

Programmierwettbewerb

Der Programmierwettbewerb aus dem Jahr 2003 lebt noch einmal auf! Es soll wieder ein Programm entwickelt und geschrieben werden, das gegen einen Spieler das Brettspiel Mühle spielen kann.

Die Regeln des Spiels müssen beachtet werden. Ziel im Rahmen dieser Lehrveranstaltung ist die Entwicklung einer KI, die anhand von EA-Methoden optimiert wurde. Für eine erfolgreiche Abnahme muss jede(r) Studierende aufzeigen können, dass ihre/seine KI auch mithilfe von EAs optimiert wurde.

Verschiedene Funktionen stehen zur Verfügung, mit denen man Informationen über das Spiel erhält und Spielzüge ausführen kann. Jedes Programm kann leicht getestet werden, indem es z.B. gegen einen Menschen oder gegen Walter (ein einfacher Testgegner) antritt.

Meilensteine:

  • 06.04.2011 ab 11:00 Uhr MEZ: Anmeldebeginn
  • 11.04.2011 bis 13:30 Uhr MEZ: Anmeldeschluss
  • 03.05.2011 bis 18:00 Uhr MEZ: Abgabe eines technischen Konzepts
  • 25.05.2011 bis 18:00 Uhr MEZ: Abgabe eines lauffähigen Prototypen
  • 21.06.2011 bis 18:00 Uhr MEZ: Abgabe der entwickelten Spieler inklusive Dokumentation
  • 06.07.2011 ab 11:00 Uhr MEZ: Siegerehrung und Auswertung des Wettbewerbs
  • Spielregeln
  • Herunterladen
  • Implementierung
zurück zum Seitenanfang

Literatur

  • 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)
zurück zum Seitenanfang

Verweise auf andere Webseiten

zurück zum Seitenanfang
en lang icon de lang icon Printable View - Recent Changes
Page last modified on September 15, 2011, at 05:11 PM by cmoewes