Bacterial Foraging Optimization: Review

Bacterial Foraging Optimization: Review

Ms. Kiran, Ph.D Scholar Banasthali Vidyapith,Rajasthan,India Dr. Sunita Choudary, Banasthali Vidyapith,Rajasthan,India Ms. Sunita, A.P. SBMN, Rohtak India

Abstract Graph Coloring is a very active field of research to many practical applications as well as theoretical challenges. Bacterial Foraging Optimization Algorithms is an Artificial Intelligence technique that can be used to find appropriate solution to extremely difficult or impossible numeric maximization or minimization problem. BFOA is a probabilistic technique that models the food seeking & reproductive behavior of bacteria such as E-coli. BFO has been successfully applied in many areas and give the better results as compared to PSO and GA. Our main aim is to apply BFO for Graph Coloring Problem.

Keywords: Bacterial Foraging Optimization, Graph Coloring and Swarm Based Optimization.

1. 1. The Graph Coloring Problem

      \The Graph Coloring Problem (GCP) is a very famous problem which deals with the

      minimum number required to color the vertices in such a way that no two adjoining vertices of same color will stay together.

      GCP is a well known NP hard problem besides that it appears in various applications such as register allocation and time table examination scheduling.

      Fig. Example of colored graph

      Graph Coloring Problem uses some version to solve a problem. These versions are

      Vertex Coloring, Edge Coloring, Face Coloring and Total Coloring.

      Vertex Coloring is the main initiating point and other coloring problems can be transformed into a vertex version. Vertex coloring is an assignment of colors to each vertex of a graph such that no two adjacent vertexes will be of same color or there should be no edge between the two same colored vertices.

      Edge Coloring assigns a color to each edge so that no two adjacent edges share the same color. An edge coloring of a graph is a proper coloring of the edges meaning an assignment of colors to edges so that no vertex is incident to two edges of the same color. An edge coloring of a graph is just a vertex coloring of its line graph.

      Face Coloring assigns a color to each face or region so that no two faces that share a boundary have the same color or we can say that face coloring is just a vertex coloring of its planes.

      Total Coloring is a type of coloring on the vertices & edges of a graph when used without any qualification. A total coloring is always assumed to be proper in the sense that no two adjacent vertices, no adjacent edges & no edge & its vertices are assigned the same color.

      Our main focus is vertex coloring. The most common type of vertex coloring seeks to minimize the number of colors for a given graph. This type of coloring is known as a minimum vertex coloring, and the minimum number of colors by which the vertices of a graph G may be colored is called the chromatic number, denoted by (G). A vertex coloring of a graph with k colors is known as a k-coloring. A graph having a k-coloring (and therefore chromatic number) is called as a k-colorable graph, while a graph having chromatic number (G) = k is said to be a k-chromatic graph. That number for a given graph (G) is known as the Chromatic Number ( (G)) [10].

   2. Application

      Graph coloring problem has many applications in both technical as well as in real life. Some of the applications are

      • Scheduling

In the cleanest form, a given set of jobs need to be assigned to time slots, each job requires one such slot. Jobs can be scheduled in any order, but pairs of jobs may be in conflict in the sense that they may not be assigned to the same time slot, for

example because they both rely on a shared resource.

• Register Allocation

  A compiler is a computer program that translates one computer language into another. To improve the execution time of the resulting code, one of the techniques of compiler optimization is register allocation, where the most frequently used values of the compiled program are kept in the fast processor registers. Ideally, values are assigned to registers so that they can all reside in the registers when they are used.

• Frequency Assignment

A number of mobile radio transmitters have to be assigned a frequency such that two transmitters that are close to each other are assigned different frequencies and a minimum number of frequencies are used.

Some other applications are pattern matching, recreational puzzle Sudoku etc.

1. Bio Inspired Algorithm (Biologically Inspired algorithm) means inspiration from biology that lead to several successful algorithmic approaches also it is a category of algorithms that imitate the way nature performs. Many problems can be solved using Bio inspired without rigorous mathematical approach. Evolutionary algorithm, Swarm based & Ecology algorithm fall in this category and these algorithms have found numerous applications for problem solving.

   1. Swarm-Based Optimization

      Swarm intelligence is based on nature- inspired behavior and is successfully applied to optimization problems in a variety of fields. The goal of optimization is to find the optimum in the smallest possible amount of iterations, where optimum means the best from all possibilities chosen from a particular point of view.

      Swarm-based intelligence is artificial intelligence technique based on the study of collective behavior in self-organizing systems. Swarm-based systems are usually composed from population of individual, which takes effect between each other and

      environment. Individual could communicate directly or through impacting in surroundings. Although this systems do not have any central control of the individual behavior, interaction between individuals and simple behavior between them usually lead to detection of aggregate behavior, which is typical for whole colony. This could by observe by ants, bees, birds or bacteria in the nature. By inspiration of these colonies were develop algorithms called Swarm-based intelligence and are successfully apply for solving complicate optimization problems [11].

   2. Bacterial Foraging Optimization

      BFOA is an AI technique that can be used to find approximate solution to extremely difficult or impossible numeric maximization or minimization problem. BFO is a probabilistic technique that models the food-seeking & reproductive behavior of common bacteria such as E-coli in order to solve numeric optimization problem where there is no effective deterministic approach. BFO was introduced by Kevin M. Passino in 2000 for distributed optimization problems [16]. Bacterial Foraging Optimization (BFO) algorithm is a novel evolutionary computation algorithm proposed based on

      the foraging behavior of Escherichia coli (E. coli) bacteria living in human intestine [15]. The BFO algorithm is a biologically inspired computing technique which is based on mimicking the foraging behavior of E. coli bacteria. Natural selection tends to remove animals with poor foraging strategies and favors the circulation of genes of those animals that have successful foraging strategies, since they are more likely to enjoy reproductive success. After many generations, poor foraging strategies are either removed or shaped into good ones. This activity of foraging is used in optimization process.

      BFO is a Meta heuristic means that it is just a conceptual framework that can be used to design specific algorithm. There are many algorihm which are used for optimization of various problems & these are replaced by swarm inspired algorithm. BFO is the latest among them and is widely accepted as global optimization technique due to its ease of implementation

2. 1. Musa M. Hindi and Roman V. Yampolskiy (2012) proposed a paper about graph coloring problem using Genetic Algorithm. In this paper GA utilize more than one parent selection

      and mutation methods depending on the state of fitness of its best solution. The algorithm is tested against the standard DIMACS benchmark tests while limiting the number of usable colors to the known chromatic numbers. The proposed algorithm succeeded at solving the sample data set and even outperformed a recent approach in terms of the minimum number of colors needed to color some of the graphs [10].

   2. Sambarta Dasgupta, Arjit Biswas, Swagatam Das & Ajith Abraham (2012) presented an application of an adaptive version of the BFOA to the task of automatic circle detection from gray images. The objective is to performed the classical BFOA & GA in terms of final accuracy & computational speed over all the test image. [15].

   3. Morteza Dastkhosh Nikoo, Ahmad Faraahi, Seyyed Mohsen Hashemi, Seyyed Hossein Erfani4 (2012) proposed a model to summarize the text, by using the bacterial foraging optimization algorithm. This model works based on scoring the words and sentences. Each component which is a bacteria attempts to summarize the text and improves its position each time. Summary Process of the bacteria,

      continues while the value of bacteria converging to the threshold value. Limitation of this model is that this model cannot be used for summarizing documents in other languages [14].

   4. S. Subramanian and S. Padma (2011) the selection behavior of bacteria tends to remove reduced foraging strategies and recover successful foraging strategies. BFO is used to minimizing cost and improves the efficiency simultaneously by using a multi objective based Bacterial foraging algorithm [8].

   5. Sastry V.R.S Gollapudi, Shyam (2009) Proposed a new approach by hybridizing BFO technique with PSO named as IBFO to calculate resonant Frequency of RMA Result shows promising improvement in the accuracy while achieving drastic reduction in computational time. This navel technique will be useful to solve many engineering [13].

   6. Jing Dang, Anthony Brabazon, Michael ONeill, and David Edition (2008) have proposed a paper about Bacterial Foraging Optimization (BFO) algorithm. This is a biologically inspired computation technique which is based on mimicking the foraging behavior of

      Escherichia Coli bacteria. During the lifetime of E.coli bacteria, they undergo different stages such as chemotaxis, reproduction and elimination-dispersal. BFO algorithm was implemented various real world problems. Kim suggested that the BFO could be applied to find solutions for difficult engineering design problems [15].

   7. Fatma Mohammed Jabber,Kha Wla HusseinAli,and Kareem Radhi Hassan (2006) proposed a paper for solving Graph Coloring Problem. Ants of the artificial colony are able to generate successively shorter feasible tours by using information accumulated in the form of pheromone trail deposited of the edge of the colonies ant. Computer simulations demonstrate that the artificial ant colony is capable of generating good solutions [7].

3. Graph coloring is still a very active field of research, because it enjoys many practical applications as well as theoretical challenges. The main aim of GCP is to reduce the number of the colors that are used to color the graph. BFO is easy to implement and there are few parameters to adjust. Therefore, BFO has

   been successfully applied in many areas and give the better results as compared to PSO and GA. Our main aim is to apply BFO for Graph Coloring Problem.

4. • Analysis

     • Studying the various existing optimization techniques for solving Graph Coloring Problem.

     • Studying the various problems where BFOA have been applied.

   • Design

     • Proposing an algorithm to solve the graph coloring problem using BFOA.

   • Verification

     • Verifying the new results with the help of simulation.

The bacterial swarm proceeds through four principal mechanisms namely chemotaxis, swarming, reproduction, and elimination- dispersal [5], defined as below.

Chemo taxis simulates the movement of an E.coli cell through swimming and tumbling via flagella.

Swarming is an interesting group behavior 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.

Reproduction is process where least healthy bacteria eventually die while each of the healthier bacteria (those yielding higher value of fitness function) asexually split into two bacteria, which are placed in the same location. This keeps the swarm size constant.

Elimination and Dispersal is process in which gradual or sudden changes in the

no

yes

yes

start Initialization

Evaluation

Evaluation

Moving Tumble/swim

Moving Tumble/swim

Elimination

Elimination

End NofoLife

End of Eli.?

End of Eli.?

End of Rep.

End of Life

yes

no

no

no no

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.

1. Conclusion: end

   The main aim of GCP is to reduce the number of the colors that are used to color the graph. BFO is easy to implement and there are few parameters to adjust. This technique will be useful to solve many engineering and scientific applications. In this paper we are proposing an BFO algorithm to solve graph coloring problem.

1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Rondald. L. Introduction to Algorithms, Pages 962-963, 1994.

2. Dorigo, M & Di Caro, G, The Ant Colony Optimization Meta- Heuristic, UK, McGraw-Hill. 1999.

3. Binitha S Siva Sathya, A Survey of Bio inspired Optimization Algorithms, International Journal of Soft Computing and Engineering ISSN: 2231-2307,Volume-2,Issue- 2,May 2012.

4. Narendhar. S and Amudha. A Hybrid Bacterial Foraging Algorithm for Solving Job Shop Scheduling Problems, International Journal of Programming Languages and Applications Vol.2, No.4, October 2012.

5. Kevin M. Passino. Biomimicry of bacterial foraging for distributed Optimization and control, IEEE Control Systems Magazine, 22(3):52-67, 2002.

6. Kevin M. Passino, Bacterial Foraging optimization, International Journal of Swarm Intelligence Research, pp. 1-16, Jan-Mar 2010.

7. Fatma Mohammed Jabber, Kha Wla

   Hussein Ali, Kareem Radhi Hassan, Ant Colony Optimization for Graph Coloring Problem, Basrah Journal of Science (A), Vol.24 (2), 38-47, 2006.

8. S. Subramanian and S. Padma, Bacterial Foraging Algorithm Based Multi Objective Optimal Design of single phase Transformer, Journal of Computer Science And Engineering, Vol. 6, Issue 2, 2011.

9. Ehsan Salari & Kourosh Eshghi, An ACO Algorithm for the Graph Coloring Problem, International Journal Contemp. Math Sciences, Vol.3, No.6, 293-304, 2008.

10. Musa M. Hindi and Roman V. Yampolskiy, Genetic Algorithm Applied to the Graph Coloring Problem, Twenty-third Midwest Artificial Intelligence and Cognitive Science Conference, 2012.

11. Sambarta Dasgupta, Arjit Biswas, Swagatam Das & Ajith Abraham Automatic Circle Detection on Images with a Adaptive Bacterial Foraging Algorithm, Soft

    Computing, Vol. 14, Issue 11, No

    1151-1164, 2012.

12. Sastry V.R.S Gollapudi, Shyam, Intelligent Bacterial Foraging Optimization Technique To Calculate Resonant Frequency of RMA, International Journal of Microwave And Optical Technology Vol.4, No.2, March 2009.

13. Morteza Dastkhosh, Ahmad Faraahi, Seyyed Mohsen Hashemi, Seyyed Hossein Erfani, A Method for Text Summarization by Bacterial Foraging Optimization Algorithm, International Journal of Computer Science Issues, Vol. 9, Issue 4, No. 1, 2012.

14. Jing Dang, Anthony Brabazon, Michael ONeill, and David Edition, Option Model Calibration using a Bacterial Foraging Optimization Algorithm, Springer Berlin Heidelberg, No 113-122, 2008.

15. Chunguo Wu, Na Zhang, Jingqing Jiang, Jinhui Yang, and Yanchun Liang, Improved Bacterial Foraging Algorithms and their Applications to Job Shop Scheduling Problems, 8th International Conference, ICANNGA, No 562- 569, 2007.

16. A. Hertz and D.De Werra, Lausanne, Using Tabu Search Techniques for Graph Coloring In Computing, Springer Verlag computing 39, Pages 345-351, 1987.

17. Sambarta Dasgupta, Swagatam Das, Ajith Abraham, IEEE, and Arijit Biswas, Adaptive Computational Chemo taxis in Bacterial Foraging Optimization: An Analysis, IEEE Transactions on Evolutionary Computation, Vol.13, No.4, August 2009.