Improving Evolvability Through Novelty Search And Self .

Improving Evolvability through Novelty Search andSelf-AdaptationIn: Proceedings of the 2011 IEEE Congress on Evolutionary Computation (CEC 2011). Piscataway, NJ: IEEEJoel LehmanKenneth O. StanleyDepartment of Electrical Engineeringand Computer ScienceUniversity of Central FloridaOrlando, Florida 32826–2363Email: jlehman@eecs.ucf.eduDepartment of Electrical Engineeringand Computer ScienceUniversity of Central FloridaOrlando, Florida 32826–2363Email: kstanley@eecs.ucf.eduAbstract—A challenge for current evolutionary algorithms is toyield highly evolvable representations like those in nature. Suchevolvability in natural evolution is encouraged through selection:Lineages better at molding to new niches are less susceptibleto extinction. Similar selection pressure is not generally presentin evolutionary algorithms; however, the first hypothesis in thispaper is that novelty search, a recent evolutionary technique,also selects for evolvability because it rewards lineages able tocontinually radiate new behaviors. Results in experiments ina maze-navigation domain in this paper support that noveltysearch finds more evolvable representations than regular fitnessbased search. However, though novelty search outperforms fitnessbased search in a second biped locomotion experiment, it provesno more evolvable than fitness-based search because delicatelybalanced behaviors are more fragile in that domain. The secondhypothesis is that such fragility can be mitigated through selfadaption, whereby genomes influence their own reproduction.Further experiments in fragile domains with novelty searchand self-adaption indeed demonstrate increased evolvability,while, interestingly, adding self-adaptation to fitness-based searchdecreases evolvability. Thus, selecting for novelty may oftenfacilitate evolvability when representations are not overly fragile;furthermore, achieving the potential of self-adaptation may oftencritically depend upon the reward scheme driving evolution.I. I NTRODUCTIONThe philosopher Diderot [5] once wrote, “It seems thatNature has taken pleasure in varying the same mechanismin an infinity of different ways . She abandons one classof production only after having multiplied the individuals ofit in all possible forms.” Naturalists of all generations havebeen similarly inspired by the vast productivity and creativityof evolution. Such diversity in nature highlights the significantevolvability of natural organisms; the tree of life branches everoutwards with high degree.Evolvability, or the capacity of an individual or a populationto further evolve, has often been studied in the context ofnatural evolution [3, 12, 20, 31]. A potential explanation fornatural evolution’s propensity to generate a wide diversity oforganisms is that greater evolvability is selected for. That is,evolvable lineages that are able to modify into more nicheshave less chance of going entirely extinct [3, 12]. Becauseof the apparent chasm between the evolvability of organismsin natural evolution and in artificial systems, measuring andincreasing evolvability has also been the subject of manystudies within evolutionary computation (EC) [6, 9, 22, 31].Traditional evolutionary algorithms (EAs), which typicallyare driven to converge to a fitness optimum, contrast with natural evolution and its consistent exploratory diffusion throughniches. Such EAs thus often lack selection pressure towardsgreater evolvability. That is, lineage-level selection is confounded when evolution converges to a single lineage; in suchcases there is no variety of lineages upon which a higher levelof selection pressure can act. Thus when optimizing staticfitness functions like those prevalent in EC, fitness may bean impoverished indicator of evolvability.In contrast, a recent technique in EC, novelty search [16],directly rewards individuals exhibiting novel behaviors and isinspired by natural evolution’s continual production of novelforms. Such selection for novelty naturally maintains a widediversity of behaviors and lineages more similar in spirit thantraditional EAs to the accumulation of niches seen in nature.The first hypothesis in this paper is thus that novelty searchmay also indirectly select for evolvable lineages just as naturalevolution does. That is, in the long run, lineages in noveltysearch more predisposed to producing novelty will generatemore offspring than those lineages that are less evolvable. Theconverse does not hold for traditional objective-based EAs:Once such EAs converge to a local optimum, selection rewardsindividuals with decreased variability that are able to achieveever slighter fitness increases [31]; the prototypical fitnesscurve in EC illustrates that in general as fitness increases itbecomes increasingly difficult to further increase it.In this paper, following Kirschner and Gerhart [12], evolvability is defined as the capacity of an organism to “generate heritable phenotypic variation.” While evolvability isoften discussed in relation to adaptation, the chosen definition reflects a growing consensus in biology that phenotypicvariability in its own right deserves study in the contextof evolvability [3, 12, 20, 31]. Thus the evolvability of anindividual is accordingly quantified in this paper by measuringits propensity for phenotypic variation [3]. Supporting thefirst hypothesis, experiments in a maze navigation domaindemonstrate that novelty search does discover more evolvable

individuals, populations, and solutions than traditional fitnessbased search. However, in a challenging biped domain, thoughit outperforms fitness-based search, novelty search is no moreevolvable than fitness-based search.This discrepancy leads to the insight that fragile domains,i.e. those in which nearly every mutation is fatal, can precludesearch methods from finding evolvable representations. Thatis, the weak indirect selection pressure towards evolvabilityin novelty search can be overpowered by the combination ofuniform mutation operators with an unforgiving domain.Yet the second hypothesis is that self-adaptation can restorethe evolvability of novelty search. Thus to remedy domainfragility, both novelty search and fitness-based search are extended with the capability to self-adapt mutational parameters,effectively giving the genome greater control over the creationof its offspring. An important result is that the greater controlprovided by such self-adaptation does not help fitness-basedsearch, which exploits self-adaptation to more effectivelyconverge as it nears local fitness optima [4, 7, 24]. However,it does allow novelty search to discover more evolvablerepresentations and sometimes to perform better.There are two conclusions. The first is that because novelty search indirectly selects for evolvable lineages, it mayoften discover more evolvable representations than traditionalobjective-based search. The second conclusion is that whileself-adaptation has the potential to increase both performance and evolvability, achieving the latent potential of selfadaptation may be more effective in evolutionary algorithmsthat encourage novelty.II. BACKGROUNDEvolvability in both natural and artificial systems is reviewed in this section, as is the neuroevolution method appliedin the experiments in this paper. Finally, novelty search, theevolutionary technique inspired by natural evolution’s continual production of diverse novel forms, is explained.A. Evolvability in Natural Evolution and ECNatural evolution has discovered flexible, highly evolvablerepresentations that have facilitated the discovery of widely diverse organisms. An important question that could inform ECis what properties of natural evolution led to such evolvability?At the same time, EC enables studies of evolvability that canpotentially inform biology through computational experimentsimpossible in nature.From a biological perspective, Kirschner and Gerhart [12]describe evolvability as “an organism’s capacity to generateheritable phenotypic variation,” and suggest that evolvabilityin natural evolution results from an accumulation of flexiblebuilding blocks that are heavily conserved. However, they canbe combined and regulated in many ways to yield substantialphenotypic variety with few mutations. Further, they argue thatsuch evolvable lineages may be selected for; a lineage able todiscover and exploit new niches or to quickly radiate throughexisting niches following extinctions will itself be less likelyto go completely extinct.Examining evolvability from both biology and EC, Wagnerand Altenberg [31] similarly describe evolvability as relatingto the phenotypic variability of a genome, and argue thatEC can potentially provide insight into evolvability that biology cannot; the effect of alternate genetic representationson evolvability can be tested within EC but are not easilyexplored in nature. Furthermore, the authors argue that thestructure of the genotype to phenotype mapping is fundamentalto evolvability. This mapping, which includes the mechanismfor the reproduction and mutation of an organism, is itselfsubject to selection and evolution in nature.Studies in EC have described a lack of evolvability in practice [22, 31] and have noted possible directions for increasingevolvability. Some argue that static fitness functions, whichare prevalent in most of EC, do not encourage evolvability[6, 22] and instead suggest that fitness functions should changeover the course of evolution. Other suggestions for improvingevolvability are to allow adaptation of the genetic operatorset [9], to increase the extent of neutral networks [6], or toemploy indirect encodings that allow more plastic genotype tophenotype mappings [22, 31]. However, prior studies have notexamined the effects of alternate reward schemes like noveltysearch on evolvability, as is undertaken in this paper.B. NeuroEvolution of Augmenting Topologies (NEAT)In experiments in this paper, behaviors are evolved thatare controlled by artificial neural networks (ANNs). Thus aneuroevolution (NE; [32]) method is needed to implementthese experiments. The NEAT method is appropriate becauseit is widely applied [1, 2, 28, 29], well understood, and oftenrun in conjunction with novelty search.The NEAT method was originally developed to evolveANNs to solve difficult control and sequential decision tasks[28, 29]. Evolved ANNs control agents that select actionsbased on their sensory inputs. Like the SAGA method [10]introduced before it, NEAT begins evolution with a populationof small, simple networks and complexifies them. The population expands into diverse species over generations, leading toincreasingly sophisticated behavior. A similar process of gradually adding new genes is seen in natural evolution [17]. Thissection briefly reviews the NEAT method; for comprehensiveintroductions see Stanley and Miikkulainen [28, 29].To keep track of which gene is which while new genes areadded, a historical marking is uniquely assigned to each newstructural component. During crossover, genes with the samehistorical markings are aligned, producing meaningful offspring efficiently. Speciation in NEAT protects new structuralinnovations by reducing competition among differing structures and network complexities, thereby giving newer, morecomplex structures room to adjust. Networks are assigned tospecies based on the extent to which they share historicalmarkings. Complexification, which resembles how genes areadded over the course of natural evolution [17], is thussupported by both historical markings and speciation, allowingNEAT to establish high-level features early in evolution andthen later elaborate on them.