Combinatorial Optimization - Gene Expression Programming - page 402

11.1 Multigene Families and Scheduling Problems

Multigene families are very useful for finding solutions to combinatorial
problems as different classes of terminals/items can be organized into differ-
ent multigene families. For instance, the different cities in the traveling sales-
person problem can be encoded in a multigene family, where each gene codes
for a city. Consider, for instance, the simple chromosome below, composed
of one MGF with nine members:

012345678
GCDAHEIFB (11.1)

where each element represents one city. In this case, the expression consists
of the spatial organization of all the elements, i.e., the orderly way in which
they interact with one another (Figure 11.1). This kind of chromosomal struc-
ture is going to be used in section 11.3.1 to solve the traveling salesperson
problem.

a.

012345678
GCDAHEIFB

b.

D

C

A

H

F

E

B I

Figure 11.1. Expression of one-element genes as a spatial organization of sub-ETs.
If each symbol represented a city visited by a salesperson, the complete expression
of the chromosome in (a) would correspond to the nine-city tour shown in (b) . The
starting and finishing city is shown in gray.

For combinatorial problems with N classes of terminals, multigenic chro-
mosomes composed of N multigene families can be used. In the task assign-
ment problem of section 11.3.2, a simple six-by-six optimization problem,
two multigene families representing two different classes of elements will
be used. For instance, the following chromosome:

012345 012345
632451 EDFCBA (11.2)

is composed of 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