What is Ant Colony Optimization and how does it help?
Deep dive into mechanics and applications of Ant Colony Optimization
Ant colony optimization algorithm is a probabilistic technique for finding optimal paths of different computational problems. Initially, it was used to solve the well-known traveling salesman problem. Later, it is used for solving different hard optimization problems. Ant colony optimization is based on the technique known as Swarm Intelligence, which is a sub-field of Artificial Intelligence.
Brief about Swarm Intelligence
Swarm intelligence is a relatively new approach to problem-solving that takes inspiration from the collective behavior of elements in decentralized and self-organized systems comprised of relatively simple agents interacting locally with one another and with the environment, much like the natural swarms actually do.
The behavior of social insects has been studied due to their efficiency of solving complex problems such as finding the shortest path between their nest and food source or organizing their nests. In spite of the fact that these insects are unsophisticated individually, they make wonders as a swarm by interaction with each other and their environment. They communicate and coordinate themselves with a chemical language and specialized enzymes and receptors.
Behavioral Pattern of Ants
Ant colony optimization (ACO) was first introduced by Marco Dorigo in the 90s in his Ph.D. thesis. As the name suggests, this algorithm is based on the foraging behavior of an ant for seeking a path between their colony and source food.
Ants contain an organic compound called pheromone and they release it on the ground while moving from their colony, in search of food.
When an ant finds some amount of food it carries as much as it can carry and while returning back to the colony it deposits pheromone on the paths based on the quantity and quality of the food. Other ants can smell this and follow the path. The higher the pheromone level, the higher probability of other ants choosing that path and following it. Since each ant will release pheromone, its amount increases gradually.
As seen in the above image, there are two ways for the ants to procure their food. The shortest way to the food is determined by pheromone levels on ground.
At first, there is no pheromone on the ground. Consider two ants leave the colony at once and there are two routes to the food. Therefore, there’s a 50% probability of ants choosing each route. The distance between the two routes is different. So, the ant on the shorter route reaches the food faster as compared to the other ant on the longer route. As discussed earlier, after finding food, the ant carries some food with itself while depositing pheromone on the ground while returning back to the colony. The ant following the shorter route will reach the colony earlier.
When the third ant wants to go out for searching food it will follow the route having shorter distance based on the pheromone level on the ground since it has more pheromones than the longer. The third ant will also deposit some amount of pheromone on the ground and this cycle continue.
By the time the ant following the longer route returned to the colony, 3 or maybe 4 ants already have followed the shorter route as it has more pheromones level. Since the number of ants depositing pheromones on the shorter route increases, more and more ants follow the shorter route.
ACO Algorithm:
Generate m random ants.
An ant k (where k = 1 2, ..., m) represents a solution string with a selected value for each variable.
k is evaluated according to an objective function.
Pheromone concentration associated with each possible route is changed in a way to reinforce good solutions as follows:
ACO Pseudo Code:
Begin;
Initialize the pheromone trails and parameters;
Generate population of m solutions (ants);
For each individual ant k € m: calculate fitness (k);
For each ant determine its best position;
Determine the best global ant;
Update the pheromone trail;
Check if termination = true;
End;
Pheromone Concentration Calculations:
Once the pheromone is updated after an iteration, the next iteration starts by changing the ants' paths (i.e. associated variable values) in a manner that respects pheromone concentration and also some heuristic prefer-ence. As such, an ant k at iteration t will change the value for each variable according to the following probability:
where Pij(k, t) = probability that option I, is chosen by ant k
for variable i at iteration 1; T (r) = pheromone concentration
associated with option I at iteration 1; Mi= heuristic factor for preferring among available options and is an indicator of how good it is for ant k to select option I (this heuristic factor is generated by some problem characteristics and its value is fixed for each option (y); and o and are exponent parameters that control the relative importance of pheromone concentration versus the heuristic factor.
Applications of ACO:
Scheduling problems.
Vehicle routing problem.
Assignment problem.
Set problem.
Travelling salesman problem.
NP-Hard combinational problems.
Data mining.
Connectionless networking routing, etc.
References:
Credits:
We at Vevesta Labs are maintaining this library of articles and we welcome article requests. Please mail us at info@vevesta.com
Vevesta: Your Machine Learning Team’s Collective Wiki: Identify and use relevant machine learning projects, features and techniques
For more such stories, follow us on twitter at @vevesta_labs
100 early birds who login to Vevesta get free subscription for 3 months.