Supplemental Material for Tag-based Genetic Regulation for Genetic Programming
2021-03-28
Chapter 1 Introduction
This is the supplemental material for our work, ‘Tag-based Genetic Regulation for Genetic Programming’. This is not intended as a stand-alone document, but as a companion to our paper.
1.1 About our supplemental material
As you may have noticed (unless you’re reading a pdf version of this), our supplemental material is hosted using GitHub pages. We compiled our data analyses and supplemental documentation into this nifty web-accessible book using bookdown.
The source code/configuration files for this supplemental material can be found in this GitHub repository.
Our supplemental material includes the following:
- Data availability (Section 2)
- Step-by-step guide to compiling and running our experiments (Section 3)
- More details on the SignalGP representation used in this work (Section 4)
- A formal definition of the Streak metric used to quantify tag similarity in this work (Section 5)
- Visualizations of the exponential regulator used in this work (Section 6)
- Fully-detailed analysis scripts for each experiment (including source code)
- Hand-coded SignalGP example programs (Section 12)
1.3 Research overview
1.3.1 Abstract
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.
1.3.2 Tag-based Referencing
Tags are evolvable labels that can be mutated, and the similarity (or dissimilarity) between any two tags can be quantified (Spector et al. 2011). 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.
Example of tag-based referencing.
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).
1.3.3 Tag-based Regulation
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.
1.3.4 SignalGP
Cartoon overview of SignalGP.
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 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).
1.3.4.1 Genetic Regulation in SignalGP
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.
Example of tag-based genetic regulation in SignalGP.
1.3.5 Experiments
We compared the performance of regulation-enabled and regulation-disabled SignalGP on five problems:
- Signal-counting Problem
- Contextual-signal Problem
- Indepedent-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.
1.3.6 Results
- 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.
References
Lalejini, Alexander, and Charles Ofria. 2018. “Evolving Event-Driven Programs with SignalGP.” In Proceedings of the Genetic and Evolutionary Computation Conference on - GECCO ’18, 1135–42. Kyoto, Japan: ACM Press. https://doi.org/10.1145/3205455.3205523.
Spector, Lee, Brian Martin, Kyle Harrington, and Thomas Helmuth. 2011. “Tag-Based Modules in Genetic Programming.” In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation - GECCO ’11, 1419. Dublin, Ireland: ACM Press. https://doi.org/10.1145/2001576.2001767.