This repository holds the supplemental material associated with "Tag-based Genetic Regulation for Genetic Programming". Out as a preprint at the moment!
Navigation
We introduce and experimentally demonstrate tag-based genetic regulation, a new genetic programming (GP) technique that allows evolving programs to regulate code modules. Tags are evolvable labels that provide a flexible mechanism for labeling and referring to code modules. Tag-based genetic regulation extends existing tag-based naming schemes to allow programs to ''promote'' and ''repress'' code modules. This extension allows evolution to form arbitrary gene regulatory networks in a program where genes are program modules and program instructions mediate regulation. We demonstrate the functionality of tag-based genetic regulation on several diagnostic tasks as well as a more challenging program synthesis problem. We find that tag-based regulation improves problem-solving performance on problems responses to particular inputs must change over time (e.g., based on local context). We also observe that our implementation of tag-based genetic regulation can impede adaptive evolution when expected outputs are not context-dependent (i.e., the correct response to a particular input remains static over time). Tag-based genetic regulation is immediately applicable to existing tag-enabled GP systems, and broadens our repertoire of techniques for evolving more dynamic programs.
Tags are evolvable labels that can be mutated, and the similarity (or dissimilarity) between any two tags can be quantified. Tags allow for inexact addressing. A referring tag targets the tagged entity (e.g., a module) with the closest matching tag; this ensures that all possible tags are potentially valid references. Further, mutations to tags do not necessarily damage existing references. For example, mutating a referring tag will have no phenotypic effect if those mutations do not change which target tag is matched. As such, this technique allows the naming and use of modularized code fragments to incrementally co-evolve.
In the tag-based referencing example above, the call instruction uses tag 1001 to reference the closest-matching module (in this case, the yellow module tagged 0001).
Tag-based regulation allows evolving programs to instantiate gene regulatory networks using tag-based referencing. This functionality allows programs to dynamically adjust which module is triggered by a particular call based on prior inputs. Specifically, we implemented tag-based genetic regulation in the context of a linear GP system (SignalGP); however, our approach is applicable to any tag-enabled GP system.
To implement tag-based genetic regulation, we supplement the instruction set with promoter and repressor instructions that, when executed, adjust how well subsequent tag-based references match with a target module. Intuitively, promoters increase a target module's tag-match score with subsequent references, thereby increasing its chances of being triggered; repressors have the opposite effect. When determining which module to reference in response to a call instruction, each module's tag-match score is a function of how well the module's tag matches the call instruction's tag as well as the module's regulatory value.
SignalGP defines a way of organizing and interpreting genetic programs to afford computational evolution access to the event-driven programming paradigm. In SignalGP, program execution is signal-driven. Programs are segmented into genetic modules (or functions), and each module can be independently triggered in response to a signal. Each module associates a tag with a linear sequence of instructions. In this work, tags are represented as fixed-length bit strings.
SignalGP makes the concept of events or signals explicit: all signals contain a tag and any associated data. Signals can originate exogenously (e.g, from the environment or other agents) or endogenously (e.g., self-signaling). We use tag-based referencing (Spector et al., 2011) to determine the most appropriate function to automatically trigger in response to a signal. Signals trigger the function with the closest matching tag.
For a more detailed description of the SignalGP representation, see (Lalejini and Ofria, 2018).
In this work, we augment the SignalGP representation with genetic regulation, allowing programs to alter their responses to signals during their lifetime. We supplement the SignalGP instruction set with promotor and repressor instructions, which, when executed, adjust how well subsequent signals or internal call instructions match with a target function (instruction-level tags and tag-based referencing are used for function targeting).
A simple example of how genetic regulation works (in an event-handling context) is given in the figure below. First (1), an event triggers the yellow function that, when executed, (2) promotes the red function and represses itself. Finally (3), when a subsequent signal (identical to the previous) is received, it triggers the up-regulated red function instead of the yellow function.
We compared the performance of regulation-enabled and regulation-disabled SignalGP on five problems:
- Signal-counting Problem
- Contextual-signal Problem
- Independent-signal Problem
- Boolean-logic Calculator Problem (prefix notation)
- Boolean-logic Calculator Problem (postfix notation)
The signal-counting, contextual-signal, and prefix notation calculator problems each required programs to dynamically adjust their responses to particular inputs over time. The independent-signal and postfix notation calculator problems did not require programs to adjust responses to inputs over time.
- Proof of method: we observed the evolution of programs capable of leveraging tag-based regulation to dynamically adjust module associations over time.
- We found that tag-based regulation improved problem-solving performance on context-dependent problems (i.e., problems in which the appropriate response to a particular input changes over time).
- We found that our implementation of tag-based regulation can impede adaptive evolution on problems that do not require programs to adjust responses to particular inputs over time.
The source code for our experiments is included in this repository (in the source/ directory). Our experiments are implemented in C++ using the Empirical library and an external implementation of SignalGP. We conducted our experiments using the high-performance computing resources providing by the Institute for Cyber-Enabled Research at Michigan State University.
We provide a step-by-step guide for compiling and running the software we used to run our experiments (including requisite dependencies): ./documents/running-experiments.md.
We conducted our data analyses using a combination of Python (version 3.8.6) and R (version 4.0.2). Python is used primarily for data wrangling, and R is used for stats and graphs/visualizations. See our supplemental material for fully-detailed data analyses/visualizations (including source code)!
In addition to our source code (found in this repository), we compiled our data analyses and supplemental documentation (including guides for replication and data availability) into a nifty web-hosted book using bookdown and GitHub pages.
➡️ Find our supplemental material here ⬅️
- documents/ contains supplemental documentation for our methods. These documents are best viewed in our compiled supplemental material
- experiments/ contains the configuration files, HPCC job submission scripts, and data analysis scripts for our experiments.
- media/ contains images used throughout repository documentation.
- scripts/ contains several root-level utility scripts for data wrangling and for generating input/output examples for test-based problems. Note that experiment-specific scripts are located in their associated experiment directory.
- source/ contains the C++ implementations of our genetic programming experiments.
Lalejini, A., & Ofria, C. (2018). Evolving event-driven programs with SignalGP. Proceedings of the Genetic and Evolutionary Computation Conference on - GECCO ’18, 1135–1142. https://doi.org/10.1145/3205455.3205523
Spector, L., Martin, B., Harrington, K., & Helmuth, T. (2011). Tag-based modules in genetic programming. Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation - GECCO ’11, 1419. https://doi.org/10.1145/2001576.2001767