Equidistant Reorder Operator for Cartesian Genetic Programming

The Reorder operator, an extension to Cartesian Genetic Programming (CGP), eliminates limitations of the classic CGP algorithm by shuffling the genome. One of those limitations is the positional bias, a phenomenon in which mostly genes at the start of the genome contribute to an output, while genes at the end rarely do. This can lead to worse fitness or more training iterations needed to find a solution. To combat this problem, the existing Reorder operator shuffles the genome without changing its phenotypical encoding. However, we argue that Reorder may not fully eliminate the positional bias but only weaken its effects. By introducing a novel operator we name Equidistant-Reorder, we try to fully avoid the positional bias. Instead of shuffling the genome, active nodes are reordered equidistantly in the genome. Via this operator, we can show empirically on four Boolean benchmarks that the number of iterations needed until a solution is found decreases; and fewer nodes are needed to efficiently find a solution, which potentially saves CPU time with each iteration. At last, we visually analyse the distribution of active nodes in the genomes. A potential decrease of the negative effects of the positional bias can be derived with our extension.