A COEVOLUTIONARY GENETIC SEARCH FOR A LAYOUT PROBLEM

This chapter is devoted to an application of genetic algorithms and coevolutionary principles to a large optimization problem. Starting point is a mixed integer linear program which models our problem—in this case a facility layout problem. As the number of binary variables increases quadratically with the problem size, currently available solvers fail already for small problem instances. Using a genetic search our algorithm reduces the number of binary variables by setting a considerable part of them. The genetic operators were specially designed to yield a high percentage of feasible variable settings. In order to further speed up the computation of large problems we propose a partition into interdependent subproblems. Each subproblem ("species") is evolved by a genetic algorithm respecting the constraints ("environment") generated by the others. Numerical experiments verify this revolutionary approach.