We have already introduced multigene families in chapter
2. These structures are very useful for finding solutions to combinatorial problems as one can include different classes of terminals/items in each multigene family. For instance, the cities visited by a salesperson will form a multigene family. The chromosome below is an example of a multigenic chromosome composed of one multigene family:
|
0123456789012345678
PMJLFNDOGKHSRQIECAB |
where each letter represents a city. This kind of chromosomal structure is going to be used in
section 6.3.1 to solve the traveling salesperson problem.
For combinatorial problems with N classes of terminals, multigenic chromosomes composed of
N multigene families can be used. In the task assignment problem of
section 6.3.2, a simple six-by-six optimization problem, two multigene families representing two different classes of elements will be used. For instance, the chromosome:
|
012345012345
632451EDFCBA |
has two multigene families. The first one is composed of the six elements of set
A representing the assistants A = {1, 2, 3, 4, 5, 6} and the second is composed of the six elements of set
T representing the tasks T = {A, B, C, D, E, F}. Obviously, how the members of one multigene family interact with the members
of the other must be decided a priori and implicitly encoded in the chromosome.
Figure 6.1 illustrates a very straightforward interaction between the members of two multigene families, in which the first member of
MGF1 interacts with the first member of MGF2, the second member of
MGF1 with the second member of MGF2, and so forth.
Figure 6.1. 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 specific interactions between multigene families, but this kind of structure is the basis to encode virtually all kinds of scheduling problems.
|