Bacterial Foraging Optimization Algorithm

The Bacterial Foraging Optimization Algorithm is inspired by the group foraging behavior of bacteria such as E.coli and M.xanthus. Specically, 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.

The following algorithm provides a pseudocode listing of the Bacterial Foraging Optimization Algorithm for minimizing a cost function.

The next algorithm 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:

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 Cell_s_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, Stepsize 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.

Given the loops in the algorithm, it can be congured 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.