Technology, nowadays, has given us huge computational potential, but computer sciences have major problems tapping into this pool of resources. One of the main issues is how to program and design distributed systems. Biology has solved this issue about half a billion years ago, during the Cambrian explosion: the evolution of multicellularity. The evolution of multicellularity allowed cells to differentiate and so divide different tasks to different groups of cells; this combined with evolution gives us a very good example of how massively parallel distributed computational system can function and be “programmed”. However, the evolution of multicellularity is not very well understood, and most traditional methodologies used in evolutionary theory are not apt to address and model the whole transition to multicellularity. In this thesis I develop and argue for new computational artificial life methodologies for the study of the evolution of multicellularity that are able to address the whole transition, give new insights, and complement existing methods. I argue that these methodologies should have three main characteristics: accessible across scientific disciplines, have potentiality for complex behaviour, and be easy to analyse. To design models, which possess those characteristics, I developed a model of genetic regulatory networks (GRNs) that control artificial cells, which I have used in multiple evolutionary experiments. The first experiment was designed to present some of the engineering problems of evolving multicelled systems (applied to graph-colouring), and to perfect my artificial cell model. The two subsequent experiments demonstrate the characteristics listed above: one model based on a genetic algorithm with an explicit two-level fitness function to evolve multicelled cooperative patterning, and one with freely evolving artificial cells that have evolved some multicelled cooperation as evidenced by novel measures, and has the potential to evolve multicellularity. These experiments show how artificial life models of evolution can discover and investigate new hypotheses and behaviours that traditional methods cannot.

This dissertation clarifies the concept of evolvability, the increased capacity of some organisms or systems to support evolution, especially the evolution of life-like complexity. I survey the literature, which is spread over the fields of population genetics, developmental biology, artificial life, and microbial and molecular evolution. Finding that researchers have often used the term vaguely and incompatibly I identify five distinct kinds or senses of evolvability. I also identify five key constituent ideas, which I discuss in the context of organismic evolvability, a sense of evolvability with deep roots in the traditional fields of animal development and macroevolution. In these fields research into evolvability has historically been hampered by an insufficiently detailed knowledge of development. Research in molecular evolution has produced a thorough knowledge of the folding of RNA into secondary structure, which can be regarded as a model of development. This has motivated new approaches to evolvability based on representing development via a single genotype-phenotype mapping function. I build on these approaches to invent new mathematical methods to formalise the traditional ideas. I create an exact model illustrating a classic example of evolvability, the capacity for repeated segmentation and simple modularity. I analyse this with two new formal approaches. First is the genospace algebra, a propositional calculus based on graph theory. It is a formal language for describing genotype-phenotype maps. It provides a system for making calculations, proofs, and diagrams about mutational structures in genotype space, and it is flexible enough to allow description at arbitrary degrees of resolution. Second is a pair of concepts, the genetic leverage and the genetic fulcrum. The leverage provides a crude numerical measure of evolvability, and the fulcrum provides a heuristic for identifying the genomic and developmental causes of evolvability. Besides its specific relevance to diversification and development, evolvability is also crucial to the fundamental question of how evolution produces ordinary biological life. Simulation systems that implement only a conventional textbook model of evolution -– systems possessing only variation, inheritance, and selection –- fail to evolve anything resembling the complexity of the biological world. Research into evolvability is our best bet to illuminate the "missing ingredient" for life-like evolution.