Carnegie Mellon University
Experiments on Commonality in Sequencing Operators

Stephen Chen and Stephen Smith
Genetic Programming 1998: Proceedings of the Third Annual Conference, 1998.

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

Traditionally, crossover operators are based on combination--an operator takes parts from two parents and combines them into an offspring. This paper presents a series of crossover operators based on commonality--an operator preserves the common parts from two parents and uses them as a base on which an offspring solution is built. Experiments on benchmark sequencing problems show that these new commonality-based operators perform better than previously developed combination-based operators. One new operator, Maximum Partial Order/Arbitrary Insertion, is capable of finding new best-known solutions for the Sequential Ordering Problem. Overall, the results support a new commonality-based framework for designing crossover operators.

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, "Experiments on Commonality in Sequencing Operators," Genetic Programming 1998: Proceedings of the Third Annual Conference, 1998.

BibTeX Reference
   author = "Stephen Chen and Stephen Smith",
   title = "Experiments on Commonality in Sequencing Operators",
   booktitle = "Genetic Programming 1998: Proceedings of the Third Annual Conference",
   publisher = "Morgan Kaufmann",
   year = "1998",