Commonality and Genetic Algorithms

Abstract

The commonality hypothesis introduced in this paper suggests that the preservation of common schemata is the central source of power in recombination operators. A commonality-based crossover operator proceeds in two steps: 1) identify the maximal common schema of two parents, and 2) complete the solution with a construction heuristic. Using this framework, two new crossover operators are proposed for sequencing problems. The first uses partial order for the basis of commonality. This operator is shown to perform well on the Traveling Salesman Problem (TSP), and it finds new best-known solutions for many Sequential Ordering Problem (SOP) instances. The second operator is based on sub-tours/edges, and it is used to demonstrate the utility of the new framework for designing hybrid genetic algorithms.