From genetic-programming-owner@list.Stanford.EDU Sun Feb 27 10:36:27 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA11953; Sun, 27 Feb 94 10:36:05 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Sat, 26 Feb 94 03:45 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id DAA01974 for ; Fri, 25 Feb 1994 03:02:08 -0800 Received: from csvax1.ucc.ie by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA03052; Fri, 25 Feb 1994 03:00:53 -0800 Received: from ravenloft.ucc.ie by csvax1.ucc.ie (MX V3.3 VAX) with SMTP; Fri, 25 Feb 1994 11:00:22 BST Received: by ravenloft.ucc.ie (Smail3.1.28.1 #6) id m0pa0HL-00004bC; Fri, 25 Feb 94 11:00 GMT Resent-Date: Sat, 26 Feb 94 11:01 EDT Date: Fri, 25 Feb 1994 11:00:18 +0100 (GMT) From: conor@ravenloft.ucc.IE Subject: RE: Diversity and sexiness in GA/GP Resent-To: lee@neural.hampshire.EDU To: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <55E05FE8AE1F02CA3A@hamp.hampshire.edu> Message-Id: X-Mailer: ELM [version 2.4 PL21] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 1613 X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: genetic-programming@cs.stanford.EDU Status: O Peter Dudney wrote: > Measure fitness for each individual for each test case. More fit > individuals are more likely to breed, as usual, but you only select > one individual to breed, and that individual chooses it's mate. The > mate is chosen, either deterministically or stochastically, according > to "sexiness", where: > __ > \ > sexiness = > success ( potential-mate ) - success (self) > /_ > n > > and n is the number of cases in the fitness test. > > > In other words, an individual is sexy to you to the extent that it > does better than you on the test cases. The formula might be changed > to sum-of-squares to increase the relative sexiness of individuals > that vastly outperform you in some areas. > I've done a fair amount of work in a related area to this, using a modified version of my Pygmy Algorithm from Kim's book. I have distinct "races" in my populations, and once an individual is chosen for breeding, it decides itself, based on an inherited racial preference factor, which race it wants to choose a mate from. The benefits of races are similar to that of seperate populations with migration, but migration between races happens automatically if left up to the individuals themselves. > > Discussion, pointer to literature? Is this a (social or genetic) > factor in biological sexual attraction? > I would definitly think it is a factor, and you might want to check out: "On the Sympatric Origin of Species: Mercurial Mating in the Quicksilver Model", Todd & Miller, in, I think, ICGA3. Conor. conor@ravenloft.ucc.ie From genetic-programming-owner@list.Stanford.EDU Fri Feb 25 15:03:08 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA03708; Fri, 25 Feb 94 15:03:04 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Fri, 25 Feb 94 13:37 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id IAA03367 for ; Fri, 25 Feb 1994 08:38:33 -0800 Received: from research.CS.ORST.EDU (chert.CS.ORST.EDU) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA13925; Fri, 25 Feb 1994 08:37:29 -0800 Received: from hume.CS.ORST.EDU by research.CS.ORST.EDU (4.1/1.30) id AA14853; Fri, 25 Feb 94 08:37:17 PST Received: by hume.CS.ORST.EDU (4.1/CS-Client) id AA19734; Fri, 25 Feb 94 08:37:16 PST Resent-Date: Fri, 25 Feb 94 14:24 EDT Date: Fri, 25 Feb 94 08:37:16 PST From: dudeyp@chert.CS.ORST.EDU Subject: Diversity and sexiness in GA/GP Resent-To: lee@neural.hampshire.EDU To: keithm@icd.ab.COM Cc: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <568D8869E8BF029680@hamp.hampshire.edu> Message-Id: <9402251637.AA19734@hume.CS.ORST.EDU> In-Reply-To: "Mike J. Keith"'s message of Fri, 25 Feb 1994 09:01:55 -0500 <199402251401.JAA15298@odin.icd.ab.com> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: keithm@icd.ab.COM X-Vms-Cc: genetic-programming@cs.stanford.EDU Status: O > Date: Fri, 25 Feb 1994 09:01:55 -0500 > From: "Mike J. Keith" > > However, I think it makes more sense to me for "sexiness" to increase > based on the opposites attract premise. That is, an individual will > desire others whos profile is good but UNIQUE from his own. > > So if you have 3 individuals A, B, and C where A is looking for a > mate. Even if B's raw fitness is better than C's, A will desire C if > C's profile is unique enough - hey I would rather kiss a stranger than > my sister even if my sister is more attractive: > > Sexiness = C1*rawFitness + C2*Uniqueness > > Where uniqueness is based on the sum of squares of differences over the > test case profile as Peter mentioned. The second term above will take more > effect later in the run. Wouldn't this make a successful twin of yourself and a horribly unfit mutant appear equally sexy? Wouldn't that be a bad thing? I figured one should choose a mate that did /well/ on problems that the chooser found difficult, not just one that had /different/ scores. Hmmm. I suppose, then, that under my original model, sum-of-cubes might be better than sum-of-squares, because squares would only emphasize difference. It is worth pointing out that this technique only insures phenotypic, rather than genotypic, diversity. /~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\ \ Peter Dudey, MS student in Artificial Intelligence, Oregon State University / / dudeyp@research.cs.orst.edu : hagbard on IGS : 257 NE 13th, Salem, OR 97301 \ \ "We feel confident that there is a 4-line LISP hack for consciousness." / ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ From genetic-programming-owner@list.Stanford.EDU Fri Feb 25 15:04:16 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA03727; Fri, 25 Feb 94 15:04:12 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Fri, 25 Feb 94 13:59 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id IAA03414 for ; Fri, 25 Feb 1994 08:47:57 -0800 Received: from research.CS.ORST.EDU (chert.CS.ORST.EDU) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA14359; Fri, 25 Feb 1994 08:46:53 -0800 Received: from hume.CS.ORST.EDU by research.CS.ORST.EDU (4.1/1.30) id AA14900; Fri, 25 Feb 94 08:46:49 PST Received: by hume.CS.ORST.EDU (4.1/CS-Client) id AA19737; Fri, 25 Feb 94 08:46:49 PST Resent-Date: Fri, 25 Feb 94 14:17 EDT Date: Fri, 25 Feb 94 08:46:49 PST From: dudeyp@chert.CS.ORST.EDU Subject: Diversity and sexiness in GA/GP Resent-To: lee@neural.hampshire.EDU To: rothfusza@osprey.nwrc.GOV Cc: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <568E8A83847F029680@hamp.hampshire.edu> Message-Id: <9402251646.AA19737@hume.CS.ORST.EDU> In-Reply-To: rothfusza@osprey.nwrc.gov's message of Fri, 25 Feb 94 08:53:30 cst <9401257621.AA762195210@osprey.nwrc.gov> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: rothfusza@osprey.nwrc.GOV X-Vms-Cc: genetic-programming@cs.stanford.EDU Status: O > Date: Fri, 25 Feb 94 08:53:30 cst > From: rothfusza@osprey.nwrc.gov > > Hello Peter: > > Your "sexiness" posting to the GP list sounds like a generalization of > my own selection algorithm. I do not completely understand your > summation, however. You seem to indicate that for each fitness test, > you calculate the success of each possible mate and the success of the > "self", take the difference, and accumulate this value over n tests. > Does this mean that "self" gets tested n times against m possible > mates? Does each possible mate repeat the process? What defines a > possible mate? Each individual is tested exactly once on each of the fitness cases. These are just problems in the domain that the individuals are supposed to be good at. For example, if one is breeding polynomials to fit a curve, the fitness cases might be the points on the curve. These are stored so that they can be re-used. The idea is that if I closely fit the first two-thirds of the data points, I want to breed with someone who does well in general, and specifically on the last one-third. I don't have any demes or the like in mind, so everyone is a potential mate. /~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\ \ Peter Dudey, MS student in Artificial Intelligence, Oregon State University / / dudeyp@research.cs.orst.edu : hagbard on IGS : 257 NE 13th, Salem, OR 97301 \ \ "We feel confident that there is a 4-line LISP hack for consciousness." / ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ From genetic-programming-owner@list.Stanford.EDU Fri Feb 25 15:04:53 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA03759; Fri, 25 Feb 94 15:04:51 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Fri, 25 Feb 94 14:07 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id JAA03578 for ; Fri, 25 Feb 1994 09:14:58 -0800 Received: from odin.icd.ab.com by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA15222; Fri, 25 Feb 1994 09:13:50 -0800 Received: from gadwal.icd.ab.com (gadwal.icd.ab.com [130.151.132.71]) by odin.icd.ab.com (8.1C/5.6) with SMTP id MAA19047; Fri, 25 Feb 1994 12:13:44 -0500 Resent-Date: Fri, 25 Feb 94 14:14 EDT Date: Fri, 25 Feb 1994 12:13:44 -0500 From: "Mike J. Keith" Subject: RE: Diversity and sexiness in GA/GP Resent-To: lee@neural.hampshire.EDU To: dudeyp@chert.CS.ORST.EDU Cc: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <568EDF90489F029680@hamp.hampshire.edu> Message-Id: <199402251713.MAA19047@odin.icd.ab.com> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: dudeyp@chert.CS.ORST.EDU X-Vms-Cc: genetic-programming@cs.stanford.EDU Status: O I offerred: > > Sexiness = C1*rawFitness + C2*Uniqueness > > > > Where uniqueness is based on the sum of squares of differences over the > > test case profile as Peter mentioned. The second term above will take more > > effect later in the run. Peter responded: >Wouldn't this make a successful twin of yourself and a horribly unfit >mutant appear equally sexy? Wouldn't that be a bad thing? A successful twin of yourself would have a low uniqueness causing the 2nd term to be low. An unfit mutant would have a low first term. Both terms will only be high when the potential mate has a high default fitness and also has a unique fitness profile with respect to the choser. You can obviously adjust C1 and C2 (perhaps even dynamically) to control how important you want uniqueness to be with respect to raw fitness (note that raw fitness is just your normal error sum). The problem with using the strait diff or a cube of the diff is that the differences between 2 individuals can cancel out. So if most of the population is able to solve half of the test cases very well and along comes an individual who is a bit worse at the known half but a bit better at the other cases. By using the sum of the squares in the 2 term formula above, this individual would be very sexy which is what I would think your after. If you use just the diff or the cube, you can only find individuals who are better overall which normal GA or GP does anyway - looking at the profile then doesn't really buy you anything ......does it ?? Mike From genetic-programming-owner@list.Stanford.EDU Fri Feb 25 15:15:22 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA03774; Fri, 25 Feb 94 15:15:20 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Fri, 25 Feb 94 14:38 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id JAA03692 for ; Fri, 25 Feb 1994 09:32:20 -0800 Received: from research.CS.ORST.EDU (chert.CS.ORST.EDU) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA15899; Fri, 25 Feb 1994 09:31:14 -0800 Received: from hume.CS.ORST.EDU by research.CS.ORST.EDU (4.1/1.30) id AA15159; Fri, 25 Feb 94 09:31:11 PST Received: by hume.CS.ORST.EDU (4.1/CS-Client) id AA19754; Fri, 25 Feb 94 09:31:10 PST Resent-Date: Fri, 25 Feb 94 15:02 EDT Date: Fri, 25 Feb 94 09:31:10 PST From: dudeyp@chert.CS.ORST.EDU Subject: Diversity and sexiness in GA/GP Resent-To: lee@neural.hampshire.EDU To: keithm@icd.ab.COM Cc: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <5688304BDF3F02C479@hamp.hampshire.edu> Message-Id: <9402251731.AA19754@hume.CS.ORST.EDU> In-Reply-To: "Mike J. Keith"'s message of Fri, 25 Feb 1994 12:13:44 -0500 <199402251713.MAA19047@odin.icd.ab.com> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: keithm@icd.ab.COM X-Vms-Cc: genetic-programming@cs.stanford.EDU Status: O > Date: Fri, 25 Feb 1994 12:13:44 -0500 > From: "Mike J. Keith" > > Peter responded: > > >Wouldn't this make a successful twin of yourself and a horribly unfit > >mutant appear equally sexy? Wouldn't that be a bad thing? > > A successful twin of yourself would have a low uniqueness causing the > 2nd term to be low. An unfit mutant would have a low first term. Both terms > will only be high when the potential mate has a high default fitness and > also has a unique fitness profile with respect to the choser. > > The problem with using the strait diff or a cube of the diff is that the > differences between 2 individuals can cancel out. So if most of the population Hmmm. Good point. Still, it appears that your scheme rewards inferiority at some test case (although it would punish inferiority at many). How about this? Sexiness = SUM superiority ( potential-mate, self, test_case(i) ) i Where superiority is: If the potential mate does better than you, the square of the diff of your fitnesses, otherwise minus the diff of your fitnesses. For example: Test Case 1 2 3 4 5 Self 3 7 3 8 2 P. Mate 8 2 9 3 1 superiority 25 -5 36 -5 -1 resulting in a sexiness of 50. If squaring is too potent, a smaller power might be in order, as might some normalization. Note that both of the schemes I have offered allow for negative sexiness, and an individual looking at a copy of itself will find it to have sexiness 0. /~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\ \ Peter Dudey, MS student in Artificial Intelligence, Oregon State University / / dudeyp@research.cs.orst.edu : hagbard on IGS : 257 NE 13th, Salem, OR 97301 \ \ "We feel confident that there is a 4-line LISP hack for consciousness." / ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ From genetic-programming-owner@list.Stanford.EDU Sat Feb 26 03:05:42 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA09526; Sat, 26 Feb 94 03:05:21 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Fri, 25 Feb 94 15:52 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id KAA04186 for ; Fri, 25 Feb 1994 10:58:09 -0800 Received: from lightstream.LightStream.COM (lightstream.com) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA19320; Fri, 25 Feb 1994 10:57:04 -0800 Received: from cockatrice.LightStream.COM by lightstream.LightStream.COM (4.1/SMI-4.1) id AA28028; Fri, 25 Feb 94 13:57:00 EST Received: by cockatrice.LightStream.COM (4.1/SMI-4.1) id AA09474; Fri, 25 Feb 94 13:56:58 EST Resent-Date: Fri, 25 Feb 94 16:33 EDT Date: Fri, 25 Feb 1994 13:56:57 -0500 From: Dave Faulkner Subject: RE: Diversity and sexiness in GA/GP Resent-To: lee@neural.hampshire.EDU To: dudeyp@chert.CS.ORST.EDU Cc: genetic-programming@cs.stanford.EDU, dfaulkne@LightStream.COM Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <567B6BFBA3BF02D81E@hamp.hampshire.edu> Message-Id: <9402251856.AA09474@cockatrice.LightStream.COM> In-Reply-To: Your message of "Thu, 24 Feb 1994 17:25:04 PST." <9402250125.AA19628@hume.CS.ORST.EDU> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: dudeyp@chert.CS.ORST.EDU X-Vms-Cc: genetic-programming@cs.stanford.EDU, dfaulkne@LightStream.COM Status: O Peter Dudey Writes: In other words, an individual is sexy to you to the extent that it does better than you on the test cases. The formula might be changed to sum-of-squares to increase the relative sexiness of individuals that vastly outperform you in some areas. ...and Mike Keith chips in with: However, I think it makes more sense to me for "sexiness" to increase based on the opposites attract premise. That is, an individual will desire others whos profile is good but UNIQUE from his own. .... Sexiness = C1*rawFitness + C2*Uniqueness Where uniqueness is based on the sum of squares of differences over the test case profile as Peter mentioned. The second term above will take more effect later in the run. Thank you for your thoughts on this matter. These are interesting metrics to be sure, but I don't think that they address the issue of mainaining *diversity* in a population based on uniqueness of genotype. Fitness is twice removed from genotypic representation, as the genotype is mapped into phenotype (problem domain) and the phenotype is then mapped to fitness (expression of an individual in the problem ecology). This distance from the original representation makes it difficult to maintain diversity in the population because the uniqueness of the individual is no longer represented in the fitness, regardless of how many cases are examined. This will lead, I believe, in faster convergence of the population toward a solution, but will not necessarily lead to a diversified population that is able to quickly adapt later to changing conditions in the environment. (Thus the computation will run out of "steam"). Think of a fitness surface with two hills. You want equal numbers of beings at each hill site if they are equal in height. With the metrics you propose, there is no difference in the metric if a being is at the same height for either hill, so there is no bias toward picking the guy (gal) not on your being's hill to mate with. Its only by looking at the genotypic (and some would say that phenotypic is preferred) representation that you know that the other guy(gal) is not on your being's hill and so to maintain diversity you should pick the guy(gal) on the other hill to mate. In GP, the problem is understanding nearness in the genotypic or phenotypic representations, I would guess. Hamming distance calculations take advantage of the consistency of a parameter string: position 3 always means "the x value" in some function, has a range from 1..-1, etc. GP s-expressions have no such consistency, and no obvious cannonical form to facilitate comparisons between s-expressions; thus no easy metric. Collins ("Studies in Artificial Evolution") and others talk about using "demes" to maintain diversity. This is an interesting idea. Rather than measuring distances between individuals, you superimpose an artificial distance that ignores representation, and the sustaining of that distance bias generation after generation creates isolated niches that are allowed to maintain uniqueness within the population due to this stochastic barrier prohibiting genetic material swapping, thus creating "islands" of relatively fit, unique individuals. (Think of an island of birds where on rare occasion, one gets blown over to another island to affect the gene pool of the other island bird population). The problem I have with this approach is that this diversity isn't really garaunteed: its an effect of an initial randomness of the population and the isolation of the islands. Given enough time, can we be sure that the majority of islands will not converge on the same hill, and eventaully that all islands will converge to the same hill? This seems like a logical conclusion; demes create divergence, but only for a while (that time being extended by the size of islands and population exchange rate). I can well see how demes will slow convergence for a very long time. In nature, I believe diversity is a function of the environment as well as the population dynamics (e.g., what if each deme has a slightly different fitness function), and unlike most of our toy models, fitness functions are not time-invariant (evolution by subsumption (?) competition excluded). Of course, tying genotypic representation to fitness modulation has many problems as well: it must be centralized, it is expensive, it is representation specific, etc. It also seems very hard for GP (at least for me). From genetic-programming-owner@list.Stanford.EDU Sat Feb 26 00:19:54 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA09465; Sat, 26 Feb 94 00:18:13 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Fri, 25 Feb 94 16:19 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id KAA04106 for ; Fri, 25 Feb 1994 10:42:56 -0800 Received: from dynamo.ecn.purdue.edu by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA18819; Fri, 25 Feb 1994 10:41:51 -0800 Received: from msesmac11.ecn.purdue.edu by dynamo.ecn.purdue.edu (5.65/1.32jrs) id AA25716; Fri, 25 Feb 94 13:41:48 -0500 Resent-Date: Fri, 25 Feb 94 16:57 EDT Date: Fri, 25 Feb 1994 13:41:49 -0600 From: tenorio@ecn.purdue.EDU Subject: RE: Diversity and sexiness in GA/GP Resent-To: lee@neural.hampshire.EDU To: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <56780FE3503F02B931@hamp.hampshire.edu> Message-Id: <9402251841.AA25716@dynamo.ecn.purdue.edu> X-Sender: tenorio@dynamo.ecn.purdue.edu X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: genetic-programming@cs.stanford.EDU Status: O >>In other words, an individual is sexy to you to the extent that it >>does better than you on the test cases. The formula might be changed >>to sum-of-squares to increase the relative sexiness of individuals >>that vastly outperform you in some areas. > >This is an interesting idea. The way I look at it is that your looking at >a "fitness-profile" instead of just a single value fitness. > >However, I think it makes more sense to me for "sexiness" to increase >based on the opposites attract premise. That is, an individual will >desire others whos profile is good but UNIQUE from his own. > >So if you have 3 individuals A, B, and C where A is looking for a >mate. Even if B's raw fitness is better than C's, A will desire C if >C's profile is unique enough - hey I would rather kiss a stranger than >my sister even if my sister is more attractive: > Shouldn't this be better summarized by saying that the most complementary form of the problem is the best partner? This is akin to a combination of low correlation among parents as well as high performance in the penalty function. The problem is that this describes a two part function to be minimize and that has all the classical problems of such multiobjective minimization. If you require high fitness, the correlation term gets neglected and you spin your wheels (focused search, low diversity). If you require uncorrelation to be higher, diversity certainly increases and so does the probability of a good solution at the expense of a more unfocused search. Sho Kuwamoto (sho@physics.purdue.edu) has explored with a number of different forms of the correlation x penalty terms in the design of the SONN (previous posting) with interesting results that where superior to not having the correlation term in the penalty function. This is an interesting problem for submodel selection. Cheers. --ft. < Manoel Fernando Tenorio > < (tenorio@ecn.purdue.edu) or (..!pur-ee!tenorio) > < MSEE233D > < Parallel Distributed Structures Laboratory > < School of Electrical Engineering > < Purdue University > < W. Lafayette, IN, 47907-1285 > < Phone: 317-494-3482 Fax: 317-494-6440 > From genetic-programming-owner@list.Stanford.EDU Sat Feb 26 00:20:36 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA09470; Sat, 26 Feb 94 00:20:20 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Fri, 25 Feb 94 16:27 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id LAA04413 for ; Fri, 25 Feb 1994 11:44:57 -0800 Received: from mail.netcom.com (netcom2.netcom.com) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA21448; Fri, 25 Feb 1994 11:43:53 -0800 Received: from localhost by mail.netcom.com (8.6.4/SMI-4.1/Netcom) id LAA16818; Fri, 25 Feb 1994 11:44:43 -0800 Resent-Date: Fri, 25 Feb 94 16:54 EDT Date: Fri, 25 Feb 1994 11:44:43 -0800 From: peb@netcom.COM Subject: PC Scheme, etc Resent-To: lee@neural.hampshire.EDU To: genetic-programming@cs.stanford.EDU, schenk@cs.bris.AC.UK Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <567899FAE03F02B931@hamp.hampshire.edu> Message-Id: <199402251944.LAA16818@mail.netcom.com> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: genetic-programming@cs.stanford.EDU, schenk@cs.bris.AC.UK Status: O Since I ran a project at Autodesk to build a Scheme environment, I have some answers to your Scheme questions... 1. Try ELK, created by Oliver Laumann. This is a fast and robust interpreter. Scheme2C from HP is probably faster, but it lacks call/cc, bignums amoung other things. 2. call/cc duplicates the stack in the heap whenever it is called. Invoking the continuation replaces the current stack with the saved one. The old stack is garbage collected if it is unbound (it could be bound by another call/cc, for instance). Call/cc thus introduces a GC problem. In the Autodesk version of Scheme I added call/cc-lite which was simply a setjmp (aside from the massive stack unwind interactions with the symbol tables...) so it did not introduce a GC problem and was much faster. (Sorry you can't use the program due to a management takeover that went back to the "core business" thus switching from Exploration to Exploitation.) 3. There must be another binding lurking around to keep the list around. Either that or you have a buggy interpreter. Paul E. Baclace peb@netcom.com From genetic-programming-owner@list.Stanford.EDU Sun Feb 27 09:24:35 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA11763; Sun, 27 Feb 94 09:24:12 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Fri, 25 Feb 94 17:26 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id MAA04747 for ; Fri, 25 Feb 1994 12:37:05 -0800 Received: from research.CS.ORST.EDU (chert.CS.ORST.EDU) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA24071; Fri, 25 Feb 1994 12:36:01 -0800 Received: from hume.CS.ORST.EDU by research.CS.ORST.EDU (4.1/1.30) id AA16464; Fri, 25 Feb 94 12:35:49 PST Received: by hume.CS.ORST.EDU (4.1/CS-Client) id AA19841; Fri, 25 Feb 94 12:35:47 PST Resent-Date: Sat, 26 Feb 94 13:06 EDT Date: Fri, 25 Feb 94 12:35:47 PST From: dudeyp@chert.CS.ORST.EDU Subject: Diversity and sexiness in GA/GP Resent-To: lee@neural.hampshire.EDU To: dfaulkne@lightstream.COM, hthies@willamette.EDU, tadepall@chert.CS.ORST.EDU Cc: genetic-programming@cs.stanford.EDU, dfaulkne@lightstream.COM Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <55CF19525E3F02AE28@hamp.hampshire.edu> Message-Id: <9402252035.AA19841@hume.CS.ORST.EDU> In-Reply-To: Dave Faulkner's message of Fri, 25 Feb 1994 13:56:57 -0500 <9402251856.AA09474@cockatrice.LightStream.COM> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: dfaulkne@lightstream.COM, hthies@willamette.EDU, tadepall@chert.CS.ORST.EDU X-Vms-Cc: genetic-programming@cs.stanford.EDU, dfaulkne@lightstream.COM Status: O > Date: Fri, 25 Feb 1994 13:56:57 -0500 > From: Dave Faulkner > > Thank you for your thoughts on this matter. These are interesting metrics to > be sure, but I don't think that they address the issue of mainaining *diversity* > in a population based on uniqueness of genotype. Fitness is twice removed from > genotypic representation, as the genotype is mapped into phenotype (problem > domain) and the phenotype is then mapped to fitness (expression of an individual > in the problem ecology). This distance from the original representation > ... > > Think of a fitness surface with two hills. You want equal numbers of beings at > each hill site if they are equal in height. With the metrics you propose, there > is no difference in the metric if a being is at the same height for either hill, > so there is no bias toward picking the guy (gal) not on your being's hill > to mate with. Its only by looking at the genotypic (and some would say that > phenotypic is preferred) representation that you know that the other guy(gal) > is not on your being's hill and so to maintain diversity you should pick > the guy(gal) on the other hill to mate. I'm not so sure. Under the sexiness scheme, you would only be "on the same hill" as me if your success chart over all of the test cases looked the same as mine. I'd expect that the technique would focus on "important" differences, where trying to maintain raw genetic diversity might waste "effort" keeping introns diverse. > In GP, the problem is understanding nearness in the genotypic or phenotypic > representations, I would guess. Hamming distance calculations take > advantage of the consistency of a parameter string: position 3 always > means "the x value" in some function, has a range from 1..-1, etc. > GP s-expressions have no such consistency, and no obvious cannonical > form to facilitate comparisons between s-expressions; thus no easy > metric. Another point for me. :-) /~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\ \ Peter Dudey, MS student in Artificial Intelligence, Oregon State University / / dudeyp@research.cs.orst.edu : hagbard on IGS : 257 NE 13th, Salem, OR 97301 \ \ "We feel confident that there is a 4-line LISP hack for consciousness." / ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ From genetic-programming-owner@list.Stanford.EDU Sun Feb 27 04:03:49 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA11709; Sun, 27 Feb 94 04:03:36 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Fri, 25 Feb 94 16:59 EDT Received: from BAY.CC.KCL.AC.UK (bay.cc.kcl.ac.uk [137.73.2.11]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id LAA04303 for ; Fri, 25 Feb 1994 11:19:32 -0800 Received: by bay.cc.kcl.ac.uk (MX V3.3 VAX) id 22502; Fri, 25 Feb 1994 19:20:54 EST Resent-Date: Sat, 26 Feb 94 21:14 EDT Date: Fri, 25 Feb 1994 19:20:43 EST From: udue074@bay.cc.kcl.AC.UK Subject: RE: Diversity and sexiness in GA/GP Resent-To: lee@neural.hampshire.EDU To: genetic-programming@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <558B04BD24DF02AE28@hamp.hampshire.edu> Message-Id: <0097A99B.E088DD40.22502@bay.cc.kcl.ac.uk> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: genetic-programming@list.Stanford.EDU Status: O >I have an idea for a somewhat related scheme that would, I think, work >for GP as well. It requires that the fitness test involve a number of >"test cases", where fitness is the sum of an individual's success over >these cases. >Measure fitness for each individual for each test case. More fit >individuals are more likely to breed, as usual, but you only select >one individual to breed, and that individual chooses it's mate. The >mate is chosen, either deterministically or stochastically, according >to "sexiness", where: > __ > \ >sexiness = > success ( potential-mate ) - success (self) > /_ > n > >and n is the number of cases in the fitness test. > > >In other words, an individual is sexy to you to the extent that it >does better than you on the test cases. The formula might be changed >to sum-of-squares to increase the relative sexiness of individuals >that vastly outperform you in some areas. I would like to specify the idea of sexiness in the following way: "an individual is sexy to you to the extent that it does better than you" on the part of the cases on which you are especially poor. In this way a complementarity of phenotype is achieved with the hope to propagate it to the children in the genotypic level. This method is successfully used in the Finate State Automaton identification problem by Vanyo Slavov (vslavov@inf.nbu.bg). As far as I know he uses the principle of sexiness not only to choose mates, but also to form a multi-cellar creaturte with differentiated cells. (Where the cells are complementary expressed in a sense that each cell solves a part of the problem, but the union of the solutions of the different cells gives approximate solution to the whole problem.) A possible fitness function can give credits if the union covers larger part of the whole solution, and possibly to punish intersections. George Bilchev / -----------------------------------------------------------------\ | George@inf.nbu.bg | New Bulgarian University | | | Dept. of Computer Science | | G.Biltchev@bay.cc.kcl.ac.uk | Sofia 1125 | | (valid until 25 March) | Bulgaria | \------------------------------------------------------------------/ From genetic-programming-owner@list.Stanford.EDU Fri Feb 25 16:34:59 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA03930; Fri, 25 Feb 94 16:34:45 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Fri, 25 Feb 94 16:14 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id LAA04370 for ; Fri, 25 Feb 1994 11:34:39 -0800 Received: from bay.cc.kcl.ac.uk by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA21046; Fri, 25 Feb 1994 11:33:30 -0800 Received: by bay.cc.kcl.ac.uk (MX V3.3 VAX) id 22550; Fri, 25 Feb 1994 19:35:53 EST Resent-Date: Fri, 25 Feb 94 16:19 EDT Date: Fri, 25 Feb 1994 19:35:41 EST From: udue074@bay.cc.kcl.AC.UK Subject: RE: Diversity and sexiness in GA/GP Resent-To: lee@neural.hampshire.EDU To: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <567D7178723F02D81E@hamp.hampshire.edu> Message-Id: <0097A99D.F7B1E6E0.22550@bay.cc.kcl.ac.uk> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: genetic-programming@cs.stanford.EDU Status: RO >I have an idea for a somewhat related scheme that would, I think, work >for GP as well. It requires that the fitness test involve a number of >"test cases", where fitness is the sum of an individual's success over >these cases. >Measure fitness for each individual for each test case. More fit >individuals are more likely to breed, as usual, but you only select >one individual to breed, and that individual chooses it's mate. The >mate is chosen, either deterministically or stochastically, according >to "sexiness", where: > __ > \ >sexiness = > success ( potential-mate ) - success (self) > /_ > n > >and n is the number of cases in the fitness test. > > >In other words, an individual is sexy to you to the extent that it >does better than you on the test cases. The formula might be changed >to sum-of-squares to increase the relative sexiness of individuals >that vastly outperform you in some areas. I would like to specify the idea of sexiness in the following way: "an individual is sexy to you to the extent that it does better than you" on the part of the cases on which you are especially poor. In this way a complementarity of phenotype is achieved with the hope to propagate it to the children in the genotypic level. This method is successfully used in the Finate State Automaton identification problem by Vanyo Slavov (vslavov@inf.nbu.bg). As far as I know he uses the principle of sexiness not only to choose mates, but also to form a multi-cellar creaturte with differentiated cells. (Where the cells are complementary expressed in a sense that each cell solves a part of the problem, but the union of the solutions of the different cells gives approximate solution to the whole problem.) A possible fitness function can give credits if the union covers larger part of the whole solution, and possibly to punish intersections. George Bilchev / -----------------------------------------------------------------\ | George@inf.nbu.bg | New Bulgarian University | | | Dept. of Computer Science | | G.Biltchev@bay.cc.kcl.ac.uk | Sofia 1125 | | (valid until 25 March) | Bulgaria | \------------------------------------------------------------------/ From genetic-programming-owner@list.Stanford.EDU Sun Feb 27 14:53:28 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA12683; Sun, 27 Feb 94 14:53:17 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Fri, 25 Feb 94 18:33 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id NAA05109 for ; Fri, 25 Feb 1994 13:46:57 -0800 Received: from dmc.com (HULK.DMC.COM) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA26635; Fri, 25 Feb 1994 13:45:38 -0800 Received: from oak by DMC.COM (MX V3.3 VAX) with UUCP; Fri, 25 Feb 1994 16:42:16 EST Received: by adapt.com (4.1/SMI-4.1) id AA26226; Fri, 25 Feb 94 16:22:01 EST Resent-Date: Sat, 26 Feb 94 01:04 EDT Date: Fri, 25 Feb 94 16:22:01 EST From: kinnear@adapt.COM Subject: RE: Diversity and sexiness in GA/GP Resent-To: lee@neural.hampshire.EDU To: dudeyp@chert.CS.ORST.EDU, keithm@icd.ab.COM Cc: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <56341E78C65F02AE28@hamp.hampshire.edu> Message-Id: <9402252122.AA26226@adapt.com> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: dudeyp@chert.CS.ORST.EDU, keithm@icd.ab.COM X-Vms-Cc: genetic-programming@cs.stanford.EDU Status: O > From thehulk!icd.ab.com!keithm Fri Feb 25 12:27:17 1994 > Date: Fri, 25 Feb 1994 09:01:55 -0500 > From: "Mike J. Keith" > To: dudeyp@chert.CS.ORST.EDU > Subject: Re: Diversity and sexiness in GA/GP > Cc: genetic-programming@cs.stanford.edu > Content-Length: 1296 > > >In other words, an individual is sexy to you to the extent that it > >does better than you on the test cases. The formula might be changed > >to sum-of-squares to increase the relative sexiness of individuals > >that vastly outperform you in some areas. > > This is an interesting idea. The way I look at it is that your looking at > a "fitness-profile" instead of just a single value fitness. I too think that this is a good idea. > > However, I think it makes more sense to me for "sexiness" to increase > based on the opposites attract premise. That is, an individual will > desire others whos profile is good but UNIQUE from his own. > > So if you have 3 individuals A, B, and C where A is looking for a > mate. Even if B's raw fitness is better than C's, A will desire C if > C's profile is unique enough - hey I would rather kiss a stranger than > my sister even if my sister is more attractive: > > Sexiness = C1*rawFitness + C2*Uniqueness Given that uniqueness is defined as "fitness uniqueness", not structural uniqueness, then I think that you both are looking at a similar measure. In Peter's approach, seems to me that it is more likely that the mate selected will do well where you do poorly (relative to the average), and less likely that it will do fantastically better than average where you do lots better than the average. That is what the concept of average is all about. I think that adding the C1*rawFitness term just covers you for the case where the first individual (that desiring a mate) has low basic raw fitness. Then, Peter's approach would allow selection of a mate which was also low fitness but somewhat better than the first, and Mike's wouldn't. > > Where uniqueness is based on the sum of squares of differences over the > test case profile as Peter mentioned. The second term above will take more > effect later in the run. > > >My prediction is that this will increase > >diversity, and possibly provide additional benefits by bringing > >together mutually beneficial subsolutions. > > Yeah it seems like thats what the fitness-vector or profile concept > could buy you. > > Mike > > Peter Dudey also says: > > I don't have any demes or the like in mind, so everyone is a potential > mate. Yes, but that is exactly what you are creating. Using these sorts of fitness functions creates demes out of your selection algorithm, but they are not spacial demes. Cheers -- Kim From genetic-programming-owner@list.Stanford.EDU Sun Feb 27 19:43:43 1994 Return-Path: Received: from hamp by neural.hampshire.EDU (4.1/SMI-4.1) id AB13842; Sun, 27 Feb 94 19:43:41 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Fri, 25 Feb 94 20:57 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id QAA06250 for ; Fri, 25 Feb 1994 16:30:46 -0800 Received: from research.CS.ORST.EDU (chert.CS.ORST.EDU) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA04804; Fri, 25 Feb 1994 16:29:37 -0800 Received: from hume.CS.ORST.EDU by research.CS.ORST.EDU (4.1/1.30) id AA18339; Fri, 25 Feb 94 16:28:00 PST Received: by hume.CS.ORST.EDU (4.1/CS-Client) id AA20027; Fri, 25 Feb 94 16:28:00 PST Resent-Date: Sun, 27 Feb 94 16:27 EDT Date: Fri, 25 Feb 94 16:28:00 PST From: dudeyp@chert.CS.ORST.EDU Subject: Diversity and sexiness in GA/GP Resent-To: lee@neural.hampshire.EDU To: kinnear@adapt.COM Cc: keithm@icd.ab.COM, genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <54E9ED1B901F02CA3A@hamp.hampshire.edu> Message-Id: <9402260028.AA20027@hume.CS.ORST.EDU> In-Reply-To: 's message of Fri, 25 Feb 94 16:22:01 EST <9402252122.AA26226@adapt.com> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: kinnear@adapt.COM X-Vms-Cc: keithm@icd.ab.COM, genetic-programming@cs.stanford.EDU Status: RO > Date: Fri, 25 Feb 94 16:22:01 EST > From: > > > Peter Dudey also says: > > > > I don't have any demes or the like in mind, so everyone is a potential > > mate. > > Yes, but that is exactly what you are creating. Using these > sorts of fitness functions creates demes out of your selection > algorithm, but they are not spacial demes. I suppose, but in a very strange way, because sexiness is not quite symmetric. (As in life...) Would it be redundant to try to match up two individuals that both found each other sexy? Hoo boy, I've opened up a real can of worms here, haven't I? :) /~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\ \ Peter Dudey, MS student in Artificial Intelligence, Oregon State University / / dudeyp@research.cs.orst.edu : hagbard on IGS : 257 NE 13th, Salem, OR 97301 \ \ "We feel confident that there is a 4-line LISP hack for consciousness." / ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ From genetic-programming-owner@list.Stanford.EDU Sun Feb 27 19:48:49 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA13884; Sun, 27 Feb 94 19:48:47 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Fri, 25 Feb 94 21:57 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id RAA06516 for ; Fri, 25 Feb 1994 17:27:45 -0800 Received: from wpo.borland.com by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA06603; Fri, 25 Feb 1994 17:26:41 -0800 Received: from Borland-Message_Server by wpo.borland.com with WordPerfect_Office; Fri, 25 Feb 1994 16:42:20 -0800 Resent-Date: Sun, 27 Feb 94 16:00 EDT Date: Fri, 25 Feb 1994 16:38:52 -0800 From: smaxwell@wpo.borland.COM Subject: Diversity and sexiness in GA/GP Resent-To: lee@neural.hampshire.EDU To: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <54EDAF9F10FF02CA3A@hamp.hampshire.edu> Message-Id: X-Mailer: WordPerfect Office 4.0 X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: genetic-programming@cs.stanford.EDU Status: RO Just to add in my $0.02... What if we were to combine the sexiness idea with the order-2 tournaments idea (sorry, forgot the reference): For each paring, conduct n sets of m [normal] fitness tournaments, resuling in n winners. Compute the distance* between each pair (n taken 2 at a time). The pair with the largest distance get to fool around. Every winner is, by definition, of high fitness. Large distance insures that each of the pair has something the other could use (opposites attract), and encourages (or at least capitalizes) diversity. The results of such pairings are likely to be more diverse, too, I think. We're as likely to get a genius with high scores from both parents as a idiot with low scores from both. -+- Sid * Distance here is the sum of squares difference per fitness case. From genetic-programming-owner@list.Stanford.EDU Sun Feb 27 19:42:49 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA13831; Sun, 27 Feb 94 19:42:41 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Sun, 27 Feb 94 14:29 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id KAA15643 for ; Sun, 27 Feb 1994 10:08:54 -0800 Received: from research.CS.ORST.EDU (chert.CS.ORST.EDU) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA16132; Sun, 27 Feb 1994 10:07:50 -0800 Received: from hume.CS.ORST.EDU by research.CS.ORST.EDU (4.1/1.30) id AA12729; Sun, 27 Feb 94 10:07:48 PST Received: by hume.CS.ORST.EDU (4.1/CS-Client) id AA00653; Sun, 27 Feb 94 10:07:48 PST Resent-Date: Sun, 27 Feb 94 16:39 EDT Date: Sun, 27 Feb 94 10:07:48 PST From: dudeyp@chert.CS.ORST.EDU Subject: Diversity and sexiness in GA/GP Resent-To: lee@neural.hampshire.EDU To: smaxwell@wpo.borland.COM Cc: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <54E8434017BF02D51D@hamp.hampshire.edu> Message-Id: <9402271807.AA00653@hume.CS.ORST.EDU> In-Reply-To: smaxwell@wpo.borland.com's message of Fri, 25 Feb 1994 16:38:52 -0800 X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: smaxwell@wpo.borland.COM X-Vms-Cc: genetic-programming@cs.stanford.EDU Status: RO > Date: Fri, 25 Feb 1994 16:38:52 -0800 > From: smaxwell@wpo.borland.com > > What if we were to combine the sexiness idea with the order-2 > tournaments idea (sorry, forgot the reference): > > For each paring, conduct n sets of m [normal] fitness tournaments, > resuling in n winners. Compute the distance* between each pair (n > taken 2 at a time). The pair with the largest distance get to fool around. That sounds very similar to Mike Keith's sexiness formula. I don't suppose there's any way you could find that reference, is there? > Every winner is, by definition, of high fitness. Large distance insures > that each of the pair has something the other could use (opposites > attract), and encourages (or at least capitalizes) diversity. Won't idiot savants (just the sort of individual with which an absent-minded professor would want to breed, genetically speaking) be culled out by the original tournaments? > The results of such pairings are likely to be more diverse, too, I think. > We're as likely to get a genius with high scores from both parents as a > idiot with low scores from both. How? If both parent were idiots, how would they get past the tournaments? > * Distance here is the sum of squares difference per fitness case. /~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\ \ Peter Dudey, MS student in Artificial Intelligence, Oregon State University / / dudeyp@research.cs.orst.edu : hagbard on IGS : 257 NE 13th, Salem, OR 97301 \ \ "We feel confident that there is a 4-line LISP hack for consciousness." / ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ From genetic-programming-owner@list.Stanford.EDU Sun Feb 27 22:48:40 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA14789; Sun, 27 Feb 94 22:48:38 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Sun, 27 Feb 94 21:31 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id QAA17339 for ; Sun, 27 Feb 1994 16:59:44 -0800 Received: from nxsci245.mrs.umn.edu by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA22140; Sun, 27 Feb 1994 16:58:40 -0800 Received: by nxsci245.mrs.umn.edu (NeXT-1.0 (From Sendmail 5.52)/NeXT-2.0) id AA01613; Sun, 27 Feb 94 18:48:02 CST Received: by NeXT Mailer (1.63) Resent-Date: Sun, 27 Feb 94 21:50 EDT Date: Sun, 27 Feb 94 18:48:02 CST From: mcphee@nxsci245.mrs.umn.EDU Subject: RE: Diversity and sexiness in GA/GP Resent-To: lee@neural.hampshire.EDU To: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <54BCEA25A21F02E65F@hamp.hampshire.edu> Message-Id: <9402280048.AA01613@nxsci245.mrs.umn.edu> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: genetic-programming@cs.stanford.EDU Status: O Since no one appears to have mentioned this yet, I thought I'd point out that there's an interesting article on the subject of diversity in the 2nd issue of _Evolutionary Computation_: "Searching for diverse, cooperative populations with genetic algorithms", by Smith, Forrest, and Perelson This is then (sort of) followed up in the next issue. Note that while they're working with GA's, the idea (summarized below) could be easily applied to GP as well. The idea in a nutshell: When it comes time to compute fitnesses, repeatedly 0. Select a certain number (say sigma) of individuals 1. Select a fitness case 2. Compute the fitness of each of the sigma individuals on this case 3. Reward the best of the lot by adding its score to its current fitness The diversity of the population is controlled by the value of sigma. If sigma is 1, then you have plain vanilla GA/GP. If sigma is equal to the size of the population, you get a whole pile of subpopulations, each of whose size is proportional to fitness at that hill. Thus if you have two equally sized hills, you'd expect two subpopulations of equal size. For values of sigma in between, you get a progressively smaller number of subpopulations. I played with it a bit in a GA context, and found it worked quite nicely without being overly expensive (some of the hamming difference difference approaches are O(N^2)). Nic McPhee mcphee@cda.mrs.umn.edu University of Minnesota, Morris From genetic-programming-owner@list.Stanford.EDU Mon Feb 28 05:10:08 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA15024; Mon, 28 Feb 94 05:10:07 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Mon, 28 Feb 94 05:10 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id AAA19039 for ; Mon, 28 Feb 1994 00:05:56 -0800 Received: from netcomsv.netcom.com (uucp2-b.netcom.com) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA05480; Mon, 28 Feb 1994 00:04:48 -0800 Received: from red.com by netcomsv.netcom.com with UUCP (8.6.4/SMI-4.1) id XAA11188; Sun, 27 Feb 1994 23:31:08 -0800 Received: by red.com (920330.SGI/921111.SGI.AUTO.ANONFTP) for @netcomsv:forrest@cs.unm.edu id AA01092; Sun, 27 Feb 94 23:28:05 -0800 Resent-Date: Mon, 28 Feb 94 05:10 EDT Date: Sun, 27 Feb 1994 23:28:02 -0800 From: cwr@red.COM Subject: RE: Diversity and sexiness in GA/GP Resent-To: lee@neural.hampshire.EDU To: mcphee@nxsci245.mrs.umn.EDU Cc: genetic-programming@cs.stanford.EDU, forrest@cs.unm.EDU, cwr@red.COM Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <547F5D16429F02ED41@hamp.hampshire.edu> Message-Id: <9402272328.ZM1090@red.com> In-Reply-To: <9402280048.AA01613@nxsci245.mrs.umn.edu> X-Mailer: Z-Mail (2.1.4 02apr93) X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: mcphee@nxsci245.mrs.umn.EDU X-Vms-Cc: genetic-programming@cs.stanford.EDU, forrest@cs.unm.EDU, cwr@red.COM Status: O Date: Sun, 27 Feb 94 18:48:02 CST From: mcphee@nxsci245.mrs.umn.edu (Nic McPhee) Since no one appears to have mentioned this yet, I thought I'd point out that there's an interesting article on the subject of diversity in the 2nd issue of _Evolutionary Computation_: "Searching for diverse, cooperative populations with genetic algorithms", by Smith, Forrest, and Perelson This is then (sort of) followed up in the next issue. Note that while they're working with GA's, the idea (summarized below) could be easily applied to GP as well... Thanks Nic for pointing this out. Indeed the "follow up" paper was: S. Forrest, B. Javornik, R. Smith, and A. Perelson (1993) Using Genetic Algorithms to Explore Pattern Recognition in the Immune System, _Evolutionary Computation_, 1(3), 191-211. Note that the goal there was not to maintain diversity while searching for a single solution to a problem, but to breed a cooperative POPULATION which worked as a team to solve a family of problems. That is, a collection of antibodies to fend off a collection of antigens. (Side note about the dynamics of our virtual community: When I made the connection and realized that Nic was talking about the immune system stuff, I had a vague memory of this topic coming up on the GP list before. I poked around and found what I was remembering. By an amazing coincidence, it was almost exactly one year ago, on March 2, 1993 that this came up. In a discussion about diversity (with the subject "DEMES") I mentioned that I'd recently heard Prof. Forrest talk about a GA model of the immune system but I didn't recall the details. There were some replies supplying the details from Ron Goldthwaite and Lee Altenberg, two members of the GP community who were unknown to me at the time, but who I've since come to know and respect.) From genetic-programming-owner@list.Stanford.EDU Mon Feb 28 09:21:59 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA15160; Mon, 28 Feb 94 09:21:58 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Mon, 28 Feb 94 09:20 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id EAA20142 for ; Mon, 28 Feb 1994 04:50:52 -0800 Received: from odin.icd.ab.com by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA06298; Mon, 28 Feb 1994 04:49:43 -0800 Received: from gadwal.icd.ab.com (gadwal.icd.ab.com [130.151.132.71]) by odin.icd.ab.com (8.1C/5.6) with SMTP id HAA03264; Mon, 28 Feb 1994 07:49:37 -0500 Resent-Date: Mon, 28 Feb 94 09:21 EDT Date: Mon, 28 Feb 1994 07:49:37 -0500 From: "Mike J. Keith" Subject: RE: Diversity and sexiness in GA/GP Resent-To: lee@neural.hampshire.EDU To: mcphee@nxsci245.mrs.umn.EDU Cc: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <545C47328D3F030071@hamp.hampshire.edu> Message-Id: <199402281249.HAA03264@odin.icd.ab.com> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: mcphee@nxsci245.mrs.umn.EDU X-Vms-Cc: genetic-programming@cs.stanford.EDU Status: RO >The diversity of the population is controlled by the value of sigma. >If sigma is 1, then you have plain vanilla GA/GP. If sigma is equal >to the size of the population, you get a whole pile of >subpopulations, each of whose size is proportional to fitness at that >hill. Thus if you have two equally sized hills, you'd expect two >subpopulations of equal size. For values of sigma in between, you >get a progressively smaller number of subpopulations. This is a cool idea and is similar in some ways to the sexiness concept. However, it seems that you would end up with a lot of individuals who are only good for one test point. You would end up perhaps overfiting the problem. In addition, this concept smells more like a classifier system to me. Your solution is not an individual but a collection of individuals. In GP, its nice to look at the solution program in one individual. Nick, how do they compbine the individuals together so that they know the "group-solution" is doing ?? Mike From genetic-programming-owner@list.Stanford.EDU Fri Feb 25 16:34:59 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA03930; Fri, 25 Feb 94 16:34:45 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Fri, 25 Feb 94 16:14 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id LAA04370 for ; Fri, 25 Feb 1994 11:34:39 -0800 Received: from bay.cc.kcl.ac.uk by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA21046; Fri, 25 Feb 1994 11:33:30 -0800 Received: by bay.cc.kcl.ac.uk (MX V3.3 VAX) id 22550; Fri, 25 Feb 1994 19:35:53 EST Resent-Date: Fri, 25 Feb 94 16:19 EDT Date: Fri, 25 Feb 1994 19:35:41 EST From: udue074@bay.cc.kcl.AC.UK Subject: RE: Diversity and sexiness in GA/GP Resent-To: lee@neural.hampshire.EDU To: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <567D7178723F02D81E@hamp.hampshire.edu> Message-Id: <0097A99D.F7B1E6E0.22550@bay.cc.kcl.ac.uk> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: genetic-programming@cs.stanford.EDU Status: RO >I have an idea for a somewhat related scheme that would, I think, work >for GP as well. It requires that the fitness test involve a number of >"test cases", where fitness is the sum of an individual's success over >these cases. >Measure fitness for each individual for each test case. More fit >individuals are more likely to breed, as usual, but you only select >one individual to breed, and that individual chooses it's mate. The >mate is chosen, either deterministically or stochastically, according >to "sexiness", where: > __ > \ >sexiness = > success ( potential-mate ) - success (self) > /_ > n > >and n is the number of cases in the fitness test. > > >In other words, an individual is sexy to you to the extent that it >does better than you on the test cases. The formula might be changed >to sum-of-squares to increase the relative sexiness of individuals >that vastly outperform you in some areas. I would like to specify the idea of sexiness in the following way: "an individual is sexy to you to the extent that it does better than you" on the part of the cases on which you are especially poor. In this way a complementarity of phenotype is achieved with the hope to propagate it to the children in the genotypic level. This method is successfully used in the Finate State Automaton identification problem by Vanyo Slavov (vslavov@inf.nbu.bg). As far as I know he uses the principle of sexiness not only to choose mates, but also to form a multi-cellar creaturte with differentiated cells. (Where the cells are complementary expressed in a sense that each cell solves a part of the problem, but the union of the solutions of the different cells gives approximate solution to the whole problem.) A possible fitness function can give credits if the union covers larger part of the whole solution, and possibly to punish intersections. George Bilchev / -----------------------------------------------------------------\ | George@inf.nbu.bg | New Bulgarian University | | | Dept. of Computer Science | | G.Biltchev@bay.cc.kcl.ac.uk | Sofia 1125 | | (valid until 25 March) | Bulgaria | \------------------------------------------------------------------/ From genetic-programming-owner@list.Stanford.EDU Mon Feb 28 17:57:32 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA16064; Mon, 28 Feb 94 17:57:28 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Mon, 28 Feb 94 14:55 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id JAA00169 for ; Mon, 28 Feb 1994 09:31:57 -0800 Received: from sun2.nsfnet-relay.ac.uk by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA06132; Mon, 28 Feb 1994 09:30:51 -0800 Received: by isis.sunderland.ac.uk (4.1/SMI-4.1) id AA02741; Mon, 28 Feb 94 16:33:47 GMT Resent-Date: Mon, 28 Feb 94 16:48 EDT Date: Mon, 28 Feb 1994 16:33:47 +0000 (GMT) From: cs0ral@isis.sunderland.AC.UK Subject: no subject (file transmission) Resent-To: lee@neural.hampshire.EDU To: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <541DD360C6DF03254F@hamp.hampshire.edu> Message-Id: <9402281633.AA02741@isis.sunderland.ac.uk> Via: uk.ac.sunderland.consgate; Mon, 28 Feb 1994 16:34:53 +0000 Via: isis.sunderland.ac.uk (isis.sund.ac.uk); Mon, 28 Feb 1994 16:32:39 +0000 X-Mailer: ELM [version 2.4 PL22] Content-Type: text Content-Length: 6517 X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: genetic-programming@cs.stanford.EDU Status: RO > >The diversity of the population is controlled by the value of sigma. > >If sigma is 1, then you have plain vanilla GA/GP. If sigma is equal > >to the size of the population, you get a whole pile of > >subpopulations, each of whose size is proportional to fitness at that > >hill. Thus if you have two equally sized hills, you'd expect two > >subpopulations of equal size. For values of sigma in between, you > >get a progressively smaller number of subpopulations. > > This is a cool idea and is similar in some ways to the sexiness > concept. However, it seems that you would end up with a lot of > individuals who are only good for one test point. You would end > up perhaps overfiting the problem. What about this?. For every individual select those case tests where the individual is good (for instance, if fm is the worst fitness of a individual and fM is the best (I am talking of fitnesses for single case test) then select those case tests where fM-f(individual,case test)<(fM-fm)/2 ). Then perform reproduction and crossover taking into account the fitness only for those selected case tests. Do this for each individual except for those individuals whose case test group has already been considered. By doing this you are dividing the case test set in problem subsets (subproblems) and evaluating all the individuals inside those subsets. This way you are making sure you don't loose individuals which are good for certain parts of the problem but not good in general. Note that problem subsets are formed dynamically (The only constant the user is selecting is 1/2). Also, individuals will tend to breed with other individuals which are good at the same problem subset solving the problem of mixing very different individuals. Now you have the problem of what individuals must be rejected. I think that those individuals which are not neccessary (i.e., if we reject them, any of the problem subsets will loose a top-fit individual). For doing this, we rank individuals for each problem subset and assign 1 point to the individual in the top, 2 points to the second, and so on. The total number of points for each individual will be the number of points obtained in subset1 plus points in subset2 and so on. This way, the individuals which are at the bottom in many subsets (i.e. they have got many points) will be rejected (no matter they are very fit) and therefore maintaining diversity. I am not saying it is good to reject very fit individuals. If you want to maintain a lot of very fit individuals in a problem subset, then you have to increase your total population. > > In addition, this concept smells more like a classifier system to > me. Your solution is not an individual but a collection of > individuals. In GP, its nice to look at the solution program > in one individual. With the difference that classifiers are using non-genetic self-organisation (i.e., the bucket brigade algorithm). With the idea I proposed above I expect that situations like the following will happen: Ind1 is good in problem subset P1 P2 P3 P4 (where Pi are case tests) Ind2 is good in problem subset P3 P4 P5 P6 Therefore Ind1 and Ind2 will breed together sometimes and perhaps we will get an individual which is good in P1 P2 P3 P4 P5 P6 (This is the basic idea of GP anyway). Problem subsets should tend to get bigger and bigger and eventually to solve the whole problem. On the other side, it looks that there is no real pressure for an individual to increase its problem subset size and as it is easier to solve one problem than to solve two, then what we would get would be a bunch of overspecialized individuals. But in this scheme, the only way of not being rejected is to find new niches (i.e., problem subsets). For instance, if we have: Ind1, fitness(P1)=10, fitness(Pi, i<>1)=0 Ind2, fitness(P2)=10, fitness(Pi, i<>2)=0 Ind3, fitness(P1)=6, fitness(P2)=6 In this case, Ind3 is better than Ind1 and Ind2 in subset P1, P2 although is not very good in any of them but it still would have a chance of surviving because it is the top individual of its own subset. > > Nick, how do they compbine the individuals together so that they > know the "group-solution" is doing ?? In the scheme above, I expect a combined solution to appear in a single individual. But sometimes, a problem is made of very different subproblems and the best way to combine them it is just to put them together and activate one of them depending of the problem. For instance, in nature it would be quite useful to be able to feed from earth (like plants), shit ( pardon : ) ) like fungus, meat, grass (like rabbits), etc, but you don't find any being on Earth able to do all this things at the same time (except some children, of course). Instead of, you find adapted individuals to some kind of food or you find raw combination of these individuals (like the combination of a couple of aerobic and anaerobic bacteria to form an Eucaryote cell or the combination human being-rabbit where the rabbit eats the grass and the human eats the rabbit : ) ). I think it would be a good idea to evolve a subproblem classifier (given a specific problem it gives you to what problem subset it belongs). Note that with my scheme the individuals themselves are dividing the problem space in problem subsets. Therefore, given a specific problem, you first have to determine to which problem subset this specific problem belongs and then activate the top individual for that problem subset. How to evolve a problem classifier? Perhaps, after the problem space has been clearly divided in problem subsets, another kind of evolution should take place: the individuals from the past evolution should be used as subroutines (like in an AFD scheme) and new functions to activate those subroutines should be included in the soup. The same sensor functions used by the original individuals could be included in the new soup to extract characteristics from the problem and therefore classify it. If we use an AFD scheme, the old individuals (now subroutines) would be allowed to evolve too further and further!. This has been a really long message. Perhaps I was just thinking loudly ... Hope you understand it, I know my English is not very good. Suggestions, ideas, money and spare time in supercomputers y/o parallel machines is welcome : ) Ricardo Aler Room D3A, School of Computing, Priestman Building University of Sunderland Sunderland (UK) e-mail: cs0ral@isis.sunderland.ac.uk From genetic-programming-owner@list.Stanford.EDU Mon Feb 28 21:20:44 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA16687; Mon, 28 Feb 94 21:20:40 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Mon, 28 Feb 94 15:37 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id KAA00292 for ; Mon, 28 Feb 1994 10:49:50 -0800 Received: from wpo.borland.com by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA11231; Mon, 28 Feb 1994 10:48:45 -0800 Received: from Borland-Message_Server by wpo.borland.com with WordPerfect_Office; Mon, 28 Feb 1994 10:47:26 -0800 Resent-Date: Mon, 28 Feb 94 15:40 EDT Date: Mon, 28 Feb 1994 10:44:09 -0800 From: smaxwell@wpo.borland.COM Subject: Diversity and sexiness in GA/GP Resent-To: lee@neural.hampshire.EDU To: dudeyp@chert.CS.ORST.EDU Cc: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <5427564C9EDF03254F@hamp.hampshire.edu> Message-Id: X-Mailer: WordPerfect Office 4.0 X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: dudeyp@chert.CS.ORST.EDU X-Vms-Cc: genetic-programming@cs.stanford.EDU Status: O > That sounds very similar to Mike Keith's sexiness formula. I don't > suppose there's any way you could find that reference, is there? I was refering to multiple tournaments, as described in Andy Singleton's 2-Jan message "Tournament Selection" follow up of his Pareto optimality discussion. > Won't idiot savants (just the sort of individual with which an absent- > minded professor would want to breed, genetically speaking) be culled > out by the original tournaments? Not if they'd win a tournament. An idiot savant would be more likely to win a tournament than a [plain] idiot. I'm assuming that by "idiot savant" you mean an individual who does very well at some subset of a problem, but otherwise poorly. > How? If both parent were idiots, how would they get past the > tournaments? It's unlikely that idiots would get past the tournament, which is why we use them (;-). However, idiot savants *can* get by them. Pair two of these, and you might result in a genius (gets the "savant" parts from both parents) or an idiot (gets the "idiot" parts), or anywhere in between. Ta da, diversity. > "We feel confident that there is a 4-line LISP hack for consciousness." Hey, I'd learn LISP all over again, if I can get a look at this hack! -+- Sid From genetic-programming-owner@list.Stanford.EDU Mon Feb 28 18:12:44 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA16079; Mon, 28 Feb 94 18:12:42 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Mon, 28 Feb 94 15:53 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id KAA00310 for ; Mon, 28 Feb 1994 10:58:45 -0800 Received: from research.CS.ORST.EDU (chert.CS.ORST.EDU) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA11710; Mon, 28 Feb 1994 10:57:40 -0800 Received: from hume.CS.ORST.EDU by research.CS.ORST.EDU (4.1/1.30) id AA21261; Mon, 28 Feb 94 10:57:37 PST Received: by hume.CS.ORST.EDU (4.1/CS-Client) id AA01743; Mon, 28 Feb 94 10:57:37 PST Resent-Date: Mon, 28 Feb 94 17:49 EDT Date: Mon, 28 Feb 94 10:57:37 PST From: dudeyp@chert.CS.ORST.EDU Subject: Diversity and sexiness in GA/GP Resent-To: lee@neural.hampshire.EDU To: smaxwell@wpo.borland.COM Cc: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <5415641192DF031618@hamp.hampshire.edu> Message-Id: <9402281857.AA01743@hume.CS.ORST.EDU> In-Reply-To: smaxwell@wpo.borland.com's message of Mon, 28 Feb 1994 10:44:09 -0800 X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: smaxwell@wpo.borland.COM X-Vms-Cc: genetic-programming@cs.stanford.EDU Status: O > Date: Mon, 28 Feb 1994 10:44:09 -0800 > From: smaxwell@wpo.borland.com > > > Won't idiot savants (just the sort of individual with which an absent- > > minded professor would want to breed, genetically speaking) be culled > > out by the original tournaments? > > Not if they'd win a tournament. An idiot savant would be more likely to > win a tournament than a [plain] idiot. I'm assuming that by "idiot savant" > you mean an individual who does very well at some subset of a problem, > but otherwise poorly. Yes, that's what I meant. > > How? If both parent were idiots, how would they get past the > > tournaments? > > It's unlikely that idiots would get past the tournament, which is why we > use them (;-). However, idiot savants *can* get by them. Pair two of I don't see how. Let's say there are 20 fitness test cases, each worth up to ten points, and total fitness is the sum of these scores. If you get 10 points on two of the cases, and 1 on each of the others, you'll still lose to evenly shoddy individuals who get 2 points on each case. > > "We feel confident that there is a 4-line LISP hack for consciousness." > > Hey, I'd learn LISP all over again, if I can get a look at this hack! Well, you have to load a few packages first... /~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\ \ Peter Dudey, MS student in Artificial Intelligence, Oregon State University / / dudeyp@research.cs.orst.edu : hagbard on IGS : 257 NE 13th, Salem, OR 97301 \ \ "We feel confident that there is a 4-line LISP hack for consciousness." / ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ From genetic-programming-owner@list.Stanford.EDU Mon Feb 28 18:34:18 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA16110; Mon, 28 Feb 94 18:34:14 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Mon, 28 Feb 94 17:10 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id MAA00605 for ; Mon, 28 Feb 1994 12:24:19 -0800 Received: from HPP.Stanford.EDU by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA16335; Mon, 28 Feb 1994 12:23:15 -0800 Received: from KSL-EXP-35 (KSL-EXP-35.Stanford.EDU) by HPP.Stanford.EDU (4.1/inc-1.0) id AA17407; Mon, 28 Feb 94 12:23:10 PST Resent-Date: Mon, 28 Feb 94 17:12 EDT Date: Mon, 28 Feb 94 12:22:48 PST From: James Rice Subject: RE: Diversity and sexiness in GA/GP Sender: RICE@KSL-EXP-35.Stanford.EDU Resent-To: lee@neural.hampshire.EDU To: smaxwell@wpo.borland.COM, dudeyp@chert.CS.ORST.EDU Cc: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <541A6F48B89F031618@hamp.hampshire.edu> Message-Id: <2971455768-13145305@KSL-EXP-35> In-Reply-To: X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: smaxwell@wpo.borland.COM, dudeyp@chert.CS.ORST.EDU X-Vms-Cc: genetic-programming@cs.stanford.EDU Status: O --> >"We feel confident that there is a 4-line LISP --> > hack for consciousness." --> Hey, I'd learn LISP all over again, if I can get a --> look at this hack! --> -+- Sid Actually, Mr D was just being kind to the rest of the world, who might be incredulous of the real state of affairs. Any serious Lisp hacker knows that the 4-line hack for conciousness is for wimps. There's a one-line hack for conciousness (and pizza) written in CL's format language. It starts something like (format t "~@:{~^~:[~ I forget the rest. Rice - Since we were on the subject of Lisps for CMs, I once saw the format control string for the print method for Xets (or maybe Xappings or Xectors, can't remember), I think Moon posted it on the CL mailing list ~8 years ago. Really made your eyes pop out. *** All Un/Subscribe messages should go to *** *** genetic-programming-REQUEST@cs.stanford.edu *** *** ^^^^^^^^ *** From genetic-programming-owner@list.Stanford.EDU Thu Mar 10 23:37:26 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA17868; Thu, 10 Mar 94 23:37:25 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Thu, 10 Mar 94 23:36 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id SAA21400 for ; Thu, 10 Mar 1994 18:37:24 -0800 Received: from research.CS.ORST.EDU (chert.CS.ORST.EDU) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA13663; Thu, 10 Mar 1994 18:36:19 -0800 Received: from hume.CS.ORST.EDU by research.CS.ORST.EDU (4.1/1.30) id AA01629; Thu, 10 Mar 94 18:36:06 PST Received: by hume.CS.ORST.EDU (4.1/CS-Client) id AA08357; Thu, 10 Mar 94 18:36:05 PST Resent-Date: Thu, 10 Mar 94 23:37 EDT Date: Thu, 10 Mar 94 18:36:05 PST From: dudeyp@chert.CS.ORST.EDU Subject: Sexiness: Did I have it backwards? Resent-To: lee@neural.hampshire.EDU To: hthies@willamette.EDU, ekerr@willamette.EDU, genetic-programming@cs.stanford.EDU, levenick@willamette.EDU, french@willamette.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <4C0927585F9F00B313@hamp.hampshire.edu> Message-Id: <9403110236.AA08357@hume.CS.ORST.EDU> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: hthies@willamette.EDU, ekerr@willamette.EDU, genetic-programming@cs.stanford.EDU, levenick@willamette.EDU, french@willamette.EDU Status: RO I've done some initial tests of sexiness, and the results haven't been very impressive. It doesn't seem to significantly worsen things, but it doesn't seem to significantly improve them, either. I ran the idea across Paul Cull, who may be the sole GA/GP afficionado here, and who specializes in "mathematical biology". "The idea," I explained, "is that you want to breed with someone who's good at the things you're not good at." He thought this was a terrrible idea, and suggested that one wants to breed with others that are GOOD at the same things. I'm going to give this a shot. What do you all think? I'm still on the lookout for some good problems where traditional GA/GP converges too soon, and sub-solutions might meaningfully be combined. /~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\ \ Peter Dudey, MS student in Artificial Intelligence, Oregon State University / / dudeyp@research.cs.orst.edu : hagbard on IGS : 257 NE 13th, Salem, OR 97301 \ \ I'm in favor of gun control, but it doesn't have much to do with / / crime. The vast majority of handgun deaths are suicides and accidents. \ \ / ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ From genetic-programming-owner@list.Stanford.EDU Fri Mar 11 01:07:49 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA18009; Fri, 11 Mar 94 01:07:47 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Fri, 11 Mar 94 01:01 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id UAA21490 for ; Thu, 10 Mar 1994 20:00:57 -0800 Received: from elaine32.Stanford.EDU by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA15384; Thu, 10 Mar 1994 19:59:53 -0800 Received: from localhost (phred@localhost) by elaine32.Stanford.EDU (8.6.4/8.6.4) id TAA11961; Thu, 10 Mar 1994 19:59:46 -0800 Resent-Date: Fri, 11 Mar 94 01:01 EDT Date: Thu, 10 Mar 1994 19:59:43 -0800 (PST) From: David Andre Subject: RE: Sexiness: Did I have it backwards?.. Resent-To: lee@neural.hampshire.EDU To: dudeyp@chert.CS.ORST.EDU Cc: genetic-programming@cs.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <4BFD3F117C9F00C34E@hamp.hampshire.edu> Message-Id: <199403110359.TAA11961@elaine32.Stanford.EDU> In-Reply-To: <9403110236.AA08357@hume.CS.ORST.EDU> from "Peter Dudey" at Mar 10, 94 06:36:05 pm X-Mailer: ELM [version 2.4 PL21] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 448 X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: dudeyp@chert.CS.ORST.EDU X-Vms-Cc: genetic-programming@cs.Stanford.EDU Status: RO I think that this is a wash -- in order to really know who one program *should* mate with, you need to know 1) what they are good at, 2) if they are 'perfect' on those things that they are good at, and 3) where to do crossover so as to salvage the things they are good at. GP 'rule-sets' are not like individual rules perhaps sexiness works better in classifier (like) systems that have multiple sets of 'rules' per individual... David Andre From genetic-programming-owner@list.Stanford.EDU Sat Mar 12 12:47:28 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA20942; Sat, 12 Mar 94 12:47:27 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Sat, 12 Mar 94 12:47 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id IAA23765 for ; Sat, 12 Mar 1994 08:05:34 -0800 Received: from worldlink.worldlink.com (worldlink.com) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA12620; Sat, 12 Mar 1994 08:04:30 -0800 Received: by worldlink.worldlink.com (5.65b/4.0.071791-Worldlink) id AA10517; Sat, 12 Mar 94 11:04:33 -0500 Resent-Date: Sat, 12 Mar 94 12:47 EDT Date: Fri, 11 Mar 94 10:09:58 -0500 From: Andrew Singleton Subject: RE: Sexiness: Did I have it backwards? Resent-To: lee@neural.hampshire.EDU To: GP list Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <4AD193B3453F00E868@hamp.hampshire.edu> Message-Id: <2972482234.0.p00396@psilink.com> In-Reply-To: <9403111849.AA20959@Xenon.Stanford.EDU> Organization: Creation Mechanics X-Mailer: PSILink-DOS (3.4) X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: GP list Status: RO The issue of combining good subsolutions is an important one, but we may have looked at it the wrong way. I suggest a more productive line of study below. Experimental evidence shows that combining very different individuals through crossover is a recipe for failure. I wrote to Peter Dudley and suggested this might be the case, and he discovered the same experimentally. Studies of "deme" based massively parallel genetic algorithms demonstrate this principle graphically. The boundaries between the demes are always marked with "lethal" failed crosses. A biologist pointed out to me that the "hybrid vigor" is almost exclusively a phenomenon of highly inbred domestic crops. In robust wild species, hybridization rarely produces a good result. GP runs produce populations of similar trees which can cross successfully. This homogenization is a critical part of the GP process, since if you crossed random trees, your results would be very poor. In fitness space, the GP run smooths the space with respect to crossover. This necessarily produces specialization. In nature, this is called speciation. One way to look at this is that populations evolve, rather than individuals. Some very experienced GPers (Walter Tackett, Peter Angeline, and others) have gone on record favoring small populations. There is a reason for this: Small populations have more genetic drift than large populations, and have the possibility of wandering off a local optima. Interestingly, the biological hypothesis of "punctuated equilibrium" relies on exactly this mechanism. Big populations demonstrate an equilibrium. Small, isolated populations gain some new fitness attributes, and then they invade the range of the original population and wipe it out in a "punctuated" event. Interbreeding is not an important mechanism. Speciation is a big irritation in GP, since it is very difficult to combine good solutions from one run with good solutions in another run. This brings us back to the original question: How do we combine two partial solutions to make a better solution? The answer to this question is in many ways the holy grail of GP. If we can anwer it, we will have the answer to the efficiency problem - We can start with pre-evolved libraries, rather than running everything from scratch - and the all important hierarchy question - How do we combine parts (subroutines) to make a more complex whole? We know one thing. The answer is NOT subtree crossover. Some possibilities have been proposed: 1) A classifier type cooperating set of GP individuals; 2) Evolving or explicitly constructing a hierarchy of pre-evolved individuals, based on parcelling out fitness cases. As was pointed out, the bidding process for a classifier system is just a way of evolving this case by case hierarchy, so these solutions are very similar. There are other mechanisms. I have been working on my own solution for this problem, and I look forward to hearing more suggestions. From genetic-programming-owner@list.Stanford.EDU Mon Mar 14 17:46:54 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA26684; Mon, 14 Mar 94 17:46:53 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Mon, 14 Mar 94 16:15 EDT Received: from Xenon.Stanford.EDU (Xenon.Stanford.EDU [36.28.0.25]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id KAA26244 for ; Mon, 14 Mar 1994 10:40:09 -0800 Received: by Xenon.Stanford.EDU (5.61+IDA/25-CS-eef) id AA20820; Mon, 14 Mar 94 10:38:51 -0800 Resent-Date: Mon, 14 Mar 94 16:16 EDT Date: Mon, 14 Mar 1994 10:38:50 -0800 (PST) From: Patrik D'haeseleer Subject: RE: Sexiness: Did I have it backwards? Resent-To: lee@neural.hampshire.EDU To: p00396@psilink.COM Cc: genetic-programming@CS.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <492216740BFF00C22F@hamp.hampshire.edu> Message-Id: <9403141838.AA20820@Xenon.Stanford.EDU> In-Reply-To: <2972482234.0.p00396@psilink.com> from "Andrew Singleton" at Mar 11, 94 10:09:58 am X-Mailer: ELM [version 2.4 PL21] Content-Type: text Content-Length: 1571 X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: p00396@psilink.COM X-Vms-Cc: genetic-programming@CS.Stanford.EDU Status: RO Andrew Singleton writes: > >A biologist pointed out to me that the "hybrid vigor" is almost >exclusively a phenomenon of highly inbred domestic crops. In robust >wild species, hybridization rarely produces a good result. > >GP runs produce populations of similar trees which can cross >successfully. This homogenization is a critical part of the GP process, >since if you crossed random trees, your results would be very poor. How about trying to cross individuals which are *genotypically* similar, but *phenotypically* different? I know, there's usually a correlation between the two, but there's still plenty of variation. What I propose is to have a genotypical distance measure G next to the phenotypical distance P (what we used to call sexiness previously), and to combine these two into a new sexiness measure S. For instance using S = P/G, or S = P - cG, or maybe a variant of any of the multi-objective optimisation techniques described on this newsgroup earlier. G should be a structural distance measure that's reasonably fast to calculate (since we'll have to calculate several of these for each crossover). This would prevent us from choosing two radically different structured individuals for crossover, even though they may seem good candidates for recombination because they solve complimentary parts of the fitness cases. On the other hand, it should also save us the trouble of crossing over nearly identical individuals, if they solve almost the same fitness cases and are therefore not very likely to yield any new solutions. Patrik From genetic-programming-owner@list.Stanford.EDU Mon Mar 14 18:05:24 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA26737; Mon, 14 Mar 94 18:05:23 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Mon, 14 Mar 94 17:22 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id LAA26338 for ; Mon, 14 Mar 1994 11:05:52 -0800 Received: from lightstream.LightStream.COM by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA07762; Mon, 14 Mar 1994 11:04:47 -0800 Received: from cockatrice.LightStream.COM by lightstream.LightStream.COM (4.1/SMI-4.1) id AA22918; Mon, 14 Mar 94 14:04:45 EST Received: by cockatrice.LightStream.COM (4.1/SMI-4.1) id AA15232; Mon, 14 Mar 94 14:04:42 EST Resent-Date: Mon, 14 Mar 94 18:02 EDT Date: Mon, 14 Mar 1994 14:04:42 -0500 From: Dave Faulkner Subject: RE: Sexiness: Did I have it backwards? Resent-To: lee@neural.hampshire.EDU To: Andrew Singleton Cc: GP list , dfaulkne@LightStream.COM Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <49132C71287F01436B@hamp.hampshire.edu> Message-Id: <9403141904.AA15232@cockatrice.LightStream.COM> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: Andrew Singleton X-Vms-Cc: GP list , dfaulkne@LightStream.COM Status: RO In a previous note to Andrew Singleton I wrote: of course, this "homogenization" must hapen at the beginning of any run, and is what happens (semi)independently and simultaneously in all demes or tag regions. Each deme (implemented via tagging, spatially or other mechanism) is a small sub-population that has the possibility of evolving a separate species that performs well. It is true that a snake does much better in some environments than a monkey and vice versa and to cross them makes no sense. But it does make sense to cross species that are "close" in some sense. I haven't read enough about demes to know if this has been tried, but it would seem that, instead of imposing an arbitrary structural distance between demes, that a dynamic structure be imposed on the subpopulation based on some type of species distance metric: situate the chimpanzee deme "near" the gorilla deme to encourage cross-breeding; allow that relationship to vary based on a metric of structural distance among/across the deme members. In particular: instead of imposing an arbitrary structural distance between demes, that a dynamic structure be imposed on the subpopulation based on some type of species distance metric: Should read: instead of imposing an arbitrary structural distance between demes, that a dynamic structure be imposed on the deme structure based on some type of species distance ^^^^^^^^^^^^^^ metric: That is, we measure some aggragate (average?) distance between the demes (probably after some speciation has taken place) and then create a relationship between the demes based on this metric, giving probablistic encouragement to deme invasion (is this the term?) among "near" demes so as to avoid fatal crossings of too dissimilar beings. Forgive me if this doesn't clear things up a bit. (I have to learn to proof read things a few minutes after writing them.) - Dave Faulkner From genetic-programming-owner@list.Stanford.EDU Mon Mar 14 17:36:39 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA26637; Mon, 14 Mar 94 17:36:37 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Mon, 14 Mar 94 16:35 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id LAA26419 for ; Mon, 14 Mar 1994 11:58:13 -0800 Received: from penguin.mcs.utulsa.edu by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA10733; Mon, 14 Mar 1994 11:57:09 -0800 Received: from puffin.mcs.utulsa.edu by penguin.mcs.utulsa.edu (5.0/SMI-SVR4) id AA00678; Mon, 14 Mar 94 13:53:39 CST Resent-Date: Mon, 14 Mar 94 17:17 EDT Date: Mon, 14 Mar 94 13:53:39 CST From: corcoran@penguin.mcs.utulsa.EDU Subject: RE: Sexiness: Did I have it backwards? Resent-To: lee@neural.hampshire.EDU To: dudeyp@chert.CS.ORST.EDU Cc: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <49197F2DD35F01463D@hamp.hampshire.edu> Message-Id: <9403141953.AA00678@penguin.mcs.utulsa.edu> X-Sun-Charset: US-ASCII Content-Length: 2041 X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: dudeyp@chert.CS.ORST.EDU X-Vms-Cc: genetic-programming@cs.stanford.EDU Status: RO > I've done some initial tests of sexiness, and the results haven't been > very impressive. It doesn't seem to significantly worsen things, but > it doesn't seem to significantly improve them, either. > > I ran the idea across Paul Cull, who may be the sole GA/GP afficionado > here, and who specializes in "mathematical biology". "The idea," I > explained, "is that you want to breed with someone who's good at the > things you're not good at." > > He thought this was a terrrible idea, and suggested that one wants to > breed with others that are GOOD at the same things. > > I'm going to give this a shot. What do you all think? This is similar to Goldberg's observations on pp. 186-189 in his book. He was commenting on the need for mating restriction on a bimodal function. However, I suspect the tables may be turned on other fitness landscapes. > I'm still on the lookout for some good problems where traditional > GA/GP converges too soon, and sub-solutions might meaningfully be > combined. One such problem is two-dimensional bin packing (aka. multiprocessor scheduling, etc.). As the problem size is increased, it is difficult for the GA to find the optimal. However, sub-solutions, such as optimally filled bins, can be preserved with improved results. In fact, the improved results can often be found with less total effort. If you are interested, I can send you some tech reports. > /~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\ > \ Peter Dudey, MS student in Artificial Intelligence, Oregon State University / > / dudeyp@research.cs.orst.edu : hagbard on IGS : 257 NE 13th, Salem, OR 97301 \ > \ I'm in favor of gun control, but it doesn't have much to do with / > / crime. The vast majority of handgun deaths are suicides and accidents. \ > \ / > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Regards, Art Corcoran corcoran@penguin.mcs.utulsa.edu From genetic-programming-owner@list.Stanford.EDU Mon Mar 14 17:58:21 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA26702; Mon, 14 Mar 94 17:58:19 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Mon, 14 Mar 94 17:51 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id NAA26513 for ; Mon, 14 Mar 1994 13:07:00 -0800 Received: from penguin.mcs.utulsa.edu by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA14419; Mon, 14 Mar 1994 13:05:55 -0800 Received: from puffin.mcs.utulsa.edu by penguin.mcs.utulsa.edu (5.0/SMI-SVR4) id AA00721; Mon, 14 Mar 94 15:02:43 CST Resent-Date: Mon, 14 Mar 94 17:55 EDT Date: Mon, 14 Mar 94 15:02:43 CST From: corcoran@penguin.mcs.utulsa.EDU Subject: RE: Sexiness: Did I have it backwards? Resent-To: lee@neural.hampshire.EDU To: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <4914406AE09F01581B@hamp.hampshire.edu> Message-Id: <9403142102.AA00721@penguin.mcs.utulsa.edu> X-Sun-Charset: US-ASCII Content-Length: 3043 X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: genetic-programming@cs.stanford.EDU Status: O > ** Andrew Singleton writes: > > >Experimental evidence shows that combining very different individuals > >through crossover is a recipe for failure. I wrote to Peter Dudley and > >suggested this might be the case, and he discovered the same > >experimentally. Studies of "deme" based massively parallel genetic > >algorithms demonstrate this principle graphically. The boundaries > >between the demes are always marked with "lethal" failed crosses. > > ok, I'll buy that: if you cross a snake with a monkey you get an animal that > does poorly in any environment. Combining a chimpanzee with a gorilla though > might give you a new type of primate that does quite well - a new species. > Isn't one of the qualities of a species is that a member of one species > can't viably mate with the member of another species? I think this analogy with nature does not apply in general to GA/GP unless the goal is to precisely model nature. I'm more interested in obtaining good approximations to hard problems than to modeling nature in this way. The reason that a monkey cannot mate with a snake is because of the incompatibility of the genetic material, NOT because of poorly performing offspring. This may be due to a hidden tendency of a species for self-preservation of the species which is independent of natural selection. That is, prevention of cross "fertilability" of similar species helps to preserve each species intact. It is natural selection which determines which species will survive. Maintaining a diverse population helps a particular species to adapt easily to a changing environment. However, the diversity of a species has no effect on the performance/adapibility of another species, does it? In general, GA/GP models a population which would be analogous to the single species idea. I have found that people will argue for either side of the "diversity" argument: either preserve diversity as in a generational model so that exploration is enhanced, or use a high selection pressure as in the steady-state model to quickly exploit the existing genetic material. Either model does well for different problems. I have yet to see any solid work showing one to be better in all cases (although I welcome any such references). Isn't this the same as arguing over how "sexiness" can help the search? Intuitively, I think that the best "sexiness" strategy depends on the problem. Ideally, there should be a problem-independent way to tell the GA/GP the correct problem-dependent "sexiness" measure. Note, most likely, the reason for so many "lethals" at the deme boundaries on a cellular GA is due to the demes being at local minima/maxima. Thus, offspring rarely outperform the parents. However, it is at this boundary that new high performing (emergent) demes appear! It may just be that the "good" offspring are more than one crossover operation away from the current best. Regards, Art "I-have-my-asbestos-underwhere-on-so-I'm-ready-for-flames" Corcoran From genetic-programming-owner@list.Stanford.EDU Mon Mar 14 18:05:15 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA26732; Mon, 14 Mar 94 18:05:14 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Mon, 14 Mar 94 17:59 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id NAA26516 for ; Mon, 14 Mar 1994 13:08:43 -0800 Received: from lightstream.LightStream.COM by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA14550; Mon, 14 Mar 1994 13:07:37 -0800 Received: from cockatrice.LightStream.COM by lightstream.LightStream.COM (4.1/SMI-4.1) id AA27805; Mon, 14 Mar 94 16:07:35 EST Received: by cockatrice.LightStream.COM (4.1/SMI-4.1) id AA15434; Mon, 14 Mar 94 16:07:33 EST Resent-Date: Mon, 14 Mar 94 18:04 EDT Date: Mon, 14 Mar 1994 16:07:32 -0500 From: Dave Faulkner Subject: Combining the ideas of demes and sharing Resent-To: lee@neural.hampshire.EDU To: GP list Cc: dfaulkne@LightStream.COM Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <4912E7BC5A1F014248@hamp.hampshire.edu> Message-Id: <9403142107.AA15434@cockatrice.LightStream.COM> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: GP list X-Vms-Cc: dfaulkne@LightStream.COM Status: RO In my last note, I wrote: But it does make sense to cross species that are "close" in some sense. I haven't read enough about demes to know if this has been tried, but it would seem that, instead of imposing an arbitrary structural distance between demes, that a dynamic structure be imposed on the subpopulation based on some type of species distance metric: situate the chimpanzee deme "near" the gorilla deme to encourage cross-breeding; allow that relationship to vary based on a metric of structural distance among/across the deme members. Let me elaborate a bit on this idea... This is something of a combination of the ideas of demes and the complement of the use of metrics in a sharing scheme. To be more specific, we use distance metrics to perform deme invasion via something similar to k-tournament selection. (It is a complement because we are encouraging close deme mixing rather than discouraging near crossover). So we use demes in a steady-state fashion for some time, creating some convergence in each deme. When the time comes for the deme invasion, we pick a being within some deme (say via tounament selection) to invade some other deme. But which deme? Lets pick D demes at random, and for each we measure the distance of one or more members in that deme to one or more members of the current deme to create an average deme-distance. We continue to do this for each of the D demes, and then choose the one with the closest (smallest distance) average distance. Our invasion is set for that deme. This procedure can be performed at each deme every so often to get the effect of the "close species crossing" that I was talking about earlier. This scheme has the advantage of approximating a distance-vector measurement between the demes while being computationally controllable; because the process is stochastic, it really doesn't need (and would probably suffer in phenotypic performance as well as computationally) if full information was known (i.e., if all d**2 relationships were measured, for d demes). It is similar to the k-tounament selction scheme in that you take the best (closest) amoung a randomly sampled set, but here that set is of demes instead of individuals. Any thoughts? - Dave Faulkner From genetic-programming-owner@list.Stanford.EDU Tue Mar 15 03:58:54 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA27898; Tue, 15 Mar 94 03:58:53 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Tue, 15 Mar 94 03:58 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id KAA26247 for ; Mon, 14 Mar 1994 10:40:32 -0800 Received: from lightstream.LightStream.COM by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA06753; Mon, 14 Mar 1994 10:39:28 -0800 Received: from cockatrice.LightStream.COM by lightstream.LightStream.COM (4.1/SMI-4.1) id AA21836; Mon, 14 Mar 94 13:39:26 EST Received: by cockatrice.LightStream.COM (4.1/SMI-4.1) id AA15185; Mon, 14 Mar 94 13:39:24 EST Resent-Date: Tue, 15 Mar 94 03:58 EDT Date: Mon, 14 Mar 1994 13:39:22 -0500 From: Dave Faulkner Subject: RE: Sexiness: Did I have it backwards? Resent-To: lee@neural.hampshire.EDU To: Andrew Singleton Cc: GP list , dfaulkne@LightStream.COM Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <48BFE91B157F014C40@hamp.hampshire.edu> Message-Id: <9403141839.AA15185@cockatrice.LightStream.COM> In-Reply-To: Your message of "Fri, 11 Mar 1994 10:09:58 EST." <2972482234.0.p00396@psilink.com> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: Andrew Singleton X-Vms-Cc: GP list , dfaulkne@LightStream.COM Status: RO ** Andrew Singleton writes: >Experimental evidence shows that combining very different individuals >through crossover is a recipe for failure. I wrote to Peter Dudley and >suggested this might be the case, and he discovered the same >experimentally. Studies of "deme" based massively parallel genetic >algorithms demonstrate this principle graphically. The boundaries >between the demes are always marked with "lethal" failed crosses. ok, I'll buy that: if you cross a snake with a monkey you get an animal that does poorly in any environment. Combining a chimpanzee with a gorilla though might give you a new type of primate that does quite well - a new species. Isn't one of the qualities of a species is that a member of one species can't viably mate with the member of another species? >GP runs produce populations of similar trees which can cross >successfully. This homogenization is a critical part of the GP process, >since if you crossed random trees, your results would be very poor. > >Speciation is a big irritation in GP, since it is very difficult to >combine good solutions from one run with good solutions in another run. of course, this "homogenization" must hapen at the beginning of any run, and is what happens (semi)independently and simultaneously in all demes or tag regions. Each deme (implemented via tagging, spatially or other mechanism) is a small sub-population that has the possibility of evolving a separate species that performs well. It is true that a snake does much better in some environments than a monkey and vice versa and to cross them makes no sense. But it does make sense to cross species that are "close" in some sense. I haven't read enough about demes to know if this has been tried, but it would seem that, instead of imposing an arbitrary structural distance between demes, that a dynamic structure be imposed on the subpopulation based on some type of species distance metric: situate the chimpanzee deme "near" the gorilla deme to encourage cross-breeding; allow that relationship to vary based on a metric of structural distance among/across the deme members. >We know one thing. The answer is NOT subtree crossover. > >Some possibilities have been proposed: >1) A classifier type cooperating set of GP individuals; >2) Evolving or explicitly constructing a hierarchy of pre-evolved >individuals, based on parcelling out fitness cases. I'm not sure I know what you mean by this but I am very intrigued. Could you possibly elaborate a little. Thanks. From genetic-programming-owner@list.Stanford.EDU Mon Mar 14 20:57:22 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA27104; Mon, 14 Mar 94 20:57:21 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Mon, 14 Mar 94 20:52 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id PAA26948 for ; Mon, 14 Mar 1994 15:59:35 -0800 Received: from lightstream.LightStream.COM (lightstream.com) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA25180; Mon, 14 Mar 1994 15:58:30 -0800 Received: from cockatrice.LightStream.COM by lightstream.LightStream.COM (4.1/SMI-4.1) id AA02942; Mon, 14 Mar 94 18:58:27 EST Received: by cockatrice.LightStream.COM (4.1/SMI-4.1) id AA16041; Mon, 14 Mar 94 18:58:25 EST Resent-Date: Mon, 14 Mar 94 20:56 EDT Date: Mon, 14 Mar 1994 18:58:22 -0500 From: Dave Faulkner Subject: RE: Sexiness: Did I have it backwards? Resent-To: lee@neural.hampshire.EDU To: corcoran@penguin.mcs.utulsa.EDU Cc: genetic-programming@cs.stanford.EDU, dfaulkne@LightStream.COM Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <48FAE7CD5DFF01391C@hamp.hampshire.edu> Message-Id: <9403142358.AA16041@cockatrice.LightStream.COM> In-Reply-To: Your message of "Mon, 14 Mar 1994 15:02:43 CST." <9403142102.AA00721@penguin.mcs.utulsa.edu> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: corcoran@penguin.mcs.utulsa.EDU X-Vms-Cc: genetic-programming@cs.stanford.EDU, dfaulkne@LightStream.COM Status: RO Art Corcoran writes...... The reason that a monkey cannot mate with a snake is because of the incompatibility of the genetic material, NOT because of poorly performing offspring. This may be due to a hidden tendency of a species for self-preservation of the species which is independent of natural selection. That is, prevention of cross "fertilability" of similar species helps to preserve each species intact. It is natural selection which determines which species will survive. Maintaining a diverse population helps a particular species to adapt easily to a changing environment. However, the diversity of a species has no effect on the performance/adapibility of another species, does it? ... I agree. Essentially I'm taking liberties in the analogue to living things. If you COULD cross a monkey with a snake, that ani-blob would likely be pretty useless. I'm trying to say that the likelihood of successfully generating a good being by crossing disparate individuals is small. There seems to be two uses for diversity: (faster) convergence and adaptibility. (I think someone in the GP mailing list said something to this effect recently). It is interesting to think about emerging species in both GA/P and life. An equilibrium is created in the relationship between a population and the fitness landscape, thereby creating a stability in the genetic dynamics - a species. For the same conditions (environment), many species may evolve that do well. Perhaps some of these species are similar, similar enough not to be separate species, per se, but perhaps "varieties" (does someone have a better term?). A plethora of mediocre, but highly diverse, beings give way to specialized, highly fit members of the population. Diversity is the space that allows convergence; once diversity is eliminated so is the ability to converge, it would seem. Then the fitness landscape changes, creating dis-equilibrium. Now we are in need of adaptability. Is it some mutation, genetic drift, or "variaties" interbreeding that produces a new population that is viable? Certainly in GA/P all of these mecanisms are available, as well as restarting (the usual way). How does nature go about this? I've heard (Stephen Gould?) that whatever mechansism is involved that its very fast relative to the geological timescales, and that's why thee are so few examples of "missing-links" in the fossil record. Thus, nature seems to be fairly well adept at creating new species quickly and efficiently. Can we learn something from this? This idea of "punctuated equilibrium" describes a bit about the dynamics of population change, but what are the *mechanisms*? Can we mimic them effectively? Any biology-types out in the crowd willing to take a stab at this? - Dave Faulkner (hope I have't burned too much bandwidth lately!) From genetic-programming-owner@list.Stanford.EDU Mon Mar 14 22:11:10 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA27195; Mon, 14 Mar 94 22:11:07 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Mon, 14 Mar 94 21:59 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id QAA26957 for ; Mon, 14 Mar 1994 16:02:59 -0800 Received: from cray.com (timbuk.cray.com) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA25328; Mon, 14 Mar 1994 16:01:50 -0800 Received: from shamu (shamu.cray.com) by cray.com (Bob mailer 1.2) id AA18307; Mon, 14 Mar 94 18:01:47 CST Received: by shamu id AA29999; 4.1/CRI-5.4; Mon, 14 Mar 94 18:01:44 CST Resent-Date: Mon, 14 Mar 94 22:10 EDT Date: Mon, 14 Mar 94 18:01:41 CST From: mwd@carina.cray.COM Subject: RE: GP and diversity /Gene regulation Resent-To: lee@neural.hampshire.EDU To: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <48F09B8F6FFF01522A@hamp.hampshire.edu> Message-Id: <9403150001.AA29999@shamu> X-Mailer: ELM [version 2.3 PL11b-CRI] X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: genetic-programming@cs.stanford.EDU Status: RO > Subject: GP and diversity > > > >So, what we want is a way to carry around material that doesn't > >necessarily get expressed, as a kind of "diversity preserve". > > > >leaving its third argument to act as a no-op during expression, but as a > >storehouse for genetic material to be passed on later...? > > OK, soon I will be embarrassingly over my head. As a biophysicist, the > general problem of preserving diveristy interests me, but I am not really > qualified to effectively discuss implementations. > With that aside, I'll risk commenting in a general fashion. I guess > I would hesitate to incorporate 'by hand' such 'preserves.' I seems to me > that it would be best to 'come up with' a general scheme for automatically > 'de-expressing' or 'amplifying' the expression of various subunits of a > program. This way one could let the pressures of evolution tune the > expression. I realize this is not trivial but likely implies a rather > intense conceptual 'shift' in the way that GP evolution is carried out. > Specifically, it entails some sort of new aspect to the individual in GP >that interacts with the program to regulate how it is executed (sort of like >regulatory proteins that control gene expression in cells). Perhaps if this > line of ideas has any merit, some one can be clever enough to design the > program itself with 'self-regulating aspects,' but presently I can only > think of having a second monitoring system (although the true biological > analog is self-regulation, as DNA codes for proteins that can control > the expression of genes that code for proteins. Gene expression can be > seriously recursive). > > > Erec Stebbins This is a good point, infact over time, the organism should generate this itself, as a means of protection/preservation(generally). This would last over time. This topic came up (well sort of) a few weeks ago when Chris Langton commented (and others) commented about (paraphrased) 'non-coding regions of DNA being the comments'. In actuality, they are in a way comments, but much more powerful, when compared to a computer program, the non-coding regions would be more like 'compiler directives' or 'ifdef' statements. (At least that is my opinion/experience). (My area is primarily a molecular biologist, under Dr. C. Weldon Jones, Dr. Perry Hackett, and lately I have focused mostly on the 3' and 5' untranslated regions, trying to understanding the importance of the secondary structure in regulation). We have found in HIV-2, that certain changes in non-translated regions cause, 1. inactivity, 2. reduced expression, sometimes based on 1 nucleic acid (it all depends on where that nucleic acid is in the structure). #IFDEF viral_binding for (virus) ; do produce_anti_viral_stuff done #ENDIF There are many examples of the non-coding region of DNA coding for regulation enhancement/inhibitors. (The difference between genetic non-coding regions and comments is that the non-coding regions are active, others examples they would be where they would 'comment out' some of the code - a place where a protein binds that 'turns off' the gene, so it cannot be read until the protein is released). There is a lot of information in the non-coding region of DNA. I do not consider genetics to be the same as 'learning' in the sense that, I view learning is more than just holding information and responding to stimuli. (I would consider it soft definition of learning). In order to get a more 'true' learning system I think it needs to be more complex than just a genetic(meaning DNA) model. We need to look at more of a biological system approach. I think combining the current knowledge in the areas of Genetics/Neurology/learning theory/memory. The brain literally changes the cellular structures when you remember (it seems like it makes the path more solid/better referenced) with the more stimulus or number of stimuli. The cellular membrane is as important to gene control as the sequence itself, as is the external environment, it is a large and inter-reliant system. You can look at how the parts work, but in order to understand one needs to look at the whole, also. 1. Recognition sites (Where the proteins bind to start transcription) 2. They are involved in regulation: expression, enhancement,inhibition,etc.. 3. There is also more being found in importance of the RNA structure in regulation in the untranslated regions. The cell environment is also very important. A simple linear DNA model of regulation is becoming less viable. The genetic material is identical (or nearly so) in almost every cell of 'higher-level' multi-cellular organisms, some genes are expressed others are turned off. These are dictated by the environment of the cell (cell membrane, the cell it was produced from, the proteins hormones, etc. in the cells environment). We need to look from a complex/ dynamic systems approach. (One concern I have about complex systems is the hype on the 'chaos' versus 'functionality', both are valuable ways to study and learn, without one method a person is likely to miss what is obvious to the other). The concept of the program not only to rewrite it self, but to also redesign the hardware I think will be an important step. Similar to how our brain works with memory (so I have been told, that the cellular structure is physically changed as a memory becomes more 'impressed'). (The machine that rewires and reprograms itself). Mark -- Mark Dalton AUG-GCU-AGA-AAG H Cray Research, Inc. M A R K | Eagan, MN 55121 CH3-S-CH2-CH2-C-COOH Internet: mwd@cray.com | (612)683-3035 NH2 From genetic-programming-owner@list.Stanford.EDU Mon Mar 14 23:47:03 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA27609; Mon, 14 Mar 94 23:47:02 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Mon, 14 Mar 94 23:46 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.4/8.6.4) with SMTP id SAA27179 for ; Mon, 14 Mar 1994 18:15:51 -0800 Received: from sgigate.SGI.COM by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA01076; Mon, 14 Mar 1994 18:14:47 -0800 Received: from relay.sgi.com (relay.sgi.com [192.26.51.36]) by sgigate.sgi.com (8.6.4/8.6.4) with SMTP id SAA13033; Mon, 14 Mar 1994 18:14:46 -0800 Received: from giraffe.asd.sgi.com by relay.sgi.com via SMTP (920330.SGI/920502.SGI) for @sgigate.sgi.com:genetic-programming@cs.stanford.edu id AA16396; Mon, 14 Mar 94 18:14:44 -0800 Received: from ivan.asd.sgi.com by giraffe.asd.sgi.com via SMTP (920330.SGI/920502.SGI) for @relay.sgi.com:genetic-programming@cs.stanford.edu id AA23857; Mon, 14 Mar 94 18:14:41 -0800 Received: by ivan.asd.sgi.com (930416.SGI/900721.SGI) for @giraffe.asd.sgi.com:genetic-programming@cs.stanford.edu id AA27284; Mon, 14 Mar 94 18:14:39 -0800 Resent-Date: Mon, 14 Mar 94 23:47 EDT Date: Mon, 14 Mar 94 18:14:39 -0800 From: ib@ivan.asd.sgi.COM Subject: Species Resent-To: lee@neural.hampshire.EDU To: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <48E314FA3BDF014427@hamp.hampshire.edu> Message-Id: <9403150214.AA27284@ivan.asd.sgi.com> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: genetic-programming@cs.stanford.EDU Status: RO Art Corcoran writes: > The reason that a monkey cannot mate with a snake is because of the > incompatibility of the genetic material I think that the creation of 'species' is inevitable (spontaneous) when evolution occurs in several places independently. For example, John Koza developed a method to evolve LISP programs. You can probably 'cross' his programs with other LISP programs derived from his work. Now imagine trying to cross those LISP programs with some completely different 'species' of programs that were developed completely independently in some remote location. Programmers have successfully 'crossed' and manually recombined various versions of the UNIX operating system, such as the original version of UNIX from AT&T and the BSD version developed at Berkeley. Now imagine trying to cross UNIX with an IBM operating system or the Apple System 7. I think that programs, operating systems, etc. must be closely related and developed in the same location or a nearby location if you want to be able to 'cross' them successfully. That seems natural even for an artificial environment. It also helps if you start from the same base. I think that evolutionary processes also inevitably and spontaneously keep increasing the distance between entities that used to have a common ancestor. Sometimes various evolutionary paths converge, but biologists are able to determine the branching of species by analyzing the genetic material in those species. What is so interesting about artificial genetics is that we often find that we have rediscovered something that we thought we have invented. Many concepts and processes encountered in artificial genetics seem similar or analogous to natural phenomena and processes. We should try to determine the basic laws, processes, procedures, or algorithms common to all evolutionary processes. Maybe we need a new type of science to do that. Maybe we will not be able to repeat a particular experiment exactly, but there will be some common (statistical) conclusions that can be drawn from many similar experiments. You may not be able to repeat an experiment without recreating exactly the same conditions, and even then genetic experiments will probably give different results. The conditions on our planet have changed so much that evolution would probably happen in a completely different way if all life on this planet was suddenly destroyed. One mystery that should be solved is why all life on this planet seems to be based on carbon, and none of it is based on, for example, silicon. What will play the role of carbon in the evolution of software? It seems that we need some simple basic components at the lowest level, and some versatile higher-level components that can be easily and spontaneously combined with other components into complex structures (software molecules). Ivan Bach, ib@asd.sgi.com From genetic-programming-owner@list.Stanford.EDU Wed Mar 16 14:33:13 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA02155; Wed, 16 Mar 94 14:33:07 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Wed, 16 Mar 94 12:55 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.7/8.6.4) with SMTP id HAA20778 for ; Wed, 16 Mar 1994 07:27:25 -0800 Received: from penguin.mcs.utulsa.edu by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA07357; Wed, 16 Mar 1994 07:26:21 -0800 Received: from puffin.mcs.utulsa.edu by penguin.mcs.utulsa.edu (5.0/SMI-SVR4) id AA00527; Wed, 16 Mar 94 09:23:03 CST Resent-Date: Wed, 16 Mar 94 12:58 EDT Date: Wed, 16 Mar 94 09:23:03 CST From: corcoran@penguin.mcs.utulsa.EDU Subject: RE: Sexiness: Did I have it backwards? Resent-To: lee@neural.hampshire.EDU To: dfaulkne@LightStream.COM Cc: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <47AB6B4F021F01A14F@hamp.hampshire.edu> Message-Id: <9403161523.AA00527@penguin.mcs.utulsa.edu> X-Sun-Charset: US-ASCII Content-Length: 1388 X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: dfaulkne@LightStream.COM X-Vms-Cc: genetic-programming@cs.stanford.EDU Status: RO Dave Faulkner writes.... > [...] > I'm trying to > say that the likelihood of successfully generating a good being > by crossing disparate individuals is small. Yes, this is the point that fascinates me. However, I think there is a need to cross both disparate and similar individuals. In a nice unimodal or bimodal function, crossing over similar individuals can help find better offspring. Note, this is a local search (hill climbing). On problems with more peaks, crossing over disparate individuals can help find other higher peaks. This is more of a global search, encouraging diversity. Thus, the sexiness measure really needs to be tunable to the fitness landscape to balance the local and global aspects of the search. This introduces two interesting questions with respect to GP: 1) The GA often does better when hill climbing is performed on each individual between generations. How can hill climbing be applied to Lisp sexpressions during GP generations? (I'm not an experienced GP hacker so this may have an obvious answer.) 2) How does one characterize the fitness landscape in GP? A small perturbation of an sexpression can have a dramatically different fitness and the search space size can be huge, thus aren't (nontrivial) GP landscapes inherently rugged and unpredictable? Inquiring minds want to know! Art From genetic-programming-owner@list.Stanford.EDU Wed Mar 16 13:37:42 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA02047; Wed, 16 Mar 94 13:37:40 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Wed, 16 Mar 94 13:25 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.7/8.6.4) with SMTP id IAA22386 for ; Wed, 16 Mar 1994 08:09:21 -0800 Received: from penguin.mcs.utulsa.edu by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA09477; Wed, 16 Mar 1994 08:08:16 -0800 Received: from puffin.mcs.utulsa.edu by penguin.mcs.utulsa.edu (5.0/SMI-SVR4) id AA00562; Wed, 16 Mar 94 10:05:02 CST Resent-Date: Wed, 16 Mar 94 13:26 EDT Date: Wed, 16 Mar 94 10:05:02 CST From: corcoran@penguin.mcs.utulsa.EDU Subject: RE: Species Resent-To: lee@neural.hampshire.EDU To: genetic-programming@cs.stanford.EDU, ib@ivan.asd.sgi.COM Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <47A76EC6997F01824B@hamp.hampshire.edu> Message-Id: <9403161605.AA00562@penguin.mcs.utulsa.edu> X-Sun-Charset: US-ASCII Content-Length: 1278 X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: genetic-programming@cs.stanford.EDU, ib@ivan.asd.sgi.COM Status: RO Ivan Bach writes: > What is so interesting about artificial genetics is that we often find that > we have rediscovered something that we thought we have invented. Many > concepts and processes encountered in artificial genetics seem similar or > analogous to natural phenomena and processes. We should try to determine > the basic laws, processes, procedures, or algorithms common to all > evolutionary processes. Yes, I think the balance between diversity and specialization is also important in nature. Certain species evolve for and thrive in a limited, specialized environment. For example, certain plants and insects have evolved a highly specialized symbiotic relationship. These represent an optima for the particular environment. However, when the environment changes these highly specialized species tend to become extinct. For example, when the plants die away, the insects soon follow. Other species, such as sharks, jellyfish, and alligators, have remained relatively unchanged for millions of years. Perhaps they have evolved to be more general, or adaptive to the environment. So, can we then conclude that encouraging specialization leads to better solutions in the short term but encouraging diversity has better long term effects? Art From genetic-programming-owner@list.Stanford.EDU Wed Mar 16 20:17:58 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA03249; Wed, 16 Mar 94 20:17:57 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Wed, 16 Mar 94 16:20 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.7/8.6.4) with SMTP id LAA29152 for ; Wed, 16 Mar 1994 11:25:10 -0800 Received: from lightstream.LightStream.COM (lightstream.com) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA19659; Wed, 16 Mar 1994 11:19:00 -0800 Received: from cockatrice.LightStream.COM by lightstream.LightStream.COM (4.1/SMI-4.1) id AA07253; Wed, 16 Mar 94 14:16:18 EST Received: by cockatrice.LightStream.COM (4.1/SMI-4.1) id AA20272; Wed, 16 Mar 94 14:16:16 EST Resent-Date: Wed, 16 Mar 94 17:40 EDT Date: Wed, 16 Mar 1994 14:16:15 -0500 From: Dave Faulkner Subject: RE: Species Resent-To: lee@neural.hampshire.EDU To: corcoran@penguin.mcs.utulsa.EDU Cc: genetic-programming@cs.stanford.EDU, ib@ivan.asd.sgi.COM, dfaulkne@LightStream.COM Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <47840B3295DF01A636@hamp.hampshire.edu> Message-Id: <9403161916.AA20272@cockatrice.LightStream.COM> In-Reply-To: Your message of "Wed, 16 Mar 1994 10:05:02 CST." <9403161605.AA00562@penguin.mcs.utulsa.edu> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: corcoran@penguin.mcs.utulsa.EDU X-Vms-Cc: genetic-programming@cs.stanford.EDU, ib@ivan.asd.sgi.COM, dfaulkne@LightStream.COM Status: RO Art Corcoran writes: Yes, I think the balance between diversity and specialization is also important in nature. Certain species evolve for and thrive in a limited, specialized environment. For example, certain plants and insects have evolved a highly specialized symbiotic relationship. These represent an optima for the particular environment. However, when the environment changes these highly specialized species tend to become extinct. For example, when the plants die away, the insects soon follow. Other species, such as sharks, jellyfish, and alligators, have remained relatively unchanged for millions of years. Perhaps they have evolved to be more general, or adaptive to the environment. So, can we then conclude that encouraging specialization leads to better solutions in the short term but encouraging diversity has better long term effects? *** Yes you might conclude that. That's not to say that there doesn't exist both a perfect solution to both the general *and* specific fitness domains, theoretically speaking; we engineers know well that this is a pipe dream in the real world. Conclusion: this is a real-world gut reaction that's probably a good tenet. However, although a single solution to a problem must usually trade-off various good and bad factors, it is not entirely true that a population of solutions needs to be compromised in the same manner. In terms of GA/P I've been thinking (and posting) about this idea of speciation as a kind of diversity that's hopefully more useful than the random start. I guess this has been kicked around by all revelers in the postings lately. To this end I've also been thinking about a meta-GA that "GA's" among sub-population groups (demes, niches, tag regions, whatever) at the same time its GA-ing within a sub-population. Thus within a GA we create many sub-population and allow speciation (convergence) within each sub-population, running normal GA. Now we need to create a constructive diversity that takes advantage of the inherent information of a species (after all, a species is a highly matured aspect of some proto-blob of the past; there must be a wealth of information within that species about the fitness landscape). So how then do we meta-GA among the sub-population/species? The idea of diffusion (probablisticly send genomes from one group to another) seems simple and mocks nature. Its an interesting dynamic that should be isolated and examined separately from the crossover/mutation/reproduction mechanisms. I've suggested a tounament selection -like mechanism based on the difficult-to-create genome distance metric. There are probably many other ways. Encouraging the creation of many species, and creating mechanisms to interact among the species, I believe will have the possibility of creating both good short-term solutions and storing the possibilities of good long-term solutions. We need some ways to develop both the sharks AND the dinosaurs (fill in your favorite exotic extinct species here) within a population. - Dave Faulkner From genetic-programming-owner@list.Stanford.EDU Wed Mar 16 19:44:55 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA03217; Wed, 16 Mar 94 19:44:53 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Wed, 16 Mar 94 17:55 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.7/8.6.4) with SMTP id NAA29477 for ; Wed, 16 Mar 1994 13:07:03 -0800 Received: from gatekeeper.imagen.com by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA24482; Wed, 16 Mar 1994 13:05:59 -0800 Received: from imagen.sclara.qms.com (imagen.imagen.com) by gatekeeper.imagen.com (4.1/SMI-4.1) id AA10165; Wed, 16 Mar 94 13:05:58 PST Received: from sun470.rd.qms.com (sun470-t1) by imagen.sclara.qms.com (4.1/SMI-4.1) id AA26302; Wed, 16 Mar 94 13:05:56 PST Received: from rdcclink.rd.qms.com by sun470.rd.qms.com (4.1/SMI-4.1) id AA19947; Wed, 16 Mar 94 15:05:01 CST Received: from ccMail by rdcclink.rd.qms.com id AA763859177 Wed, 16 Mar 94 15:06:17 CST Resent-Date: Wed, 16 Mar 94 18:13 EDT Date: Wed, 16 Mar 94 15:06:17 CST From: alexa@rdcclink.rd.qms.COM Subject: Sexiness - Diversity Resent-To: lee@neural.hampshire.EDU To: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <477F428C741F01A565@hamp.hampshire.edu> Message-Id: <9402167638.AA763859177@rdcclink.rd.qms.com> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: genetic-programming@cs.stanford.EDU Status: RO I have been seeing all these communication on Sexiness and diversity going on. I think it is high time that I put my two cents worth in. So, here it goes! I am not sure at what point this whole conversation started. Nevertheless, I guess I have gathered enough to conclude that there is a mis-interpretation all the way. Some one started on Sexiness. There came diversity into play. Let us deal with one at a time. I have reasons to beleive (natural, of course) what I am about to say. Boys and girls, we are treating (at least, it appears to be) sexiness as the only diversity. My opinion is that though this is true, we must also consider other diversities. This is science we are dealing with and political correctness has no place in it (my strong, overly slanted opinion). What's the point? The point is that when addressing diversity, we must consider ALL kinds of diversity by keeping in mind that there are more difference than just sexiness. This is to say that an individuals behaviour can be (yes, it will be) an end-result of his/her ethnic background, economic (?), cultural, social, ... etc influence. Enough said to stir a long discussion. Let me hear it guys. Now, if we want to just consider sexiness, let us NOT talk about diversity also in the same sentence. My suggestion is to deal with sexiness alone and then deal with diversity (not necessarily in the stated order) separately. If any one of the two helps understand the other better, we will take it into consideration. Otherwise, why confuse the issue. If I rambled too much, sorry about it. If what I said does not make any sense, please check with the other guy before you trash me! Regards Fellow crusader in GA/GP Alex From genetic-programming-owner@list.Stanford.EDU Wed Mar 16 19:49:39 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA03222; Wed, 16 Mar 94 19:49:37 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Wed, 16 Mar 94 17:59 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.7/8.6.4) with SMTP id NAA29507 for ; Wed, 16 Mar 1994 13:22:43 -0800 Received: from penguin.mcs.utulsa.edu by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA25735; Wed, 16 Mar 1994 13:21:38 -0800 Received: from puffin.mcs.utulsa.edu by penguin.mcs.utulsa.edu (5.0/SMI-SVR4) id AA01299; Wed, 16 Mar 94 15:18:21 CST Resent-Date: Wed, 16 Mar 94 18:12 EDT Date: Wed, 16 Mar 94 15:18:21 CST From: corcoran@penguin.mcs.utulsa.EDU Subject: RE: Species Resent-To: lee@neural.hampshire.EDU To: dfaulkne@LightStream.COM Cc: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <477F819AB9FF01A565@hamp.hampshire.edu> Message-Id: <9403162118.AA01299@penguin.mcs.utulsa.edu> X-Sun-Charset: US-ASCII Content-Length: 2381 X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: dfaulkne@LightStream.COM X-Vms-Cc: genetic-programming@cs.stanford.EDU Status: RO > In terms of GA/P I've been thinking (and posting) about this idea of > speciation as a kind of diversity that's hopefully more useful than > the random start. I guess this has been kicked around by all revelers > in the postings lately. To this end I've also been thinking about > a meta-GA that "GA's" among sub-population groups (demes, niches, tag regions, > whatever) at the same time its GA-ing within a sub-population. Thus within > a GA we create many sub-population and allow speciation (convergence) > within each sub-population, running normal GA. Now we need to create > a constructive diversity that takes advantage of the inherent information > of a species (after all, a species is a highly matured aspect of some > proto-blob of the past; there must be a wealth of information within > that species about the fitness landscape). Yes, and the meta-GA/P needs to learn which strategies are best for a particular class of landscape so it can classify new problem instances and apply the proper GA/P to solve it most efficiently. > So how then do we meta-GA among the sub-population/species? The idea of > diffusion (probablisticly send genomes from one group to another) > seems simple and mocks nature. Its an interesting dynamic that should be > isolated and examined separately from the crossover/mutation/reproduction > mechanisms. I've suggested a tounament selection -like mechanism based > on the difficult-to-create genome distance metric. There are probably > many other ways. But the meta-GA/P doesn't need to find the best sub-population does it? I would think if each species were evolved for a different environment (exploitation) then the meta-GA/P would be most successful if it encouraged co-evolution (exploration) between the sub-populations. > Encouraging the creation of many species, and creating mechanisms to > interact among the species, I believe will have the possibility of > creating both good short-term solutions and storing the possibilities > of good long-term solutions. We need some ways to develop both the sharks > AND the dinosaurs (fill in your favorite exotic extinct species here) > within a population. > > - Dave Faulkner Agreed! I think the sexiness measure can be useful in this respect, but there would have to be some work to show that it is not implicitly done in the GA/P to show it is necessary. Art From genetic-programming-owner@list.Stanford.EDU Wed Mar 16 19:31:54 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA03175; Wed, 16 Mar 94 19:31:26 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Wed, 16 Mar 94 18:28 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.7/8.6.4) with SMTP id NAA29583 for ; Wed, 16 Mar 1994 13:46:07 -0800 Received: from dmc.com (HULK.DMC.COM) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA27387; Wed, 16 Mar 1994 13:44:50 -0800 Received: from oak by DMC.COM (MX V3.3 VAX) with UUCP; Wed, 16 Mar 1994 16:40:52 EST Received: by adapt.com (4.1/SMI-4.1) id AA06651; Wed, 16 Mar 94 16:18:46 EST Resent-Date: Wed, 16 Mar 94 18:57 EDT Date: Wed, 16 Mar 94 16:18:46 EST From: kinnear@adapt.COM Subject: RE: Sexiness: Did I have it backwards? Resent-To: lee@neural.hampshire.EDU To: corcoran@penguin.mcs.utulsa.EDU, dudeyp@chert.cs.orst.EDU Cc: dfaulkne@LightStream.COM, genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <47793AFC2BBF01A836@hamp.hampshire.edu> Message-Id: <9403162118.AA06651@adapt.com> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: corcoran@penguin.mcs.utulsa.EDU, dudeyp@chert.cs.orst.EDU X-Vms-Cc: dfaulkne@LightStream.COM, genetic-programming@cs.stanford.EDU Status: RO > > > > 1) The GA often does better when hill climbing is performed on each > > individual between generations. How can hill climbing be applied > > Wow! Is there a paper on this? Well, try: Gruau, F., Whitley, D. "Adding Learning to the Cellular Developement of Neural Networks", Evolutionary Computation V1, N3, Fall 1993. Ackley, D. H., Littman, M.L., "A Case for Lamarkian Evolution", in Artificial Life III, C. G. Langton, Ed., Reading, MA: Addison-Wesley, 1994. Both of these papers are really worth looking at! > > > to Lisp sexpressions during GP generations? (I'm not an experienced > > GP hacker so this may have an obvious answer.) > > Would a mutation be a good shot at a "small step"? Only if it is *really* a small step, which the standard "replace sub-tree with random sub-tree" almost certainly isn't. But, you can probably design one that is, though they tend to be representation (and therefore problem) speciic. > > > 2) How does one characterize the fitness landscape in GP? A small > > perturbation of an sexpression can have a dramatically different > > fitness and the search space size can be huge, thus aren't > > (nontrivial) GP landscapes inherently rugged and unpredictable? > I've looked a bit at the autocorrelation of random walks on GP landscapes (following Weinbeger's work with NK landscapes), and they *do* look pretty rugged (i.e. hard). You can read about it in the paper I submitted to WCCI on the GP ftp site: ftp.cc.utexas.edu /pub/genetic-programming/papers/kinnear.wcci.ps.Z Cheers -- Kim From genetic-programming-owner@list.Stanford.EDU Wed Mar 16 19:38:14 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA03186; Wed, 16 Mar 94 19:38:10 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Wed, 16 Mar 94 18:45 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.7/8.6.4) with SMTP id OAA29598 for ; Wed, 16 Mar 1994 14:03:18 -0800 Received: from lightstream.LightStream.COM (lightstream.com) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA28299; Wed, 16 Mar 1994 14:02:13 -0800 Received: from cockatrice.LightStream.COM by lightstream.LightStream.COM (4.1/SMI-4.1) id AA12021; Wed, 16 Mar 94 17:02:12 EST Received: by cockatrice.LightStream.COM (4.1/SMI-4.1) id AA21175; Wed, 16 Mar 94 17:02:10 EST Resent-Date: Wed, 16 Mar 94 18:46 EDT Date: Wed, 16 Mar 1994 17:02:09 -0500 From: Dave Faulkner Subject: RE: Species Resent-To: lee@neural.hampshire.EDU To: corcoran@penguin.mcs.utulsa.EDU Cc: dfaulkne@LightStream.COM, genetic-programming@cs.stanford.EDU, dfaulkne@LightStream.COM Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <477ABFE023DF01A836@hamp.hampshire.edu> Message-Id: <9403162202.AA21175@cockatrice.LightStream.COM> In-Reply-To: Your message of "Wed, 16 Mar 1994 15:18:21 CST." <9403162118.AA01299@penguin.mcs.utulsa.edu> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: corcoran@penguin.mcs.utulsa.EDU X-Vms-Cc: dfaulkne@LightStream.COM, genetic-programming@cs.stanford.EDU, dfaulkne@LightStream.COM Status: RO Art Corcoran responds: > So how then do we meta-GA among the sub-population/species? The idea of > diffusion (probablisticly send genomes from one group to another) > seems simple and mocks nature. Its an interesting dynamic that should be > isolated and examined separately from the crossover/mutation/reproduction > mechanisms. I've suggested a tounament selection -like mechanism based > on the difficult-to-create genome distance metric. There are probably > many other ways. But the meta-GA/P doesn't need to find the best sub-population does it? I would think if each species were evolved for a different environment (exploitation) then the meta-GA/P would be most successful if it encouraged co-evolution (exploration) between the sub-populations. ***** I believe there's a small misunderstanding here. Let me try to clear things by explaning in more detail. In the deme idea that I'm familiar with, we have divided the populations into groups that are somewhat isolated and yet have a spatial relationship with neighbors. That is, within a subpopulation a normal GA is run. All sub-populations run the same GA with the same fitness function, as if there were many GA's being run on the same problem simultaneously, or many different runs over time. Periodically, we break the isolation of the sub-population by sending a genome to a neighboring subpopulation, and this genome visitor merrily becomes a member of the new subpopulation. This I called "invasion" in a prior posting; I think Collins calls it "diffusion". If this is a particularly good genome visitor, then its offspring will tend to add to the "goodness" of the sub-population and the sub-population as a whole will benefit. If not, then it will die out via lethal crossover. Note that without the diffusion, all we have is a bunch of isolated GA's. In a multi-modal objective function, without any planned bias mechanisms such as sharing (Goldberg's book), we sometimes end up at one fitness peak, and sometimes at another, somewhat randomly if the peaks are of equal fitness. Thus, in some runs we find one answer, in other runs we find a different answer. Now imagine that the demes are isolated by 0 probability of genome transferrence. In some demes we would expect to find a convergence at one peak, in other demes we find convergence at a different peak - purely by chance. Observing this from a global perspective, we can see the convergence of different demes or subpopulation to different peaks - and so we see the simultaneous creation of many different species, one at each deme. The meta-GA, as I called it, operates at the level of the gene transference, diffusion, invasion or what ever mechanism. I call it "meta" because we're no longer crossing individuals, but now we are thinking in terms of crossing sub-populations, or sub-population convergences - i.e., species. These mechanisms are still very simple as suggested, and perhaps could be improved upon. Collins used a arbitary imposition of space (torriod) to create deme neighbors (if I'm at location (1,1) then my neighbors are at (0,1)(1,0) (2,1)(1,2) etc.). I am suggesting that we create a metric space based on gene-distances, and that gene transference tends to take place among "close" species, or neighbors that are "close" with respect to the gene-distance metric (on the assumption that crossing a monkey with a snake doesn't work very often). Note that I use the work "tend" because we should every so often try out the monkey-snake and see if it works this time. I'm not suggesting that there are a set of diferent GA/P's and we try different kinds over runs. I'm simply isolating the diffusion mechanism and seeing it as a recursion of the selection/crossover/mutation-on-individuals functions. I don't know; is this any clearer? - Dave Faulkner There has been some From genetic-programming-owner@list.Stanford.EDU Thu Mar 17 17:10:59 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA05528; Thu, 17 Mar 94 17:10:57 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Thu, 17 Mar 94 13:00 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.7/8.6.4) with SMTP id GAA01102 for ; Thu, 17 Mar 1994 06:53:59 -0800 Received: from balder.cs.wisc.edu by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA25113; Thu, 17 Mar 1994 06:52:55 -0800 Received: by balder.cs.wisc.edu; Thu, 17 Mar 94 08:52:53 -0600 Resent-Date: Thu, 17 Mar 94 13:52 EDT Date: Thu, 17 Mar 1994 08:52:52 -0600 (CST) From: derek@cs.wisc.EDU Subject: RE: Sexiness: Did I have it backwards? Resent-To: lee@neural.hampshire.EDU To: kinnear@adapt.COM Cc: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <46DAA070281F01CD7D@hamp.hampshire.edu> Message-Id: <9403171452.AA21550@balder.cs.wisc.edu> In-Reply-To: <9403162118.AA06651@adapt.com> from "kinnear@adapt.com" at Mar 16, 94 04:18:46 pm X-Mailer: ELM [version 2.4 PL21] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 1034 X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: kinnear@adapt.COM X-Vms-Cc: genetic-programming@cs.stanford.EDU Status: O Kim Kinnear: > I've looked a bit at the autocorrelation of random walks > on GP landscapes (following Weinbeger's work with NK > landscapes), and they *do* look pretty rugged (i.e. hard). > > You can read about it in the paper I submitted to WCCI on the > GP ftp site: > > ftp.cc.utexas.edu > /pub/genetic-programming/papers/kinnear.wcci.ps.Z I have a question about this paper. When you did your autocorrelation measurements with the crossover operator, what population did you use? The distribution of subtrees changes over time as adaptation occurs, which could conceivably change the results. Did you look into this at all? Do you have any thoughts on the matter? In general for GA and GP, doesn't the fitness-proportional reproduction make the sequence of fitnesses induced by the random walk process progressively more and more non-Markovian as adaptation proceeds? Weinberger seems to have some interesting things to say about this. Oh, and was the paper accepted? I like this kind of analysis a lot. derek From genetic-programming-owner@list.Stanford.EDU Thu Mar 17 18:38:23 1994 Return-Path: Received: from hamp by neural.hampshire.EDU (4.1/SMI-4.1) id AB06403; Thu, 17 Mar 94 18:38:16 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Thu, 17 Mar 94 18:00 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.7/8.6.4) with SMTP id NAA02030 for ; Thu, 17 Mar 1994 13:06:58 -0800 Received: from research.CS.ORST.EDU (chert.CS.ORST.EDU) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA13140; Thu, 17 Mar 1994 13:05:50 -0800 Received: from hume.CS.ORST.EDU by research.CS.ORST.EDU (4.1/1.30) id AA10173; Thu, 17 Mar 94 13:04:30 PST Received: by hume.CS.ORST.EDU (4.1/CS-Client) id AA12718; Thu, 17 Mar 94 13:04:28 PST Resent-Date: Thu, 17 Mar 94 18:28 EDT Date: Thu, 17 Mar 94 13:04:28 PST From: dudeyp@chert.cs.orst.EDU Subject: Sexiness success (?), the latest definition, and CLOS code redux Resent-To: lee@neural.hampshire.EDU To: genetic-programming@cs.stanford.EDU Cc: hthies@willamette.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <46B41E625A3F01D561@hamp.hampshire.edu> Message-Id: <9403172104.AA12718@hume.CS.ORST.EDU> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: genetic-programming@cs.stanford.EDU X-Vms-Cc: hthies@willamette.EDU Status: RO I seem to be having some success with sexiness, under the latest definition: sexiness(chooser, date) = SUM fitness(chooser, case) * fitness(date, case) cases In English, you try to breed with people who do well at the same things you do well at. This /seems/ to help on the problem I'm currently running tests on (find a formula for the value of a binary number given the bits), but more tests are in order. I think I want to test it on Holland's Royal Road function R1; it might help prevent the "hitchhiking" problem mentioned in Mitchell, Holland, and Forrest, "When Will a Genetic Algorithm Outperform Hill Climbing?" One theory as to /why/ sexiness might work is as follows: GA/GP is kindasorta parallel hillclimbing, with crossover providing useful Big Jumps. It would be best, one might argue, to breed with someone on your own hill. The current sexiness approach would encourage just this sort of breeding, and discourage the often-lethal sport of valley-leaping. In a sense, each hill becomes a phenotypical deme. Comments? (I'm beginning to wonder about asking for pointers to literature; I've got about 12,000 pages to read over spring break.) Since Holland's function is for GAs, not GPs, I'm going to re-do that spiffy CLOS code to handle both. The class heirarchy will probably look like this: population / | \ GA population GP population case population | sexy population ("Case population" is one where there are a number of fitness cases, rather than one opaque fitness function.) Handily, CLOS support multiple inheritance, so it's no trouble to create a sexy-GA object. I've also changed fitness to that it's on a scale from 0 to 1000, with 1000 being best. Having higher fitness be better was more intuitive. Any requests or comments on the previously posted code? /~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\ \ Peter Dudey, MS student in Artificial Intelligence, Oregon State University / / dudeyp@research.cs.orst.edu : hagbard on IGS : 257 NE 13th, Salem, OR 97301 \ \ "I believe in peace. And bashing two bricks together." --Rev. Gumby, MPFC / ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ From genetic-programming-owner@list.Stanford.EDU Thu Mar 17 19:27:50 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA06520; Thu, 17 Mar 94 19:27:48 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Thu, 17 Mar 94 18:50 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.7/8.6.4) with SMTP id NAA02224 for ; Thu, 17 Mar 1994 13:58:11 -0800 Received: from lightstream.LightStream.COM (lightstream.com) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA16051; Thu, 17 Mar 1994 13:57:07 -0800 Received: from cockatrice.LightStream.COM by lightstream.LightStream.COM (4.1/SMI-4.1) id AA19943; Thu, 17 Mar 94 16:57:01 EST Received: by cockatrice.LightStream.COM (4.1/SMI-4.1) id AA23755; Thu, 17 Mar 94 16:56:59 EST Resent-Date: Thu, 17 Mar 94 19:17 EDT Date: Thu, 17 Mar 1994 16:56:58 -0500 From: Dave Faulkner Subject: RE: Species & Diffusion in Demes Resent-To: lee@neural.hampshire.EDU To: corcoran@penguin.mcs.utulsa.EDU Cc: genetic-programming@cs.stanford.EDU, dfaulkne@LightStream.COM Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <46AD383EB31F01E781@hamp.hampshire.edu> Message-Id: <9403172156.AA23755@cockatrice.LightStream.COM> In-Reply-To: Your message of "Thu, 17 Mar 1994 14:52:24 CST." <9403172052.AA02752@penguin.mcs.utulsa.edu> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: corcoran@penguin.mcs.utulsa.EDU X-Vms-Cc: genetic-programming@cs.stanford.EDU, dfaulkne@LightStream.COM Status: RO Art, I wrote in a previous note..... The meta-GA, as I called it, operates at the level of the gene transference, diffusion, invasion or what ever mechanism. I call it "meta" because we're no longer crossing individuals, but now we are thinking in terms of crossing sub-populations, or sub-population convergences - i.e., species. These mechanisms are still very simple as suggested, and perhaps could be improved upon. Collins used a arbitary imposition of space (torriod) to create deme neighbors (if I'm at location (1,1) then my neighbors are at (0,1)(1,0) (2,1)(1,2) etc.). I am suggesting that we create a metric space based on gene-distances, and that gene transference tends to take place among "close" species, or neighbors that are "close" with respect to the gene-distance metric (on the assumption that crossing a monkey with a snake doesn't work very often). ************************************** I see a great number of interesting possibilities in this structure. If we make a measurement of genome distance between the demes and place those into an array of d**2 elements for d demes, then what do we have? A Network of demes! Being a network engineer, this has some very fun possibilities. For example, gene transfer along the minimum spanning tree, or perhaps Hamiltonian circuit, or neighbors greater distance than x but less than y (modulate x and y: what are the best values?). Using the deme network paradigm opens up some thinking in the possibilities of trying different operations based on the network structure. Perhaps we could use a GP to find the best diffusion topology! (umh, that might be getting back to your idea.... ;^) - Dave Faulkner From genetic-programming-owner@list.Stanford.EDU Thu Mar 17 21:16:31 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA07012; Thu, 17 Mar 94 21:16:29 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Thu, 17 Mar 94 21:16 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.7/8.6.4) with SMTP id QAA02842 for ; Thu, 17 Mar 1994 16:00:05 -0800 Received: from lightstream.LightStream.COM (lightstream.com) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA21995; Thu, 17 Mar 1994 15:59:00 -0800 Received: from cockatrice.LightStream.COM by lightstream.LightStream.COM (4.1/SMI-4.1) id AA23750; Thu, 17 Mar 94 18:58:45 EST Received: by cockatrice.LightStream.COM (4.1/SMI-4.1) id AA24434; Thu, 17 Mar 94 18:58:43 EST Resent-Date: Thu, 17 Mar 94 21:16 EDT Date: Thu, 17 Mar 1994 18:58:42 -0500 From: Dave Faulkner Subject: RE: Sexiness success (?), the latest definition, and CLOS code redux Resent-To: lee@neural.hampshire.EDU To: dudeyp@chert.cs.orst.EDU Cc: genetic-programming@cs.stanford.EDU, hthies@willamette.EDU, dfaulkne@LightStream.COM Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <469C9C72EBFF01DF13@hamp.hampshire.edu> Message-Id: <9403172358.AA24434@cockatrice.LightStream.COM> In-Reply-To: Your message of "Thu, 17 Mar 1994 13:04:28 PST." <9403172104.AA12718@hume.CS.ORST.EDU> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: dudeyp@chert.cs.orst.EDU X-Vms-Cc: genetic-programming@cs.stanford.EDU, hthies@willamette.EDU, dfaulkne@LightStream.COM Status: RO Hi Peter. I'm getting more intrigued by your "sexiness" formula (no offense, but my formula would include different factors, most probably not suited for GP). I don't understand why this works - the math. expression - I understand the valley-leaping analogy. What are "chooser" and "date" in the formula's and how are they creating phenotypical demes? Your reasoning seems sound, I just don't understand your formula. Thanks for any explanation attempts... - Dave Faulkner From genetic-programming-owner@list.Stanford.EDU Thu Mar 17 22:17:02 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA07193; Thu, 17 Mar 94 22:17:01 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Thu, 17 Mar 94 22:15 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.7/8.6.4) with SMTP id QAA02939 for ; Thu, 17 Mar 1994 16:38:25 -0800 Received: from research.CS.ORST.EDU (chert.CS.ORST.EDU) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA23885; Thu, 17 Mar 1994 16:37:20 -0800 Received: from hume.CS.ORST.EDU by research.CS.ORST.EDU (4.1/1.30) id AA12022; Thu, 17 Mar 94 16:37:14 PST Received: by hume.CS.ORST.EDU (4.1/CS-Client) id AA12803; Thu, 17 Mar 94 16:37:13 PST Resent-Date: Thu, 17 Mar 94 22:16 EDT Date: Thu, 17 Mar 94 16:37:13 PST From: dudeyp@chert.cs.orst.EDU Subject: RE: Sexiness success (?), the latest definition, and CLOS code redux Resent-To: lee@neural.hampshire.EDU To: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <469446BEE4FF01CE31@hamp.hampshire.edu> Message-Id: <9403180037.AA12803@hume.CS.ORST.EDU> In-Reply-To: <9403172358.AA24434@cockatrice.LightStream.COM> (message from Dave Faulkner on Thu, 17 Mar 1994 18:58:42 -0500) X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: genetic-programming@cs.stanford.EDU Status: RO > Date: Thu, 17 Mar 1994 18:58:42 -0500 > From: Dave Faulkner > > I'm getting more intrigued by your "sexiness" formula (no offense, > but my formula would include different factors, most probably not > suited for GP). Oh, there have been half a dozen formulae suggested; feel free to join in. :) I take it yours would include some genotypic measurements, then? > I don't understand why this works - the math. expression - I understand > the valley-leaping analogy. What are "chooser" and "date" in > the formula's and how are they creating phenotypical demes? The whole process for breeding with sexiness is: 1) Choose one individual by fitness (the chooser) 2) Compute sexiness for each other individual (date) from the point of view of the chooser. 3) Choose the other individual based on this sexiness, perhaps roulette-wheel style. 4) Cross 'em. Since, under the proposed formula, critters which are good at different parts of the fitness problem won't tend to breed; they are somewhat isolated by their phenotypic difference. /~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\ \ Peter Dudey, MS student in Artificial Intelligence, Oregon State University / / dudeyp@research.cs.orst.edu : hagbard on IGS : 257 NE 13th, Salem, OR 97301 \ \ "I believe in peace. And bashing two bricks together." --Rev. Gumby, MPFC / ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ From genetic-programming-owner@list.Stanford.EDU Fri Mar 18 03:30:22 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA08208; Fri, 18 Mar 94 03:30:20 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Fri, 18 Mar 94 03:30 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.7/8.6.4) with SMTP id SAA03089 for ; Thu, 17 Mar 1994 18:06:24 -0800 Received: from wpo.borland.com by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA27850; Thu, 17 Mar 1994 18:05:19 -0800 Received: from Borland-Message_Server by wpo.borland.com with WordPerfect_Office; Thu, 17 Mar 1994 17:51:27 -0800 Resent-Date: Fri, 18 Mar 94 03:30 EDT Date: Thu, 17 Mar 1994 17:48:19 -0800 From: smaxwell@wpo.borland.COM Subject: RE: Sexiness success (?), the latest definition, and CLOS code redux Resent-To: lee@neural.hampshire.EDU To: dudeyp@chert.cs.orst.EDU Cc: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <466867FC205F01DC68@hamp.hampshire.edu> Message-Id: X-Mailer: WordPerfect Office 4.0 X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: dudeyp@chert.cs.orst.EDU X-Vms-Cc: genetic-programming@cs.stanford.EDU Status: RO Dave asks: > I don't understand why this works - the math. expression - I > understand the valley-leaping analogy. What are "chooser" and "date" > in the formula's and how are they creating phenotypical demes? I have similar questions, and [yet another] idea draw from the references to simulated anealing, sexiness, et al. How about modifying the likelyhood of crossing two 'distant' individuals (either deme-ish, sexiness, or whatever) based on the slope of the average fitness at the time. The purpose might be to expand the search, if you will, when things are slow but narrow it if things are progressing more quickly. -+- Sid From genetic-programming-owner@list.Stanford.EDU Fri Mar 18 20:57:37 1994 Return-Path: Received: from hamp by neural.hampshire.EDU (4.1/SMI-4.1) id AB09665; Fri, 18 Mar 94 20:57:36 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Fri, 18 Mar 94 20:23 EDT Received: from Xenon.Stanford.EDU (Xenon.Stanford.EDU [36.28.0.25]) by list.Stanford.EDU (8.6.7/8.6.4) with SMTP id MAA04264 for ; Fri, 18 Mar 1994 12:08:54 -0800 Received: by Xenon.Stanford.EDU (5.61+IDA/25-CS-eef) id AA15079; Fri, 18 Mar 94 12:07:04 -0800 Resent-Date: Fri, 18 Mar 94 20:45 EDT Date: Fri, 18 Mar 1994 12:07:02 -0800 (PST) From: Patrik D'haeseleer Subject: RE: Sexiness: Did I have it backwards? Resent-To: lee@neural.hampshire.EDU To: dfaulkne@LightStream.COM Cc: MJS14@vms.bton.AC.UK, GENETIC-PROGRAMMING@cs.stanford.EDU, dfaulkne@LightStream.COM Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <45D7C886251F02216A@hamp.hampshire.edu> Message-Id: <9403182007.AA15079@Xenon.Stanford.EDU> In-Reply-To: <9403181839.AA25801@cockatrice.LightStream.COM> from "Dave Faulkner" at Mar 18, 94 01:39:00 pm X-Mailer: ELM [version 2.4 PL21] Content-Type: text Content-Length: 3578 X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: dfaulkne@LightStream.COM X-Vms-Cc: MJS14@vms.bton.AC.UK, GENETIC-PROGRAMMING@cs.stanford.EDU, dfaulkne@LightStream.COM Status: RO Dave Faulkner writes: >Malcom SHUTE asks: >> >>BTW: Please could someone explain in a sentence (or two) what a deme is? >>I think I have got a general feel for what it is, by context, from discussions >>in this group. Thanks in advance. > >First, let me say that this is my understanding, not necessarily the right >one. Second, a far better source than me is the reference by Collins, >"Studies in Artificial Evolution", a PhD dissertation that is >easily accessed via anonymous ftp at ftp.cognet.ucla.edu, /pub/papers/alife. > >My view on what Collins' is doing is to run large GA's on a grid. ALthough >many dimentsions are possible lets use the two dimensional case. Each >chromosome is placed on the grid, and the grid is chopped up into equally >spaced areas, called "demes", dividing the population of chromosomes >into chromosome areas. > >The selection mechanism is modified in the following way: to choose a >member to reproduce, I perform a random walk within some particular area, >(deme) never crossing area borders, walking between k chromes, looking at their >fitness values. I choose to reproduce the most fit chrome that I have met >along my walk. To choose a mate, I perform a similar walk. As you can see, >I am isolating the selection of who reproduces and who mates with whom >by this imposition of a pretend geography created by the grid which I >started with. Hmm... if you're splitting up the grid explicitely into separate "deme areas", I don't see why you would still do a random walk for selection. There are basically two different approaches being used to implement demes these days. Either you "hardwire" the demes explicitely, by splitting up the population into small chunks and specifying inter and intra-deme breeding probabilities. Or you let demes evolve dynamically by adding some kind of incentive to breed with geographically, genotypically or phenotypically "close" individuals. (an example of this would be Dudey's current sexiness scheme, which would favor phenotypically close individuals) People who want to cash in on the possible performance improvements demes can offer, tend to prefer the "hardwired demes" approach, because it lends itself perfectly to parallelization: each deme can be run on a separate processor, and inter-processor communication only depends on the (small) migration rate between demes. On the other hand, allowing the dems to develop dynamically leads to a whole bunch of interesting new dynamical phenomena like deme migration and interaction. (which is why evolution types tend to use this scheme...) The method Collins used was to let demes evolve spontaneously through isolation by distance. Using a random walk on a grid, individuals tend to interact more with their immediate neighbors than with far-off individuals. This will lead to closer genotypical similarities between neighbors. The problem Collins was looking at with this setup had two symmetrical solutions, which means that he could easily show graphically which areas of the grid chose to go for one solution or the other by coloring the corresponding pixels black or white. In a non-deme population, you would expect some kind of gray mixture of both solutions, converging into a uniform "white" or "black" population. Using random walks for selection however, he got nice large globs of black and white which were a lot less likely to converge into one single solution. Since I'm writing this all from memory, I figure I'd better second the motion to read Collins PhD dissertation mentioned above as well. Patrik From genetic-programming-owner@list.Stanford.EDU Fri Mar 18 21:01:00 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA09672; Fri, 18 Mar 94 21:00:59 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Fri, 18 Mar 94 17:21 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.7/8.6.4) with SMTP id MAA04288 for ; Fri, 18 Mar 1994 12:26:50 -0800 Received: from odin.icd.ab.com by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA28777; Fri, 18 Mar 1994 12:25:24 -0800 Received: from gadwal.icd.ab.com (gadwal.icd.ab.com [130.151.132.71]) by odin.icd.ab.com (8.1C/5.6) with SMTP id PAA18511; Fri, 18 Mar 1994 15:25:14 -0500 Resent-Date: Fri, 18 Mar 94 19:13 EDT Date: Fri, 18 Mar 1994 15:25:14 -0500 From: "Mike J. Keith" Subject: RE: Sexiness: Did I have it backwards? Resent-To: lee@neural.hampshire.EDU To: dfaulkne@LightStream.COM, genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <45E495E5B69F021C04@hamp.hampshire.edu> Message-Id: <199403182025.PAA18511@odin.icd.ab.com> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: dfaulkne@LightStream.COM, genetic-programming@cs.stanford.EDU Status: RO >My view on what Collins' is doing is to run large GA's on a grid. ALthough >many dimentsions are possible lets use the two dimensional case. Each >chromosome is placed on the grid, and the grid is chopped up into equally >spaced areas, called "demes", dividing the population of chromosomes Actually, one does not explicitly chop up grids to form demes. They form naturaly by limiting the distance of the selection mechanism. You can do a tourney with individuals localized within a given distance or you can do a random walk etc. Mike Keith From genetic-programming-owner@list.Stanford.EDU Sun Mar 20 05:28:29 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA10822; Sun, 20 Mar 94 05:27:58 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Sun, 20 Mar 94 04:00 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.7/8.6.4) with SMTP id KAA04083 for ; Fri, 18 Mar 1994 10:42:36 -0800 Received: from dmc.com (HULK.DMC.COM) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA24801; Fri, 18 Mar 1994 10:41:28 -0800 Received: from oak by DMC.COM (MX V3.3 VAX) with UUCP; Fri, 18 Mar 1994 13:37:45 EST Received: by adapt.com (4.1/SMI-4.1) id AA07004; Fri, 18 Mar 94 13:30:11 EST Resent-Date: Sun, 20 Mar 94 04:12 EDT Date: Fri, 18 Mar 94 13:30:11 EST From: kinnear@adapt.COM Subject: RE: Sexiness: Did I have it backwards? Resent-To: lee@neural.hampshire.EDU To: kinnear@adapt.COM, derek@cs.wisc.EDU Cc: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <44D0340E027F023E75@hamp.hampshire.edu> Message-Id: <9403181830.AA07004@adapt.com> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: kinnear@adapt.COM, derek@cs.wisc.EDU X-Vms-Cc: genetic-programming@cs.stanford.EDU Status: O > From thehulk!cs.wisc.edu!derek Thu Mar 17 16:15:12 1994 > From: derek@cs.wisc.edu (Derek Zahn) > Subject: Re: Sexiness: Did I have it backwards? > To: kinnear@adapt.com > Date: Thu, 17 Mar 1994 08:52:52 -0600 (CST) > Cc: genetic-programming@cs.stanford.edu > X-Mailer: ELM [version 2.4 PL21] > Mime-Version: 1.0 > Content-Type> : > text/plain> ; > charset=US-ASCII> > Content-Transfer-Encoding: 7bit > Content-Length: 1034 > > Kim Kinnear: > > > I've looked a bit at the autocorrelation of random walks > > on GP landscapes (following Weinbeger's work with NK > > landscapes), and they *do* look pretty rugged (i.e. hard). > > > > You can read about it in the paper I submitted to WCCI on the > > GP ftp site: > > > > ftp.cc.utexas.edu > > /pub/genetic-programming/papers/kinnear.wcci.ps.Z > > I have a question about this paper. When you did your autocorrelation > measurements with the crossover operator, what population did you use? > The distribution of subtrees changes over time as adaptation occurs, > which could conceivably change the results. Did you look into this > at all? Do you have any thoughts on the matter? Good question. The autocorrelation values reported in the paper are all from generation 0, i.e. there had been no evolution on the population (yet). At one point I remember trying the autocorrelation on populations after they had found a successful individual (i.e. had stopped with success), but I don't remember that the results differed markedly from those in gen 0 (which implies that I *would* remember if they did, which I think I would). Certainly I didn't make enough runs on non-gen 0 populations to have an informed opinion about them and how they might differ from the gen 0 runs. It isn't hard to do this -- it only takes time, the only quantity *always* in short supply. I *do* know that there was no correlation between the results of a particular gen 0 autocorrelation and whether that particular gen 0 produced a successful individual (or how quickly that individual would be produced). The autocorrelations differed from each other a fair bit, which is why the graphs presented in the paper are the average of at least 10 runs each. > > In general for GA and GP, doesn't the fitness-proportional reproduction > make the sequence of fitnesses induced by the random walk process > progressively more and more non-Markovian as adaptation proceeds? There may well be some interesting information to be gleaned from autocorrelations on adapting populations -- but I'm not too sure just what that is. What would you expect to find and what would you do with it? Is there some hypothesis that you would expect to (in)validate by some information from autocorrelations of non-gen 0 populataions? > Weinberger seems to have some interesting things to say about this. > > Oh, and was the paper accepted? I like this kind of analysis a lot. Thanks, yes. I just heard yesterday that it was. Cheers -- Kim > > derek > From genetic-programming-owner@list.Stanford.EDU Sun Mar 20 05:33:00 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA10827; Sun, 20 Mar 94 05:32:25 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Sun, 20 Mar 94 04:02 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.7/8.6.4) with SMTP id KAA04071 for ; Fri, 18 Mar 1994 10:40:16 -0800 Received: from lightstream.LightStream.COM (lightstream.com) by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA24630; Fri, 18 Mar 1994 10:39:07 -0800 Received: from cockatrice.LightStream.COM by lightstream.LightStream.COM (4.1/SMI-4.1) id AA22967; Fri, 18 Mar 94 13:39:04 EST Received: by cockatrice.LightStream.COM (4.1/SMI-4.1) id AA25801; Fri, 18 Mar 94 13:39:02 EST Resent-Date: Sun, 20 Mar 94 04:11 EDT Date: Fri, 18 Mar 1994 13:39:00 -0500 From: Dave Faulkner Subject: RE: Sexiness: Did I have it backwards? Resent-To: lee@neural.hampshire.EDU To: MJS14@vms.bton.AC.UK Cc: GENETIC-PROGRAMMING , dfaulkne@LightStream.COM Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <44D04638E37F023E75@hamp.hampshire.edu> Message-Id: <9403181839.AA25801@cockatrice.LightStream.COM> In-Reply-To: Your message of "Fri, 18 Mar 1994 10:25:00 GMT." <199403181038.AA05969@Sunburn.Stanford.EDU> X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: MJS14@vms.bton.AC.UK X-Vms-Cc: GENETIC-PROGRAMMING , dfaulkne@LightStream.COM Status: O Malcom SHUTE asks: BTW: Please could someone explain in a sentence (or two) what a deme is? I think I have got a general feel for what it is, by context, from discussions in this group. Thanks in advance. ******* Since I haven't heard anything from the crowd I'll give it a shot (this may be because I'm on the east coast and things are slow in getting here from the mail daemon on the west coast? Maybe the list is long...). First, let me say that this is my understanding, not necessarily the right one. Second, a far better source than me is the reference by Collins, "Studies in Artificial Evolution", a PhD dissertation that is easily accessed via anonymous ftp at ftp.cognet.ucla.edu, /pub/papers/alife. My view on what Collins' is doing is to run large GA's on a grid. ALthough many dimentsions are possible lets use the two dimensional case. Each chromosome is placed on the grid, and the grid is chopped up into equally spaced areas, called "demes", dividing the population of chromosomes into chromosome areas. The selection mechanism is modified in the following way: to choose a member to reproduce, I perform a random walk within some particular area, (deme) never crossing area borders, walking between k chromes, looking at their fitness values. I choose to reproduce the most fit chrome that I have met along my walk. To choose a mate, I perform a similar walk. As you can see, I am isolating the selection of who reproduces and who mates with whom by this imposition of a pretend geography created by the grid which I started with. Run like this, we have simply a bunch of isolated GAs. The twist is to allow diffusion: periodically (a fairly low probability) I choose a member of one of the neighboring areas (demes) instead of a member in my own area (deme) to reproduce or mate. This allows convergence to occur in each deme independently for some time, but then we break the isolation/independence with a little injection of genetic material from a neighboring proto-niche (deme). This genetic diffusion is an attempt to prevent premature convergence to local optima by assuming that among the population of demes there is a potential for a greater diversity. Thus cross-deme mixing is the balance to the arbitrary imposition of isolation on sub-populations. The idea of demes is of populations of sub-populations. I hope this helps! - Dave Faulkner From genetic-programming-owner@list.Stanford.EDU Wed Mar 30 04:06:38 1994 Return-Path: Received: from hamp.hampshire.edu by neural.hampshire.EDU (4.1/SMI-4.1) id AA05260; Wed, 30 Mar 94 04:06:36 EST Resent-From: genetic-programming-owner@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Received: from list.Stanford.EDU by hamp.hampshire.edu; Wed, 30 Mar 94 04:07 EDT Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [36.8.0.178]) by list.Stanford.EDU (8.6.7/8.6.4) with SMTP id GAA18156 for ; Mon, 28 Mar 1994 06:45:35 -0800 Received: from atc.boeing.com by Sunburn.Stanford.EDU with SMTP (5.67b/25-SUNBURN-eef) id AA03423; Mon, 28 Mar 1994 06:44:30 -0800 Received: by atc.boeing.com (5.57) id AA08305; Mon, 28 Mar 94 06:46:04 -0800 Received: from hsvaic.hv.boeing.com by splinter.boeing.com with SMTP (16.6/16.2) id AA19467; Mon, 28 Mar 94 06:46:33 -0800 Received: by hsvaic.hv.Boeing.COM (4.1/SMI-4.1-hsvaic-s.7) id AA22441; Mon, 28 Mar 94 08:46:25 CST Resent-Date: Wed, 30 Mar 94 04:07 EDT Date: Mon, 28 Mar 1994 08:46:25 -0600 From: george@hsvaic.hv.boeing.COM Subject: Sexiness: psychological experimental evidence Resent-To: lee@neural.hampshire.EDU To: genetic-programming@cs.stanford.EDU Errors-To: mail-errors@list.Stanford.EDU Resent-Message-Id: <3CF54191AB5F03BC36@hamp.hampshire.edu> Message-Id: <9403281446.AA22441@hsvaic.hv.Boeing.COM> X-Mailer: Mail User's Shell (7.2.3 5/22/91) X-Envelope-To: lee@neural.hampshire.edu X-Vms-To: genetic-programming@cs.stanford.EDU Status: RO The recent discussions of sexiness came to mind when I saw this: Excerpts from an article in Science News v.145, n.12, 3/19/94, p.182, "Facial beauty may lie more than skin deep", by Bruce Bower, which cites an article in March 17 Nature by three psychologists. "...the shape of the most fetching faces differs in important ways from the average shape of all faces in a population, contend David I. Perret and Keith A. May, both of the University of St. Andrews in Fife, England, and Sakiko Yoshikawa of Otemon Gakuin University in Osaka, Japan. This conclusion contrasts with that of another study, which places averageness at the center of facial attractiveness (SN: 5/12/90, p.298). ... "An initial composite came from pictures of 60 white British women between 20 and 30 years old. A computer fashioned an `average' image from measurements of the shape and position of 224 anatomical features on each face. A second composite represented the average of 15 of those faces given the highest attractiveness ratings by 36 male and female British adults. A third computer-derived face served as a caricature of the second image by exaggerating differences between it and the first composite. "Nearly all of a second set of 36 comparable volunteers rated the second image more attractive than the first and the caricature as more appealing than the second composite. "Perret's team then generated three types of composites from the faces of 342 Japanese women age 18 and 19. In tests with 26 Japanese and 36 British men and women, the caricature again garnered the highest attractiveness ratings, followed by a composite of the 16 most attractive individuals. "Another 30 British volunteers similarly rated composites of British male faces, the scientists report. An `attractive' male composite and its caricature yielded comparably high ratings. "Highly attractive male and female composites share some common traits, Perrett says, such as larger eyes relative to face size and shorter distances from mouth to chin and from nose to mouth. "The results coincide with research directed by Michael R. Cunningham of the University of Louisville (Ky.). Cunningham argues that truly beautiful faces display atypical features (SN 10/21/91, p.234). "The Louisville psychologist theorizes that five categories of human facial features have evolved... ... "The average of all facial features in a population provides the fundamental building block of facial beauty, counters Judith H. Langlois of the University of Texas at Austin. Humans may have evolved to view an extremely `average' face as closer to a prototype, or best example, of attractiveness, adds Lori A. Roggman of Utah State University in Logan. They reject the division of facial attractiveness into separate categories. I've drawn some immediate conclusions about what we might be able to do to mimic this in GAs, but I won't clutter this initial message with them. I wanted to see how others reacted. And maybe Peter Dudey would like to try this in his experiments. --george George Williams Huntsville Advanced Computing Group The Boeing Company Internet: George.Williams@hsvaic.hv.boeing.com POBox 240002, M/S JN-55 UUCP: ...!uw-beaver!bcsaic!hsvaic!george Huntsville AL 35824-6402 Phone: 205+461-2950 FAX: 205+461-2286