Lander Genetic Algorithm Simulation

Inspiration

I was inspired by a few YouTube videos explaining genetic algorithms and, more generally, how to incorporate features we see in nature into computer programs. The Coding Train's Nature of Code series on genetic algorithms was of particular inspiration while the inspiration for a lander program was from a CodinGame challenge.

What it does

This spacecraft lander genetic algorithm simulation attempts to show a population of landers as they navigate a terrain. The terrain is a Perlin noise terrain that is randomly generated each time the project is run with an atmosphere that is also randomly generated (or sometimes the terrain lacks an atmosphere). Forces such as gravity, lander thrust, drag, and wind forces are all simulated. Although the latter two don't exist on a terrain with no atmosphere. Temperature for each lander is also simulated with a default temperature of 273 which increases as the lander continues to experience drag. If the lander's temperature exceeds 1400, it overheats and receives a penalty in its fitness score (although it still continues to land as normal in the visualization). The fitness score also penalizes for change in impulse as the lander collides and for deviations between terrain slope and lander heading.

There are 20 landers/probes. Each probe possesses a "DNA" which codes the thrust at each moment in time. In the first generation, this thrust will be random and the probe will spiral out of control. However, the most successful landers based on their fitness score will have higher probabilities of being selected into the next generation. Reproduction occurs at the end of each generation. Two probes are randomly selected based on their prior probabilities and "mix" their DNA contents (by taking the average of the thrust of the two probes at each moment in time). Then a mutation occurs where there is a 1% chance of a random gene (a thrust at one point in time) changing to a random vector. This process is repeated as many times as necessary to refill the population (in this case 20). And so the process continues generation after generation until the viewer decides to stop the program.

How I built it

I built this using the p5.js library which is great for 2D animations and a web-based version of the original Processing library in Java.

Challenges I ran into

There were quite a number of bugs and issues I ran into when working on this project. I couldn't quite get the thruster appearance right so I scrapped it entirely. (The landing spacecraft still thrusts but it isn't indicated by jets firing on the lander.) I was able to solve the persisting issue of lander collisions fairly satisfactorily (although not perfect). Since a noisy terrain is not easily differentiable, I instead computed a difference quotient for an arbitrarily small change in terrain to calculate the slope of the terrain. And that was compared to the heading of the lander at collision to give a fitness score penalty if the terrain slope and lander heading deviated significantly. (For example if the lander landed on its side.)

Accomplishments that I'm proud of

It was fun to watch the population of landers evolve themselves through the generations. There are some key factors that I am looking forward to adding in the future (see What's next for Lander Genetic Algorithm Simulation).

What I learned

I learned a lot about genetic algorithms and how to represent various concepts from Darwinian natural selection such as variation, selection, and heredity in a computer simulation. Genetic algorithms can be contrasted with other algorithms from machine learning such as reinforcement learning and provide another valid method of searching for a solution (or multiple solutions) in a large space of possibilities where bruteforcing is not viable.

What's next for Lander Genetic Algorithm Simulation

There are lots of improvements that can be done with this project. While the calculation regarding lander heading has been pretty much solved for when the probe has landed, the lander still spins uncontrollably in descent. This is not necessarily a bug but certainly not the way I intended it. So an improvement here could be to add a positive fitness score if the lander is close to upright as it is descending. Additionally, I hope to fix the issue with the thruster appearance so that I can show it again on the actual canvas.

There is little data visualization on screen other than terrain attributes and the lander population's generation. I could add data about each lander in a separate screen (or on the webpage itself) such as each lander's velocity, drag, temperature, momentum, and fitness score.

Perhaps for a future hackathon, I can attempt to create a more ambitious version of this project in 3D with perhaps either Three.js, Babylon.js, or Unity where landers are simulated on a 2D noisy terrain with 3D force vectors and 3D collisions.

Built With

• javascript
• p5