978-0-262-31709-2-ch014 (Rice), страница 4

If we examine the c.d.f.’s we seeseveral interesting things.First, the c.d.f.’s for evolution of genotypes have zeroslope during lean epochs, which suggests that new genotypes typically appear during flush epochs, when fitness isequated with effective complexity. Conversely, the c.d.f.’sfor genotype fixation have zero slope during flush epochs,which leads us to conclude that fixation of genotypes typically occurs during lean epochs, when fitness is equated withefficiency. This is consistent with an increase in diversityduring flush epochs and a decrease during lean epochs.Second, there is always a lag between the generations ofevolution and fixation, and the size of the lag depends onthe improvement in self-replication efficiency–the greaterthe improvement, the shorter the lag.

The C allele (whichconfers an advantage of 119 returns relative to the A allele)requires more time for fixation than the B allele (which confers an advantage of 218 returns).If we know the generation in which each genotypeevolved, it is possible to estimate probabilities for each ofthe pathways leading from the (least complex and least efficient) A genotype to the (most complex and most efficient)D genotype; see Table 3.

This analysis shows that in 64%of the runs in which D evolved, one of the B or C allelesevolved and was fixed prior to the evolution of the other;ECAL 2013tB < tC < tD0.26the D genotype then evolved by mutation from an ancestralprogram of the B or C genotype. However, in 35% of theruns in which D evolved, something (arguably) more interesting happened. Namely, the B and C alleles evolved in distinct lineages before either was fixed. The D genotype thenevolved when an individual with the B allele and an individual with the C allele were combined by crossover. Stateddifferently, in 35% of the runs where D evolved, beneficialtraits which evolved separately were combined by crossoverto produce a child program more complex and more efficientthan either parent program.Table 2: Generation of initial evolution and fixation.B0.9021.821.011tC < tB = tD0.31• In the present system, de Bruijn indices are used mainly tosimplify the compilation process by eliminating the needfor static analysis; however, it is difficult to see how newlexical scopes could evolve (via a new mutation operatorwhich introduces lambda expressions) unless bound variables are represented by symbols, and this would meanthat the self-hosting compiler must be generalized so thatit performs static analysis.• Demonstration of auto-constructive evolution as described by (Spector and Robinson, 2002), in which artificial organisms possess not only their own means of selfreplication, but also of producing variation; this would require coding all mutation operators in Skeme and including this code in the subtree of the self-hosting compilerwhich copies quoted expressions.• Reification of the compiling quine as a self-replicatingdistributed virtual machine (including the items listedabove) and demonstration of evolution of increased complexity and self-replication efficiency by reified artificialorganisms.92ECAL - General TrackReferencescumulative probability (%)100Adami, C., Brown, C.

T., and Kellogg, W. (1994). Evolutionarylearning in the 2D artificial life system “Avida”. In ArtificialLife IV, pages 377–381. MIT Press.80De Bruijn, N. G. (1972). Lambda calculus notation with nameless dummies: a tool for automatic formula manipulation,with application to the Church-Rosser theorem. IndagationesMathematicae, 34:381–392.6040200D’haeseleer, P. (1994). Context preserving crossover in geneticprogramming.

In IEEE World Congress on ComputationalIntelligence, pages 27–29.B (evolved)B (fixed)C (evolved)C (fixed)D (evolved)D (fixed)0102030405060generation7080Dybvig, R. K. (1987). Three implementation models for Scheme.PhD thesis, University of North Carolina.90Finnigan, G., Hanson-Smith, V., Stevens, T., and Thornton, J. W.(2012). Evolution of increased complexity in a molecularmachine.

Nature, 481(7381):360–364.Figure 8: Cumulative distribution functions representing theprobabilities that genotypes B, C, and D have evolved andare fixed by the given generation.Kirshenbaum, E. (2000). Genetic programming with staticallyscoped local variables. In Genetic and Evolutionary Computation (GECCO).ConclusionKoza, J. (1994). Artificial life: spontaneous emergence of selfreplicating and evolutionary self-improving computer programs. In Langdon, C., editor, Artificial Life III, pages 225–262.

Addison Wesley.We introduced a new type of self-replicating program which(unlike previous self-replicating programs) includes distinctphenotype and genotype components. Although the program is encoded in machine language, and (for this reason)can be executed on a CPU (or reified as a distributed virtual machine) it reproduces by compiling itself from its ownsource code, which is written in a more expressive high-levellanguage.

Because compiling is an intrinsically more complex process than copying, there is a much larger space ofimplementations to be explored by an evolutionary process;because its genotype is encoded in a high-level language, thespace of neighboring self-replicating programs can be moreefficiently probed.To address the problem of how a complicated lexicallyscoped program like a compiler can evolve into a more complex and efficient program without breaking, we designed,implemented and tested a novel genetic programming system, which uses a pair of mutation operators analogous togene duplication and specialization, together with homologous crossover and an alternating fitness function which selects for complexity or efficiency depending on epoch.

Using this system, we experimentally demonstrated the evolution of several self-replicating programs of increased complexity and efficiency from a less complex and less efficientancestor. We were able to show that in a population of 200individuals, the most complex and efficient self-replicatingprogram evolved within 100 generations in over three quarters of all trials, and by crossover of less complex and lessefficient parent programs a significant fraction of the time.Koza, J., Bennet, F., Andre, D., and Keene, M. (1999).

The designof analog circuits by means of genetic programming. Evolutionary Design by Computers, pages 365–385.Offman, M. N., Tournier, A. L., and Bates, P. A. (2008). Alternating evolutionary pressure in a genetic algorithm facilitatesprotein model selection.

BMC Structural Biology, 8(34).Pujol, J. C. F. (1999). Evolution of artificial neural networks using a two-dimensional representation. PhD thesis, School ofComputer Science, University of Birmingham, UK.Ray, T. S. (1994). An evolutionary approach to synthetic biology,zen and the art of creating life. Artificial Life, 1:179–209.Spector, L. and Robinson, A. (2002). Genetic programmingand auto-constructive evolution with the push programminglanguage.

Genetic Programming and Evolvable Machines,3(1):7–40.Stephenson, M., Amarasinghe, S. P., Martin, M. C., and O’Reilly,U. (2003). Meta optimization: improving compiler heuristicswith machine learning. In Cytron, R. and Gupta, R., editors,PLDI, pages 77–90. ACM.Taylor, T. and Hallam, J. (1997). Studying evolution with selfreplicating computer programs. In Fourth European Conf. onArtificial Life, pages 550–559. MIT Press.Williams, L.

(2012). Robust evaluation of expressions by distributed virtual machines. In Unconventional Computationand Natural Computation (UCNC), Orleans, France.Zou, R. and Lung, W. (2004). Robust water quality model calibration using an alternating fitness genetic algorithm. J. WaterResource Planning Management, 130(6):471–479.AcknowledgementsThanks to Jeff Barnett, Stephanie Forrest, Ben Edwards,Neal Holtschulte and Melanie Moses for helpful comments.93ECAL 2013.