Fly me to the Moon
Fly me to the Moon
Daan van Berkel and Rico Huijbers
Buy on Leanpub

What this book is all about

This book is an compendium to a workshop exploring genetic programming. Genetic programming is

a technique whereby computer programs are encoded as a set of genes that are then modified (evolved) using an evolutionary algorithm.

This book will explain various ideas and will ground them by discussing ways you could implement them. It will provide you with a practical introduction to genetic programming and hones it with exercises, both pen and paper as implementation exercises.

Each chapter will introduce ideas needed to create your own, or work with a, genetic programming environment, that can solve a certain problem. The ideas will be illustrated by the following projects.

  1. Nadezhda was the name of a cockroach sent into space to study its behavior. Even though cockroaches have far more intricate behavior than we attribute them during this problem, we like to stay in the space theme. You can inspect the code in the nadezhda directory. This project is used as an illustration to explore the concepts of genetic programming. It is very much a toy problem, but it can illustrate the important concepts.
  2. AGC is an abbreviation for Apollo’s Guidance Computer that was responsible for aiding in computations of guidance, navigation and control of the space craft. If you want, you could implement this yourself, if you follow the project in this book. This project is a bit more involved than Nadezhda, and allows you to take a genetic programming framework for a spin. You can use your new found skills from the ground up to really test your understanding.
  3. Lunar Lander tries to land safely on the surface of the moon. The catch is that you are giving control to a program that a computer wrote. This project demonstrates that hard problems can be solved by genetic programming. You can inspect the result in moonlander-ast-rust. This project is included to focus on the interesting aspects of genetic programming. I.e. how to find a good fitness function for my problem.

Jump aboard the HMS Beagle

In this chapter we will give a lay-mans introduction to evolution and how it applies to the projects we are studying.

Evolution

Evolution tracks a population over time in their environment. A population consists of individuals. Individuals differ by there genetic makeup. The survival of the genetic makeup of an individual is determined by their fitness, i.e. how well they are adapted to their environment. Individuals that are fitter, have a higher chance of reproducing, allowing their genetic makeup to prosper.

Translation

Above we gave in broad strokes a general description of evolution. In this section we are going to paint a little bit more detail. We do this by providing a translation, from the general term to the specific term that we are going to use.

Individuals

Our individuals will be abstract syntax trees or AST for short. Abstract syntax trees are a means to accurately describe the structure of a certain program. We will use grammars to define which abstract syntax trees are allowed.

Genetic Makeup

The behavior of a program is determined by evaluating an AST. So the genetic makeup is the AST itself.

Environment

We have a number of environments that our AST will flourish in. The environments are described in the About chapter.

Fitness

The fitness of our AST will be measured by a fitness function. This is a function that tracks the performance of a AST in her environment and assigns a numerical value to it. This numerical value will be used to compare AST to determine their relative fitness.

Further reading

Below we have some suggestions on what to read next.

If you want to learn how to genetic programming works by and studying the nitty gritty details, work through all the chapters up to A Framework for Genetic Programming. It will teach you everything you need to know to work with, or create your own, genetic programming framework.

If you want to work on the AGC project, or work on your own problem, go to the A Framework for Genetic Programming chapter. It explains how to use the framework on the problem of landing a lunar lander on the surface of the moon. It is an ideal stomping ground to learn about the framework for your own use.

If you want to construct good fitness functions in order to let the lunar lander land safely on the surface of the moon, head over to Tweak Fitness Functions. There you can try to guide the safe landing of the lunar lander, by writing the fitness function.

Projects

In this chapter we describe the back story for our projects in a little detail.

Nadezhda

This projects aims to model a simple robotic cockroach. The cockroach moves along a line. Each turn it either takes a step forward, takes a step backwards, or stops.

The goal of the cockroach is to reach a supply of food somewhere along the line. Its performance is measured by the distance to the food source.

Moonlander

This is the ultimate project. The goal for this project is to safely land a lander on the surface of the moon. We are modeling the control program of the lander. Each decision moment the program can decide to do the following things

  1. Skip, does nothing
  2. Left, fires some positioning blasters that will increase the rotational speed to the left.
  3. Right, does something similar as Left, only to the right.
  4. Thrust, fire the main thruster, changing the velocity of the lander.

You will be able to work on specific, characteristic problems applying what you learned in the Nadezhda project.

AGC

In this project we are modeling doing calculations with a single variable. One example would be \(3x + 5\).

The goal is to match a series of function values as closely as possible. This project is one that you could try to implement yourself, guided by exercises in this book.

Grammars

Grammars are a way to specify which structures are possible. There are a lot of formal definitions of grammars. We on the other hand will go for a working knowledge. I.e. we will describe how to specify a grammar, and how to implement it in rust.

Grammar Game

We will view grammars as a kind of game. Like any game the grammar game has some objects to manipulate. The objects to manipulate will be sequences of symbols. There will be two types of symbols: terminal symbols and non-terminal symbols. The reason why the symbols are called that way will be given shortly. Terminal symbols will be written with lowercase words. E.g a, by or cat. Non-terminal symbols on the other hand will be written starting with an uppercase letter, followed by lowercase letters. E.g A, By, Cat.

Besides symbols also have production rules. A production rule is written as follows

1 A -> aAb

It has a single non-terminal symbol on the left of an arrow. To the right of the arrow is a sequence of symbols. A grammar game can have multiple production rules, even with the same non-terminal symbol to the left of an arrow. If that is the case, one is allowed to list the alternative sequences of symbols to the right of the arrow separated by a pipe |. E.g. given a grammar with two production rules A -> aA and A -> b, we are allowed to write this as:

1 A -> aA
2    | b

There is an other convention that we will use. Sometimes we will want to replace a non-terminal symbol with the empty string. This will be represented by a production rule like A -> ''.

Below you find an example of a grammar that will play a role in the exercises.

1 A -> aAb
2    | B
3 B -> c 
4    | ''

How to play?

We are discussing the grammar game, but we failed to mention how to play this game. The game is played by starting with a non terminal symbol. That will be are current sequence of symbols. Next we chose a non terminal symbol from our current sequence, find a production rule which has that symbol to the left of an arrow and apply it. We apply it by replacing the occurrence of the left side of the arrow by the sequence of symbols to the right. This will give us a new current sequence and we can choose a new production rule. We continue as long as there are non-terminal symbols to choose from our current sequence of symbols.

Let’s work out an example. Take the grammar above. We start with the non-terminal symbol A. We choose the production rule A -> aAb. Applying it results in the follow sequence of symbols aAb. We choose the same production rule again and apply it again, resulting in aaAbb. Next we choose the alternative production rule for A. I.e. A -> B, and apply it to aaAbb. This transforms into aaBbb. As a last application we choose the production rule B -> '' resulting in aabb, and we are finished.

We call the act of applying production rules deriving, and when we come to a sequence of only terminal symbols, we say that this sequence can be derived from the non-terminal symbol we started with.

Nadezhda

For the Nadezhda project we are going to look into the following grammar.

1 Program -> forward Program
2   -> backward Program
3   -> stop

This grammar models the decisions our robot cockroach will make in finding her virtual food supply.

Exercises

  1. Which of the following sequences can be derived from the non-terminal symbol A given the grammar 
    1 A -> aAb
2    | B
3 B -> c
4    | ''
    • ’’
    • c
    • cc
    • ab
    • abb
    • aab
    • aabb
    • aacbb
    • aaccbb
  2. For the Nadezhda grammar, is there a limit on the number of forward symbols in a sequence that is derived?
  3. Create a grammar that is capable of expressing calculations.

Abstract Syntax Trees

An abstract Syntax Tree (AST)

is a tree representation of the abstract syntactic structure of source code written in a programming language

For us it will just be an instance of a Rust data structure, that corresponds with the grammar we want to represent.

Nadezhda AST as enums

Rust has enums that are well suited for the task of modeling ASTs. Once you have a grammar, it is a small step to implement in Rust.

You will encounter one small problem. We will illustrate that with an example. Take the Nadezhda grammar

1 Program -> forward Program
2          | backward Program
3          | stop

If we would translate this into Rust without really thinking we would come up with something like the following code

1 enum Program {
2     Forward(Program),
3     Backward(Program),
4     Stop,
5 }

Which is almost a direct translation. Unfortunately this does not compile. The rust compiler spits out the following warning.

1 error: recursive type `Program` has infinite size [E0072]
2 enum Program {
3     Forward(Program),
4     Backward(Program),
5     Stop,
6 }
7 help: run `rustc --explain E0072` to see a detailed explanation
8 help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `Pr\
9 ogram` representable

We remedy this by wrapping the inner programs in a Box.

1 pub enum Program {
2     Forward(Box<Program>),
3     Backward(Box<Program>),
4     Stop,
5 }

Exercises

  1. What would be other options to appease the Rust compiler when building recursive types? How would that differ from using Box.
  2. Is stop necessary in the Nadezhda grammar?

Parsers

Parsers are a

software component that takes input data (frequently text) and builds a data structure – often some kind of parse tree, abstract syntax tree or other hierarchical structure – giving a structural representation of the input, checking for correct syntax in the process

This wordy definition is hard to take in. For us, a parser will be a means to go from a syntax, i.e. characters typed in a file, to an Abstract Syntax Tree (AST).

Creating parsers is a rich subject with very interesting nuances. We can largely avoid creating our own parser by leveraging the excellent parser of Rust.

Domain Specific Language

Domain Specific Language (DSL) is a

computer language specialized to a particular application domain.

We will make use of a internal DSL, i.e. a DSL embedded in Rust. This will save us work, because we are leveraging the Rust parser.

We will achieve this by the use of macros.

For an excellent treatment on DSL consult Domain Specific Languages.

Nadezhda

We will demonstrate how to create an internal DSL for the Nadezhda grammar. The Nadezhda grammar is defined as

1 Program -> forward Program
2          | backward Program
3          | stop

We would like to write something as close as possible to this structure. Ideally we would want forward(forward(backward(stop))), to be a valid program. With Rust macros we can come close.

Below you find a macro definition for the forward macro. Macros for backward and stop are similar.

1 #[macro_export]
2 macro_rules! forward {
3     ($program: expr) => (Forward(Box::new($program)))
4 }

It creates a program by wrapping a boxed contained program with a Forward tag. This allows use to write our intentions as close to our desires as Rust allows us.

Exercises

  1. What benefits does an internal DSL have over an external DSL?

Random Generation of AST

When we create a population of individuals, we do not want to create every individual by hand. We would rather generate them by some random process. This chapter explains how this can be achieved.

In short generating an Abstract Syntax Tree comes down to picking an alternative at each level of the grammar. This will become clear in examples.

Nadezhda

The Nadezhda grammar is implemented assert

1 pub enum Program {
2     Forward(Box<Program>),
3     Backward(Box<Program>),
4     Stop,
5 }

We would like to generate a program with the following line of code:

1 let program = rand::Random();

For this to work we need to implement rand::Rand for Program. The basic strategy is to generate a number from 0 up to 3 and depending on the number create one of the three alternatives.

 1 impl rand::Rand for Program {
 2     fn rand<R: rand::Rng>(rng: &mut R) -> Self {
 3         let random_number = rng.gen_range(0, 3);
 4         match random_number {
 5             0 => {
 6                 let nested_program: Program = Program::rand(rng);
 7                 Program::Forward(Box::new(nested_program))
 8             },
 9             1 => {
10                 let nested_program: Program = Program::rand(rng);
11                 Program::Backward(Box::new(nested_program))
12             },
13             _ => Program::Stop,
14         }
15     }
16 }

Note that for the Forward and Backward alternative we need to also create a nested program that will be wrapped.

Generating more complex grammars

In generating random programs one quickly encounters a problem. The problem manifest itself in occasional stack overflows. In order to examine the problem we are taking a closer look at the heart of the problem.

Take a look at the following grammar

1 Tree -> leaf
2       | node Tree Tree

It expresses a tree structure. If one would write corresponding abstract syntax trees and generators for this grammar, the same problem would occur. If there are equal chances to generate a leaf or a node out of a Tree, we are very likely to end up with a very deep tree.

The solution is to bias the generation in favor of leafs. This will short circuit the infinite descent and makes stack overflows unlikely.

Mathematically inclined readers can follow along to investigate the issue further. Lets assume that there is a chance \(p\) to generate a node and a chance \(q = 1 - p\) to generate a leaf. We would like to express the expected number of nodes and leafs \(E\) in our generated trees. By linearity of expected values we have

$$ E = p \cdot (1 + 2E) + q \cdot 1 $$

Because for each node there is 1 extra node plus for the left and right branches two times the expected number of nodes and leafs, and for each leaf there is one extra leaf. Using the relation \(q = 1 - p\) and solving for \(E\) we get

$$ E = \frac{1}{1 - 2p} = \frac{1}{2q - 1} $$

If there are is an equal change to generate nodes and leafs this expression diverges. I.e. the expected number of nodes and leafs will be infinite.

Exercises

  1. What is the expected length of a randomly generated Nadezhda program.
  2. When writing generators it gets tedious to constantly write the same boilerplate code. Alleviate this nuisance by writing a macro.

Environment

The environment is what the individuals are inhabiting. Their actions determine in part how the environment changes. We will describe each environment.

Nadezhda

For our trusty cockroach the environment is basic. We only need to keep track of the source of food, and the location of the cockroach. We model that by integers.

1 pub struct Environment {
2     /// The location of the cockroach
3     pub cockroach_location: i32,
4     /// The location of the pile of food
5     pub food_location: i32,
6 }

Exercises

  1. Creating structs with many fields is cumbersome. An fluent interface could alleviate the nuisance. Create an fluent interface for the various environment.

Evaluate

Our Abstract Syntax Trees change the environment by evaluating themselves. In this chapter we see how that can be accomplished.

Nadezhda

We want our cockroach to evaluate her brain and change the environment accordingly. For this we introduce a trait Evaluator.

1 pub trait Evaluator {
2     fn evaluate_on(&self, environment: Environment) -> Environment;
3 }

If we would implement Evaluator for Program we could use it like.

1 let program: Program = forward!(forward!(forward!(stop!())));
2 let start: Environment = Environment::new(5);
3 
4 let finish: Environment = program.evaluate_on(start);

The implementation of Evaluator for Program directly reflects the structure of AST. For each encountered Forward we increment the cockroach position, for each encountered Backward we decrement the coackroach position and we stop when encountered Stop.

 1 impl Evaluator for Program {
 2     fn evaluate_on(&self, environment: Environment) -> Environment {
 3         match *self {
 4             Program::Forward(ref contained_program) => {
 5                 let next_environment =
 6                 Environment { cockroach_location : environment.cockroach_locatio\
 7 n + 1,
 8                   .. environment
 9                 };
10                 contained_program.evaluate_on(next_environment)
11             },
12             Program::Backward(ref contained_program) => {
13                 let next_environment =
14                 Environment { cockroach_location : environment.cockroach_locatio\
15 n - 1,
16                   .. environment
17                 };
18                 contained_program.evaluate_on(next_environment)
19             },
20             Program::Stop => {
21                 Environment { .. environment }
22             }
23         }
24     }
25 }

Fitness

We would like to give a score to how well our programs perform. This can be done by introducing a fitness function. The fitness function is arguably the most important part of evolutionary programming. Without a good fitness function, you likely will not get results you are hoping for.

Nadezhda

For our cockroach a Score will be nothing more than an alias for an integer.

1 pub type Score = i32;

A ScoreCard is a trait that can be implemented to assign a score to a program in an environment.

1 pub trait ScoreCard {
2     fn score(&self, program: Program, environment: Environment) -> Score;
3 }

We could create a dummy struct Config and implement ScoreCard for. A score would be given as the squared distance of the cockroach from the food location.

 1 impl ScoreCard for Config {
 2     fn score (&self, program: Program, environment: Environment) -> Score {
 3         let result = program.evaluate_on(environment);
 4         let score = 
 5             (result.cockroach_location - result.food_location)
 6             .abs()
 7             .pow(2);
 8             
 9         score
10     }
11 }

Exercises

  1. Determine the program length of a Nadezhda program and include it in the score.
  2. How would you extend the Nadezhda ScoreCard to include weight factors for the different parts of the score?

Population

In order to keep track of the individual programs we define a population.

Nadezhda

Little more is needed for our Nadezhda problem then a vector of Programs. We wrap a Vec<Program> in our Population.

1 pub struct Population(pub Vec<Program>);

Exercises

  1. Implement a way to create a Nadezhda population.

Darwin

We now are ready to implement the core of the evolutionary algorithm. Our goal is to run a simulation of an evolution for a number of generations. Before we can tie the preceding chapters together, we still need to provide a few key ingredients

  1. mutation, a means to change a Program in the hopes to be better adopted to the environment.
  2. crossover, a means for two Programs to have offspring, having parts of their parents DNA.

Nadezhda

mutate

We will mutate a program in the following way. For each part of the program, we will decide if we are changing it or not. The MutateDecision is responsible for making this decision.

1 pub trait MutateDecision {
2     fn should_mutate(&mut self) -> bool;
3 }

We will provide a trait Mutable that accepts a MutateDecision in a mutate function. It will return a mutate variant of Self, in our case a Program.

1 pub trait Mutatable {
2     fn mutate(&self, decide: &mut MutateDecision) -> Self;
3 }

One way of implementing Mutatable for Program is shown below.

 1 impl Mutatable for Program {
 2     fn mutate(&self, mut decide: &mut MutateDecision) -> Program {
 3         match *self {
 4             Program::Forward(ref contained_program) => {
 5                 if decide.should_mutate() {
 6                     Program::Backward(Box::new(contained_program.mutate(decide)))
 7                 } else {
 8                     Program::Forward(Box::new(contained_program.mutate(decide)))
 9                 }
10             },
11             Program::Backward(ref contained_program) => {
12                 if decide.should_mutate() {
13                     Program::Forward(Box::new(contained_program.mutate(decide)))
14                 } else {
15                     Program::Backward(Box::new(contained_program.mutate(decide)))
16                 }
17             },
18             Program::Stop => Program::Stop,
19         }
20     }
21 }

Crossover

Crossover is combining the DNA of two parent to produce offspring. We will always use the two-for-two method. I.e. take two parents and produce two offspring.

For the Nadezhda setting, the high level crossover algorithm is outlined below. We have parents A and B.

  1. Randomly chose a cut-points in programs A and B.
  2. The two children are
  3. Everything before cut-point of A followed by everything after cut-point of B.
  4. Everything before cut-point of B followed by everything after cut-point of A.

Evolve

Evolution is the culmination of our hard work. This ties in all the ingredients we have been exploring. The gist of evolution is

  1. Generate a random population.
  2. Until you are satisfied repeat.
  3. Create a successor population.

A succession can be made in a number of ways, but variations do not seem to change the overall effect. Below we list some characteristic steps.

  1. Determine the fitness of the individuals in the generation.
  2. Pass top individuals directly into the next generation.
  3. Repeat until population is big enough
  4. Cross two parents and add children to the population.
  5. Mutate an individual and add to the population.
  6. A combination of the above.

Exercises

  1. Implement a RandomDecision. I.e. implement the trait MutateDecision by performing a random decision.
  2. Can the mutate function shown change the length of a Program?
  3. Implement crossover for Nadezhda.

A framework for Genetic Programming

Up until now, we’ve done everything by hand. You might notice that some of the work is applicable, such as generating a random population of trees, and applying reproduction, crossover and mutation to build new generations is to every genetic programming task.

To help you solve genetic programs quickly, we’ve wrapped up most of the machinations necessary to abstract these concerns away into a library. We’re going to introduce that library by taking you through the implementation of a GP model for the Moonlander problem, that uses this library.

Both the generic library and the model to solve the moonlander problem are available on GitHub. They’re called moonlander-gp and moonlander-ast, respectively, and the locations can be found in the resources.

Overview of the framework

The operations that are provided by the framework are:

  • Generating a new population with random trees
  • Evolving the population using the three genetic operations:
    • Reproduction
    • Mutation
    • Crossover

To use the framework, you’ll need to supply two things of your own:

  • A set of AST node types, thereby specifying a grammar for the solution
  • A fitness function to score solutions.

Framework Traits

To work with ASTs in a generic way, we’ve had to implement quite some traits in Rust. We’ll quickly take you through them, before explaining that we won’t need to implement most of them yourself.

An important constraint for many of these traits is that concrete type information cannot be used, because we’ll pick random nodes at runtime, so the types can not be known statically. Hence, some traits, like Copyable, will duplicate similar traits like Clone that work on static information.

AstNode

This trait should be implemented by all types that represent a node in the abstract syntax tree. It is used to generically iterate over and construct trees.

Because Any::get_type_id() is not stable, it also contains a method to return an identifier per node type, so that we can match nodes of the same type in different trees during crossover.

1 pub trait AstNode: Any+Mutatable+Copyable+Sync {
2     fn node_type(&self) -> usize;
3     fn children(&self) -> Vec<&AstNode>;
4     fn replace_child(&self, old_child: &AstNode, new_child: &mut Option<Box<AstN\
5 ode>>) -> Box<AstNode>;
6 }

RandNode

This trait should be implemented to construct a random subtree with the root of the given type. It is like rand::Rand, except the generic Rng argument has been replaced with a reference to a generic Rng argument, because we’ll need to be calling this from trait functions on AstNode, and trait functions cannot be generic.

For the implementation of this trait, you can use the pick![] macro.

The function also takes an argument of type NodeWeights, which is used to control the height of trees that get generated. Whenever there’s a choice to be made between internal and leaf nodes in the tree, the weights on that object will be used to control the relative probabilities. This (roughly) controls the height of the generated subtree.

1 pub trait RandNode: Sized {
2     fn rand(weights: NodeWeights, rng: &mut Rng) -> Self;
3 }

Mutatable

This trait is used for mutation of a node, or a subtree. There is a default implementation for all nodes that uses the RandNode implementation to replace the subtree with a new random subtree, but you can also mutate nodes in a more controlled fashion, such as replacing the operator in a node that represents a binary operation, while keeping the operands the same, by implementing this trait directly.

1 pub trait Mutatable {
2     /// Return a mutation of this node
3     fn mutate(&self, max_height: i32, rng: &mut Rng) -> Box<AstNode>;
4 }

Copyable

As aforementioned, this is a trait that we use to construct a copy of a subtree. Implementation of this trait comes for free for every type that implements Clone.

1 pub trait Copyable {
2     fn copy(&self) -> Box<AstNode>;
3 }

impl_astnode!

Fortunately, you can get implementation of most of these traits for free for enums by using the impl_astnode! macro, which implements both AstNode and RandNode. This brings Mutatable for free, and if you #[derive(Clone)] as well you get Copyable for free as well.

Hence, AST nodes and all of their traits can be defined as succinctly as:

 1 #[derive(Clone)]
 2 pub enum Condition {
 3 	True,
 4 	False,
 5 	And(Box<Condition>, Box<Condition>),
 6     ...
 7 	Less(Box<Expression>, Box<Expression>),
 8 	LessEqual(Box<Expression>, Box<Expression>),
 9     ...
10 }
11 
12 impl_astnode!(Condition, 0,
13               leaf True(),
14               leaf False(),
15               int And(left, right),
16               int Less(left, right),
17               int LessEqual(left, right),

This defines an enum and some cases. The impl_astnode! macro takes some the enum name, a node type number, and the various case arms, describing whether they’re internal or leaf nodes, and generates the required traits.

Mark internal nodes with the prefix int, and leaf nodes with the prefix leaf. This will be used in the generated implementation of RandNode to pick either the provided weight for internal nodes or for leaf nodes.

Moonlander

In the moonlander problem, the objective is to evolve a program that will succesfully control a spacecraft to safely land on the surface of a moon.

First, this requires that we have a spacecraft to control, a surface to land on, and physics to which the lander will be subject.

Simulation

As part of the evaluation of a program (i.e., calculating its fitness), we will run the program through a simulation of the landing. This simulation will have a model of physics. For instance, the moonlander will have a position (x, y) in space, somewhere above the surface. It will have a velocity (vx, vy), and every tick of the simulation, the position will be updated with the velocity. in the same way, the ship will have a rotation and a rotational velocity.

The moonlander can affect its velocities, and hence ultimately its position, by controlling the actuators on the ship. There are three actuators: the main thrusters, boosting the ship forward in its current direction, or attitute thrusters which will change the ships rotational velocity.

When the y position of the moonlander has hit 0, signifying that it has hit the surface, we’ll evaluate the ship’s angle and vertical velocity, and deem it to having succeeded when the velocity is low enough and the angle is close enough to vertical.

To make sure the program we’re about to evaluate has enough information to make correct decisions, we’ll equip the ship with virtual “sensors”, allowing it to sense various properties about itself. In this case, we’ll allow the ship access to all properties of the simulation, so that includes the aforementioned (x, y), (vx, vy) and so on.

You can imagine a simulation in which there is information that the control program does not have access to. For example, the exact velocity might not be known. In this case however, we want to give our control program the greatest chance of success, and we’ll supply all information.

The information will be made available to the control program in the SensorData structure:

1 pub struct SensorData {
2     pub x:  Number,
3     pub y:  Number,
4     pub vx: Number,
5     pub vy: Number,
6     pub o:  Number,
7     pub w:  Number,
8     pub fuel: Number,
9 }

Grammar

All computer programs have an associated grammar that describes the space of possible programs. It’s important that this space can in principle contain program that solve the problem.

There is a choice of the style of program to allow. We can consider generating either imperative programs or functional programs. The space of functional programs without recursion is very safe, because programs are guaranteed to terminate, and there are no data dependencies between statements (such as variables having been declared or initialized).

For this problem we’ll opt to model a simple function that every tick takes the SensorData and outputs a single Command, which is the action to perform that round.

We’ll start off even simpler than the fully general program, and simply generate a program that evaluates to a boolean. We’ll couple this boolean to the main thrusters, firing the thrusters if the program returns true, and do nother otherwise.

Obviously, this simple program will not allow us to do attitute control, because there’s no way for us to trigger the Left and Right thrusters, but we can always extend the grammar later.

Let’s start by defining the sensors:

We want to define arbitrary conditions. Those conditions will eventually contain numerical expressions, and some of those numbers may come from the sensors.

This leads us to the following initial grammar:

Condition:

 1 #[derive(Clone)]
 2 pub enum Condition {
 3 	True, False,
 4 
 5 	Not(Box<Condition>),
 6     Or(Box<Condition>, Box<Condition>), And(Box<Condition>, Box<Condition>),
 7 
 8 	Less(Box<Expression>, Box<Expression>), LessEqual(Box<Expression>, Box<Expressi\
 9 on>),
10 	Equal(Box<Expression>, Box<Expression>),
11     GreaterEqual(Box<Expression>, Box<Expression>), Greater(Box<Expression>, Box\
12 <Expression>),
13 }
14 
15 impl_astnode!(Condition, 2,
16               leaf True(), leaf False(),
17               int Not(cond),
18               int Or(left, right), int And(left, right),
19               int Less(left, right), int LessEqual(left, right),
20               int Equal(left, right),
21               int GreaterEqual(left, right), int Greater(left, right));

Expression:

 1 #[derive(Clone)]
 2 pub enum Expression {
 3 	  Constant(Number),
 4 	  Sensor(Box<Sensor>),
 5 	  Plus(Box<Expression>, Box<Expression>), Minus(Box<Expression>, Box<Expression\
 6 >),
 7 	  Multiply(Box<Expression>, Box<Expression>), Divide(Box<Expression>, Box<Expre\
 8 ssion>),
 9 }
10 
11 impl_astnode!(Expression, 3,
12               leaf Constant((data n random_constant)),
13               leaf Sensor(sensor),
14               int Plus(left, right), int Minus(left, right),
15               int Multiply(left, right), int Divide(left, right));

Sensor:

1 #[derive(Clone)]
2 pub enum Sensor { X, Y, Vx, Vy, O, W, Fuel, }
3 
4 impl_astnode!(Sensor, 0,
5               leaf X(), leaf Y(), leaf Vx(), leaf Vy(),
6               leaf O(), leaf W(), leaf Fuel());

Evaluation

In every step of the simulation, the program will be given a chance to decide whether or not to fire its thrusters. This means we have to evaluate the AST of the program with the current values of the sensors to produce the output for this decision.

In the moonlander framework, this means implementing the trait EvaluateToCommand for the root node of the program. Evaluation of the AST uses the following traits, whose implementations are quite straightforward (refer to the moonlander-ast source if you’re curious):

 1 trait EvaluateToCommand {
 2 	fn evaluate(&self, sensor_data: &SensorData) -> Command;
 3 }
 4 
 5 trait BooleanValue {
 6 	fn is_true(&self, sensor_data: &SensorData) -> bool;
 7 }
 8 
 9 trait NumericValue {
10 	fn num_value(&self, sensor_data: &SensorData) -> Number;
11 }

The magic that connects the abstract and generic AST to the actual simulation is in the implementation of NumericValue for Sensor:

 1 impl NumericValue for Sensor {
 2     fn num_value(&self, sensor_data: &SensorData) -> Number {
 3         match *self {
 4             Sensor::X    => sensor_data.x,
 5             Sensor::Y    => sensor_data.y,
 6             Sensor::Vx   => sensor_data.vx,
 7             // ...etc...
 8         }
 9     }
10 }

Fitness

Now that we can run the simulation, and can have the program make decisions inside it that affect the simulation, it’s time to define the criteria that make a program successful.

We do this by writing a fitness function. This function assigns a numerical score to the performance of a program in the simulation. The goal of the genetic algorithm will be to maximize the value of the fitness function. It’s therefore helpful if higher values for the fitness function corresponds to better actual performance in ways that we care about!

It’s also helpful if the fitness function can be made as monotonically increasing towards the better program space as possible. If the fitness function returns 1,000 if the program finally met the victory condition, but 0 everywhere else, the intermediate values will not help guide the evolutionary algorithm towards the more successful part of the program space. The evolutionary algorithm will most likely be wandering around arbitrary parts of the program space, generating and selecting all equivalently successful programs (all scoring 0), until by chance it might hit upon a winning program. Depending on how rare successful program are, this might take quite a while.

In the framework, the fitness function takes a reference to a program, and returns any object that implements the Fitness trait. The only notable quality of the Fitness trait is that it has something called a ScoreCard:

1 pub trait Fitness: Send {
2     fn score_card(&self) -> &ScoreCard;
3 }

The ScoreCard represents the actual numerical score of an algorithm, which can be composed of many subscores and penalties. This labeled subdivision will be useful for human operators, to judge whether the scores assigned by the fitness function make sense.

Fitness is a trait, so that any actual object may be substituted. This allows us to collect and export extra data during simulation in a struct of our choosing. In the moonlander-ast project, we use this to collect trace of all frames of the moonlander during each simulation, so that we can export and visualize those traces later.

We collect the fitness like this:

 1 pub fn score_lander<P>(program: &P, _: &mut Rng, mut sensor_data: SensorData, wo\
 2 rld: &World) -> LandingTrace
 3     where P: EvaluateToCommand+AstNode
 4 {
 5     // ...
 6     while !sensor_data.hit_ground {
 7         // ...
 8     }
 9 
10     LandingTrace {
11         trace: trace,
12         score_card: ScoreCard::new(vec![
13             ("survival_bonus",   3.0 * frames),
14             ("fuel_bonus",       (100.0 * total_fuel / frames)),
15             // ...more scores here...
16         ])
17     }
18 }

Of course, this gives us the score for one run.

We probably want to run the simulation multiple times under randomized conditions. This will help us avoid overfitting the program to a fixed problem, and generate programs that generalize well.

However, randomized conditions introduce the chance that a potentially good program has a bad luck of the draw, performs poorly in its simulation, and gets culled from the population.

To reduce the chances of this happening, we’ll run the simulation multiple times and average the scores. For that we use the function score_lander_multi, which takes a number of rounds to evaluate, calls score_lander N times, and combines the results.

1 pub fn score_lander_multi<P, G>(n: usize, program: &P, rng: &mut Rng, sensor_dat\
2 a_fn: G, world: &World) -> LandingTrace
3     where P : EvaluateToCommand+AstNode,
4           G : Fn(&mut Rng) -> SensorData

Appendix: Resources

Accompanying this book is a set of resources that facilitate in understanding the ideas presented. It will help you get a flying start to mastering Genetic Programming.

Below are several ways to obtain the resources

Workshop

I you are lucky enough to find yourself at a workshop, there are probably a few memory sticks lying around that contain the resources. Grab one, copy workshop.tar.gz to your machine and extract it to a suitable folder of you choosing and you are good to go.

Download

Outside a workshop, you can retrieve a copy by downloading workshop.tar.gz from the following address: https://s3.amazonaws.com/darwins-challenge/workshop.tar.gz

Clone

It is also possible to clone the repository directly. Execute the following command

1 git clone --recursive https://github.com/darwins-challenge/workshop.git

This will setup a repository and all the submodules correctly.

Appendix: Play the Game

Sometimes you can only appreciate an achievement when you know how difficult it is. In order to set you expectations you can control a lander and try to land it safely on the surface of the moon.

Online

If you have access to the internet it is possible to play the game online. You can find the game at

http://darwins-challenge.github.io/moonlander-game/

Offline

If you are unable to access the internet and still want to play the game you need to obtain a copy of the resources. Read the Resources chapter for pointers how to get them.

Once you get them, open moonlander-game/index.html in a browser.

Appendix: Fast and the Curious

So you want to get to the result fast? You came to the right place. First things first, you need to get a copy of the resources. You can find pointers on how to obtain them from the Resources chapter.

Change directory to the help directory and use cargo to build the evolve_condition example.

1 cargo run --release --example evolve_condition 1a_fixed_vertical_landing.toml > \
2 fast-furious.json

Wait for the run to start and head over to the moonlander-visualisation directory. Run that project providing it with a directory which has the fast-furious.json file.

1 cargo run --release ../moonlander-ast/

Follow the programs instruction to open localhost:8080 in a browser. To view a trace of a run of evolution, open the load trace tab. Search for the fast-furious.json file, hit the load button. A list of generations can be seen. Click on one of them to see the performance of the moonlander. To see later generations reload the fast-furious.json file.

If you want to stop, don not forget to quit the evolve_condition example program.

What to Do

Here we give some suggestions for projects you could do

  1. Tweak Fitness Function
  2. AGC
  3. Bring your Own

Tweak Fitness Function

In this project you will learn the importance of a fitness function by trying to land a lunar lander safely on the surface of the moon. Find a detailed description in the corresponding chapter. j ## AGC We will try to fit the series of points with a function. You find a skeleton project in the AGC directory. See the AGC chapter in the accompanying book for a description of the book.

Bring your own

We would love to see this tool used to solve a problem that you have. There is a skeleton project that will give you a running start. Other than that you are on your own.

Tweak Fitness Function

The most important part of a genetic program is the fitness function. It guides programs along a favorable evolutionary path if it is constructed properly, or will let the programs run aground before the are well on their way.

We have created a few scenarios that of increasing complexity to test your understanding of fitness functions.

Straight Landing

First scenario

The lander starts at a fixed height, without any rotation, and needs to successfully land. To solve this scenario, it suffices to evaluate a Condition program.

If the Condition evaluates to true, the lander will use its thrusters (the command will be Thrust). If it doesn’t, it won’t (the command will be Skip).

Second scenario

The previous scenario evolved a program that started at a fixed position. However, such a winning program might be overfitting to the problem. In this scenario, the lander starts at a random height.

Does your model still evolve a successful solution?

With a Twist

First scenario

In the preceding project, the lander always started upright. In this project, it will start at angle.

Using the Condition, we could evaluate one of two commands: Thrust or Skip. Once the lander also needs to correct its attitude, those two commands are no longer sufficient (check: can evolve_condition evolve a winning solution to this scenario?)

Instead, we’ll need a new type of AST node, to increase the range of programs that we can express.

Can you invent and implement such an AST node? (Don’t forget to make a new example to evolve it, and don’t forget to update the fitness function)

AGC

With the use of the framework getting started with genetic programming comes down to the following steps

  1. Describe a grammar.
  2. Describe a fitness function.

The only thing you need is a good description of the problem.

Description

We want polynomial function like \(3x^{2}+2x+1\) that will fit values. More specifically given \(n\) values, e.g \(3, 1, 4, 1, 5\), the target function \(f\) should the \(i\)th value when evaluating \(i\), i.e. \(f(0) = 3\), \(f(1) = 1\) etcetera.

Bring your own

You are a creative person, so have fun and don’t forget to tell us what you have done.

Notes

1The HMS Beagle was the ship that took Charles Darwin around the world. It wad during this trip that Darwin collected data that led him to formulate the idea of evolution. His work culminated into his seminal book On the Origins of Species.↩