The phrase "evolution of evolvability," coined by Dawkins (1988), was adopted by several researchers to better summarize a theoretical subject that originated with Riedl (1975) and Conrad (1977). Here "evolvability" means the upper tail of the distribution of fitness effects of genetic variation. While many assert that the evolution of evolvability is "controversial," the evolution of the upper tail of fitness distributions actually goes back to Fisher (1930). "Evolvability," when understood as the upper tail of offspring fitness distributions, is clearly not a "population-level feature" requiring group or lineage selection to evolve, but is a property of individuals. The upper tail will evolve when it co-varies with individual fitnesses, as described by the Price (1970) equation. In the usual model of a population evolving toward an adaptive peak, as in Fisher's geometric model, the covariance will be negative, and the upper fitness tail will shrink. More challenging is to identify evolutionary mechanisms that systematically cause the upper fitness tail to be maintained or to expand.

My contribution is to theoretically tie the upper tail of fitness distributions together with several disparate phenomena: the modularity and complexity of the genotype-phenotype map, gene origin dynamics, the relationship of gene duplication effects to allelic variation, and the consequences of iterative gene duplication over macroevolutionary time. These relationships are still not widely understood, so they will be the focus of my talk.

The Adaptive Immune System as a Learning Algorithm

Shishi Luo, Los Alamos National Laboratory

Our adaptive immune system has the remarkable ability to learn and remember how to neutralize most foreign pathogens that invade our body. One pathogen for which this system seems to fail is human immunodeficiency virus (HIV). Suppose we formulate the adaptive immune response to a pathogen as a search process on some space of molecular shapes. what properties might it have and what is it about HIV that makes this process less effective?

Download Video [229.6MB .mp4]

Satisfiability and Evolution

Andrew Wan, Tsinghua University

How does a beneficial trait, one that is determined by the interaction between many genes, become fixed in a population? We consider the interaction between n genes and their evolving genotype frequencies, with reproduction through recombination, as a process on a Boolean function: when the Boolean function is satisfied by an assignment (i.e., a genotype), a small evolutionary advantage is conferred. Our main result shows that for any Boolean function and populations of polynomial size (polynomial in the number of genes and the inverse probability of initial satisfaction), with very high probability every individual in the population will be satisfying after polynomially many generations.

Download Video [213.6MB .mp4]

The Dynamics of Complex Adaptation

Daniel Weissman, IST Austria

When and how can populations acquire complex adaptations that need multiple mutations to provide a fitness benefit? At least for toy population models, we can find simple, universal approximations for how the dynamics of the process depend on both the genetics of the adaptation (the number of necessary mutations, their individual fitness costs and rates of occurrence, and the recombination rate among them) and the size and structure of the population. Qualitatively, the potential complexity of adaptations is generally highest in large populations undergoing an intermediate amount of recombination.

Download Video [148.7MB .mp4]

A Few Comments (& Questions!) from a Condensed Matter Physicist

Daniel Fisher, Stanford University

Download Video [109.6MB .mp4]

Non-Adaptive Evolvability

Jeff Clune, University of Wyoming
I summarize two separate papers that document cases where evolution failed to evolve evolvability, even though it would have benefitted from doing so. Instead, in both cases, evolvability arises because of an accidental constraint of physics.The first documents that evolution fails to optimize mutation rates for long-term adaptation on rugged fitness landscapes [1]. The second documents that evolution does not evolve modularity in networks (e.g. genetic or neural) unless there exists a cost for network connections, even though such modularity improves performance and evolvability [2]. Together, these papers raise the question of how many instances of evolvability in nature arise as a by-product of some other force. The papers also provide instructions to engineers that wish to harness evolution to produce artificial intelligence as to how to increase the evolvability of evolutionary algorithms.

[1] Clune J, Misevic D, Ofria C, Lenski RE, Elena SF, and Sanjuán R (2008)
Natural selection fails to optimize mutation rates for long-term adaptation on rugged fitness landscapes. PLoS Computational Biology 4(9): e1000187.

[2] Clune J, Mouret J-B, Lipson H (2013)
The evolutionary origins of modularity. Proceedings of the Royal Society B. 280: 20122863.

Download Video [238.1MB .mp4]

Complexity of Evolutionary Equilibria in Static Fitness Landscapes

Artem Kaznatcheev, McGill University

A fitness landscape is a genetic space—with two genotypes adjacent if they differ in a single locus—and a fitness function. Evolutionary dynamics produce a flow on this landscape from lower fitness to higher; reaching equilibrium only if a local fitness peak is found. I use computational complexity to question the common assumption that evolution on static fitness landscapes can quickly reach a local fitness peak. I do this by showing that the popular NK model of rugged fitness landscapes is PLS-complete for K >= 2; there are NK fitness landscapes where every adaptive path from some vertices is of exponential length. Alternatively—under the assumption that there are problems in PLS not solvable in polynomial time—this means that there are no evolutionary dynamics (known, or to be discovered, and not necessarily following adaptive paths) that can converge to a local fitness peak on all NK landscapes with K = 2. Further, there exist single-peaked landscapes with no reciprocal sign epistasis where the expected length of an adaptive path following strong selection weak mutation dynamics is exp(O(n^1/3)) even though an adaptive path to the optimum of length less than n is available from every vertex. Finally, I discuss the effects of approximate equilibria and a connection to the long term E.coli evolution project.

preprint: http://arxiv.org/abs/1308.5094

Download Video [150.9MB .mp4]

Everything not Forbidden is Allowed

Aviv Bergman, Albert Einstein College of Medicine

Explaining Adaptation in Genetic Algorithms with Uniform Crossover

Keki Burjorjee, Zite Inc.
Hyperclimbing is an intuitive, general-purpose, global optimization heuristic applicable to discrete product spaces with rugged or stochastic cost functions. The strength of this heuristic lies in its insusceptibility to local optima when the cost function is deterministic, and its tolerance for noise when the cost function is stochastic. Hyperclimbing works by decimating a search space, i.e., by iteratively fixing the values of small numbers of variables. The hyperclimbing hypothesis posits that genetic algorithms with uniform crossover (UGAs) perform optimization by implementing efficient hyperclimbing. Proof of concept for the hyperclimbing hypothesis comes from the use of an analytic technique that exploits algorithmic symmetry. By way of validation, we will present experimental results showing that a simple tweak inspired by the hyperclimbing hypothesis dramatically improves the performance of a UGA on large, random instances of MAX-3SAT and the Sherrington Kirkpatrick Spin Glasses problem. An exciting corollary of the hyperclimbing hypothesis is that a form of implicit parallelism more powerful than the kind described by Holland underlies optimization in UGAs. The implications of the hyperclimbing hypothesis for Evolutionary Computation and Artificial Intelligence will be discussed.

Download Video [147MB .mp4]