Revisiting the GEMGA: Scalable evolutionary optimization through linkage learning

The Gene expression messy genetic algorithm (GEMGA) is a new generation of messy genetic algorithms (GAs) that pays careful attention to linkage learning (identification of partitions defining the good schemata) using motivations from the natural process of gene expression (DNA-->mRNA-->Protein). This paper proposes a version of GEMGA that offers much better performance for problems in which schemata do not delineate the search space in very clearly defined good and bad regions. The proposed algorithm for detecting schema linkage runs in linear time and therefore replaces the previously suggested technique that required quadratic number of experiments. This paper also reports the scalable linear performance of the GEMGA for various difficult, large, discrete optimization problems.