Evolutionary Robustness

title = "Evolutionary Robustness",

booktitle = "2nd GECCO workshop on Graph-based Genetic Programming",

year = "2024",

editor = "Dennis G. Wilson and Roman Kalkreuth and Eric Medvet and Giorgia Nadizar and Giovanni Squillero and Alberto Tonda and Yuri Lavinas",

address = "Melbourne",

series = "GECCO '24",

month = "14 " # jul,

organisation = "SIGEVO",

publisher = "Association for Computing Machinery",

publisher_address = "New York, NY, USA",

note = "Invited talk",

keywords = "genetic algorithms, genetic programming, genetic improvement",

URL = "

https://graphgp.com/program/#evolutionary-robustness",

video_url = "

http://www.cs.ucl.ac.uk/staff/W.Langdon/gecco2024/ggp2024/langdon_ggp2024.mp4",

slide_url = "

http://www.cs.ucl.ac.uk/staff/W.Langdon/gecco2024/ggp2024/langdon_ggp2024_slides.pdf",

abstract = "Genetic programming (GP) and other types of Evolutionary Algorithms (EC) have long been demonstrated to be creative. A recently \cite{langdon:jaws30} raised question was how much are they used? Data from the genetic programming bibliography for last year suggests about 38 percent of published papers are primarily on applications which just happen to use GP. Many applications relate to health, civil engineering or solid state materials, e.g. batteries.

Lenski et al. studies of long term evolution in biology show evolution can retain its ability for continued change even after 75,000 generations. Instead of 36 years, with performance effectively exceeding a trillion GP operations per second \cite{langdon:2022:trillion}, GP experiments can be run to a million generations in weeks on a single computer \cite{Langdon:2022:ALJ}. Information theory explains why in small populations, GP populations converge \cite{langdon:GPEM:gpconv} and the rate of fitness improvement falls as huge GP trees become more robust to crossover.

Mutation testing on C and C++ programs show that real software can also be robust to many source code changes \cite{langdon:2024:GI}. As with lisp functional language in tree GP, there is a tendency for deeply nested imperative code to be more robust.

There are already examples of human written software systems that exceed a billion lines of (imperative) source code. Information theory failed disruption propagation (FDP) \cite{Petke:2021:FSE-IVR} helps to explain why maintaining, testing and debugging such deeply nested code repositories is hard and why software companies prefer unit testing of modules (each of which is typically only shallowly nested) rather than system testing of complete functional hierarchies. There is already SBSE work on automatically optimizing test oracles. FDP suggests systems should be built with many densely packed test agents so that disruption caused by bugs has little distance to travel before being discovered by an oracle.

For evolutionary computing and artificial life experiments aiming for sustained innovation, we propose the use of ''mangrove'' architectures \cite{langdon:ei2024} composed of many small trees which are intimate with their environment. For continuous innovative evolution the fitness function needs to be able to measure on average if genetic changes are good or not, or at least have made a difference. This means we must overcome robustness, without introducing chaos. We suggest this might be met by systems where the bulk of the code remains close to the fitness environment and the disruption caused by most mutations and crossovers has only a short depth to propagate in order to have a measurable fitness impact.",

notes = "Abstract only. No paper in GECCO 2024 proceedings.

GECCO-2024 A Recombination of the 33rd International Conference on Genetic Algorithms (ICGA) and the 29th Annual Genetic Programming Conference (GP)",