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.

Share

Description

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

Tags

Transcript

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 ﬁnd that the coevolutionary model has a relatively large efﬁ-cacy: 86 out of 100 (86%) of the simulations produce high quality strategies. Incontrast, the evolutionary model has a very low efﬁcacy: a high quality strategy isfound in only two out of 100 runs (2%). We show that the increased efﬁcacy 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 ﬁt-ness of evolving solutions depends on the state of other, coevolving individuals ratherthan a ﬁxed evaluationfunction. Coevolutionary search involves either one or two pop-ulations. In the ﬁrst case individual ﬁtness is based on competitions among individualsin the population (Rosin & Belew, 1997; Angeline & Pollack, 1993; Sims, 1994). Inthe second case the ﬁtness 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 efﬁciency of coevolutionarysearchalgorithms arethe gaininefﬁciencyoftheevaluationofevolvingsolutions (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.,ﬁtness 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 ﬁtness shar-ing to produce and maintain diverse populations (Rosin & Belew, 1997) or techniquessuch as lifetime ﬁtness 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. Themostsigniﬁcant result of the study is the difference in efﬁcacy of the two models on a giventask. Whereas the coevolutionary model ﬁnds solutions that use high quality strategiesin 86 out of 100 runs (86%), the evolutionary model ﬁnds 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 efﬁcacy, 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 classiﬁcation task
The task given to both models is the density classiﬁcation task for cellular automata(CAs) (Packard, 1988; Mitchell
et al.
, 1994). The density classiﬁcation task is deﬁnedfor 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, deﬁned 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 deﬁned. The CAs in our studyoperate on a lattice of size 149 whose initial conﬁguration 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 classiﬁes the bitstring as density class 0. If the CA settles into a homogeneous state of all 1s it classiﬁesthe bit string as density class 1. If the CA does not settle into a homogeneous state itmakes by deﬁnition a mis-classiﬁcation. 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 classiﬁcation 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 conﬁguration in the diagram on the left has low densityand is correctly classiﬁed as class 0. The initial conﬁguration in the diagram on theright has high density. It contains a sufﬁciently large block of 1s, which expands to ﬁllup the lattice, resulting in a correct classiﬁcation as class 1. (Adapted from Mitchell
et al.
, 1996.)AnobjectivemeasureoftheclassiﬁcationaccuracyofaCAisits
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 conﬁguration in the diagram on the left has low density and the correct clas-siﬁcation of all 0s. The high-density initial conﬁguration on the right is also correctlyclassiﬁed. (Adapted from Mitchell
et al.
, 1996.)
, deﬁnedas the fraction of correct classiﬁcations 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 difﬁcultycases 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 classiﬁes 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 classiﬁed correctly. Block-expanding strategies, illustrated in ﬁg.1, are reﬁnements of the default strategy. In a block-expanding strategy bit stringsare classiﬁed to one density class, for instance density class 0 (left-hand side of ﬁg.1), unless the bit string contains a sufﬁciently large block of, in this case, 1s, whichresults in the block expanding to cover the whole lattice, yielding a classiﬁcation of density class 1 (right-hand side of ﬁg. 1). The deﬁnition of “sufﬁciently large” block depends on the particular CA, but typically means blocks equal to or larger than theCA neighborhood size of 7 cells. This “strategy” reﬂects 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 classiﬁed accordingly. Block-expanding strategies typicallyhave performance values between 0.55 and 0.72 on bit strings of length 149. Finally,particle strategies, illustrated in ﬁg. 2, use interactions between meso-scale patternsin order to classify bit strings (Crutchﬁeld & Mitchell, 1995; Das
et al.
, 1994). Theytypically have performance values of 0.72 and higher on bit strings of length 149.The three classiﬁcation strategies, default, block-expanding, and particle, exhibitincreasing computational complexity (Crutchﬁeld & Mitchell, 1995). In evolutionary4
search runs one typically sees a series of epochs in which default strategies are evolvedﬁrst, then block-expanding strategies, and ﬁnally (on some runs) particle strategies(Crutchﬁeld & Mitchell, 1995). The highest observed performance to date of a particleCA on the density-classiﬁcation task is 0.86 on bit strings of length 149 (Juill´e &Pollack, 2000).A number of research groups have used evolutionary search to ﬁnd strategies forthe CA density classiﬁcation 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 ﬁtness of a CA is the fraction of correct classiﬁcations it makes on a small random sample of bit strings interpreted asinitial conﬁgurations (ICs) for the CA. In a coevolutionary setup the bit strings, or ICs,make up the second population and the ﬁtness 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 difﬁcult to evolve high-performance CAs; only asmall number of runs produce CAs that use particle strategies. If we deﬁne the
efﬁ-cacy
of an evolutionary search model as the percent of runs of that model that produceparticle strategies, then the efﬁcacy 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 efﬁcacy (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 densityclassiﬁcation task generally showRed Queen dynamics of the CAs and ICs (Paredis, 1997; Pagie & Hogeweg, 2000;Juill´e & Pollack, 2000). For the density classiﬁcation 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 ﬁtness function used to evaluate theICs which imposes stabilizing selection on the ICs toward strings that can be classiﬁedmore easily by CAs. Here we use the same IC ﬁtness function
¢¡¤£¦¥¨§©
:
¢¡¤£¦¥§©
¢
if classiﬁed correctly
!"#%$
¡¤£¦¥§©'&)(0
otherwise.5

Related Search

World Of A Song Of Ice And FireA Song Of Ice And FireA comparison of competition measures for preda Review of Thermal and Mechanical Analysis iInternational Association Of Machinists And AHistory of Science and Medicine In Medieval aTheories of Ritual and Myth, Animal Studies aA History of the Internet and the Digital FutCell and Molecular Biology of Medicinal and AAn African Journal of Philosophy and Public A

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