Paper abstract

An Introduction to Evolutionary Computation

Wim Hordijk

In K. Krithivasan and R. Rama (eds.), Formal Language Aspects of Natural Computing, 77-84, 2005.

Evolutionary Computation (EC) deals with computational methods that incorporate ideas and principles from natural evolution. More specifically, it includes a class of so-called evolutionary algorithms (EAs), which are heuristic search algorithms that can be used to search for good solutions to difficult problems. These algorithms try to “evolve” better and better solutions, as opposed to constructing one from scratch, and are particularly suitable for problems for which no known efficient (polynomial-time) algorithm exists, and for which exhaustive search is inpractical. These evolutionary algorithms are fairly simple and general, and can be applied to a wide range of search and optimization problems. However, to get an appreciation for how and why they work, it is useful to understand the basics of genetics and natural evolution.

This paper is organized as follows. First, a brief overview of genetics and evolution is presented. Then, the concepts of search spaces, representations, and fitness functions are explained. Next, one particular evolutionary algorithm, namely the genetic algorithm, is explained in some detail, after which its advantages and disadvantages are discussed. A list of applications is then presented to give an idea of the kinds of problems that a genetic algorithm can be applied to successfully. Finally, some pointers to more information about genetic algorithms and evolutionary computation are provided.