Applying Genetic Algorithms to Real-world Problems

Thursday, October 24, 1996 - 11:00am - 12:00pm
Keller 3-180
Emanuel Falkenauer (Brussels University)
This paper outlines what the author perceives as crucial ingredients of a successful application of Genetic Algorithms (GAs) to real-world combinatorial problems. First, the importance of the Schema Theorem is stressed, pointing to crossover as the most potent force in a GA. Second, the importance of an encoding and operators adapted to the problem being solved is demonstrated, with two implications: the importance of the binary alphabete has been largely overestimated in the past, and practical GAs must be built to solve problems (i.e. sets of instances) rather than (arbitrary) functions. Finally, the benefits and possible caveats of local optimization are discussed. The benefits of the above guidliness are illustrated by the Grouping GA (GGA), applied to three different grouping problems, namely Bin Packing, Equal Piles and Economies of Scale. The first application suggest a superiority of crossover-based search over a classical Branch-and-Bound, the second shows the superiority of the GGA over standard GAs, and the third illustrates the kind of industrial applications GAs can be called upon to solve.