Evolutionary Computation 1

Basic Algorithms and Operators

Thomas Baeck, Thomas Baeck, D.B Fogel, Z Michalewicz

• Publisher: CRC Press
• Year: 2018
• ISBN:
  9781351989428
• Edition: 1
• Topic: Computer Science
• Subtopic: Programming Games
• Index: Computer Science

The field of evolutionary computation is expanding dramatically, fueled by the vast investment that reflects the value of applying its techniques. Culling material from the Handbook of Evolutionary Computation, Evolutionary Computation 1: Basic Algorithms and Operators contains up-to-date information on algorithms and operators used in evolutionary computing. This volume discusses the basic ideas that underlie the main paradigms of evolutionary algorithms, evolution strategies, evolutionary programming, and genetic programming. It is intended to be used by individual researchers, teachers, and students working and studying in this expanding field.

1

Introduction to evolutionary computation

David B Fogel

1.1 Introductory remarks

As a recognized field, evolutionary computation is quite young. The term itself was invented as recently as 1991, and it represents an effort to bring together researchers who have been following different approaches to simulating various aspects of evolution. These techniques of genetic algorithms (Chapter 7), evolution strategies (Chapter 8), and evolutionary programming (Chapter 9) have one fundamental commonality: they each involve the reproduction, random variation, competition, and selection of contending individuals in a population. These form the essential essence of evolution, and once these four processes are in place, whether in nature or in a computer, evolution is the inevitable outcome (Atmar 1994). The impetus to simulate evolution on a computer comes from at least four directions.

1.2 Optimization

Evolution is an optimization process (Mayr 1988, p 104). Darwin (1859, ch 6) was struck with the ‘organs of extreme perfection’ that have been evolved, one such example being the image-forming eye (Atmar 1976). Optimization does not imply perfection, yet evolution can discover highly precise functional solutions to particular problems posed by an organism’s environment, and even though the mechanisms that are evolved are often overly elaborate from an engineering perspective, function is the sole quality that is exposed to natural selection, and functionality is what is optimized by iterative selection and mutation.

It is quite natural, therefore, to seek to describe evolution in terms of an algorithm that can be used to solve difficult engineering optimization problems. The classic techniques of gradient descent, deterministic hill climbing, and purely random search (with no heredity) have been generally unsatisfactory when applied to nonlinear optimization problems, especially those with stochastic, temporal, or chaotic components. But these are the problems that nature has seemingly solved so very well. Evolution provides inspiration for computing the solutions to problems that have previously appeared intractable. This was a key foundation for the efforts in evolution strategies (Rechenberg 1965, 1994, Schwefel 1965, 1995).

1.3 Robust adaptation

The real world is never static, and the problems of temporal optimization are some of the most challenging. They require changing behavioral strategies in light of the most recent feedback concerning the success or failure of the current strategy. Holland (1975), under the framework of genetic algorithms (formerly called reproductive plans), described a procedure that can evolve strategies, either in the form of coded strings or as explicit behavioral rule bases called classifier systems (Chapter 12), by exploiting the potential to recombine successful pieces of competing strategies, bootstrapping the knowledge gained by independent individuals. The result is a robust procedure that has the potential to adjust performance based on feedback from the environment.

1.4 Machine intelligence

Intelligence may be defined as the capability of a system to adapt its behavior to meet desired goals in a range of environments (Fogel 1995, p xiii). Intelligent behavior then requires prediction, for adaptation to future circumstances requires predicting those circumstances and taking appropriate action. Evolution has created creatures of increasing intelligence over time. Rather than seek to generate machine intelligence by replicating humans, either in the rules they may follow or in their neural connections, an alternative approach to generating machine intelligence is to simulate evolution on a class of predictive algorithms. This was the foundation for the evolutionary programming research of Fogel (1962, Fogel et al 1966).

1.5 Biology

Rather than attempt to use evolution as a tool to solve a particular engineering problem, there is a desire to capture the essence of evolution in a computer simulation and use the simulation to gain new insight into the physics of natural evolutionary processes (Ray 1991) (see also Chapter 4). Success raises the possibility of studying alternative biological systems that are merely plausible images of what life might be like in some way. It also raises the question of what properties such imagined systems might have in common with life as evolved on Earth (Langton 1987). Although every model is incomplete, and assessing what life might be like in other instantiations lies in the realm of pure speculation, computer simulations under the rubric of artificial life have generated some patterns that appear to correspond with naturally occurring phenomena.

1.6 Discussion

The ultimate answer to the question ‘why simulate evolution?’ lies in the lack of good alternatives. We cannot easily germinate another planet, wait several millions of years, and assess how life might develop elsewhere. We cannot easily use classic optimization methods to find global minima in functions when they are surrounded by local minima. We find that expert systems and other attempts to mimic human intelligence are often brittle: they are not robust to changes in the domain of application and are incapable of correctly predicting future circumstances so as to take appropriate action. In contrast, by successfully exploiting the use of randomness, or in other words the useful use of uncertainty, ‘all possible pathways are open’ for evolutionary computation (Hofstadter 1995, p 115). Our challenge is, at least in some important respects, to not allow our own biases to constrain the potential for evolutionary computation to discover new solutions to new problems in fascinating and unpredictable ways. However, as always, the ultimate advancement of the field will come from the careful abstraction and interpretation of the natural processes that inspire it.

References

Atmar J W 1976 Speculation on the Evolution of Intelligence and its Possible Realization in Machine Form Doctoral Dissertation, New Mexico State University

Atmar W 1994 Notes on the simulation of evolution IEEE Trans. Neural Networks NN-5 130–47

Darwin C R 1859 On the Origin of Species by Means of Natural Selection or the Preservation of Favoured Races in the Struggle for Life (London: Murray)

Fogel D B 1995 Evolutionary Computation: Toward a New Philosophy of Machine Intelligence (Piscataway, NJ: IEEE)

Fogel L J 1962 Autonomous automata Industr. Res. 4 14–9

Fogel L J, Owens A J and Walsh M J 1966 Artificial Intelligence through Simulated Evolution (New York: Wiley)

Hofstadter D 1995 Fluid Concepts and Creative Analogies: Computer Models of the Fundamental Mechanisms of Thought (New York: Basic Books)

Holland J H 1975 Adaptation in Natural and Artificial Systems (Ann Arbor, MI: University of Michigan Press)

Langton C G 1987 Artificial life Artificial Life ed C G Langton (Reading, MA: Addison-Wesley) pp 1–47

Mayr E 1988 Toward a New Philosophy of Biology: Observations of an Evolutionist (Cambridge, MA: Belknap)

Ray T 1991 An approach to the synthesis of life Artificial Life II ed C G Langton, C Taylor, J D Farmer and S Rasmussen (Reading, MA: Addison-Wesley) pp 371–408

Rechenberg I 1965 Cybernetic Solution Path of an Experimental Problem Royal Aircraft Establishment Library Translation 1122, Farnborough, UK

——1994 Evolutionsstrategies ‘94 (Stuttgart: Frommann-Holzboog)

Schwefel H-P 1965 Kybernetische Evolution als Strategie der Experimentellen Forschung in der Strömungstechnik Diploma Thesis, Technical University of Berlin

——1995 Evolution and Optimum Seeking (New York: Wiley)

2

Possible applications of evolutionary computation

David Beasley

2.1 Introduction

Applications of evolutionary computation (EC) fall into a wide continuum of areas. For convenience, in this chapter they have been split into five broad categories:

• planning
• design
• simulation and identification
• control
• classification.

These categories are by no means meant to be absolute or definitive. They all overlap to some extent, and many applications could rightly appear in more than one of the categories.

A number of bibliographies where more extensive information on EC applications can be found are listed after the references at the end of this chapter.

2.2 Applications in planning

2.2.1 Routing

Perhaps one of the best known combinatorial optimization problems is the traveling salesman problem or TSP (Goldberg and Lingle 1985, Grefenstette 1987, Fogel 1988, Oliver et al 1987, Mühlenbein 1989, Whitley et al 1989, ...

Table of contents

• Cover Page
• Half Title
• Authors
• Title Page
• Copyright Page
• Contents
• Preface
• List of contributors
• Glossary
• 1 Introduction to evolutionary computation — David B Fogel
• 2 Possible applications of evolutionary computation — David Beasley
• 3 Advantages (and disadvantages) of evolutionary computation over other approaches — Hans-Paul Schwefel
• 4 Principles of evolutionary processes — David B Fogel
• 5 Principles of genetics — Raymond C Paton
• 6 A history of evolutionary computation — Kenneth De Jong, David B Fogel and Hans-Paul Schwefel
• 7 Introduction to evolutionary algorithms — Thomas Bäck
• 8 Genetic algorithms — Larry J Eshelman
• 9 Evolution strategies — Günter Rudolph
• 10 Evolutionary programming — V William Porto
• 11 Derivative methods in genetic programming — Kenneth E Kinnear, Jr
• 12 Learning classifier systems — Robert E Smith
• 13 Hybrid methods — Zbigniew Michalewicz
• 14 Introduction to representations — Kalyanmoy Deb
• 15 Binary strings — Thomas Bäck
• 16 Real-valued vectors — David B Fogel
• 17 Permutations — Darrell Whitley
• 18 Finite-state representations — David B Fogel
• 19 Parse trees — Peter J Angeline
• 20 Guidelines for a suitable encoding — David B Fogel and Peter J Angeline
• 21 Other representations — Peter J Angeline and David B Fogel
• 22 Introduction to selection — Kalyanmoy Deb
• 23 Proportional selection and sampling algorithms — John Grefenstette
• 24 Tournament selection — Tobias Blickle
• 25 Rank-based selection — John Grefenstette
• 26 Boltzmann selection — Samir W Mahfoud
• 27 Other selection methods — David B Fogel
• 28 Generation gap methods — Jayshree Sarma and Kenneth De Jong
• 29 A comparison of selection mechanisms — Peter J B Hancock
• 30 Interactive evolution — Wolfgang Banzhaf
• 31 Introduction to search operators — Zbigniew Michalewicz
• 32 Mutation operators — Thomas Bäck, David B Fogel, Darrell Whitley and Peter J Angeline
• 33 Recombination — Lashon B Booker , David B Fogel, Darrell Whitley, Peter J Angeline and A E Eiben
• 34 Other operators — Russell W Anderson, David B Fogel and Martin Schütz
• Index