In a system like this though, you always have to start with some primitives. It's really matter of where you can get from the primitives and whether there is a steadily uphill (in terms of fitness) path for getting there.
In answer to whether I've heard of any successful sorts, the answer is no. Genetic programming (PG) was originally intended to evolve computer programs. It has failed miserably. It only evolves programs of the simplest sort, generally without loops. GP has been quite successful in generating very sophisticated designs, though. John Koza calls these human competitive. These are designs that would be publishable on their own merits (or patentable, etc.) even if produced directly by a human. I'm at GECCO this week, writing from Portland. One paper is about using Cartesian Genetic Programming that evolves programs to compute pi and e. That's quite impressive! What is evolved is a program that modifies itself as it runs. The more time it's run, the closer the approximation. It essentially embeds a inline subprogram into itself on each iteration. So in this case the evolutionary step generates a program that modifies itself each time it executes. Somewhat strange but quite impressive. But even in this case, the repeated runs are done outside the system! It still doesn't have embedded loops! It's not that one can't include a looping structure as a primitive. It's that GP is not good at using it. Another interesting paper was on how Eureqa <http://ccsl.mae.cornell.edu/eureqa>solved f(f(x)) = x^2 -2. (This is a famous problem: find a function f that does this.) It found a new solution, which involves limits! If you are interested in GP look at Eureqa. It's Genetic Programming to be used by scientists, not programmers. Very nice. It does what's called symbolic regression: find a function that fits a set of data points. Back to the sorting questions, I'd be very interested in hearing more about the sorting program that found a new way to sort. -- Russ Abbott ______________________________________ Professor, Computer Science California State University, Los Angeles cell: 310-621-3805 blog: http://russabbott.blogspot.com/ vita: http://sites.google.com/site/russabbott/ ______________________________________ On Sat, Jul 10, 2010 at 6:18 PM, Marcus Daniels <mar...@snoutfarm.com>wrote: > John Kennison wrote: > >> Putting in the swapping primitive seems like aiming for the simple sort >> which keeps on swapping until it can't be done anymore. >> >> >> > It seems then the question is whether or not a swapping primitive can be > evolved... And then whether or not whatever primitives are chosen for > evolving swapping can be evolved. If the dots can be connected, it should > just be a question of being patient enough or having enough computational > power.. > > Marcus > > > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > lectures, archives, unsubscribe, maps at http://www.friam.org >
============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org
