Evolutionäre Algorithmen

Im Modul Künstliche Intelligenz, 2. Semester Master Informatik

• Biologische Evolution, Evolutionstheorie, Genotyp, Phänotyp, Evolutionsfaktoren, Bedingungen der Evolutio
• Evolution als Optimierung und Suche, Lösungsraumsuche,
• Lösungsräume: Nachbarschaft, Fitnesslandschaft, Fitnessfunktion, lokale Suche, Optima
• Deterministische Optimierung: Koordinatenverfahren, Gradientenverfahren, Simplexverfahren
• Nicht-deterministische Optimierung: Monte-Carlo-Verfahren, Simulated Annealing, Toleranzschwelle, Sintflut-Algorithmus,Evolutionäre Algorithmen, Einordnung und Vergleich der Verfahren
• Evolutionäre Algorithmen (EA) GA, GP, ES, EP
• Annahme, Heuristik des GA, einfacher genetischer Algorithmus vs. steady state, Fitnesstypen, Selektionstypen, Mehrzieloptimierung mit paretobasierter Rangselektion
• Genetische Operatoren Crossover und Mutation, Anwendbarkeit und problemspezifische Zutaten
• Genetische Programmierung (GP): S-Expression, Crossover*, Mutation (2!*)
• Vehicle routing Problem: Permutationskodierung, PMX-Crossover
• Großer Anwendungsteil, viele praktische Übungen

Abschlussarbeiten

• Modellierung und Simulation biologischer Bewegungsapparate zur Veranschaulichung von Evolutionseffekten in einem künstlichen Ökosystem mit Unreal Engine, A.C. Fodi, Masterarbeit, 2022
• Konzeption und Umsetzung eines Neuroevolutionären Algorithmus zur Steuerung eines Fahrzeugs in Unity, M. Alesali, Masterarbeit, 2021
• Anwendung interaktiver evolutionärer Algorithmen zur Erzeugung von Schlagzeugrhythmen, M. Kaulmann, Masterarbeit, 2020
• Evolution regulärer Ausdrücke zur Segmentierung digitalisierter Keilschrifttafeln in 3D, B. Gumz, Masterarbeit, 2014
• Automatisierte Merkmalsextraktion und Klassifizierung von Vogelstimmen mittels genetischer Programmierung, J. Scheer, Masterarbeit, 2013
• Interaktive Evolution zur Assistenz bei der Einrichtungsplanung, S. Dreyer, Masterarbeit, 2012
• Genetische Programmierung zur Merkmalsdefinition bei der Klassifikation von Wertereihen, Johannes Scheer, Studienarbeit Master Informatik, 2012
• Benutzerschnittstellen für die interaktive Evolution, S. Dreyer, Studienarbeit Master Informatik, 2011
• Review und Versuch zu „Distilling Free-form Natural Laws from Experimental Data“, C. Freye, Hausarbeit im Mastermodul KI, 2009
• GeneFlower - Evolution sensomotorischer Kopplungen, S. Dreyer, Hausarbeit im Mastermodul KI, 2010
• Anpassung eines Active Appearance Model an ein menschliches Gesicht durch einen evolutionären Algorithmus, S. Moritz, Hausarbeit im Mastermodul KI, 2009
• Entwicklung einer Software zur optimierten Auslagerung in einem Medikamentenlager, R. Peschmann, Diplomarbeit, 2009
• Entwicklung einer Applikation zur Layoutoptimierung von Webseiten mit evolutionären Algorithmen und interaktiver Fitness, R. Fischer, Bachelorarbeit, FH Brandenburg, 2008
• Automatische Generierung von Bewegungsmustern für reale Roboter mit Evolutionären Algorithmen, M. Hüllein, Diplomarbeit, 2006
• Evolution einer 3D-Beschreibung aus Bildern mit Hilfe von Lindenmayer-Systemen (L-Systemen), J. Derer, Diplomarbeit, 2004
• Einsatz Evolutionärer Algorithmen zur Optimierung der Tourenplanung eines Wachschutzunternehmens, Tino Schonert, Diplomarbeit, 2003

KI-Projekte:

• WS 2009/2010: GeneFlower - Evolution sensomotorischer Kopplungen
• WS 2004/2005: Maschinelles Lernen am Laufroboter ELFE - KI-Projekt WS 2004/2005
• WS 2001/2002: Genetisches Programmieren von Spielstrategien
• WS 1999/2000: Genetisches Programmieren einfacher Roboterfähigkeiten (Paper und Vortrag)

Genetisches Programmieren

• Applet zum GP Schätzung einer unbekannten Funktion (function regression, ETH Zürich, local mirror)
  
  • Falls das Applet nicht läuft, hilft für Windows und Firefox die Anleitung
  • Testfunktionen für das GP-Applet (local)
• Sony AIBO: Autonomous Evolution of Gaits with the Sony Quadruped Robot.
  
• Lindenmayer Grammatiken
• Eureqa - Nutzerfreundliches GP-Tool mit Optimierung von Fehler und Komplexität (dazu Paper von Schmidt M., Lipson H. (2009) Distilling Free-Form Natural Laws from Experimental Data)

Genetische Algorithmen

• Berechenbare Fitness
  • Applet zu GA von Dr. M. Syrjakov
  • Evolution statischer Strukturen, Brandeis University (Massachusetts), WIE funktionert es (pdf 1.6MB, Hornby, Gregory. S. and Pollack, Jordan. B. (2001))
  • Konstruktionsunterstützung
    LEGO-CAD, Brandeis University (Massachusetts), JAVA-Client-Server-Applikation
  • Evolving 2D/3D Creatures, Brandeis University (Massachusetts)
  • Evolvable Hardware - GOLEM-Project an der Brandeis University (Massachusetts)
    
  • Framsticks - three-dimensional life simulation project (Win), Poznan University of Technology
    
  • Karl Sims Virtual Creatures (Moving Image Archive)
• Interaktive Fitness
  
  • Imogenes (Autor Harley Davis, Win), local mirror
  • Tron (Applet, Brandeis Uni)
  • Bugs (im CMU AI Repository, X11)

• Implizite Fitness
  • Genpool, DarwinPond (Win)
  • Aeon - Positive feedback loop of increasing complexity between two populations (JAVA-Applikation)
• Online-Vorlesung von D.E. Goldberg, auf Bild "Course Preview" klicken, Dauer ca. 50min (best/only viewed with IE)
  Goldberg ist der Begründer der fundamentalen "Building Block Hypothese" für GA - der Antwort auf die Frage: "Warum funktionieren GAs?"
• CMU Artificial Intelligence Repository
• GP-Quick - handlicher GP-Kernel in C++