Information Technology Reference
In-Depth Information
The variety of functions GAs' chromosomes are able to play is severely
limited by this dual function they have (genotype and phenotype) and by
their structural organization, especially the simple language of the chromo-
somes and their fixed length. Indeed, GAs' chromosomes very much resem-
ble simple RNA replicators, in which the linear RNA genome is also capable
of exhibiting limited structural and functional diversity. In both cases, the
whole structure of the replicator determines the functionality and, therefore,
the fitness of the individual. For instance, in such systems it is not possible to
use only a particular region of the replicator as a solution to a problem; the
whole replicator is always the solution: nothing more, nothing less. As a
result, these systems are highly constrained.
1.5 Genetic Programming
Genetic Programming, invented by Cramer in 1985 (Cramer 1985) and fur-
ther developed by Koza (1992), finds an alternative to fixed length solutions
through the introduction of nonlinear structures (parse trees) with different
sizes and shapes. The alphabet used to create these structures is also more
varied than the 0's and 1's of GAs' individuals, creating a richer, more versa-
tile system of representation. Notwithstanding, GP individuals also lack a
simple, autonomous genome: like the linear chromosomes of GAs, the
nonlinear structures of GP are also naked replicators cursed with the dual
role of genotype/phenotype.
The parse trees of GP resemble protein molecules in their use of a richer
alphabet and in their complex and unique hierarchical representation. In-
deed, parse trees are capable of exhibiting a great variety of functionalities.
The problem with these complex replicators is that their reproduction with
modification is highly constrained in evolutionary terms, simply because the
modifications must take place on the parse tree itself and, consequently, only
a limited range of modification is possible. Indeed, the genetic operators of
GP operate at the tree level, modifying or exchanging particular branches
between trees. For instance, the simple, yet high-performing, point mutation
cannot be used as, most of the times, it would generate structural
impossibilities. As a comparison, it is worth emphasizing that, in nature, the
expression of any protein gene always results in a valid protein structure.
Despite its lack of linear chromosomes, GP is also a genetic algorithm
as it uses populations of individuals, selects them according to fitness, and
