Skip to main content

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.

Image for post

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

Image for post

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.

Image for post

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.

Image for post

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)

Image for post

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.

Image for post

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

Image for post

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.

Image for post

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


Anurag Rana Educator CSE/IT

Comments

Popular posts from this blog

JAVA Scrollbar, MenuItem and Menu, PopupMenu

ava AWT Scrollbar The  object  of Scrollbar class is used to add horizontal and vertical scrollbar. Scrollbar is a  GUI  component allows us to see invisible number of rows and columns. AWT Scrollbar class declaration public   class  Scrollbar  extends  Component  implements  Adjustable, Accessible   Java AWT Scrollbar Example import  java.awt.*;   class  ScrollbarExample{   ScrollbarExample(){               Frame f=  new  Frame( "Scrollbar Example" );               Scrollbar s= new  Scrollbar();               s.setBounds( 100 , 100 ,  50 , 100 );               f.add(s);               f.setSize( 400 , 400 );               f.setLayout( null );               f.setVisible( true );   }   public   static   void  main(String args[]){           new  ScrollbarExample();   }   }   Output: Java AWT Scrollbar Example with AdjustmentListener import  java.awt.*;   import  java.awt.event.*;   class  ScrollbarExample{        ScrollbarExample(){               Frame f=  new  Frame( "Scro

Difference between net platform and dot net framework...

Difference between net platform and dot net framework... .net platform supports programming languages that are .net compatible. It is the platform using which we can build and develop the applications. .net framework is the engine inside the .net platform which actually compiles and produces the executable code. .net framework contains CLR(Common Language Runtime) and FCL(Framework Class Library) using which it produces the platform independent codes. What is the .NET Framework? The Microsoft .NET Framework is a platform for building, deploying, and running Web Services and applications. It provides a highly productive, standards-based, multi-language environment for integrating existing investments with next-generation applications and services as well as the agility to solve the challenges of deployment and operation of Internet-scale applications. The .NET Framework consists of three main parts: the common language runtime, a hierarchical set of unified class librari

Standard and Formatted Input / Output in C++

The C++ standard libraries provide an extensive set of input/output capabilities which we will see in subsequent chapters. This chapter will discuss very basic and most common I/O operations required for C++ programming. C++ I/O occurs in streams, which are sequences of bytes. If bytes flow from a device like a keyboard, a disk drive, or a network connection etc. to main memory, this is called   input operation   and if bytes flow from main memory to a device like a display screen, a printer, a disk drive, or a network connection, etc., this is called   output operation . Standard Input and Output in C++ is done through the use of  streams . Streams are generic places to send or receive data. In C++, I/O is done through classes and objects defined in the header file  <iostream> .  iostream  stands for standard input-output stream. This header file contains definitions to objects like  cin ,  cout , etc. /O Library Header Files There are following header files important to C++ pro