Thats why I have always loved genetic algorithms.

They are creating some patent worthy inventions using them now. Check John Koza's work.

http://www.popsci.com/popsci/science/0e13af26862ba010vgnvcm1...

Genetic algorithms are fun but let's not overhype them. They solve optimization problems by following an iteration procedure. And we all know that iteration commonly produces a _local_ maximum.

True, but there are a host of techniques to skip local maximums, for example running several totally separate populations (families) for a certain number of generations and then creating a new population (family) based only on combinations from two other families.

And a lot of times even the first local maximums are impressive.

To see how powerful these things can be just compare using brute force random solutions to genetic algorithms you get results that are better by quite a few orders of magnitude.

Or in short don't knock it till you've tried it. It isn't a universal solution for every problem and it can take quite a lot of work to correctly tweak with the fitness score and with all the variables but it is a very useful tool and can produce some very cool results.

Are you sure you're not getting GAs mixed up with gradient descent? The whole point of a GA is that they're a global search. Mutation and crossover (with certain conditions) generally mean you don't get stuck in local maxima.

Of course, there are conditions on that. The quality of your RNG, the probabilities of mutation/crossover, etc..

Marcus replied to that http://news.ycombinator.com/item?id=90115.

Exactly. He's describing gradient descent (and possibly simulated annealing), not a genetic algorithm.

Mutation, especially burst mutation with population stagnation, is what stops you getting stuck in local maxima.

It does not matter _how_ it is done, it is still an iteration. You may have several iterations going on but at best you can expect to find several local maxima - at any given time. Further, if there is no "stagnation", how do you know that you've found a solution?

Stagnation is the case where the best individuals in the populations fitness hasn't increased by some value for a certain period of time.

I'm not sure I understand what you mean by 'a solution'? You know you've not arrived at an acceptable solution when your fitness is below your required level.

Granted, you never know there is a configuration with a fitness greater than your required fitness but this is generally considered when constructing the fitness function.

I understand that when a certain level of fitness is reached the procedure stops. But, it may stop too early - missing the global max. And second, it may never stop!

True.

I've seen some interesting work on the latter case that produces upper and lower bounds for time to an acceptable solution but so far it seems to be limited in it's application to real world tasks.

Missing the global max less of an issue, an acceptable level of fitness is generally all that's required for most applications. Though I guess there are several tasks for which a global max would be useful.

Pix,

What is the liscence policy on the pixcavator SDK? If I wanted to incorporate some of your binaries into a product, what would be the cost?

It is free currently. Get in touch though. And thanks for a new name, I like it!

The local maximum problem has something to do with iteration?

Yes, iteration in this sense is basically traversing along a plane mostly in the direction of biggest gain. So you'll mostly traverse to local maximum, once you get to a local maximum, there is no evolutionary advantage to doing a step in any direction as they all lead to reduced performance which can cause you to miss a bigger maximum just around the corner.

That is why all iterative algorithms suffer from local maximum problems.

Don't they use large populations of possible solutions for this very problem?

Very, very interesting link... thank you!

It's not a good comparison. In the very, very long-term, the "fit" inventions do tend to win out, but that says nothing about the processes by which they were built. That is, unless you get really loose with the definition. If I'm designing a bridge, and I come up with 10 blueprints, and select the best one...that's not really an evolutionary process, and neither would it be if 10 different engineers came up with a blueprint. If we build 10 bridges and wait for nine to collapse, well, that would be an evolutionary engineering process. (Again, over centuries and centuries, that very thing occurs.)

A better analogy would be comparing the marketplace with a harsh environment. There, Linux survives for a mundane reason--just like mammals needed less heat from the atmosphere, linux needs less money from its customers. So, it may win out in the end.

Its not a comparison at all.

Linus replied to someone who said Linux coding style is not improving because no one sets the rules. Linus said that it is improving via evolution. Style liked by many will be taken over by others, style liked by few will fade out.

Not a comparison. Just a fact.

Orgel's Second Rule: "Evolution is cleverer than you are."

But that's just because humans are pretty stupid in the grand scheme of things.

Cue Matrix

Yeah, but making a new "most complex piece of engineering" is fire-and-forget (at least if you move out of state and change your name).

 >apt-get install human-2.0
  Building dependency tree
  Reading state information... Done

  After delivery $2.5 million will be used.
  Do you want to continue [Y/n]? n
  Abort.