Ant colony optimization(ACO) : A Probabilistic Technique for finding Optimal Paths

Optimization problems are very important in the field of both scientific and industrial. Some real-life examples of these optimization problems are time table scheduling, nursing time distribution scheduling, train scheduling, capacity planning, traveling salesman problems, vehicle routing problems, Group-shop scheduling problem, portfolio optimization, etc. Many optimizations algorithms are developed for this reason. Ant colony optimization is one of them. Ant colony optimization is a probabilistic technique for finding optimal paths. In computer science and researches, the ant colony optimization algorithm is used for solving different computational problems.

Ant colony optimization(ACO) was first introduced by Marco Dorigo in the 90s in his Ph.D. thesis. This algorithm is introduced based on the foraging behavior of an ant for seeking a path between their colony and source food. Initially, it was used to solve the well-known traveling salesman problem. Later, it is used for solving different hard optimization problems.

Ants are social insects. They live in colonies. The behavior of the ants is controlled by the goal of searching for food. While searching, ants roaming around their colonies. An ant repeatedly hops from one place to another to find the food. While moving, it deposits an organic compound called pheromone on the ground. Ants communicate with each other via pheromone trails. When an ant finds some amount of food it carries as much as it can carry. When returning it deposits pheromone on the paths based on the quantity and quality of the food. Ant can smell pheromone. So, other ants can smell that and follow that path. The higher the pheromone level has a higher probability of choosing that path and the more ants follow the path, the amount of pheromone will also increase on that path.

Let’s see an example of this. Let consider there are two paths to reach the food from the colony. At first, there is no pheromone on the ground. So, the probability of choosing these two paths is equal that means 50%. Let consider two ants choose two different paths to reach the food as the probability of choosing these paths is fifty-fifty.

The distances of these two paths are different. Ant following the shorter path will reach the food earlier than the other.

After finding food, it carries some food with itself and returns to the colony. When it tracking the returning path it deposits pheromone on the ground. The ant following the shorter path will reach the colony earlier.

When the third ant wants to go out for searching food it will follow the path having shorter distance based on the pheromone level on the ground. As a shorter path has more pheromones than the longer, the third ant will follow the path having more pheromones.

By the time the ant following the longer path returned to the colony, more ants already have followed the path with more pheromones level. Then when another ant tries to reach the destination(food) from the colony it will find that each path has the same pheromone level. So, it randomly chooses one. Let consider it choose the above one(in the picture located below)

Repeating this process again and again, after some time, the shorter path has a more pheromone level than others and has a higher probability to follow the path, and all ants next time will follow the shorter path.

For solving different problems with ACO, there are three different proposed version of Ant-System:

Ant Density & Ant Quantity: Pheromone is updated in each movement of an ant from one location to another.

Ant Cycle: Pheromone is updated after all ants completed their tour.

Let see the pseudocode for applying the ant colony optimization algorithm. An artificial ant is made for finding the optimal solution. In the first step of solving a problem, each ant generates a solution. In the second step, paths found by different ants are compared. And in the third step, paths value or pheromone is updated.

procedure ACO_MetaHeuristic is
    while not_termination do
        generateSolutions()
        daemonActions()
        pheromoneUpdate()
    repeat
end procedure

There are many optimization problems where you can use ACO for finding the optimal solution. Some of them are:

1. Capacitated vehicle routing problem
2. Stochastic vehicle routing problem (SVRP)
3. Vehicle routing problem with pick-up and delivery (VRPPD)
4. Group-shop scheduling problem (GSP)
5. Nursing time distribution scheduling problem
6. Permutation flow shop problem (PFSP)
7. Frequency assignment problem
8. Redundancy allocation problem
9. Traveling salesman problem(TSP)

Let see the mathematical terms of ACO(typically for a TSP problem).

Pheromone update

Source: Wikipedia

The left side on the equation indicates the amount of pheromone on the given edge x,y

ρ — the rate of pheromone evaporation

And the last term on the right side indicated the amount of pheromone deposited.

Source: Wikipedia

Where L is the cost of an ant tour length and Q is a constant.

Anurag Rana Educator CSE/IT