Nature Inspired Optimization Algorithms : Ant Colony Optimization
This is the part 2 of the article series Nature Inspired Algorithms. Introductory article could be found at https://dindisn.medium.com/nature-inspired-optimization-algorithms-part-1-introduction-11dafcba07db
In 1992, ant colony optimization was initially introduced by Marco Diago and today with many variations, applied in diverse applications such as,
- production planning
- vehicle routing systems
- traffic control systems
- structural optimization
- scheduling in manufacturing systems
- sequential ordering problems
- facility location problems (optimal placement of facilities to minimize the transportation costs)
- portfolio optimization etc.
Even after this many years, it is considered as one of the most successful paradigm to design effective combinatorial optimization solutions.
Natural Behaviour of Ants
Being social creatures, ants live as groups in the colonies and depending on the species the number can go up to millions. Their cooperative behaviour enables them to survive in many difficult conditions. Amidst their complex behaviours, the way they forage is the base for the ant colony optimization.
When looking for food, worker ants first roam around until they find something edible. When they find a food source, it carries as much as possible back to the nest and on the way back deposit a substance called pheromone on the ground. The other ants could smell the pheromones and know if they follow this path they could find the food. These pheromones evaporate with time, so only the most recent trails taken would have higher concentration of this. As ants tend to take higher concentrated pheromone paths, after a certain period higher concentration of pheromones will be deposited in the shortest path.
For the simple illustrative purposes, let’s consider ants A- E and the possible paths x and y, x being the shorter path.
Ants A, B have found the food source at time t1 and from that location come back to the colony with food along paths x and y respectively.
By t6 A,C, E have taken the shorter path and as the time flaws with the combined impact of additional pheromones due to more ants and the pheromone decay over time, more dominant path will be the shorter path.
This amazing way of nature with positive reinforcement and gradual convergence to the optimised solution with a simple decision making process has been mimicked to solve many different combinatorial problems .
When converting to an algorithm two main concepts has been considered.
- Probability of choosing a path
- Evaporation rate of the pheromones
Say the probability of an ant choosing the path from nest i to food source j is Pij. It can be represented as
α, β > 0 are the influence parameters
φij is the pheromone concentration on the path i to j
dij is the desirability of the path i to j. In some cases d_ij ∝ 1 / lij where lij is the distance from path i to j.
α represents the attractiveness of the pheromone on that path and β represents the preference of the path.
Larger the α , ants will prefer the paths with more pheromone levels (increasing the exploitation) whereas larger the value of β, it will lead the search towards finding the best path (increasing the exploration) as this will lead the ants to shift the paths rather than following the same path as the initial ant. Tweaking these parameters and adding problem specific variants will deem robust algorithms which can be used in different domains of problems.