Re: [FRIAM] Virtual-world genetic algorithm example... help!
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 hpco...@hpcoders.com.au Australiahttp://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: [FRIAM] Virtual-world genetic algorithm example... help!
Right. That was his work on sorting networkshttp://www.cogs.susx.ac.uk/users/inmanh/easy/alife06/PhysicaD1990-42-1-3-Hillis.pdf . -- Russ On Sun, Jul 11, 2010 at 10:47 AM, Russell Standish r.stand...@unsw.edu.auwrote: 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 hpco...@hpcoders.com.au Australiahttp://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: [FRIAM] 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
Computationhttp://www.cs.bham.ac.uk/%7Ewbl/biblio/cache/http___www.cs.virginia.edu__weimer_p_p109-weimer.pdf
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, *Flight
of the FINCH through the Java
wilderness*javascript:popUp('http://www.cs.bgu.ac.il/~sipper/papabs/finch-tevc.html'),
*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 russ.abb...@gmail.com wrote:
Right. That was his work on sorting
networkshttp://www.cogs.susx.ac.uk/users/inmanh/easy/alife06/PhysicaD1990-42-1-3-Hillis.pdf
.
-- Russ
On Sun, Jul 11, 2010 at 10:47 AM, Russell Standish r.stand...@unsw.edu.au
wrote:
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 hpco...@hpcoders.com.au
Australiahttp://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
[FRIAM] 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: [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 jkenni...@clarku.edu 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: [FRIAM] 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: friam-boun...@redfish.com [friam-boun...@redfish.com] On Behalf Of Russ Abbott [russ.abb...@gmail.com] 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 jkenni...@clarku.edumailto:jkenni...@clarku.edu 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: [FRIAM] 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
