Last active
July 13, 2022 09:29
-
-
Save x0xMaximus/8626921 to your computer and use it in GitHub Desktop.
Bacterial Foraging Optimization Algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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() |
@ZER-0-NE
Unfortunately I can't use this code too!
How can I use this code for maximization problems? Can you suggest the places where I need to make changes?
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hey what is given as input to this optimization algorithm?