Compositional Evolution:
Interdisciplinary Investigations in
Evolvability, Modularity, and Symbiosis.
Richard A. Watson
 

Abstract


A Dissertation Presented to the Faculty of the Graduate School of Arts and Sciences of Brandeis University, Waltham, Massachusetts
by Richard A. Watson

Conventionally, evolution by natural selection is almost inseparable from the notion of accumulating successive slight variations. Although it has been suggested that symbiotic mechanisms that combine together existing entities provide an alternative to gradual, or 'accretive', evolutionary change, there has been disagreement about what impact these mechanisms have on our understanding of evolutionary processes. Meanwhile, in artificial evolution methods used in computer science, it has been suggested that the composition of genetic material under sexual recombination may provide adaptation that is not available under mutational variation, but there has been considerable difficulty in demonstrating this formally. Thus far, it has been unclear what types of systems, if any, can be evolved by such 'compositional' mechanisms that cannot be evolved by accretive mechanisms.

This dissertation takes an interdisciplinary approach to this question by building abstract computational simulations of accretive and compositional mechanisms. We identify a class of complex systems possessing 'modular interdependency', incorporating highly epistatic but modular substructure. This class typifies characteristics that are pathological for accretive evolution - the corresponding fitness landscape is highly rugged, has many local optima creating broad fitness saddles, and includes 'irreducibly complex' adaptations that cannot be reached by a succession of gradually changing proto-systems. Nonetheless, we provide simulations to show that this class of system is easily evolvable under sexual recombination or a mechanism of 'symbiotic encapsulation'. Our simulations and analytic results help us to understand the fundamental differences in the adaptive capacities of these mechanisms, and the conditions under which they provide an adaptive advantage. These models exemplify how certain kinds of complex systems, considered unevolvable under normal accretive change, are, in principle, easily evolvable under compositional evolution.
 
Full postscript/pdf available here.
  Table of Contents available here.

Related publications

(>> = most central ones)

Symbiotic encapsulation vs crossover -> 'Symbiogenic Evolutionary Adaptation Model (SEAM)'

>> Watson, R.A. and Pollack, J.B. (2002). A Computational Model of Symbiotic Composition in Evolutionary Transitions (PREPRINT) . Biosystems Special Issue on Evolvability, (preprint 2001 - to appear 2002).

Watson, R.A. and Pollack, J.B. (2001). Symbiotic Composition and Evolvability. Advances in Artificial Life, 6th European Conference, (ECAL 2001) , Prague, Czech Republic, September 10-14, 2001, Proceedings. Jozef Kelemen, Petr Sosik (Eds.): Lecture Notes in Computer Science 2159 Springer 2001, ISBN 3-540-42567-5. pp. 480-490.

Watson, R.A. and Pollack, J.B. (2000). Symbiotic Combination as an Alternative to Sexual Recombination in Genetic Algorithms. Proceedings of Parallel Problem Solving from Nature (PPSNVI), Marc Schoenauer, Kalyanmoy Deb, Guenter Rudolph, Xin Yao, Evelyne Lutton, Juan Julian Merelo, Hans-Paul Schwefel (Eds)., 2000. Springer Verlag, Lecture Notes in Computer Science 1917 © Springer-Verlag.

Watson, R.A. and Pollack, J.B. (1999). Incremental Commitment in Genetic Algorithms . Proceedings of 1999 Genetic and Evolutionary Computation Conference (GECCO 99). Banzhaf, Daida, Eiben, Garzon, Honavar, Jakiela, Smith, eds., Morgan Kauffmann, pp.710-717.

Multi-dimensional treatment of coevolution -> 'Pareto Coevolution'

Watson, R.A. and Pollack, J.B. (2001). Coevolutionary Dynamics in a Minimal Substrate. Proceedings of the 2001 Genetic and Evolutionary Computation Conference, Spector, L, et al (eds.), Morgan Kaufmann, 2001.

Noble, J. and Watson, R.A. (2001). Pareto coevolution: Using performance against coevolved opponents in a game as dimensions for Pareto selection . In Spector, L., Goodman, E., Wu, A., Langdon, W.B., Voigt, H.-M., Gen, M., Sen, S., Dorigo, M., Pezeshk, S., Garzon, M., & Burke, E. (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2001, pp. 493-500. Morgan Kauffman, San Francisco.

Building-block test problems for GAs/ mutation vs crossover -> 'Hierarchical-if-and-only-if (HIFF)'/'modular interdependency'

>> Watson, R.A. (2001). Analysis of Recombinative Algorithms on a Non-Separable Building-Block Problem. Foundations of Genetic Algorithms, Volume 6 , proceedings of FOGA VI, Charlottesville, VA, July 21-23, 2000, Edited by Worthy N. Martin and William M. Spears, Morgan Kaufmann.

Watson, R.A. and Pollack, J.B. (1999). Hierarchically-Consistent Test Problems for Genetic Algorithms . Proceedings of 1999 Congress on Evolutionary Computation (CEC 99). Angeline, Michalewicz, Schoenauer, Yao, Zalzala, eds. IEEE Press, pp.1406-1413.

>> Watson, Richard A. , Hornby, G. S. and Pollack, J. B. (1998). Modeling Building-Block Interdependency . Parallel Problem Solving from Nature, proceedings of Fifth International Conference /PPSN V, Springer 1998, pp.97-106.

Baldwin effect -> 'Symbiotic Scaffolding'/'stochastic lookahead'

Watson, R.A. , Reil, T. and Pollack, J.B. (2000). Mutualism, Parasitism, and Evolutionary Adaptation. Proceedings of Artificial Life VII, Bedau, M, McCaskill, J, Packard, N, Rasmussen, S (eds.), 2000.

>> Watson, R.A. and Pollack, J.B. (1999). How Symbiosis Can Guide Evolution . Fifth European Conference on Artificial Life. Dario Floreano, Jean-Daniel Nicoud, Francesco Mondada, eds. Springer, 1999.