02-05-2014, 04:18 PM
Bacterial Foraging Optimization Algorithm: Theoretical Foundations, Analysis, and Applications
Bacterial Foraging Optimization.pdf (Size: 331.6 KB / Downloads: 43)
Abstract
Bacterial foraging optimization algorithm (BFOA) has been widely accepted as a global optimization
algorithm of current interest for distributed optimization and control. BFOA is inspired by the social foraging
behavior of Escherichia coli. BFOA has already drawn the attention of researchers because of its efficiency in
solving real-world optimization problems arising in several application domains. The underlying biology behind
the foraging strategy of E.coli is emulated in an extraordinary manner and used as a simple optimization
algorithm. This chapter starts with a lucid outline of the classical BFOA. It then analyses the dynamics of the
simulated chemotaxis step in BFOA with the help of a simple mathematical model. Taking a cue from the
analysis, it presents a new adaptive variant of BFOA, where the chemotactic step size is adjusted on the run
according to the current fitness of a virtual bacterium. Nest, an analysis of the dynamics of reproduction operator
in BFOA is also discussed. The chapter discusses the hybridization of BFOA with other optimization techniques
and also provides an account of most of the significant applications of BFOA until date.
Introduction
Bacteria Foraging Optimization Algorithm (BFOA), proposed by Passino [1], is a new comer to the
family of nature-inspired optimization algorithms. For over the last five decades, optimization
algorithms like Genetic Algorithms (GAs) [2], Evolutionary Programming (EP) [3], Evolutionary
Strategies (ES) [4], which draw their inspiration from evolution and natural genetics, have been
dominating the realm of optimization algorithms. Recently natural swarm inspired algorithms like
Particle Swarm Optimization (PSO) [5], Ant Colony Optimization (ACO) [6] have found their way
into this domain and proved their effectiveness. Following the same trend of swarm-based algorithms,
Passino proposed the BFOA in [1]. Application of group foraging strategy of a swarm of E.coli
bacteria in multi-optimal function optimization is the key idea of the new algorithm. Bacteria search
for nutrients in a manner to maximize energy obtained per unit time. Individual bacterium also
communicates with others by sending signals. A bacterium takes foraging decisions after considering
two previous factors. The process, in which a bacterium moves by taking small steps while searching
for nutrients, is called chemotaxis and key idea of BFOA is mimicking chemotactic movement of
virtual bacteria in the problem search space.
The Bacteria Foraging Optimization Algorithm
During foraging of the real bacteria, locomotion is achieved by a set of tensile flagella. Flagella help an
E.coli bacterium to tumble or swim, which are two basic operations performed by a bacterium at the
time of foraging [7, 8]. When they rotate the flagella in the clockwise direction, each flagellum pulls
on the cell. That results in the moving of flagella independently and finally the bacterium tumbles with
lesser number of tumbling whereas in a harmful place it tumbles frequently to find a nutrient gradient.
Moving the flagella in the counterclockwise direction helps the bacterium to swim at a very fast rate.
In the above-mentioned algorithm the bacteria undergoes chemotaxis, where they like to move towards
a nutrient gradient and avoid noxious environment. Generally the bacteria move for a longer distance
in a friendly environment. Figure 1 depicts how clockwise and counter clockwise movement of a
bacterium take place in a nutrient solution.
Analysis of the Chemotactic Dynamics in BFOA
Let us consider a single bacterium cell that undergoes chemotactic steps according to (1) over a single-
dimensional objective function space. Since each dimension in simulated chemotaxis is updated
independently of others and the only link between the dimensions of the problem space are introduced
via the objective functions, an analysis can be carried out on the single dimensional case, without loss
of generality. The bacterium lives in continuous time and at the t-th instant its position is given by
θ (t ) . Next we list a few simplifying assumptions that have been considered for the sake of gaining
mathematical insight.