Page 16 - 49A Field Guide to Genetic Programming

2 1 Introduction

Solution
Generate Population Run Programs and
of Random Programs Evaluate Their Quality (* (SIN (- y x))
(IF (> x 15.43)
(+ 2.3787 x)
(* (SQRT y)
(/ x 7.54))))
Breed Fitter Programs

Figure 1.1: The basic control flow for genetic programming, where survival
of the fittest is used to find solutions.

1.1 Genetic Programming in a Nutshell

In genetic programming we evolve a population of computer programs. That
is, generation by generation, GP stochastically transforms populations of
programs into new, hopefully better, populations of programs, cf. Figure 1.1.
GP, like nature, is a random process, and it can never guarantee results.
GP’s essential randomness, however, can lead it to escape traps which de-
terministic methods may be captured by. Like nature, GP has been very
successful at evolving novel and unexpected ways of solving problems. (See
Chapter 12 for numerous examples.)
The basic steps in a GP system are shown in Algorithm 1.1. GP finds out
how well a program works by running it, and then comparing its behaviour
to some ideal (line 3). We might be interested, for example, in how well a
program predicts a time series or controls an industrial process. This com-
parison is quantified to give a numeric value called fitness. Those programs
that do well are chosen to breed (line 4) and produce new programs for the
next generation (line 5). The primary genetic operations that are used to
create new programs from existing ones are:
• Crossover: The creation of a child program by combining randomly
chosen parts from two selected parent programs.
• Mutation: The creation of a new child program by randomly altering
a randomly chosen part of a selected parent program.

1.2 Getting Started

Two key questions for those first exploring GP are:

1. What should I read to get started in GP?
2. Should I implement my own GP system or should I use an existing
package? If so, what package should I use?