The Entities of Gene Expression Programming - Gene Expression Programming - page 33

ming and evolvability, for they allow the modification of the genome through
the use of virtually any kind of genetic operator without any kind of restric-
tion, always producing syntactically correct programs. And this opens up
new grounds for the exploration of the search space as all the recesses of the
fitness landscape are now accessible. Thus, in gene expression programming,
the fundamental property of genotype/phenotype systems - syntactic clo-
sure - is intrinsic, allowing the totally unconstrained manipulation of the
genotype and, consequently, an efficient evolution. Indeed, this is the para-
mount difference between gene expression programming and previous GP
implementations, with or without linear genomes, all of them either limiting
themselves to inefficient genetic operators or checking exhaustively all the
newly created programs for syntactic errors (for a review on genetic pro-
gramming with linear genomes see Banzhaf et al. 1998).
Let us now analyze the structural organization of GEP genes in order to
understand how they invariably code for syntactically correct computer pro-
grams and why their revolutionary structure allows the unconstrained appli-
cation of virtually any search operator and, therefore, guarantees the genera-
tion of the quintessential genetic variation fundamental for the evolution of
good solutions.

2.1.2 Structural and Functional Organization of Genes

So, what is so special about the structure of GEP genes? Well, they are com-
posed of two different domains - a head and a tail domain - each with differ-
ent properties and functions. The head domain is used mainly to encode the
functions chosen for the problem at hand, whereas the tail works as a buffer
or reservoir of terminals in order to guarantee the formation of only valid
structures. Thus, the head domain contains symbols that represent both func-
tions and terminals, whereas the tail is composed of only terminals.
For each problem, the length of the head h is chosen, whereas the length
of the tail t is a function of h and the number of arguments of the function
with more arguments n max (also called maximum arity) and is evaluated by
the equation:

t h ( max n 1 1

(2.4)

Consider a gene for which the set of functions F = {Q, *, /,-, +} and the set
of terminals T = {a, b}, thus giving n max = 2. And if we chose an h = 15, then
t = 15 · (2 - 1) + 1 = 16 and the length of the gene g is 15 + 16 = 31. One such
gene is shown below (the tail is shown in bold):