Bacterial Foraging Optimization Algorithm

BFOA.py

# Bacterial Foraging Optimization Algorithm
# (c) Copyright 2013 Max Nanis [max@maxnanis.com].

import os, random, math, csv

class BFOA():

  def __init__(self, pop_size = 100, problem_size = 2, dimension = [-1, 1], elim_disp_steps = 1, repro_steps = 4, chem_steps = 30):
    self.step_index = 0
    self.run_id = os.urandom(6).encode('hex')

    # problem configuration
    self.problem_size = problem_size
    self.dimension = [-1, 1]
    self.search_space = [self.dimension for x in range(self.problem_size)]
    # algorithm configuration
    self.pop_size = pop_size
    self.step_size = 0.1 # Ci

    self.elim_disp_steps = 1 # Ned, number of elimination-dispersal steps
    self.repro_steps = repro_steps # Nre, number of reproduction steps

    self.chem_steps = chem_steps # Nc, number of chemotaxis steps
    self.swim_length = 3 # Ns, number of swim steps for a given cell
    self.p_eliminate = 0.25 # Ped

    self.d_attr = 0.1 # attraction coefficients
    self.w_attr = 0.2
    self.h_rep = self.d_attr # repulsion coefficients
    self.w_rep = 10

    # Generage the new randomly positioned population
    self.cells = [{'vector' : self.random_vector(self.search_space)} for x in range(self.pop_size)]


  def objective_function(self, vector):
    return sum(x**2.0 for x in vector)


  def random_vector(self, minmax):
    return [random.uniform(x[0], x[1]) for x in minmax]


  def generate_random_direction(self):
    return self.random_vector([self.dimension for x in range(self.problem_size)])


  def compute_cell_interaction(self, cell, d, w):
    '''
      Compare the current cell to the other cells for attract or repel forces
    '''
    sum = 0.0

    for other_cell in self.cells:
      diff = 0.0
      for idx, i in enumerate( cell['vector'] ):
        diff += (cell['vector'][idx] - other_cell['vector'][idx])**2.0

      sum += d * math.exp(w * diff)
    return sum


  def attract_repel(self, cell):
    '''
      Compute the competing forces
    '''
    attract = self.compute_cell_interaction(cell, -self.d_attr, -self.w_attr)
    repel = self.compute_cell_interaction(cell, self.h_rep, -self.w_rep)
    return attract + repel


  def evaluate(self, cell):
    cell['cost'] = self.objective_function( cell['vector'] )
    cell['inter'] = self.attract_repel(cell)
    cell['fitness'] = cell['cost'] + cell['inter']
    return cell


  def tumble_cell(self, cell):
    step = self.generate_random_direction()

    vector = [None] * len(self.search_space)
    for idx, i in enumerate(vector):

      # For this dimension, move in that direction by the step distance from
      # where the cell currently is
      vector[idx] = cell['vector'][idx] + self.step_size * step[idx]

      # If the step takes you beyond the enviroment bounds, stay on the edge
      if vector[idx] < self.search_space[idx][0]: vector[idx] = self.search_space[idx][0]
      if vector[idx] > self.search_space[idx][1]: vector[idx] = self.search_space[idx][1]

    return {'vector' : vector}


  def save(self):
      # Write cell position to file
      with open('bfoa_'+ self.run_id +'.csv', 'a+eb') as csvfile:
        writer = csv.writer(csvfile, delimiter=',')
        writer.writerow(["step_index", "x", "y", "cost", "inter", "fitness", "sum_nutrients"])

        for cell in self.cells:
          arr = [self.step_index, cell['vector'][0], cell['vector'][1], cell['cost'], cell['inter'], cell['fitness'], cell['sum_nutrients'] ]
          writer.writerow(arr)


  def chemotaxis(self):
    '''
      Best returns a cell instance
    '''
    best = None

    # chemotaxis steps
    for j in range(self.chem_steps):
      moved_cells = []

      # Iterate over each of the cells in the population
      for cell_idx, cell in enumerate(self.cells):

        sum_nutrients = 0.0
        # Determine J of current cell position
        cell = self.evaluate(cell)

        # If the first time, or if this movement gave the cell a lower energy
        if best is None or cell['cost'] < best['cost']: best = cell
        sum_nutrients += cell['fitness']

        # The cell will swim or tumble some every time interval
        for m in range(self.swim_length):

          # Move the cell to a new location
          new_cell = self.tumble_cell(cell)
          # Determine J of the moved to cell position
          new_cell = self.evaluate(new_cell)

          # If the newly positioned cell (from the last run) has the lowest J, track it
          if cell['cost'] < best['cost']: best = cell
          # If the newly positioned cell is worse off than before, try again
          if new_cell['fitness'] > cell['fitness']: break

          # If the new cell is better off, save it
          # and log the total amount of food it's consumed
          cell = new_cell
          sum_nutrients += cell['fitness']

        cell['sum_nutrients'] = sum_nutrients
        moved_cells.append( cell )

      print "  >> chemo=#{0}, f={1}, cost={2}".format(j, best['fitness'], best['cost'] )
      self.cells = moved_cells
      # Also capture these steps
      self.save()
      self.step_index += 1

    return best


  def search(self):
    '''
      Algorithm iterates over a new random population
    '''
    best = None

    # Elimination-dispersal: cells are discarded and new random samples are inserted with a low probability
    for l in range(self.elim_disp_steps):

      # Reproduction: cells that performed well over their lifetime may contribute to the next generation
      for k in range(self.repro_steps):

        # Chemotaxis: cost of cells is derated by the proximity to other cells and cells move along the manipulated cost surface one at a time
        # returns a single cell
        c_best = self.chemotaxis()

        # If the first time, or if this reproduction step gave a lower energy cell
        if best is None or c_best['cost'] < best['cost']: best = c_best
        print " > best fitness={0}, cost={1}".format( best['fitness'], best['cost'] )

        # 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.
        self.cells = sorted(self.cells, key=lambda k: k['sum_nutrients'])
        lowest_cost_cells = self.cells[:self.pop_size/2]
        self.cells =  lowest_cost_cells + lowest_cost_cells

        # Also capture these steps
        self.save()
        self.step_index += 1


      # Elimination-dispersal over each cell
      for cell in self.cells:
        if random.random() <= self.p_eliminate: cell['vector'] = self.random_vector(self.search_space)


      self.save()
      self.step_index += 1


    print "best :: ", best
    return best


if __name__ == "__main__":
  try:
    abspath = os.path.abspath(__file__)
    dname = os.path.dirname(abspath)
    base_path = os.path.join(dname, 'bfoa_results')
    os.chdir(base_path)
  except RuntimeError:
    print "A 'results' folder must be created in the project directory"

  bfoa = BFOA(pop_size = 600, elim_disp_steps = 3, repro_steps = 4, chem_steps = 40, )
  best = bfoa.search()