Is the Common Good? A New Perspective Developed in Genetic Algorithms

Abstract

Similarities are more important than differences. The importance of these common components is set forth by the commonality hypothesis: schemata common to above-average solutions are above average. This hypothesis is corroborated by the isolation of commonality-based selection. It follows that uncommon components should be below average (relative to their parents). In genetic algorithms, the traditional advantage of crossover has been attributed to the recombination of (uncommon) parent components. However, the original analysis focused on how the schemata of a single parent were affected by crossover. Using an explicit two-parent perspective, the preservation of common components is emphasized. The commonality hypothesis suggests that these common schemata are the critical building blocks manipulated by crossover. Specifically, common components have a higher expected fitness than uncommon components. The Commonality-Based Crossover Framework redefines crossover as a two step process: 1) preserve the maximal common schema of two parents, and 2) complete the solution with a construction heuristic. To demonstrate the utility of this design model, domain-independent operators, heuristic operators, and hybrid operators have been developed for benchmark and practical problems with standard and non-standard representations. The new commonality-based operators have performed consistently better than comparable operators which emphasize combination. In heuristic operators (which use problem specific heuristics during crossover), the effects of commonality-based selection have been isolated in GENIE (a genetic algorithm that eliminates fitness-based selection of parents). Since the effectiveness of construction heuristics can be amplified by using only commonality-based restarts, the preservation of common components has supplied selective pressure at the component (rather than individual) level. This result corroborates the commonality hypothesis--the preserved common schemata are above average. Transferring the concept of commonality-based selection back to standard crossover operators, beneficial changes should occur more frequently when they are restricted to uncommon schemata. Since multiple parents are required to identify common compo-nents, commonality-based selection is an advantage that multi-parent operators (e.g. crossover) can have over single-parent operators (e.g. mutation). These observations present a novel perspective on iterative improvement.