Clever Algorithms: Nature-Inspired Programming Recipes

By Jason Brownlee PhD

Home | Read Online

This is the ad-supported version of the book. Buy it now if you like it.

Bacterial Foraging Optimization Algorithm

Bacterial Foraging Optimization Algorithm, BFOA, Bacterial Foraging Optimization, BFO.


The Bacterial Foraging Optimization Algorithm belongs to the field of Bacteria Optimization Algorithms and Swarm Optimization, and more broadly to the fields of Computational Intelligence and Metaheuristics. It is related to other Bacteria Optimization Algorithms such as the Bacteria Chemotaxis Algorithm [Muller2002], and other Swarm Intelligence algorithms such as Ant Colony Optimization and Particle Swarm Optimization. There have been many extensions of the approach that attempt to hybridize the algorithm with other Computational Intelligence algorithms and Metaheuristics such as Particle Swarm Optimization, Genetic Algorithm, and Tabu Search.


The Bacterial Foraging Optimization Algorithm is inspired by the group foraging behavior of bacteria such as E.coli and M.xanthus. Specifically, the BFOA is inspired by the chemotaxis behavior of bacteria that will perceive chemical gradients in the environment (such as nutrients) and move toward or away from specific signals.


Bacteria perceive the direction to food based on the gradients of chemicals in their environment. Similarly, bacteria secrete attracting and repelling chemicals into the environment and can perceive each other in a similar way. Using locomotion mechanisms (such as flagella) bacteria can move around in their environment, sometimes moving chaotically (tumbling and spinning), and other times moving in a directed manner that may be referred to as swimming. Bacterial cells are treated like agents in an environment, using their perception of food and other cells as motivation to move, and stochastic tumbling and swimming like movement to re-locate. Depending on the cell-cell interactions, cells may swarm a food source, and/or may aggressively repel or ignore each other.


The information processing strategy of the algorithm is to allow cells to stochastically and collectively swarm toward optima. This is achieved through a series of three processes on a population of simulated cells: 1) 'Chemotaxis' where the cost of cells is derated by the proximity to other cells and cells move along the manipulated cost surface one at a time (the majority of the work of the algorithm), 2) 'Reproduction' where only those cells that performed well over their lifetime may contribute to the next generation, and 3) 'Elimination-dispersal' where cells are discarded and new random samples are inserted with a low probability.


Algorithm (below) provides a pseudocode listing of the Bacterial Foraging Optimization Algorithm for minimizing a cost function. Algorithm (below) provides the pseudocode listing for the chemotaxis and swing behaviour of the BFOA algorithm. A bacteria cost is derated by its interaction with other cells. This interaction function ($g()$) is calculated as follows:

$g(cell_k) = \sum_{i=1}^S\bigg[-d_{attr}\times exp\bigg(-w_{attr}\times \sum_{m=1}^P (cell_m^k - other_m^i)^2 \bigg) \bigg] + \sum_{i=1}^S\bigg[h_{repel}\times exp\bigg(-w_{repel}\times \sum_{m=1}^P cell_m^k - other_m^i)^2 \bigg) \bigg]$

where $cell_k$ is a given cell, $d_{attr}$ and $w_{attr}$ are attraction coefficients, $h_{repel}$ and $w_{repel}$ are repulsion coefficients, $S$ is the number of cells in the population, $P$ is the number of dimensions on a given cells position vector.

The remaining parameters of the algorithm are as follows $Cells_{num}$ is the number of cells maintained in the population, $N_{ed}$ is the number of elimination-dispersal steps, $N_{re}$ is the number of reproduction steps, $N_{c}$ is the number of chemotaxis steps, $N_{s}$ is the number of swim steps for a given cell, $Step_{size}$ is a random direction vector with the same number of dimensions as the problem space, and each value $\in [-1,1]$, and $P_{ed}$ is the probability of a cell being subjected to elimination and dispersal.

Input: $Problem_{size}$, $Cells_{num}$, $N_{ed}$, $N_{re}$, $N_{c}$, $N_{s}$, $Step_{size}$, $d_{attract}$, $w_{attract}$, $h_{repellant}$, $w_{repellant}$, $P_{ed}$
Output: $Cell_{best}$
Population $\leftarrow$ InitializePopulation($Cells_{num}$, $Problem_{size}$)
For ($l=0$ To $N_{ed}$)
    For ($k=0$ To $N_{re}$)
        For ($j=0$ To $N_{c}$)
            ChemotaxisAndSwim(Population, $Problem_{size}$, $Cells_{num}$, $N_{s}$, $Step_{size}$, $d_{attract}$, $w_{attract}$, $h_{repellant}$, $w_{repellant}$)
            For (Cell $\in$ Population)
                If (Cost(Cell) $\leq$ Cost($Cell_{best}$))
                    $Cell_{best}$ $\leftarrow$ Cell
        Selected $\leftarrow$ SelectByCellHealth(Population, $\frac{Cells_{num}}{2}$)
        Population $\leftarrow$ Selected
        Population $\leftarrow$ Selected
    For (Cell $\in$ Population)
        If (Rand() $\leq$ $P_{ed}$)
            Cell $\leftarrow$ CreateCellAtRandomLocation()
Return ($Cell_{best}$)
Pseudocode for the BFOA.
Input: Population, $Problem_{size}$, $Cells_{num}$, $N_{s}$, $Step_{size}$, $d_{attract}$, $w_{attract}$, $h_{repellant}$, $w_{repellant}$
For (Cell $\in$ Population)
    $Cell_{fitness}$ $\leftarrow$ Cost(Cell) + Interaction(Cell, Population, $d_{attract}$, $w_{attract}$, $h_{repellant}$, $w_{repellant}$)
    $Cell_{health}$ $\leftarrow$ $Cell_{fitness}$
    $Cell'$ $\leftarrow$ $\emptyset$
    For ($i=0$ To $N_{s}$)
        RandomStepDirection $\leftarrow$ CreateStep($Problem_{size}$)
        $Cell'$ $\leftarrow$ TakeStep(RandomStepDirection, $Step_{size}$)
        ${Cell'}_{fitness}$ $\leftarrow$ Cost($Cell'$) + Interaction($Cell'$, Population, $d_{attract}$, $w_{attract}$, $h_{repellant}$, $w_{repellant}$)
        If (${Cell'}_{fitness}$ > $Cell_{fitness}$)
            $i \leftarrow$ $N_{s}$
            Cell $\leftarrow$ $Cell'$
            $Cell_{health}$ $\leftarrow$ $Cell_{health}$ + ${Cell'}_{fitness}$
Pseudocode for the ChemotaxisAndSwim function.


  • The algorithm was designed for application to continuous function optimization problem domains.
  • Given the loops in the algorithm, it can be configured numerous ways to elicit different search behavior. It is common to have a large number of chemotaxis iterations, and small numbers of the other iterations.
  • The default coefficients for swarming behavior (cell-cell interactions) are as follows $d_{attract}=0.1$, $w_{attract}=0.2$, $h_{repellant}=d_{attract}$, and $w_{repellant}=10$.
  • The step size is commonly a small fraction of the search space, such as 0.1.
  • During reproduction, typically half the population with a low health metric are discarded, and two copies of each member from the first (high-health) half of the population are retained.
  • The probability of elimination and dispersal ($p_{ed}$) is commonly set quite large, such as 0.25.

Code Listing

Listing (below) provides an example of the Bacterial Foraging Optimization Algorithm implemented in the Ruby Programming Language. The demonstration problem is an instance of a continuous function optimization that seeks $\min f(x)$ where $f=\sum_{i=1}^n x_{i}^2$, $-5.0\leq x_i \leq 5.0$ and $n=2$. The optimal solution for this basin function is $(v_0,\ldots,v_{n-1})=0.0$. The algorithm is an implementation based on the description on the seminal work [Passino2002]. The parameters for cell-cell interactions (attraction and repulsion) were taken from the paper, and the various loop parameters were taken from the 'Swarming Effects' example.

def objective_function(vector)
  return vector.inject(0.0) {|sum, x| sum +  (x ** 2.0)}

def random_vector(minmax)
  return do |i|
    minmax[i][0] + ((minmax[i][1] - minmax[i][0]) * rand())

def generate_random_direction(problem_size)
  bounds ={[-1.0,1.0]}
  return random_vector(bounds)

def compute_cell_interaction(cell, cells, d, w)
  sum = 0.0
  cells.each do |other|
    diff = 0.0
    cell[:vector].each_index do |i|
      diff += (cell[:vector][i] - other[:vector][i])**2.0
    sum += d * Math.exp(w * diff)
  return sum

def attract_repel(cell, cells, d_attr, w_attr, h_rep, w_rep)
  attract = compute_cell_interaction(cell, cells, -d_attr, -w_attr)
  repel = compute_cell_interaction(cell, cells, h_rep, -w_rep)
  return attract + repel

def evaluate(cell, cells, d_attr, w_attr, h_rep, w_rep)
  cell[:cost] = objective_function(cell[:vector])
  cell[:inter] = attract_repel(cell, cells, d_attr, w_attr, h_rep, w_rep)
  cell[:fitness] = cell[:cost] + cell[:inter]

def tumble_cell(search_space, cell, step_size)
  step = generate_random_direction(search_space.size)
  vector =
  vector.each_index do |i|
    vector[i] = cell[:vector][i] + step_size * step[i]
    vector[i] = search_space[i][0] if vector[i] < search_space[i][0]
    vector[i] = search_space[i][1] if vector[i] > search_space[i][1]
  return {:vector=>vector}

def chemotaxis(cells, search_space, chem_steps, swim_length, step_size,
    d_attr, w_attr, h_rep, w_rep)
  best = nil
  chem_steps.times do |j|
    moved_cells = []
    cells.each_with_index do |cell, i|
      sum_nutrients = 0.0
      evaluate(cell, cells, d_attr, w_attr, h_rep, w_rep)
      best = cell if best.nil? or cell[:cost] < best[:cost]
      sum_nutrients += cell[:fitness]
      swim_length.times do |m|
        new_cell = tumble_cell(search_space, cell, step_size)
        evaluate(new_cell, cells, d_attr, w_attr, h_rep, w_rep)
        best = cell if cell[:cost] < best[:cost]
        break if new_cell[:fitness] > cell[:fitness]
        cell = new_cell
        sum_nutrients += cell[:fitness]
      cell[:sum_nutrients] = sum_nutrients
      moved_cells << cell
    puts "  >> chemo=#{j}, f=#{best[:fitness]}, cost=#{best[:cost]}"
    cells = moved_cells
  return [best, cells]

def search(search_space, pop_size, elim_disp_steps, repro_steps,
    chem_steps, swim_length, step_size, d_attr, w_attr, h_rep, w_rep,
  cells = { {:vector=>random_vector(search_space)} }
  best = nil
  elim_disp_steps.times do |l|
    repro_steps.times do |k|
      c_best, cells = chemotaxis(cells, search_space, chem_steps,
        swim_length, step_size, d_attr, w_attr, h_rep, w_rep)
      best = c_best if best.nil? or c_best[:cost] < best[:cost]
      puts " > best fitness=#{best[:fitness]}, cost=#{best[:cost]}"
      cells.sort{|x,y| x[:sum_nutrients]<=>y[:sum_nutrients]}
      cells = cells.first(pop_size/2) + cells.first(pop_size/2)
    cells.each do |cell|
      if rand() <= p_eliminate
        cell[:vector] = random_vector(search_space)
  return best

if __FILE__ == $0
  # problem configuration
  problem_size = 2
  search_space = {|i| [-5, 5]}
  # algorithm configuration
  pop_size = 50
  step_size = 0.1 # Ci
  elim_disp_steps = 1 # Ned
  repro_steps = 4 # Nre
  chem_steps = 70 # Nc
  swim_length = 4 # Ns
  p_eliminate = 0.25 # Ped
  d_attr = 0.1
  w_attr = 0.2
  h_rep = d_attr
  w_rep = 10
  # execute the algorithm
  best = search(search_space, pop_size, elim_disp_steps, repro_steps,
    chem_steps, swim_length, step_size, d_attr, w_attr, h_rep, w_rep,
  puts "done! Solution: c=#{best[:cost]}, v=#{best[:vector].inspect}"
Bacterial Foraging Optimization Algorithm in Ruby
Download: bfoa.rb.


Primary Sources

Early work by Liu and Passino considered models of chemotaxis as optimization for both E.coli and M.xanthus which were applied to continuous function optimization [Liu2002]. This work was consolidated by Passino who presented the Bacterial Foraging Optimization Algorithm that included a detailed presentation of the algorithm, heuristics for configuration, and demonstration applications and behavior dynamics [Passino2002].

Learn More

A detailed summary of social foraging and the BFOA is provided in the book by Passino [Passino2005]. Passino provides a follow-up review of the background models of chemotaxis as optimization and describes the equations of the Bacterial Foraging Optimization Algorithm in detail in a Journal article [Passino2010]. Das et al. present the algorithm and its inspiration, and go on to provide an in depth analysis the dynamics of chemotaxis using simplified mathematical models [Das2009].


[Das2009] S. Das and A. Biswas and S. Dasgupta and A. Abraham, "Bacterial Foraging Optimization Algorithm: Theoretical Foundations, Analysis, and Applications", in Foundations of Computational Intelligence Volume 3: Global Optimization, pages 23–55, Springer, 2009.
[Liu2002] Y. Liu and K. M. Passino, "Biomimicry of Social Foraging Bacteria for Distributed Optimization: Models, Principles, and Emergent Behaviors", Journal of Optimization Theory and Applications, 2002.
[Muller2002] S. D. Müller and J. Marchetto and S. Airaghi and P. Koumoutsakos, "Optimization Based on Bacterial Chemotaxis", IEEE Transactions on Evolutionary Computation, 2002.
[Passino2002] K. M. Passino, "Biomimicry of bacterial foraging for distributed optimization and control", IEEE Control Systems Magazine, 2002.
[Passino2005] K. M. Passino, "Part V: Foraging", in Biomimicry for Optimization, Control, and Automation, Springer, 2005.
[Passino2010] K. M. Passino, "Bacterial Foraging Optimization", International Journal of Swarm Intelligence Research, 2010.
Clever Algorithms: Nature-Inspired Programming Recipes

Free Course

Get one algorithm per week...
  • ...delivered to your inbox
  • ...described in detail
  • read at your own pace
Sign-up Now

Own A Copy

This 438-page ebook has...
  • ...45 algorithm descriptions
  • practice usage
  • ...pseudo code
  • ...Ruby code
  • ...primary sources
Buy Now

Please Note: This content was automatically generated from the book content and may contain minor differences.

Clever Algorithms: Nature-Inspired Programming Recipes

Do you like Clever Algorithms?
Buy the book now.

© Copyright 2015. All Rights Reserved. | About | Contact | Privacy