Förderverein Technische Fakultät

Am 2. Feber fand der Vortrag von Prof. Mittermeir zum Thema “Zufallsgesteuerte Algorithmen – der Natur abgeschaut” statt. Folien zum Vortrag siehe unten.

Zusammenfassung:

In der Regel erwarten wir von einem Algorithmus, dass er möglichst rasch das richtige (oder optimale) Ergebnis liefert. Für eine Fülle von Problemen ist dies jedoch nur dann möglich, wenn der Problemumfang relativ klein ist. Es handelt sich dabei um sogenannte NP-harte und NP-vollständige Probleme.

Im Vortrag wollen wir anhand eines Rundreiseproblems (Travelling Salesman) die Problematik NP-harter Probleme zeigen und anschließend Heuristiken besprechen, die zwar die Optimalität der Lösung nicht garantieren können, von denen jedoch gezeigt werden kann, dass sie nach vergleichsweise kurzer Zeit zu einer Lösung in der Nähe des Optimums konvergieren.

Als Beispiel für von der Natur inspirierten Algorithmen werden ausgehend vom Verhalten biologischer Ameisen die Metaheuristiken Ant System und Ant Colony System entwickelt und diskutiert in welcher Weise „künstliche Ameisen“ von ihren natürlichen Vorbildern abweichen müssen, um auch für umfangreiche Problemstellungen sehr gute Ergebnisse zu liefern.