A New Representation and Operators for Genetic Algorithms Applied to Grouping Problems

An important class of computational problems are grouping problems, where the aim is to group together members of a set (i.e., find a good partition of the set). We show why both the standard and the ordering GAS fare poorly in this domain by pointing out their inherent difficulty to capture the regularities of the functional landscape of the grouping problems. We then propose a new encoding scheme and genetic operators adapted to these problems, yielding the Grouping Genetic Algorithm (GGA). We give an experimental comparison of the GGA with the other GAS applied to grouping problems, and we illustrate the approach with two more examples of important grouping problems successfully treated with the GGA: the problems of Bin Packing and Economies of Scale.