Global Bacteria Optimization Meta-Heuristic: Performance Analysis and Application to Shop Scheduling Problems

Global Bacteria Optimization Meta-Heuristic: Performance Analysis and Application to Shop Scheduling Problems

Elyn L. Solano-Charris (Universidad de La Sabana, Colombia), Libardo S. Gómez-Vizcaíno (Universidad Autónoma del Caribe, Colombia), Jairo R. Montoya-Torres (Universidad de La Sabana, Colombia) and Carlos D. Paternina-Arboleda (Universidad del Norte, Colombia)
DOI: 10.4018/978-1-61350-086-6.ch009
OnDemand PDF Download:
$37.50

Abstract

A large number of real-life optimization problems in economics and business are complex and difficult to solve. Hence, using approximate algorithms is a very good alternative to solve this class of problems. Meta-heuristics solution procedures represent general approximate algorithms applicable to a large variety of optimization problems. Most of the meta-heuristics mimic natural metaphors to solve complex optimization problems. This chapter presents a novel procedure based on Bacterial Phototaxis, called Global Bacteria Optimization (GBO) algorithm, to solve combinatorial optimization problems. The algorithm emulates the movement of an organism in response to stimulus from light. The effectiveness of the proposed meta-heuristic algorithm is first compared with the well-known meta-heuristic MOEA (Multi-Objective Evolutionary Algorithm) using mathematical functions. The performance of GBO is also analyzed by solving some single- and multi-objective classical jobshop scheduling problems against state-of-the-art algorithms. Experimental results on well-known instances show that GBO algorithm performs very well and even outperforms existing meta-heuristics in terms of computational time and quality of solution.
Chapter Preview
Top

Global Bacteria Optimization Meta-Heuristic

Preliminaries: What is a Bacterium?

A bacterium is a prokaryotic unicellular organism. Its structure is basically conformed by a central body of microscopic size that can take many different forms (Young, 2006) and whose size can vary from 0.01 μm3 to a volume 1010 times bigger (Angert et al., 1993; Rappe et al., 2002). Many bacteria are endowed with a series of rotating flagella in its cell surface that act as propellants, allowing them to swim at a speed of 10-35 μm/s (Guzmán et al., 2010). In addition to the appropriate structure to move in an autonomous way, bacteria have potential receivers (chemoreceptors and photoreceptors) capable of detecting temporal-space changes in the environment that surrounds them. In this way, when an external perturbation is detected, bacteria use their memory to make a temporal-space comparison of the gradients found. Depending on the external conditions sensed, bacteria change their movements from a random walk to a biased walk (Guzmán et al., 2010).

Complete Chapter List

Search this Book:
Reset