Friday, 7 January 2011

Experiments With A Simple Evolutionary Algorithm (2)

Why is this interesting?

It's the way that the problem is solved. Normally with a program you work out what the problem is that needs to be solved and write code to solve that specific problem. With this algorithm less understanding is needed, you just need to work out if one child is 'fitter' than another, everything else is solved randomly.

Mama doesn't know best

In my original version of the algorithm I allowed cloning. If no child was better than the parent then the parent would be passed back to start the next generation. When I took this out, it seemed to make little or no difference to the number of generations that were taken to solve the problem.


This is a very simple genetic algorithm, it relies solely on mutation, rather than sexual breeding, and it only breeds from one, the very best, child.

I haven't tried it yet, but I suspect that it would be easy for the program to vanish up a blind alley.

Say that, instead of a phrase, the goal was to solve a maze, or to find a route on a road map between two points, the fitness test would probably be distance from the goal. In either of the two examples the test could easily drive the program into a dead end -and it has no way of backing out of it.

How to get out of it? What happens in life? In short I haven't a clue. A few  possible approaches would be :

  1. Relax the breeding algorithm to let more than the very best breed, perhaps by having multiple children, their number determined by fitness.
  2. Sex (imagine Clarkson saying it) this would shake things up a bit.
  3. Backtracking -valid in AI (and politics) but maybe not in evolution.
  4. Competition, more starting places, so more routes to the goal.
I may try some of these out, but I want to play with Bimorphs in HTML5 as well -oh and find a job.

No comments:

Post a Comment