The Robotics Institute

Carnegie Mellon Robotics Institute

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",
}

The Robotics Institute

Menu