IBA Laboratory

Genetic Programming (GP)

Genetic Programming is a program induction technique operating upon dynamically allocated parse trees with a genetic algorithm. GP is an extension of the conventional Genetic Algorithm in which the structures undergoing adaptation are hierarchical computer programs of dynamically varying size and shape.

Genetic Programming is an attempt to deal with one of the central questions in computer science: How can computers learn to solve problems without being explicitly programmed? In other words, how can computers be made to do what needs to be done, without being told exactly how to do it?

The search space in GP is the space of all possible computers programs composed of functions and terminals appropriate to the problem domain. In applying GP there are five major preparatory steps. These five steps involve determining The set of terminals The set of primitive functions The fitness measure The parameters for controlling the run and The method for designing a result and the criteria for terminating a run

The first major steps in preparing to use GP is to identify the terminal set for the problem. The terminals correspond to the inputs of the as-yet-undiscovered  computer program.

Second step involves determining the function set which may be any arithmetic operations, standard programming operations, standard mathematical functions, logical functions, or domain-specific functions.

Fitness measurement controls the flow of GP which evaluates how well each computer program in the population performs in its problem.

The Primary parameters for GP is the population size and generation size while secondary parameters are quantitative and qualitative variables used to control the run of GP.

A precondition for solving a problem by GP is that the set of terminals as well as the set of functions satisfy sufficiency requirement in the sense that they are together capable of expressing a solution to the problem.

So GP breeds computer programs to solve problems by executing the following three steps: Generate an initial population of random compositions of the functions and terminals of the problem (computer program). Iteratively perform the following sub steps until the termination criteria has been satisfied:

a)     Execute each program in the population and assign it a fitness value

b)     Create a new population of computer programs by applying the following two primary operations. The operations are applied to computer programs in the population selected with a probability based on fitness

I)                    Reproduce an existing program by coping it into the new population

II)                   Create two new computer programs from existing programs by genetically recombining randomly chosen parts of two existing programs using the crossover operation applied at a randomly chosen crossover point within each program Design the program that is identified by the method of result designation as the result of the run of GP. This result may represent a solution to the problem.

In GP ADF is a function (i.e. subroutine, procedure, module) that is dynamically evolved during a run of GP and which may be called by a calling program that is simultaneously being evolved. GP with ADF may solve regularity-rich problems in a hierarchical way for example microprocessor chip design where certain circuits each performing the same elementary function throughout the chip are reused, computer programming involving a similar process of reuse when a subroutine is repeatedly called from a calling program.

Reference: Genetic Programming II by John R. Koza

Pseudocode for Genetic Programming

{M=Population Size; N=Maximum No. of Run}

Run: =0;

FOR I: =1 TO N DO

BEGIN

Gen: =0

Generate Initial Population Randomly

WHILE NOT (Terminate Condition for Run)

BEGIN

Evaluate fitness of each individual;

FOR J: =1 TO M DO

BEGIN

Op: =Select Genetic Operator;

CASE Op is

UNARY:

BEGIN

Select one individual based on fitness;

Perform Reproduction with Probability Pr;

Copy the offspring into new Population;

END;

BINARY:

BEGIN

Select two individuals based on fitness;

Perform Crossover with Probability Pc;

J: =J+1;

Insert two offspring into new Population;

END;

END;

Gen: =Gen+1;

END;

Designate Result for Run;

Run: =Run+1;

END

END.