Computational Modeling of Evolution


Palmer, M.E. "Gene networks have a predictive long-term fitness,"
Genetic and Evolutionary Computation Conference (GECCO 2013). Amsterdam, The Netherlands, 2013, pp. 727-734. (Link)
Abstract: Using a model of evolved gene regulatory networks, we illustrate several quantitative metrics relating to the long-term evolution of lineages. The k-generation fitness, and k-generation survivability measure the evolutionary success of lineages. An entropy measure is used to quantify the predictability of lineage evolution. The metrics are readily applied to any system in which lineage membership can be periodically counted, and provide a quantitative characterization of the genetic landscape, genotype-phenotype map, and fitness landscape. Evolution is shown to be surprisingly predictable in gene networks: only a small number of the possible outcomes are ever observed in multiple replicate experiments. Notably, the long-term fitness is shown to be distinct from the short-term fitness. We emphasize the view that the lineage (not the individual, or the genotype) is the evolving entity over the long term. Since evolution is repeatable over the long-term, this implies long-term selection on lineages is possible; the evolutionary process need not be “short-sighted”. If we wish to evolve very complex artifacts, it will be expedient to promote the long-term evolution of the genetic architecture by tailoring our models to emphasize long-term selection.

Palmer, M.E., Moudgil, A, and Feldman, M.W. "Long-term evolution is surprisingly predictable in lattice proteins,"
Journal of the Royal Society Interface, 10(82), 20130026 (2013). doi: 10.1098/​rsif.2013.0026 (Link)
Abstract: It has long been debated whether natural selection acts primarily upon individual organisms, or whether it also commonly acts upon higher-level entities such as lineages. Two arguments against the effectiveness of long-term selection on lineages have been (i) that long-term evolutionary outcomes will not be sufficiently predictable to support a meaningful long-term fitness and (ii) that short-term selection on organisms will almost always overpower long-term selection. Here, we use a computational model of protein folding and binding called ‘lattice proteins’. We quantify the long-term evolutionary success of lineages with two metrics called the k-fitness and k-survivability. We show that long-term outcomes are surprisingly predictable in this model: only a small fraction of the possible outcomes are ever realized in multiple replicates. Furthermore, the long-term fitness of a lineage depends only partly on its short-term fitness; other factors are also important, including the ‘evolvability’ of a lineage—its capacity to produce adaptive variation. In a system with a distinct short-term and long-term fitness, evolution need not be ‘short-sighted’: lineages may be selected for their long-term properties, sometimes in opposition to short-term selection. Similar evolutionary basins of attraction have been observed in vivo, suggesting that natural biological lineages will also have a predictive long-term fitness.

Palmer, M.E., Lipsitch, M, Moxon, E.R., and Bayliss, C.D. "Broad Conditions Favor the Evolution of Phase-Variable Loci," mBio, 4(1), e00430-12 (2013). (Link)
Abstract: Simple sequence repeat (SSR) tracts produce stochastic on-off switching, or phase variation, in the expression of a panoply of surface molecules in many bacterial commensals and pathogens. A change to the number of repeats in a tract may alter the phase of the translational reading frame, which toggles the on-off state of the switch. Here, we construct an in silico SSR locus with mutational dynamics calibrated to those of the H. influenzae mod locus. We simulate its evolution in a regime of two alternating environments, simultaneously varying the selection coefficient, s, and the epoch length, T. Some recent work in a simpler (two locus) model suggested that stochastic switching in a regime of two alternating environments may be evolutionarily favored only if the selection coefficients in both environments are nearly equal (“symmetric”), or selection is very strong. This finding was puzzling as it greatly restricted the conditions under which stochastic switching might evolve. Instead, we find agreement with other recent theoretical work, observing selective utility for stochastic switching if the product sT is large enough for the favored state to nearly fix in both environments. Symmetry is required in neither s, nor in sT. Because we simulate finite populations and use a detailed model of the SSR locus, we are also able to examine the impact of population size, and of several SSR locus parameters. Our results indicate that conditions favoring evolution and maintenance of SSR loci in bacteria are quite broad.

Palmer, M.E. and Feldman, M.W. "Survivability is More Fundamental than Evolvability," PLoS One, 7(6): e38025 (2012). (Link)
Abstract: For a lineage to survive over long time periods, it must sometimes change. This has given rise to the term evolvability, meaning the tendency to produce adaptive variation. One lineage may be superior to another in terms of its current standing variation, or it may tend to produce more adaptive variation. However, evolutionary outcomes depend on more than standing variation and produced adaptive variation: deleterious variation also matters. Evolvability, as most commonly interpreted, is not predictive of evolutionary outcomes. Here, we define a predictive measure of the evolutionary success of a lineage that we call the k-survivability, defined as the probability that the lineage avoids extinction for k generations. We estimate the k-survivability using multiple experimental replicates. Because we measure evolutionary outcomes, the initial standing variation, the full spectrum of generated variation, and the heritability of that variation are all incorporated. Survivability also accounts for the decreased joint likelihood of extinction of sub-lineages when they 1) disperse in space, or 2) diversify in lifestyle. We illustrate measurement of survivability with in silico models, and suggest that it may also be measured in vivo using multiple longitudinal replicates. The k-survivability is a metric that enables the quantitative study of, for example, the evolution of 1) mutation rates, 2) dispersal mechanisms, 3) the genotype-phenotype map, and 4) sexual reproduction, in temporally and spatially fluctuating environments. Although these disparate phenomena evolve by well-understood microevolutionary rules, they are also subject to the macroevolutionary constraint of long-term survivability.

Palmer, M.E. and Feldman, M.W.
"Spatial Environmental Variation Can Select for Evolvability," Evolution, 65: 2345-2356 (2011). (Link)
Abstract: Previous studies have shown that temporally fluctuating environments can create indirect selection for modifiers of evolvability. Here, we use a simple computational model to investigate whether spatially varying environments (multiple demes with limited migration among them, and a different, static selective optimum in each) can also create indirect selection for increased evolvability. The answer is surprisingly complicated. Spatial variation in the environment can sharply reduce the survival rate of migrants, because migrants may be maladapted to their new deme, relative to incumbents. The incumbent advantage can be removed by occasional extinctions in single demes. After all incumbents in a particular deme die, incoming migrants from other demes will, on average, be similarly maladapted to the new environment. This sets off a race to adapt rapidly. Over many extinction events, and the subsequent invasions by maladapted immigrants into a new environment, indirect selection for the ability to adapt rapidly, also known as high evolvability, may result.

Palmer, M.E. and Feldman, M.W.
"Dynamics of hybrid incompatibility in gene networks in a constant environment," Evolution, 63: 418-441 (2009). (Link)
Abstract: After an ancestral population splits into two allopatric populations, different mutations may fix in each. When pairs of mutations are brought together in a hybrid offspring, epistasis may cause reduced fitness. Such pairs are known as Bateson–Dobzhansky–Muller (BDM) incompatibilities. A well-known model of BDM incompatibility due to Orr suggests that the fitness load on hybrids should initially accelerate, and continue to increase as the number of potentially incompatible substitutions increases (the “snowball effect”). In the gene networks model, which violates a key assumption of Orr's model (independence of fixation probabilities), the snowball effect often does not occur. Instead, we describe three possible dynamics in a constant environment: (1) Stabilizing selection can constrain two allopatric populations to remain near-perfectly compatible. (2) Despite constancy of environment, punctuated evolution may obtain; populations may experience rare adaptations asynchronously, permitting incompatibility. (3) Despite stabilizing selection, developmental system drift may permit genetic change, allowing two populations to drift in and out of compatibility. We reinterpret Orr's model in terms of genetic distance. We extend Orr's model to the finite loci case, which can limit incompatibility. Finally, we suggest that neutral evolution of gene regulation in nature, to the point of speciation, is a distinct possibility.
 
Palmer, M.E. and Lipsitch, M.
"The Influence of Hitchhiking and Deleterious Mutation Upon Asexual Mutation Rates," Genetics, 173: 461–472 (May 2006). (Link)
Abstract: The question of how natural selection affects asexual mutation rates has been considered since the 1930s, yet our understanding continues to deepen. The distribution of mutation rates observed in natural bacteria remains unexplained. It is well known that environmental constancy can favor minimal mutation rates. In contrast, environmental fluctuation (e.g., at period T) can create indirect selective pressure for stronger mutators: genes modifying mutation rate may “hitchhike” to greater frequency along with environmentally favored mutations they produce. This article extends a well-known model of Leigh to consider fitness genes with multiple mutable sites (call the number of such sites α). The phenotypic effect of such a gene is enabled if all sites are in a certain state and disabled otherwise. The effects of multiple deleterious loci are also included (call the number of such loci γ). The analysis calculates the indirect selective effects experienced by a gene inducing various mutation rates for given values of α, γ, and T. Finite-population simulations validate these results and let us examine the interaction of drift with hitchhiking selection. We close by commenting on the importance of other factors, such as spatiotemporal variation, and on the origin of variation in mutation rates.
  

Artificial Evolution / Evolutionary Robotics


Palmer, M.E., and Chou, A. "Evolved neural network controllers for physically simulated robots that hunt with an artificial visual cortex," in
Artificial Life XIII. East Lansing, MI, 2012.
Abstract: Using a rule-based system for growing artificial neural networks, we have evolved controllers for physically simulated robotic "spiders". The controllers take their input from an “artificial retina” that senses other spiders and inanimate barrier objects in the environment, and must provide output to dynamically control the 18 degrees of freedom of the six legs of the robot every time step. We perform evolutionary runs with two species of spider that interact in simulation with each other and with inanimate barrier objects. One species (the "predator") is selectively rewarded for "eating" (by physically colliding with) the other species, and the other (the "prey") is selectively penalized for being caught, and rewarded for "eating" the barriers. The two species evolve complex running gaits, with control inputs coming from their retinas that produce hunting or avoidance behavior. We suggest that predator-prey frequency dependent selection can provide a relatively long-term genetic memory of previously searched regions of phenotype space, enforcing a form of novelty search that may reduce duplicated evolutionary search effort. (PDF) (Videos) (Source Code)

Palmer, M.E.
"Evolved Neurogenesis and Synaptogenesis for Robotic Control: the 'L-Brain' Method," in Genetic and Evolutionary Computation Conference (GECCO 2011). Dublin, Ireland, 2011. (PDF) (Videos) (Source Code)
Abstract: We have developed a novel method to "grow" neural networks according to an inherited set of production rules (the genotype), inspired by Lindenmayer systems. In the first phase (neurogenesis), the neurons proliferate in three-dimensional space by cell division, and differentiate in function, according to the production rules. In the second phase (synaptogenesis), axons emerge from the neurons and seek out connection targets. Part of each production rule is an augmented Reverse Polish Notation expression; this permits regulation of the applicable rules, as well as introduction of spatial and temporal context to the developmental process. We connect each network to a (fixed) robotic body with a set of input sensors and muscle actuators. The robot is placed in a physically simulated environment and controlled by its network for a certain time, receiving a fitness score according to its behavior (the phenotype). Mutations are introduced into offspring by making changes to their sets of production rules. This paper introduces the "L-brain" developmental method, and describes our first experiments with it, which produced controllers for robotic "spiders" with the ability to gallop, and to follow a compass heading.

Palmer, M.E., Miller, D.B., and Blackwell, T.L. "An Evolved Neural Controller for Bipedal Walking: Transitioning from Simulator to Hardware," in
IEEE IROS 2009 Workshop on Exploring New Horizons in Evolutionary Design of Robots (Evoderob09), pp 51-58. St Louis, MO. 2009. (PDF) (Video1) (Video2) (Video3)
Abstract: In the field of evolutionary robotics, evolution is commonly done with simulated hardware; the transition to real hardware can be difficult. We evolved a neural network controller that produces dynamic walking in a simulated bipedal robot with compliant actuators, a difficult control problem. We describe some of the challenges of transitioning from a simulated robot to the hardware. Currently our controller can make the robot balance in a standing position, both in simulation and on the hardware; the controller can also successfully walk in simulation, but not yet on the hardware.
 
Palmer, M.E., and Miller, D.B. "Evolved Neural Controllers for Bipedal Dynamic Walking with Multiple Demes and Progressive Fitness Functions," in
Genetic and Evolutionary Computation Conference (GECCO 2009). Montreal, Canada, 2009. (PDF) (Video1) (Video2)
Abstract: We successfully evolved a neural network controller that produces dynamic walking in a simulated bipedal robot with compliant actuators, a difficult control problem. The evolutionary evaluation uses a detailed software simulation of a physical robot. We describe: 1) a novel theoretical method to encourage populations to evolve “around” local optima, which employs multiple demes and fitness functions of progressively increasing difficulty, and 2) the novel genetic representation of the neural controller.

Palmer, M.E. and Smith, S.J. "Improved Evolutionary Optimization of Difficult Landscapes: Control of Premature Convergence through Scheduled Sharing," Complex Systems, Vol 5 (1991), pp. 443-458. (PDF)
Abstract: Massively parallel computers afford to genetic algorithms the use of very large populations, which allow the algorithms to attack more difficult optimization problems than were feasible in the past. Optimization performance on difficult search spaces - those that are both vast and have large numbers of local optima - can be particularly crippled by a common problem of genetic algorithms: premature convergence of the population to a suboptimum. In nature, however, competition between like organisms prevents total convergence, and this competition effect can also be introduced to the standard genetic algorithm by an extension called sharing. Sharing forces organisms within a niche to compete. In past work, the size of the niche has been fixed, and calculated by hand for simple test problems. This paper introduces an improvement to fixed-niche sharing called scheduled sharing, which (1) allows for the application of sharing to complex problems where there is no definable best niche size, and (2) does not violate the "black box" principle in the calculation of niche size, instead borrowing from simulated annealing an exponentially decreasing schedule. We show that scheduled sharing inhibits convergence and improves performance for optimization problems that are difficult relative to the size of the population used.


Unrefereed Conference Presentations


Palmer, M.E. "The Red Queen's Race Can Select for Evolvability." Evolution 2010, Portland, OR, June, 2010.

Palmer, M.E. "Environmental Variation and the Evolution of Evolvability." Evolution 2008, Minneapolis, MN, June, 2008.

Palmer, M.E. "Limitation of Dobzhansky-Muller Incompatibilities by Variational Constraint in Gene Networks." Evolution 2007, Christchurch, New Zealand, June 2007.

Palmer, M.E., and Feldman, M.W. "Recombination And Mutation In Gene Networks In Silico." Evolution 2006, Stony Brook, NY, June 2006.


Other Publications (mostly Parallel Volume Rendering)


Palmer, M.E., Totty, B., and Taylor, S.
"Ray Casting on Shared-Memory Architectures: Memory Hierarchy Considerations in Volume Rendering," IEEE Concurrency, 6(1):20-35, Spring, 1998.
 
Palmer, M.E., Taylor, S., and Totty, B.
"Exploiting Deep Parallel Memory Hierarchies for Ray Casting Volume Rendering," The 1997 Symposium on Parallel Rendering, pp 15-22,115-116. Phoenix, AZ. ACM SIGGRAPH, 1997.
 
Taylor, Watts, Rieffel and Palmer.
"The Concurrent Graph: Basic Technology for Irregular Problems", IEEE Parallel and Distributed Technology, 4(2):15-25, Summer 1996.

Palmer, M.E., Taylor, S., and Totty, B.
"Interactive Volume Rendering on Clusters of Shared-Memory Multiprocessors," Parallel Computational Fluid Dynamics '95, Pasadena, CA. Elsevier Science Publishers B.V., 1995.
 
Palmer, M.E. and Taylor, S.
"Rotation Invariant Partitioning for Concurrent Scientific Visualization," Parallel Computational Fluid Dynamics '94, Kyoto, Japan. Elsevier Science Publishers B.V., 1994.
 
Palmer, M.E. "The Airplane Finder Project, or An Attention-Focusing Neural Network for Pattern Recognition on Clusterable Data Spaces,"
Proceedings of the 1990 Long Island I.E.E.E. Student Conference on Neural Networks. pp. 45-48. Editor, Frank P. Li. N.Y.I.T. (Winner, Best Undergraduate Paper.)
  
Palmer, M.E.
Exploiting Parallel Memory Hierarchies for Ray Casting Volumes, Ph.D. Thesis, California Institute of Technology, 1997.
 
Palmer, M.E.
Scientific Visualization of Unstructured Volumetric Data on Concurrent Architectures, Master's Thesis, California Institute of Technology, 1993.