Is there a way to improve my genetic algorithm?

An answer to this question on Stack Overflow.

Question

I got interested in GA and want to do my own.
This is the task, I want to achieve:
I got a "world" 16x16 fields. I create 16 bots with random genes. Each gene is an array with 4 numbers from 1-19(16-19 will turn the bot direction and 1 - 15 is the amount of field the bot will go in a specified direction). In this word I take a random position and trying to make the distance from the leader bot to the target as small as possible.

The way I create new generation:

  1. Picking 8 bots with the lowest distance and putting them into the next generation(without crossover)

  2. Doing crossover for the 8 best bots I picked in '1)'(so I get 8 new bots)

  3. Mutating randomly 2 of the crossovered bots and finally putting them into the next generation. Now I have 16 bots in the new generation.

And the problem is: I only get the distance == 0 in 1/100 of all my tries. But I get the distances 1 and 2 quite often(I wait until generation 1000 and then I give up, trying one more time) Is there is a way to improve this? Or is it not possible to do it better with GA?

Answer

There are a lot of things that are going wrong.

Some general comments

  1. Genetic algorithms are usually a course of last resort for an algorist. You use them when things like Dijkstra (which is most appropriate for your use case), linear programming, specific constraint satisfaction techniques, &c all fail. Presumably, you're using them because you want to explore this area.

  2. People who use genetic algorithms rarely expect them to achieve the global optimum of a solution. "Good" local optima are usually the best you can do. A GA will find these fairly easily, but will have a hard time "zeroing" in on a solution. (Papadimitriou, a computer scientist at UC Berkeley, has shown that evolution doesn't, in fact, maximize fitness, but rather, the mixability of genes.)

Crossover vs. Mutation

Crossover is used to interchange large parts of a genome which is known to work. Mutation refines pieces of a genome. Roughly speaking, crossover helps you combine two good solutions in hopes that this will quickly bootstrap you to an even better solution, while mutation explores the space near a solution.

Crossover can also destroy a good solution by breaking it into two pieces that don't make sense independently or combining two pieces that produce a non-sensical output.

In many situations, mutation is sufficient to explore an entire space, albeit slowly. This is the case in your space since score decreases monotonically with distance from your goal. In a more complicated space, crossover may help you jump over barriers between local minima.

Putting It Together

My recommendation is that you reduce the amount of crossover in your populations given time. Initially, crossover might help you get some rapid gains in progress. But, as time goes on, and, especially, near the end of your simulation, you'll want delicate refinement. This techniques is similar to simulated annealing.