Over Sampling Local Optima: Selection and Sampling Bias in Hybrid Genetic Algorithms

Partition Crossover induces lattices over subsets of local optima in the search spaces of classic combinatorial problems such as MAX-SAT and the Traveling Salesman Problem. This paper explores the interaction between Partition Crossover, the lattices that are produced, and various algorithmic decisions. First, we prove that hard selection such as “truncation selection” will make it more difficult to find opportunities to successfully apply Partition Crossover. This suggests that less aggressive forms of selection could be more productive. Second, we consider hybrid genetic algorithms (GAs) that only recombine solutions that are local optima. We prove that hybrid GAs have an inherent bias that makes them more likely to sample other local optima. These two results can inform the design of more effective hybrid evolutionary algorithms.