Information Technology Reference
In-Depth Information
11
Combinatorial Optimization
In gene expression programming the simplest chromosome will code for a
single gene composed of only one terminal. This kind of gene is obtained
when the head length
h
is zero. Then, applying equation (2.4) for determin-
ing tail length, we get a gene length
g
= 1 and genes exclusively composed of
terminals. So, in its simplest representation, gene expression programming
is equivalent to the canonical genetic algorithm in which each gene consists
of just one terminal.
Although of little use in unigenic chromosomes, in multigenic chromo-
somes, one-element genes are extremely useful as they can be organized in
multigene families (MGFs). These multigene families consist of clusters of
related genes encoding, for instance, a particular class of terminals. Thus, in
MGFs, each gene codes for a particular terminal or task. We will see in this
chapter that such chromosomes composed of MGFs are very useful for evolv-
ing solutions to scheduling problems. We will see, however, that the evolu-
tion of such solutions requires special combinatorial-specific operators so
that populations of candidate solutions can evolve efficiently. Indeed, in the
GA community, several researchers created modifications to the basic ge-
netic operators of mutation and recombination in order to create high per-
forming combinatorial-specific operators (see, e.g., Larrañaga 1998 for a
review). However, it is not known which operators perform better as no sys-
tematic comparisons have been done.
In this chapter, a new combinatorial optimization algorithm that explores
a new chromosomal organization based on multigene families will be de-
scribed. We will see that this new chromosomal organization together with
several combinatorial-specific search operators, namely, inversion, gene de-
letion/insertion, sequence deletion/insertion, restricted permutation, and gen-
eralized permutation, allow the algorithm to perform with high efficiency,
astoundingly outperforming the canonical genetic algorithm.
