Genetic algorithm demo: finding optimal vehicle design (in Flash)

http://www.qubit.devisland.net/ga/

by mambodog • 16 years ago

65 16 16 years ago

qubit.devisland.net

cubicle67• 16 years ago

I'm sure I've run this as Java code years ago, along with another demo that evolved a car capable of navigating around a course

Edit: I remember now - I was trying to learn neural networks and the code demonstrated using GA to evolve a neural network. Can't find a link, unfortunately, which is a shame as it's an interesting subject

mambodog• 16 years ago

I just had a look at the source and it's written in pure AS2 which makes me think that it's probably kind of old. Either that or the person who wrote it never made the switch to AS3.

I just thought it was interesting because I haven't personally seen many realtime demos of genetic algorithms, especially ones that run in the browser, though I don't doubt that they've been kicking around for years.

AdamTReineke2• 16 years ago

I know I've seen this Flash version a few years back.

bennysaurus2• 16 years ago

Source code puts parts of it to Jan 2007, but looks like this particular version is Dec 2008. Nice bit of code for 16K

dansingerman• 16 years ago

This is very cool.

Idea: a game where each level you get a terrain and must design the optimal vehicle to traverse it (or does this exist?)

AdamTReineke2• 16 years ago

Like a cross between JellyCar and Crayon Physics?

zith• 16 years ago

Fantastic contraption is a bit like that. It's also incredibly addictive.

http://fantasticcontraption.com/

jules• 16 years ago

It looks like a random search to me.

_delirium• 16 years ago

In a lot of cases, "GA" just seems to be a fancy name for randomized search. Even when it does use elements from the evolutionary metaphor (crossover operators, etc.), you can often get equivalent results with a non-GA randomized-optimization method.

The interesting part here IMO is how to pose the problem as an optimization problem, and what representation they used for the candidate solutions. The details of how you optimize once you have those two things aren't as exciting, and on a lot of problems don't matter that much, so it's a bit of a shame that they always get emphasized (admittedly, the "genetic" and "evolutionary" metaphors make for nice PR, whereas a lot of randomized-optimization algorithms are really boring sounding).

ahilss• 16 years ago

I believe they are using a non-standard crossover operator in this implementation. A standard crossover operator will generate some permutation of the genes of the two parents: either you inherit the gene from your mother or your father. This implementation creates a new gene that is a weighted average of the genes of the two parents. This will probably cause rapid convergence of the gene pool, which may or may not be intended. Changing Math.random() to Math.round(Math.random()) in crossVars would change this to the standard crossover operator. I'd be interested to see how this affects performance.

mrcharles• 16 years ago

Can someone please explain what the graph is? I can't quite figure it out. I'm assuming that the green is total distance traveled... but I can't figure out what the black one means.

a-priori• 16 years ago

If I'm reading it right, the black line is the best fitness in a given generation, and the green line is the average fitness.

gentrysherrill• 16 years ago

I think the green line is average fitness of all iterations and the black line is a logarithmic index of each generation's maximum fitness to the optimal achieved (both relative to time). So the black line pretty quickly gets bounded by an asymptote at the top of the screen, because the improvements in fitness are far more significant early on. Basically an example of diminishing returns...

There is a great discussion of this (and a further mapping of fitness functions and evolutionary algorithms to a 2-dimensional "fitness landscape") in The Origin of Wealth by Eric Beinhocker - http://www.amazon.com/Origin-Wealth-Evolution-Complexity-Eco...

Absolutely phenomenal exploration of complexity economics.

RiderOfGiraffes• 16 years ago

I think ...

For each iteration there are 20 individuals. Each gets a score according to how far they get. The horizontal line is the generation. The black line shows the best in each generation, and green line shows the average over the 20 individuals in that generation.

The black line is always above the green, but sometimes crashes way down. The green line doesn't change dramatically, and generally climbs.

cellularmitosis• 16 years ago

mine appears to have found a local maxima which produces unicycles :)

http://www.youtube.com/watch?v=L39u6dMSkLA

Genetic algorithm demo: finding optimal vehicle design (in Flash)

Related Stories