Node Preservation and its Effect on Crossover in Cartesian Genetic Programming
Mark Kocherovsky, Illya Bakurov, Wolfgang Banzhaf · 2025
Read Node Preservation and its Effect on Crossover in Cartesian Genetic Programming by Mark Kocherovsky, Illya Bakurov, Wolfgang Banzhaf (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-00634.txt.
Introduction
Mark Kocherovsky, Illya Bakurov, and Wolfgang Banzhaf revisit a dogma of Cartesian genetic programming, a method that evolves programs laid out on a grid of nodes. Crossover, the mixing of two parents' material, is prized in other genetic programming families, yet in this one it is widely said to harm search, so mutation-only strategies became canonical. A general fix has been missing.
The authors compare basic one-point and uniform crossover against variants with node preservation, where crossover may not tear instructions apart, including a published subgraph crossover. They also test a node mutation that swaps whole nodes against traditional point mutation. On symbolic regression benchmarks, node preservation improved search in both crossover and mutation. Respecting the building blocks of a program, it seems, lets crossover finally pull its weight.
Catalog record
| CREATOR | Mark Kocherovsky, Illya Bakurov, Wolfgang Banzhaf |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-00634
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Node Preservation and its Effect on Crossover in Cartesian Genetic Programming Mark Kocherovsky, Illya Bakurov, Wolfgang Banzhaf Abstract 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 + λ ) (1+\lambda) 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. 1 Introduction Genetic Programming (GP) has seen several decades of research as a subfield of Evolutionary Computation (EC). Established in the late 1980s / early 1990s by John Koza [ 26 , 27 ] , GP extends traditional Genetic Algorithmic (GA) methods by evolving programs , ranging from basic Boolean and symbolic expressions to complex system control algorithms. Programs are traditionally represented as trees (TGP), where leaves contain terminals (input variables and constants) and parent nodes contain operators. As the tree is traversed, an expression is constructed. Crossover occurs by swapping subtrees between individuals, and mutation changes the tree structure. A notable feature of GP is the presence of introns , also referred to as ineffective instructions . These are parts of the program that do not influence the final output behavior, yet they are believed to play a beneficial role by providing additional genetic material for variation operators to act upon. In contrast, exons are parts of the code that directly contribute to the output behavior of programs [ 7 , 38 ] . A consistent problem with GP is bloat , a phenomenon where individuals become increasingly large, thus more complex, leading to slower run-times and deteriorating interpretability. Early studies established that the majority of the genome in GP consists of introns [ 37 , 38 ] . More recent findings have shown that this proportion further increases when also considering genes that only marginally affect behavioral semantics [ 3 ] . Additionally, even under exploratory evolutionary dynamics, the genotypic population is often dominated by a small number of distinct phenotypes, i.e., tree structures composed primarily of exonic (active) components. Bloat in TGP has been extensively studied, with several theories proposed to explain its emergence [ 45 , 29 , 30 , 16 , 31 , 6 , 2 , 42 , 5 ] . One prominent theory derives parallels from intron research in genetics [ 48 ] , and suggests that bloat arises as a protective mechanism to preserve useful substructures, or building blocks, which are otherwise vulnerable to disruption by mutation and crossover [ 38 , 37 , 31 , 6 , 2 , 42 ] . This vulnerability arises from the lack of explicit built-in mechanisms for preservation and modular reuse of building blocks in basic TGP. As a response to TGP’s limitations, numerous alternative GP paradigms have been developed. These primarily differ in the data structures used to represent candidate solutions and in the design of initialization and variation operators tailored to those representations [ 4 , 8 ] . One of these alternatives is Linear GP (LGP), where programs are represented as variable-length sequences of instructions executed in order [ 4 , 8 , 43 , 40 , 32 , 33 ] . Each instruction operates on a set of registers, which serve as a steady-state memory module that stores intermediate results. This register-based architecture facilitates the reuse of partial computations and reduces the risk of structural disruption during variation [ 24 ] . Cartesian Genetic Programming (CGP) is another form of GP; CGP uses a fixed-length linear genome to encode programs represented as directed acyclic graphs (DAGs), where each gene specifies a functional component and its connections in a cartesian grid-like structure [ 33 ] . Each node in the genome applies a function to a fixed number of inputs, selected from earlier nodes or input variables, thereby supporting explicit reuse of intermediate results. Unlike LGP, however, CGP does not use registers and instead relies on positional references within the genome [ 24 ] . The fixed-length representation in CGP helps to control bloat by forcing the evolutionary search to operate within a bounded genomic space. However, this structural rigidity can also limit evolvability, particularly in problems that benefit from larger or more modular solutions. On the other hand, the fixed-length encoding enables direct crossover at the genomic level. Thus, it became tempting for researchers and practitioners to use traditional GA-style crossover operators in CGP. Yet, empirical studies have consistently shown that such operators are often detrimental to CGP’s search performance [ 10 , 24 ] , and the scientific community mostly avoids their usage [ 34 ] . As such, a ( 1+\lambda ) configuration is typically used in practice. In response, researchers have proposed systematic explanations for CGP’s crossover limitations and introduced alternative operators specifically tailored to its representation [ 9 , 10 , 23 , 15 , 20 , 19 , 14 , 12 , 11 ] . In particular, Kalkreuth [ 20 , 21 , 22 ] and Cui [ 12 , 14 , 11 , 13 ] , have advanced a deeper understanding of CGP’s structural and positional constraints, leading to more principled crossover operators. These efforts demonstrate that effective crossover is possible when grounded in a clear rationale, yet the field still lacks a unified theory or widely accepted best practices for recombination in CGP. In 2024, Kocherovsky and Banzhaf hypothesized that CGP lacks means to “anchor” good substructures, as the steady-state memory does in LGP [ 24 ] . Building on this, their 2025 work [ 25 ] reaffirmed the positional and structural insights from Cui [ 14 ] , arguing that the failure of some CGP crossover strategies stems from implicit assumptions about positional equivalence and structural interchangeability. From this basis, we follow Kalkreuth [ 21 ] and Kocherovsky et al. [ 24 , 25 ] in testing one of the features of Subgraph crossover in the general case: crossover in Subgraph crossover necessarily operates at node-level, instead of at the genomic level , because otherwise its behavioral constraints would be broken. We call this technique Node Preservation , because the node is structurally preserved throughout the operation. Here we thus argue that by ensuring to perform node preservation — which can be accomplished as easily as changing the representation of a program from a one-dimensional vector to a two-dimensional matrix — both crossover and mutation are generally improved. We test one-point and uniform crossover methods, which are classical operators in the wider field of evolutionary