Zufallsgesteuerte Algorithmen – der Natur abgeschaut

MittermeirIn 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.

Posted in TEWI-Kolloquium | Tagged , , | Kommentare deaktiviert für Zufallsgesteuerte Algorithmen – der Natur abgeschaut
RSS
EMAIL