The grouping genetic algorithm (GGA), developed by Emmanuel Falkenauer, is a genetic algorithm whose encoding and operators are tailored to suit the special structure of grouping problems. In particular, the crossover operator for a GGA involves the development of heuristic procedures to restore group membership to any entities that may have been displaced by preceding actions of the operator. In this paper, we present evidence that the success of a GGA is heavily dependent on the replacement heuristic used as a part of the crossover operator. We demonstrate this by comparing the performance of a GGA that uses a naïve replacement heuristic (GGA0?) to a GGA that includes an intelligent replacement heuristic (GGACF). We evaluate both the naïve and intelligent approaches by applying each of the two GGAs? to a well-known grouping problem, the machine-part cell formation problem. The algorithms are tested on problems from the literature as well as randomly generated problems. Using two measures of effectiveness, grouping efficiency and grouping efficacy, our tests demonstrate that adding intelligence to the replacement heuristic enhances the performance of a GGA, particularly on the larger problems tested. Since the intelligence of the replacement heuristic is highly dependent on the particular grouping problem being solved, our research brings into question the robustness of the GGA.
Evelyn C. Brown and Robert T. Sumichrast, Impact of the replacement heuristic in a grouping genetic algorithm, Computers & Operations Research, Volume 30, Issue 11, September 2003, Pages 1575-1593.
http://dx.doi.org/10.1016/S0305-054800085-0 DOI
Local filename: science5.pdf
Talks about grouping GAs? (i.e. where the problem is to divide a set into subsets which are then tested against the fitness function) and why a traditional GA isn't suitable [more info on grouping GAs? in RefFalkenauer1998, citation [4] in this paper].
Provides a good explanation of the representation used.