ANT COLONY OPTIMIZATION

Abstract

By using Ant Colony Optimization (ACO) and swarm intelligence the best/optimal/shortest path can be found for solving computational problems. There are many methods to solve computational problems, but taking the optimal and shortest method is very helpful and consumes less time. The shortest-path algorithm calculates the shortest path from a start node to each node of a connected graph. Marco Dorigo in his ph. D introduced ant colony optimization (ACO) in 1992. Ant-colony optimization is one of the probabilistic techniques for finding optimal paths. Ants are tiny insects which live in colonies. Ants roam around their colonies in search of food and deposit an organic substance called pheromone (a chemical substance i.e., carriers of information between individuals within the species) on the ground. Other ants reach their destination with the smell of pheromones, however the strength of pheromone will reduce due to the process of evaporation. Most ants follow the path of greater pheromone levels. When ants take different paths to reach a destination, the pheromone level will be higher on the shortest path. Depending on the rate of evaporation and the frequency with which the ants pass there, the path, initially chosen at random, starts to be known as the best path to food. The pheromone imprint grows stronger over time and cannot be overcome by the evaporation event.The applications of ant colony optimization are used to examine potential paths on the graphs in order to solve graph problems.

Code Description & Execution for Ant Colony Optimization

Algorithm Description:

There are three main phases :

Phase 1 : The calculation of probability of each route

The above formula is used to calculate the pheromone between the two nodes. The result of this equation will inform the probability that a particular route analysed will have to be chosen.

Phase 2: Choosing the route based on probability results.

To choose the route roulette mechanism is used as it generates random routes. But the results of the probability calculations obtained in phase one are not ignored.

The above formula is used to add the cumulative sum of each visit made by an ant to the available routes. Here the delta ‘Δ’ is used to know the amount of pheromone released by an ant between ‘i’ and ‘j’ points. ‘lk’ is the amount of pheromone that should be deposited. The above formula will suffer loss due to evaporation

The higher the pheromone the lower the route being chosen again so to generate the inverse effect the alpha exponent used in the pheromone process was defined as negative. After calculating the probabilities, the values are informed to the random choice system.