ABSTRACT

Genetic programming is a predefined and systematic method to obtain a solution to a problem automatically using computers. Genetic Programming (GP) is a member of evolutionary computation or evolutionary algorithms and this method also follows Darwin’s theory of evolution the “survival of the fittest”. A set of computer programs are chosen as population of individuals and these individuals reproduce among themselves. As this process increases, the best individuals will survive and seem to be successful in evolving well in the given environment. GP definition - “Genetic programming is an automated method for cre-

ating a working computer program from a high-level problem statement of a problem. Genetic programming does this by genetically breeding a population of computer programs using the principles of Darwinian natural selection and biologically inspired operations.” Practically, the genetic programming model can be implemented with

arrays of bits or characters to represent the chromosomes. The genetic operations such as crossover, mutation, etc., can be performed using simple bit manipulations. Genetic Programming is the extension of the genetic model of learning into the space of programs. The components that represent the population are not fixed-length character strings and they encode possible solutions to the given problem. These components in the population are programs and when they are executed, they are the candidate solutions to the problem. These programs are expressed in genetic programming as parse trees, rather than as lines of code. Genetic Programming generates programs by following an evolution-

ary approach. The process is as follows: The task or the problem that is to be solved should be specified by the user along with the evaluation function. The user has to specify the kind of operation that is to be performed by the programs. Once the specifications are provided, an initial population of programs is randomly generated. Each and every program undergoes a translation, compilation, and execution process.

process enables the calculation of a fitness value for each of the programs, and the best of them are chosen for reproduction. The chosen programs undergo a mutation operation and the offspring produced are added to the next generation of programs. This process repeats until a termination condition is attained. In this section, a brief history of genetic programming is discussed. To get an idea about programming a basic introduction to Lisp Programming Language is dealt. The basic operations of GP are discussed along with an illustration. The programs in GP are evolved to solve pre-defined problems. The

term evolution refers to an artificial process modeled from natural evolution of living organisms. This process has been abstracted and stripped off of most of its intricate details. It has been transferred to the world of algorithms where it can serve the purpose of approximating solutions to given or even changing problems (machine learning) or for inducing precise solutions in the form of grammatically correct (language) structures (automatic programming). Genetic programming is a domain-independent method that genet-

ically breeds a population of computer programs to solve a problem. Moreover, genetic programming transforms a population of computer programs into a new generation of programs by applying analogs of naturally occurring genetic operations iteratively. This process is illustrated in Figure 14.1. The genetic operations include crossover (sexual recombination), mu-

tation, reproduction, gene duplication, and gene deletion. Analogs of developmental processes are sometimes used to transform an embryo into a fully developed structure. Genetic programming is an extension of the genetic algorithm in which the structures in the population are not fixed-length character strings that encode candidate solutions to a problem, but programs that, when executed, are the candidate solutions to the problem. The programs are represented in a tree form in GP, which is the most

common form, and the tree is called program tree (or parse tree or syntax tree). Some alternative program representations include finite automata (evolutionary programming) and grammars (grammatical evolution). For example, the simple expression min(x/y*5, x+y)is represented as shown in Figure 14.2. The tree includes nodes (which are also called points) and links. The nodes indicate the instructions to execute. The links indicate the arguments for each instruction. In the following, the internal nodes in a tree will be called functions, while the tree’s leaves will be called terminals. The trees and their expressions in genetic programming can be repre-

sented using prefix notation (e.g., as Lisp S-expressions). A basic idea of

FIGURE 14.1: Main Loop of Genetic Programming