Smooth uniform crossover, sub-machine code GP and demes: a recipe for solving high-order Boolean parity problems
Riccardo Poli, Jonathan Page, William B. Langdon · 1999
We describe a recipe to solve very large parity problems using GP. The recipe includes: smooth uniform crossover (a crossover operator inspired by our theoretical research), sub-machine-code GP (a technique to speed up fitness evaluation in Boolean classification problems), and interacting demes (sub-populations) running on separate workstations. We tested this recipe on parity problems with up to 22 input variables, solving them with a very high success probability. 1 INTRODUCTION The even-n-parity functions have long been recognised as difficult for Genetic Programming (GP) to induce if no bias favourable to their induction is introduced in the function set, the input representation, or in any other part of the algorithm. For this reason they have been widely used as benchmark tests [1, 3, 4, 5, 6, 16, 17, 19]. For an even-parity function of n Boolean inputs, the task is to evolve a function that returns 1 if an even number of the inputs evaluate to 1, 0 otherwise. The tas...