Evolving a path to cover a grid

In the few years that I've been interested in the evolution/creation so-called debate, I have always wanted to make an evolutionary algorithm. These algorithms give the anti-evolution side a lot of problems, because they directly demonstrate what they claim is impossible - that mindless evolution cannot produce novelty. Watching them try to argue around these is actually quite funny - the most popular claim is that because the program itself was written by an intelligence, the output is therefore intelligently designed, which shows you the kind of weasels we have to cope with.

What follows is my first evolutionary algorithm, written using only the very basic principles of evolution: variation, natural selection, and inheritance.

The problem

Given an x-by-y grid (in this case, 24 by 24), produce a path that covers as much of the grid as possible, without going back on itself.

For a human, of course, this problem is utterly trivial, but I want to see if evolution can come up with a solution too. The idea was inspired by the Tower Assault webgame, although the problem in that is a little more difficult.

Representing the solutions

Because this is a genetic algorithm, the solution will be represented in the form of a genome - a string of code, or, if you like, virtual DNA.

To represent a path, the 'genome' is made up of a string of numbers which represent directions:

0 = north
1 = east
2 = south
3 = west
4 = empty

The 'empty' code simply gives no instruction, and is the default state of all codes in the genome to start with. The length of the genome is the same as the amount of grid squares, to give the path a chance to cover the whole grid.

To construct the path from the code, it is read left to right one number at a time. The path extends in the direction specified by the number, except in the following circumstances:

- if the way is already blocked by the path
- if the path is going off the edge of the grid
- if the path is trying to go back on itself

If an instruction is encountered that the path cannot obey for the above reasons, it is skipped.

Mating

Mating takes place between two paths, which produce one child path.

The parents genomes are cut into two pieces at the same random point. The child inherits the first piece of the first parent's genome, and the second piece from the second parent.

The child's genome then undergoes mutation. Each number in the genome has a 1/100 chance of turning into a randomly selected direction (this does not, however, rule out the possibility that it may change into itself, which has no effect on the genome).

The algorithm

The algorithm operates as follows:

1) A population of paths is obtained. At the start, these are empty, but they could be random or chosen if I wanted to.

2) Each path in the population is rated by how many grid squares it has covered.

3) The population is sorted by score.

4) The top quarter of the population is kept to survive and mate.

5) Every member of the remaining three-quarters is discarded and replaced by a child from two random maters.

6) The process repeats from (1), with this new population.

The applet

See for yourself! This applet will show the top scoring path at each generation (which, since it is guaranteed to survive, will only change when it is replaced by a better scoring mutant). I'd like to remind antievolutionists that the genomes start off empty (that is, they look like '444444444444444...').

Comments

I'm quite proud of this first attempt, but if you've played with the applet, you'll see the algorithm is far from perfect, achieving a score of about 70% most of the time. This success seems to inversely scale with the grid, decreasing in larger grids, but increasing in smaller ones. Nonetheless, it seems to consistently beat randomly generated paths, which tend to score about 40-50% at most in the same time.

I was quite surprised to find out how little mutation (1%) was actually needed for the evolution. Initially I felt a 25% (one in four) mutation rate would be enough, but after seeing its effect I can see now that that's a little like sticking DNA in a blender. In fact, the higher the mutation rate, the closer the simulation comes to simply making random paths, which as I've just said is not efficient.