Experiments on Commonality in Sequencing Operators

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


Download
  • 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.

Abstract
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.

Keywords
genetic algorithms, Traveling Salesman Problem, commonality hypothesis

Notes
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
@inproceedings{Chen_1998_553,
   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",
}