Genetic Programming

After numerous adventures in ExtremeGeneticProgramming the ultimate question of "why are we here" has been answered. The answer is almost axiomatic and is not the obvious "to be fruity and multiply (or divide)". The obvious notion of procreation being the reason for our existence is a fallacy; it is merely a means to the end.

"The reason for existence is to fill a niche in the universe". -- JonGroff


I was checking out a video tape on GeneticProgramming and was curious how Wiki folks view the technology ... I've had some people say that it "proves evolution works" and others say that you only get what you put in with random variations ... the truth probably lies somewhere in between as usual. -- RaySchneider


(I got one too. A remarkably boring tape.) Note that despite good results in most cases, it still fails from time to time. -- JeffGrigg

Y'all gotta read the book Genetic Programming III. It answers lots of these questions here. They brag they have a GP implementation (proprietary, of course) that can re-create plenty of very old patents in the field of optimized circuit design. -- PhlIp

Genetic Programming III - GeneticProgrammingThree

Didn't get a video tape :-) Seriously, my experiences are extremely varying. From nearly unusable in some cases (where theory of course says GeneticProgramming produces good results), to surprisingly well working solutions where I just used GeneticProgramming as an experiment and for educational purposes only. -- ThomasWeidenfeller


All EvolutionaryAlgorithms need MetaOptimization before they can be expected to work. There's NoFreeLunch with automated design and search - no shrinkwrapped software or downloaded library will work better than random guessing without being tuned to match the problem you're trying to solve. -- BillTozier

True, if "tuning" is your euphemism for "writing the fitness function". -- JohnDouglasPorter

No, brute force search through the space is guaranteed to work eventually in finite domains. The algorithm is meant to probably reduce the time it takes to find a good enough solution. The metaoptimizations are meant to improve the probability. In infinite domains, nothing is guaranteed to work. Evolutionary algorithms once again merely improve your odds. -- SunirShah

GeneticProgramming will still work in infinite domains - you just need an infinite amount of time. And the great advantage of GP is that you can stop it halfway through and still get a decent result. If you were to stop a deterministic algorithm halfway through you'd probably get something that doesn't work at all. In any case you can always use nothing instead, given that its guaranteed to work. :-) -- RichardCordova

Actually, more often than MetaOptimization improves results, it makes them worse. The more MetaOptimization you do, the more probable are the solutions that you were thinking of from the beginning. To make EvolutionaryAlgorithms truly good at adaptation, one should usually make them as random as possible. (But that does require more computational power or more parallelism.) -- PanuKalliokoski

I'm not sure I agree, since in this context I take "MetaOptimization" to mean things like heuristic pruning and bloat avoidance. These things can pay off big in terms of performance, even though you might, as a result, introduce bias against some regions of the solution space. -- JohnDouglasPorter


Note that GeneticProgramming is not the same thing as GeneticAlgorithms, although they share many principles and they are both types of EvolutionaryAlgorithms. See http://www.genetic-programming.org/ or ISBN 0262111705 for details.


I'm not entirely sure how it proves evolution works. Evolution is more of a description of a class of iterated, randomized optimization algorithms. The things that need proving mathematically are what particular mathematical representations are most efficient at achieving end results in particular contexts. But in terms of the RealWorld, the proof is a) did some sort of evolution create the world genome, b) which one(s) in particular. -- SunirShah


GeneticProgramming is my TruePassion?. I've implemented genetic programming, and I would like to point out that genetic programming is entirely domain independent, or at least analogously as C++ is independent of the domain of games programming, for example.

GeneticProgramming has a specific domain-dependent part. Namely, the fitness function. This is also the case with natural evolution where the fitness test is ultimately survival. And in a way, even if you simulate mortality in your system, you still have some conditions that define survivability, and that is what your bred programs will ultimately tend toward.

From what I've seen, GP has solved problems from symbolic regression to binary circuit optimization to programming a simple robot to navigate a domain. In each case, the programming language was exactly the same, the only differences were the test cases. UnitTest anybody? (I don't see what bearing the programming language has here.)

I've long studied the possibility of growing a physical representation from the same genome (program) to basically grow and program virtual robots to fulfil tasks (ultimately to have the MIT ANTS play chess).

I would love to explore this with like-minded people. -- SvenNeumann

I've recently discovered GP. I'm exploring it bit by bit...read through GP I and II, poking around on the web. I'm putting together a small framework for myself, but I'm at a loss when it comes to applications to explore with it. I did the canonical symbolic regression and artificial ant, so I'm looking for something a bit more fulfilling... Interesting-looking, that is. Right now I'm leaning toward some sort of pretty-picture-but-otherwise-meaningless _something_. -- MattMaravillas?
For those interested in exploration, WardCunningham and I have created a concept called ExtremeGeneticProgramming. Fundamentally, it involves using the UnitTestAsFitnessFunction. I believe it is the purest form of TestFirstDesign. Self-directed teams shepherd the evolution of software by PairProgramming unit tests using an integrated version of the FrameworkForIntegratedTest. The GP application, called Neovolve, then uses the tests to converge on a solution.

Results can be found on the FitWiki and at http://www.NeoCoreTechs.com -- JonGroff
Essentially, EvolutionaryAlgorithms turn an evaluation algorithm into a (heuristic) algorithm to produce results that get good values on this evaluation measure. The relation is close to that of deterministic and indeterministic algorithms: for every deterministic test, there is an indeterministic algorithm to find whether there exists a datum to pass the test. The theory EvolutionaryAlgorithms is simply that locally good changes are globally good changes. This is the heuristic EvolutionaryAlgorithms use to avoid searching exhaustively the whole solution domain. As such they are vulnerable to local maxima. -- PanuKalliokoski

So is real life. Here are some alleged "compromises" that evolution has left in humans:


CategoryEvolution

EditText of this page (last edited December 1, 2012) or FindPage with title or text search