Deep Genetic Programming Trees are Robust

title = "Deep Genetic Programming Trees are Robust",

journal = "ACM Transactions on Evolutionary Learning and Optimization",

year = "2022",

volume = "2",

number = "2",

articleno = "6",

month = jun,

keywords = "genetic algorithms, genetic programming, heritability, information theory, information funnels, sandpile 1/f powerlaw, self-organised criticality, SOC, self-similar fractal, GP fitness landscape, evolvability, mutational robustness, neutral networks, SBSE, software robustness, correctness attraction, diversity, software testing, theory of bloat, introns, error hiding, invisible faults, disruption propagation failure, DPF, FEP",

ISSN = "2688-299X",

URL = "

http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/langdon_2022_TELO.pdf",

DOI = "

doi:10.1145/3539738",

size = "34 pages",

abstract = "We sample the genetic programming tree search space and show it is smooth since many mutations on many test cases have little or no fitness impact. We generate uniformly at random high order polynomials composed of 12500 and 750000 additions and multiplications and follow the impact of small changes to them. From information theory 32 bit floating point arithmetic is dissipative and even with 1501 test cases deep mutations seldom have any impact on fitness. Absolute difference between parent and child evaluation can grow as well as fall further from the code change location but the number of disrupted fitness tests falls monotonically. In many cases deeply nested expressions are robust to crossover syntax changes, bugs, errors, run time glitches, perturbations, etc., because their disruption falls to zero, and so it fails to propagate beyond the program.",