News for hackers. Stuff that matters.
Re:Genetic Algorithm Used to Build Car With Box2D by aothman on Friday January 21, 2011 @11:59PM (#2129970)
Cool demo, but from a practical perspective there's absolutely no reason to use GAs to solve a non-linear optimization problem. I know people like them because they have a really pleasing and intuitive backstory, but as a grad student in AI I can tell you that they suck at actually solving anything. Mostly this is due to the fact that GAs take what is already a difficult, non-linear problem (the problem you're trying to solve) and immediately, explosively, complicate it (what's your mutation rate? what are the chromosomes? how are crossovers handled? how are you deciding the answers to these questions?)
Re:Genetic Algorithm Used to Build Car With Box2D by bermanoid on Saturday January 22, 2011 @10:41AM (#2130511)
I think the real problem with most uses of GAs (including this one) is that to the extent that they work at all, they're merely performing a random walk search driven by mutation, and the "crossover" operation is, for all intents and purposes, just functioning as a random-restart of the search, a jump to a new spot in parameter space rather than a useful shuffling of units of functionality.

Sometimes a random local search is exactly what the doctor ordered, of course, it's almost entirely trivial to code and especially if you tune the variance over time you can get pretty good results, though I'd agree that in general you can usually get better results in less computer time with a more typical algorithm (though you've still got to choose the algorithm, implement/integrate it, test it, etc., so you lose a lot of programming time unless it's already part of your framework).

Genetic algorithms should really shine when it's not clear how to cast the problem as a finite dimensional optimization problem, for instance if you're trying to evolve some constructive procedure to solve a problem rather than tweak variables to improve performance. You're absolutely right, aothman, most problems, even most problems specifically constructed to show off GAs, don't fit into this category, so there's no real point except that the algorithm sounds cool...

Re:Genetic Algorithm Used to Build Car With Box2D by Andys on Saturday January 22, 2011 @12:50AM (#2130048)
Solution: Use a GA to evolve the GA parameters. I'd better go and patent this brilliant idea ...
Re:Genetic Algorithm Used to Build Car With Box2D by mzl on Saturday January 22, 2011 @09:00AM (#2130399)
Well, to be fair the parameter problem is common for all kinds of local search and is an interesting research topic. That being said, I agree that GAs are seldom the most efficient, other kinds of local search are typically better.

For problems where there is a natural way to express chromosomes, mutations, and crossover that captures interesting and relevant information GAs can be useful as an additional meta-heuristic.

Re:Genetic Algorithm Used to Build Car With Box2D by Vivtek on Saturday January 22, 2011 @12:13AM (#2129996)
Didn't I read relatively recently about a patent filed on something discovered using a GA? Maybe for lens design?
Re:Genetic Algorithm Used to Build Car With Box2D by stipes on Saturday January 22, 2011 @02:25PM (#2130851)
I believe Koza has several patents for things he has discovered using Genetic Programming / Algorithm techniques.
Re:Genetic Algorithm Used to Build Car With Box2D by reitzensteinm on Friday January 21, 2011 @08:55PM (#2129661)
I recently built a game with similar mechanics (http://www.bigblockgames.com/games/goblin/), and this is basically what my first day of development looked like, just sped up between takes.

Except at least this doesn't create many cars unstable enough that the structure starts oscillating before shooting off to infinity. So I guess GA 1, Michael 0.

Re:Genetic Algorithm Used to Build Car With Box2D by Vivtek on Saturday January 22, 2011 @12:45AM (#2130041)
I don't normally get into video games, but dear Lord I like that one.
Re:Genetic Algorithm Used to Build Car With Box2D by reitzensteinm on Saturday January 22, 2011 @02:56AM (#2130158)
Cheers dude :)

Our philosophy is basically to make flash games that don't suck! Goblin seems to have gotten quite a bit of attention over the past 72 hours or so.

Re:Genetic Algorithm Used to Build Car With Box2D by aerique on Saturday January 22, 2011 @07:11AM (#2130330)
Sorry for the perhaps silly question, but do you make money off it and if so: how?

I'm asking because I've been on an iPhone since this was posted and won't have access to a real machine until tomorrow so I cannot check the game out.

Re:Genetic Algorithm Used to Build Car With Box2D by reitzensteinm on Saturday January 22, 2011 @09:25AM (#2130425)
Currently, it just attracts people to the site (which it's done in a pretty extreme way). We'll probably follow it up with a level pack that's for sale, though.

In other words, we lose a little on each hit, and make up for it with volume!

Re:Genetic Algorithm Used to Build Car With Box2D by aerique on Saturday January 22, 2011 @11:18AM (#2130552)
Thanks for the answer!
Re:Genetic Algorithm Used to Build Car With Box2D by steverb on Friday January 21, 2011 @09:05PM (#2129689)
Found that game earlier this week due to BoingBoing. Nice job.
Re:Genetic Algorithm Used to Build Car With Box2D by reitzensteinm on Friday January 21, 2011 @09:10PM (#2129700)
Thanks :)
Re:Genetic Algorithm Used to Build Car With Box2D by solipsist on Friday January 21, 2011 @08:48PM (#2129651)
I've let it run for 10 generations in the background, and keep coming back to be entertained. It's fun to see the cars tackle the course. I've already gotten attached to a few of them - I cheer them on when they make it over a hill and cry with despair when they don't. =)

Here is one car that I got in generation 10: http://i.imgur.com/J0kdV.png

It didn't do too well, but it reminded me of a [update] penny-farthing. This should be familiar to people living in Palo Alto: http://www.paloaltoonline.com/news/show_story.php?id=11781%3...

Re:Genetic Algorithm Used to Build Car With Box2D by templaedhel on Saturday January 22, 2011 @09:45AM (#2130450)
I let it run overnight, getting up to 60 generations. I cannot tell if the cars are actually improving that much, but the graph says they are. I saw one get to 245, but I missed that screenshot. Unfortunately a lot of the good cars spawn with their wheels upside down, or rotated, I wonder if spawn orientation is evolving along with the car. It would appear not. Here is the best car of the 62 gen.

http://i.imgur.com/H1Rrw.png

Re:Genetic Algorithm Used to Build Car With Box2D by solipsist on Saturday January 22, 2011 @12:29PM (#2130671)
I did that too and got it up to the 114th generation. Unfortunately, the car has gotten stuck and the game seems to be going nowhere. So I'll never see the 115th generation...

http://i.imgur.com/bAnmY.png

Re:Genetic Algorithm Used to Build Car With Box2D by joshu on Friday January 21, 2011 @08:54PM (#2129658)
(the bike is a penny-farthing. http://en.wikipedia.org/wiki/Penny-farthing )
Re:Genetic Algorithm Used to Build Car With Box2D by solipsist on Friday January 21, 2011 @08:58PM (#2129669)
Thanks for pointing that out. To be technical, though, it is a reverse penny-farthing.
Re:Genetic Algorithm Used to Build Car With Box2D by reitzensteinm on Friday January 21, 2011 @09:01PM (#2129677)
I don't think it is? It's driving to the right, which is towards big wheel, unless the picture has been flipped.
Re:Genetic Algorithm Used to Build Car With Box2D by solipsist on Friday January 21, 2011 @09:05PM (#2129690)
Sorry, let me clarify. The cyclist in Palo Alto rides a reverse penny-farthing, while the vehicle generated by the genetic algorithm is the traditional penny-farthing.
Re:Genetic Algorithm Used to Build Car With Box2D by solipsist on Saturday January 22, 2011 @12:52AM (#2130050)
1st generation

  #0  : 6
  #1  : 1.7
  #2  : 0.5
  #3  : 0.4
  #4  : 0.9
  #5  : 0
  #6  : 2.6
  #7  : 0
  #8  : 0
  #9  : 0
  #10 : 0.4
  #11 : 6.1
  #12 : 0.2
  #13 : 0.7
  #14 : 1.7
  #15 : 0
  #16 : 0
  #17 : 1.4
  #18 : 0
  #19 : 1.3

  Average : 1.2

  One of the cars from generation 43: http://i.imgur.com/95QvW.png
43rd generation (after hours of waiting!)

  #0  : 146.3
  #1  : 211.6
  #2  : 237
  #3  : 235.8
  #4  : 0
  #5  : 128.4
  #6  : 0
  #7  : 0
  #8  : 204.4
  #9  : 137.7
  #10 : 85.9
  #11 : 208
  #12 : 211.1
  #13 : 36.3
  #14 : 0
  #15 : 202.8
  #16 : 247
  #17 : 239
  #18 : 230.2
  #19 : 139.5

  Average : 145.1

  One of the cars from generation 43: http://i.imgur.com/WZtZq.png
Now that's what I call evolution!
Re:Genetic Algorithm Used to Build Car With Box2D by RevRal on Friday January 21, 2011 @09:41PM (#2129749)
Re:Genetic Algorithm Used to Build Car With Box2D by Vivtek on Saturday January 22, 2011 @12:12AM (#2129993)
I've seen that before - there doesn't seem to be anywhere that you can see his code, especially his selection function. I'd find that pretty interesting.
Re:Genetic Algorithm Used to Build Car With Box2D by sorbus on Friday January 21, 2011 @07:18PM (#2129487)
Link to the Reddit discussion: http://news.ycombinator.com/item?id=2127367
Re:Genetic Algorithm Used to Build Car With Box2D by mambodog on Friday January 21, 2011 @10:01PM (#2129779)
I previously submitted this similar (old) demo: http://www.qubit.devisland.net/ga/
Re:Genetic Algorithm Used to Build Car With Box2D by huherto on Friday January 21, 2011 @10:04PM (#2129781)
This was very nice. I remember this, we spend a lot of time just watching it.
Re:Genetic Algorithm Used to Build Car With Box2D by keyle on Friday January 21, 2011 @08:21PM (#2129604)
That's so funny I spilled my coffee.