Non-Wrapping Order Crossover: An Order Preserving Crossover Operator that Respects Absolute Position

In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'06), volume 2, pages 1125-1131. ACM Press, .

Nominated for the Genetic Algorithms Track Best Paper Award.

[PDF] [BIB] [DOI]

Abstract

In this paper, we introduce a new crossover operator for the permutation representation of a GA. This new operator, Non-Wrapping Order Crossover (NWOX), is a variation of the well-known Order Crossover (OX) operator. It strongly preserves relative order, as does the original OX, but also respects the absolute positions within the parent permutations. This crossover operator is experimentally compared to several other permutation crossover operators on an NP-Hard problem known as weighted tardiness scheduling with sequence-dependent setups. A GA using this NWOX operator finds new best known solutions for several benchmark problem instances and proves to be superior to the previous best performing metaheuristic for the problem.