Experiments on Commonality in Sequencing Operators

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 commonalitybased framework for designing crossover operators. 1. Introduction A genetic algorithm (GA) has three basic features: a population of solutions, fitness-based selection, and crossover. In isolation, fitness-based selection over a population of solutions causes various building blocks (or schemata) to increase ..