Virtual-world genetic algorithm example... help!
Locked
Virtual-world genetic algorithm example... help!
 
|
I am reminded of two conflicting reports I got from two friends about an attempt to evolve a sorting program. One friend reported that it was discouraging. The evolved programs never were reliable and they took all kinds of time and had many superfluous features. The only way to actually get an algorithm that worked was to have a sorting method in mind then give the program more survival credit the more it mimicked the program in mind. Another friend reported that the attempt was a phenomenal success. A program evolved which sorted lists perfectly and efficiently and which was unlike any known sorting algorithm, In fact, no on could figure out what the program was doing; the only reason they felt it most be theoretically correct was that it sorted a huge number of lists perfectly every time. Can any of you tell me which friend is giving a more accurate account? (It is possible that the accounts refer to different experiments and are both accurate. The pessimistic account was told to me about 10 years ago, the other account recently.) ============================================================ 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 |
Re: Virtual-world genetic algorithm example... help!
|
|
I've had both experiences. The successful version had a couple of advantages. It had more useful primitives and a more useful fitness function. I don't remember the details, but a primitive that says swap adjacent cells if one is less that the other helps a lot! A fitness function that counts the number of elements out of place is much less useful than one that measures the extent to which the result is ordered, e.g., how many elements are on the correct side of their neighbors.
The bottom line is that there has to be a path from the initial primitives to the goal in which each step has increasing fitness. If you've got that an evolutionary process should get there. If not, it probably won't. -- Russ On Sat, Jul 10, 2010 at 1:22 PM, John Kennison <[hidden email]> wrote:
============================================================ 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 |
Re: Virtual-world genetic algorithm example... help!
|
|
Thanks Russ. depending on the primitives chosen, this could be more in line with the pessimistic account. Putting in the swapping primitive seems like aiming for the simple sort which keeps on swapping until it can't be done anymore. Do you know of any evolutionary process which produced a highly efficient and previously unknown sorting algorithm? ---John ________________________________________ From: [hidden email] [[hidden email]] On Behalf Of Russ Abbott [[hidden email]] Sent: Saturday, July 10, 2010 8:32 PM To: The Friday Morning Applied Complexity Coffee Group Subject: Re: [FRIAM] Virtual-world genetic algorithm example... help! I've had both experiences. The successful version had a couple of advantages. It had more useful primitives and a more useful fitness function. I don't remember the details, but a primitive that says swap adjacent cells if one is less that the other helps a lot! A fitness function that counts the number of elements out of place is much less useful than one that measures the extent to which the result is ordered, e.g., how many elements are on the correct side of their neighbors. The bottom line is that there has to be a path from the initial primitives to the goal in which each step has increasing fitness. If you've got that an evolutionary process should get there. If not, it probably won't. -- Russ On Sat, Jul 10, 2010 at 1:22 PM, John Kennison <[hidden email]<mailto:[hidden email]>> wrote: I am reminded of two conflicting reports I got from two friends about an attempt to evolve a sorting program. One friend reported that it was discouraging. The evolved programs never were reliable and they took all kinds of time and had many superfluous features. The only way to actually get an algorithm that worked was to have a sorting method in mind then give the program more survival credit the more it mimicked the program in mind. Another friend reported that the attempt was a phenomenal success. A program evolved which sorted lists perfectly and efficiently and which was unlike any known sorting algorithm, In fact, no on could figure out what the program was doing; the only reason they felt it most be theoretically correct was that it sorted a huge number of lists perfectly every time. Can any of you tell me which friend is giving a more accurate account? (It is possible that the accounts refer to different experiments and are both accurate. The pessimistic account was told to me about 10 years ago, the other account recently.) ============================================================ 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 |
Re: Virtual-world genetic algorithm example... help!
|
|
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 |
Re: Virtual-world genetic algorithm example... help!
|
|
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 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 <[hidden email]> wrote:
============================================================ 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 |
Re: Virtual-world genetic algorithm example... help!
|
|
Russ Abbott wrote:
> 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. That's a question of how diversity is maintained in population and what kind of transformations are made to the population of programs. If transformations are modular or there is no mechanism for maintaining diversity, then a rugged fitness landscape may well cause problems -- the population can reduce to, in-effect, one individual and be stuck in a rut forever. It's a problem with optimization algorithms in general, not just genetic programming. > It's not that one can't include a looping structure as a primitive. > It's that GP is not good at using it. I suspect enhanced evaluation mechanisms are needed to influence fitness. I speculate that historical human imperative programing habits aren't particularly helpful either for automated programming (better to have lambdas bound to names and recursion). The size of the expression tree has been used in GP for a long time to encourage parsimonious solutions to be found, but I suspect there hasn't been much work has been done to provide a cost of a calculation. By that I mean stuff like L3 cache misses (how irregular is the memory access pattern?), the maximum depth of the stack pointer (is it non-terminating recursion?), instructions retired (logically how efficient is the calculation?), and total joules used (what does it really take to make CPUs do it?). Optimizing over that space is what quantifies the difference between good and bad programs.. 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 |
Re: Virtual-world genetic algorithm example... help!
|
|
In reply to this post by Russ Abbott
On Sat, Jul 10, 2010 at 06:38:54PM -0700, Russ Abbott wrote:
> > Back to the sorting questions, I'd be very interested in hearing more about > the sorting program that found a new way to sort. > > I recall Danny Hillis achieved this with a coevolutionary genetic algorithm back in the early '90s. I think it was published in one of the early ALife proceedings (probably volume 2 - the one I never managed to get a copy of :). Cheers -- ---------------------------------------------------------------------------- Prof Russell Standish Phone 0425 253119 (mobile) Mathematics UNSW SYDNEY 2052 [hidden email] Australia http://www.hpcoders.com.au ---------------------------------------------------------------------------- ============================================================ 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 |
Re: Virtual-world genetic algorithm example... help!
|
|
Right. That was his work on sorting networks.
-- Russ On Sun, Jul 11, 2010 at 10:47 AM, Russell Standish <[hidden email]> wrote: On Sat, Jul 10, 2010 at 06:38:54PM -0700, Russ Abbott wrote: ============================================================ 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 |
Re: Virtual-world genetic algorithm example... help!
|
|
At some point I said that GP has not succeeded in generating what we normally think of as computer programs. Recently, however, there has been some impressive work on debugging existing programs. "Automatic Program Repair with Evolutionary Computation" from the May CACM reports on work that was presented at last year's GECCO. This year I heard a presentation about this paper: M. Orlov and M. Sipper,
<a href="javascript:popUp('http://www.cs.bgu.ac.il/~sipper/papabs/finch-tevc.html')">Flight of the FINCH through the Java wilderness,
IEEE Transactions on Evolutionary Computation,
Strangely, I can't find anything like it listed anywhere in the GECCO proceedings. The pointer is to the abstract of the paper to appear in IEEE Transactions on Evolutionary Computation. The full paper is apparently not available on the web.
-- Russ On Sun, Jul 11, 2010 at 7:05 AM, Russ Abbott <[hidden email]> wrote:
============================================================ 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 |
«
Return to Friam
|
1 view|%1 views
| Free forum by Nabble | Edit this page |