Genetic Algorithm building a little car | Hacker News Reader

Genetic Algorithm building a little car

wreck.devisland.net

126 pointssanj54 comments

Open articleView on HN

Had a 12-person seminar with the founder of Genetic Algorithms, John Holland. Read about him here:

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-Complex...

Professor Holland is sharp as hell, insistent about expanding interdisciplinary studies, and a very nice guy.

Ok 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.

This one has docs and links to wikipedia, while being in javascript to boot

http://news.ycombinator.com/item?id=100521

What 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?

Yeah, I'm curious about the details, such as the mutation function and the phenotype. Otherwise it's a pretty straightforward GA.

And 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...

How 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.

You can think of the programmer as the physics laws in the universe.

This law, being a law, just dictates rules of what is possible, but the outcome is what happen in the mean-time.

Some people do think that God is the Physics Law. Some do think that God is the Time, where this happened.

If the programmer specifies the boundaries (laws) of his own universe, then the evolutionary processes that happen within his own universe are not representative of the actual universe which he claims to be modeling. Why?

1) Current scientific claims express that the laws and boundaries of the universe came into existence without a designer. Having a designer anywhere in the equation is unacceptable, even one who simply created the universe, because that invalidates (or at least casts heavy doubt) on the naturalistic claims of any designer-free subprocesses that happen within the universe (specifically, Evolution).

2) Evolution itself is devoid of a designer and end goal.

Logically, it is impossible to model a process that is inherently devoid of any design or purpose.

It would only be scientific to question the accuracy of any model that can't even replicate the basic core constraints (eg. lack of a designer) of the system which it is trying to represent.

The point of genetic algorithms is NOT to replicate evolution. Like you mention, evolution has no end goal whereas engineers usually have very explicit end goals. (Other problems include time constraints and computing power!)

The point of genetic algorithms is to exploit the principle of natural selection under very specific constraints and explicitly constructed utility functions that are likely to lead to a better solution to a given problem.

Of course we're cheating a little, but we have to. "Organic" genetic algorithms that consistently achieve engineering design principles (like robustness, modularity, compartmentation, etc.) without constraints are the holy grail of the field.

+1 Thanks for the explanation. I can fully understand both the legitimacy and the desire to model the specific process of genetic propagation, but was somewhat confused how exactly that logically validates it as an accurate representation of its function in evolution as a whole.

It's pretty clear one model has a designer and the other does not, and you certainly agree that the existence of a designer is more than just a small issue when dealing with the validity of evolutionary "models". =)

If you mean that there is a 'designer' of the system, then sure, there is. But if you mean that there is a 'designer' of the little model cars, then no, you are absolutely wrong (except in the sense that the GA itself, a mindless mathematical process, is a designer).

In other words, this is a pretty faithful model of evolution if we postulate that once the first self-replicating organism came into being (once the programmer had written the model/fitness function), no further interference is necessary - a purely mathematical process will lead to artifacts that appear 'designed'.

To be clear, the field of genetic algorithms is split into two groups: one primarily concerned with function optimization for engineering application, the other at providing a laboratory for understanding evolutionary processes.

I beg to differ - evolution, in the 'life on Earth' sense has a very very specific goal - to reproduce genes as successfully as possible. To date, we know no life that does not seek this primal goal.

You clearly misunderstand your own theory, because this specific paper written by an evolutionist (on TalkOrigins, the shrine of evidence for Evolution) reinforces the view on why biological evolution has no goal: http://www.talkorigins.org/faqs/evolphil/teleology.html

When Dawkins talks about genes maximising their representation in the gene pool, this is a metaphor not an explanation. Genes just replicate. It happens that those that out-replicate others end up out-surviving them. There is no 'goal' to genetic behaviour.

Evolutionists are always screaming about the evidence, and it's rarely been debated that biological evolution is completely devoid of a designer, purpose, intelligence, or end goal anywhere in the process. That's one of the basic truths you get out of the naturalistic assumptions that base biological Evolution.

1) It's not my theory 2) Whilst it is true that individual genes do not have goals, it is not true that natural evolution, as a search algorithm, does not. When we talk about goals for GAs (which is of course the context of this very discussion we are having), we are specifically talking about high values of the fitness function of the GA. In the case of natural evolution, the 'goal' is to reproduce a gene as much as possible. Note, this is a goal of the GA, not of the gene, and the usage of the word here does not indicate an actually entity with a motivation, but simply reuses terminology that is quite common in discussion of search algorithms (evolution being but one example of these).

Do you think evolution really cares whether constraints are artificial or not?

I knew someone was going to post this and should have addressed it..

Programming an evolutionary model is not setting artificial environmental constraints and then letting an unbounded process operate at will (as your comment implies). You would agree that the very act of coding a process puts constraints upon it. Programming any evolutionary model puts artificial constraints on both the environment and the evolutionary process itself.

Regardless, as "nsrivast" cleared up above, they are not striving to model Evolution (nor should they be claiming a process that has no constraints, intelligence or purpose is modeled accurately via constraints, a designer, and an end goal). As nsrivast noted, some of the most common constraints are time and computing power.

I think the quote that you're looking for is: "All models are wrong; some are useful".

That said, selection pressure is selection pressure, regardless of whether the means are artificial (being culled from a list in RAM) or natural (being eaten by a lion). I don't see that evolution in a computer process, even with artificial constraints, is that much different to evolution in the "real world".

I'm also not 100% sure exactly what your definition of an artificial constraint is, but something like Tierra might be more what you're looking for.

Your definition of evolution is incorrect. Evolution is a process which occurs in any system that has:

* replication

* selection pressure

* variation

No claims about that system's progeny are made by evolution.

Evolution simply means change over time.

Your description is more akin to natural selection as a mechanism for evolution.

Words have multiple definitions. Yes, "evolution" simply meant change over time, prior to Darwin's publication of the Theory of Evolution. In the context of this conversation, "evolution" refers to the process Darwin was describing, but in reference to digital individuals rather than biological organisms.

Certainly, the word "evolution" in none of its permutations describes how the process started.

I left my browser open and had it running for 12 hours now, and now my car looks like a porsche.

Genetic 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.

An 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.

i 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.

One 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/Daimler_AG 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.

note to pg, these are valid URL characters: "()"

I'm surprised you of all people aren't more partial to them

The problem is breaking stuff like

(also see url: 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.

Indeed. Though I'm accustomed to adding a space at the end of urls.

might wanna send him an email, to pg@...

It'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

The href can be that ugly link while the parens are still visible. The issue is when to parse the parens as part of the link.

Edit: but I guess you're saying I could do this to make it clickable. No thanks.

Yup, that's what I ment. This is what I do when posting Wikipedia urls with parens here.

For parsing parens problem, heuristics proposed by lacker seems reasonable.

Anyway, I guess like 99% of broken parens cases here would be Wikipedia links, which are quite well defined (except for pages for emoticons and parens symbols themselves).

http://news.ycombinator.com/item?id=10889

When is a paren not a paren? When it's punctuation.

Cool-looking, but I'm not quite sure what's going on. Explanations?

"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_p...

What does the graph depict? What is the black and green lines mean?

From 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.

I 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) ?

Due to the naïveté of the model I would say it's pretty unlikely that there are many different car-combinations with high fitness.

Has 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...

I 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.

In 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.

Open 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.

I'd like to try and compete with an intelligent design - see how many generations it takes for the GA to beat me.

Really cool and reminds me of self-modeling robots: http://ccsl.mae.cornell.edu/research/selfmodels/

Very 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.

Lots of the parameters could be adjusted using some kind of gradient descent. Have you looked at using differential evolution?

I'm assuming 'GA' mean Genetic Algorithm.

Anyone else ever seen one get past the first major drop?

Really nice visualization of GAs

it appears that evolutionary dead ends are possible, which is cool

looks nice, but seriously, what's happenin behind??

Reply on news.ycombinator.com