6 ms·
Genetic Algorithm building a little car
- jdrock 18y agoReally nice visualization of GAs
- tc7 18y agoCool-looking, but I'm not quite sure what's going on. Explanations?
- jonknee 18y ago"This is a GA I wrote to design a little car for a specific terrain. It runs in real-time in Flash. The fitness function is the distance travelled before the red circles hit the ground, or time runs out. The degrees of freedom are the size and inital positions of the four circles, and length, spring constant and damping of the eight springs. The graph shows the "mean" and "best" fitness. I should really make a new version with better explanations of what's going on." http://www.reddit.com/r/programming/comments/7i22c/genetic_programming_evolution_of_mona_lisa/c06pt65 http://www.reddit.com/r/programming/comments/7i22c/genetic_p...
- cnu 18y agoWhat does the graph depict? What is the black and green lines mean?
- dangoldin 18y agoFrom what I can tell and my limited genetic programming experience the idea is to create a car that is able to drive across the course. A car is defined as being a quadrilateral with two wheels and two counterweights (I think that's what they are). It starts off by randomly creating 20 cars with variable car shapes, wheel sizes, and counterweight sizes. It determines how well each car does on the course and uses this information to mate the cars together in order to get a more successful car. The way this is traditionally done is by evaluating a "fitness" function on each individual in the population and giving the higher scoring individuals a better chance of mating. This process keeps on going on until some criteria is reached. On average, the higher the generation count the better the offspring should be.
- andr 18y agoOk this is the second evolutionary computing post of today that does something cool with little or no explanation of what's going on. Stop teasing.
- icefox 18y agoThis one has docs and links to wikipedia, while being in javascript to boot http://news.ycombinator.com/item?id=100521 http://news.ycombinator.com/item?id=100521
- iamwil 18y agoWhat do you mean? I see the GA being tested against the fitness function one at a time with the individuals in the population, with subsequent populations being the mutated and crossover'd versions of the previous generation. Are you asking about the details of how each individual is represented? How the individuals are crossed over? What the rate of extinction is?
- andr 18y agoYeah, I'm curious about the details, such as the mutation function and the phenotype. Otherwise it's a pretty straightforward GA.
- demallien 18y agoAnd I for one would love to know what the fitness function is, and what the physics being used is. And then, why not, what were the parametres that the ga was acting on...
- kirse 18y agoHow exactly is it evolutionary computing when there is a designer in the equation (programmer) who puts constraints on the algorithm by the simple act of coding it and running it on systems that he designed? This seems more like "computing to model the process of genetic adaptation". You can't label it evolutionary when there's a designer in the equation. The very definition of the evolutionary process does not allow for constraints on the process itself nor an end goal/purpose, something inherent to any system built by a programmer.
- slater 18y agoi misread the title and thought that at least one of the "Big Three" had finally gotten it, and was starting to make SMART-size cars. Dang.
- ivankirigin 18y agoOne of the big 3 did build the smart car. Sorta. If you count Daimler AG ( previous owner of Chrysler, and current owner of Smart) as the maker. http://en.wikipedia.org/wiki/Chrysler_Group http://en.wikipedia.org/wiki/Chrysler_Group http://en.wikipedia.org/wiki/Daimler_AG http://en.wikipedia.org/wiki/Daimler_AG http://en.wikipedia.org/wiki/Smart_(automobile) http://en.wikipedia.org/wiki/Smart_(automobile) I'll take this opportunity to note that bailing out companies originally founded by Americans in such a globalized market is arbitrary and harmful.
- ivankirigin 18y agonote to pg, these are valid URL characters: "()" I'm surprised you of all people aren't more partial to them
- lacker 18y agoThe problem is breaking stuff like (also see url: http://google.com http://google.com) Might be better to treat a trailing ) as not part of a url only if there is no ( earlier in the url.
- ivankirigin 18y agoIndeed. Though I'm accustomed to adding a space at the end of urls.
- swombat 18y agomight wanna send him an email, to pg@...
- bd 18y agoIt's possible to get around using escape sequences. In Python: import urllib print urllib.quote("en.wikipedia.org/wiki/Smart_(automobile)") It looks ugly, but it makes links clickable: http://en.wikipedia.org/wiki/Smart_%28automobile%29 http://en.wikipedia.org/wiki/Smart_%28automobile%29
- bprater 18y agoI'm assuming 'GA' mean Genetic Algorithm.
- nihilocrat 18y agoGenetic algorithms are pretty fun to talk about, but actually seeing it in action is awesome. Here, you can clearly see when a new car is born and when it fails, and see that the designs that manage to live longer are going to be more successful.
- dskhatri 18y agoReally cool and reminds me of self-modeling robots: http://ccsl.mae.cornell.edu/research/selfmodels/ http://ccsl.mae.cornell.edu/research/selfmodels/
- vorador 18y agoI wonder if the car that best fits the constraints is always the same (i.e : do we see the same car, or each user sees a different car) ?
- andr 18y agoOpen another instance in a second window and you'll quickly see the answer. Only one car would best fit the constraints (that's by definition). However, it's probably not the car you are seeing, because the algorithm tends to get stuck on local maxima. After about 2 hours of running, the thing has flatlined as each window I opened has 20 copies of pretty much the same car (although they differ between windows), and they are not getting that far.
- bayleo 18y agoDue to the naïveté of the model I would say it's pretty unlikely that there are many different car-combinations with high fitness.
- friism 18y agoHas anyone bred one than gets past the dip after hill and doesn't somersault? The ones I have now seem to have optimum suspension for quickly motoring over the initial bumbs, but they all die in that damn ditch...
- andyking 18y agoI think that ditch just coincides with a time limit of about ten seconds on most cars. I wonder how far they'd get if they weren't time-limited.
- erik 18y agoIn the second tab I opened there is a car that makes it past the point that causes most cars to flip. The run currently times out at the top of the next hill, but the distance is still slowly improving.
- jwilliams 18y ago
- tvchurch 18y agoHad a 12-person seminar with the founder of Genetic Algorithms, John Holland. Read about him here: http://en.wikipedia.org/wiki/John_Henry_Holland http://en.wikipedia.org/wiki/John_Henry_Holland In my opinion, this is his most accessible book (for the topic that is) about GA's: http://www.amazon.com/Hidden-Order-Adaptation-Builds-Complexity/dp/0201442302/ref=sr_1_3?ie=UTF8&s=books&qid=1228762794&sr=8-3 http://www.amazon.com/Hidden-Order-Adaptation-Builds-Complex... Professor Holland is sharp as hell, insistent about expanding interdisciplinary studies, and a very nice guy.
- jedc 18y agoVery cool. Back in college our final assignment was a GA to find the best trajectory for a hypothetical space mission. (You had to go by particular planets in particular windows in time.) It was great fun playing around with it.
- deleted 18y ago[deleted]
- socratees 18y agolooks nice, but seriously, what's happenin behind??
- dangoldin 18y agoAn interesting thought I had from this was the difference between Genetic Algorithms and Genetic Programming. Genetic Algorithm is what we are seeing but Genetic Programming would tell us that the car might need 3 wheels.
- timtrueman 18y agoAnyone else ever seen one get past the first major drop?
- aak 18y agoI left my browser open and had it running for 12 hours now, and now my car looks like a porsche.
- yters 18y agoLots of the parameters could be adjusted using some kind of gradient descent. Have you looked at using differential evolution?
- nazgulnarsil 18y agoit appears that evolutionary dead ends are possible, which is cool