Information Technology Reference
In-Depth Information
second is composed of the six elements of set
T
representing the tasks to be
assigned T = {A, B, C, D, E, F}. Obviously, how the members of one MGF
interact with the members of the other must be decided a priori and implic-
itly encoded in the chromosome. Figure 11.2 illustrates a very straightfor-
ward interaction between the members of two multigene families, in which
the first member of MGF
1
interacts with the first member of MGF
2
, the sec-
ond member of MGF
1
with the second member of MGF
2
, and so forth.
a.
012345
632451
012345
EDFCBA
b.
6
E
3
D
2
F
4
5
B
1
A
Figure 11.2.
Expression of chromosomes composed of multigene families.
a)
The
chromosome with two multigene families.
b)
A fully developed individual where the
interactions between the sub-ETs are represented by the arrows.
Obviously, different combinatorial problems require different chromosomal
organizations and the specification of the interactions between multigene
families, but this kind of structure is the basis to encode virtually all kinds of
scheduling problems.
11.2 Combinatorial-specific Operators: Performance and
Mechanisms
In combinatorial optimization problems, the elements of a multigene family
must all be present and cannot be represented more than once. Therefore,
special modification mechanisms must be created in order to introduce ge-
netic variation in the population. In this section, I will start by describing the
three most efficient combinatorial-specific genetic operators: inversion, gene
deletion/insertion, and restricted permutation, and finish by describing the
