Many interesting meta-heuristics have been bio-inspired. Some of them are:
- Ant colony Optimization
- Cuckoo Search
- Genetic Algorithm
Ant Colony Optimization
This technique has been adapted from the studies carried out on the behavior of ants. It was observed that foraging ants quickly traversed the shortest path from the anthill to the food source and back. This was initially proposed by Marco Dorigo in 1992 PhD thesis. See here to know more about his works.
Subsequently further studies on the ant behavior have led to this technique being adapted to address a wider range of problems. See here
The attempt here is to present the basics of the method in a simple manner.
Ant foraging behaviour
However if you imagine that this ant is not the first one and that some ants have already passed this point then the path chosen by this ant could be different. The path chosen will depend upon the number of ants that have passed before and more specifically the path chosen by those earlier ants. The reason is simple. Foraging ants do not want to get lost. Hence whenever they leave the nest and take a path they deposit a chemical called a pheromone and this chemical deposit helps them to return to the nest after they have foraged. This helps the foraging ants to return quickly and also help other ants to reach the food spot more efficiently.
So the probability that an ant will take a path when there is no pheromone trail is same as that for the other path. If there are two paths then the chances are 50-50. Shorter paths would have higher density of accumulation. Thus when the trail has a higher concentration of pheromone then the chance for taking the path is higher.
Ant Colony Optimization proposed by Dorigo and subsequently enhanced by many, have found uses in variety of the applications viz., travelling salesman, graph colouring, vehicle routing, network optimization, and job shop scheduling amongst many others.
Some challenges however have been faced using this meta-heuristic. Modifications have been suggested by many researchers to overcome these challenges. Different techniques, such having different strategies for different ants and acceleration methods of path search have been used to arrive at better performance.
Simple and very good
Thanks. simple and interesting read. A quick question based on the high level understanding. What if the first ant takes the long route, so in this case rest follows it as there would be more pheromone deposit, resulting not necessarily be the shortest route.
In the case of the ant, that is possibly true.
But in the case of systems, i am sure the enhancements to this model will allow the long/problem path to be overriden based on latest choice made.
Meaning, if i choose a long path, there can be manual override to allow choose a different path – less problematic path – therefore allowing future choices to be influenced by this override.