A biased random-key genetic algorithm (BRKGA) is a general search metaheuristic 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:

 

1) A fixed chromosome encoding using a vector of N random keys or alleles over the real 

interval [0, 1), where the value of N depends on the instance of the optimization problem;

 

2) A well-defined evolutionary process adopting parameterized uniform crossover to 

generate offspring and thus evolve the population;

 

3) The introduction of new chromosomes called mutants in place of the mutation operator 

usually found in evolutionary algorithms.

 

Such features simplify and standardize the metaheuristic 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 an Application 

Programming Interface (API) for quick implementations of BRKGA heuristics. We then 

apply the framework to a number of packing and layout problems, including

 

1) 2D and 3D constrained orthogonal packing

 

2) 2D and 3D bin packing

 

3) Unequal area facility layout

 

We conclude with a brief review of other domains where BRKGA have been applied.