Carnegie Mellon University
Putting the "Genetics" back into Genetic Algorithms (Reconsidering the Role of Crossover in Hybrid Operators)

Stephen Chen and Stephen Smith
Foundations of Genetic Algorithms 5, 1999.

  • Adobe portable document format (pdf) (148KB)
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.

The original analysis of genetic algorithms presents combination to be the primary mechanism of crossover. Although good solutions can be found by combination, they are often not locally optimal. Thus, a popular technique is to locally optimize each crossover solution before adding it to the population. In these ``hybrid'' operators, crossover can be viewed as a means of restarting the local optimizer. Unfortunately, if crossover does little more than combine random parts of two parent solutions, the performance of the resulting hybrid operator may not be significantly different from random restart of the local optimizer. The design of the crossover operator affects the efficiency and effectiveness of hybrid operators. A new analysis presents preserving common schemata as an important design consideration for crossover.

genetic algorithms, Traveling Salesman Problem, commonality hypothesis

Associated Center(s) / Consortia: Center for Integrated Manfacturing Decision Systems
Associated Lab(s) / Group(s): Intelligent Coordination and Logistics Laboratory

Text Reference
Stephen Chen and Stephen Smith, "Putting the "Genetics" back into Genetic Algorithms (Reconsidering the Role of Crossover in Hybrid Operators)," Foundations of Genetic Algorithms 5, 1999.

BibTeX Reference
   author = "Stephen Chen and Stephen Smith",
   editor = "Wolfgang Banzhaf, Colin Reeves",
   title = "Putting the "Genetics" back into Genetic Algorithms (Reconsidering the Role of Crossover in Hybrid Operators)",
   booktitle = "Foundations of Genetic Algorithms 5",
   publisher = "Morgan Kaufmann",
   year = "1999",