Graphics enhanced version of this site

Commonality and Genetic Algorithms
S. Chen and S. Smith
tech. report CMU-RI-TR-96-27, Robotics Institute, Carnegie Mellon University, December, 1996.

Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference

Adobe portable document format (pdf) [776 KB]

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 commonality hypothesis introduced in this paper suggests that the preservation of common schemata is the central source of power in recombination operators. A commonality-based crossover operator proceeds in two steps: 1) identify the maximal common schema of two parents, and 2) complete the solution with a construction heuristic. Using this framework, two new crossover operators are proposed for sequencing problems. The first uses partial order for the basis of commonality. This operator is shown to perform well on the Traveling Salesman Problem (TSP), and it finds new best-known solutions for many Sequential Ordering Problem (SOP) instances. The second operator is based on sub-tours/edges, and it is used to demonstrate the utility of the new framework for designing hybrid genetic algorithms.

Sponsor: ARPA, Rome Laboratory
Grant ID: F30602-95-1-0018

Number of pages: 12

S. Chen and S. Smith, Commonality and Genetic Algorithms, tech. report CMU-RI-TR-96-27, Robotics Institute, Carnegie Mellon University, December, 1996.

@techreport{Chen_1996_419,
   author = "Stephen Chen and Stephen Smith",
   title = "Commonality and Genetic Algorithms",
   institution = "Robotics Institute, Carnegie Mellon University",
   month = "December",
   year = "1996",
   number = "CMU-RI-TR-96-27",
   address = "Pittsburgh, PA"
}