nach oben

2009 | Buch

Kapitel lesen Erstes Kapitel lesen

Artificial Life: Borrowing from Biology

4th Australian Conference, ACAL 2009, Melbourne, Australia, December 1-4, 2009. Proceedings

herausgegeben von: Kevin Korb, Marcus Randall, Tim Hendtlass

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book constitutes the refereed proceedings of the 4th Australian Conference on Artificial Life, ACAL 2009, held in Melbourne, Australia, in December 2009. The 27 revised full papers presented were carefully reviewed and selected from 60 submissions. Research in Alife covers the main areas of biological behaviour as a metaphor for computational models, computational models that reproduce/duplicate a biological behaviour, and computational models to solve biological problems. Thus, Alife features analyses and understanding of life and nature and helps modeling biological systems or solving biological problems. The papers are organized in topical sections on alife art, game theory, evolution, complex systems, biological systems, social modelling, swarm intelligence, and heuristics.

Inhaltsverzeichnis

Frontmatter

Alife Art

An Empirical Exploration of a Definition of Creative Novelty for Generative Art

Abstract

We explore a new definition of creativity — one which emphasizes the statistical capacity of a system to generate previously unseen patterns — and discuss motivations for this perspective in the context of machine learning. We show the definition to be computationally tractable, and apply it to the domain of generative art, utilizing a collection of features drawn from image processing. We next utilize our model of creativity in an interactive evolutionary art task, that of generating biomorphs. An individual biomorph is considered a potentially creative system by considering its capacity to generate novel children. We consider the creativity of biomorphs discovered via interactive evolution, via our creativity measure, and as a control, via totally random generation. It is shown that both the former methods find individuals deemed creative by our measure; Further, we argue that several of the discovered “creative” individuals are novel in a human-understandable way. We conclude that our creativity measure has the capacity to aid in user-guided evolutionary tasks.

Taras Kowaliw, Alan Dorin, Jon McCormack

A New Definition of Creativity

Abstract

Creative artifacts can be generated by employing A-Life software, but programmers must first consider, explicitly or implicitly, what would count as creative. Most apply standard definitions that incorporate notions of novelty, value and appropriateness. Here we re-assess this approach. Some basic facts about creativity suggest criteria that guide us to a new definition of creativity. We briefly defend our definition against some plausible objections and explore the ways in which this new definition differs and improves upon the alternatives.

Alan Dorin, Kevin B. Korb

Genetically Optimized Architectural Designs for Control of Pedestrian Crowds

Abstract

Social force based modeling of pedestrian crowds is an advanced microscopic approach for simulating the dynamics of pedestrian motion and has been effectively used for pedestrian simulations in both normal and panic situations. A disastrous form of pedestrian behavior is stampede, which is usually triggered in life-threatening situations such as fires in crowded public halls or rush for some large-scale events (like millions praying to the gods at an auspicious time and space). The architectural designs of the hall influence to a large extent the evacuation process. In this paper we apply an advanced genetic algorithm for optimal designs of suitable architectural entities so as to smoothen the pedestrian flow in panic situations. This has practical implications in saving lives/ injuries during a stampede. The effects of these new designs in normal situations are also discussed.

Pradyumn Kumar Shukla

Game Theory

Co-evolutionary Learning in the N-player Iterated Prisoner’s Dilemma with a Structured Environment

Abstract

Co-evolutionary learning is a process where a set of agents mutually adapt via strategic interactions. In this paper, we consider the ability of co-evolutionary learning to evolve cooperative strategies in structured populations using the N-player Iterated Prisoner’s Dilemma (NIPD). To do so, we examine the effects of both fixed and random neighbourhood structures on the evolution of cooperative behaviour in a lattice-based NIPD model. Our main focus is to gain a deeper understanding on how co-evolutionary learning could work well in a spatially structured environment. The numerical experiments demonstrate that, while some recent studies have shown that neighbourhood structures encourage cooperation to emerge, the topological arrangement of the neighbourhood structures is an important factor that determines the level of cooperation.

Raymond Chiong, Michael Kirley

Evolving Cooperation in the N-player Prisoner’s Dilemma: A Social Network Model

Abstract

We introduce a social network based model to investigate the evolution of cooperation in the N-player prisoner’s dilemma game. Agents who play cooperatively form social links, which are reinforced by subsequent cooperative actions. Agents tend to interact with players from their social network. However, when an agent defects, the links with its opponents in that game are broken. We examine two different scenarios: (a) where all agents are equipped with a pure strategy, and (b) where some agents play with a mixed strategy. In the mixed case, agents base their decision on a function of the weighted links within their social network. Detailed simulation experiments show that the proposed model is able to promote cooperation. Social networks play an increasingly important role in promoting and sustaining cooperation in the mixed strategy case. An analysis of the emergent social networks shows that they are characterized by high average clustering and broad-scale heterogeneity, especially for a relatively small number of players per game.

Golriz Rezaei, Michael Kirley, Jens Pfau

Using Misperception to Counteract Noise in the Iterated Prisoner’s Dilemma

Abstract

The Iterated Prisoner’s Dilemma is a game-theoretical model which can be identified in many repeated real-world interactions between competing entities. The Tit for Tat strategy has been identified as a successful strategy which reinforces mutual cooperation, however, it is sensitive to environmental noise which disrupts continued cooperation between players to their detriment. This paper explores whether a population of Tit for Tat players may evolve specialised individual-based noise to counteract environmental noise. We have found that when the individual-based noise acts similarly to forgiveness it can counteract the environmental noise, although excessive forgiveness invites the evolution of exploitative individual-based noise, which is highly detrimental to the population when widespread.

Lachlan Brumley, Kevin B. Korb, Carlo Kopp

Evolution

An Analysis and Evaluation of the Saving Capability and Feasibility of Backward-Chaining Evolutionary Algorithms

Abstract

Artificial Intelligence, volume 170, number 11, pages 953–983, 2006 published a paper titled “Backward-chaining evolutionary algorithm”. It introduced two fitness evaluation saving algorithms which are built on top of standard tournament selection. One algorithm is named Efficient Macro-selection Evolutionary Algorithm (EMS-EA) and the other is named Backward-chaining EA (BC-EA). Both algorithms were claimed to be able to provide considerable fitness evaluation savings, and especially BC-EA was claimed to be much efficient for hard and complex problems which require very large populations. This paper provides an evaluation and analysis of the two algorithms in terms of the feasibility and capability of reducing the fitness evaluation cost. The evaluation and analysis results show that BC-EA would be able to provide computational savings in unusual situations where given problems can be solved by an evolutionary algorithm using a very small tournament size, or a large tournament size but a very large population and a very small number of generations. Other than that, the saving capability of BC-EA is the same as EMS-EA. Furthermore, the feasibility of BC-EA is limited because two important assumptions making it work hardly hold.

Huayang Xie, Mengjie Zhang

Evolutionary Intelligence and Communication in Societies of Virtually Embodied Agents

Abstract

In order to overcome the knowledge bottleneck problem, AI researchers have attempted to develop systems that are capable of automated knowledge acquisition. However, learning in these systems is hindered by context (i.e., symbol-grounding) problems, which are caused by the systems lacking the unifying structure of bodies, situations and needs that typify human learning. While the fields of Embodied Artificial Intelligence and Artificial Life have come a long way towards demonstrating how artificial systems can develop knowledge of the physical and social worlds, the focus in these areas has been on low level intelligence, and it is not clear how, such systems can be extended to deal with higher-level knowledge. In this paper, we argue that we can build towards a higher level intelligence by framing the problem as one of stimulating the development of culture and language. Specifically, we identify three important limitations that face the development of culture and language in AI systems, and propose how these limitations can be overcome. We will do this through borrowing ideas from the evolutionary sciences, which have explored how interactions between embodiment and environment have shaped the development of human intelligence and knowledge.

Binh Nguyen, Andrew Skabar

Testing Punctuated Equilibrium Theory Using Evolutionary Activity Statistics

Abstract

The Punctuated Equilibrium hypothesis (Eldredge and Gould,1972) asserts that most evolutionary change occurs during geologically rapid speciation events, with species exhibiting stasis most of the time. Punctuated Equilibrium is a natural extension of Mayr’s theories on peripatric speciation via the founder effect, (Mayr, 1963; Eldredge and Gould, 1972) which associates changes in diversity to a population bottleneck. That is, while the formation of a foundation bottleneck brings an initial loss of genetic variation, it may subsequently result in the emergence of a child species distinctly different from its parent species. In this paper we adapt Bedau’s evolutionary activity statistics (Bedau and Packard, 1991) to test these effects in an ALife simulation of speciation. We find a relative increase in evolutionary activity during speciations events, indicating that punctuation is occurring.

O. G. Woodberry, K. B. Korb, A. E. Nicholson

Complex Systems

Evaluation of the Effectiveness of Machine-Based Situation Assessment

Abstract

This paper describes a technique for measuring the effectiveness of machine-based situation assessment, one of the levels of data fusion. Using the computer to perform situation assessment assists human operators in comprehending complex situations. The evaluation technique is an iterative one that utilises a metric to measure the divergence between the situation assessment and the ground truth in a simulation environment. Different pieces of divergent information can be weighted separately using methods based on the Hamming distance, the number of antecedents, or a Bayesian approach. The evaluation technique is explored using Random Inference Networks and shows promise. The results are very sensitive to the phase of the inference network, i.e. stable, critical or chaotic phase.

David M. Lingard, Dale A. Lambert

Experiments with the Universal Constructor in the DigiHive Environment

Abstract

The paper discusses the performance and limitations of the universal constructor embedded in the DigiHive environment and presents the results of two simulation experiments showing the possibility of workaround the limitations.

Rafal Sienkiewicz

Making a Self-feeding Structure by Assembly of Digital Organs

Abstract

In Nature, the intrinsic cooperation between organism’s parts is capital. Most living systems are composed of organs, functional units specialized for specific actions. In our last research, we developed an evolutionary model able to generate artificial organs. This paper deals with the assembly of organs. We show, through experimentation, the development of an artificial organism composed of four digital organs able to produce a self-feeding organism. This kind of structure has applications in the mophogenetic-engineering of future nano and bio robots.

Sylvain Cussat-Blanc, Hervé Luga, Yves Duthen

Towards Tailored Communication Networks in Assemblies of Artificial Cells

Abstract

Living Technology is researching novel IT making strong use of programmable chemical systems. These chemical systems shall finally converge to artificial cells resulting in evolvable complex information systems. We focus on procedural manageability and information processing capabilities of such information systems. Here, we present a novel resource-saving formation, processing, and examination procedure to generate and handle single compartments representing preliminary stages of artificial cells. Its potential is exemplified by testing the influence of different glycerophospholipids on the stability of the compartments. We discuss how the procedure could be used both in evolutionary optimization of self-assembling amphiphilic systems and in engineering tailored communication networks enabling life-like information processing in multicompartment aggregates of programmable composition and spatial configuration.

Maik Hadorn, Bo Burla, Peter Eggenberger Hotz

Biological Systems

A Developmental System for Organic Form Synthesis

Abstract

Modelling the geometry of organic forms using traditional CAD or animation tools is often difficult and tedious. Different models of morphogenesis have been successfully applied to this problem; however many kinds of organic shape still pose difficulty. This paper introduces a novel system, the Simplicial Developmental System (SDS), which simulates morphogenetic and physical processes in order to generate specific organic forms. SDS models a system of cells as a dynamic simplicial complex in two or three dimensions that is governed by physical rules. Through growth, division, and movement, the cells transform the geometric and physical representations of the form. The actions of the cells are governed by conditional rules and communication between cells is supported with a continuous morphogen model. Results are presented in which simple organic forms are grown using a model inspired by limb bud development in chick embryos. These results are discussed in the context of using SDS as a creative system.

Benjamin Porter

Layered Random Inference Networks

Abstract

Random Boolean Networks (RBN) have been used for decades to study the generic properties of genetic regulatory networks. This paper describes Random Inference Networks (RIN) where the aim is to study the generic properties of inference networks used in high-level information fusion. Previous work has discussed RIN with a linear topology, and this paper introduces RIN with a layered topology. RIN are related to RBN, and exhibit stable, critical and chaotic dynamical regimes. As with RBN, RIN have greatest information propagation in the critical regime. This raises the question as to whether there is a driver for real inference networks to be in the critical regime as has been postulated for genetic regulatory networks. Key Words: situation assessment, inference network, information propagation, criticality

David M. Lingard

Modelling Hepatitis B Virus Antiviral Therapy and Drug Resistant Mutant Strains

Abstract

Despite the existence of vaccines, the Hepatitis B virus (HBV) is still a serious global health concern. HBV targets liver cells. It has an unusual replication process involving an RNA pre-genome that the reverse transcriptase domain of the viral polymerase protein translates into viral DNA. The reverse transcription process is error prone and together with the high replication rates of the virus, allows the virus to exist as a heterogeneous population of mutants, known as a quasispecies, that can adapt and become resistant to antiviral therapy. This study presents an individual-based model of HBV inside an artificial liver, and associated blood serum, undergoing antiviral therapy. This model aims to provide insights into the evolution of the HBV quasispecies and the individual contribution of HBV mutations in the outcome of therapy.

Julie Bernal, Trevor Dix, Lloyd Allison, Angeline Bartholomeusz, Lilly Yuen

Multivesicular Assemblies as Real-World Testbeds for Embryogenic Evolutionary Systems

Abstract

Embryogenic evolution emulates in silico cell-like entities to get more powerful methods for complex evolutionary tasks. As simulations have to abstract from the biological model, implicit information hidden in its physics is lost. Here, we propose to use cell-like entities as a real-world in vitro testbed. In analogy to evolutionary robotics, where solutions evolved in simulations may be tested in real-world on macroscale, the proposed vesicular testbed would do the same for the embryogenic evolutionary tasks on mesoscale. As a first step towards a vesicular testbed emulating growth, cell division, and cell differentiation, we present a modified vesicle production method, providing custom-tailored chemical cargo, and present a novel self-assembly procedure to provide vesicle aggregates of programmable composition.

Maik Hadorn, Peter Eggenberger Hotz

Social Modelling

Designing Adaptive Artificial Agents for an Economic Production and Conflict Model

Abstract

Production and conflict models have been used over the past 30 years to represent the effects of unproductive resource allocation in economics. Their major applications are in modelling the assignment of property rights, rent-seeking and defense economics. This paper describes the process of designing an agent used in a production and conflict model. Using the capabilities of an agent-based approach to economic modelling, we have enriched a simple decision-maker of the kind used in classic general equilibrium economic models, to build an adaptive and interactive agent which uses its own attributes, its neighbors’ parameters and information from its environment to make resource allocation decisions. Our model presents emergent and adaptive behaviors than cannot be captured using classic production and conflict agents. Some possible extensions for future applications are also recommended.

Behrooz Hassani-M, Brett W. Parris

Emergent Societal Effects of Crimino-Social Forces in an Animat Agent Model

Abstract

Societal behaviour can be studied at a causal level by perturbing a stable multi-agent model with new microscopic behaviours and observing the statistical response over an ensemble of simulated model systems. We report on the effects of introducing criminal and law-enforcing behaviours into a large scale animat agent model and describe the complex spatial agent patterns and population changes that result. Our well-established predator-prey substrate model provides a background framework against which these new microscopic behaviours can be trialled and investigated. We describe some quantitative results and some surprising conclusions concerning the overall societal health when individually anti-social behaviour is introduced.

Chris J. Scogings, Ken A. Hawick

Swarm Intelligence

A Heterogeneous Particle Swarm

Abstract

Almost all Particle Swarm Optimisation (PSO) algorithms use a number of identical, interchangeable particles that show the same behaviour throughout an optimisation. This paper describes a PSO algorithm in which the particles, while still identical, have two possible behaviours. Particles are not interchangeable as they make independent decisions when to change between the two possible behaviours. The difference between the two behaviours is that the attraction towards a particle’s personal best in one is changed in the other to repulsion from the personal best position. Results from experiments on three standard functions show that the introduction of repulsion enables the swarm to sequentially explore optima in problem space and enables it to outperform a conventional swarm with continuous attraction.

Luke Cartwright, Tim Hendtlass

An Analysis of Locust Swarms on Large Scale Global Optimization Problems

Abstract

Locust Swarms are a recently-developed multi-optima particle swarm. To test the potential of the new technique, they have been applied to the 1000-dimension optimization problems used in the recent CEC2008 Large Scale Global Optimization competition. The results for Locust Swarms are competitive on these problems, and in particular, much better than other particle swarm-based techniques. An analysis of these results leads to a simple guideline for parameter selection in Locust Swarms that has a broad range of effective performance. Further analysis also demonstrates that “dimension reductions” during the search process are the single largest factor in the performance of Locust Swarms and potentially a key factor in the performance of other search techniques.

Stephen Chen

Continuous Swarm Surveillance via Distributed Priority Maps

Abstract

With recent and ongoing improvements to unmanned aerial vehicle (UAV) endurance and availability, they are in a unique position to provide long term surveillance in risky environments. This paper presents a swarm intelligence algorithm for executing an exhaustive and persistent search of a non-trivial area of interest using a decentralized UAV swarm without long range communication. The algorithm allows for an environment containing arbitrary arrangements of no-fly zones, non-uniform levels of priority and dynamic priority changes in response to target acquisition or external commands. Performance is quantitatively analysed via comparative simulation with another leading algorithm of its class.

David Howden

Optimization in Fractal and Fractured Landscapes Using Locust Swarms

Abstract

Locust Swarms are a newly developed multi-optima particle swarm. They were explicitly developed for non-globally convex search spaces, and their non-convergent search behaviours can also be useful for problems with fractal and fractured landscapes. On the 1000-dimensional “FastFractal” problem used in the 2008 CEC competition on Large Scale Global Optimization, Locust Swarms can perform better than all of the methods in the competition. Locust Swarms also perform very well on a real-world optimization problem that has a fractured landscape. The extent and the effects of a fractured landscape are observed with a practical new measurement that is affected by the degree of fracture and the lack of regularity and symmetry in a fitness landscape.

Stephen Chen, Vincent Lupien

Heuristics

A Hybrid Extremal Optimisation Approach for the Bin Packing Problem

Abstract

Extremal optimisation (EO) is a simple and effective technique that is influenced by nature and which is especially suitable to solve assignment type problems. EO uses the principle of eliminating the weakest or the least adapted component and replacing it by a random one. This paper presents a new hybrid EO approach that consists of an EO framework with an improved local search for the bin packing problem (BPP). The stochastic nature of the EO framework allows the solution to move between feasible and infeasible spaces. Hence the solution has the possibility of escaping from a stagnant position to explore new feasible regions. The exploration of a feasible space is complemented with an improved local search mechanism developed on the basis of the proposed Falkenauer’s technique. The new local search procedure increases the probability of finding better solutions. The results show that the new algorithm is able to obtain optimal and efficient results for large problems when the approach is compared with the best known methods.

Pedro Gómez-Meneses, Marcus Randall

Feedback of Delayed Rewards in XCS for Environments with Aliasing States

Abstract

Wilson [13] showed how delayed reward feedback can be used to solve many multi-step problems for the widely used XCS learning classifier system. However, Wilson’s method – based on back-propagation with discounting from Q-learning – runs into difficulties in environments with aliasing states, since the local reward function often does not converge. This paper describes a different approach to reward feedback, in which a layered reward scheme for XCS classifiers is learnt during training. We show that, with a relatively minor modification to XCS feedback, the approach not only solves problems such as Woods1 but can also solve aliasing states problems such as Littman57, MiyazakiA and MazeB.

Kuang-Yuan Chen, Peter A. Lindsay

Memetic Approaches for Optimizing Hidden Markov Models: A Case Study in Time Series Prediction

Abstract

We propose a methodology for employing memetics (local search) within the framework of evolutionary algorithms to optimize parameters of hidden markov models. With this proposal, the rate and frequency of using local search are automatically changed over time either at a population or individual level. At the population level, we allow the rate of using local search to decay over time to zero (at the final generation). At the individual level, each individual is equipped with information of when it will do local search and for how long. This information evolves over time alongside the main elements of the chromosome representing the individual.

We investigated the performance of different local search schemes with different rates and frequencies as well as the two newly proposed strategies. Four time series of the exchange rate were used to test the performance. The results showed the inconsistent behaviour of the approaches that used manual settings on local search’s parameters, while showing the good performance of adaptive and self-adaptive strategies.

Lam Thu Bui, Michael Barlow

The Effects of Different Kinds of Move in Differential Evolution Searches

Abstract

In the commonly used DE/rand/1 variant of differential evolution the primary mechanism of generating new solutions is the perturbation of a randomly selected point by a difference vector. The newly selected point may, if good enough, then replace a solution from the current generation. As the replaced solution is not the one perturbed to create the new, candidate solution, when the population has divided into isolated clusters large moves by solutions are the result of small difference vectors applied within different clusters. Previous work on two- and 10-dimensional problems suggests that these are the main vehicle for movement between clusters and that the quality improvements they yield can be significant. This study examines the existence of such non-intuitive moves in problems with a greater number of dimensions and their contribution to the search—changes in solution quality and impact on population diversity—over the course of the algorithm’s run. Results suggest that, while they frequently contribute solutions of higher quality than genuine large moves, they contribute to population convergence and, therefore, may be harmful.

James Montgomery

Backmatter

Titel: Artificial Life: Borrowing from Biology
herausgegeben von: Kevin Korb
Marcus Randall
Tim Hendtlass
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-10427-5
Print ISBN: 978-3-642-10426-8
DOI: https://doi.org/10.1007/978-3-642-10427-5