Node Preservation and its Effect on Crossover in Cartesian Genetic Programming
This addresses a specific bottleneck in CGP for evolutionary computation researchers, but it is incremental as it builds on existing operators.
The paper tackled the problem that crossover deteriorates search performance in Cartesian Genetic Programming (CGP), finding that node preservation in both mutation and crossover improves search on symbolic regression benchmarks, moving towards a general solution.
While crossover is a critical and often indispensable component in other forms of Genetic Programming, such as Linear- and Tree-based, it has consistently been claimed that it deteriorates search performance in CGP. As a result, a mutation-alone $(1+λ)$ evolutionary strategy has become the canonical approach for CGP. Although several operators have been developed that demonstrate an increased performance over the canonical method, a general solution to the problem is still lacking. In this paper, we compare basic crossover methods, namely one-point and uniform, to variants in which nodes are ``preserved,'' including the subgraph crossover developed by Roman Kalkreuth, the difference being that when ``node preservation'' is active, crossover is not allowed to break apart instructions. We also compare a node mutation operator to the traditional point mutation; the former simply replaces an entire node with a new one. We find that node preservation in both mutation and crossover improves search using symbolic regression benchmark problems, moving the field towards a general solution to CGP crossover.