Genetic Programming Engine[![Build Status](https://travis-ci.org/darwins-challenge/moonlander-gp.svg?branch=master)](https://travis-ci.org/darwins-challenge/moonlander-gp)
==========================

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.)
    ])