Ant Colony Optimization(ACO)
Introduction
Ant colony optimization (ACO) is a population-based can be used to find approximate solutions to difficult optimization problems.An ant colony optimization is an algorithm for finding optimal path in the graph that is based on the behavior of ants searching for food.It is probabilistic technique.
An ant system was developed by Marco Dorigo (Iitaly) in his PhD thesis in 1992.after five year ant colony was developed by Gambardella Dorigo in 1997. This algorithm come under the category in swarm intelligence, it is a new approach to problem solving that takes inspiration from the social behaviour of insects and of other animals.
Under Evolutionary Computation, are the Swarm Intelligence Techniques which include Ant Colony Optimization.
What Actually It is?
In the natural, we know an ant having ability or capability to find their food form nest in best way and you may be surprised that some of the ants doesn’t have eyes, though they can communicate with other by using their smelling sense. Usually the ants has organs which disperse pheromone. Basically, there are 10 to 20 types of pheromones presents and all these different pheromones smell convey different massage and ant are familiar with it. When Ants are in search for food randomly in their colony, and upon finding food return to their colony while laying down pheromone trails. So, the only way is to communicate with other ants by releasing pheromone trails in their path. As pheromone trails is chemical evaporate over a time, Thus its attractive strength decreases. So, ant which will follow the longer route to travel down and come back again, the more time the pheromone trails have to evaporate. A short path, by comparison, gets followed over more frequently, and thus the pheromone density become higher on shorter paths than longer ones. Pheromone evaporation also has the advantage of avoiding the convergence to a locally optimal solution Thus path will be chosen by the ants which has the more pheromone level density. subsequently they find the optimal solution.
The overall result is that when one ant finds a good (i.e., short) path from the colony to a food source, other ants are more likely to follow that path, and positive feedback eventually leads to many ants following a single path.
Practical Scenerio:-
· An obstruction in the path.
· Let’s say that ant’s take 1 second to complete 2d distance.
If the pheromone remains there as it is for 1 secons, becomes ½ in next second , become 1/4th in next second and so on .
Then after 1 second, Upper path has pheromone of 100 ants, where as lower pheromone of 50 ants only (note other side ant has yet to reach).
The concentration in upper path will keep increasing.
After some seconds all ants will follow the upper path.
At last after some time pass all ant will follow the upper route .
Ant colony optimization algorithm
In ACO, a set of software agents called artificial ants search for good solutions to a given optimization problem. To apply ACO, the optimization problem is transformed into the problem of finding the best path on a weighted graph. The artificial ants incrementally build solutions by moving on the graph. The solution construction process is biased by a pheromone model, that is, a set of parameters associated with graph components (either nodes or edges) whose values are modified at run-time by the ants.
Here i represent nest and j represent the food. There ( Pij ^k ) define probability of movement ant k. these probability will be depends on two factor.
1)attractive coefficient ( η i j) with respect to time t,
2)Pheromone trial level density (ῑ i j ) with respect to time.
α is a parameter to control the influence of τ i,j
β is a parameter to control the influence of η i,j
Amount of pheromone is updated according to the equation
τi,j = (1 − ρ)τi,j + ∆τi,j
where τi,j is the amount of pheromone on a given edge i, j
ρ is the rate of pheromone evaporation ∆τi,j is the amount of pheromone deposited,
typically given by
∆τ k i,j = {1/Lk
if ant k travels on edge i, j 0 otherwise where Lk is the cost of the k th ant’s tour (typically length).
Applications:
- Travelling sales man problem
- Routing in telecommunication networks
- Vehicle routing problem
References:
Scholarpedia
wikipedia
youtube
slideshare