Engineering Tag-Matching Systems for Digital Evolution

This Hot-off-the-Press paper summarizes our recently published work, “Matchmaker, Matchmaker, Make Me a Match: Geometric, Variational, and Evolutionary Implications of Criteria for Tag Affinity.” This work appeared in Genetic Programming and Evolvable Machines. Genetic programming systems commonly use tag matching to decide interactions between system components. However, the implications of criteria used to determine affinity between tags with respect evolutionary dynamics have not been directly studied. We investigate differences between tag-matching criteria with respect to geometric constraint and variation generated under mutation. In experiments, we find that tag-matching criteria can influence the rate of adaptive evolution and the quality of evolved solutions. Better understanding of the geometric, variational, and evolutionary properties of tag-matching criteria will facilitate more effective incorporation of tag matching into genetic programming systems. By showing that tag-matching criteria influence connectivity patterns and evolutionary dynamics, our findings also raise fundamental questions about the properties of tag-matching systems in nature.

Matthew Andres Moreno, Alexander Lalejini, and Charles Ofria. 2023. Tag Affinity Criteria Influence Adaptive Evolution. In Proceedings of the Companion Conference on Genetic and Evolutionary Computation (GECCO ‘23 Companion). Association for Computing Machinery, New York, NY, USA, 35–36. https://doi.org/10.1145/3583133.3595834

• presentation via YouTube
• slides via Google Slides
• LaTeX source via GitHub
• primary publication

Genetic programming and artificial life systems commonly use tag matching to decide interactions between system components. However, the implications of criteria used to determine affinity between tags with respect evolutionary dynamics have not been directly studied. We investigate differences between tag-matching criteria with respect to geometric constraint and variation generated under mutation. In experiments, we find that tag-matching criteria can influence the rate of adaptive evolution and the quality of evolved solutions. Better understanding of the geometric, variational, and evolutionary properties of tag-matching criteria will facilitate more effective incorporation of tag matching into genetic programming and artificial life systems. By showing that tag-matching criteria influence connectivity patterns and evolutionary dynamics, our findings also raise fundamental questions about the properties of tag-matching systems in nature.

Moreno, M.A., Lalejini, A. & Ofria, C. Matchmaker, matchmaker, make me a match: geometric, variational, and evolutionary implications of criteria for tag affinity. Genet Program Evolvable Mach 24, 4 (2023). https://doi.org/10.1007/s10710-023-09448-0

• data via Open Science Framework ❋
• source code via GitHub
• source code via GitHub
• LaTeX source via GitHub
• twitter thread

This Hot-off-the-Press paper summarizes our recently published work, “Tag-based regulation of modules in genetic programming improves context-dependent problem solving,” published in Genetic Programming and Evolvable Machines. We introduce and experimentally demonstrate tag-based genetic regulation, a genetic programming (GP) technique that allows programs to dynamically adjust which code modules to express. Tags are evolvable labels that provide a flexible naming scheme for referencing code modules. Tag-based regulation extends tag-based naming schemes to allow programs to “promote” and “repress” code modules to alter module execution patterns. We find that tag-based regulation improves problem-solving success on problems where programs must adjust how they respond to current inputs based on prior inputs; indeed, some of these problems could not be solved until regulation was added. We also identify scenarios where the correct response to an input does not change over time, rendering tag-based regulation an unnecessary functionality that can sometimes impede evolution. Broadly, tag-based regulation adds to our repertoire of techniques for evolving more dynamic computer programs and can easily be incorporated into existing tag-enabled GP systems.

Alexander Lalejini, Matthew Andres Moreno, and Charles Ofria. 2022. Tag-based Module Regulation for Genetic Programming. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO ‘22). Association for Computing Machinery, New York, NY, USA, 25–26. https://doi.org/10.1145/3520304.3534060

• primary publication

We introduce and experimentally demonstrate the utility of tag-based genetic regulation, a new genetic programming (GP) technique that allows programs to dynamically adjust which code modules to express. Tags are evolvable labels that provide a flexible mechanism for referencing code modules. Tag-based genetic regulation extends existing tag-based naming schemes to allow programs to “promote” and “repress” code modules in order to alter expression patterns. This extension allows evolution to structure a program as a gene regulatory network where modules are regulated based on instruction executions. We demonstrate the functionality of tag-based regulation on a range of program synthesis problems. We find that tag-based regulation improves problem-solving performance on context-dependent problems; that is, problems where programs must adjust how they respond to current inputs based on prior inputs. Indeed, the system could not evolve solutions to some context-dependent problems until regulation was added. Our implementation of tag-based genetic regulation is not universally beneficial, however. We identify scenarios where the correct response to a particular input never changes, rendering tag-based regulation an unneeded functionality that can sometimes impede adaptive evolution. Tag-based genetic regulation broadens our repertoire of techniques for evolving more dynamic genetic programs and can easily be incorporated into existing tag-enabled GP systems.

Lalejini, A., Moreno, M.A. & Ofria, C. Tag-based regulation of modules in genetic programming improves context-dependent problem solving. Genet Program Evolvable Mach 22, 325–355 (2021). https://doi.org/10.1007/s10710-021-09406-8

• data via Open Science Framework ❋
• source code via GitHub