A comparison of evolutionary and coevolutionary search

of 18

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
18 pages
3 downs
Previous work on coevolutionary search has demonstrated both successful and unsuccessful applications. As a step in explaining what factors lead to success or failure, we present a comparative study of an evolutionary and a coevolutionary search
  A comparison of evolutionary and coevolutionarysearch Ludo Pagie   and Melanie MitchellSanta Fe Institute1399 Hyde Park RoadSanta Fe, NM87501, USludo@santafe.edumm@santafe.eduphone: (+1)(505)-984-8800fax: (+1)(505)-982-0565 Abstract Previous work on coevolutionary search has demonstrated both successful andunsuccessful applications. As a step in explaining what factors lead to success orfailure, we present a comparative study of an evolutionary and a coevolutionarysearch model. In the latter model, strategies for solving a problem coevolve withtraining cases. We find that the coevolutionary model has a relatively large effi-cacy: 86 out of 100 (86%) of the simulations produce high quality strategies. Incontrast, the evolutionary model has a very low efficacy: a high quality strategy isfound in only two out of 100 runs (2%). We show that the increased efficacy in thecoevolutionary model results from the direct exploitation of low quality strategiesby the population of training cases. We also present evidence that the generality of the high-quality strategies can suffer as a result of this same exploitation. 1 Introduction Coevolutionary search is an extension of standard evolutionary search in which the fit-ness of evolving solutions depends on the state of other, coevolving individuals ratherthan a fixed evaluationfunction. Coevolutionary search involves either one or two pop-ulations. In the first case individual fitness is based on competitions among individualsin the population (Rosin & Belew, 1997; Angeline & Pollack, 1993; Sims, 1994). Inthe second case the fitness of individuals is based on their behavior in the context of theindividuals of the other population (Hillis, 1990; Juill´e & Pollack, 1996; Paredis, 1997; ¡ Current address: Department of Zoology, University of Oxford, South Parks Road, Oxford OX1 3PS,UK 1  Pagie & Hogeweg, 1997). This latter type of coevolutionary search is often describedas “host-parasite”, or “predator-prey” coevolution.The reasons typically cited for the expected increased success and efficiency of coevolutionarysearchalgorithms arethe gaininefficiencyoftheevaluationofevolvingsolutions (Hillis, 1990), the possible automatic adjustment of the selection gradientwhich is imposed on the evolving solutions (Juill´e & Pollack, 2000), and the potentialopen-ended nature of coevolutionary systems (Rosin & Belew, 1997; Ficici & Pollack,1998).Some successful applications of coevolutionary search have used spatially embed-ded systems (Hillis, 1990; Husbands, 1994; Pagie & Hogeweg, 1997). In such systemsthe individuals are distributed on a regular grid and the evolutionary processes (i.e.,fitness evaluation, selection, and, if applicable, crossover) take place locally amongneighboring individuals. Hillis (1990) and Pagie & Hogeweg (1997) gave examplesof spatially embedded coevolutionary models that were more successful than spatiallyembedded, but otherwise standard, evolutionary models for the same search problem.Other successful applications of coevolution have used techniques such as fitness shar-ing to produce and maintain diverse populations (Rosin & Belew, 1997) or techniquessuch as lifetime fitness evaluation to retain good solutions in the populations (Paredis,1997).In contrast to the successful applications of coevolutionary search there are a num-ber of studies showing that coevolutionary dynamics can lead to non-successful searchas well. Such cases are often characterized by the occurrence of  Red Queen dynamics (Paredis, 1997; Shapiro, 1998; Pagie & Hogeweg, 2000; Juill´e & Pollack, 2000), spe-ciation (Pagie, 1999), or mediocre stable states (Pollack  et al. , 1997; Juill´e & Pollack,2000).In earlier work it was shown how Red Queen dynamics can occur in a spatiallyembedded coevolutionary model under continuous mixing   , while high quality solu-tions evolve in the same model if mixing is omitted so that spatial patterns can form(Pagie & Hogeweg, 2000). In the latter case speciation events can result in persistingsub-species, whereas in the former case global competitive exclusion occurs on a muchshorter time-scale and tends to converge the population to one species. Heterogeneityin the populations prevents Red Queen dynamics from persisting. Instead, evolutionproceeds to produce general, high quality solutions (Pagie & Hogeweg, 2000), or re-sults in very diverse populations in which the individuals exhibit sub-optimal behavior(Pagie, 1999).Here we report results from a follow-up comparative study of a coevolutionary andastandardevolutionarysearchprocess, bothofwhichareembeddedinspace. Themostsignificant result of the study is the difference in efficacy of the two models on a giventask. Whereas the coevolutionary model finds solutions that use high quality strategiesin 86 out of 100 runs (86%), the evolutionary model finds such a solution only twice in100 runs (2%). By comparing the evolutionary dynamics in the two models we try tocharacterize the processes that lead to this large difference in search efficacy, therebypinpointing important aspects of coevolutionary search. ¡ Continuous mixing in a spatial model approximates a non-spatial model in which selection and recom-bination take place without regard for spatial location of individuals. 2  2 CA density classification task The task given to both models is the density classification task for cellular automata(CAs) (Packard, 1988; Mitchell et al. , 1994). The density classification task is definedfor one-dimensional, binary state CAs with a neighborhood size of 7; that is, at eachtime step a cell’s new state (0 or 1) is determined by its current state and the states of itsthreeneighborsoneachside. TheCAs employperiodic (circular) boundaryconditions.The task for a CA is to classify bit strings on the basis of density, defined as thefraction of 1s in the string. If the bit string has a majority of 0s it belongs to densityclass 0; otherwise it belongs to density class 1. Here we restrict our study to bit stringsof length 149, which means that the majority is always defined. The CAs in our studyoperate on a lattice of size 149 whose initial configuration of states is the given bitstring. (Note that the performance of a CA on this task generally degrades with in-creasing length of the bit string.) A CA makes 320 iterations (slightly more than twicethe lattice size). If the CA settles into a homogeneous state of all 0s it classifies the bitstring as density class 0. If the CA settles into a homogeneous state of all 1s it classifiesthe bit string as density class 1. If the CA does not settle into a homogeneous state itmakes by definition a mis-classification. Land & Belew (1995) showed that no two-state CA exists that can correctly classify all possible bit strings of arbitrary lengths,but did not give an upper bound on possible classification accuracy. 0 Time 148148 Site 0148 Site 0 Figure 1: Space-time diagrams illustrating the behavior of a typical block-expandingstrategy. The 149-cell one-dimensional CA lattice is displayed on the horizontal axis,with time increasing down the page. Cells in state 0 are colored white; cells in state 1are colored black. The initial configuration in the diagram on the left has low densityand is correctly classified as class 0. The initial configuration in the diagram on theright has high density. It contains a sufficiently large block of 1s, which expands to fillup the lattice, resulting in a correct classification as class 1. (Adapted from Mitchell et al. , 1996.)AnobjectivemeasureoftheclassificationaccuracyofaCAisits  performance value3  0 Time 148148 Site 0148 Site 0 Figure 2: (a) Space-time diagram illustrating the behavior of a typical particle strategy.The initial configuration in the diagram on the left has low density and the correct clas-sification of all 0s. The high-density initial configuration on the right is also correctlyclassified. (Adapted from Mitchell et al. , 1996.)     , definedas the fraction of correct classifications of  ¡£¢¥¤ strings, eachselected from an“unbiased” distribution—a binomial density distribution centered around density 0.5.(This distribution results in strings with density very close to 0.5—the most difficultycases to correctly classify.) An important characteristic of a CA is the type of strategythat it uses in order to classify a string. The three main strategies discussed by Mitchell etal. (1994)—alldiscoveredbytheirgeneticalgorithm—aredefault, block-expanding,and particle. The default strategy classifies all bit strings to a single density class (class0 or class 1) by always iterating to a homogeneous state of all 0s or all 1s. Thus thereare two types of default strategies; default-0 and default-1. Default strategies haveperformance valuesofapproximately0.5,since approximatelyhalfofa random sampleof  ¡£¢¤ strings will be classified correctly. Block-expanding strategies, illustrated in fig.1, are refinements of the default strategy. In a block-expanding strategy bit stringsare classified to one density class, for instance density class 0 (left-hand side of fig.1), unless the bit string contains a sufficiently large block of, in this case, 1s, whichresults in the block expanding to cover the whole lattice, yielding a classification of density class 1 (right-hand side of fig. 1). The definition of “sufficiently large” block depends on the particular CA, but typically means blocks equal to or larger than theCA neighborhood size of 7 cells. This “strategy” reflects the fact that the presenceof a block of 1s (0s) in a 149-bit string roughly correlates with overall high (low)density, and the string is classified accordingly. Block-expanding strategies typicallyhave performance values between 0.55 and 0.72 on bit strings of length 149. Finally,particle strategies, illustrated in fig. 2, use interactions between meso-scale patternsin order to classify bit strings (Crutchfield & Mitchell, 1995; Das et al. , 1994). Theytypically have performance values of 0.72 and higher on bit strings of length 149.The three classification strategies, default, block-expanding, and particle, exhibitincreasing computational complexity (Crutchfield & Mitchell, 1995). In evolutionary4  search runs one typically sees a series of epochs in which default strategies are evolvedfirst, then block-expanding strategies, and finally (on some runs) particle strategies(Crutchfield & Mitchell, 1995). The highest observed performance to date of a particleCA on the density-classification task is 0.86 on bit strings of length 149 (Juill´e &Pollack, 2000).A number of research groups have used evolutionary search to find strategies forthe CA density classification task as a paradigm for the evolution of collective com-putation in locally interacting dynamical systems (e.g., Mitchell et al. , 1996; Juill´e &Pollack, 2000). In a standard evolutionary setup, the fitness of a CA is the fraction of correct classifications it makes on a small random sample of bit strings interpreted asinitial configurations (ICs) for the CA. In a coevolutionary setup the bit strings, or ICs,make up the second population and the fitness evaluation of the CAs is based on theevolving ICs. Coevolutionary models which focus on this task were previously studiedby Paredis (1997), Juill´e & Pollack (2000), and Pagie & Hogeweg (2000).Previous studies indicate that, under a standard evolutionary model as well as pre-vious coevolutionary models, it is difficult to evolve high-performance CAs; only asmall number of runs produce CAs that use particle strategies. If we define the effi-cacy of an evolutionary search model as the percent of runs of that model that produceparticle strategies, then the efficacy of standard evolutionary and previous coevolution-ary search models has been found to fall somewhere between 0% and 40% (Mitchell et al. , 1996; Werfel et al. , 2000; Juill´e & Pollack, 2000; Oliveira et al. , 2000), withthe remaining runs producing block-expanding CAs (see Mitchell et al. , 1994 for somecomments on this issue). Two studies report very high efficacy (Andre et al. , 1996;Juill´e & Pollack, 2000) but in these cases the computational resources used per simu-lation were orders of magnitude higher than used here or in the other studies.Coevolutionarymodelsappliedto theCA densityclassification task generally showRed Queen dynamics of the CAs and ICs (Paredis, 1997; Pagie & Hogeweg, 2000;Juill´e & Pollack, 2000). For the density classification task this type of evolutionarydynamics is characterized byoscillations in the types of ICs and CAs that are presentinthe population. The IC population oscillates, with a fairly constant frequency, betweenbit strings with density less than 0.5 and bit strings with density greater than 0.5. TheCA population oscillates at a similar frequency between default-0 strategies, whichcorrectlyclassifytheformer, anddefault-1strategies,whichcorrectlyclassifythelatter.Paredis (1997) circumvented Red Queen dynamics by replacing the coevolution of theICs by randomly generated ICs. Juill´e & Pollack (2000) changed the coevolutionarysetup by introducing a limit on the selection of ICs such that it was constrained bythe ability of the CAs. Pagie & Hogeweg (2000) embedded the coevolutionary modelin a 2D grid and introduced an extension on the fitness function used to evaluate theICs which imposes stabilizing selection on the ICs toward strings that can be classifiedmore easily by CAs. Here we use the same IC fitness function  ¢¡¤£¦¥¨§© :  ¢¡¤£¦¥§©  ¢ if classified correctly !"#%$ ¡¤£¦¥§©'&)(0 otherwise.5
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks