Improving Evolvability Through Novelty Search And Self .

3y ago
20 Views
3 Downloads
392.73 KB
8 Pages
Last View : 9d ago
Last Download : 6m ago
Upload by : Aarya Seiber
Transcription

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.

The next section reviews novelty search, a technique in ECthat rewards only behavioral novelty.C. Novelty SearchThe problem with the objective-based search paradigm thatis common in EC models is that an objective function (i.e.the fitness function) does not necessarily reward the intermediate stepping stones that lead to the objective, nor does itnecessarily distinguish more evolvable individuals. The moreambitious the objective, the harder it is to identify a priorithese evolvable stepping stones.The approach suggested by Lehman and Stanley [16] isto identify novelty as a proxy for stepping stones. Instead ofsearching for a final objective, the learning method is rewardedfor finding any instance whose functionality is significantlydifferent from what has been discovered before. Thus, insteadof an objective function, search employs a novelty metric.Novelty search differs from objective-based search by rewarding stepping stones. That is, anything that is genuinelydifferent is rewarded and promoted as a jumping-off pointfor further evolution. Additionally, those lineages discoveringmore stepping stones will be indirectly rewarded, encouragingevolvability. While we cannot know which stepping stonesare the right ones, if we accept that the primary pathologyin objective-based search is that it cannot detect the steppingstones at all, then that pathology is remedied. This idea isalso related to research in curiosity seeking in reinforcementlearning [25].EAs such as NEAT are well-suited to novelty search becausethe population that is central to such algorithms naturally covers a range of behaviors. In fact, tracking novelty requires littlechange to any evolutionary algorithm aside from replacing thefitness function with a novelty metric.The novelty metric measures how different an individualis from other individuals, creating a constant pressure to dosomething new. The key idea is that instead of rewardingperformance on an objective, novelty search rewards divergingfrom prior behaviors. Therefore, novelty needs to be measured.The novelty of a newly-generated individual is computedwith respect to the behaviors (i.e. not the genotypes) of anarchive of past individuals and the current population. The aimis to characterize how far away the new individual is from therest of the population and its predecessors in behavior space,i.e. the space of unique behaviors. A good metric should thuscompute the sparseness at any point in the behavior space.Areas with denser clusters of visited points are less novel andtherefore rewarded less.A simple measure of sparseness at a point is the averagedistance to the k-nearest neighbors of that point, where kis a fixed parameter that is determined experimentally. Thesparseness ρ at point x is given byk1Xdist(x, µi ),(1)ρ(x) k i 0where µi is the ith-nearest neighbor of x with respect to thedistance metric dist, which is a domain-dependent measure ofbehavioral difference between two individuals in the searchspace. The nearest neighbors calculation must take into consideration individuals from the current population and from thepermanent archive of novel individuals. Candidates from moresparse regions of this behavioral search space then receivehigher novelty scores.The current generation plus the archive give a comprehensive sample of where the search has been and where itcurrently is; that way, by attempting to maximize the noveltymetric, the gradient of search is simply towards what is new,with no other explicit objective. Note that novelty search isnot an exhaustive or random search because many genotypesmap to the same behavior, and the number of novel behaviorsis reasonable and limited in many practical domains.Once objective-based fitness is replaced with novelty, theunderlying NEAT algorithm operates as normal, selecting themost novel individuals to reproduce. Over generations, thepopulation spreads out across the space of possible behaviors,sometimes finding an individual that solves the problem eventhough progress towards the solution is not directly rewarded.In fact, there have been several successful applications ofnovelty search in neuroevolution [16, 19, 23] and genetic programming [8, 15]. Novelty search was introduced in Lehmanand Stanley [14] and applied to a deceptive maze task; theseresults were replicated in Mouret [19]. Experiments have alsoshown that encouraging novelty is useful in evolving adaptiveANNs (i.e ANNs that learn during their lifetimes) [23, 26].These results were surprising because they established thatan algorithm with no knowledge of its objective can often outperform one specifically rewarded for achieving that objective.However, an interesting question orthogonal to performancethat is addressed in this paper is whether abandoning pressureto optimize the objective can also affect higher-level propertiessuch as evolvability.III. M EASURING E VOLVABILITYThe primary hypothesis in this paper is that rewardingnovelty increases evolvability when compared with rewardingprogress towards a fixed objective. Therefore, an importantaspect of evaluating this hypothesis is quantifying evolvability.One definition of evolvability is “an organism’s capacity togenerate heritable phenotypic variation” [12]. Brookfield [3]similarly suggests evolvability is “the proportion of radicallydifferent designs created by mutation that are viable and fertile.” These definitions reflect a growing consensus in biologythat the ability to generate phenotypic variation is fundamentalto evolvability [3, 12, 20, 31].From these definitions, a way of estimating an individual’sevolvability is to generate many children from it and then measure the degree of phenotypic variation among those offspring.In effect, this measure quantifies how well the organizationof the individual’s representation has internalized domaininformation to enable more behaviorally diverse mutations.This measure is similar in intention to that in Reisinger et al.[22] but is more granular because it quantifies how well an

individual’s evolved representation exploits domain structureinstead of measuring an encoding’s ability to do the same.Accordingly, the measure of evolvability in this paper is tocount how many distinct behaviors there are among a seriesof generated offspring of a particular individual. An individualwhose offspring tend to display many distinct behaviors iscapable of generating much heritable phenotypic variation,and is thus evolvable. In practice, such a measure requiresa domain-fitted test between two individuals to determinewhether their behaviors are distinct.The domain-specific novelty metric in novelty search thatmeasures behavioral distance between two individuals cannaturally be adapted for this purpose: Two behaviors aredistinct if the behavioral distance between them is greater thana fixed threshold.Using this test of behavioral distinction, the number ofdistinct behaviors among a list of behaviors can be calculatedby the following greedy algorithm that accumulates a list ofdistinct behaviors: The first behavior is added to this list bydefault, and each subsequent behavior is added if it is distinctfrom each behavior already in the distinct behavior list. Thesize of this filtered list is the number of distinct behaviors, anestimate of the individual’s evolvability.At regular intervals during a run, the evolvability of eachindividual in the population is measured. That is, for eachindividual in the population many offspring are sequentiallygenerated by first cloning the individual and then mutatingthe clone; the idea is to sample the genotypic space aroundan individual and examine the distribution of those samples inbehavior space. The behaviors of these perturbed clones arethen concatenated to form a list, with the number of distinctbehaviors in the concatenated list acting as an indicator of thatindividual’s phenotypic variability, i.e. its evolvability.IV. E XPERIMENTSTo compare the evolvability of individuals evolved by bothnovelty search and traditional objective fitness-based search,experiments are conducted in two domains previously employed to compare the performance of the two varieties ofsearch, i.e. maze-navigation and biped locomotion [16].This paper’s experiments utilize NEAT, which has beenproven in many control tasks [2, 14, 16, 28, 29

structure of the genotype to phenotype mapping is fundamental to evolvability. This mapping, which includes the mechanism for the reproduction and mutation of an organism, is itself subject to selection and evolution in nature. Studies in EC have described a lack of evolvability in prac

Related Documents:

NOVELTY Ticket To Ride Europe Board Game N 625 Monopoly: Game of Thrones Collector’s Edition N 610. 194 www.highwayimportersonlineshop.com NOVELTY Monopoly Fortnite Vertellis Bonding Game – Red N 325 N 610. www.highwayimpor

Paid vs. Organic Search Search Engine Marketing (SEM) is a term used to describe the various means of marketing a website via search engines, and entails both organic search engine optimization and paid search strategies. Organic search is based on unpaid, natural rankings determined by search engine algorithms, and can be optimized

abstract, but not the full-text. To access the full-text, search the DDUH/TCD Library catalogues 5. Search Limits Limit your search in the search tab at the top of your search results. 6. Advanced search / Search Manager . The Cochrane Library consists of 6 distinct databases: Cochrane Database of Systematic Reviews (Cochrane Reviews)

With your search results displayed, click the “Search/Browse” drop-down menu and select within results. Type a new search expression in the Search Expression field . Click Go. CCH IntelliConnect searches for your new search expression within the search results of the selected search, and your results display .

The results displayed on a search engine include paid search ads and organic (or un-paid) search links. Online advertisers pay the search engine for all impressions or clicks to their ads, but do not pay for organic search links. Importantly, search ads always appear at the top of the page, followed by organic search links (see Figure1).

Both paid search advertising and organic search engine optimization are essential tools to help you show up in search engine results. SEARCH 93% Of consumers begin on a search engine.13 75% Of searchers never scroll past the first page of search results.14 50% Paid search ads provide 50% incremental clicks even when a business ranks #1 for

1.1 Search Engine Optimization Figure 1 highlights the avenues that retailers have for gaining traffic through search engines. This screenshot shows the search results that appear following a search for "shoes online" on Google Search. In this particular example, three different types of links appear: top ads, side ads, and

Fundamentals; Harmony; Jazz, Pop, and Contemporary Music Theory (including Twentieth-Century Music); and Form in Music. The format for each volume is consistent: 1. The left column lists terms to help you organize your study and find topics quickly. 2. Bold indicates key concepts. 3. Each volume ends with a Remember-Forever Review and More