The Grouping Genetic Algorithms: Widening the scope of the GAs

An important class of computational problems are grouping problems, where the aim is to group members of a set, i.e. to find a good partitioning of the set. The paper shows why both the classic and the ordering GAs fare poorly in this domain by pointing out their inherent difficulty to capture the regularities of the ‘functional landscape’ of grouping problems. It then proposes a new encoding scheme and genetic operators adapted to these problems, yielding the Grouping Genetic Algorithm (GGA) paradigm. The paper illustrates the approach with three examples of important grouping problems successfully treated with the GGA: the problems of Bin Packing and Line Balancing, Economies of Scale, and Conjunctive Conceptual Clustering applied to the problem of creation of part families.