Genetic Algorithms Digest Thursday, 16 August 1990 Volume 4 : Issue 16 - Send submissions to GA-List@AIC.NRL.NAVY.MIL - Send administrative requests to GA-List-Request@AIC.NRL.NAVY.MIL Today's Topics: **** SPECIAL ISSUE OF WORKSHOP ABSTRACTS **** - Message from moderator - The Classifier System Concept Description Language Lashon Booker - A Study of Reproduction in Generational and Steady State GAs Gilbert Syswerda - Spurious Correlations and Premature Convergence in Genetic Algorithms J. David Schaffer, Larry J. Eshelman, and Daniel Offutt - The CHC Adaptive Search Algorith: How to have Safe Search When Engaging in Nontraditional Genetic Recombination Larry Eshelman - Weakest Conditions for Implicit Parallelism John Grefenstette - An Analysis of Multi-point Crossover K. De Jong & Wm. Spears ****************************************************************************** CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) Conference on Simulation of Adaptive Behavior, Paris (v3n21) Sep 24-28, 1990 Workshop Parallel Prob Solving from Nature, W Germany (v4n5) Oct 1-3, 1990 2nd Intl Conf on Tools for AI, Washington, DC (v4n6) Nov 6-9, 1990 4th Intl. Conference on Genetic Algorithms (v4n9) Jul 14-17, 1991 (Send announcements of other activities to GA-List@aic.nrl.navy.mil) ****************************************************************************** Date: Wed, 15 Aug 1990 From: Alan C. Schultz (GA-List Moderator) Subject: Special issue This issue is comprised of abstracts from talks presented at the Foundations of Genetic Algorithms Workshop held July 15-18, 1990, at Indiana University. The workshop was organized by Gregory Rawlins. This is, hopefully, the first of several such issues; which is my way of saying that we would like to get abstracts from those who have not yet sent them. --Alan ----------------------------------- Date: Tue, 24 Jul 90 09:08:45 EDT From: booker@AIC.NRL.Navy.Mil Subject: Workshop abstract The Classifier System Concept Description Language by Lashon B. Booker Legitimate concerns have been raised about the expressive adequacy of the classifier language. This paper shows that many of those concerns stem from the inadequacies of the binary encodings typically used with classifier systems, not the classifier language per se. In particular, we describe some straightforward binary encodings for attribute-based instance spaces. These encodings give classifier systems the ability to represent ordinal and nominal attributes as expressively as most symbolic machine learning systems, without sacrificing the building blocks required by the genetic algorithm. ----------------------------------- Date: Wed, 1 Aug 90 19:56:18 EDT From: Gilbert Syswerda Subject: Workshop Abstract A Study of Reproduction in Generational and Steady State Genetic Algorithms Two techniques of population control are currently used in the field of genetic algorithms: generational and steady state. It has become apparent that the two techniques are actually quite different and that steady state in general performs much better than generational. In this paper, I study the performance of each with regard to reproduction. ----------------------------------------- Date: Mon, 30 Jul 90 07:41:34 EDT From: ds1@philabs.Philips.Com (Dave Schaffer) Subject: workshop abstract Spurious Correlations and Premature Convergence in Genetic Algorithms J. David Schaffer Larry J. Eshelman Daniel Offutt Philips Laboratories, North American Philips Corporation, 345 Scarborough Road, Briarcliff Manor, New York 10510 ABSTRACT What distinguishes genetic algorithms (GAs) from other search methods is their inherent exploitive sampling ability known as implicit parallelism. We argue, however, that this exploitive behavior makes GAs sensitive to spurious correlations between schemata that contribute to performance and schemata that are parasitic. If not combatted, this can lead to premature convergence. Among crossover operators, some are more disruptive than others, and traditional arguments have held that less disruption is better for implicit parallelism. To explore this issue we examine the behavior of two crossover operators, two-point and uniform crossover, on a problem contrived to contain specific spurious correlations. The more disruptive operator, uniform crossover, is more effective at combatting the spurious correlations at the expense of also more disruption of the effective schemata. Elitist selection procedures are shown to be able to ameliorate this somewhat, suggesting that research into ways of dealing with the effects of the inevitable sampling errors may lead to generally more robust algorithms. ------------------------------------ Date: Tue, 7 Aug 90 09:03:12 EDT From: lje@philabs.Philips.Com (Larry Eshelman) Subject: Abstract, GA Workshop ABSTRACT This paper describes and analyzes CHC, a nontraditional genetic algorithm which combines a conservative selection strategy that always preserves the best individuals found so far with a radical (highly disruptive) recombination operator that produces offspring that are maximally different from both parents. It is argued that the traditional reasons for preferring a recombination operator with a low probability of disrupting schemata do not hold when such a conservative selection strategy is used, and that, on the contrary, at least some highly disruptive crossover operators provide more effective search. Empirical evidence is provided to support these claims. --Larry Eshelman -------------------------------- Date: Wed, 15 Aug 90 14:45:02 EDT From: gref@AIC.NRL.Navy.Mil Subject: FOGA-90 Abstract Weakest Conditions for Implicit Parallelism John Grefenstette Many interesting varieties of genetic algorithms have been designed and implemented in the last fifteen years. One way to improve our understanding of genetic algorithms is to identify properties that are invariant across these seemingly different versions. This talk focuses on invariances among GAs that differ along two dimensions: (1) the way user-defined objective function is mapped to a fitness measure, and (2) the way the the fitness measure is used to assign offspring to parents. A GA is called admissible if it meets what seem to be the weakest reasonable requirements along these dimensions. It is shown that any admissible GA exhibits a form of implicit parallelism. -------------------------------- Date: Thu, 16 Aug 90 12:38:44 EDT From: dejong@AIC.NRL.Navy.Mil Subject: abstract An Analysis of Multi-point Crossover K. De Jong & Wm. Spears At the FOGA Workshop, we presented some theoretical results on n-point and uniform crossover. This analysis extended the work from De Jong's thesis, which dealt with disruption of n-point crossover on 2nd order schemata. We have made various extensions to this theory: 1) An analysis of the disruption of n-point crossover on kth order schemata. 2) The computation of tighter bounds on the disruption caused by n-point crossover, by examining the cases in which both parents are members of the schema (i.e., the values of the defining bits are the same). 3) An analysis of the disruption caused by uniform crossover on kth order schemata. Disruption of schemata is important for understanding the effects of crossover when populations are diverse (typically early in the evolutionary process). If a population becomes quite homogeneous, another factor becomes important: the probability that the offspring produced by crossover will be different than their parents in some way (thus generating a new sample). These probability computations turn out to be the same as the above disruption computations. In other words, those operators that are more disruptive are also more likely to create new individuals from parents with nearly identical genetic material. These theoretical results appear to explain many of the conflicting experimental results concerning the advantages/disadvantages of 1-pt, 2-pt, and uniform crossover and suggest an interplay with population size. With a small population, more disruptive crossover operators such as uniform or n-pt ( n>2) yield better results because they help overcome the limited carrying capacity of smaller populations and the tendency for more homogeneity. However, with larger populations, less disruptive crossover operators (2-pt) work better, as suggested by Holland's original analysis. -------------------------------- End of Genetic Algorithms Digest ********************************