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.
