Bacterial Foraging Optimization Algorithm (BFOA): Inspired from Social foraging behavior of Escherichia coli

1. Introduction                                     

         Bacterial Foraging Optimization Algorithm (BFOA), proposed by Passino (2002), is a new comer to the family of nature-inspired optimization algorithms. Natural selection tends to eliminate animals with poor “foraging strategies” (methods for locating, handling, and ingesting food) and favor the propagation of genes of those animals that have successful foraging strategies since they are more likely to enjoy reproductive success (they obtain enough food to enable them to reproduce) [1]. After many generations, poor foraging strategies are either eliminated or shaped into good ones (redesigned). Logically, such evolutionary principles have led scientists in the field of “foraging theory” to hypothesize that it is appropriate to model the activity of foraging as an optimization process: A foraging animal takes actions to maximize the energy obtained per unit time spent foraging, in the face of constraints presented by its own physiology (e.g., sensing and cognitive capabilities) and environment (e.g., density of prey, risks from predators, physical characteristics of the search area) [2]. Evolution has balanced these constraints and essentially “engineered” what is sometimes referred to as an “optimal foraging policy” (such terminology is especially justified in cases where the models and policies have been ecologically validated). Optimization models are also valid for “social foraging” where groups of animals cooperatively forage [3]. 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 [4].

2. E.coli Bacteria Structure

Locomotion is achieved via a set of relatively rigid flagella that enable the bacterium to swim via each of them rotating in the same direction at about 100-200 revolutions per second (in control systems terms, we think of the flagellum as providing for actuation). Each flagellum is a left-handed helix configured so that as the base of the flagellum (i.e., where it is connected to the cell) rotates counterclockwise, as viewed from the free end of the flagellum looking toward the cell, it produces a force against the bacterium so it pushes the cell [5]. An E. coli bacterium can move in two different ways; If the flagella rotate clockwise, each flagellum pulls on the cell, and the net effect is that each flagellum operates relatively independently of the others, and so the bacterium “tumbles” about (i.e., the bacterium does not have a set direction of movement and there is little displacement See Fig.2) [6]. If the flagella move counterclockwise, their effects accumulate by forming a bundle (it is thought that the bundle is formed due to viscous drag of the medium), and hence they essentially make a composite propeller and push the bacterium so that it runs (swims) in one direction (see Fig.2 ) [7].

3. Bacterial Foraging Optimization Algorithm (BFOA)

     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 [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 [9]. 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 [10].                                                                                                  

        When they get food in sufficient, they are increased in length and in presence of suitable temperature they break in the middle to from an exact replica of itself. This phenomenon inspired Passino to introduce an event of reproduction in BFOA. Due to the occurrence of sudden environmental changes or attack, the chemotactic progress may be destroyed and a group of bacteria may move to some other places or some other may be introduced in the swarm of concern. This constitutes the event of elimination-dispersal in the real bacterial population, where all the bacteria in a region are killed or a group is dispersed into a new part of the environment.

3.1. Steps for BFOA

• Initialize parameter
• Chemotaxis
• Swarming
• Reproduction
• Elimination and Disporsal

3.1.1. Initialize parameter

      Bacteria could form intricate stable spatio-temporal patterns in certain semisolid nutrient substances and they can survive through a medium if placed together initially at its center [11]. Moreover, under certain conditions, they will secrete cell-to-cell attractant signals so that they will group and protect each other [12].

3.1.2. Chemotaxis

      The characteristics of movement of bacteria in search of food can be defined in two ways, i.e. swimming and tumbling together knows as chemotaxis [13]. A bacterium is said to be ‘swimming’ if it moves in a predefined direction, and ‘tumbling’ if moving in an altogether different direction [14].

3.1.3. Swarming

      For the bacteria to reach at the richest food location, it is desired that the optimum bacterium till a point of time in the search period should try to attract other bacteria so that together they converge at the desired location more rapidly [15]. To achieve this, a penalty function based upon the relative distances of each bacterium from the fittest bacterium till that search duration, is added to the original cost function. Finally, when all the bacteria have merged into the solution point, this penalty function becomes zero. The effect of swarming is to make the bacteria congregate into groups and move as concentric patterns with high bacterial density [16].

3.1.4. Reproduction

       The original set of bacteria, after getting evolved through several chemotactic stages reaches the reproduction stage. Here, best set of bacteria gets divided into two groups. The healthier half 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 [17].

3.1.5. Elimination and Dispersal

       In the evolution process, a sudden unforeseen event can occur, which may drastically alter the smooth process of evolution and cause the elimination of the set of bacteria and/or disperse them to a new environment [18]. Most ironically, instead of disturbing the usual chemotactic growth of the set of bacteria, this unknown event may place a newer set of bacteria nearer to the food location. From a broad perspective, elimination, and dispersal are parts of the population level long distance motile behavior. In its application to optimization, it helps in reducing the behavior of stagnation often seen in such parallel search algorithms [19].

3.2. Flowchart of BFOA

4. Numerical Expression for BFOA

     In order to test the validity of the proposed bacteria foraging algorithm, the results of four constrained optimization problems have been considered [20].

5. Applications of BFOA

• Wavelet based Neural Network(WNN)
• Dynamical resource allocation
• Independent Component Analysis(ICA)
• Neuro Fuzzy structure
• Simultaneous localization and Mapping problem
• Job shop scheduling

6. Advantages of BFOA

• Strong parallel search ability and easy to get out of local minimum.
• The convergence speed is slow and the computation is large.
• Routine methodology well developed Rapid response to changes, including pollution, Ease of sampling [21].
• Improved efficiency.
• Lack of dust.
• Optimal formulation diets.
• Use of home grown cereds no pelleting saving of cost.

Reference

 [1] LIU, X. and ZHAO, K. (2013). Bacteria foraging optimization algorithm based on immune algorithm. Journal of Computer Applications, 32(3), pp.634-637.

[2] Ali, E. and Abd-Elazim, S. (2011). Bacteria foraging optimization algorithm based load frequency controller for interconnected power system. International Journal of Electrical Power & Energy Systems, 33(3), pp.633-638.

[3] Kim, D., Abraham, A. and Cho, J. (2007). A hybrid genetic algorithm and bacterial foraging approach for global optimization. Information Sciences, 177(18), pp.3918-3937.

[4] Sathish Kumar, K. and Jayabarathi, T. (2012). Power system reconfiguration and loss minimization for an distribution systems using bacterial foraging optimization algorithm. International Journal of Electrical Power & Energy Systems, 36(1), pp.13-17.

[5] Emre, Y., Altun, O. and Osman, A. (2015). Computational Chemotaxis in Micro Bacterial Foraging Optimization for High Dimensional Problems: A Comparative Study on Numerical Benchmark. International Journal of Computer Applications, 124(4), pp.1-8.

[6] Das, S., Dasgupta, S., Biswas, A., Abraham, A. and Konar, A. (2009). On Stability of the Chemotactic Dynamics in Bacterial-Foraging Optimization Algorithm. IEEE Transactions on Systems, Man, and Cybernetics – Part A: Systems and Humans, 39(3), pp.670-679.

[7] Self-adaptive Bacterial Foraging Optimization Algorithm Based On Evolution Strategies. (2016). Revista Tecnica De La Facultad De Ingenieria Universidad Del Zulia.

[8] Devi, S. and Geethanjali, M. (2014). Application of Modified Bacterial Foraging Optimization algorithm for optimal placement and sizing of Distributed Generation. Expert Systems with Applications, 41(6), pp.2772-2781.

[9] Devabalaji, K., Ravi, K. and Kothari, D. (2015). Optimal location and sizing of capacitor placement in radial distribution system using Bacterial Foraging Optimization Algorithm. International Journal of Electrical Power & Energy Systems, 71, pp.383-390.

[10] Li, L. and Mai, X. (2013). Bacterial Foraging Algorithm Based on Quantum-Behaved Particle Swarm Optimization for Global Optimization. Advanced Materials Research, 655-657, pp.948-954.

[11] Liu, Y. and Passino, K. (2002). Biomimicry of Social Foraging Bacteria for Distributed Optimization: Models, Principles, and Emergent Behaviors. Journal of Optimization Theory and Applications, 115(3), pp.603-628.

[12] Abd-Elazim, S. and Ali, E. (2012). Power System Stability Enhancement via Bacteria Foraging Optimization Algorithm. Arabian Journal for Science and Engineering, 38(3), pp.599-611.

[13] Hota, P., Barisal, A. and Chakrabarti, R. (2010). Economic emission load dispatch through fuzzy based bacterial foraging algorithm. International Journal of Electrical Power & Energy Systems, 32(7), pp.794-803.

[14] Tripathy, M. and Mishra, S. (2007). Bacteria Foraging-Based Solution to Optimize Both Real Power Loss and Voltage Stability Limit. IEEE Transactions on Power Systems, 22(1), pp.240-248.

[15] Devabalaji, K. and Ravi, K. (2016). Optimal size and siting of multiple DG and DSTATCOM in radial distribution system using Bacterial Foraging Optimization Algorithm. Ain Shams Engineering Journal, 7(3), pp.959-971.

[16] Farhat, I. and El-Hawary, M. (2010). Dynamic adaptive bacterial foraging algorithm for optimum economic dispatch with valve-point effects and wind power. IET Generation, Transmission & Distribution, 4(9), p.989.

[17] Sathya, P. and Kayalvizhi, R. (2011). Optimal multilevel thresholding using bacterial foraging algorithm. Expert Systems with Applications, 38(12), pp.15549-15564.

[18] LIU, X. and ZHAO, K. (2013). Bacteria foraging optimization algorithm based on immune algorithm. Journal of Computer Applications, 32(3), pp.634-637.

[19] Nanda, J., Mishra, S. and Saikia, L. (2009). Maiden Application of Bacterial Foraging-Based Optimization Technique in Multiarea Automatic Generation Control. IEEE Transactions on Power Systems, 24(2), pp.602-609.

[20] Ali, E. and Abd-Elazim, S. (2012). TCSC damping controller design based on bacteria foraging optimization algorithm for a multimachine power system. International Journal of Electrical Power & Energy Systems, 37(1), pp.23-30.

[21] Abd-Elazim, S. and Ali, E. (2012). Bacteria Foraging Optimization Algorithm based SVC damping controller design for power system stability enhancement. International Journal of Electrical Power & Energy Systems, 43(1), pp.933-940.