ptGAs--Genetic Algorithms Evolving Noncoding
Segments by Means of Promoter/Terminator Sequences
Evolutionary Computation, 6 (4):
361--386 (Winter 1998)DOI: doi:10.1162/evco.1998.6.4.361
Abstract
In this article we present work on chromosome
structures for genetic algorithms (GAs) based on
biological principles. Mainly, the influence of
noncoding segments on GA behavior and performance is
investigated. We compare representations with noncoding
sequences at predefined, fixed locations with
"junk" code induced by the use of
promoter/terminator sequences (ptGAs) that define start
and end of a coding sequence, respectively. As one of
the advantages of noncoding segments a few researchers
have identified the reduction of the disruptive effects
of crossover, and we solidify this argument by a formal
analysis of crossover disruption probabilities for
noncoding segments at fixed locations. The additional
use of promoter/terminator sequences not only enables
evolution of parameter values, but also allows for
adaptation of number, size, and location of genes
(problem parameters) on an artificial chromosome.
Randomly generated chromosomes of fixed length carry
different numbers of promoter/terminator sequences
resulting in genes of varying size and location.
Evolution of these ptGA chromosomes drives the number
of parameters and their values to (sub)optimal
solutions. Moreover, the formation of tightly linked
building blocks is enhanced by self-organization of
gene locations. We also introduce a new, nondisruptive
crossover operator emerging from the ptGA gene
structure with adaptive crossover rate, location, and
number of crossover sites. For experimental comparisons
of this genetic operator to conventional crossover in
GAs, as well as properties of different ptGA chromosome
structures, an artificial problem from the literature
is used. Finally, the potential of ptGA is demonstrated
on an NP-complete combinatorial optimization problem.
