Is the common good? A new perspective developed in genetic algorithms.

摘要

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 components, 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.