Exploring Genetic Algorithms with Kotlin

This story is about chimps trying to land on Mars. Yes, really.

There are a lot and some of them can succeed. We use a genetic algorithm to select the best chimps of each generation until the selection is down to the hero who will land safely on Mars with the fullest fuel tank possible.

Disclaimer: This post is about my first experiments on genetic algorithms. I’m not an expert.

Edit: here is the complete project on github.

Landing on Mars

The algorithm answers CodinGame’s first puzzle on landing on Mars.

The Lander evolves in two dimensions. The chimp must control it using angle and thrust power commands. The gravity is -3,711 m/s² (see details on CodinGame’s website).

The challenge is to find the correct commands to have the lander hit the ground on the landing zone (horizontal) with a vertical speed lower than 40 m/s and an horizontal speed under 20 m/s.

Genetic Algorithm principles

Genetic Algorithms try to mimic the natural selection in order to resolve problems where solutions are hard to find.

The steps are :

1. generate a population of random genomes,
2. convert theses genome into input parameters of our simulation,
3. play the simulation,
4. evaluate the results of each genome,
5. select the best genomes, recombine and mutate them to produce the next generation,
6. iterate until a solution is found.

Representing the model

We must have a simulator representing precisely the model.

For that purpose, I split my code into a simplified cartesian system, small physics classes and the Lander.

This is the code of my simplified cartesian system.

The main idea of these classes is to simplify the manipulation of points, vector and lines.

Points and Vector will help us managing the position, the speed, the acceleration of the lander. The rotate function of Vector will be the only one containing trigonometry.

The line is here to represent Mars surface and check if the lander hits the ground.

Kotlin operator overloading is interesting to manipulate these concepts and simplify our domain. This will allow us to write code like:

val endPoint = startPoint + moveVector
val composedVector = vector1 + vector2

One more file for physics :

We now have all the basics to implement the Lander simulator:

The state class holds the Lander state at one moment : it’s position, angle, power, speed and fuel.

The ControlCmd holds the command that can be asked : an angle and a thrust power.

Given a lander at an initial state, we can simulate its complete trajectory after having applied a list of commands. The simulation should respect exactly the target domain constraints if we want our algorithm to be relevant. In our case, we check that applying a list of static commands ( 100 × (15°,power 1) for example) to an initial state results in having the Lander at the exact same state on CodinGame simulator.

Ok, we have our simulator. Now, let’s code the genetic algorithm.

The Genetic Algorithm

So here is the code of a generic Genetic Algorithm in kotlin:

The Gene class represents a single gene implemented by a random double. We provide a method to simplify its use as an Int.

A Genome is an array of Genes.

We have a utility class GenomeAndResult which keeps together a genome and the corresponding object created from it. This class is generic and can be reused for any domain.

The entry point of the algorithm is the findBestChimp function. This function takes two parameters that are also functions:

1. A create function that builds a object from a genome.
2. A fitness function that evaluates an object according to the goal of the algorithm.

The genetic algorithm creates a population from random genomes. The population is sorted with the fitness function. The selection process then randomly picks individuals, the best ones having more chances to procreate.

The creation of new individuals is done through a crossover combination of parent genomes. After the crossover, the genome is altered by mutations that help exploring new areas.

The last effort is now on implementing the function that creates a Lander from a genome and the fitness function. In fact it is the trickiest part. The performance of the genetic algorithm (it’s ability to rapidly converge to a solution) is defined by the quality of the creation and fitness functions.

Even if the lander crashed we should be able to compare the crashes to allow the algorithm to give more chances to the «best crashes» genomes.

Here is my code for the first CodinGame puzzle. The Lander has just a vertical trajectory and we don’t have to manage it’s angle.

Running the program we can see that the generations are rapidly converging to the best solution.

Using the commands found by the algorithm shows a perfect landing.

All the code of the MarsLander 1 is available on this github repository.

Implementing the create and fitness functions for Mars Lander 2 requires 40 lines of code. Look them up for some nice touchdowns: