A glowing DNA double helix

Genetic algorithms explained: from random letters to mice that find the cheese

Build a genetic algorithm in JavaScript with a fitness function, selection, crossover and mutation. Try every step in a live demo, and watch a group of mice evolve their way to a piece of cheese.

In the demo below, 100 mice try to get from the left side of a garden to a piece of cheese. Nobody tells them where to go. In the first generation, they just run around at random, and most of them bump into a hedge. But every new generation is bred from the mice that got closest to the cheese, and after a while, they find their way around the hedge in the middle. Click or tap the garden to move the cheese, and watch them work it out all over again:

Speed

By the end of this tutorial, you'll know how to build this yourself. First, you'll learn each step on a simpler problem: guessing a phrase. Then you'll use the same steps to evolve the mice.

What is a genetic algorithm?

A genetic algorithm finds a solution to a problem by copying the way evolution works in nature. You start with a group of random attempts and breed better ones from them, generation after generation, until they're good enough. The data that describes an attempt is called its DNA.

Every genetic algorithm is built from the same five parts:

  • Population - A group of attempts at a solution. In the demo above, each mouse is one attempt.
  • Fitness - A score for each attempt. The closer a mouse gets to the cheese, the higher its score.
  • Selection - Picking the parents for the next generation. Attempts with a higher score are more likely to be picked.
  • Crossover - Mixing the DNA of two parents to make a child.
  • Mutation - Changing a small part of the DNA at random, so that something new can show up.

A genetic algorithm is useful when you can tell how good a solution is, but you don't know how to build a good one. It's easy to measure how close a mouse gets to the cheese, but it's hard to write down the moves that get it there. So you let the algorithm find those moves.

Try to guess a phrase at random

Let's say you want the computer to come up with the phrase 'SPICY YOGHURT'. The phrase will be right there in the code, but pretend the computer doesn't know it. All it can do is check how close a guess is. The simplest thing you could try is guessing at random. Here are two functions that make a random guess of 13 characters, using the 26 letters of the alphabet and a space:

const target = 'SPICY YOGHURT';
const letters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ ';

function getRandomLetter() {
    return letters[Math.floor(Math.random() * letters.length)];
}

function getRandomGuess() {
    let guess = '';
    for (let i = 0; i < target.length; i++) {
        guess += getRandomLetter();
    }
    return guess;
}

getRandomLetter() picks a random character from letters. A string works like an array here, so this is just like picking a random item from an array, as in the tutorial about random numbers in JavaScript. getRandomGuess() calls getRandomLetter() once for every character of target.

The demo below makes random guesses as fast as it can and keeps the best guess so far. Characters in the right spot get a green box:

Even after a million guesses, the best guess usually has only 6 characters right, sometimes 7. That's because each of the 13 characters can be one of 27 options, so there are 27 to the power of 13 possible guesses. That's about 4 quintillion! At a million guesses per second, it would take around 128,000 years on average to hit the right one. So how does a genetic algorithm do better?

Score every guess with a fitness function

Random guessing throws away everything it learns. A guess with 6 characters right is a lot closer than a guess with 1, but the next guess starts from scratch. A genetic algorithm keeps the good guesses around and builds on them. To do that, it needs to know which guesses are good.

That's the job of the fitness function: it gives every guess a score. Here, the score is the number of characters in the right spot:

function calculateFitness(guess) {
    let score = 0;
    for (let i = 0; i < target.length; i++) {
        if (guess[i] == target[i]) {
            score++;
        }
    }
    return score;
}

For 'SKICQ XWGLZFT', calculateFitness() returns 6, because the S, the I, the C, the space, the G and the T are in the right spot. A perfect guess scores 13.

The fitness function is the only part of the algorithm that knows what you're looking for. That's why the score needs to show how close a guess is, not just whether it's right. If the function only said right or wrong, almost every guess would score 0, and the algorithm would be back to guessing blindly.

Give better guesses a higher chance of becoming parents

A genetic algorithm doesn't work with one guess at a time, but with a whole group of guesses, called the population. Say you start with 200 random guesses from getRandomGuess(), each with a score from calculateFitness(). That's the first generation.

The next step is selection: picking the parents for the next generation. You could simply take the best guesses, but then the population quickly turns into copies of the same guess. A guess with a lower score might still get a character right that the best guess gets wrong. So instead, a guess's chance of being picked grows with its score.

A common way to do that is to use a roulette wheel. Each guess gets a slice of the wheel in proportion to its score. A guess with a score of 10 gets a slice twice as big as a guess with a score of 5. A guess with a score of 0 gets no slice, so it can't become a parent.

Then you spin the wheel. The roulette wheel is the same idea as the weighted random pick in the tutorial about random numbers in JavaScript, where rare loot has a small chance and common loot a large one. Here's the code:

function pickParent(population, scores) {
    let totalScore = 0;
    for (const score of scores) {
        totalScore += score;
    }

    let spin = Math.random() * totalScore;
    for (let i = 0; i < population.length; i++) {
        spin -= scores[i];
        if (spin < 0) {
            return population[i];
        }
    }
    return population[population.length - 1];
}

pickParent() adds up all the scores and picks a random number between 0 and that total. Then it goes through the guesses and subtracts each score from that number until the number drops below 0. The guess where that happens is the parent. The last line is a safety net: a tiny rounding error can leave the number just above 0 at the end of the loop. That can happen with scores that have decimals, like the ones for the mice later on.

Another way to pick parents is a tournament. You pick two random guesses, and the one with the higher score wins:

function pickParentByTournament(population, scores) {
    const a = Math.floor(Math.random() * population.length);
    const b = Math.floor(Math.random() * population.length);
    return scores[a] > scores[b] ? population[a] : population[b];
}

Try both in the demo below. The number after each guess is its score. Press Pick parents to choose two:

Selection

On the roulette wheel, guess 5 has the highest score, 11, and the biggest slice, so it's picked most often. But guess 2 is still picked now and then, even though it has the lowest score. In a tournament, the worst guess only wins if it's picked twice and plays against itself. Both work fine. From here on, this tutorial uses the roulette wheel.

Mix two parents with crossover

Two parents make one child. For the phrase, the DNA of a guess is simply its characters. The child gets the first part of one parent and the rest of the other, cut at a random spot. This is called crossover:

function makeChild(parentA, parentB) {
    const cut = Math.floor(Math.random() * parentA.length);
    return parentA.slice(0, cut) + parentB.slice(cut);
}

slice(0, cut) takes the characters before the cut from parentA, and slice(cut) takes the rest from parentB. In the demo below, parent A has the start of the phrase right, and parent B the end. Press New child to cut them at another spot. The code under the demo shows the two parts and the child:

Live demo The code updates as you play around
// This time, the cut is at 6
parentA.slice(0, 6); // 'SPICY '
parentB.slice(6);    // 'YOGHUBT'
child;               // 'SPICY YOGHUBT'

When the cut is at 6, the child gets 'SPICY ' from parent A and 'YOGHUBT' from parent B. With 12 characters right, it's better than both of its parents! That's the idea behind crossover: the good parts of different parents can end up together in one child. But crossover can also go the other way and give a child the bad parts of both. Those children get a low score, so they're less likely to become parents themselves.

Add a little mutation

With selection and crossover, the guesses get better and better. But there's a problem. Crossover only mixes characters that are already there. If no guess in the population has a G in the ninth spot, no child will ever get one. A character can also get lost if none of the guesses that had it are picked as parents.

The fix is mutation: every character of a child has a small chance to change into a random one. Here's the code, with a chance of 1%:

const mutationRate = 0.01;

function mutate(guess) {
    let result = '';
    for (const letter of guess) {
        result += Math.random() < mutationRate
            ? getRandomLetter()
            : letter;
    }
    return result;
}

Now you have all the pieces. Here's the rest of the genetic algorithm for the phrase. It starts with 200 random guesses and makes new generations until one of the guesses is 'SPICY YOGHURT':

const populationSize = 200;

let population = [];
let generation = 1;

window.onload = init;

function init() {
    for (let i = 0; i < populationSize; i++) {
        population.push(getRandomGuess());
    }
    while (!population.includes(target) && generation < 1000) {
        makeNextGeneration();
    }
    console.log('Generation ' + generation);
}

function makeNextGeneration() {
    const scores = population.map(calculateFitness);
    const nextPopulation = [];
    while (nextPopulation.length < populationSize) {
        const parentA = pickParent(population, scores);
        const parentB = pickParent(population, scores);
        nextPopulation.push(mutate(makeChild(parentA, parentB)));
    }
    population = nextPopulation;
    generation++;
}

makeNextGeneration() scores every guess with calculateFitness(), and then fills a new population with children. Each child gets two parents from pickParent(). makeChild() mixes them, and mutate() changes the result a little. The loop in init() stops when the phrase is in the population, or after 1,000 generations, in case it never shows up. Then init() logs the generation number to your browser's console.

To try it yourself, put the code from this section and the sections before it in a <script> tag in an HTML file, and open the file in your browser. Leave out the small code block right under the crossover demo. It only shows what one cut does, and it would cause an error in the full program.

You can also try it right here, with three mutation rates:

Mutation rate

With 1%, the algorithm usually finds the phrase in 20 to 100 generations, often around 40. That's about 8,000 guesses, instead of 4 quintillion. With 0%, it often gets stuck with a character or two wrong, because the right character is no longer anywhere in the population. With 30%, it never gets there, because mutation breaks the right characters just as fast as selection can spread them. A little mutation goes a long way.

Give a mouse its own DNA

A phrase is easy to score, but it isn't much to look at. So let's move on to the mice. Each mouse has to get from the left side of the garden to the cheese, without running into a hedge. It doesn't know where the cheese is. It just follows its DNA.

The DNA of a mouse is a list of 300 directions, one for each step. At every step, the mouse steers a little in the direction its DNA gives for that step. That's a steering force, like in the tutorial about steering behaviors in JavaScript, but here it comes from the DNA instead of from a target. Here's the Mouse class:

const lifespan = 300;
const maxForce = 0.4;
const maxSpeed = 3.5;

class Mouse {
    constructor(dna) {
        this.dna = dna;
        this.x = 60;
        this.y = 200;
        this.vx = 0;
        this.vy = 0;
        this.crashed = false;
        this.reachedCheese = false;
        this.steps = 0;
    }

    update(step) {
        const angle = this.dna[step];
        this.vx += Math.cos(angle) * maxForce;
        this.vy += Math.sin(angle) * maxForce;

        // Never go faster than maxSpeed
        const speed = Math.hypot(this.vx, this.vy);
        if (speed > maxSpeed) {
            this.vx *= maxSpeed / speed;
            this.vy *= maxSpeed / speed;
        }

        this.x += this.vx;
        this.y += this.vy;
        this.steps++;
    }
}

function getRandomDna() {
    const dna = [];
    for (let i = 0; i < lifespan; i++) {
        dna.push(Math.random() * Math.PI * 2);
    }
    return dna;
}

In update(), the mouse looks up the direction for this step in its DNA: an angle in radians. Math.cos() and Math.sin() turn that angle into a force along the x and y axes. The mouse adds that force to its velocity, which is the speed and direction it moves in. The speed never goes above maxSpeed, so the mouse can't race off. getRandomDna() makes a list of 300 random angles between 0 and Math.PI * 2, which is a full circle.

Every mouse starts at (60, 200), on the left side of a garden that's 750 pixels wide and 400 pixels high. lifespan is the number of steps a mouse gets, one for each direction in its DNA. maxForce is how hard a mouse steers at each step, and maxSpeed is how many pixels it can move in one step. steps counts the steps a mouse takes before it stops, crashed says if it hit a hedge, and reachedCheese says if it found the cheese. You'll need steps, crashed and reachedCheese in the next sections.

Here are 100 mice with random DNA:

They run all over the place, and most of them bump into the hedge around the garden. Now and then, one of them ends up near the cheese by luck. That's all a genetic algorithm needs to get started.

Let the mice evolve

To evolve the mice, you use the same steps as for the phrase. First, you need a few global variables:

const populationSize = 100;
const mutationRate = 0.01;

let mice = [];
let cheese = {x: 690, y: 200};
let generation = 1;
let step = 0;

step counts how many steps the current generation has taken so far.

Next, the fitness function. The closer a mouse ends up to the cheese, the higher its score. A mouse that runs into a hedge gets a much lower score, so that the mice learn to stay away from hedges:

function getDistance(a, b) {
    return Math.hypot(a.x - b.x, a.y - b.y);
}

function calculateFitness(mouse) {
    let fitness = 1 / getDistance(mouse, cheese);
    if (mouse.crashed) {
        fitness /= 10;
    }
    return fitness;
}

getDistance() uses Math.hypot() to measure the distance between the mouse and the cheese. One divided by that distance gives a high score when the mouse is close. A mouse that ends up 50 pixels from the cheese scores twice as much as one that ends up 100 pixels away.

Every frame, each mouse takes one step, so at 60 frames per second, a generation of 300 steps takes 5 seconds. After that, the next generation starts:

function updateMice() {
    for (const mouse of mice) {
        if (mouse.crashed || mouse.reachedCheese) {
            continue;
        }
        mouse.update(step);
        if (getDistance(mouse, cheese) < 20) {
            mouse.reachedCheese = true;
        } else if (isHedge(mouse.x, mouse.y)) {
            mouse.crashed = true;
        }
    }
    step++;
    if (step == lifespan) {
        makeNextGeneration();
    }
}

function makeChildDna(dnaA, dnaB) {
    const cut = Math.floor(Math.random() * dnaA.length);
    return dnaA.slice(0, cut).concat(dnaB.slice(cut));
}

function mutateDna(dna) {
    return dna.map(function (angle) {
        return Math.random() < mutationRate
            ? Math.random() * Math.PI * 2
            : angle;
    });
}

function makeNextGeneration() {
    const scores = mice.map(calculateFitness);
    const nextMice = [];
    while (nextMice.length < populationSize) {
        const parentA = pickParent(mice, scores);
        const parentB = pickParent(mice, scores);
        const dna = makeChildDna(parentA.dna, parentB.dna);
        nextMice.push(new Mouse(mutateDna(dna)));
    }
    mice = nextMice;
    generation++;
    step = 0;
}

updateMice() skips the mice that already crashed or found the cheese. A mouse that gets within 20 pixels of the cheese has found it. isHedge() checks if a point is in a hedge or outside the garden. In the example code at the end of this page, the only hedge is a rectangle. So isHedge() only has to check that rectangle and the edges of the garden.

Two more pieces of code aren't shown here, but they're in the example code. At the start, a loop creates 100 mice with getRandomDna() and puts them in mice. And a game loop calls updateMice() once every frame, as in the tutorial about the JavaScript game loop.

makeNextGeneration() works just like the one for the phrase. pickParent() is exactly the same function. makeChildDna() and mutateDna() do the same as makeChild() and mutate(), but with a list of angles instead of a string. concat() glues two lists together, the way + does with strings.

A child runs the first part of parent A's route and then steers like parent B, from wherever it is at that moment. That doesn't always work, but it works often enough.

Here's the result, in a garden without hedges in the middle:

Speed

In the first few generations, a handful of mice get close to the cheese by luck. They get the highest scores, so their DNA ends up in the next generation. After 20 generations, about a third of the mice reach the cheese, and more and more of them follow. The demo starts at 5x speed. Switch to 1x to watch each generation at normal speed.

Reward the fastest mice

There's one thing the fitness function doesn't look at: time. Every mouse stops as soon as it gets within 20 pixels of the cheese. So all the mice that reach the cheese get about the same score, whether they ran straight there or took a long detour. That means the algorithm has no reason to prefer the fast mice. On top of that, a mouse that reaches the cheese scores only a little more than one that ends up just short of it.

To fix that, give a mouse that reaches the cheese a bonus for the steps it had left:

function calculateFitness(mouse) {
    let fitness = 1 / getDistance(mouse, cheese);
    if (mouse.crashed) {
        fitness /= 10;
    }
    if (mouse.reachedCheese) {
        const stepsLeft = lifespan - mouse.steps;
        fitness *= 1 + 10 * stepsLeft / lifespan;
    }
    return fitness;
}

stepsLeft is the number of steps the mouse didn't need. A mouse that gets to the cheese with half of its steps left scores 6 times as much as it would without the bonus. The 10 makes the bonus big enough for fast mice to stand out. You can try other numbers too.

The demo below has a hedge between the mice and the cheese. Switch between the two fitness functions:

Fitness
Speed

With Distance, fewer than a third of the mice make it around the hedge after 40 generations. With Distance and time, the first mice that make it get a big bonus, and after 40 generations, almost half of the mice reach the cheese. The time of the fastest mouse also keeps going down. The algorithm is the same. Only the fitness function is different.

Keep your best mice with elitism

Sometimes, the best mouse of a generation doesn't have any children. The roulette wheel gives it the best chance, but it can still lose. And even if it does have children, crossover and mutation can break the very moves that made it good. When that happens, the next generation can be worse than the one before.

Elitism fixes that: the best mice go on to the next generation unchanged. Two is enough. Add const eliteCount = 2; to the other global variables at the top of your script. Then add this code to makeNextGeneration(), right below the line that creates nextMice:

// Keep the best mice as they are
const ranked = mice.slice().sort(function (a, b) {
    return calculateFitness(b) - calculateFitness(a);
});
for (let i = 0; i < eliteCount; i++) {
    nextMice.push(new Mouse(ranked[i].dna));
}

slice() makes a copy of the list of mice, and sort() puts the copy in order, from the highest score to the lowest. The two best mice each come back as a new Mouse with the same DNA, so they start again on the left side of the garden. The while loop then fills the other 98 spots. The graph in the top-right corner of the demo below shows the best score of every generation:

Elitism
Speed

With elitism off, the line sometimes drops, because the best mice of the previous generation didn't make it into the next one. With elitism on, it never drops, because the best mice are always still there. That also helps the rest of the mice: it takes about 10 fewer generations for half of them to reach the cheese.

Build your own garden

Now it's your turn. In the garden below, you can draw hedges and move the cheese. Choose Hedge or Eraser and draw on the garden, or choose Cheese and click or tap to put the cheese somewhere else. The mice keep evolving while you change things:

Tool
Mutation rate
Speed

This garden uses elitism and the fitness function that looks at both distance and time. Try the three mutation rates. With 0.1%, almost all of the mice quickly find the cheese, but they all take the same route and hardly try anything new. With 10%, only a few mice make it, because mutation keeps breaking the good routes. With 1%, you get something in between.

Then try to fool them. Draw a box around the cheese, with the opening on the far side, away from the mice. The mice that end up right in front of the near wall of the box are the closest to the cheese, so they get the highest scores. Soon, a lot of mice crowd against that wall, and hardly any of them ever find the opening. This is called a local optimum: a solution that's better than everything close to it, but not the best one.

In the demo below, the box is already in the garden. Watch what happens after a few generations:

Speed

To find the opening, a mouse would first have to move away from the cheese. If a mouse moves away but doesn't make it all the way around, it ends up farther from the cheese than the mice at the wall. So it gets a lower score.

More mutation doesn't help much, because a mouse would need a lot of lucky changes at once to find the way in. A better fix is a smarter fitness function, for example one that measures the walking distance around the hedges instead of the distance in a straight line. But to measure that, you need to know the way, and then you might as well use a pathfinding algorithm like A*.

Common questions about genetic algorithms

Is a genetic algorithm machine learning?

Not in the usual sense. Machine learning normally means training a model on lots of data. A genetic algorithm doesn't need data, only a way to score an attempt. It's a search method from the field of artificial intelligence, like the A* algorithm. Genetic algorithms and machine learning do meet in neuroevolution: a genetic algorithm evolves a neural network, for example one that steers a car in a game.

How do you choose the mutation rate and the population size?

Start with a mutation rate of around 1% per character or step, and a population of 100 to 200. Then experiment. A mutation rate that's too high breaks good solutions, and with one that's too low, the algorithm gets stuck. For the phrase in this tutorial, a population of 50 needs about 550 generations, and a population of 1,000 only about 20. But each generation of 1,000 is 20 times as much work as one of 50. A population of 200 needs the fewest guesses in total, about 8,000.

Why does my genetic algorithm get stuck?

Usually, the population has lost its diversity. All the attempts are almost the same, so crossover has nothing new to mix. More mutation or a bigger population can help. Another reason is a local optimum, like the box in the garden: the fitness function leads the population into a dead end. In that case, it's time to rethink the fitness function.

Does a genetic algorithm always find the best solution?

No. It usually finds a good solution, but there's no guarantee that it's the best one, or that it finds one at all. If you need the best answer and there's a way to calculate it, like the shortest path through a maze, use that instead.

Why not just use A* to find the cheese?

You could, and it would be much faster. The A* algorithm from the tutorial about pathfinding algorithms knows the whole map and calculates the shortest path right away. A genetic algorithm is for problems where you can score a solution, but you can't calculate it. The mice are just an example that you can watch.

What's the difference between a genetic algorithm and an evolutionary algorithm?

An evolutionary algorithm is any algorithm that mimics evolution, with a population, selection and small changes from one generation to the next. A genetic algorithm is the best-known kind, with DNA, crossover and mutation. Other kinds, like evolution strategies, mutate the DNA in a different way and often skip crossover.

Can a genetic algorithm solve the traveling salesman problem?

Yes, it's a classic example. The DNA is the order in which the salesman visits the cities. You do need a different crossover and mutation, because every city has to appear in the list exactly once. A common mutation swaps two cities, and a common crossover copies part of one parent and fills in the rest in the order of the other. The algorithm finds a short route, but not always the shortest.

What are genetic algorithms used for?

For problems with lots of possible answers and no easy way to calculate the best one. In 2006, NASA launched three small satellites, each with an antenna designed by an evolutionary algorithm. The antennas had an odd, bent shape that no human designer would have come up with. Genetic algorithms are also used for timetables and schedules, for designing parts, and in games, to evolve creatures, levels or computer players.

Is Conway's Game of Life a genetic algorithm?

No. In Conway's Game of Life, cells live or die by fixed rules, and a generation is just the next step. Nothing gets a score, and nothing is selected. A genetic algorithm has generations too, but each one is bred from the best attempts of the one before.

Example code: mice that find the cheese

Here's an example page that puts the basics from this tutorial together in a single HTML file. It evolves 100 mice using elitism and the fitness function that looks at both distance and time. There's one hedge in the garden, and you can click or tap to move the cheese. Paste the code below into an HTML file and open it in your browser:

Conclusion

A genetic algorithm finds a solution by mimicking evolution. You start with a population of random attempts, give each one a score with a fitness function, and let the better ones become parents more often. Crossover mixes their DNA, and mutation adds a little randomness. Generation after generation, the attempts get better, without you ever telling them how.

The steps are always the same, whether you're guessing a phrase or evolving mice that find the cheese. Only the DNA and the fitness function change. Most of the work is in the fitness function: if it rewards the wrong thing, the algorithm finds the wrong thing, as the box in the garden showed.

That's all for now. If you have any questions, feel free to ask them in the comment section. You can