PhD in Dortmund in Ingo Wegener's group, now in Berkeley with the ICSI

AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

Ant colony optimization is inspired by the foraging behavior of natural ants. Ants deposit pheromone trails on the ground that attract other ants. This simple communication mechanism results in swarm intelligence phenomena that can solve complex tasks in nature such as finding short paths to food sources. Ant-inspired algorithms form a powerful optimization paradigm with many successful applications to problems such as the TSP, network routing, and scheduling problems. I will present analyses for the running time of ant algorithms for shortest path problems. This is joint work with Christian Horoba and it extends previous work by Attiratanasunthron and Fakcharoenphol. For the single-destination shortest path problem we obtain an almost tight upper bound. This bound transfers to the all-pairs shortest path problem where different types of ants search for different destinations. A simple interaction mechanism between different types of ants leads to a significant speed-up. Interestingly, this speed-up is achieved by sending ants to intermediate destinations chosen uniformly at random.

Benjamin Doerr

--email hidden

passcode not visible

logged in users only

I told the speaker that the typical attendee has no background in ant colony optimization and he promised that the talk will reflect this.