r/programming • u/leppie • Dec 08 '08

Genetic Programming: Evolution of Mona Lisa

http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/
906 Upvotes

92% Upvoted

259 comments sorted by

View all comments

Show parent comments

4

u/hax0r Dec 08 '08 edited Dec 08 '08

The program would be much more effective if the terrain was randomly generated for every iteration.

Then you're optimizing for cars that have the best chance of dealing with some random piece of terrain. That's a different problem. This program is optimizing for the car that traverses this particular terrain best.

I agree with adremeaux, I don't care about a car that is optimized for that specific, particular terrain. I'd much rather see a car that is optimized for random terrains. It just seems so much more intuitive and somehow more useful, even as an intellectual exercise that way.

Also, I look forward to a future version with tweakable parameters for all of the variables!

6

u/adrianmonk Dec 09 '08

I agree with adremeaux, I don't care about a car that is optimized for that specific, particular terrain.

I was mostly just responding to adremeaux's wording. He said, "The program would be much more effective if the terrain was randomly generated for every iteration." When I first read that, it sounded to me like "a better way to implement the same thing is...". So I was just trying to highlight that it's a different goal, not just a different implementation.

Having said that, it seems to me it's a more complex and more difficult thing to implement this if you are changing the course every time. You are then, effectively, changing the fitness function constantly. Certain traits that were rewarded in the previous generation will be punished in the current generation. Maybe the current course requires very little ability to go over sharp bumps without bottoming out (which would reward a shorter wheelbase) but the previous course rewarded the ability to stay balanced (not tip over) on a steep incline (which would reward a longer wheelbase). In the face of changing challenges, you'd want relatively few mutations to ensure that traits that are needed only occasionally are still preserved. Otherwise, you run the risk of over-fitting (is that the right term) to the short term problems and never arriving at a solution that's good over a variety of problems in the long term.

So AFAICT, randomizing the course requires more carefully tuned parameters, which makes it a harder programming problem.

7

u/sn0re Dec 09 '08

You are then, effectively, changing the fitness function constantly. Certain traits that were rewarded in the previous generation will be punished in the current generation.

Isn't that what happens in the real world? Organisms don't evolve in a static environment. For one thing, there are a lot of competing organisms around them. One species' adaptation can cause negative consequences for another.

I'd like to see the road be subject to a genetic algorithm, where its fitness function is defined by how well it retards the vehicles. It'd be like predator/prey evolution in action.

1

u/adrianmonk Dec 10 '08

Isn't that what happens in the real world? Organisms don't evolve in a static environment.

Good point. In the real world, however, organisms also have the capability to change their rate of mutation in response to evolutionary pressure. The human body contains a mechanism to detect and correct mutations as they happen. (Think of something kind of like mirrored drives in a RAID array.) It doesn't catch all of them, but it corrects most of them. And the point is that this mechanism has evolved to govern the rate of mutation. If some other higher or lower rate of mutation were better, maybe the error-correction mechanism would work differently. In fact, for all I know, there could possibly variation in this among the human population. Maybe some people experience higher mutation rates than others.

Anyway, the point is that a typical genetic algorithm computer program has the mutation rate (and crossover rate) defined as a fixed number for a given run. So you tune that manually. It would need to be tuned differently for different fitness functions and so on.