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: [email protected] [[email protected]] On Behalf Of Russ Abbott [[email protected]] 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 <[email protected]<mailto:[email protected]>> 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
