Experiments on Commonality in Sequencing Operators

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.