Stochastic Optimization: Ant Colony Optimization
What is Stochastic Optimization?
Stochastic optimization is the process of maximizing or minimizing the value of a mathematical or statistical function when one or more of the input parameters is subject to randomness. The word stochastic means involving chance or probability.
Stochastic optimization plays an important role in the analysis, design, and performance of modern systems. Stochastic optimization usually looks at problems from two perspectives: through the objective functions (cost functions) or through limitations.
The common example for stochastic optimization is the traveling salesman problem which states “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?”
We can solve this problem by using a stochastic optimization algorithm called ant colony optimization.
Ant Colony Optimization
Inspiration
This algorithm is inspired by the ant colonies, how ant travel from nest to the food source and then get back to their nest. Ants initially go out randomly to find the food source and each ant leaves a trail of pheromone on the ground and comes back with the food.
Consider an example here, let's suppose that two ants go out to search for food and reach the same food source using different paths.
One path is shorter than the other so ant following the shorter path will reach the food source first.
And it will get back to the nest first with the food source. Remember each ant leaves a trail of pheromones on the ground. So when the first ant reaches the nest with the food the other ants follow its pheromone trail to reach the food source.
By the time the ant following the longer path returned to the nest, more ants already had followed the path with higher pheromone levels.
And it also starts to follow the trail with higher pheromone levels, leaving the longer path.In this way all ants start to follow the shortest path.
And for some reason if ants face blockage in their path then they again follow the same approach. They start to move randomly until they find the pheromone trail again with the shortest path.
What is Ant Colony Optimization?
Ant colony optimization (ACO) is a population-based metaheuristic that can be used to find approximate solutions to difficult optimization problems.
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 (hereafter ants) incrementally build solutions by moving on the graph. The solution construction process is stochastic and 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 runtime by the ants.
Metaheuristic
Metaheuristic algorithms are algorithms which, in order to escape from local optima, drive some basic heuristic: either a constructive heuristic starting from a null solution and adding elements to build a good complete one, or a local search heuristic starting from a complete solution and iteratively modifying some of its elements in order to achieve a better one. The metaheuristic part permits the low-level heuristic to obtain solutions better than those it could have achieved alone, even if iterated.
How does ant colony optimization work?
Ant Colony optimization is a class of algorithms whose first member is called Ant System. The main idea is that of a parallel search over several computational constructive threads based on local problem data.
Consider the following graph with four nodes and initially the pheromone level is the same for each edge.
Ant is a simple computational agent you place on a node of a graph randomly
Each ant can visit each need only once. The probability of visiting a certain node is calculated by the following formula.
It is explained like this: pheromone level for the concerned edge into the heuristic value or cost for visiting that edge divided by the sum of pheromone level and heuristic value of other edges that can be visited. For the edges that cannot be visited its value is 0. where α and β are user-defined parameters (0 ≤ α,β ≤ 1) that control the relative importance of the pheromone versus the heuristic information ηij=1/dij where dij is the length of the visiting edge.
When all the ants have completed their tours then the pheromone level is calculated for all the edges and the heuristic values are also calculated. Pheromones are updated using
It is explained like this: sum of one 1 minus evaporation rate ρ of pheromone level into the current pheromone level and sum of pheromone level calculated by the other ants for that particular edge.
The pheromone level laid by particular ant on that specific edge is calculated by
Where L is the length of the total path traveled by k ant after the whole iteration.
This whole process is repeated until an optimal solution is found.
Ant Colony System
Major improvement in this was the ant colony system which instead of using probabilistic rule for visiting certain edge, pseudorandom proportional rule was used. In this a random variable is used which is uniformly distributed between 0 and 1. We calculate the probabilities in the same previous way but there is an extra step involved . We divide those probabilities between 0 and 1 and then generate a random number, ant will choose the path in which that number lies.
This rather greedy rule, which favors exploitation of the pheromone information, is counterbalanced by the introduction of a diversifying component: the local pheromone update. The local pheromone update is performed by all ants after each construction step. Each ant applies it only to the last edge traversed:
Where φ∈(0,1] is the pheromone decay coefficient, and τ0 is the initial value of the pheromone.
The main goal of the local update is to diversify the search performed by subsequent ants during one iteration. In fact, decreasing the pheromone concentration on the edges as they are traversed during one iteration encourages subsequent ants to choose other edges and hence to produce different solutions. This makes it less likely that several ants produce identical solutions during one iteration. Additionally, because of the local pheromone update in ACS, the minimum values of the pheromone are limited.
Let us know if you have already applied above mentioned optimization processes and how it helped you to solve your problem. We would also love to know if you are a newbie and this blog helped you in any way.