Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

Experimentelle Laufzeitanalyse Evolutionärer Algorithmen

MSc Projektseminar - Winter 2020/21

Diese Lehrveranstaltung wird hybrid durchgeführt. Deshalb ist es wichtig, dass sich alle Teilnehmenden bis zum 29. Oktober im Moodle des Kurses einschreiben. Beachte das dieser Termin von der allgemeinen Einschreibefrist abweicht und die Registrierung zusätzlich zur normalen Einschreibung über das Studienreferat erfolgt. Im Moodle wird zeitnah der Zoom-Link für das erste Treffen veröffentlicht, das am 3. November um 9:15 Uhr stattfindet. Wer mag, darf dies in Präsenz in A-1.12 wahrnehmen. Weitere Treffen nach Absprache.

Beschreibung

In diesem Kurs geht es um die experimentelle Evaluierung von Algorithmen, konkreter um eine experimentelle Laufzeitanalyse von randomisierten Suchheuristiken. Zum Beispielen wollen wir experimentell nachvollziehen, dass ein einfacher evolutionräter Algorithmus das Maximum der Funktion, welche einem Bitstring immer die Anzahl der 1en im Bitstring zuordnet, in Zeit O(n log n) findet. Hierfür gibt es natürlich auch Beweise, man kommt mit schon leicht komplexeren Algorithmen aber schon schnell an die Grenzen des beweisbaren.

Um die Beweisfindung zu unterstützen hilft häufig eine experimentelle Analyse. In vergangenen Jahren hat die saubere experimentelle Analyse immer mehr an Ansehen gewonnen und kann inzwischen selbst als Ergänzung zu theoretischen Arbeiten publiziert werden.

Im ersten Teil dieses Kurses wollen wir ein webbasiertes Open Source Tool entwickeln, mit dem man nun seine eigene Suchheuristiken aus Bausteinen selbst zusammen bauen kann (wir wollen Blockly nutzen). Der Fokus soll hierbei auf evolutionären Algorithmen (EAs) nach dem Konzept Variation-Selektion liegen. Ziel ist es (a) theoretische Forscher schnell Vermutungen zu Laufzeitschranken entwickeln zu lassen sowie (b) Dozenten eine einfache Möglichkeit zu geben, praktische EA-Erfahrungen in Kurse zu integrieren.

Im zweiten Teil wollen wir nun selbst EAs analysieren, insbesondere der sogenannte Crossover entzieht sich bisher immer wieder einer detaillierten Analyse. Hier wollen wir experimentell ein paar Aussagen über das Laufzeitverhalten treffen. Dies dient auch als Showcase für das im ersten Teil entwickelte Tool.

Das Tool mit Showcase wollen wir dann in einer gemeinsamen Publikation veröffentlichen.

Voraussetzungen

Vorausgesetzt wird eine Bereitschaft zum selbstständigen Arbeiten. Weiterhin benötigen wir Techniken aus dem Bereich der Webprogrammierung, welche nicht in dem Kurs vermittelt werden; der Anteil der experimentellen Laufzeitanalyse wird in diesem Kurs vermittelt.

Lern- und Lehrformen

Die Studierenden implementieren selbstständig eine Oberfläche für die Analyse grundlegender Suchheuristiken; die genauen Anforderungen an diese Oberfläche werden dabei gemeinsam von den Studierenden und den beiden Dozenten entwickelt. Danach nutzen die Studierenden die Oberfläche zur Analyse von Suchheuristiken, betreut durch die Dozenten. Insgesamt ergibt sich also ein problembasiertes Lernen. Das die Ziel ist eine gemeinsame Publikation.

Leistungserfassung

Das Projektergebnis (interaktive Webseite sowie experimentelle Laufzeitanalyse, jeweils 50%) wird als Teamarbeit bewertet.

Termine

Unsere Treffen finden dienstags, 9:15 - 10:45 im A-1.12 statt.