Title of Presentation: Biased Random-Key Genetic Algorithms

Joint meeting of the XVI Latin-Ibero-American Congress on Operations Research and theXLIV Symposium on the Brazilian Operations Research Society

Rio de Janeiro, Brazil

September 2012

Abstract:

A biased random-key genetic algorithm (BRKGA) is a metaheuristic for combinatorial and continuous global optimization. In this tutorial, we introduce BRKGAs and show how they can be applied to find optimal or near-optimal solutions to optimization problems. The tutorial is organized as two 1.5 hour sections spread over two days.

In the first day, we introduce the general concepts of the method. We first briefly cover basic notions of combinatorial and continuous global optimization. We then review the basic idea of genetic algorithms (GAs). Finally we present BRKGAs, pointing out the differences between them and classical GAs. We consider the basic architecture of BRKGAs and then concentrate on each specific component. Finally, we consider extensions to the basic architecture. Throughout our discussion we make use of a classical combinatorial optimization problem to illustrate the metaheuristic.

In the second day, we consider implementation and applications of BRKGAs. We begin by describing an application programming interface (API) for BRKGAs and then describe applications of BRKGAs on several combinatorial and continuous global optimization problems.

Bio

Mauricio G. C. Resende is a research scientist at the Algorithms and Optimization Research Department of AT&T Labs Research. His research has focused on optimization, including interior point algorithms for linear programming, network optimization, and nonlinear programming, as well as heuristics for discrete optimization problems arising in telecommunications, scheduling, location, assignment, and graph theory. Most of his work with heuristics has concentrated on GRASP (greedy randomized adaptive search procedures), a metaheuristic that he and Thomas A. Feo developed in the late 1980s, and more recently on biased random-key genetic algorithms. Besides telecommunications area, he has worked in the electrical power and semiconductor manufacturing industries, where he developed several decision support systems (tools) for optimization problems.

He has published over 150 papers and is co-editor of five books, including the Handbook of Optimization in. Telecommunications and the Handbook of Applied Optimization. He is on the editorial boards of several journals. He earned a M.Sc. in operations research at the Georgia Institute of Technology and his Ph.D. in operations research at the University of California, Berkeley.