2010-12-16

Problem-solving Ants

Ants lead way to speedier computer networks : Nature News





A problem-solving tactic used by insects looks set to help engineers.

An analysis of how ants quickly find new routes in a changing maze reveals techniques that could be useful to systems engineers.


Problem-solving ants inspire next generation of algorithms - News and Events - University of Sydney


An ant colony is probably the last place you'd expect to find a maths whiz, but researchers from the University of Sydney have shown that the humble ant is not only capable of solving difficult mathematical problems, but is even able to do what few computer algorithms can - adapt the optimal solution to fit a changing problem.

These findings, published in the Journal of Experimental Biology, deepen our understanding of how even simple animals can overcome complex and dynamic problems in nature, and will help computer scientists develop even better software to solve logistical problems and maximise efficiency in many human industries.



The ants were able to find the shortest route from one end of the maze to the other in under an hour, then were able to adapt and find the second shortest route when obstacles were put in their path.


Ants lay trail to complex problem-solving › News in Science (ABC Science)


Towers of Hanoi

In the study, Argentine ants were collected in the grounds of University of Sydney were introduced to a specially designed maze modelled on the 'Towers of Hanoi' puzzle.

The puzzle, also called 'Towers of Brahma', consists of three rods and a number of different-sized discs which have to be moved from one rod to the next without placing a larger disc on top of a smaller one. In legend, Brahmin priests are working to solve such a puzzle comprising 64 discs. When the puzzle is complete, the legend says, the world will end.

The rules for solving the problem with the minimum number of steps is called an algorithm.

Lead author Chris Reid, a PhD candidate at the University of Sydney, says that the best known nature inspired algorithm of this type is 'ant colony optimisation'. This involves finding the optimal path based on the behaviour of foraging ants.
Because the pheromones that ants use to mark their pathways are volatile and gradually evaporate, over time the colony selects the shortest path so that the signal remains stronger for longer.

The researchers say that most nature-inspired algorithms take only superficial inspiration from nature, and little is known about how real biological systems solve difficult problems.


Ant colony optimization - Wikipedia, the free encyclopedia


In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs.

This algorithm is a member of ant colony algorithms family, in swarm intelligence methods, and it constitutes some metaheuristic optimizations. Initially proposed by Marco Dorigo in 1992 in his PhD thesis,[1][2] the first algorithm was aiming to search for an optimal path in a graph, based on the behavior of ants seeking a path between their colony and a source of food. The original idea has since diversified to solve a wider class of numerical problems, and as a result, several problems have emerged, drawing on various aspects of the behavior of ants.