IBA Laboratory

Research overview

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.

ADF (Automatically Defined Function)

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