News for hackers. Stuff that matters.
Re:Genetic Algorithm building a little car by tvchurch on Monday December 08, 2008 @02:04PM (#390177)
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.

Re:Genetic Algorithm building a little car by andr on Monday December 08, 2008 @01:14PM (#390112)
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.
Re:Genetic Algorithm building a little car by icefox on Monday December 08, 2008 @01:38PM (#390144)
This one has docs and links to wikipedia, while being in javascript to boot

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

Re:Genetic Algorithm building a little car by kirse on Monday December 08, 2008 @04:03PM (#390372)
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.

Re:Genetic Algorithm building a little car by malkia on Monday December 08, 2008 @04:11PM (#390386)
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.

Re:Genetic Algorithm building a little car by kirse on Monday December 08, 2008 @04:26PM (#390404)
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.

Re:Genetic Algorithm building a little car by nsrivast on Monday December 08, 2008 @04:35PM (#390412)
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.

Re:Genetic Algorithm building a little car by wheels on Tuesday December 09, 2008 @04:06AM (#391125)
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.
Re:Genetic Algorithm building a little car by kirse on Monday December 08, 2008 @04:39PM (#390418)
+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". =)

Re:Genetic Algorithm building a little car by demallien on Tuesday December 09, 2008 @04:57AM (#391145)
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'.

Re:Genetic Algorithm building a little car by demallien on Tuesday December 09, 2008 @04:52AM (#391143)
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.
Re:Genetic Algorithm building a little car by kirse on Tuesday December 09, 2008 @12:50PM (#391496)
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.

Re:Genetic Algorithm building a little car by demallien on Wednesday December 10, 2008 @05:12AM (#392725)
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).
Re:Genetic Algorithm building a little car by DavidSJ on Monday December 08, 2008 @09:00PM (#390786)
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.

Re:Genetic Algorithm building a little car by RK on Tuesday December 09, 2008 @01:37PM (#391555)
Evolution simply means change over time.

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

Re:Genetic Algorithm building a little car by DavidSJ on Tuesday December 09, 2008 @01:59PM (#391587)
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.

Re:Genetic Algorithm building a little car by anthonyb on Monday December 08, 2008 @07:08PM (#390636)
Do you think evolution really cares whether constraints are artificial or not?
Re:Genetic Algorithm building a little car by kirse on Monday December 08, 2008 @08:35PM (#390751)
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.

Re:Genetic Algorithm building a little car by anthonyb on Monday December 08, 2008 @10:55PM (#390921)
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.

Re:Genetic Algorithm building a little car by iamwil on Monday December 08, 2008 @03:51PM (#390364)
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?

Re:Genetic Algorithm building a little car by demallien on Tuesday December 09, 2008 @04:42AM (#391141)
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...
Re:Genetic Algorithm building a little car by andr on Monday December 08, 2008 @04:13PM (#390391)
Yeah, I'm curious about the details, such as the mutation function and the phenotype. Otherwise it's a pretty straightforward GA.
Re:Genetic Algorithm building a little car by aak on Monday December 08, 2008 @09:39PM (#390837)
I left my browser open and had it running for 12 hours now, and now my car looks like a porsche.
Re:Genetic Algorithm building a little car by nihilocrat on Monday December 08, 2008 @01:33PM (#390138)
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.
Re:Genetic Algorithm building a little car by dangoldin on Monday December 08, 2008 @05:04PM (#390460)
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.

Re:Genetic Algorithm building a little car by slater on Monday December 08, 2008 @01:27PM (#390129)
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.
Re:Genetic Algorithm building a little car by ivankirigin on Monday December 08, 2008 @02:10PM (#390192)
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.

Re:Genetic Algorithm building a little car by ivankirigin on Monday December 08, 2008 @02:11PM (#390196)
note to pg, these are valid URL characters: "()"

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

Re:Genetic Algorithm building a little car by lacker on Monday December 08, 2008 @02:53PM (#390275)
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.

Re:Genetic Algorithm building a little car by ivankirigin on Monday December 08, 2008 @02:56PM (#390297)
Indeed. Though I'm accustomed to adding a space at the end of urls.
Re:Genetic Algorithm building a little car by bd on Monday December 08, 2008 @06:26PM (#390580)
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

Re:Genetic Algorithm building a little car by ivankirigin on Monday December 08, 2008 @08:08PM (#390723)
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.

Re:Genetic Algorithm building a little car by bd on Monday December 08, 2008 @08:40PM (#390754)
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).

Re:Genetic Algorithm building a little car by msg on Monday December 08, 2008 @06:42PM (#390607)
http://news.ycombinator.com/item?id=10889

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

Re:Genetic Algorithm building a little car by swombat on Monday December 08, 2008 @05:26PM (#390492)
might wanna send him an email, to pg@...
Re:Genetic Algorithm building a little car by tc7 on Monday December 08, 2008 @12:59PM (#390089)
Cool-looking, but I'm not quite sure what's going on. Explanations?
Re:Genetic Algorithm building a little car by jonknee on Monday December 08, 2008 @01:01PM (#390093)
"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...

Re:Genetic Algorithm building a little car by cnu on Thursday December 11, 2008 @03:52AM (#394138)
What does the graph depict? What is the black and green lines mean?
Re:Genetic Algorithm building a little car by dangoldin on Monday December 08, 2008 @01:03PM (#390098)
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.

Re:Genetic Algorithm building a little car by vorador on Monday December 08, 2008 @01:59PM (#390168)
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) ?
Re:Genetic Algorithm building a little car by jwilliams on Monday December 08, 2008 @09:19PM (#390816)
I'd like to try and compete with an intelligent design - see how many generations it takes for the GA to beat me.
Re:Genetic Algorithm building a little car by andr on Monday December 08, 2008 @02:15PM (#390206)
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.

Re:Genetic Algorithm building a little car by bayleo on Monday December 08, 2008 @02:09PM (#390188)
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.
Re:Genetic Algorithm building a little car by friism on Monday December 08, 2008 @04:00PM (#390370)
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...
Re:Genetic Algorithm building a little car by erik on Monday December 08, 2008 @06:30PM (#390587)
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.
Re:Genetic Algorithm building a little car by andyking on Monday December 08, 2008 @05:30PM (#390500)
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.
Re:Genetic Algorithm building a little car by dskhatri on Monday December 08, 2008 @01:48PM (#390156)
Really cool and reminds me of self-modeling robots: http://ccsl.mae.cornell.edu/research/selfmodels/
Re:Genetic Algorithm building a little car by jedc on Monday December 08, 2008 @02:51PM (#390271)
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.

Re:Genetic Algorithm building a little car by yters on Tuesday December 09, 2008 @06:33AM (#391190)
Lots of the parameters could be adjusted using some kind of gradient descent. Have you looked at using differential evolution?
Re:Genetic Algorithm building a little car by bprater on Monday December 08, 2008 @01:32PM (#390136)
I'm assuming 'GA' mean Genetic Algorithm.
Re:Genetic Algorithm building a little car by timtrueman on Monday December 08, 2008 @09:06PM (#390790)
Anyone else ever seen one get past the first major drop?
Re:Genetic Algorithm building a little car by jdrock on Monday December 08, 2008 @02:17PM (#390208)
Really nice visualization of GAs
Re:Genetic Algorithm building a little car by nazgulnarsil on Wednesday December 10, 2008 @01:39AM (#392576)
it appears that evolutionary dead ends are possible, which is cool
Re:Genetic Algorithm building a little car by socratees on Monday December 08, 2008 @04:37PM (#390416)
looks nice, but seriously, what's happenin behind??