Genetic algorithm

The big ring of the Sokol circuit is 4.3 kilometres of asphalt with long straights and sharp corners. Where on the road should you drive to make the lap as fast as possible? Clip the corner on the inside, shortening the path, or go in wide and keep your speed? Let us describe a racing line by 74 numbers, how far the car is from the centre line of the road every 60 metres, and give evolution 40 random lines. Along the centre line our car does a lap in 100.4 seconds. See what the generations do.

The first lines weave from kerb to kerb, and the car barely crawls: every kink is a corner where it has to brake. After a few dozen generations the best line smooths out, and then it begins to take the corners on a wider arc than the centre line: in some corners you can even see the racing rule “outside, inside, outside”, where before a corner the car moves to the outer edge, touches the inner one at the apex and goes out again. Nobody told the algorithm this rule; it found it by trying options. Zoom the map with the buttons to look at the corners. Switch the method to “no crossover”, “annealing” and “random”: the curves of all the runs stay at the bottom, and they can be compared on one chart.

The idea

Keep not one solution but a whole population. Each is scored with a number, its fitness. The best become parents more often; a child is put together from pieces of two parents, which is crossover, and a few of its genes change at random, which is mutation. Generation after generation, good pieces of solutions spread and combine with each other. The bet is that the problem has such pieces: a good way through one corner from one parent and a good way through another from the other.

These are all words from biology, and the algorithm itself was devised on the model of natural selection. But biology here is only a metaphor: the “genes” are numbers, the “individuals” are candidate solutions, and what makes the selection “natural” is a function the programmer writes.

How it works

Encoding. Across the road, every three points of the centre line, about 60 metres, stand “gates”, 74 in all. A gene is the car’s position in a gate: 21 options from −5 to +5 metres from the centre line in steps of half a metre (the road in the model is 12 metres wide, the car about two). Between gates the car moves across evenly. An individual is 74 genes, that is, the whole racing line of a lap.

Fitness is the lap time, and it has to be made smaller. For each point of the line the corner radius R is computed from it and its two neighbours, and the speed there cannot exceed √(a·R), or the car will fly off; a = 1.5 g. Then two passes round the ring: forward, where the speed grows no faster than an acceleration of 0.6 g allows, and backward, where it must manage to drop before a corner with braking at 1.5 g. Real autonomous racing systems compute the speed profile the same way, with a forward and a backward pass, for example Alexander Heilmeier and co-authors (2020). The model is crude: it has no mass, no tyres, no aerodynamics, but the corners, acceleration and braking in it are real.

Selection. A parent is chosen by tournament: take three random individuals and keep the fastest. Good lines win tournaments more often, but bad ones sometimes become parents too, and the population does not converge on one solution too early.

Crossover. Two random cuts split the lap into three pieces; the child takes the middle piece from the second parent and the rest from the first. On the track this means literally: “take this section like your father, and the rest of the lap like your mother”. It happens with probability 0.9; otherwise the child is a copy of the first parent.

Mutation. Each gene with probability 2/74 is shifted by an amount from −1.5 to +1.5 metres. On average two genes out of 74 change.

A generation. The two best lines pass into the new generation unchanged, so the best result is not lost; the other 38 places are taken by children. Each child is one lap-time evaluation, so a generation costs 38 evaluations.

A fair comparison

Evolution is easy to love for its beauty, so it has to be compared with rivals on equal terms: the same lap, the same car model and the same number of lap-time evaluations, the most expensive operation. The rivals: the same algorithm without crossover (only mutation and selection), simulated annealing, which shifts one gene and accepts worsening by the Metropolis rule, and random search over lines. Below is the median of three runs: by how many seconds the best lap found is slower than 98 seconds.

What the chart shows.

• Random search is hopeless. Even the best of 8000 random lines does a lap in 104.4 seconds, four seconds worse than simply driving along the centre line. A random line weaves, and 74 genes give 21⁷⁴ options, a number of 98 digits, almost all of them bad.
• Crossover works. After a thousand evaluations the algorithm with crossover is 2.3 seconds behind 98 seconds, and without crossover 4.9; after 8000, 0.28 and 0.57. Well-taken corners appear in different lines, and crossover gathers them into one, while one mutation after another has to find them in turn.
• Annealing is no worse. At 500 and 1000 evaluations the genetic algorithm is ahead, at 2000, 4000 and 8000 annealing is (0.21 seconds against 0.28 after 8000 evaluations). For this problem that is the honest verdict: the population gives no gain in the number of evaluations compared with a good local search.

But the population has an advantage that this chart does not show. All 38 children of a generation are evaluated independently of each other, and if you have 38 processors, a generation takes the time of one evaluation: 8000 evaluations are 210 “ticks”. Annealing is built as a chain: the next step cannot be taken without knowing the result of the previous one, and 8000 evaluations are 8000 ticks. When one evaluation is a minute-long simulation rather than a few microseconds, as here, the difference becomes decisive. This is just how, in 2017, researchers at Uber AI trained neural networks with four million weights to play Atari games: a simple genetic algorithm learned one game in about an hour on 720 processor cores, and in four hours on one desktop computer. There was, incidentally, no crossover in their algorithm at all, “for simplicity”, as the authors write.

What the schema theorem promises

Why should crossover help at all? John Holland, who devised genetic algorithms in their classic form, answered with the schema theorem. Let the individuals be strings of length l of zeros and ones. A schema is a template where some positions are fixed and the rest are marked with an asterisk, “anything”: the schema 1**0 matches 1000, 1010, 1100 and 1110. A schema H has an order o(H), the number of fixed positions, and a defining length δ(H), the distance between the outermost fixed positions: 1**0 has order 2 and length 3. Let m(H, t) be the number of strings of generation t that match the schema, f(H, t) their mean fitness, and f̄(t) the mean fitness of the whole generation.

The theorem reads like this: a schema that is better than average (f(H) > f̄), short and of low order multiplies on average, and from generation to generation there is more of it. Holland, and later David Goldberg in a 1989 book, drew from this the “building block hypothesis”: a genetic algorithm finds short good schemata and assembles a solution from them, like bricks. On the track this is familiar: “a well-taken corner” is just a short schema of a few neighbouring genes.

But the theorem promises much less than it seems.

• It is an inequality for one generation and for an expectation. About what will happen ten generations on in a population of forty strings, where randomness is large, it says nothing.
• f(H, t) is the mean fitness of the schema’s strings in the current generation, not the “true” worth of the schema. It changes with the population, and when the population converges, f̄ catches up with it, and the “exponential growth” of good schemata that is sometimes written about stops.
• The theorem counts only the destruction of schemata and says nothing about the main thing, how crossover combines good schemata. The building block hypothesis is not proved.
• By the “no free lunch” theorem of Wolpert and Macready (1997), averaged over all possible problems no search algorithm is better than any other, random search included. If a genetic algorithm is good at something, it is thanks to the structure of the particular problem, not by itself.

The most vivid test of the hypothesis was set up in 1992–1993 by Melanie Mitchell, Stephanie Forrest and Holland. They devised a function that seems made for it, the “Royal Road”: a string of 64 bits is split into eight blocks of eight, and each block of all ones scores 8 points. Building blocks in their purest form. They expected the genetic algorithm to beat hill climbing. It came out the other way round.

In the experiment of Mitchell, Holland and Forrest the genetic algorithm found the string of all ones in 61,334 evaluations on average, while the simplest hill climbing, flip a random bit and keep it if things did not get worse, took 6179, almost ten times fewer. In our measurement thirty runs give an average of 32,175 evaluations for the genetic algorithm and 7134 for hill climbing.

The reason can be seen in the scene. As soon as some string completes a full block, it multiplies quickly, and along with the block its zeros in the other blocks spread through the population; the authors called this “hitchhiking”. Other strings, which already had other blocks almost assembled, are crowded out, and the population loses the diversity it was kept for. Hill climbing, on the other hand, assembles the blocks one at a time: a one-bit mutation that does not spoil what is assembled is accepted, and sooner or later a block comes together. The authors computed that for N blocks of K bits hill climbing needs on average about 2^K·N·(ln N + γ) evaluations, where γ ≈ 0.577 is Euler’s constant; for eight blocks of eight that is about 5400.

Code

The program reads the centre line of the ring from the data file, builds the normals, computes the lap time and runs the evolution twice: with crossover and without. Floating-point arithmetic is identical in Python and Go down to the last bit; for this, in Go the products are wrapped in float64(…): otherwise on ARM processors the compiler fuses a*b + c into one operation with different rounding, and the evolution goes off down another path.

The run is short, 40 generations of 24 lines each, to fit into the site’s sandbox, but the difference shows even here: with crossover the line gets down to 100.35 seconds, without crossover to 101.64. The letters in the last line are the genes of the best line: “a” is five metres right of the centre line, “u” five metres left, “k” on the centre line.

Notice how little of the program is the evolution itself: a tournament, a cut, a shift of genes and a sort to find the two best. Almost all of the code and almost all of the running time is the fitness function. This is almost always so: a genetic algorithm is written in half an hour, and the model it evaluates in weeks.

What it costs

A generation of N individuals of length l costs N fitness evaluations plus O(N·l) for crossover and mutation and O(N log N) for sorting to find the best. If an evaluation costs c, G generations are O(G·N·c), and almost always c outweighs everything else. For the racing line c = O(l): two passes over 221 points. Memory is O(N·l) for the population.

There are no guarantees on time, as with annealing: a genetic algorithm does not know whether it has found the best, and it is stopped by a budget or when the best result has stopped changing. And the N evaluations of a generation are independent and are split between processors without any rework of the code; this is the main strength of the method.

When a genetic algorithm fits

Our experiment and the Royal Road experiment together give a sober picture. A genetic algorithm is not a magic universal optimiser but a reasonable choice under certain conditions.

• The evaluation is a black box. Fitness is computed by a simulation, an experiment, another program, and nothing is known about its structure: no gradient, no fast recomputation after a small change. Annealing then also has to evaluate everything anew, and its advantage in simplicity disappears.
• Evaluations can be computed in parallel. A generation is a batch of independent jobs, and there are plenty of cores and machines today.
• The solution has independent parts that can be found separately and put together, like the corners of a track. Then crossover really does save evaluations: in our case by half.
• Not one answer but a set is needed. A population naturally keeps many different good solutions, and in multi-objective problems, where both fast and cheap matter, the whole trade-off front at once; this is how the NSGA-II algorithm of Kalyanmoy Deb and co-authors (2002) works.

And when it is not worth it. If the problem has an exact or specialised method, take it: in practice a car’s racing line is computed by quadratic programming and optimal control, not evolution. If a move is cheap and its cost easy to recompute, start with local search or annealing. And always compare with a simple rival at an equal number of evaluations, as we did above: the Royal Road shows that even a problem devised for a genetic algorithm can turn out easier for hill climbing.

Where it works

• Antennas. For the three satellites of NASA’s Space Technology 5 mission, the engineers Jason Lohn, Gregory Hornby and Derek Linden grew an antenna with an evolutionary algorithm: it turned out better than the antenna designed by hand by a contractor, and on 22 March 2006 it flew into space; the authors call it the first hardware designed by computer evolution in space.
• Neural networks without a gradient. The “deep GA” of Uber AI (2017) trained networks with millions of weights to play Atari and in places beat reinforcement learning; OpenAI’s evolution strategies of the same year, a related method, also relied on massive parallelism.
• Multi-objective design: NSGA-II and its descendants give an engineer a set of trade-offs between weight, strength and cost, from which a person then chooses.
• Tuning parameters of simulations, schedules, other algorithms, where each evaluation is a run of something long.

History

The idea of modelling evolution on a computer appeared almost simultaneously in several groups in the 1950s and 1960s. In the 1960s Ingo Rechenberg and Hans-Paul Schwefel devised evolution strategies, to choose the shape of bodies in a wind tunnel, and Lawrence Fogel evolutionary programming of finite automata. John Holland and students studied adaptive systems in the same years, and in 1975 Holland published the book “Adaptation in Natural and Artificial Systems”, which described the genetic algorithm with a population, crossover and mutation and proved the schema theorem. The method spread widely after the book by Holland’s student David Goldberg, “Genetic Algorithms in Search, Optimization, and Machine Learning” (1989).

Criticism came from inside too: the Royal Road experiments of Mitchell, Forrest and Holland in the early 1990s showed that the building block hypothesis explains far from everything, and the theorem of Wolpert and Macready (1997) recalled that there is no universally best search method.

Problems

The first is the heart of our example: the lap time of a racing line, by two passes round the ring; one of the tests is the real Sokol. The second is the schema theorem at work: estimate how many strings of a schema will be in the next generation.