Genetic Programming Engine

This Genetic Programming library in Rust was developed for the "Fly me to the Moon" workshop.

Purpose

Genetic Programming is about expressing the solution to a particular problem in an Abstract Syntax Tree (i.e., as a representation of a computer program that will solve the problem), and then using genetic operations to generate and improve the population of programs. Hopefully, eventually the population will converge to a set of programs that successfully solve the problem in question.

Genetic Programming works with by evolving subsequent generations of an initially randomized population. The create a new generation, we apply 3 genetic operations to individual programs from the last generation.

The genetic operations are:

• Reproduction. We pick an individual program from the current generation and copy it into the next generation. By picking well-performing individuals, we hope to keep the fitness of the population up.
• Mutation. We pick an program from the current generation, change it slightly, and insert it into the next generation. Mutation gets us out of local maxima.
• Crossover. We pick two programs, and splice their programs together. By using crossover, we hope to produce programs that are better than either parent.

You'll notice that all of these genetic operations contain the notion of a "picking an individual". The library provides tournament selection, which picks N random individuals, and then selects the best individual from those N. This gives fitter individuals a better chance of being chosen.

Mutation and crossover are implemented at the AST node level. We'll pick a random node from the AST and replace it with another node (either a randomly generated subtree, or a randomly picked node of the same type from the other parent).

How to use this library

This library provides the evolution framework. To use it, you need to supply:

• An AST grammar. This is the set of node types that can be used in the solution, and what subnodes can appear in what parent nodes. AST nodes are represented as enums with various cases.
• A fitness function. The fitness function will evaluate how good a particular solution is. In practice, this means you will supply a function that iterates over the AST to evaluate it in some way, then ranks the result of that evaluation as a numeric value. This function will be maximized.

Grammar nodes

Grammar nodes are specified as enums which need to implement some particular traits. Most of these trait implementations can be autogenerated using a macro, though:

#[derive(Clone)]
enum Statement {
    IfFoodAhead(Box<Statement>, Box<Statement>),
    Prog2(Box<Statement>, Box<Statement>),
    Prog3(Box<Statement>, Box<Statement>, Box<Statement>),
    Command(Box<Command>)
}

impl_astnode!(Statement, 1,
              int IfFoodAhead(then, els),
              int Prog2(one, two),
              int Prog3(one, two, three),
              leaf Command(cmd));

Fitness function

The fitness function has the following shape:

fn fitness(program: &Program, rng: &mut Rng) -> SomeFitnessStruct

Where Program is the root type of the AST, and SomeFitnessStruct is any object that implements Fitness. Use the struct to retain any information you want to persist after evolving (for example, a trace of a simulation). If that's not required, a SimpleFitness object can be used.

Ultimately, the score is provided in a ScoreCard object, which contains both labels and scores. Scores may be negative to encode penalties:

SimpleFitness::new(vec![
    ("food_eaten", ant.food_eaten as f32),
    ("complexity_penalty", (depth(ant) as f32) * -10.)
])