| Title | Learning from Real Ants: Building Robust Ant Algorithms that always find the Shortest Path |
| Speaker | Dr. Jayadeva |
| Chair | Yuhui Shi |
Abstract
In the most basic application of Ant Colony Optimization (ACO), a set of artificial ants find the shortest path between a source and a destination. Ants deposit pheromone on paths they take, preferring paths that have more pheromone on them. Since shorter paths are traversed faster, more pheromone accumulates on them in a given time, attracting more ants and leading to reinforcement of the pheromone trail on shorter paths. This is a positive feedback process that can also cause trails to persist on longer paths, even when a shorter path becomes available. In fact, we show that beyond a threshold, initial bias on a longer path cannot be overcome, and ants will continue to trail a longer path even when a shorter one is found.
It is well known that obtaining high performance in ACO algorithms typically requires fine tuning several parameters that govern pheromone deposition and removal. We begin by revisiting known facts about biological ants, and motivate a new family of ant algorithms, termed as EigenAnt, that are based on selective pheromone removal that occurs only on the path that is actually chosen for each trip. This may happen, for example, by mechanical rubbing off by traiing ants. We show several parallels between biological ants and the modellled ones. The shortest path is the only stable equilibrium for EigenAnt, which means that it is maintained for arbitrary initial pheromone concentrations on paths, and even when path lengths change with time. The EigenAnt algorithm uses only two parameters and does not require them to be tuned. EigenAnt provides useful directions not only for developing artificial ant algorithms, but also for understanding how swarms can behave robustly despite diversity and environmental variation.
Biography
Prof. Jayadeva obtained his B.Tech and Ph.D degrees from the Department of Electrical Engineering, IIT Delhi in 1988 and 1993. He is currently a Professor in the same department. He has been a speaker on the IEEE Computer Society Distinguished Visitor Programme, and is a recipient of the Young Engineer Award from the Indian National Academy of Engineering, the Young Scientist Award from the Indian National Science Academy, and the BOYSCAST Fellowship from the Department of Science and Technology, Govt. of India. He was a URSI Young Scientist at the General Assembly in Lille, France (1996), and received the Sir J. C. Bose Young Scientist title from the Indian Council of the URSI. He visited the Department of Brain and Cognitive Sciences, Massachusetts Institute of Technology in 1997 as a BOYSCAST fellow. He spent a sabbatical year as a visiting Researcher at IBM India Research Laboratory, from July 2006. One of his papers in Neurocomputing was listed on the Top25 hotlist; he is a recipient of best paper awards from the IETE Journal of Research, and three other conference papers. He holds a US Patent on A/D conversion, another on assessing pronunciation abilities, and is the co-author of the book “Numerical Optimization and Applications”. He has served on the Steering and Program Committees of several international conferences. He was a keynote speaker at the International Workshop on Mobile Technologies for Pervasive Healthcare, Philip Island, Australia in 2007, was tutorial chair for PrEMI 2009, and delivered an invited talk at ICICS, Singapore, 2011. His research interests include Swarm Intelligence, Machine Learning, Optimization, and VLSI. Amongst his recent works that has received notable attention is the Twin Support Vector Machine.
