Evolutionary Systems

There have been more than four decades of computational systems inspired by natural evolution. It has become a major field of machine learning and optimization. Beyond AI, it has been used in hardware and circuit design, robotics, and more recently in industrial design and architecture. It has of course also been deeply explored in art and music.

Karl Sims

Natural and artificial evolution

The theory of natural evolution combines population, diversity, heredity and selection. Evolution requires a population of individuals that exhibit diversity (both similarities and variations between each other, both within and between species). These individuals can produce new individuals; offspring that exhibit similarites with the parent(s) through heredity. However not all of the population can successfully reproduce. Any factor that affects the possibility of an individual reproducing, thus also affects what characteristics are inherited in the population as a whole. Charles Darwin's theory of natural selection, proposed in 1859, is that the section of the population that can reproduce is not entirely random, but rather is regulated by interactions between inherited characteristics and environmental constraints (such as available food, populations of symbionts, predators and parasites, and so on). Accordingly, the characteristics of a species may change over time (evolution), forming a history that can be investigated through the fossil records.

Origin of the Species

Artificial evolution is a form of computational simulation whose process mirrors the abstract structure of natural evolution:

The main systematic differences are that the underlying mechanisms specified by us in advance, as are the initial populations and environmental conditions (if any). Most importantly, the mechanism of selection is usually predetermined. And of course, artificial evolution occurs in a much simpler substrate than real chemistry.

A fantastic list of practical applications of genetic algorithm & evolutionary programming

Some inspiration

Karl Sims' Genetic Images -- and the 1991 Siggraph Paper

Karl Sims: Evolving 3D Morphology and Behavior by Competition, 1994:

Scott Draves, “Evolution and Collective Intelligence of the Electric Sheep,” The Art of Artificial Evolution, 2008.

High Fidelity Sample from Scott Draves on Vimeo.

Evolving 2D cars Evolving soft robots Evolving neural networks to play Mario:

An excellent discussion of the genetic algorithm in art and its relation to Deleuze, by Manuel Delanda

Subtleties and misconceptions

Darwin's theory is sometimes misconceived as "survival of the fittest" or even the competitive "law of the jungle", but evolution turns out to be quite a bit more subtle than this.

Heredity and variation: genetics

In 1865 Mendel proposed that characteristics are transmitted to offspring through particles of matter (which we now call genetic material). Schroedinger conjectured that these materials must be aperiodic crystals, and the actual structure of DNA was identified several years later. The "modern synthesis" in biology today has integrated genetics with natural evolution, through the interaction of genotypes and phenotypes:

Hence the modern synthesis requires not only a model for how variation is introduced, but also how genetic material is transfered, how the phenotype accordingly emerges from the genotype (developmental models), and what other roles it plays. It is increasingly being understood how the complexity of the environment and materials of life are likely as much or more responsible for the variety of life than the genes themselves, however, these mechanisms are still in the progress of being revealed.

Briefly: a biological cell contains a vast array of different proteins, whose concentrations determine structures and behaviors of the cell. The proteins are specifed by information in the DNA genetic material (grouped physically into chromosomes). When a cell reproduces by mitosis, a copy of the DNA is made in the new cell. The sections of a DNA chromosome that code for behavior are called genes. These regions are constantly being transcribed, producing a specific RNA strand for each coding gene region which is in turn used to produce a specific protein; the protein string immediately folds up (in a way we cannot yet simulate) into a particular reactive shape which specifies the protein's behavioral role in the cell. This is a one-directional flow of information: Coding DNA -> RNA -> folding -> active protein. In addition to coding regions genes may also have regulatory region which can react with specific proteins to activate or inhibit the coding-protein system, forming a complex regulatory network of interactions by which one gene can activate or inhibit another, and also specify changes of behavior of a cell according to environmental conditions such as chemical signals. These networks can be fantastically complex even in very simple organisms, according to the scientific results of functional genomics. Between the coding and regulatory regions of DNA, there are huge sections of nongenic DNA, whose role (or lack thereof) is not yet understood.

Rendering

The current theory of cell replication and DNA transcription been beautifully illustrated by Drew Berry; and more of his animations here

Genetic variation can occur during replication of the genome, such as copying-error mutations (reversals of segments, insertion & removal of segments, changing individual elements in the sequence, and pair-wise substitution over whole sections) and recombination (taking sections from two different parent genes to construct a new child gene).

Artificial evolution

An artificial evolutionary system thus requires:

  1. A representation of genotypes.
  2. A mechanism to produce phenotypes from genotypes (development).
  3. Mechanisms to introduce diversity to a genotype.
  4. A mechanism to evaluate the fitness (or viability) of phenotypes.

These components must be provided by the author. The system is then run by these steps:

  1. Initialization of a 'seed' population of genotypes
  2. Development of phenotypes from the genotypes
  3. Evaluation and selection of best/viable candidates of phenotypes, according to fitness criteria or ongong viability conditions, to choose who may reproduce.
  4. Reproduction, creating new genotypes by applying mechanisms of variation, according to variation rates/probabilities.
  5. Repeat from step (2) or terminate if a terminating condition is satisfied (such as sufficient fitness).

Steps 2-5 may be run in lock-step, or asynchronously with overlapping individual life-spans.

Genetic representation

Many systems represent genetic information as a sequence of data, such as a string of characters or binary digits. Some systems use more elaborate structures (trees, networks), but these are usually reducible to and encoded as linear sequences. After all, our genes wind up in complex structures with different reactive regions, but at the lowest level are just a long singular chain of A, G, C or T molecules.

The simplest systems have a fixed length, but nature shows quite a lot of variance (not particularly correlated with the size, complexity, or evolutionary age of a species).

Initializing the genotypes implies generating randomized candidates that stay within its bounds but hopefully give a sufficiently diverse range of the possibilities of the genotype. For a simple sequence of bits, symbols, or numbers, this is fairly easy to do.

Development

In some systems the developmental process is little more than a trivial mapping, but this potentially misses an entire and fascinating source of diversity. Incorporating more complex developmental models can lead to geometric variations that are not stored as simple parameters, to repeated segments and recursive structures, to symmetries, and to the re-application of common toolboxes toward a widely differing set of purposes -- all things that are evident in biological evolution.

Selection

For problem solving in data mining, engineering, design, architecture, etc.: If the fitness criterion is static and designed around a particular problem we wish to find a solution for, evolution can help evaluate & test candidate solutions and selectively breed them to produce better solutions, ideally converging on an optimal one, without having to understand or derive by proof. It is a form of optimization. However this process may take a long time or a lot of processing power to find a satisfactory result, or may not reach a result at all. Not all problems are suitable for evolutionary search.

Evidently, these systems differ markedly from natural evolution by having a static measure, and thus a singular teleological character, a meaningful sense of progress, across the entire history of the system. This is more akin to selective breeding than natural evolution.

Note that simply taking the best candidate alone is not necessarily the ideal strategy; selecting randomly by proportion to fitness ("roulette wheel" selection) may better overcome local maxima.

For art, music, and other less formalized domains we may need to consider other methods of selection, since a formal measure may not be possible, or the problem may not be clearly statable in advance. E.g. can we measure aesthetic quality in formal terms?

Variation

The mechanisms of variation possible partly depend on the representation chosen. The two most common principles of variation in artificial evolution are naturally inspired:

Why use reproduction for evolution? In the face of an unpredictable environment, we cannot know which strategy will be best; we can try small variations, and hedge our bets by making very many of them (population diversity). An individual loss is not catastrophic, but a few successes can be learned from. Furthermore, the face of unpredictibility implies that what was true today may not be tomorrow, so the flexibility to avoid timeless commitment is also a good strategy; but the inheritance of choices is a useful option when the environment retains some stability. If the world were fully predictable, a rational, teleological, monothematic strategy would be preferable. But the world isn't totally random either (if it was, there would be no valid strategy worth pursuing.)

As with temperature-like parameters we saw in CA, a crucial factor in evolution is the rate or probability of variation. Too much, and the population may never significantly diverge from a randomly initialized one; too little, and it may find itself stuck on the first solution it finds, with a largely homogenous population. It may be wise to have different mutation rates for different genes, or for different members of a population, or by fitness rank etc. It is likely desirable to gradually reduce mutation rates over time, unless the population appears to be stagnating. (See also simulated annealing.)


A trivial string generator

Just to practice the mechanics, we can start by evolving sentences toward a desired result. Each gene is an integer, which is mapped to a word from a predefined list:

// the desired result:
var target = "the quick brown fox jumped over the lazy dog";

// the set of components:
var dictionary = ["I", "a", "an", "bleep", "blown", "bog", "box", "broad", "brown", "bumped", 
    "cat", "cog", "coloured", "colourful", "colourless", "crazy", "creep", "crown", "dig", 
    "do", "dog", "door", "dot", "ever", "fit", "fix", "flick", "for", "fox", "frown", 
    "glean", "great", "greed", "green", "greet", "hazy", "he", "hog", "ideas", "idols", 
    "in", "it", "jumble", "jumped", "jumper", "jumps", "last", "lazy", "leaped", "lumped", 
    "maze", "of", "offer", "ogre", "older", "on", "or", "over", "quick", "quite", "rapid", 
    "she", "sheen", "sheep", "sick", "sleep", "slept", "slow", "spelt", "spilt", "the", 
    "town", "under"];

// initial:
var geno = [];
for (var i=0; i < 9; i++) {
    geno[i] = random(dictionary.length);
}
// develop:
var pheno = [];
for (var i=0; i < geno.length; i++) {
    pheno[i] = dictionary[ geno[i] ];
}
pheno = pheno.join(" ");

To evaluate, we could compare how many of the right characters are in the right places:

var err = 0;
for (var i=0; i < pheno.length; i++) {
    if (pheno.substr(i, 1) != target.substr(i, 1)) {
        err++;
    }
}
// make it fair between long & short strings:
err /= pheno.length;

To convert this error into a fitness, where fittest is 1 and least fit is zero, we could apply a 1/(1+n) mapping:

var fitness = 1 / (1 + err);

This gives us all the basic components we need to generate a random population as genotypes. We already know how to develop and evaluate such a genotype, and storing several in a population is trivial.

It is generally useful to sort a population by fitness, which can be done like so:

// sort the population by comparing pairs
// as a result, the fittest candidate will be in population[0]
population.sort(function(a, b) { return b.fitness - a.fitness; });

After sorting it is convenient to print out the candidates, their fitness, etc, so we can see how the evolution proceeds.

After evaluating, we create a new generation of candidates, broadly derived from the previous, but with fitter candidates being more likely to be progenitors. The simplest method is to pick a parent at random, but biasing toward the lower indices. (A simple trick to do this is for the nth child to use a the parent at index random(n).)

This is called stochastic universal sampling: it draws samples from the entire range, but selects fitter individuals more often than less-fit candidates.

We must also introduce some variation (mutations) while generating new genotypes at this point. The simplest method is to introduce a branch with a predetermined probability to randomize a gene rather than copy from the parent, e.g.:

// copy or mutate genes:
for (var j = 0; j < gene_size; j++) {
    // mutate?
    if (random() < mutability) {
        child[j] = random(gene_range); 
    } else {
        // copy:
        child[j] = parent[j];
    }
}

Does it work? If not, can you think of ideas why -- and any ideas to improve it?

Here's something like this in the editor.

Does it sometimes seem to get stuck? Can you suggest why? Can you think of any way to modify the mutation, evaluation, or even the genetic representation to overcome this?

Here's a variant, using the concept of the longest common substring as the measure of fitness

As an extension, can you imagine working from a much larger lexicon of words, and coming up with a fitness measure that evaluates according to how much sense a randomized sentence makes? Perhaps take a look at n-grams, and/or grammar parsing, and/or methods used in natural language generation. Or, since English syntax and semantics are pretty hard, how about generating random but syntactically correct programs?

A simple math solver

The string example was a little silly, but let's say we want to write a program (the phenotype) that can solve math problems. To start as simple as possible, we can restrict our programs to numerals and symbols of basic arithmetic:

var symbols = ["+", "-", "*", "/", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0"];

To generate a random program, of say, length 10 characters, and run it, we would do something like this:

// fill an array:
var arr = [];
for (var i=0; i<10; i++) {
    // pick a symbol at random to add:
    arr[i] = symbols[random(symbols.length)];
}
// convert the array of symbols to a string of code:
var code = "return " + arr.join("");
// convert to an executable function:
var f = new Function(code);
// run it to get the result
console.log(f());

The chances are, the generated code is garbage, and might well throw an error, or return a meaningless result such as Infinity or NaN. These errors could break or throw off our simulation, but we can trap them safely as follows:

try {
    // convert to an executable function:
    var f = new Function(code);
    // run it to get the result
    var result = f();
    if (result != Infinity && result != -Infinity && result == result) {
        console.log(result);
    }
}

Now we can evaluate the fitness of our result, relative to a target number. We can take the absolute difference, and then put this through a 1/(1+n) mapping as before. This mapping is somewhat arbitrary, but works for our purposes here:

fitness = 1 / 1 + (Math.abs(result - target));

Here's something like this in the editor.

With this in play, we should already see some clear evolutionary behaviour. You may notice punctuated equilibria. Run the simulation many times, and you may notice that the fittest candidate is not always converging to the same result. There are clearly multiple distant fitness peaks here.

You may notice that the code generated sometimes looks odd -- and that the evolution has discovered tricks such as adding numbers multiplied by zero, prefixing zeroes to numbers, and even placing two slashes to create a comment (followed by "junk DNA"), in order to get a result with the specific gene length. We could easily prevent this by turning our "/" symbol into a " / " symbol, but perhaps there is an advantage not to?

Try changing the genome size, the population size, and the mutation rates, to see how it changes.

Try playing with the symbol list. What happens if you add the "." character? How about "(" and ")"?

The mutation rate acts a bit like a temperature control -- too high and good results can't remain viable, too low and it takes to long to get anywhere. Larger populations help to generate more chances of leaping off a local peak. Too short genome sizes can be a tough challenge, but too long genomes make it less likely to find a result quickly -- and add more noise. Is there a way to make genome size variable, and give shorter results higher fitness? What other mutation methods could help? What other developmental models could be tried? Is there a better way to pick parents?

Generally, by observing the behaviour, what insights can you draw, and what ideas have you for improving it?

How would you be able to add operators such as Math.sin()?

What other problems could you imagine addressing, other than calculating numbers? (What kinds of problems is this method suited for?)

Tournament Selection

We can continue using the fitness-proportionate selection as before, via stochastic universal sampling, however many systems use a different form of selection known as tournament selection, in which a number of individuals are chosen at random from the population to create a temporary neighbourhood set, and the fittest of this neighbourhood set is chosen as parent to create a new individual. (Or sometimes, a weighted probability veering toward the fittest in the neighbourhood set, to make it less deterministic.)

In part this helps to mirror the spatial/network effects of populations, in that it is unlikely for every member of a population to meet every other; selection is made on the somewhat random subset of the population that is encountered.

Selection pressure is easily adjusted by changing the tournament neighbourhood set size. If the size is larger, weak individuals have a smaller chance to be selected.

Here's the Pi hunting example modified to use probabilistic tournament selection


Aesthetic selection of biomorphs

Biomorphs are virtual entities that were devised by Richard Dawkins in his book The Blind Watchmaker as a way to visualize the power of evolution. Dawkins used a simple symbolic rendering of lines at fixed angles, grown in a kind of tree structure, as his phenotypes. Of a given generation, he selected the biomorph he found most aesthetically pleasing, making this the parent of the next generation.

biomorph

Adding new lines (or removing them) based on simple developmental rules offered a discrete set of possible new shapes (mutations), which were displayed on screen so that the user could choose between them. The chosen mutation would then be the basis for another generation of biomorph mutants to be chosen from, and so on. Thus, the user, by selection, could steer the evolution of biomorphs. This process often produced images which were reminiscent of real organisms for instance beetles, bats, or trees. Dawkins speculated that the unnatural selection role played by the user in this program could be replaced by a more natural agent if, for example, colourful biomorphs could be selected by butterflies or other insects, via a touch sensitive display set up in a garden.

Check out this biomorphs recreation online!

Turtle graphics

One of the simplest ways to create a biomorph is to interpret strings as instructions for another program. The genotype is a string of symbols, the phenotype is the graphics that result. The classic example is using them as instructions for a "turtle graphics" interpreter. Our alphabet & semantics could be something like this:

One of the advantages of using strings of symbols as genotypes is their readability, but another is the flexibility to perform different kinds of mutations:

Some of these mutations can change the length of the string. It may be advisable to add limits on the minimum or maximum length of the string mutations can produce.

Now we can show all members of a generation side-by-side, and use the mouse to choose the member we prefer to form the parent of the next generation.

See this example of evolving biomorphs

Here's a variation of the biomorphs example that displays candidates on a grid

Possible extensions:

The past point is important to consider. A convincing form of bilateral symmetry (something found in many organisms) can be achieved by L-system production rules, rather than by embedding this into the interpreter.

Examples of aesthetic selection from previous classes

Development & meta-evolution

In some cases, there may be several stages of code development. The biomorphs example hints at this, and already grants built-in symmetries and modular structures as are frequently found in nature -- this is partly why we respond to them. But the developmental approach can be taken much further. Sims' evolved virtual creatures had a genotype that encoded a LISP function (the developmental system), which when run would produce a body shape, but also produced an executable function for behaviour (the neural system). That is, the genetic code produces a developmental program that produces a neural program. More generally, since we are evolving code, we may want to the genome to produce re-usable subroutines that can be used multiple times within the main phenotype program.

Think back to the turtle example. Imagine that instead of drawing lines, it is generating richer code. Here's a variation of the biomorphs example that does just that: it generates code once rather than interpreting the genome on each frame -- and this could be used as a template on which to add more behaviour than simply drawing, for example.

Another interesting result is that the developmental program could also be gradual, meaning we can model the increase in complexity of an organism from embryo to adult through the rewriting of its behavioural programs.

Taken to the most general form, it allows us to explore models in which the mechanisms of evolution are also subject to evolutionary pressures; see Spector, Lee. "Autoconstructive evolution: Push, pushGP, and pushpop." Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001). Vol. 137. 2001.. This is meta-evolution: that the mechanisms of evolution (including development, variation, etc.) are also subject to variation and selection. After all, sexual reproduction had to be discovered. It turns out that some parts of our genes have evolved to be far less volatile than others, for good reason. Jurgen Schmidhuber also proposed using genetic programming (GP) to evolve GP (meta-GP), since things like chromosomes, crossover etc. are themselves phenomena that have evolved.


Agent-based evolution

Viability-based selection and ecosystemic evolution

So far we have replaced entire generations at a time, but of course in the real world creatures' life spans interleave in all kinds of ways, with population booms and busts. Moreover we have rather artificially tested candidates against a pre-defined function, or against the whims of an interacting user or participant. But this isn't how nature works most of the time. As noted already, viability-based selection depends only on fundamental internal processes and exchanges with an environment (including other creatures of various species) to determine whether a creature can survive, and reproduce. Often this approach involves populations of agents.

When a new agent is created from nothing, as happens at the start of the simulation, and also as a fail-safe if the population ever dwindles away, a randomized genome must be added to the agent. When an agent spawns a child, the child also needs a genome, created by mutation of the parent's. This could be extended by adding sexual reproduction, only occurring when agents meet, and implemented with crossover as well as mutation.

But most importantly, parts of the genome must determine behavioural properties of the agent -- how it behaves and interacts with the world -- else there's no selection at all. (It can be useful to also modify how the agent appears graphically, but this has no effect on evolution.)

Parametric variation

A good starting point may be to have the genome modify parameters of the agent; for example, the amount of random walk, ranges of sensing, the reproduction threshold, thresholds of probability for selecting different actions, etc. Be careful with features like speed -- you might want to model an energetic cost to go with it for realism (and to avoid breeding supersonic agents!).

Also be careful not to oversimplify. Making a parameter of "energy efficiency" is clearly going to evolve toward maximum efficiency; there's nothing interesting about this. Things get more interesting when there are multiple constraints in play; if increasing one parameter weakens another, for example.

Similarly, a direct mapping of each gene in the genome to each parameter is likely less interesting than a more complex mapping, in which multiple processes are applied to the genome data to determine the parameters. This is exactly why the evolution of math functions was more interesting than the evolution of text: the outcome of the math function is a very complex mapping of the genes that go in. Complex enough to have surprises.

Another way of achieving this complexity in the mapping is to have the parameters drive features that have non-obvious effects or that depend on other parameters. For example, one could model a swimming organism by the speed it flaps its tail, the range it flaps over, and the average direction. Only together do these three parameters produce an arc of motion. Multiple such tails can lead to very complex motions. Similarly, taking Braitenberg's vehicles model, one could imagine placing a wire between every sensor and every motor, where the evolved parameters are the amplification weights on the wires.

sticky feet

For example, see Sticky Feet: Evolution in a Multi-Creature Physical Simulation -- including the video. In this example, the genome determines the structure of an organism as a set of point masses connected by springs. The springs are muscle-like in that their rest lengths oscillate, and the point masses also oscillate in their 'stickiness' (environmental friction) in order to support locomotion. Each organism has a heart and a mouth -- if the mouth of one agent touches the heart of another, it can eat it, and is rewarded by reproduction. Organisms may also have antennae attached to a spring segment, which detect either mouths or hearts, and modulate the spring length or stickiness. (A simple 3-segment creature with two sensors can very easily result in similar behaviour to the Braitenberg vehicles.)

Energy conservation and global adaptive constraints

Naturally environmentally-based viability selection has also led to models of ecological or ecosystemic basis. A simple starting point may be to take the agent-based example of variable populations with energy-exchange and preservation, and add genetics. In this case viability is principally determined by energy maintenance, so we have to take extra care in modeling this well. Every action an agent takes must cost energy, and this should be proportionate to the action taken. Sprinting takes more energy than sauntering. Locomotion models can estimate energy cost from the force actually applied; which is exactly the acceleration multiplied by the mass. We can approximate this by taking the difference between current & new velocities (after all clamping) and multiplying by the organism size. It may also be wise to have a basic metabolism cost to remain alive, that perhaps may increase with size, and with age.

Here's a start in this direction

As organisms evolve better strategies, they can better utilize the finite energy resources of the world, and thus support greater populations. An adaptive difficulty, perhaps applied to the metabolism cost, or applied generally to the available energy in the world, may help keep selection pressure effective at maintaining population size. For example, we can gradually decrease the total energy in the ecosystem while populations are large, and increase it again while populations are small.

Note that exactly how new energy is introduced can have quite drastic effect on the adaptive conditions -- since effectively organisms are trying to evolve strategies to be more viable, the distribution of energy in the world is the primary factor. The simplest option is to reintroduce the energy immediately, spread uniformly over the space, e.g. field.add(energy_deficit/(field.width*field.height)). More interesting behaviours can emerge when energy is redistributed more gradually and non-uniformly in space.

The Genetic Representation

At this point, should be clear that the effectiveness of evolution depends very much on both the genetic representation as well as its behaviour in producing phenotypes. If we consider the genetic representation as a language, then the evolutionary effectiveness depends both on the syntax and the semantics.

The syntax determines how a phenotype is encoded, what kinds of mutations are likely/unlikely/impossible, and what transformations these result in, how much space it takes up, the potential of redundancy and neutral data, and so on.

The semantics define the basic primitive concepts from which phenotypes are produced, and thus what kinds of phenotypes are likely/unlikely/impossible, including the overal size of the set of all possible phenotypes, the resolution of variations between them, and so forth. Put another way: A very common and very general method of solving problems (mathematical, computational, and otherwise), is to translate the problem into a more convenient language. We saw that our agents could reason about neighbours more easily when the neighbour poses where translated out of global space and into the coordinate space of the agent itself. Similarly, the turtle graphics language made it very easy to create simple line drawings, and with just a handful of special tokens quite complex structures, but there are still many shapes this language is unable or very unlikely to express. Simply, some languages work better than others for certain problems. (This may related to the reason why so many species share huge sequences of the same DNA.)

A good genetic representation should consider both syntax and semantics. We don't want to make our intermediate language to too restrictive, else it will not be powerful and extensible enough to encompass a wide enough range of expected and unexpected solutions. For example, we saw how creating an intermediate language of predefined words ensured we have readable (if nonsense) sentences, whereas translating into random numbers and arithmetic symbols opened the possibility of invalid expressions, but also was able to discover unexpected methods (such as using comment symbols for neutral drift). However, we also don't want our intermediate language so powerful and extensible that it becomes inefficient or intractable to actually apply, or upon which evolution has barely a chance to have impact. Our math & turtle graphics examples demonstrated how using a programming language as intermediate representation can achieve great power/diversity with succinct syntax.

Programmatic variation

For a more ambitious, but more interesting challenge, we can try to build up a population of evolving agents whose phenotypic behaviour is a unique program. That is, the "update" routine for each agent is different because it has different code, not just different parametric values. The biomorphs were a good example of this. Arguably this permits a vaster range of possible behaviours, because less of an organism's architecture is fixed for all time.

One model to achieve this is to think of the agent as comprising a collection of sensors, a collection of internal nodes of computing, and a number of output nodes (as actuator potentials) that cause actions in the world:

agent diagram

Possible outputs include:

If it is helpful, you may imagine the buttons you can press to control a videogame character. Each button is an output.

It may also be worth asking whether actions can occur concurrently, or whether activating one will suppress others. E.g. can you reproduce while in motion? Can you change direction when not in motion? The simplest technique here is to limit output to one action per frame.

Possible inputs include:

It is likely necessary to conform inputs to ranges of sensitivity, such that external quantities are always mapped into internal ranges clamped in a unipolar 0..1 range, or perhaps a bipolar -1..1 range. Outputs may also need to map their intrinsic ranges (unipolar or bipolar) into useful ranges in the world. For example, a unipolar consumption range could be used as a proportion of available food that is actually ingested. Alternatively, it could be mapped to a range determined by the maximum eating rate an organism can sustain (a constant).

For both inputs and outputs, we may need to distinguish between occasional "events" (think of buttons and impacts) and more continuously varying "signals" (think of knobs and rotations), though it is simpler if we do not need to.

Event-like inputs can be treated as signals whose value is zero when no event is occurring. Event-like outputs can be treated as signals that pass a given threshold, or change by a significant margin. Thresholding is a general way to convert a signal to an event, possibly with some accumulation & relaxation time, and sampling is a way to convert an event into a signal, possibly with some averaging/smoothing.

Possible internal operations:

The middle layers between inputs & outputs may utilize a palette of mathematical mappings and simple signal-processing operators. For example, the set of "neural nodes" available in Karl Sims' evolving virtual creatures simulation included:

sum, product, divide, greater-than, sign-of, min, max, abs, if, interpolate, sin, cos, atan, log, expt, sigmoid,

Furthermore, a number of more complex "stateful" operators (i.e. operators which include their own history/memory) were included:

sum-threshold, integrate, differentiate, smooth, oscillate-wave, and oscillate-saw.

Sum-threshold refers to a unit that operates much like a real neuron, accumulating inputs until a threshold is reached, then outputting a pulse and relaxing to zero. That is, neural networks are often modeled using only the sum-threshold (or even simpler, sigmoid) operators. Integrate is a simple counter, but it may be wise to make it "leaky", such that the accumulated value naturally decays over time. Smooth is a simple moving average, or low-pass filter, such as averaging the current and previous input. The oscillators are a combination of a counter with a trigonometric or modulo operation.

Other kinds of internal operations could be structural, such as creating a sequence of actions (and possibly including policies to abort a sequence if an action cannot be completed) or a sequence of options (taking the first one that can be executed).


agent graph

Genetic Programming

Genetic Programming was invented by Nigel Cramer in 1985, but greatly expanded through the work of John Koza. GP evolves programs; it is an example of metaprogramming. GP has been used to generate programs to solve hard problems, and to evolve control systems for artificial agents and robots. Karl Sims used GP for his genetic images as well as for his evolving virtual creatures.

In GP that the generating a phenotype is a process of generating programs, however programs are usually expressed as syntax trees rather than as lines of code. The leaves of the tree are terminals, while the non-terminal branches are functions. Terminals have no inputs; typical terminals are constant numbers and external/global variable names, but this set can also include zero-argument functions such as "random()" or context-sensing such as "get_orientation()". Non-terminal functions are specified according to their operator (such as mathematical addition, multiplication, cosine, etc.); they have one or more inputs (the number of inputs is the arity), which may be filled by terminals or other functions. The set of all possible terminals and non-terminal functions constitutes the primitive set of a GP system (a union of the terminal set and the function set).

This structure is natural to LISP programs:

(* (sin (+ x 2)) (cos x))

In this case, the terminal set appears to include integers and "x", the function set includes "sin", "cos", and binary operators such as "+", and "*".

Javascript does not have this representational succinctness, but can get close to it by nested arrays:

["*", ["sin", ["+", "x", 2]], ["cos", "x"]]

Or more graphically:

[
    "*", 
    [
        "sin", 
        [
            "+", 
            "x", 
            2]
    ], 
    [
        "cos", 
        "x"
    ]
]

Note that our representation is more brittle than a simple string of symbols: any array beginning with "sin" must have one more element following it as the argument; any array beginning with "+" must have two elements (array length 3) following it as arguments. Moreover, those arguments must either be terminal nodes such as "x" or numbers, or they must be arrays -- that is, operator symbols like "sin" and "+" can only occupy the first position. Since we know that our operators require at most two arguments, we could simply give all functions two arguments, and ignore the un-used ones as neutral junk genetic data, e.g.:

[
    "*", 
    [
        "sin", 
        [
            "+", 
            "x", 
            2], 
        5        // junk
    ], 
    [
        "cos", 
        "x", 
        "x"        // junk
    ]
]

Interpretation (development)

To turn this data into something we can actually run as code, we could spell it out as an expression:

return (Math.sin(x + 2) * Math.cos(x));

Here's a recursive solution:

function develop(node) {
    // terminals:
    if (typeof node == "string" || typeof node == "number") {
        return node;
    }
    // non-terminals:
    var op = node[0];
    var a = node[1];
    var b = node[2];
    if (op == "sin" || op == "cos") {
        // unary Math function call:
        return "Math." + op + "(" + develop(a) + ")";
    } else if (op == "+" || op == "*" || op == "-" || op == "/" || op == "%") {
        // binary operator:
        return "(" + develop(a) + op + develop(b) + ")";
    }
}

Choice of primitive set

A couple of things to watch out for here:

Seed generation

To generate a random seed genotype, we can also use a recursive procedure. One thing to watch out for: we need to make sure we don't spawn infinitely large genotypes! To do that, we'll need to pass some information through the recursion to bail out at a certain depth, or when the genome has a certain size. For example, we could limit the recursive depth as follows:

var ops = ["sin", "cos", "+", "-", "*", "/", "%"];

function pick_random_operator() {
    return ops[random(ops.length)];
}
function make_random_terminal() {
    return random(2) ? "time" : Math.random()*1000;
}

function generate(depth) {
    // forces use of terminal when depth == 1, randomized otherwise:
    if (random(depth) == 0) {
        return make_random_terminal();
    } else {
        return [
            pick_random_operator(), 
            generate(depth-1), 
            generate(depth-1)
        ];
    }
}

// generate with maximum depth 6:
var data = generate(6);

// print out nicely:
console.log(JSON.stringify(data, null, " "));

Koza also recommends creating a seed population with a variety of depths, which we can easily do by randomizing the initial argument to generate().

Mutations and recombinations

GP departs significantly from other evolutionary algorithms in the implementation of mutation and recombination. It is not just individual terminal symbols that can be mutated, but also entire branches. Extra care has to be taken here to prune genomes that are getting too large (or to avoid then getting too small!). Some possible mutations include:

A tricky point -- most of these mutations depend on choosing a random non-terminal. How can we pick one randomly? And how can we ensure that the genomes stay of a reasonable size? The solutions to these problems are not trivial enough to work through in our labs.

Alternative representations

Many GP systems today assume that all non-terminal functions have the same arity (the same no. of arguments). By doing so, it turns out that the brackets become redundant, and trees can efficiently be represented as simple linear sequences. The above example can be simply listed as:

* sin + x 2 5 cos x x

Clearly this makes some mutations easier -- we can pick random items in the list and replace them with equivalents, e.g. replacing terminals with terminals, operators with operators. We can easily see the genome size, and use that as a selection factor. But it is still not so trivial to make replacements and ensure the whole genome still generates a complete program.


Another variant, called "linear genetic programming", also uses a flat list of nodes, but in a format closer to a register language (in fact, closer to the underlying architecture of modern PCs). Each node in this list has an operator, to determine what kind of instruction it is (e.g. "+", "sin", "var", etc.), followed by some values to specify which existing "registers", that is, previously-computed values, are to be used as arguments to the operation. Each operation will then produce a new register in turn. So, the code generated will look something like this:

var r1 = x;
var r2 = 2;
var r3 = r1 + r2;
var r4 = Math.sin(r3);
var r5 = x;
var r6 = Math.cos(r5);
var r7 = r4 * r6;
return r7;

A genetic representation might be something like this:

[
    [ "var", "x" ],
    [ "num", 2 ],
    [ "+", 1, 0 ],
    [ "sin", 0 ],
    [ "var", "x" ],
    [ "cos", 0 ],
    [ "*", 2, 0 ],
]

Notice how registers are stored as offsets back from the currently-assigning register. So, an argument of 0 means the last-computed-register, 1 means the one computed before that, etc. This kind of relative indexing makes the representation far more robust -- less likely to be malformed after mutation. Even greater safety can be ensured by wrapping register indices within the available range. For a linearized genotype representation, the genetic mutations and crossover operators are similar to other sequence-based evolutionary systems.

An example using a kind of linear-GP, somewhat akin Karl Sims' evolving images, is in the lab editor here

An example using this scheme to generate random video feedback systems, in the lab editor

An example of this using jit.gen in Max/MSP/Jitter


Yet another very different but related approach is gramatical evolution. In GE, genomes are simply lists of integers, for example in the range 0-99. The possible shape of programs is determined by a grammar. The generator follows each rule of the grammar in turn, and when multiple options are possible, the next genome integer is used to determine the choice (modulo the number of choices). This not only guarantees that all generated programs are formally correct (no matter how complex the grammar involved), it also seems to lend some advantages with respect to mutations. Grammatical evolution has been very successful and is widely used.

Further reading: