[Termine] [Zusammenfassung] [Folien] [Übungen]
| Wann? | Wo? | |
| Vorlesung | do 10 - 12 | O-H 14, R 104 |
| Übung | di 12 - 14 | O-H 14, R 104 |
Evolutionäre Algorithmen haben ihre Wurzeln in der Bionik: Man hofft durch Nachahmung von Vorgängen, die man in der Natur zu erkennen glaubt, hilfreiche praktische Verfahren zu erhalten. Auch ganz entgegengesetzte Interessen gibt es: Man hofft, den Prozess der natürlichen Evolution besser zu verstehen, indem man ihn algorithmisch nachahmt und untersucht. Wir wollen uns evolutionäre Algorithmen aber weder aus der Sicht der Ingenieurwissenschaften noch aus der Sicht der Biologie ansehen. Wir nehmen die Perspektive der Informatik ein.
Evolutionäre Algorithmen sind randomisierte Suchheuristiken, die in vielen verschiedenen Bereichen eingesetzt werden können. Es gibt nicht "den" evolutionären Algorithmus: Es handelt sich um eine recht große Klasse von Algorithmen, wobei die Grenzen fließend sind. Wir nehmen eine Modulsicht ein, beschreiben die grundlegenden Module, aus denen evolutionäre Algorithmen zusammengesetzt werden und lernen die wichtigsten Implementierungen der verschiedenen Module kennen. Das erlaubt es uns, in unsere Beschreibung auch randomisierte Suchheuristiken mit einzubeziehen und einzuordnen, die typischer Weise nicht mehr zu den evolutionären Algorithmen gezählt werden.
Wir untersuchen evolutionäre Algorithmen vor allem aus einer theoretischen Perspektive. Wir verschaffen uns darum zunächst einen Überblick über übliche Ansätze zur theoretischen Untersuchung evolutionärer Algorithmen und konzentrieren uns dann auf die Untersuchung der erwarteten Optimierzeit. Für erste theoretische Analysen ist es hilfreich, sich künstliche Beispielfunktionen anzusehen, die eine klare Struktur haben. Wir lernen einige wichtige Beispielfunktionen kennen und diskutieren auch evolutionäre Algorithmen im Kontext kombinatorischer Optimierung. Dabei dienen uns die konkreten Ergebnisse vor allem als Beispiele für erfolgreiche Anlysemethoden.
Wir betrachten auf der anderen Seite auch Fragen nach der Komplexität von Problemen. In diesem Zusammenhang besprechen wir das so genannte No-Free-Lunch-Theorem mit seinen Grenzen und Konsequenzen, außerdem beschäftigen wir uns mit Black-Box-Komplexität, einer für randomisierte Suchheuristiken angemessenen Komplexitätstheorie.
Hier gibt es vorlesungsbegleitend die Folien zum Download.