Title of Presentation: Biased Random-Key Genetic Algorithms: Components, Evolutionary Dynamics and Applications
A biased random-key genetic algorithm (BRKGA) is a general search procedure for finding optimal or near-optimal solutions to hard combinatorial optimization problems. It is derived from the random-key genetic algorithm of Bean (1994), differing in the way solutions are combined to produce offspring. BRKGAs have three key features that specialize genetic algorithms. First, a fixed chromosome encoding using a vector of N random keys over the real interval [0, 1), where the value of N depends on the instance of the optimization problem. Second, a well-defined evolutionary process adopting a parameterized uniform crossover to generate offspring and thus evolve the population. Third, the introduction of new chromosomes called mutants in place of the mutation operator usually found in evolutionary algorithms. Such features simplify and standardize the procedure with a set of self-contained tasks from which only one is problem-dependent: that of decoding a chromosome, i.e. using the keys to construct a solution to the underlying optimization problem, from which the objective function value or fitness can be computed. In this talk, we review the basic components of a BRKGA and introduce a framework for quick implementations of BRKGA heuristics. We then illustrate the application of this framework to a few case studies in a network routing, load scheduling and data mining problems. We conclude with a brief review of other domains where BRKGAs have been applied.
Celso C. Ribeiro is a Full Professor at the Department of Computer Science of Universidade Federal Fluminense, Brazil. He obtained his doctorate in Computer Science at the Ecole Nationale Supérieure des Télécommunications, France, in 1983. He chaired the Departments of Electrical Engineering (1983-1987) and Computer Science (1993-1995) of the Catholic University of Rio de Janeiro, Brazil.