The grouping genetic algorithms: widening the scope of the GA's

Abstract

An important class of computational problems are grouping problems, where the aim is to group membersofa set, i.e. to find a good partitioning of the set. We show why both the classic and the ordering GA's fare poorly in this domain by pointing out their inherent difficulty to capture the regularities of the “functional landscape” of grouping problems. We then propose a new encoding scheme and genetic operators adapted to these problems, yielding the Grouping Genetic Algorithm (GGA) paradigm. We illustrate 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.