Ant Colony Optimization

This Optimization is a metaheuristic inspired via the foraging ant colonies' behavior. The procedure is imitated in ant colony optimization through the employ of a set of easy agents that is artificial ants which were assigned with computational resources and also they exploit stigmergic communication that is a form of indirect communication mediated via the environment, to determine the solution to the problem on hand. In computational environment, ants construct the solution upon the basis of graphical illustration of the problem and several partial solutions are achieved whenever ants visit several node. Ants visit from one node to another upon the basis of pheromone trail and heuristic information termed as visibility. Mathematically, the node transition rule can be explained as:

Here, y^k_ij is the probability of ant k to traverse from node i to j. τ_ij is the trail laid on edge (i, j) and η_ij is the visibility from node i to j. A particular data structure termed as "tabu" ensures about the coverage of all the nodes in tour of ants and prevents also them to revisit ant node. The pheromone trial laid via ants has also the property to evaporate like the time passes, described as:

                            τ_ij(t) = (1 - ρ) τ_ij + _Dτ_ij.........................................Eq(10)

Here, τ_ij is the pheromone trial and

ρ is the trail evaporation rate and

Δτ_ij can be evaluated as:

In above equation, Q is the objective function value and I_k is the length of the tour performed by ant k, here K is the whole number of ants. The basic configuration of ant colony optimization is described in following figure.

Initialize

Represent the underlying problem by a weighted connected graph. Set initial pheromone for each edge.

 Repeat

 For each ant do

Randomly select a starting node.

Repeat

Move to the next node as per to node transition rules.

Until a complete tour is fulfilled.

For each edge do

Update the pheromone intensity using pheromone-updating rules.

Until the stopping criterion is satisfied.

Output the global best result

                                               Program: Step-wise Procedure of Ant Colony Optimization