Evolutionary Computation: Theory and Applications

The following sections are included:

• Preface

• Acknowledgements

• List of Contributors

• Contents

The following sections are included:

• What Is Evolutionary Computation
  • A Brief History
  • A General Framework of Evolutionary Algorithms
  • Evolution Strategies
  • Evolutionary Programming
  • Genetic Algorithms
  • Other Topics in Evolutionary Computation

• A Brief Overview of Evolutionary Computation
  • Evolutionary Computation Theory
  • Evolutionary Optimisation
  • Evolutionary Learning

• Evolutionary Algorithm and Generate-and-Test Search Algorithm

• Search Operators
  • Recombination Operators
  • Mutation Operators
  • Selection

• Summary

• Bibliography

In the last few years we have used ALECSYS, a parallel learning classifier system based on the genetic algorithm, to develop behavioral modules for mobile robots, both simulated and real. In this paper we briefly report on our experience, and then reflect on various concepts stemming from the application of evolutionary computation to agent building. We propose a definition of agent, analyze the relationships holding between an agent and its external environment, and discuss some important similarities and differences between natural and artificial systems; in particular, we compare the concept of fitness of an organism with that of quality of an artifact. We then concentrate on adaptation, regarded as a basic process for the development of both biological organisms and artificial agents. We carry on our analysis trying to understand where and how Behavior Engineering (i.e., the discipline concerned with the development of artificial agents) might profit from the use of evolutionary strategies. We argue that an evolutionary approach might allow us to search the space of nonrational design, thus opening a whole new world of possibilities for the implementation of artificial systems.

I describe a novel paradigm for reinforcement learning (RL) with limited computational resources in realistic, non-resettable environments. The learner's policy is an arbitrary modifiable algorithm mapping environmental inputs and internal states to outputs and new internal states. Like in the real world, any event in system life and any learning process computing policy modifications may affect future performance and preconditions of future learning processes. There is no need for pre-defined “trials”. At a given time in system life, there is only one single training example to evaluate the current long-term usefulness of any given previous policy modification, namely the average reinforcement per time since that modification occurred. At certain times in system life called checkpoints, such singular observations are used by a stack-based backtracking method which invalidates certain previous policy modifications, such that the history of still valid modifications corresponds to a history of long-term reinforcement accelerations (up until to the current checkpoint, each still valid modification has been followed by faster reinforcement intake than all the previous ones). Until the next checkpoint there is time to collect delayed reinforcement and to execute additional policy modifications; until then no previous policy modifications are invalidated; and until then the straight-forward, temporary generalization assumption is: each modification that until now appeared to contribute to an overall speed-up will remain useful. The paradigm provides a foundation for (1) “meta-learning”, and (2) multi-agent learning. The principles are illustrated in (1) a single, self-referential, “evolutionary” system using an assembler-like programming language to modify its own policy, and to modify the way it modifies its policy, etc., and (2) another “evolutionary” system consisting of multiple agents, where each agent is in fact just a connection in a fully recurrent RL neural net.

In this chapter, we present the design of Teacher (an acronym for TEchniques for the Automated Creation of HEuRistics), a system for learning and for generalizing heuristics used in problem solving. Our system learns knowledge-lean heuristics whose performance is measured statistically. The objective of the design process is to find, under resource constraints, improved heuristic methods (HMs) as compared to existing ones. Teacher addresses five general issues in learning heuristics: (1) decomposition of a problem solver into smaller components and integration of HMs designed for each together; (2) classification of an application domain into subdomains so that performance can be evaluated statistically for each; (3) generation of new and improved HMs based on past performance information and heuristics generated; (4) evaluation of each HM's performance; and (5) performance generalization to find HMs that perform well across the entire application domain. Teacher employs a genetics-based machine learning approach and divides the design process into four phases. In the classification phase, the application domain is divided into subspaces (based on user requirements) and problem subdomains (based on the performance behavior of HMs), In the learning phase, HMs are generated and evaluated under resource constraints with a goal of discovering improved HMs. In the performance-verification phase, good HMs from the learning phase are further evaluated to acquire more accurate and more complete performance information. Finally, in the performance-generalization phase, HMs most likely to provide the best performance over the entire application domain are selected. We conclude the chapter by showing some experimental results on heuristics learned for two problems used in circuit testing.

Automated methods of machine learning may prove to be useful in discovering biologically meaningful information hidden in the rapidly growing databases of DNA sequences and protein sequences.

Genetic programming is an extension of the genetic algorithm in which a population of computer programs is bred, over a series of generations, in order to solve a problem. Genetic programming is capable of evolving complicated problem-solving expressions of unspecified size and shape. Moreover, when automatically defined functions are added to genetic programming, genetic programming becomes capable of efficiently capturing and exploiting recurring sub-pattems.

This chapter describes how genetic programming with automatically defined functions successfully evolved motifs for detecting the D-E-A-D box family of proteins and for detecting the manganese superoxide dismutase family. Both motifs were evolved without prespecifying their length. Both evolved motifs employed automatically defined functions to capture the repeated use of common subexpressions. When tested against the SWISS-PROT database of proteins, the two genetically evolved consensus motifs detect the two families either as well, or slightly better than, the comparable human-written motifs found in the PROSITE database.

This paper is divided into two parts: in part 1, we will consider the role of self organization in evolutionary computations (ECs), and in part 2, we will consider a specific example to illustrate the importance of the information assessment stage in an evolutionary computing system. In part 1, we present a generic EC system, which consists of two stages, viz., the information gathering and assessment stage, and the action stage. Each stage is active in each sampling interval, and the system is allowed to evolve. A number of current EC systems are shown to be modelled by this generic EC system. It is shown then in the information assessment stage, two approaches may be taken, viz., the supervised learning scheme, and the supervised learning scheme. It is argued that in EC systems, the unsupervised learning scheme would be more prevalent. It is also argued that the action stage is problem specific, i.e., it depends on the problem under study.

Part 2 gives a specific illustrative example to show the importance of the information assessment stage in an EC system. This system aims to investigate the behaviour of multiple insects. It is argued that a simple functional model of an insect consisting of a number of instincts arranged in a hierarchy, and a number of associated sensors, it is shown that the information processing stage consists of two parts: a learning vector quantization stage, and a modified hebbian learning stage. It is shown how this combination can be used to overcome the problem that the target output is not given explicitly. Then a number of simulation experiments are shown based first on a single insect, and then on multiple insects. The behaviour of the single insect appears to mimic quite closely the behaviour of a scout ant. The behaviour of the multiple insects appear to exhibit pack group behaviour. This emerging group behaviour appears to be very interesting, as it clearly indicates the role of evolutionary computing in the simulation of complex system behaviours.

The following sections are included:

• Introduction

• Virus-Evolutionary Genetic Algorithm
  • Genetic Algorithm
  • Virus Theory of Evolution
  • Virus-Evolutionary Genetic Algorithm Architecture
  • Virus Infection Operators

• Numerical Simulation
  • Traveling Salesman Proble
  • Simulation Results

• Conclusions

• Bibliography

The following sections are included:

• Introduction

• Constrained Optimization Problem

• Hybrid Evolutionary Programming
  • First Stage of the Hybrid EP
  • Second Stage of the Hybrid EP
  • Simulation Results

• Two-Phase Evolutionary Programming
  • Augmented Lagrangians
  • TPEP method

• Simulation Results and Discussion

• Conclusions

• Bibliography

This chapter describes an ambitious eight year research project which aims to implement a cellular automata based artificial brain with a billion neurons by 2001, which grows/evolves at (nano)electronic speeds inside a Cellular Automata Machine — ATR's so-called “CAN-Brain Project.” The states of the cellular automata (CA) cells and the CA state transition rules can be stored cheaply in gigabytes of RAM. By using state of the art cellular automata machines, e.g., MIT's “CAM8” machine ($40,000, which can update 200 million CA cells a second) it is technically feasible by the end of 1995 to evolve artificial nervous systems containing a hundred thousand neurons, and within a few years, a million neurons. By the end of the current research project, i.e., 2001, it should be possible using nano-scale electronics to grow/evolve artificial brains containing a billion neurons and upwards. This is our aim.

The Iterated Prisoner's Dilemma game has been used extensively in the study of the evolution of cooperative behaviours in social and biological systems. There have been a lot of experimental studies on evolving strategies for 2-player Iterated Prisoner's Dilemma games (2IPD). However, there are many real world problems, especially many social and economic ones, which cannot be modelled by the 2IPD. The n-player Iterated Prisoner's Dilemma (NIPD) is a more realistic and general game which can model those problems. This chapter presents two sets of experiments on evolving strategies for the NIPD. The first set of experiments examine the impact of the number of players in the NIPD on the evolution of cooperation in the group. Our experiments show that cooperation is less likely to emerge in a large group than in a small group. The second set of experiments study the generalisation ability of evolved strategies from the point of view of machine learning. Our experiments reveal the effect of changing the evolutionary environment of evolution on the generalisation ability of evolved strategies.

The following sections are included:

• Index