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\nwrap a Vec<Program> in our Population.

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

\n\n

Exercises

Implement a way to create a Nadezhda population.

",{"_300":301,"_43":44,"_47":48,"_45":46,"_70":71,"_302":303,"_364":298},"previewContent","

\n What this book is all about\n
\n Jump aboard the HMS Beagle\n
- \n Evolution\n
- \n Translation\n
- \n Further reading\n
\n
\n Projects\n
- \n Nadezhda\n
- \n Moonlander\n
- \n AGC\n
\n
\n Grammars\n
- \n Grammar Game\n
- \n Nadezhda\n
- \n Exercises\n
\n
\n Abstract Syntax Trees\n
- \n Nadezhda AST as enums\n
- \n Exercises\n
\n
\n Parsers\n
- \n Domain Specific Language\n
- \n Nadezhda\n
- \n Exercises\n
\n
\n Random Generation of AST\n
- \n Nadezhda\n
- \n Generating more complex grammars\n
- \n Exercises\n
\n
\n Environment\n
- \n Nadezhda\n
- \n Exercises\n
\n
\n Evaluate\n
- \n Nadezhda\n
\n
\n Fitness\n
- \n Nadezhda\n
- \n Exercises\n
\n
\n Population\n
- \n Nadezhda\n
- \n Exercises\n
\n
\n Darwin\n
- \n Nadezhda\n
- \n Exercises\n
\n
\n A framework for Genetic Programming\n
- \n Overview of the framework\n
- \n Framework Traits\n
- \n Moonlander\n
\n
\n Appendix: Resources\n
- \n Workshop\n
- \n Download\n
- \n Clone\n
\n
\n Appendix: Play the Game\n
- \n Online\n
- \n Offline\n
\n
\n Appendix: Fast and the Curious\n
\n What to Do\n
- \n Tweak Fitness Function\n
- \n Bring your own\n
\n
\n Tweak Fitness Function\n
- \n Straight Landing\n
- \n With a Twist\n
\n
\n AGC\n
- \n Description\n
\n
\n Bring your own\n
\n Notes\n

What this book is all about

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

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n\n

Jump aboard the HMS Beagle

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

\n\n

Evolution

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

\n\n

Translation

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

\n\n

Individuals

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

\n\n

Genetic Makeup

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

\n\n

Environment

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

\n\n

Fitness

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

\n\n

Projects

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

\n\n

Nadezhda

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

\n\n

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

\n\n

Moonlander

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

\n\n

\nSkip, does nothing
\nLeft, fires some positioning blasters that will increase the rotational\nspeed to the left.
\nRight, does something similar as Left, only to the right.
\nThrust, fire the main thruster, changing the velocity of the lander.

\n\n

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

\n\n

AGC

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

\n\n

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

\n\n\n

Grammars

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

\n\n

Grammar Game

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

\n\n

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

\n\n

1 A -> aAb\n

\n\n\n\n

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

\n\n

1 A -> aA\n2    | b\n

\n\n\n\n

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

\n\n

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

\n\n

1 A -> aAb\n2    | B\n3 B -> c \n4    | ''\n

\n\n\n\n

How to play?

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

\n\n

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

\n\n

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

\n\n

Nadezhda

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

\n\n

1 Program -> forward Program\n2   -> backward Program\n3   -> stop\n

\n\n\n\n

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

\n\n

Exercises

Which of the following sequences can be derived from the non-terminal symbol\nA given the grammar\n
\n
```
1 A -> aAb\n2    | B\n3 B -> c\n4    | ''\n
```
\n\n
\n\n
- ’’
- c
- cc
- ab
- abb
- aab
- aabb
- aacbb
- aaccbb
\n
For the Nadezhda grammar, is there a limit on the number of forward symbols\nin a sequence that is derived?
Create a grammar that is capable of expressing calculations.

\n\n\n

Abstract Syntax Trees

An abstract Syntax Tree\n(AST)

\n\n

\n
is a tree representation of the abstract syntactic structure of source code\nwritten in a programming language
\n

\n\n

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

\n\n

Nadezhda AST as enums

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

\n\n

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

\n\n

1 Program -> forward Program\n2          | backward Program\n3          | stop\n

\n\n\n\n

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

\n\n

1 enum Program {\n2     Forward(Program),\n3     Backward(Program),\n4     Stop,\n5 }\n

\n\n\n\n

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

\n\n

1 error: recursive type `Program` has infinite size [E0072]\n2 enum Program {\n3     Forward(Program),\n4     Backward(Program),\n5     Stop,\n6 }\n7 help: run `rustc --explain E0072` to see a detailed explanation\n8 help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `Pr\\\n9 ogram` representable\n

\n\n\n\n

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

\n\n

1 pub enum Program {\n2     Forward(Box<Program>),\n3     Backward(Box<Program>),\n4     Stop,\n5 }\n

\n\n\n\n

Exercises

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

\n\n\n

Parsers

Parsers are a

\n\n

\n
software component that takes input data (frequently text) and builds a data\nstructure â€“ often some kind of parse tree, abstract syntax tree or other\nhierarchical structure â€“ giving a structural representation of the input,\nchecking for correct syntax in the process
\n

\n\n

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

\n\n

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

\n\n

Domain Specific Language

Domain Specific Language (DSL)\nis a

\n\n

\n
computer language specialized to a particular application domain.
\n

\n\n

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

\n\n

We will achieve this by the use\nof macros.

\n\n

For an excellent treatment on DSL\nconsult Domain Specific Languages.

\n\n

Nadezhda

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

\n\n

1 Program -> forward Program\n2          | backward Program\n3          | stop\n

\n\n\n\n

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

\n\n

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

\n\n

1 #[macro_export]\n2 macro_rules! forward {\n3     ($program: expr) => (Forward(Box::new($program)))\n4 }\n

\n\n\n\n

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

\n\n

Exercises

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

\n\n\n

Random Generation of AST

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

\n\n

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

\n\n

Nadezhda

The Nadezhda grammar is implemented assert

\n\n

1 pub enum Program {\n2     Forward(Box<Program>),\n3     Backward(Box<Program>),\n4     Stop,\n5 }\n

\n\n\n\n

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

\n\n

1 let program = rand::Random();\n

\n\n\n\n

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

\n\n

 1 impl rand::Rand for Program {\n 2     fn rand<R: rand::Rng>(rng: &mut R) -> Self {\n 3         let random_number = rng.gen_range(0, 3);\n 4         match random_number {\n 5             0 => {\n 6                 let nested_program: Program = Program::rand(rng);\n 7                 Program::Forward(Box::new(nested_program))\n 8             },\n 9             1 => {\n10                 let nested_program: Program = Program::rand(rng);\n11                 Program::Backward(Box::new(nested_program))\n12             },\n13             _ => Program::Stop,\n14         }\n15     }\n16 }\n

\n\n\n\n

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

\n\n

Generating more complex grammars

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

\n\n

Take a look at the following grammar

\n\n

1 Tree -> leaf\n2       | node Tree Tree\n

\n\n\n\n

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

\n\n

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

\n\n

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

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

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

\n\n\n$$\nE = \\frac{1}{1 - 2p} = \\frac{1}{2q - 1}\n$$\n\n

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

\n\n

Exercises

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

\n\n\n

Environment

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

\n\n

Nadezhda

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

\n\n

1 pub struct Environment {\n2     /// The location of the cockroach\n3     pub cockroach_location: i32,\n4     /// The location of the pile of food\n5     pub food_location: i32,\n6 }\n

\n\n\n\n

Exercises

Creating structs with many fields is cumbersome.\nAn fluent interface could\nalleviate the nuisance. Create an fluent interface for the various\nenvironment.

\n\n\n

Evaluate

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

\n\n

Nadezhda

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

\n\n

1 pub trait Evaluator {\n2     fn evaluate_on(&self, environment: Environment) -> Environment;\n3 }\n

\n\n\n\n

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

\n\n

1 let program: Program = forward!(forward!(forward!(stop!())));\n2 let start: Environment = Environment::new(5);\n3 \n4 let finish: Environment = program.evaluate_on(start);\n

\n\n\n\n

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

\n\n

 1 impl Evaluator for Program {\n 2     fn evaluate_on(&self, environment: Environment) -> Environment {\n 3         match *self {\n 4             Program::Forward(ref contained_program) => {\n 5                 let next_environment =\n 6                 Environment { cockroach_location : environment.cockroach_locatio\\\n 7 n + 1,\n 8                   .. environment\n 9                 };\n10                 contained_program.evaluate_on(next_environment)\n11             },\n12             Program::Backward(ref contained_program) => {\n13                 let next_environment =\n14                 Environment { cockroach_location : environment.cockroach_locatio\\\n15 n - 1,\n16                   .. environment\n17                 };\n18                 contained_program.evaluate_on(next_environment)\n19             },\n20             Program::Stop => {\n21                 Environment { .. environment }\n22             }\n23         }\n24     }\n25 }\n

\n\n\n\n\n

Fitness

\n\n

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

\n\n

Nadezhda

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

\n\n

1 pub type Score = i32;\n

\n\n\n\n

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

\n\n

1 pub trait ScoreCard {\n2     fn score(&self, program: Program, environment: Environment) -> Score;\n3 }\n

\n\n\n\n

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

\n\n

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

\n\n\n\n

Exercises

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

\n\n\n

Population

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

\n\n

Nadezhda

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

\n\n

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

\n\n\n\n

Exercises

Implement a way to create a Nadezhda population.

\n\n\n

Darwin

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

\n\n

\nmutation, a means to change a Program in the hopes to be better adopted to\nthe environment.
\ncrossover, a means for two Programs to have offspring, having parts of\ntheir parents DNA.

\n\n

Nadezhda

\n\n

mutate

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

\n\n

1 pub trait MutateDecision {\n2     fn should_mutate(&mut self) -> bool;\n3 }\n

\n\n\n\n

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

\n\n

1 pub trait Mutatable {\n2     fn mutate(&self, decide: &mut MutateDecision) -> Self;\n3 }\n

\n\n\n\n

One way of implementing Mutatable for Program is shown below.

\n\n

 1 impl Mutatable for Program {\n 2     fn mutate(&self, mut decide: &mut MutateDecision) -> Program {\n 3         match *self {\n 4             Program::Forward(ref contained_program) => {\n 5                 if decide.should_mutate() {\n 6                     Program::Backward(Box::new(contained_program.mutate(decide)))\n 7                 } else {\n 8                     Program::Forward(Box::new(contained_program.mutate(decide)))\n 9                 }\n10             },\n11             Program::Backward(ref contained_program) => {\n12                 if decide.should_mutate() {\n13                     Program::Forward(Box::new(contained_program.mutate(decide)))\n14                 } else {\n15                     Program::Backward(Box::new(contained_program.mutate(decide)))\n16                 }\n17             },\n18             Program::Stop => Program::Stop,\n19         }\n20     }\n21 }\n

\n\n\n\n

Crossover

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

\n\n

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

\n\n

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

\n\n

Evolve

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

\n\n

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

\n\n

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

\n\n

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

\n\n

Exercises

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

\n\n\n

A framework for Genetic Programming

\n\n

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

\n\n

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

\n\n

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

\n\n

Overview of the framework

\n\n

The operations that are provided by the framework are:

\n\n

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

\n\n

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

\n\n

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

\n\n

Framework Traits

\n\n

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

\n\n

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

\n\n

AstNode

\n\n

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

\n\n

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

\n\n

1 pub trait AstNode: Any+Mutatable+Copyable+Sync {\n2     fn node_type(&self) -> usize;\n3     fn children(&self) -> Vec<&AstNode>;\n4     fn replace_child(&self, old_child: &AstNode, new_child: &mut Option<Box<AstN\\\n5 ode>>) -> Box<AstNode>;\n6 }\n

\n\n\n\n

RandNode

\n\n

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

\n\n

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

\n\n

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

\n\n

1 pub trait RandNode: Sized {\n2     fn rand(weights: NodeWeights, rng: &mut Rng) -> Self;\n3 }\n

\n\n\n\n

Mutatable

\n\n

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

\n\n

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

\n\n\n\n

Copyable

\n\n

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

\n\n

1 pub trait Copyable {\n2     fn copy(&self) -> Box<AstNode>;\n3 }\n

\n\n\n\n

impl_astnode!

\n\n

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

\n\n

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

\n\n

 1 #[derive(Clone)]\n 2 pub enum Condition {\n 3 \tTrue,\n 4 \tFalse,\n 5 \tAnd(Box<Condition>, Box<Condition>),\n 6     ...\n 7 \tLess(Box<Expression>, Box<Expression>),\n 8 \tLessEqual(Box<Expression>, Box<Expression>),\n 9     ...\n10 }\n11 \n12 impl_astnode!(Condition, 0,\n13               leaf True(),\n14               leaf False(),\n15               int And(left, right),\n16               int Less(left, right),\n17               int LessEqual(left, right),\n

\n\n\n\n

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

\n\n

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

\n\n

Moonlander

\n\n

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

\n\n

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

\n\n

Simulation

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

1 pub struct SensorData {\n2     pub x:  Number,\n3     pub y:  Number,\n4     pub vx: Number,\n5     pub vy: Number,\n6     pub o:  Number,\n7     pub w:  Number,\n8     pub fuel: Number,\n9 }\n

\n\n\n\n

Grammar

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

Let’s start by defining the sensors:

\n\n

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

\n\n

This leads us to the following initial grammar:

\n\n

Condition:

\n\n

 1 #[derive(Clone)]\n 2 pub enum Condition {\n 3 \tTrue, False,\n 4 \n 5 \tNot(Box<Condition>),\n 6     Or(Box<Condition>, Box<Condition>), And(Box<Condition>, Box<Condition>),\n 7 \n 8 \tLess(Box<Expression>, Box<Expression>), LessEqual(Box<Expression>, Box<Expressi\\\n 9 on>),\n10 \tEqual(Box<Expression>, Box<Expression>),\n11     GreaterEqual(Box<Expression>, Box<Expression>), Greater(Box<Expression>, Box\\\n12 <Expression>),\n13 }\n14 \n15 impl_astnode!(Condition, 2,\n16               leaf True(), leaf False(),\n17               int Not(cond),\n18               int Or(left, right), int And(left, right),\n19               int Less(left, right), int LessEqual(left, right),\n20               int Equal(left, right),\n21               int GreaterEqual(left, right), int Greater(left, right));\n

\n\n\n\n

Expression:

\n\n

 1 #[derive(Clone)]\n 2 pub enum Expression {\n 3 \t  Constant(Number),\n 4 \t  Sensor(Box<Sensor>),\n 5 \t  Plus(Box<Expression>, Box<Expression>), Minus(Box<Expression>, Box<Expression\\\n 6 >),\n 7 \t  Multiply(Box<Expression>, Box<Expression>), Divide(Box<Expression>, Box<Expre\\\n 8 ssion>),\n 9 }\n10 \n11 impl_astnode!(Expression, 3,\n12               leaf Constant((data n random_constant)),\n13               leaf Sensor(sensor),\n14               int Plus(left, right), int Minus(left, right),\n15               int Multiply(left, right), int Divide(left, right));\n

\n\n\n\n

Sensor:

\n\n

1 #[derive(Clone)]\n2 pub enum Sensor { X, Y, Vx, Vy, O, W, Fuel, }\n3 \n4 impl_astnode!(Sensor, 0,\n5               leaf X(), leaf Y(), leaf Vx(), leaf Vy(),\n6               leaf O(), leaf W(), leaf Fuel());\n

\n\n\n\n

Evaluation

\n\n

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

\n\n

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

\n\n

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

\n\n\n\n

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

\n\n

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

\n\n\n\n

Fitness

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

1 pub trait Fitness: Send {\n2     fn score_card(&self) -> &ScoreCard;\n3 }\n

\n\n\n\n

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

\n\n

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

\n\n

We collect the fitness like this:

\n\n

 1 pub fn score_lander<P>(program: &P, _: &mut Rng, mut sensor_data: SensorData, wo\\\n 2 rld: &World) -> LandingTrace\n 3     where P: EvaluateToCommand+AstNode\n 4 {\n 5     // ...\n 6     while !sensor_data.hit_ground {\n 7         // ...\n 8     }\n 9 \n10     LandingTrace {\n11         trace: trace,\n12         score_card: ScoreCard::new(vec![\n13             (\"survival_bonus\",   3.0 * frames),\n14             (\"fuel_bonus\",       (100.0 * total_fuel / frames)),\n15             // ...more scores here...\n16         ])\n17     }\n18 }\n

\n\n\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n\n\n\n

Appendix: Resources

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

\n\n

Below are several ways to obtain the resources

\n\n

Workshop

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

\n\n

Download

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

\n\n

Clone

It is also possible to clone the\nrepository directly. Execute\nthe following command

\n\n

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

\n\n\n\n

This will setup a repository and all the\nsubmodules correctly.

\n\n\n

Appendix: Play the Game

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

\n\n

Online

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

\n\n

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

\n\n

Offline

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

\n\n

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

\n\n\n

Appendix: Fast and the Curious

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

\n\n

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

\n\n

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

\n\n\n\n

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

\n\n

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

\n\n\n\n

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

\n\n

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

\n\n\n

What to Do

Here we give some suggestions for projects you could do

\n\n

Tweak Fitness Function
AGC
Bring your Own

\n\n

Tweak Fitness Function

In this project you will learn the importance of a fitness function by trying to\nland a lunar lander safely on the surface of the moon. Find a detailed\ndescription in the corresponding chapter.\nj\n## AGC\nWe will try to fit the series of points with a function. You find a skeleton\nproject in the AGC directory. See the AGC chapter in the accompanying book for\na description of the book.

\n\n

Bring your own

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

\n\n\n

Tweak Fitness Function

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

\n\n

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

\n\n

Straight Landing

\n\n

First scenario

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

\n\n

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

\n\n

Second scenario

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

\n\n

Does your model still evolve a successful solution?

\n\n

With a Twist

\n\n

First scenario

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

\n\n

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

\n\n

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

\n\n

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

\n\n\n

AGC

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

\n\n

Describe a grammar.
Describe a fitness function.

\n\n

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

\n\n

Description

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

\n\n\n

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\nship that took\nCharles Darwin around the\nworld. It wad during this trip that Darwin collected data that led him to\nformulate the idea of evolution. His work culminated into his seminal book\nOn the Origins of Species.↩

\n\n\n

\n\n

\n\n","tocStructure",[304,305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,346,347,348,349,350,351,352,353,354,355,356,357,358,359,360,361,362,363],{"_80":81,"_43":82,"_75":-5,"_83":84,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":81,"_43":90,"_75":-5,"_83":91,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":95,"_75":-5,"_83":96,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":100,"_75":-5,"_83":101,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":103,"_75":-5,"_83":104,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":81,"_43":106,"_75":-5,"_83":107,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":110,"_75":-5,"_83":111,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":113,"_75":-5,"_83":114,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":116,"_75":-5,"_83":117,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":81,"_43":119,"_75":-5,"_83":120,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":123,"_75":-5,"_83":124,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":110,"_75":-5,"_83":126,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":128,"_75":-5,"_83":129,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":81,"_43":131,"_75":-5,"_83":132,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":135,"_75":-5,"_83":136,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":128,"_75":-5,"_83":138,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":81,"_43":140,"_75":-5,"_83":141,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":144,"_75":-5,"_83":145,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":110,"_75":-5,"_83":147,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":128,"_75":-5,"_83":149,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":81,"_43":151,"_75":-5,"_83":152,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":110,"_75":-5,"_83":155,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":157,"_75":-5,"_83":158,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":128,"_75":-5,"_83":160,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":81,"_43":162,"_75":-5,"_83":163,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":110,"_75":-5,"_83":166,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":128,"_75":-5,"_83":168,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":81,"_43":170,"_75":-5,"_83":171,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":110,"_75":-5,"_83":174,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":81,"_43":176,"_75":-5,"_83":177,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":110,"_75":-5,"_83":180,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":128,"_75":-5,"_83":182,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":81,"_43":184,"_75":-5,"_83":185,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":110,"_75":-5,"_83":188,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":128,"_75":-5,"_83":190,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":81,"_43":192,"_75":-5,"_83":193,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":110,"_75":-5,"_83":196,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":128,"_75":-5,"_83":198,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":81,"_43":200,"_75":-5,"_83":201,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":204,"_75":-5,"_83":205,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":207,"_75":-5,"_83":208,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":113,"_75":-5,"_83":210,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":81,"_43":212,"_75":-5,"_83":213,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":216,"_75":-5,"_83":217,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":219,"_75":-5,"_83":220,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":222,"_75":-5,"_83":223,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":81,"_43":225,"_75":-5,"_83":226,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":229,"_75":-5,"_83":230,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":232,"_75":-5,"_83":233,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":81,"_43":235,"_75":-5,"_83":236,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":81,"_43":239,"_75":-5,"_83":240,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":243,"_75":-5,"_83":244,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":246,"_75":-5,"_83":247,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":81,"_43":243,"_75":-5,"_83":249,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":252,"_75":-5,"_83":253,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":255,"_75":-5,"_83":256,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":81,"_43":116,"_75":-5,"_83":258,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":94,"_43":261,"_75":-5,"_83":262,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":81,"_43":246,"_75":-5,"_83":264,"_76":85,"_97":-5,"_98":-5,"_88":-5},{"_80":81,"_43":267,"_75":-5,"_83":268,"_76":85,"_97":-5,"_98":-5,"_88":-5},"publicChapterContent","nextChapter","sections",[337,338],"routes/_store+/_layout","routes/_store+/_readers+/_layout","actionData","errors"]

Population

Nadezhda

Exercises

Table of Contents

What this book is all about

Jump aboard the HMS Beagle

Evolution

Translation

Individuals

Genetic Makeup

Environment

Fitness

Further reading

Projects

Nadezhda

Moonlander

AGC

Grammars

Grammar Game

How to play?

Nadezhda

Exercises

Abstract Syntax Trees

Nadezhda AST as enums

Exercises

Parsers

Domain Specific Language

Nadezhda

Exercises

Random Generation of AST

Nadezhda

Generating more complex grammars

Exercises

Environment

Nadezhda

Exercises

Evaluate

Nadezhda

Fitness

Nadezhda

Exercises

Population

Nadezhda

Exercises

Darwin

Nadezhda

mutate

Crossover

Evolve

Exercises

A framework for Genetic Programming

Overview of the framework

Framework Traits

AstNode

RandNode

Mutatable

Copyable

impl_astnode!

Moonlander

Simulation

Grammar

Evaluation

Fitness

Appendix: Resources

Workshop

Download

Clone

Appendix: Play the Game

Online

Offline

Appendix: Fast and the Curious

What to Do

Tweak Fitness Function

Bring your own

Tweak Fitness Function

Straight Landing

First scenario

Second scenario

With a Twist

First scenario