Non-conventional evolutionary computation

Ongoing work on non-conventional evolutionary computation at GEB is presented in this page.

 

Artificial embryogeny

Artificial embryogenies are an extension to evolutionary algorithms. Evolutionary algorithms use a number of mechanisms that have been inspired through biological evolution, e.g. reproduction, mutation, recombination, and selection, to optimize a problem. In this sense, a solution to the problem would be an individual from the population. Reproduction, mutation and recombination operators produce new individuals, i.e. solutions to the problem. Selection discards the worst individuals while keeping the best ones. This process is repeated iteratively a fix amount of iterations or until an acceptable individual is found.

A possible limitation of many evolutionary algorithms is their lack of a clear distinction between genotype and phenotype. Genotype is an organism’s full hereditary information, while the phenotype is an organism’s actual observed properties. In nature, the fertilized egg’s cell undergoes a complex process orchestrated by its genotype, this is known as embryogenesis, to become a mature phenotype. Artificial embryogenies study and implement complex genotype-phenotype mappings inspired by biological development. This approach allows evolutionary algorithms to evolve phenotypes with a far higher degree of complexity compared to the traditional representations.

A number of results using artificial embryogenies that has been designed in our lab are presented here. First, an artificial embryogeny based in rewriting rules is presented, where the phenotype is a structure formed by connected semi-rigid bars.  The genome in this embryogeny is composed by rules that transform the bars, e.g. rules that change the length of a bar, or rules that duplicate a bar. Bars represent the cells of an organism, and, as in biology, each bar has a genome copied from its parent’s bar. The embryogeny of a structure starts with a single bar; the zygote. The following animation demonstrates an example of the embryogeny process.

 

 

 

The implemented embryogenesis has been used in an evolutionary algorithm in order to optimize the bar structures that accommodate the impact in a landing test. The landing test measures the degree of deformation that the structure suffers as a result of the impact and the displacement from the contact point. The following animation shows an example of the landing test of a random structure.


 

Starting with a population of random structures as shown in the previous animation, the evolutionary algorithm automatically optimizes them. An evolved structure is shown in the next animation. Observe how the evolutionary process manages to automatically design a pyramidal form that helps the structure to avoid deformation and displacement during the landing, until it eventually stands on the ground.

 

 

For more information, please see the following paper:

Lobo D & Vico FJ (2010) Evolutionary development of tensegrity structures. Biosystems, 101(3): 167-176. DOI:10.1016/j.biosystems.2010.06.005

 

Evolution of form and function

The previous project goal was an evolutionary system able to design a structure optimized for a task. In this work we have designed a system able to evolve virtual organisms that interact with a virtual world.

Organisms are encoded in an indirect way by a genome that controls the division and differentiation of a multicellular graph-like phenotype. They are simulated as spring networks in the virtual environment to determine their skills as path followers. Organisms are formed from three types of cells: motors cells, sensors cells, and structural cells. During simulation in the virtual world, motors cells continually push in their direction, sensors cells enlongate when exiting the path, and structural cells are normal springs without any particular effect.

An evolutionary algorithm evolves organisms to optimize their ability to traverse a path. A rich variety of evolved original behaviors to follow a path has been observed, showing skills that are complex, considering the simplicity of their bodies

The following animation shows an example of an evolved organism traversing a path. Edges in red color are motor edges, cyan edges are sensors, and structural edges are showed in green. It can be seen that, as some sensors exit the path, their change in length pushes some nodes towards the interior of the path (they cannot extend outside of the organism, because there is a solid external skeleton of structural edges), this displaces the forces of friction in a way that corrects the direction of the organism, which recovers its original configuration when it travels again over the path.

 

 

The following animation demonstrates an example of the very complex behavior of an evolved organism in the virtual world. The organism follows a straight direction when it is inside of the path. When it exits the path the sensor elongates and provokes an unstable equilibrium, since a pair of motors moves forward. This equilibrium breaks at some point and forces the organism to return, since the pair of motors now points backwards. When it reenters the path, the sensor restores its rest length and the pair of motor edges returns to the normal position, correcting the original direction of the organism some 40º, what allows traveling the path again.

 

 

For more information, please see the following paper:

Lobo D & Vico FJ (2010) Evolution of form and function in a model of differentiated multicellular organisms with gene regulatory networks. Biosystems, 102(2-3): 112-123. DOI:10.1016/j.biosystems.2010.08.003

 

Self-regulated artifical embryology

Since in most extant animal species the complex growth from zygote to adult organism is orchestrated by a complex gene regulatory network (GRN), the prevalent view is that the evolution of diverse morphologies must result from the evolution of diverse GRN topologies. Therefore, in typical implementations of evolutionary algorithms with artificial embryogeny (as the previous examples) a more or less complex genetic model controls the development of individuals. However, the introduction of a developmental stage adds a new layer of complexity in many cases.

In this context, we present a study which represents an exploration of how small the genetic component of an AD model can become, while also keeping structural principles simple and still enabling an evolutionary search to solve a problem; in this case, give rise to a diversity of morphologies. We abstract embryonic tissues as tensegrity structures. Since the elements of a tensegrity structure store potential energy, the structure can find itself in an unstable state. If the balance of forces is perturbed beyond a certain threshold, whether by shape deformation or modification of the stress properties of the elements, the structure will "snap" to accommodate these new constraints. It will then settle again into a lower-energy state possibly characterized by a very different shape, dissipating potential energy in the process.

Our work is inspired by a simple 2D developmental model of invagination, in which a circular sheet of cells is modeled as a closed chain of cellular cytoskeletons. To provoke an invagination process in one region of the cell sheet, it is sufficient to shorten the resting length of the outer elastic links in that region. This shows that a very simple and localized genetic signal controlling only a few cytoskeletal features is able to induce a dramatic phenotypic change:

We adopt a similar 2D structure as a starting point for the present evolutionary study, leaving aside its origins as a cell sheet model. Instead, we construe it as an abstract model of morphogenetic processes. In our model, the genome specifies a list of perturbations to the structure (erasing some elastic links, or changing their stiffness and/or length). These perturbations are applied just at the beggining of the simulation, and then the tensegrity structure undergoes a series of complex shape changes, which are entirely regulated by its geometry and physics, wihtout genomic control. In other words, the genome just specifies an initial state, and the ensuing developmental process is self-regulated. Applying an evolutionary algorithm to select for genomes able to induce a long sequence of changes, we arrive at diverse morphologies:

 Morphologies

 

 

For more information on this project, please see the following paper:

J.D. Fernández, F. Vico, R. Doursat,
Complex and Diverse Morphologies Can Develop from a Minimal Genomic Model,
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO2012),
New York, United States, 2012.

 

 

Computation from spatial constraints

The explicit treatment of space in computer models and algorithms is one of the topics of spatial computing, and it can be harnessed to design novel evolutionary algorithms.

In evolutionary algorithms, the genomes of the individuals being optimized are mutated, and the best ranked ones are selected. However, in rugged fitness landscapes, many coordinated changes may be needed in order to transform a given individual into a better one, so the evolutionary search is likely to get trapped in local optima. Artificial embryogeny, explained in the previous sections, provides the means to solve this problem: when genomes indirectly encode the structure and the behavior of the agents as the specifications or instructions to drive a self-organization or self-assembly process, a small mutation in the genome is frequently translated as many (small or big) correlated changes in the phenotype, potentially smoothing the fitness landscape.

However, a similar morphogenetic effect can be attained at the evolutionary scale (instead of in the genotype-phenotype mapping) if the mutation operator is able to make many coordinated changes to the phenotype directly, even if the genotype-phenotype mapping is mainly direct. For example, when the individuals subject to evolutionary optimization are modeled as networks of elastic links (springs), such a mutation operator can be implemented as a random change of the natural length of one or more randomly chosen links, followed by a physical simulation of the relaxation process. Eventually, the structure stabilizes into a new configuration with many correlated changes:

Spatial mutation operator

Evolutionary algorithms with artificial embryogeny have been applied in a wide range of design problems, including the structure and controller of robots, digital creatures in Artificial Life studies, and computer animated characters. However, in almost all these models, the control system is fairly complex (often, some kind of recurrent neural network), and in many cases this is unnecessarily overcomplicated.

However, and explicit modeling of space can be often used to minimize the need for complex control systems. Drawing inspiration from molecular motor proteins, we have designed agents able to walk along a filament without a complex control system, but just a simple reactive system in their limbs. The walking behavior emerges from the interaction between the morphology of the structure and its reactive system, and the filament:

For more information on this project, please see the following papers:

J.D. Fernández, R. Doursat, F. Vico,
The Evolution of Controller-Free Molecular Motors from Spatial Constraints,
Proceedings of the Spatial Computing Workshop 2012 (SCW2012),
Valencia, Spain, 2012.

J.D. Fernández, F.J. Vico,
Automating the search of molecular motor templates by evolutionary methods,
Biosystems, vol. 106, pp. 82-93, 2011.

 

 

L-system evolution

L-systems constitute a powerful formal method to encode complex structures. It consists in a parallel string rewriting system. A graphical interpretation is usually associated to the words generated by the system, such that each symbol represents a basic graphical instruction such as “draw forward” or “turn the pen 90º”. Those generated graphics could represent for example abstract forms, structures, or biological plant morphologies.

Understanding the dynamics of biodiversity has become an important line of research in theoretical ecology and, in particular, conservation biology. However, studying the evolution of ecological communities under traditional modeling approaches based on differential calculus requires species' characteristics to be predefined, which limits the generality of the results. An alternative but less standardized methodology relies on intensive computer simulation of evolving communities made of simple, explicitly described individuals. We have studied the formation, evolution and diversity dynamics of a community of virtual plants based on L-systems. On the population scale, the heterogeneous spatial structuration of the plant community at each generation depends solely on the evolution of its component plants. Generated morphologies vary from the simplest one-branch structure of promoter plants to a complex arborization of several hundred thousand branches in highly evolved variants:

 
 
 
 

The results demonstrate that diversity can spontaneously emerge in a community of mutually interacting individuals under the influence of specific environmental conditions. The cost of growing largely determines the dynamics of the model. If growing is cheap, we observe that our simulated plants evolve increasingly elaborate canopies, which are capable of intercepting ever greater amounts of light:

 
 

However, if growing is expensive, plants will keep simpler and closer to the ground, getting more complex only when the local population density triggers red queen races:

 

 

 

For more information on this project, please see the following paper:

J.D. Fernández, F.J. Vico, D. Lobo, G. Martín, R. Doursat,
Emergent diversity in an open-ended evolving virtual community,
Artificial Life, vol. 18(2):199-222, 2012.

 

 

Machine metabolism

GEB, in collaboration with the Cornell Computational Synthesis Lab in the USA, have designed and implemented a non-conventional evolutionary algorithm that has been inspired by biological metabolism. Biological metabolism is the process by which an organism breaks food down into its constituent modular elements and the uses those raw materials to create new tissue. Through duplicating these properties in a robotic ecology and composing, decomposing, and then recomposing items out of such modular elements results in the possibility of gaining a wide range of applications, ranging from infrastructure recovery to space exploration. The first steps that we have accomplished in this line is a solution for the algorithmic problem of: how to transform an initial structure into an unknown desired target structure that optimizes a known desired new function, and how to design a truss such that it is easily robotically manipulatable.

Individuals in this evolutionary algorithm are reconfiguration plans for structures especially designed for robotic manipulation. The target structure is not explicitly specified, only its desired function, and so the planning needs to account for both the design and the corresponding deconstruction and construction sequence simultaneously.

The following figure shows a physical implementation of an evolved reconfiguration process. The original structure is shown in (1). The evolved reconfiguration steps are shown in (2-9). The final evolved structure is shown in (9), which optimizes the required functions of height and robustness in a minimum number of steps.

 

ncea.reconfreal
   

 

In order to demonstrate the robustness of the algorithm experiments have been performed by randomly deleting 10% of the edges of the given structure. An example is shown in the next figure where a reconfiguration process has evolved transforming the left structure into the right one. The optimized function is yet again aimed at obtaining a new structure with maximum height and adequate robustness in a minimum number of steps.

 

 
 
ncea.reconfdiagram
 

Finally, more complex functional requirements have been tested. A physics simulator based on springs has been implemented to realistically simulate the resulting structures. The following figure shows an evolutionary result using the physics simulator with the aim to find a bridge by maximizing the length of the structure, but, at the same time, minimizing the tension of the edges and the deflection of the structure under its own weight.

 

ncea.bridge

 

 

For more information on this project, please see the following paper:

D. Lobo, D.A. Hjelle, H. Lipson

Proceedings of  ReMAR2009, ASME/IFToMM International Conference on Reconfigurable Mechanisms and Robots, London, UK, 2009.