INTRODUCTION:
Bacteria Foraging Optimization Algorithm (BFOA), proposed by Kevin M.Passino, is a newcomer to the family of nature-inspired optimization algorithms. For over the last five decades, optimization algorithms like Genetic Algorithms (GA), Evolutionary Programming (EP), Evolutionary Strategies (ES), 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), Ant Colony Optimization (ACO) have found their way into this domain and proved their effectiveness. Following the same trend of swarm-based algorithms, Passino proposed the BFOA . 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. The 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 the chemotactic movement of virtual bacteria in the problem search space.
Since its inception, BFOA has drawn the attention of researchers from diverse fields of knowledge especially due to its biological motivation and graceful structure. Researchers are trying to hybridize BFOA with different other algorithms in order to explore its local and global search properties separately. It has already been applied to many real-world problems and proved its effectiveness over many variants of GA and PSO. Mathematical modeling, adaptation, and modification of the algorithm might be a major part of the research on BFOA in future
The foraging strategy is governed basically by four processes namely Chemotaxis, Swarming, Reproduction, Elimination, and Dispersal.
A) CHEMOTAXIS:
Some bacteria, such as E. coli, have several flagella per cell (4–10 typically). These can rotate in two ways:
1. Counter-clockwise rotation aligns the flagella into a single rotating bundle, causing the bacterium to swim in a straight line.
2. Clockwise rotation breaks the flagella bundle apart such that each flagellum points in a different direction, causing the bacterium to tumble in place. The directions of rotation are given for an observer outside the cell looking down the flagella toward the cell.
Behavior:-
The overall movement of a bacterium is the result of alternating tumble and swim phases. If one watches a bacterium swimming in a uniform environment, its movement will look like a random walk with relatively straight swims interrupted by random tumbles that reorient the bacterium. Bacteria such as E. coli are unable to choose the direction in which they swim, and are unable to swim in a straight line for more than a few seconds due to rotational diffusion. In other words, bacteria "forget" the direction in which they are going. By repeatedly evaluating their course, and adjusting if they are moving in the wrong direction, bacteria can direct their motion to find favorable locations with high concentrations of attractants (usually food) and avoid repellents (usually poisons).
In the presence of a chemical gradient, bacteria will chemotaxis, or direct their overall motion based on the gradient. If the bacterium senses that it is moving in the correct direction (toward attractant/away from repellent), it will keep swimming in a straight line for a longer time before tumbling. If it is moving in the wrong direction, it will tumble sooner and try a new direction at random. In other words, bacteria like E. coli use temporal sensing to decide whether their situation is improving or not. In this way, it finds the location with the highest concentration of attractant (usually the source) quite well. Even under very high concentrations, it can still distinguish very small differences in concentration. Fleeing from a repellent works with the same efficiency.
This biased random walk is a result of simply choosing between two methods of random movement; namely tumbling and straight swimming. In fact, chemotactic responses such as forgetting direction and choosing movements to resemble the decision-making abilities of higher life-forms with brains that process sensory data.
The helical nature of the individual flagella filament is critical for this movement to occur. As such, the protein that makes up the flagella filament, flagellant, is quite similar among all flagellated bacteria. Vertebrates seem to have taken advantage of this fact by possessing an immune receptor designed to recognize this conserved protein.
As in many instances in biology, there are bacteria that do not follow this rule. Many bacteria, such as Vibrio, are mono flagellated and have a single flagellum at one pole of the cell. Their method of chemotaxis is different. Others possess a single flagellum that is kept inside the cell wall. These bacteria move by spinning the whole cell, which is shaped like a corkscrew
B) SWARMING: An interesting group behavior has been observed for several motile species of bacteria including E.coli and S. Typhimurium, where intricate and stable spatiotemporal patterns (swarms) are formed in a semisolid nutrient medium. A group of E.coli cells arranges themselves in a traveling ring by moving up the nutrient gradient when placed amidst a semisolid matrix with a single nutrient chemo-effecter. The cells when stimulated by a high level of succinate, release an attractant aspartate, which helps them to aggregate into groups and thus move as concentric patterns of swarms with high bacterial density. Mathematically Swarming behavior can be modeled as:
Some bacteria, such as E. coli, have several flagella per cell (4–10 typically). These can rotate in two ways:
1. Counter-clockwise rotation aligns the flagella into a single rotating bundle, causing the bacterium to swim in a straight line.
2. Clockwise rotation breaks the flagella bundle apart such that each flagellum points in a different direction, causing the bacterium to tumble in place. The directions of rotation are given for an observer outside the cell looking down the flagella toward the cell.
Behavior:-
The overall movement of a bacterium is the result of alternating tumble and swim phases. If one watches a bacterium swimming in a uniform environment, its movement will look like a random walk with relatively straight swims interrupted by random tumbles that reorient the bacterium. Bacteria such as E. coli are unable to choose the direction in which they swim, and are unable to swim in a straight line for more than a few seconds due to rotational diffusion. In other words, bacteria "forget" the direction in which they are going. By repeatedly evaluating their course, and adjusting if they are moving in the wrong direction, bacteria can direct their motion to find favorable locations with high concentrations of attractants (usually food) and avoid repellents (usually poisons).
In the presence of a chemical gradient, bacteria will chemotaxis, or direct their overall motion based on the gradient. If the bacterium senses that it is moving in the correct direction (toward attractant/away from repellent), it will keep swimming in a straight line for a longer time before tumbling. If it is moving in the wrong direction, it will tumble sooner and try a new direction at random. In other words, bacteria like E. coli use temporal sensing to decide whether their situation is improving or not. In this way, it finds the location with the highest concentration of attractant (usually the source) quite well. Even under very high concentrations, it can still distinguish very small differences in concentration. Fleeing from a repellent works with the same efficiency.
This biased random walk is a result of simply choosing between two methods of random movement; namely tumbling and straight swimming. In fact, chemotactic responses such as forgetting direction and choosing movements to resemble the decision-making abilities of higher life-forms with brains that process sensory data.
The helical nature of the individual flagella filament is critical for this movement to occur. As such, the protein that makes up the flagella filament, flagellant, is quite similar among all flagellated bacteria. Vertebrates seem to have taken advantage of this fact by possessing an immune receptor designed to recognize this conserved protein.
As in many instances in biology, there are bacteria that do not follow this rule. Many bacteria, such as Vibrio, are mono flagellated and have a single flagellum at one pole of the cell. Their method of chemotaxis is different. Others possess a single flagellum that is kept inside the cell wall. These bacteria move by spinning the whole cell, which is shaped like a corkscrew
B) SWARMING: An interesting group behavior has been observed for several motile species of bacteria including E.coli and S. Typhimurium, where intricate and stable spatiotemporal patterns (swarms) are formed in a semisolid nutrient medium. A group of E.coli cells arranges themselves in a traveling ring by moving up the nutrient gradient when placed amidst a semisolid matrix with a single nutrient chemo-effecter. The cells when stimulated by a high level of succinate, release an attractant aspartate, which helps them to aggregate into groups and thus move as concentric patterns of swarms with high bacterial density. Mathematically Swarming behavior can be modeled as:
where Jcc (θ,P(j,k,l)) is the objective function value to be added to the actual objective function (to be minimized) to present a time-varying objective function, S is the total number of bacteria, p is the number of variables to be optimized, which are present in each bacterium and θ = [θ1,θ2,...,θp ]T is a point in the p-dimensional search domain. dattractant ,wattractant , hrepellant ,wrepellant are different coefficients that should be chosen properly
C) REPRODUCTION:
In this step, population members who have had sufficient nutrients will reproduce and the least healthy bacteria will die. The healthier half of the population replaces with the other half of bacteria which gets eliminated, owing to their poorer foraging abilities. This makes the population of bacteria constant in the evolution process.
D) ELIMINATION AND DISPERSAL:
Gradual or sudden changes in the local environment where a bacterium population lives may occur due to various reasons e.g. a significant local rise of temperature may kill a group of bacteria that are currently in a region with a high concentration of nutrient gradients. Events can take place in such a fashion that all the bacteria in a region are killed or a group is dispersed into a new location. To simulate this phenomenon in BFO Algorithm some bacteria are liquidated at random with a very small probability while the new replacements are randomly initialized over the search space.
No comments:
Post a Comment