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

Stephen Chen
doctoral dissertation, tech. report CMU-RI-TR-99-21, Robotics Institute, Carnegie Mellon University, September, 1999


Download
  • Adobe portable document format (pdf) (348KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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.


Notes

Text Reference
Stephen Chen, "Is the Common Good? A New Perspective Developed in Genetic Algorithms," doctoral dissertation, tech. report CMU-RI-TR-99-21, Robotics Institute, Carnegie Mellon University, September, 1999

BibTeX Reference
@phdthesis{Chen_1999_3273,
   author = "Stephen Chen",
   title = "Is the Common Good? A New Perspective Developed in Genetic Algorithms",
   booktitle = "",
   school = "Robotics Institute, Carnegie Mellon University",
   month = "September",
   year = "1999",
   number= "CMU-RI-TR-99-21",
   address= "Pittsburgh, PA",
}