Signal GP, an Introduction

Posted November 3, 2017 by Alex Lalejini in Research, Software Development / 0 Comments

Genetic programming (GP) is the application of natural principles to evolve computer programs rather than writing them by hand. Here, I introduce Signal GP, a new type of linear GP representation designed to more directly capture the event-driven programming paradigm, allowing evolved programs to handle signals from the environment or from other agents in a more biologically inspired way than traditional linear GP representations.

GP is successful across a growing set of problem domains. Signal GP targets problems where programs, much like biological organisms, must react on-the-fly to signals in the environment or from other agents.

I’ll address the following questions in this blog post: What is linear genetic programming? What exactly is the event-driven programming paradigm, why is it so powerful, and why do we want to capture it in GP? And, how exactly does Signal GP capture the event-driven paradigm?

Computer Program Husbandry (i.e. genetic programming)

Genetic programming starts with a primordial ooze of randomly generated computer programs composed of available programmatic ingredients and then applies the principles of animal husbandry to breed a new (and often improved) population of programs. — John Koza in (Koza, 1995)

There are many flavors of genetic programming, each differing in how their programmatic ingredients are organized. Tree-based GP representations organize programs as tree structures (Koza, 1992). Cartesian GP represents programs as graphs (Miller and Thomson, 2000). Linear GP represents programs in a way more directly familiar to software developers: as linear sequences of instructions (Brameier and Banzhaf, 2007).

Linear genetic programs traditionally follow an imperative paradigm where computation is driven procedurally, often starting at the top of the program and proceeding in sequence, instruction-by-instruction, jumping or branching as dictated by executed instructions. Linear genetic programs might look like C programs or assembly code. For those familiar with the Avida Digital Evolution Platform, the genomes of digital organisms in Avida are linear genetic programs (shown in Figure 1). Because linear genetic programs are in such a familiar form — sequences of program instructions — it’s not terribly difficult to trace evolved programs instruction-by-instruction to get an understanding of how the program’s algorithm works.

figure_1
Fig 1: Digital organism in Avida where the genome (stored in Memory) is a linear genetic program. Figure from (Ofria et al., 2009).

What is event-driven computation?

In event-driven computation, a program’s execution is driven primarily by signals (i.e. events), easing the design and development of reactive programs. Thus, the event-driven paradigm is particularly useful in domains such as robotics or user interface design.

Let’s imagine a scenario where we have the network of agents depicted in Figure 2, and each agent in the network is controlled by a linear program. In this thought exercise, we’ll be responsible for writing the program for the node labeled X in the center of the network.

figure_2
Fig 2: Example distributed network of computational nodes where node X is directly connected to: NAO, Echo, Hal 9000, BB-8, Roomba, and R2-D2. Image credits here.

Let’s say that, in this scenario, node X must listen for messages from its neighbor, Roomba, and when node X receives a message from Roomba, node X must perform a particular computation on the contents of the message. How might we implement this in a traditional linear program? No problem here. We’ll just set up a loop that continuously checks node X’s message inbox for messages from Roomba, and if a message from Roomba is detected, our program can then perform the proper computation.

While(alive) {
  While(!message_inbox.empty()) {
    message = message_inbox.pop_front();
    if (message.source == "Roomba") {
      // Perform necessary computations
      ...
    }
  }
}

Okay, now let’s say we need node X to perform a different computation on the contents of any messages received from NAO. No problem, we can just add that into the loop right after we handle any detected messages from Roomba.

While(alive) {
  While(!message_inbox.empty()) {
    message = message_inbox.pop_front();
    if (message.source == "Roomba") {
      // Perform necessary computations.
      ...
    } else if (message.source == "NAO") {
      // Perform necessary computations.
      ...
    }
  }
}

What if node X needs to be able to respond uniquely to messages from all of its neighbors? And, for added complication, let’s also say that node X has an ambient light sensor module that will send a message to node X’s control program (i.e. the linear program we’re writing) when the ambient light exceeds a certain threshold so that node X can respond appropriately. We can add all of these checks in our original loop, checking for messages from other agents and checking for messages from node X’s sensor module and handling each appropriately. This really isn’t even that bad if the programming language we’re using has functions: we write a handler function for each message type, and in every iteration through the program’s loop, we can call the appropriate function for each received message.

While (alive) {
  While (!message_inbox.empty()) {
    message = message_inbox.pop_front();
    if (message.source == "Roomba") {
      HandleMessageFromRoomba(message);
    } else if (message.source == "NAO") {
      HandleMessageFromNAO(message);
    } else if (message.source == "Echo") {
      HandleMessageFromEcho(message);
    } else if (message.source == "Hal 9000") {
      HandleMessageFromHal9000(message);
    } else if (message.source == "BB-8") {
      HandleMessageFromBB8(message);
    } else if (message.source == "R2-D2") {
      HandleMessageFromR2D2(message);
    } else if (message.source == "Ambient-Light-Sensor") {
      HandleAmbientLight();
    }
  }
}

If we shift our terminology a bit, it’s clear that we’ve implemented node X’s procedural program in an event-driven way: messages from sensors or other agents are events, and the functions for processing those messages are event handlers. In event-driven computation terminology, our outermost loop is a dispatcher, dispatching received events to the appropriate event handler.

As I hope this example made clear, the event-driven paradigm is a useful design philosophy for creating programs that we want to be reactive. However, our example program is still implemented in an imperative representation where computation is not fully driven by events. The example program must poll periodically (every time we go through the outermost loop) for events instead of responding to them on-the-fly. Imagine that we have many more events that our program must be able to detect and respond to; polling may become incredibly cumbersome. Signal GP gives linear genetic programming more direct access to the event-driven design philosophy, making reactive programs easier to evolve.

Signal GP

Signal GP extends the domain of linear genetic programming by directly capturing the event-driven programming paradigm. While most linear genetic programming representations are Turing Complete (i.e. they can theoretically encode programmatic solutions to any computable problem), depending on how programs are represented and interpreted, different types of programs are more or less challenging to evolve using genetic programming. Moreover, in environments where timing and program response time is critical, how efficiently a representation is able to encode a response to an environmental signal matters. The Signal GP representation has the event-driven programming paradigm baked in, making reactive programs easily evolvable.

Signal GP Programs
In contrast to traditional linear GP where programs consist of a linear sequence of instructions, programs in Signal GP are made up of a set of functions where each function is a linear sequence of instructions. Additionally, each function has an associated bit string affinity that can be thought of as the function’s name. Affinities in Signal GP are analogous to the concept of tags conceived by Holland in (Holland, 1993) and more recently demonstrated in (Spector et al., 2011). Figure 3 provides a visual comparison of Signal GP programs and traditional linear GP programs.

figure_3
Fig 3: The contrasting structures of a traditional linear GP program and a Signal GP program.

Signal GP makes explicit the concept of events (Figure 4). At a high level, events are packets of information, and, like functions, every event has an associated affinity.

Fig 4: The basic components of an event in Signal GP.
Fig 4: The basic components of an event in Signal GP – a bit string affinity and some associated data.

When a Signal GP program must react to an event, we can try to ‘bind’ the event to a function in the program (Figure 5). Here, binding is simple: we just look for the function in the program with the most similar affinity to the event’s affinity and call that function using the event’s data as input. Events can be self-generated, generated by the environment, or generated by other agents. In this way, event handling intuitively facilitates agent-agent, agent-environment, and agent-self interactions.

Fig 5: Depiction of event handling in Signal GP. (1) The program must respond to an event. (2) The event's affinity is matched against each of the affinities for each function in the program. (3) The event binds to the function with the strongest match.
Fig 5: Depiction of event handling in Signal GP. (1) The program must respond to an event. (2) The event’s affinity is matched against each of the affinities for each function in the program. (3) The event binds to the function with the strongest match.

Function affinities can also be used to call functions from within a program. We can have an explicit ‘Call’ instruction with an associated affinity that, when executed, binds (i.e. calls) the function with the most similar affinity (Figure 6). It’s also easy to imagine a ‘Send-Message’ instruction that has an associated affinity. When a Send-Message instruction is executed by an agent, we can generate an event with the same affinity as the executed Send-Message instruction and send that event to another agent.

figure_6
Fig 6: Depiction of how internal function calls can work in Signal GP.

This method of using affinities for event and function call binding is a form of tag-based referencing (Spector et al., 2011) inspired by cell signal transduction and the way communication among nodes is implemented in the Robot Operating System (ROS). This type of function-referencing approach allows programs to have an arbitrary and dynamic number of functions without needing to add special instructions to the instruction set to refer to them. If function affinities and the affinities of instructions that directly call functions or that generate events are allowed to mutate, evolution can easily rewire which functions are called by particular call instructions and which functions are used to handle particular events.

Signal GP Virtual Hardware
A computer program does nothing without the appropriate hardware to run it. Likewise, Signal GP programs aren’t interesting outside of the context of the virtual hardware designed to run them. I don’t want to get terribly bogged down in details in this introductory blog post, so I’ll try to keep the description of my Signal GP virtual hardware at a high level. In case you’re curious about exactly how I’ve implemented things, my implementation of Signal GP can be found in the Empirical library: Empirical Github repository.

The Signal GP virtual hardware is made up of several components and is depicted in Figure 7.

figure_7
Fig 7: Signal GP virtual hardware.

The Signal GP virtual hardware has an arbitrary number (theoretically unbounded, but practically bounded) of execution cores that run in parallel. When the virtual hardware advances by a single unit of computational time, each active core on the virtual hardware advances by a single step (i.e. executes a single instruction). Each core can be dedicated to handling a separate event, allowing the Signal GP hardware to handle multiple events simultaneously. Shared memory is accessible by all cores, allowing them to store and share global information. The event queue stores received events that are waiting to be dispatched and handled.

Each core maintains a call stack that stores information about the active function calls on that core. The state of the current active function call for a given core resides at the top of that core’s call stack. Each call state has its own local memory, input memory, and output memory. Local memory is typically what instructions that perform mathematical/computational operations act on. Input memory is loosely analogous to function arguments, and output memory is loosely analogous to return memory. By convention, local and shared memory are readable and writable, input memory is read-only, and output-memory is write-only (however, these conventions are not enforced; anyone can write Signal GP instructions that break convention).

Event Handling
The Signal GP virtual hardware dispatches all accumulated events in the event queue at the beginning of every unit of computational time; the delay between receiving an event and being able to react to an event is, at most, a single unit of computational time. On an event dispatch, the hardware searches for the most appropriate function to bind to the event by ranking the affinity similarity scores between the event and each function in the program. Binding can be done probabilistically (i.e. bind to each function with a probability proportional to their affinity match scores) or deterministically (i.e. always bind to the function with the highest affinity match score).

When a function is selected to handle an event, a new core is created, and the selected function is called on that execution core. The input memory of the new call state, which is created as a result of the function call, is populated with the data contained in the event. In this way, events are able to pass information to the function that handles them.

Function Calls
As mentioned previously, Signal GP functions may be called from within a program via a ‘Call’ instruction. Like events, call instructions also have an affinity. And again like events, the call instruction’s affinity is used to determine which function it calls. The conventional difference between calls and events, however, is that calls do not spin up a new processing core. I say convention because the Signal GP instruction set is flexible: if you want a call instruction that calls a function on a new core, it’s trivial to add it to the instruction set.

When a function is called, a new call state is created with empty input, local, and output memory. This call state is pushed onto the call stack of the execution core where the call happened. The input of the new call state is then populated with the local memory of the caller’s state (i.e. the arguments to the newly created function are the local memory contents of the caller). When a function call returns by reaching the end of the function’s instruction sequence or by executing a return instruction, the returning function state is popped from its call stack, and any data written into the output memory is returned to the local memory of the caller state. In this way, function calls can be thought of as operations over the caller’s local memory.

For More Details

In my description of Signal GP, I glossed over many of my implementation details, such as:

  • Q: What does the default instruction set look like?
    • A: Reasonable. It covers the basics: loops, branching, messaging, function calling, basic memory manipulation, and basic mathematical operations. My implementation is flexible; it’s trivial to customize the instruction set.
  • Q: What exactly happens every time the virtual hardware advances by a single unit of computational time?
    • A: 1) Process event queue. 2) Advance each active core by a single CPU cycle. 3) Check for and clean up any dead cores (i.e. cores with no active functions/cores with empty call stacks). 4) Create any new cores that were requested during execution.
  • Q: How exactly does memory access work?
    • A: In my current implementation memory addresses are integers and memory values are doubles. If a memory location that has yet to be set is accessed, populate the location given by the address with a default value before reading.

For full details, my implementation is here. However, I want to stress that the core ideas behind Signal GP are independent of my implementation. I am most interested in communicating the core ideas of Signal GP: how programs are organized, how events are handled, and how functions are called.

My primary goal for Signal GP is to capture event-driven programming within a linear genetic programming representation, providing a more natural representation for evolving algorithms for embedded systems, robots, agents in a distributed network, or anything where computation is driven primarily by external forces.

An Epilogue: Chimera GP

My conception of Signal GP as a linear genetic programming representation is a historical contingency. I have a soft spot in my heart for linear genetic programming representations. I love being able to reverse engineer my evolved algorithms, which is made easier if the evolved algorithms are represented in a familiar form: a sequence of instructions. I (and likely many others) find that reverse engineering evolved solutions in representations like artificial neural networks (ANNs), Markov Network Brains, etc. is often an unpleasant challenge; thus, my attraction to linear genetic programming.

Chimera GP extends Signal GP functions to arbitrary representations. At their core, functions in Signal GP have the following properties:

  • A function can take input (via its input memory) and can produce some output (via its output memory, by manipulating shared memory, or by broadcasting a message).
  • A function has an evolvable name (i.e. an affinity).

It doesn’t actually matter what representation sits underneath each function. It doesn’t even matter that all of the functions in a program are of the same representation! For example, we could have a program with any number of linear GP functions, ANN functions, Markov Network Brain functions, Cartesian GP functions, or hand-written functions (e.g. particle filters, complex mathematical transforms, etc.).

I don’t think the following is a very controversial statement: different representations are better at accomplishing different tasks. If I’m evolving a controller for a robot, I can easily imagine that certain aspects of robot control are best handled by some form of genetic program (i.e. linear, tree-based), while other aspects are best handled by an artificial neural network or a Markov Network Brain, and still other aspects might be best handled by a hand-written, human-engineered algorithm.

That’s the pitch for Chimera GP: a modification of Signal GP that allows for functions to be an arbitrary representation.

A Call for Feedback

My inspirations for Signal GP come from a messy amalgamation of linear GP representations, Koza’s automatically defined functions (Koza, 1994), tag-based references (Holland 1993; Spector et al., 2011), artificial gene regulatory networks, cell signal transduction, and my experience writing robotics software. My knowledge and familiarity with the related literature, however, is not even close to exhaustive. Thus, I would very much appreciate the full range of feedback on Signal GP (and Chimera GP).

Do you have questions? Were my explanations clear? Has this been done before? Do you have suggestions? Comments? Concerns? Ideas for applications? Insights from biology, existing evolutionary computation literature, or anywhere else? A few words of encouragement or discouragement? Drop me a comment or an email (alex@lalejini.com).

References

Brameier, M. F., & Banzhaf, W. (2007). Linear genetic programming. Springer Science & Business Media.

Holland, J. (1993). The effect of labels (tags) on social interactions (pp. 532-554). Santa Fe Institute Working Paper 93-10-064. Santa Fe, NM.

Koza, J. R. (1992). Genetic programming: on the programming of computers by means of natural selection (Vol. 1). MIT press.

Koza, J. R. (1994). Genetic programming II: Automatic discovery of reusable subprograms. Cambridge, MA, USA.

Koza, J. R. (1995, August). Gene duplication to enable genetic programming to concurrently evolve both the architecture and work-performing steps of a computer program. In IJCAI (1) (pp. 734-740).

Miller, J. F., & Thomson, P. (2000, April). Cartesian genetic programming. In European Conference on Genetic Programming (pp. 121-132). Springer, Berlin, Heidelberg.

Ofria, C., & Wilke, C. O. (2004). Avida: A software platform for research in computational evolutionary biology. Artificial life, 10(2), 191-229.

Spector, L., Harrington, K., Martin, B., & Helmuth, T. (2011). What’s in an evolved name? the evolution of modularity via tag-based reference. In Genetic Programming Theory and Practice IX (pp. 1-16). Springer New York.

Image credits (from Figure 2):
Amazon Echo photo by Frmorrison at English Wikipedia / CC BY-SA 3.0
BB8 / CC0
HAL’s camera eye image by Cryteria / CC BY 3.0
NAO Robot photo by Softbank Robotics Europe / CC BY-SA 4.0
R2-D2 / CC0
Roomba Photo by CEphoto, Uwe Aranas / CC BY-SA 4.0

Alex Lalejini

I am a doctoral student in the Digital Evolution Laboratory at Michigan State University in Computer Science and Ecology, Evolutionary Biology, & Behavior. I use digital evolution to study the evolution of distributed systems of both the biological and computational sort. My interests include exploring the stepping stones for major evolutionary transitions in individuality and leveraging those stepping stones to evolve distributed computational systems.

More Posts - Website - Twitter

Leave a Reply