Genetic Algorithms Digest Thursday, 27 July 1989 Volume 3 : Issue 12 - Send submissions to GA-List@AIC.NRL.NAVY.MIL - Send administrative requests to GA-List-Request@AIC.NRL.NAVY.MIL Today's Topics: - Re: GA on parity function (GA-List v3n11) - Double Auction Tournament - IJCNN session on EVOLUTIONARY PROCESSES (2) - Messy GAs (mGAs) -------------------------------- Date: Wed, 12 Jul 89 08:30:22 EDT From: smith@Think.COM Subject: Re: GA on parity function (GA-List v3n11) > I was just given a problem (by George Benke, a methemetician here who's > trying to understand the GA) that it seems the ga is absolutely no good > for, as far as we can tell. > > The problem is to model an environment defined by the parity function, > where a string has value 1 if it has an even number of bits, and 0 > otherwise. The function is very global in character. It seems to so > completely violate the building blocks assumption that (correct me if > I'm wrong) the ga drives to a population with 50% even, 50% odd parity > even if it starts with a "really good" population of 100% even parity > individuals. This is because the odds of crossover between good parents > leading to good offspring is 50%. Mutation would seem to be even worse. > > Someone out there must have looked at this before. Is there a way in > which a solution to this problem might conceivably evolve? How? > > Jim Antonisse > MITRE I think that the real problem here is that your search space has multiple optima [(expt 2 (- n 1))]. So for a problem like this you really need speciation to occur. Using Goldberg and Richardson's sharing function (ICGA 87) or Deb and Goldberg's sharing with restricted crossover (ICGA 89) would probably help. The simplest solution would be to have the organisms laid out on some low dimensionality grid (say 2d) and then require them to mate and compete locally. I think you'd see a whole bunch clusters of different solutions arise almost immediately. Eventually (and I mean a long time) this would probably all converge to one solution due to genetic drift. - Stephen -------------------------------- Date: Wed, 12 Jul 89 10:50:11 MDT From: John Miller Subject: Double Auction Tournament Enclosed you will find an announcement for a computerized Double Auction Tournament being sponsored by the Santa Fe Institute. We are hoping to get a variety of entries, including some based on GAs and Classifier Systems. We would be most appreciative if you could post this notice in the next GA Digest. Thanks. --John ************** DOUBLE AUCTION TOURNAMENT Computer Strategy Challenge Rewards: $10,000 THE CHALLENGE Entries in the form of computer programs are invited for a Double Auction Tournament to be conducted at the Santa Fe Institute in March 1990. The Double Auction game is based on the operation of the New York Stock Exchange and the Chicago Board of Trade, and is of current interest to economists and game theorists. Developing an effective strategy for playing the game is apparently a simple challenge, but actually rather subtle. THE GAME Each player in a game is either a buyer or a seller of tokens. A seller tries to sell his or her tokens for as much as possible above token cost. A buyer tries to purchase tokens as cheaply as possible below their redemption value. Each seller's token costs and each buyer's redemption values are preassigned and differ from player to player. They are private information not known to the other players. Each auction proceeds in alternating bid/offer and buy/sell steps. In a bid/offer step each seller may offer to sell a token, and each buyer may make a bid to buy a token, each at prices they themselves specify. The lowest offer and highest bid determine the current bid and current offer prices. Then in the following buy/sell step the holder of the current bid may accept the current offer, or vice-versa, thus completing a transaction. If both sides accept, the tie is broken randomly. THE TOURNAMENT In the computer tournament each player will be represented by a separate computer program. A central monitor program manages the game. Reward money totaling $10,000 will be distributed among the participants in proportion to the total trading profit earned by their programs. Many games will be played to determine which programs make the highest profit on average. Entries will be limited to 100 and a small entrance fee will be charged. The purpose of the tournament is to gather scientific data to improve our understanding of market trading strategies, which may offer new insights into the behavior of real world markets. Each player's program may be written in C, Fortran or Pascal. Skeleton programs are provided in these languages so that participants only need to develop the routines that make the strategic decisions, such as how high to bid or when to accept an offer. THE SANTA FE TOKEN EXCHANGE Participants who have access to the worldwide Internet computer network will be able to play each other and local strategies in practice games by connecting to the Santa Fe Token Exchange. The Exchange is a monitor running regularly at the Santa Fe Institute until just before the actual tournament. MORE INFORMATION For further details about the tournament please include an electronic mail address, if available, and write to: Double Auction Tournament Santa Fe Institute 1120 Canyon Road Santa Fe, NM 87501 or send electronic mail to dat@sfi.santafe.edu. This tournament is sponsored by the Economics Program of the Santa Fe Institute. Reward money provided in part by IBM. Developed by Richard Palmer, John Rust and John Miller. Sponsored by the Santa Fe Institute. -------------------------------- Date: Sun, 23 Jul 89 16:17:42 EDT From: mlittman@wind.bellcore.com (Michael S. Littman) Subject: IJCNN session on EVOLUTIONARY PROCESSES (1) In a recent issue of GA-List, John Grefenstette detailed a call for papers for the upcoming IJCNN conference. He mentioned a special, full-length session of invited an contributed talks on EVOLUTIONARY PROCESSES. This conference was also described in a recent Neuron Digest (volume 5, issue 31) with no mention of the session on evolutionary processes. As such, I am not sure how to respond to their request to: > Be sure to specify which track and session you are submitting your > paper to and whether you prefer an Oral or Poster presentation. Is there any more information known about this? Thank you for your help. -Michael -------------------------------- Date: Mon, 24 Jul 89 22:27:14 EDT From: mlittman@wind.bellcore.com (Michael S. Littman) Subject: IJCNN session on EVOLUTIONARY PROCESSES (2) I got a note from the person who posted a IJCNN announcement in "neuron list" (Mike Lehr (lehr@isl.stanford.edu)). He said that there would most definitely be a special session: > Yes, there is a special session on evolutionary effects. There have > been three changes to the call for papers since I posted it. The > name of the "Neurobiology Track" has been changed to the "Neural & > Cognitive Sciences Track", an "Other Real-World applications" > session has been added to the Applications Track, and the session > "Special Session: Evolutionary Effects" has been added to the Neural > & Cognitive Sciences Track. On a semi-related topic, I have a question. Do you know of where I could find references of examples of people using GAs to train NNs (for instance, as an alternative to backprop)? I know this has been done but I have no handle into the literature. I'm looking for some citable source. Thanks! -Michael -------------------------------- Date: Thu, 29 Jun 89 06:29:51 CDT From: Dave Goldberg Subject: Messy GAs (mGAs) TCGA Report 89003 entitled "Messy Genetic Algorithms: Motivation, Analysis, and First Results" describes the development, analysis, and testing of a somewhat different type of genetic algorithm called a messy GA (mGA). Where simple GAs use fixed-length, fixed coding strings, messy GAs allow variable- length strings that may be either under- or overspecified with respect to the problem being solved. In proof-of-principle experiments, the an mGA solves a 30-bit, order-3 deceptive problem to optimality with no prior knowledge of good string orderings. By contrast, a simple GA with random ordering makes errors at 75% of all bit positions. Remaining challenges are described in the report, as are potential application of messy methods in messy permutation codes, messy adaptive floating point codes, and messy rules (classifiers). A draft version is available via e-mail or real-mail: Dave Goldberg dgoldber@ua1vm.ua.edu Department of Engineering Mechanics University of Alabama 210 Hardaway Hall Tuscaloosa, AL 35487 205-348-1618 -------------------------------- End of Genetic Algorithms Digest ********************************