Recent Advances in Artificial Life

Preface

Contents

Any study of the evolutionary past is hampered by the size and type of events involved. Change on such a grand scale cannot be observed directly or manipulated experimentally, and so to date it has been deduced from clues left in the present day. This limitation can be overcome by replaying the course of evolution and observing what results and whether it matches what we know of present day biology. Here I present MeSA, a sophisticated framework for the simulation of large-scale evolution, and demonstrate how this approach can be used to investigate key innovations, a putative cause of patterns of biodiversity.

During the last decade, Air Traffic movements worldwide have experienced a tremendous growth with new concepts such as Free Flight. Under Free Flight, current procedures of Airways and Waypoints for maintaining separation wouldn’t be there. In the absence of Airway structure and ground based tactical support, automated conflict detection and resolution tools will be required to ensure safe and smooth flow of Air traffic. The main challenge is to develop robust and efficient conflict detection and resolution algorithms to achieve real time performance for complex scenarios of conflicts in a Free Flight Airspace. This paper investigates preliminary design and implementation issues in two dimension application of evolutionary techniques for collision detection and resolution. The preliminary results demonstrate that an artificial neural network (ANN) using evolutionary techniques can be trained not only follow optimum trajectories, but also to detect and avoid collisions in two dimensions.

Genotype-phenotype mapping plays an important role in the evolutionary process. In this paper, we argue that an adaptive mapping could help to solve a special class of highly epistatic problems known as rotated problems. Our conjecture is that co-evolving the mapping represented by a population of matrices in parallel with the genotypes will overcome the problem of epistasis. We use the fast evolutionary programming (FEP) algorithm which is known to be unsuitable for rotated problems. We compare the results against the traditional FEP and a conventional co-evolutionary algorithm. The results show that, in tackling rotated problems, both FEP and the co-evolutionary FEP were inferior to the proposed model.

In this article we present an agent-based simulations of the spread of a vector borne disease in a population with limited mobility. The model assumes two types of agents, namely “vectors” and “people agents”; infections can only be transmitted between agents of different type. We discuss how the infection levels of the population depend on the mobility of agents.

Enumeration of the factors underlying the formation of modules and hierarchical structures in evolution is a major current goal of artificial life research. Evolutionary algorithms are often pressed into service, but it is not clear how the various possible features of such models facilitate this goal. We address this question by using a model that allows experimentation with several candidate model features. We show how the notions of variable length genotype, variable genotype to phenotype mapping, pseudo-spatial environment, and memetic evolution can be combined. We quantify the effects of these features using measures of module size, and show that information shared between individuals allows them to build modules and combine them to form hierarchical structures. These results suggest an important role for phase changes in this process, and should inform current artificial life research.

Patterns are a tool that enables the collective knowledge of a particular community to be recorded and transmitted in an efficient manner. Initially developed in the field of architecture and later developed by software engineers [138], they have now been adopted by the complex systems modelling community [417]. It can be argued that, while most complex systems models are idiosyncratic and highly specific to the task for which they are constructed, certain tools and methodologies may be abstracted to a level at which they are more generally applicable. This paper presents one such pattern, Perturbation Analysis, which describes the underlying framework used by several analytical and visualisation tools to quantify and explore the stability of dynamic systems. The format of this paper follows the outline specified in [417].

Evolutionary processes and the dynamics of Mendelian populations result from the complex interactions of organisms with other organisms and with their environment. Through simulations of virtual organisms the basic dynamics of these populations can be emulated. A conceptual model is used to define the universe, the hierarchical structures and a small set of rules that govern the basic behavior of these virtual populations. At the organism level a simple genetic algorithm is used to model the genotype of the entities and the Mendelian genetic processes. The model is implemented in an educational simulator called Sigex. From a small set of low level rules at the organism level, higher-order population and environmental interactions emerge that are in accordance to those postulated by the theory of population genetics.

Evolutionary behaviour in “animat” or physical-agent models has been explored by several researchers, using a number of variations of the genetic algorithmic approach. Most have used a bio-inspired mutation/evolution of low-level behaviours or model properties and this leads to large and mostly “uninteresting” model phase-spaces or fitness landscapes. Instead we consider individual animats that evolve their priorities amongst short-lists of high-level behavioural rules rather than of lower-level individual instructions. This dramatically shrinks the combinatorial size of the fitness landscape and focuses on variations within the “interesting” regime. We describe a simple evolutionary survival experiment, which showed that some rule-priorities are drastically more successful than others. We report on the success of the rule-priority evolutionary approach for our predator-prey animat model and consider how it would apply to more general agent-based models.

Despite its early successes, ALife has not tended to live up to its original promise, with any emergent behavior very rarely manifesting itself in such a way that new higher level emergence can occur. This problem has been recognised in two related concepts; the failure of ALife simulations to display Open Ended Evolution, and their inability to dynamically generate more than two hierarchical levels of behavior. This paper will suggest that these problems of ALife stem from a missing sense of contextuality in the models of ALife. A number of theories which exhibit some form of contextual dependence will be discussed, in particular, the gauge theories of quantum field theory.

Several studies have shown the existence of critical transition phenomena in cellular automata rule-space (i.e. a sharp transition from order to chaos), but the problem of precisely localising such transitional regime in the rule-space has not been solved yet. Previous parametric approaches, such as classic lambda parameter, failed to individuate a precise parameter value at which the transition is found. In this work we localise the critical transition in a parameterised survey of multi-valued cellular automata rule-space, showing that there exists a hyperplane that precisely localises the critical transition and cuts the rule-space into two separate regions: the region of ordered rules and the region of chaotic rules. We also found that near this hyperplane, complex rules neither ordered nor chaotic, are likely to be found. Moreover, considering the normal vector of the hyperplane, we define a new critical parameter that is able to localise the critical transition.

Traditional approaches to evolvable hardware (EHW), in which the field programmable gate array (FPGA) configuration is directly encoded, have not scaled well with increasing circuit and FPGA complexity. To overcome this there have been moves towards encoding a growth process, known as morphogenesis. Using a morphogenetic approach, has shown success in scaling gate-level EHW for a signal routing problem, however, when faced with a evolving a one-bit full adder, unforseen difficulties were encountered.

In this paper, we provide a measurement of EHW problem difficulty that takes into account the salient features of the problem, and when combined with a measure of feedback from the fitness function, we are able to estimate whether or not a given EHW problem is likely to be able to be solved successfully by our morphogenetic approach. Using these measurements we are also able to give an indication of the scalability of morphogenesis when applied to EHW.

Evolutionary algorithms are a practical means of optimising the topology of graphs. This paper explores the use of phenotype diversity measures as objectives in a graph grammar-based model of multi-objective graph evolution. Since the initial population in this model is exclusively constituted by empty productions, an active promotion of diversity is needed to establish the necessary building blocks from which optimal graphs can be constructed. Six diversity measures are evaluated on problems of symbolic regression, the 6-multiplexer, and neural control of double pole balancing. The highest success rates are obtained by defining diversity as the number of solutions that differ in at least one fitness case and do not Pareto-dominate each other.

When Trivers [396] introduced the concept of parental investment to evolutionary theory, he clarified many of the issues surrounding sexual selection. In particular, he demonstrated how sex differences in parental investment can explain how sexually dimorphic structure and behaviour develops in a species. However, the origins of dimorphic parental investments also need explanation. Trivers and others have suggested several hypotheses, including ones based on prior investment, desertion, paternal uncertainty, association with the offspring and chance dimorphism. In this paper, we explore these hypotheses within the setting of an ALife simulation. We find support for all these alternatives, barring the prior investment hypothesis.

For over a century, the analysis of community food webs has been central to ecology. Community food webs describe the feeding relationships between species within an ecosystem. Over the past five years, many complex systems —including community food webs— have been shown to exhibit similar global statistical properties (such as higher than expected degree of clustering) in the arrangement of their underlying components. Recent studies have attempted to go beyond these global features, and understand the local structural regularities specific to a given system. This is done by detecting nontrivial, recurring patterns of interconnections known as motifs. Theoretical studies on the complexity and stability of ecosystems generally concluded that model ecosystems tend to be unstable. However this is contradicted by empirical studies. Here we attempt to resolve this paradox by examining the stability of common motifs, and show that the most stable motifs are most frequently encountered in real ecosystems. The presences of these motifs could explain why complex ecosystems are stable and able to persist.

We address the issue of how an embodied system can autonomously explore and discover the action possibilities inherent to its body. Our basic assumption is that the intrinsic dynamics of a system can be explored by perturbing the system through small but well-timed feedback actions and by exploiting a mechanism of feedback resonance. We hypothesize that such perturbations, if appropriately chosen, can favor the transitions from one stable attractor to another, and the discovery of stable postural configurations. To test our ideas, we realize an experimental system consisting of a ring-shaped mass-spring structure driven by a network of coupled chaotic pattern generators (called coupled chaotic fields). We study the role played by the chaoticity of the neural system as the control parameter governing phase transitions in movement space. Through a frequency-domain analysis of the emergent behavioral patterns, we show that the system discovers regions of its state space exhibiting notable properties.

Meta-heuristic search techniques have been extensively applied to static optimisation problems. These are problems in which the definition and/or the data remain fixed throughout the process of solving the problem. Many real-world problems, particularly in transportation, telecommunications and manufacturing, change over time as new events occur, thus altering the solution space. This paper explores methods for solving these problems with ant colony optimisation. A method of adapting the general algorithm to a range of problems is presented. This paper shows the development of a small prototype system to solve dynamic multidimensional knapsack problems. This system is found to be able to rapidly adapt to problem changes.

Natural ants have the property that they will follow one another along a trail between the nest and the food source (and vice versa). While this is a desirable biological property, it can lead to stagnation behaviour within artificial systems that solve combinatorial optimisation problems. Although the evaporation of pheromone within local update rules, mutating pheromone values or the bounding of pheromone values may alleviate this, they are only implicit forms of diversification within a colony. Hence, there is no guarantee that stagnation will not occur. In this paper, a new explicit diversification measure is devised that balances between the restriction and freedom of incorporating various solution components. In terms of the target applications, the travelling salesman problem and quadratic assignment problem, this form of diversification allows for the comparison of sequences of common solution components. If an ant is considered too close to another member of the colony, it is explicitly forced to select another component. This restriction may also be lifted if necessary as part of the aspiration criteria. The results reveal improved performance over a control ant colony system.

The generation of pattern and form in a developing organism results from a combination of interacting processes, guided by a programme encoded in its genome. The unfolding of this programme involves a complex interplay of gene regulation and intercellular signalling, as well as the mechanical processes of cell growth, division and movement.

In this study we present an integrated modeling framework for simulating multicellular morphogenesis that includes plausible models of both genetic and cellular processes, using leaf morphogenesis as an example. We present results of an experiment designed to investigate the contribution that genetic control of cell growth and division makes to the performance of a developing system.

Network or graph structures are ubiquitous in the study of complex systems. Often, we are interested in complexity trends of these system as it evolves under some dynamic. An example might be looking at the complexity of a food web as species enter an ecosystem via migration or speciation, and leave via extinction.

In this paper, a complexity measure of networks is proposed based on the complexity is information content paradigm. To apply this paradigm to any object, one must fix two things: a representation language, in which strings of symbols from some alphabet describe, or stand for the objects being considered; and a means of determining when two such descriptions refer to the same object. With these two things set, the information content of an object can be computed in principle from the number of equivalent descriptions describing a particular object.

I propose a simple representation language for undirected graphs that can be encoded as a bitstring, and equivalence is a topological equivalence. I also present an algorithm for computing the complexity of an arbitrary undirected network.

Templates (or patterns) in the environment are often used by social insects to guide their building activities. Robot swarms can also use templates during construction tasks. This paper develops a generalised technique for generating templates that can vary in space and with time. It is proposed that such templates are theoretically sufficient to facilitate the loose construction of any desired planar structure. This claim is supported by a number of experimental trials in which structures are built by a real robot swarm.

In small networks, ant based algorithms proved to perform better than the conventional routing algorithms. Their performance decreases by increasing the number of nodes in the network. The scalability of the algorithms is affected by the increasing number of agents used. In this paper we present a scalable Hierarchical Ant Based Control algorithm (H-ABC) for dynamic routing. The network is split into several smaller and less complex networks called sectors. The agents are divided in two categories: local ants and exploring ants. Only the nodes situated at the border between sectors can generate exploring ants, the ones used to maintain the paths between different sectors. They are carrying no stack which reduces the overhead in the network. The algorithm was implemented and its performance compared with the well known AntNet.

Artificial chemistries are promising candidates for formalisms to support designing molecular computation. One of the most significant works in the area of molecular computing is the biomolecular implementation of finite automata by Benenson et al., in which finite automata with two states were constructed using DNA and enzyme. In this study, we described their implementation using our simple artificial chemistry to model the mechanism of the computation. The rules intuitively describe the interactions among DNA molecules and enzyme. We executed the description on our simulator to confirm the correctness of the description. The capability of modelling and simulating molecular reaction will be beneficial not only in designing molecular computation but also in modelling natural living systems.

The development and use of complex systems models can involve many common problems, problems that are solved again and again by different researchers with various backgrounds and experience. The application of the software engineering patterns paradigm to complex systems modeling will enable capture of the wisdom of the network modeling community in such a way that proven solutions to recurring challenges can be identified and tailored to the specific problem at hand. The use of networks for simulation and analysis are two areas of complex systems modeling that stand to benefit from the patterns approach. The use of networks to guide thinking, as analytic tools and as visualizations is ubiquitous in the field of complex systems. However, various methods of using networks (e.g. design, updating functions, visualization, analysis) are not always obvious to a newcomer and are often assumed as general knowledge in the literature. This paper is a first step towards a pattern language addressing these issues for the complex systems community.

Inclusive fitness theory [177], better known as kin selection, has often been cited as an alternative to group selection as a way of explaining the evolution of altruistic behavior. However, an evolving understanding of inclusive fitness has seen it redefined, by its creator, in terms of levels of selection, leading to a blurring of the distinctions between the two. Hamilton suggests that if a distinction is to be made between group and kin selection, the term ‘group selection’ should only be used when there is no reliance on kin associations.

Based on the early group selection model of Gilpin [145] for the evolution of predatory restraint, Mitteldorf [282] designed an ALife simulation that models the evolution of aging and population regulation. Mitteldorf sees the evolution of aging as a case of ‘extreme’ altruism “…in the sense that the cost to the individual is high and direct, while the benefit to the population is far too diffuse to be accounted for by kin selection” [282, p. 346].

We demonstrate that Mitteldorf’s simulation is dependent on kin selection, by reproducing his ALife simulations and then introducing a mechanism to remove all and only the effects of kin selection within it. The result is the collapse of group selection in the simulation, suggesting a new understanding of the relation between group and kin selection is needed.

Over the last decade, it has widely been accepted that warfare is a complex adaptive system (CAS). The multi-agent technology is a promising tool to study CASs. The warfare intelligent system for dynamic optimization of missions (WISDOM) is an agent based distillation (ABD) system for warfare. WISDOM-II, the second version of WISDOM is based on a novel network-centric multi-agent architecture (NCMAA). WISDOM-II allows analysts to study the new theory of network centric warfare (NCW) easily and effectively. In this paper, we use multi-objective optimization to evolve capability requirements for the blue (friendly) force. We examine four setups, where either the blue or the red (adversary) force adapts NCW. We show that capability requirements are different when the red force switches from a platform centric warfare (PCW) to a NCW. For a platform-based blue force, an increase in cost is required to meet the same mission when compared to a network-centric blue force.

Appendix

Bibliography

Index