Evolve a script

This page is an experiment. DNA (which codes for proteins that peform functions in individual cells) is like the source code for the biological machinery in living organisms. So if the process of evolution generated all the biological complexity encoded in DNA, then shouldn't it also be able to generate complex computer programs? The code on this page simulates chemical evolution to try and evolve simple JavaScript functions with given behaviours from basic building blocks. The question is, does the evolutionary process cause the random starting programs to become more complex?

But that's where I need your help: Your challenge, should you choose to accept it, is to tune the parameters below, to reliably evolve a function with one of the example behaviours. But be warned: this may not be as simple as you think...

The Algorithm

The following pseudocode describes the basic genetic search algorithm we've implemented to simulate the evolutionary process.

Create initial population P of random viable programs.
Evaluate the fitness of every p in P using the fitness function.
While generation g is less than MAX GENERATIONS:
1. Select Q to the top MAX PARENTS in P by fitness.
2. For every parent program p1 in Q
  Repeat CHILDREN PER PARENT times:
  1. If SEXUAL REPRODUCTION enabled:
    1. Select random parent p2 from Q.
    2. Generate c by combining p1 and p2 using crossover function.
  2. Else
    1. Generate c by cloning p1
  3. Mutate c with random probabilty.
  4. Evaluate fitness of c using fitness function.
  5. Add c to Q'
3. Replace P with Q union Q'
4. Increment g

Child programs are generated in sexual reproduction by combining two parent programs using the crossover function. This function combines the statement/expression trees by recursively combining any statements with the same number of placeholders, and then randomly choosing to use the expression from the left or right parent wherever there are different numbers of placeholders.

Child programs are mutated with random probability by: swapping random sub-statements/expressions, replacing a statement with another random statement, inserting a random statement, or deleting a random branch.

Examples Choose an example:

Choose an example from the list above to pre-populate the search fields.

Fitness formulae

These equations are like genetic markers which define what it means for a candidate JavaScript program to be "fit" in a given environment. Together with the fitness test function below, these define how likely a candidate program is to surive and reproduce (i.e. be selected). They should be one per line in the form f(args) = return_value.

Search space

These templates are like a "pre-biotic soup" containing the basic building blocks from which to build the candidate programs. They should be one per line, and can contain placeholders using the ?? wildcard. Together with the maximum program size parameter they define the search space of all possible programs to consider.

Search space size: possible programs.

Search parameters

The following inputs allow you to "tune the dials" on the evolutionary process:

Search space size: possible programs.

Fitness test function

function (args, required, actual) {
    // Pearsons correlation coefficient
    var n = required.length;

var required_min = required[0];
    var required_offset = 0;

var actual_min = actual[0];
    var actual_offset = 0;

var equal = 1;
    for (var i = 0; i < n; i++) {
        if (actual[i] == null || isNaN(actual[i])) return null;
        if (actual[i] != required[i]) equal = 0;
        if (actual[i] < actual_min) actual_min = actual[i];
        if (required[i] < required_min) required_min = required[i];
    }
    if (equal == 1) return 0;

if (required_min <= 0) required_offset = required_min + 1;
    if (actual_min <= 0) actual_offset = actual_min + 1;

var offset_required = required.map(a => a + required_offset);
    var offset_actual = actual.map(a => a + actual_offset);

var offset_required_mean = offset_required.reduce((a,b) => (a+b), 0) / n;
    var offset_actual_mean = offset_actual.reduce((a,b) => (a+b), 0) / n;

var offset_required_std_dev = Math.sqrt(offset_required.reduce((a,b) => a+(b-offset_required_mean)**2, 0) / (n-1));
    var offset_actual_std_dev = Math.sqrt(offset_actual.reduce((a,b) => a+(b-offset_actual_mean)**2, 0) / (n-1));

if (offset_actual_std_dev == 0 || offset_required_std_dev == 0) return null;

var sum = 0;
    for (var i = 0; i < n; i++) {
        var p1 = offset_required[i] - offset_required_mean;
        var p2 = offset_actual[i] - offset_actual_mean;
        sum += p1 * p2;
    }

var covariance = sum / (n-1);
    var r = covariance / (offset_required_std_dev * offset_actual_std_dev);

return 1-Math.abs(r);

}

function (args, required, actual) {
    // Pearson's of log of values
    // i.e. use for exponential functions

var n = required.length;

var required_min = required[0];
	var required_offset = 0;

var actual_min = actual[0];
	var actual_offset = 0;

var equal = 1;
    for (var i = 0; i < n; i++) {
        if (actual[i] == null || isNaN(actual[i])) return null;
		if (actual[i] != required[i]) equal = 0;
		if (actual[i] < actual_min) actual_min = actual[i];
		if (required[i] < required_min) required_min = required[i];
    }
	if (equal == 1) return 0;

if (required_min <= 0) required_offset = required_min + 1;
	if (actual_min <= 0) actual_offset = actual_min + 1;

var log_required = required.map(a => Math.log(a + required_offset));
    var log_actual = actual.map(a => Math.log(a + actual_offset));

var log_required_mean = log_required.reduce((a,b) => (a+b), 0) / n;
    var log_actual_mean = log_actual.reduce((a,b) => (a+b), 0) / n;

var log_required_std_dev = Math.sqrt(log_required.reduce((a,b) => a+(b-log_required_mean)**2, 0) / (n-1));
    var log_actual_std_dev = Math.sqrt(log_actual.reduce((a,b) => a+(b-log_actual_mean)**2, 0) / (n-1));

if (log_actual_std_dev == 0 || log_required_std_dev == 0) return null;

var sum = 0;
    for (var i = 0; i < n; i++) {
        var p1 = log_required[i] - log_required_mean;
		var p2 = log_actual[i] - log_actual_mean;
		sum += p1 * p2;
    }

var covariance = sum / (n-1);
	var r = covariance / (log_required_std_dev * log_actual_std_dev);

return 1-Math.abs(r);

}

This function evaluates the fitness of a given candidate function. It does this by comparing the actual return values returned by the candidate to expected return values defined in the equations. It should return a positive numeric error value to represent "how far" the actual values are from the required solutions. Here lower values indicate better results, where 0 means the function returned the exact values required. If an actual equals null this means the candidate raised an Exception (e.g. SyntaxError) to that input arg. If this function returns null, it means that this candidate is not viable and is therefore considered completely unfit i.e. "dead".

Search status Current generation: 0
Current population size: 0
Total candidates evaluated: 0 of possible.
Total mutations applied: 0
Number of correct solutions generated: 0
Best error value so far:

Why didn't it work?