Bacterial Foraging Optimization Algorithm #

Name #

Bacterial Foraging Optimization Algorithm (BFOA), Bacterial Foraging Optimization, BFO

Taxonomy #

Bacterial Foraging Optimization Algorithm is a biologically inspired optimization technique that belongs to the field of Swarm Intelligence, which is a subfield of Computational Intelligence. It is closely related to other swarm-based algorithms such as Particle Swarm Optimization (PSO) and Ant Colony Optimization (ACO).

• Computational Intelligence
  • Swarm Intelligence
    • Particle Swarm Optimization (PSO)
    • Ant Colony Optimization (ACO)
    • Bacterial Foraging Optimization Algorithm (BFOA)

Strategy #

The Bacterial Foraging Optimization Algorithm mimics the foraging behavior of bacteria, particularly the species Escherichia coli (E. coli). The algorithm simulates the four principal mechanisms observed in real bacterial foraging: chemotaxis, swarming, reproduction, and elimination-dispersal.

Chemotaxis #

In the chemotaxis phase, bacteria move in the search space by taking small steps in random directions. If the fitness at the new location is better, the bacterium continues moving in that direction; otherwise, it tumbles and moves in a different random direction. This process simulates the movement of bacteria towards nutrients and away from noxious substances.

Swarming #

During the swarming phase, bacteria communicate with each other by releasing attractants and repellents. This cell-to-cell signaling mechanism causes the bacteria to swarm together, which is modeled in the algorithm by a fitness function that considers the relative distances of bacteria from each other.

Reproduction #

After a certain number of chemotactic steps, the reproduction phase takes place. Healthier bacteria (those with better fitness values) split into two, while less healthy bacteria die. This keeps the population size constant.

Elimination-Dispersal #

In the elimination-dispersal phase, bacteria in a region are either eliminated or dispersed into a new part of the search space. This is done with a low probability and helps to prevent the algorithm from being trapped in local optima.

Procedure #

Data Structures #

• Bacterium: Represents a candidate solution in the search space.
• Population: Collection of bacteria.

Parameters #

• p: Dimension of the search space
• S: Total number of bacteria in the population
• N_c: Number of chemotactic steps
• N_s: Swimming length
• N_re: Number of reproduction steps
• N_ed: Number of elimination-dispersal events
• P_ed: Elimination-dispersal probability
• C(i): Step size taken in random direction for bacterium i

Steps #

1. Initialize the population of S bacteria randomly in the search space.
2. For each elimination-dispersal step l = 1 to N_ed:
   1. For each reproduction step k = 1 to N_re:
      1. For each chemotactic step j = 1 to N_c:
         1. For each bacterium i = 1 to S:
            1. Compute the fitness function for bacterium i.
            2. Let J_last = J(i, j, k, l) to save this value.
            3. Tumble: Generate a random vector Delta(i) in [-1, 1].
            4. Move: J(i, j+1, k, l) = J(i, j, k, l) + C(i) * Delta(i) / sqrt(Delta(i)' * Delta(i)).
            5. Compute the fitness function for bacterium i at the new location.
            6. Swim:
               1. Let m = 0 (counter for swim length).
               2. While m < N_s:
                  1. Let m = m + 1.
                  2. If J(i, j+1, k, l) < J_last, let J_last = J(i, j+1, k, l) and move bacterium i using the same formula as in the Tumble step.
                  3. Else, m = N_s (end the while loop).
         2. Compute the health of each bacterium as the sum of its fitness over the chemotactic lifetime.
      2. Reproduction:
         1. Sort bacteria in ascending order of their health.
         2. Eliminate the S_r = S/2 least healthy bacteria.
         3. Duplicate the S_r healthiest bacteria.
   2. If l < N_ed, go to step 3 for the next elimination-dispersal event.
3. Elimination-Dispersal: For i = 1 to S, with probability P_ed, eliminate and disperse each bacterium to a random location in the search space.
4. If a termination condition is met, stop; otherwise, go to step 2.

Considerations #

Advantages #

• Suitable for optimization problems with noisy and dynamic environments.
• Capable of escaping local optima due to the elimination-dispersal mechanism.
• Efficient in exploring the search space because of the chemotaxis and swarming behaviors.

Disadvantages #

• Requires tuning of several parameters, which can be time-consuming.
• May converge slowly for high-dimensional problems.
• The reproduction step may lead to premature convergence if not balanced with exploration.

Heuristics #

Parameter Selection #

• The population size S should be chosen based on the complexity of the problem. Larger populations are needed for more complex problems.
• The chemotactic step size C(i) should be adaptive, decreasing with each generation to balance exploration and exploitation.
• The number of chemotactic steps N_c should be large enough to allow bacteria to explore the search space effectively.
• The swimming length N_s should be small to prevent bacteria from moving too far away from promising regions.
• The number of reproduction steps N_re and elimination-dispersal events N_ed should be chosen to balance the exploration and exploitation capabilities of the algorithm.

Initialization #

• Initialize bacteria randomly across the search space to ensure diversity in the initial population.
• If prior knowledge about the problem is available, use it to seed the initial population with potentially good solutions.

Termination Criteria #

• Terminate the algorithm when a maximum number of iterations or function evaluations is reached.
• Stop if the best fitness value has not improved for a specified number of iterations.
• Terminate if the population diversity falls below a threshold, indicating convergence.