Variation Operators for Grouping Genetic Algorithms: A Review

Grouping problems are combinatorial optimization problems, most of them NP-hard, related to the partition of a set of items into different groups or clusters. Given their numerous real-world applications, different solution approaches have been presented to deal with the high complexity of NP-hard grouping problems. However, the Grouping Genetic Algorithm (GGA) is one of the most outstanding solution methods. GGA is an extension to the traditional Genetic Algorithm (GA) that uses a representation scheme based on groups and variation operators adapted to work at the groups level. Since its emergence, GGA has been used to address several grouping problems with distinct traits. Therefore, at present, there are different variation operators developed to solve problems with diverse grouping constraints and conditions. This paper presents a review of variation operators included in GGAs solving NP-hard grouping problems. Three classifications are introduced, organizing the variation operators according to the variation-degree, the solutions encoding, and the parameter setting-level, respectively.