mod5-ant colony optmi

• Optimization


  Maximization or Minimization of a function
• Optimization techniques are used in every sphere of life nowadays, knowingly or unknowingly
• Examples of optimization


  • Purchase some items from a market
  • Answering a Question paper
  • Scheduling a trip
  • Expenses in a private/public function
  • Constructing a house
  • All shortest path algorithms
• Steps involved in the process of optimization


  1. We have an objective in our view

  2. There are a certain number of constraints attached with it

  3. We move from solution to solution if an item satisfying our constraints (This is called the solution space)

  4. We rank the solutions with respect to a certain criteria and go for the best one
• Resources to be optimized


  Profit, quality, time, space, money, infrastructure available
• Constraints


  The resources which are always limited
• Decision variables


  The variables which form a part of the objective
• Optimization example


  1. Automobile company produces 3 types of vehicles

  2. Gets a profit of Rs.10,000 on a 4 wheeler, Rs.4000 on a three wheeler and Rs.2000 on a 2 wheeler

  3. Objective function is to maximize F(x, y, z) = 10,000x+4000y+2000z

  4. Constraint is 100x+60y+20z <= 4000 (man hours)
• Mathematical formulation of optimization


  Minimize or maximize a real valued function f(x) subject to constraints
• Solution space


  • Contains many feasible solutions (solutions which satisfy all the constraints)
• Classical optimization approaches


  • Direct Method (Exhaustive Search)
  • Gradient based Methods
• Direct Method (Exhaustive Search)


  1. Only objective function f(x) and constraint values are used to guide the search strategy

  2. These methods are generally slow, requiring many function evaluations for convergence

  3. Can be applied to many problems without much changes in the algorithm
• Direct Method example


  • Given x + y = 14, find the maximum area of a rectangle
• Gradient Method


  1. Frame the objective function A(x) = x(14-x)

  2. Find the derivative dA/dx and equate it to 0 to find the critical values

  3. The optimal values lie among these critical values
• General structure of an optimization problem


  • There are n decision variables represented as a vector x
  • The objective function is denoted by f(x)
• Some common difficulties faced in optimization
• Convex Optimization


  There can be only one optimal solution, which is globally optimal
• Non-Convex Optimization


  • May have multiple locally optimal points
  • Possibility of getting stuck in the local minimum without converging to the global minimum
• Difficulties in classical optimization
• Bio-Inspired Algorithms (BIAs)


  • Mimic the intelligent behaviours from biologic behaviour of animal, bird, fish and so on
  • Part of nature inspired algorithms
  • Motivated by challenges where conventional optimization techniques are not effective
• Main branches of BIAs


  • Evolutionary algorithms (EAs)
  • Swarm intelligence (SI)
• Swarm Intelligence


  • A "swarm" is a disorganized population of individuals that will cluster together although each individual moves in a random direction
  • The algorithm uses a number of agents (particles) that constitute a swarm moving around in the search space looking for the best solution
  • Each particle adjusts its movement according to its own experience as well as the moving experience of other particles
• Representation of a particle


  • Particle(k).x - Position of the kth particle
  • Particle(k).v - Velocity of the kth particle
  • Particle(k).pbest - Best solution found by the kth particle
  • Particle(k).cost - Value of the cost function at the location of the kth particle
• Particle Swarm Optimization (PSO)


  • Each particle keeps track of its coordinates in the problem space which are associated with the best solution it has achieved so far (pbest)
  • The best value is a global best and is called gbest
• Ant Colony Optimization (ACO)


  • Inspired by the behavior of ants seeking a path between their colony and a food source
  • Ants initially wander randomly, and upon finding food return to their colony while laying down pheromone trails
  • Other ants are likely to follow the trail, returning and reinforcing it if they find food
  • Pheromone evaporation avoids convergence to a locally optimal solution
  • The probability of selection of a path by following ants is based on the pheromone concentration and evaporation rate
• Pheromone Update in ACO


  1. All ants are placed at the source vertex (ant colony)

  2. Ants move from source to destination (food source) following a step

  3. Ants conduct their return trip and reinforce their chosen path based on the length of the paths and the evaporation rate of pheromone