Second order heuristics in ACGP

Genetic Programming explores the problem search space by means of operators and selection. Mutation and crossover operators apply uniformly, while selection is the driving force for the search. Constrained GP changes the uniform exploration to pruned non-uniform, skipping some subspaces and giving preferences to others, according to some heuristics. Adaptable Constrained GP is a methodology for discovery of such useful heuristics. Both methodologies have previously demonstrated their surprising capabilities using only first-order (parent-child) heuristics. Recently, they have been extended to second-order (parent-children) heuristics. This paper describes the second-order processing, and illustrates the usefulness and efficiency of this approach using a simple problem specifically constructed to exhibit strong second-order structure.