Wednesday, April 6, 2011

Learning From Ants


Jack Dikian
April 2011

Ants

We’ve all come across a line of ants seemingly marching to and from their nest and food. Some of us may have even owned an ant farm created between 2 panes of glass. Like all, besides the idea that we don’t want them in our house, we have probably also marveled at their ingenuity and keenness for social behavior in order to survive and thrive.


In fact one of the greatest advantages for ants is their social behaviour - working as a colony with specialized duties, they are more efficient than insects in getting necessary things done.


Communicating and Learning their way to food


Ants form and maintain a line to their food source by laying a trail of pheromone, i.e. a chemical to which other members of the same species are very sensitive. They deposit a certain amount of pheromone while walking, and each ant prefers to follow a direction rich in pheromone. This enables the ant colony to quickly find the shortest route. The first ants to return should normally be those on the shortest route, so this will be the first to be doubly marked by pheromone (once in each direction). Thus other ants will be more attracted to this route than to longer ones not yet doubly marked, which means it will become even more strongly marked with pheromone. Soon, therefore, nearly all the ants will choose this route. Here, ants are using the environment as a medium of communication.


Studying this uncanny skill has enabled researchers to create algorithms aimed to search optimal paths in graphs, and applied to applications such as rerouting traffic in busy communications network.


Us learning from ants

In computing research ant colony optimization algorithm (part of swarm intelligence methods) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. Graphs are mathematical structures used to model pair-wise relations between objects in a collection.

Whilst the first algorithm was aiming to search for an optimal path in a graph based on the behavior of ants, this idea has since diversified to help solve a wider class of numerical problems.

Application

The use of the ant colony optimization algorithms has produced near-optimal solutions to the travelling salesman problem.

The travelling salesman problem is one of the most intensively studied problems in computational mathematics – that is finding the shortest route visiting each member of a collection of locations and returning to the start. Even rewards are offered in various forums encouraging solutions to this problem. For example,

In February 2009, Robert Bosch (Oberlin College) created a 100,000-city instance of the travelling salesman problem that provides a representation of Leonardo da Vinci's Mona Lisa as a continuous-line drawing. An optimal solution to the 100,000-city Mona Lisa instance would set a new world record for the travelling salesman problem – and $1000 prize.

Because ant colony optimization algorithm can be run continuously and adapt to changes in real time, this gives them an advantage over simulated information annealing (which all users of the system are permitted to change the system) and genetic algorithms. Network routing, urban transportation systems and resource-constrained project scheduling are areas with an interest in this type of algorithms.

No comments:

Post a Comment