Seminar: Evolutionäre Algorithmen

Dozent Andreas Zell, Fabian Becker, Nedim Šrndić
Sprechstunde nach Vereinbarung
Zeit Mittwoch, 16:15h
Umfang 2 SWS, 4 LP
Beginn 5. November 2014
Vorbesprechung 15. Oktober 2014, 17:15h
Ort Sand 1, C 311
Turnus unregelmäßig

Beschreibung

Das Seminar Evolutionäre Algorithmen behandelt Evolutionäre Algorithmen und weitere Optimierungsalgorithmen zur Optimierung schwerer Funktionen. Die behandelten Algorithmen zählen vorwiegend zur Klasse der Metaheuristiken und finden häufig Anwendung für 'Black-Box-Funktionen', deren Eigenschaften weitgehend unbekannt sind, weil sie analytisch schwer zu fassen sind. Wie in vielen technischen Feldern werden auch hier immer wieder biologische Prozesse als Vorbild genommen ('Bionik') und in leistungsfähige Algorithmen übertragen. Im Vergleich zu analytischen Verfahren sind sie in der Regel prinzipell wesentlich einfacher und dennoch in vielen Fällen erfolgreich. Die Seminarsprache ist englisch.

Hinweise:

  • Alle Teilnehmenden stellen ihre Arbeiten in je einem Vortrag (45 min. Dauer + 10 min. Diskussion) sowie einer schriftlichen Ausarbeitung (15-20 Seiten) vor.
  • Wir bitten um vorherige Mitteilung, falls jemand den Vorbesprechungstermin nicht wahrnehmen kann.
  • Die Vortragstermine werden je nach Teilnehmerzahl in der Vorbesprechung festgelegt.

Themen und Termine

"; // Sollen Anmeldebuttons gezeigt werden? if (!isset($isActive)) { $isActive = ($_GET['isActive'] == 'yes'); } // Inkludiere Parameter include_once("globalSettings.php"); // Variablen $tableHead = "background-color:#f0ece1;"; $tableRowStyle = "height:28"; $rowHeight = "18"; $tableRow1st = "background-color:#f4f1f0"; $tableRow2nd = "background-color:#ffffff"; $anmeldenButton = ""; $anmeldenURL = "/php/wwwseminar/anmeldung.php"; // Beginne Tabelle // print "\n\n"; print "\n
\n\n"; // Ermittle, ob es sich um ein Praktikum handelt, und ob man sich anmelden kann // Suche nach dem Schlüsselwort "Praktikum" im Titel des Seminars $query = "SELECT titel,querycode FROM seminar WHERE seminarURL = '$url'"; $result = mysql_query($query); $titel = mysql_result($result, 0,"titel"); $querycode = mysql_result($result, 0, "querycode"); $isPraktikum = (stristr($titel,"praktikum")!==false); // Prüfe, ob Veranstaltung zum laufenden Semester gehört $semester = getSemester($url); // $isActive = ($semester == $currentSemester); // Liste aller Termine einer Veranstaltung abrufen $query = "SELECT * FROM termin LEFT JOIN referent USING (ID_termin) LEFT JOIN seminar USING (ID_seminar) LEFT JOIN betreuer USING (betreuer) WHERE (termin.datum > '$WAITDATE_SQL') AND (seminarURL = '$url') ORDER BY termin.datum, termin.ID_termin"; $result = mysql_query($query); $number = mysql_numrows($result); if ($number <= 0) { // wenn keine Termine gefunden print "

Themen werden so schnell wie möglich online gestellt.

"; // Liste aller Termine einer Veranstaltung abrufen $query = "SELECT * FROM seminar WHERE (seminarURL = '$url')"; $result = mysql_query($query); $number = mysql_numrows($result); if ($number <= 0) { // wenn kein Eintrag in DB vorhanden // Veranstaltung eintragen $querycode = getRandomString(8); $query = "INSERT INTO seminar (titel, seminarURL, querycode) VALUES ('Titel','$url','$querycode')"; $result = mysql_query($query); } } else { // wenn Termine gefunden $i = 0; $HTMLrowcount = 0; $ID_temin_old = -1; if ($isPraktikum) { // print " \n"; print " \n"; print " \n"; print " \n"; print " \n"; print " \n"; while ($i < $number): // Daten aus SQL-Abfrage-Ergebnis extrahieren $ID_termin = mysql_result($result, $i, "ID_termin"); $betreuer = mysql_result($result, $i, "betreuer"); $betreuerURL = mysql_result($result, $i, "betreuer.url"); $maxReferenten = mysql_result($result, $i, "maxReferenten"); $vorname = htmlentities(mysql_result($result, $i, "vorname")); $name = htmlentities(mysql_result($result, $i, "name")); if (($vorname > "") || ($name > "")) { $referent = $vorname . " " . $name; } elseif ($maxReferenten > 0 and $isActive) { $referent = "$anmeldenButton"; } else { $referent = ""; } // Wechselnder Hintergrund für gerade/ungerade Tabellenzeilen // $style = ++$HTMLrowcount % 2 ? 'tr-even' : 'tr-odd'; // Ausgabe einer Tabellenzeile // print " \n"; print " \n"; $ii = $i + 1; print " \n"; if ($betreuerURL != "") { print " \n"; } else { print " \n"; } print " \n"; print " \n"; $i++; endwhile; } else { // wenn kein Praktikum // print " \n"; print " \n"; print " \n"; print " \n"; print " \n"; print " \n"; print " \n"; while ($i < $number): // Daten aus SQL-Abfrage-Ergebnis extrahieren $datum = formatDate(mysql_result($result,$i,"datum")); $ID_termin = mysql_result($result,$i,"ID_termin"); $titel = mysql_result($result,$i,"titel"); $betreuer = mysql_result($result,$i,"betreuer"); $betreuerURL = mysql_result($result,$i,"betreuer.url"); $maxReferenten = mysql_result($result,$i,"maxReferenten"); $vorname = mysql_result($result,$i,"vorname"); $name = mysql_result($result,$i,"name"); if (($vorname > "") || ($name > "")) { $referent = $vorname . " " . $name; } elseif ($maxReferenten > 0 and $isActive) { $referent = "$anmeldenButton"; } else { $referent = ""; } // Wechselnder Hintergrund für gerade/ungerade Tabellenzeilen // $style = ++$HTMLrowcount % 2 ? 'tr-even' : 'tr-odd'; // Ausgabe einer Tabellenzeile // print " \n"; print " \n"; print " \n"; print " \n"; if ($betreuerURL != "") { print " \n"; } else { print " \n"; } print " \n"; print " \n"; $i++; endwhile; } } // Warteliste eines Seminars abrufen // Als Warteliste wird ein Termin mit einem speziellen Datum ($WAITDATE_SQL) für ein bestimmtes Seminar angenommen. $query = "SELECT * FROM termin LEFT JOIN referent USING (ID_termin) LEFT JOIN seminar USING (ID_seminar) LEFT JOIN betreuer USING (betreuer) WHERE (termin.datum<='$WAITDATE_SQL') AND (seminarURL = '$url') ORDER BY referent.datum DESC"; $result = mysql_query($query); $number = mysql_numrows($result); if ($number > 0) { // Wenn Warteliste gefunden (Info: Eine Warteliste kann auch leer sein, d.h. noch keinen Namen enthalten) $j = 0; // Muster für Befehl vor Serverumstellung im März 2008: // $titel = mysql_result($result,$j,"termin.titel"); $titel = mysql_result($result,$j,"titel"); $ID_termin = mysql_result($result,$j,"ID_termin"); $warteliste = ""; while ($j < $number): // Daten aus SQL-Abfrage-Ergebnis extrahieren $vorname = htmlentities(mysql_result($result,$j,"vorname")); $name = htmlentities(mysql_result($result,$j,"name")); if(($vorname > "") || ($name > "")) { $warteliste = "$vorname $name
\n" . $warteliste; }; $j++; endwhile; $warteliste .= $isActive ? "$anmeldenButton" : ""; // Wechselnder Hintergrund für gerade/ungerade Tabellenzeilen // $style = i % 2 ? 'tr-odd' : 'tr-even'; // Ausgabe einer Tabellenzeile // print " \n"; print " \n"; if (!$isPraktikum) { print " \n"; } print " \n"; print " \n"; print " \n"; print " \n"; } print "\n
PraktikumsplatzBetreuungTeilnehmer(in)
$ii$betreuer$betreuer$referent
DatumThemaBetreuungReferent(in)
$datum$titel$betreuer$betreuer$referent
 $titel $warteliste
\n"; if ($isActive) { if ($isPraktikum) { print "

Zur Reservierung eines Platzes tragen Sie sich bitte mit den Schaltflächen ganz rechts in der Tabelle ein.
Diese Anmeldung ersetzt nicht die offizielle Anmeldung über das Campus-System! Sie dient zur Vorreservierung der einzelnen Plätze bis zur Vorbesprechung, an der Sie persönlich anwesend sein müssen.

"; } else { print "

Zur Reservierung eines Themas tragen Sie sich bitte mit den Schaltflächen ganz rechts in der Termin-Tabelle ein.
Diese Anmeldung ersetzt nicht die offizielle Anmeldung über das Campus-System! Sie dient zur Vorreservierung der einzelnen Termine bis zur Vorbesprechung, an der Sie persönlich anwesend sein müssen.

"; } } $getquery = explode('=', $_GET["query"]); if ( ($getquery[0] === "getlist") && ($getquery[1] === $querycode) ) { print "

Liste aller Teilnehmer

\n"; print "\n\n\n"; print " \n"; print " \n"; print " \n"; print " \n"; print " \n"; print " \n"; print " \n"; print " \n"; print " \n"; $query = "SELECT * FROM termin LEFT JOIN referent USING (ID_termin) LEFT JOIN seminar USING (ID_seminar) LEFT JOIN betreuer USING (betreuer) WHERE seminarURL = '$url' ORDER BY referent.datum DESC"; $result = mysql_query($query); $number = mysql_numrows($result); for ($i = 0; $i < $number; ++$i) { // Daten aus SQL-Abfrage-Ergebnis extrahieren $name = htmlentities(mysql_result($result, $i, "name")); $vorname = htmlentities(mysql_result($result, $i, "vorname")); $semester = htmlentities(mysql_result($result, $i, "semester")); $matrikelnr = htmlentities(mysql_result($result, $i, "matrikelnr")); $studiengang = htmlentities(mysql_result($result, $i, "studiengang")); $email = htmlentities(mysql_result($result, $i, "email")); $betreuer = htmlentities(mysql_result($result, $i, "betreuer")); print " \n"; print " \n"; print " \n"; print " \n"; print " \n"; print " \n"; print " \n"; print " \n"; print " \n"; } print "\n
NameVornameMatr.-Nr.EmailStudiengangSem.Betreuer
$name$vorname$matrikelnr$email$studiengang$semester$betreuer
\n"; // print email list print "

Email-Liste

\n

"; for ($i = 0; $i < 1; ++$i) { $email = htmlentities(mysql_result($result, $i, "email")); print "$email"; } for ($i = 1; $i < $number; ++$i) { $email = htmlentities(mysql_result($result, $i, "email")); print ", $email"; } print "

"; } ?>

Literaturempfehlungen

[1] Areibi, S. and Yang, Z. (2004). Effective memetic algorithms for vlsi design = genetic algorithms + local search + multi-level clustering. Evolutionary Computation, 12(3), 327-353.
[2] Bird, S. and Li, X. (2006). Adaptively choosing niching parameters in a PSO. In GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation, pages 3-10, New York, NY, USA. ACM.
[3] Blum, C. (2005). Ant colony optimization: Introduction and recent trends. Physics of Life reviews, 2(4), 353-373.
[4] Clerc, M. (2005). Particle Swarm Optimization. ISTE Ltd, London, UK.
[5] Clerc, M. and Kennedy, J. (2002). The Particle Swarm-Explosion, Stability, and Convergence in a Multidimensional Complex Space. IEEE Transactions on Evolutionary Computation, 6(1), 58-73.
[6] Dorigo, M. and Socha, K. (2007). An introduction to ant colony optimization.
[7] Dorigo, M. and Stützle, T. (2003). The ant colony optimization metaheuristic: Algorithms, applications, and advances. Handbook of metaheuristics, pages 250-285.
[8] Eiben, A. E. and Smith, J.E. Introduction to Evolutionary Computing. Springer, Natural Computing Series. 2nd printing, 2007. ISBN: 978-3-540-40184-1
[9] Engelbrecht, A. P. (2007). Computational Intelligence: An Introduction. Wiley. Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. The University of Michigan Press, Cambridge, MA, USA.
[10] Juille, H. and Pollack J.B. (1996). Dynamics of Co-evolutionary Learning. Fourth International Conference on Simulation of Adaptive Behavior, pages 526-534.
[11] Lozano, M., Herrera, F., Krasnogor, N., and Molina, D. (2004). Real-coded memetic algorithms with crossover hill-climbing. Evolutionary Computation, 12(3), 273--302.
[12] Merz, P. (2004). Advanced fitness landscape analysis and the performance of memetic algorithms. Evolutionary Computation, 12(3), 303-325.
[13] Pollack, J., Blair, A., and Land, M. (1997). Coevolution of a backgammon player. Artificial life five, 5.
[14] Price, K. and Storn R.M. and Lampinen J.A. (2005). Differential Evolution: A Practical Approach to Global Optimization. Springer, Natural Computing Series.
[15] Rechenberg, I. (1973). Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Fromman-Holzboog, Stuttgart.
[16] Schwefel, H.-P. (1975). Evolutionsstrategie und numerische Optimierung. Dr.-Ing. Thesis, Technical University of Berlin, Department of Process Engineering.

Stilvorlage

  • Für die Erstellung der Ausarbeitung mit Word97/2000 gibt es hier eine Stilvorlage ( Word97-Format, 27kB).
  • Wenn Sie eine andere Textverarbeitung bevorzugen, orientieren Sie sich bitte an diesem Muster ( PDF-Format, 13kB).
  • Für Latex-Fans gibt es einen Style mit kleiner Demo.

Diese Seite drucken