

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
asyetundiscovered computer program. Second
step involves determining the function set which may be any arithmetic
operations, standard programming operations, standard mathematical functions,
logical functions, or domainspecific 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 regularityrich
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. USEFUL LINKS
Evolutionary
computing in a nutshell  What is it? Evolutionary Programming Society geneticprogramming.orgHomePage International Society for Genetic
and Evolutionary Computation ISGEC Library of Genetic Algorithm(Galib) The Genetic Algorithm Archives Welcome to our EHW (evolvable hardware) Web
site! 
